search

georust / rstar

R*-tree spatial index for the Rust ecosystem
https://docs.rs/rstar
Apache License 2.0
384 stars 67 forks source link

Fix a stack overflow error in DrainIterator #127

Closed nickguletskii closed 1 year ago

nickguletskii commented 1 year ago

Fixes a stack overflow error when using RTree::drain_with_selection_function or any other method that uses DrainIterator.

rmanoka commented 1 year ago

Could we add a test-case to ensure it does not regress? It's not clear what the bug was from the code diff.

nickguletskii commented 1 year ago

Could we add a test-case to ensure it does not regress? It's not clear what the bug was from the code diff.

I've added the quick-and-dirty fuzz test that I've implemented in order to track down this bug. Unfortunately, I don't have a simpler test case - it seems that this bug doesn't manifest itself that often.

adamreichold commented 1 year ago

Could we add a test-case to ensure it does not regress? It's not clear what the bug was from the code diff.

I've added the quick-and-dirty fuzz test that I've implemented in order to track down this bug. Unfortunately, I don't have a simpler test case - it seems that this bug doesn't manifest itself that often.

I am not a fan of adding this library-specific fuzz test in this PR here. Especially since the change really is a quality of implementation issue, i.e. it is basically a manual tail call optimization.

I would like to include the fuzz test, but as a separate PR that can be reviewed without the time pressure of a bugfix release. For this PR, a single test case for example using a synthetic selection function would be fine for me, but I would also merge this without a test case triggering the stack overflow. (This depends on the environment in any case, i.e. I guess this is might be possible to trigger by running an existing test in a thread with an artificially small stack size set via thread::Builder::stack_size.)

nickguletskii commented 1 year ago

Could we add a test-case to ensure it does not regress? It's not clear what the bug was from the code diff.

I've added the quick-and-dirty fuzz test that I've implemented in order to track down this bug. Unfortunately, I don't have a simpler test case - it seems that this bug doesn't manifest itself that often.

I am not a fan of adding this library-specific fuzz test in this PR here. Especially since the change really is a quality of implementation issue, i.e. it is basically a manual tail call optimization.

I would like to include the fuzz test, but as a separate PR that can be reviewed without the time pressure of a bugfix release. For this PR, a single test case for example using a synthetic selection function would be fine for me, but I would also merge this without a test case triggering the stack overflow. (This depends on the environment in any case, i.e. I guess this is might be possible to trigger by running an existing test in a thread with an artificially small stack size set via thread::Builder::stack_size.)

Sorry for the delay again. I've removed the commits containing the fuzz test from this PR.

As for manually setting the stack size, I haven't had much luck reproducing this bug with the existing tests or tests derived from them even with a 64kb stack. I suspect that it might only exhibit itself after a lot of interleaved inserts and removals of random leaves with loose-fitting AABBs.

rmanoka commented 1 year ago

Apologies, it took me a bit to understand that this is a tail-call optimization. I'm okay with adding this without a test-case too. Currently, I think we do not re-balance during removal, so our data-structure can get very deep (depth = O(nodes)) if used as a dynamic tree.

adamreichold commented 1 year ago

bors r=adamreichold,rmanoka

bors[bot] commented 1 year ago

Build succeeded!

The publicly hosted instance of bors-ng is deprecated and will go away soon.

If you want to self-host your own instance, instructions are here. For more help, visit the forum.

If you want to switch to GitHub's built-in merge queue, visit their help page.