Subtraction with underflow in constructor for `ImmutableKdTree`

[claytonwramsey]

Hi! I found what seems to be a bug in ImmutableKdTree with a certain set of points for construction. When constructed with a certain set of points, it fails with the following message on debug builds:

thread 'main' panicked at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:379:67:
attempt to subtract with overflow
stack backtrace:
   0: rust_begin_unwind
             at /rustc/098d4fd74c078b12bfc2e9438a2a04bc18b393bc/library/std/src/panicking.rs:647:5
   1: core::panicking::panic_fmt
             at /rustc/098d4fd74c078b12bfc2e9438a2a04bc18b393bc/library/core/src/panicking.rs:72:14
   2: core::panicking::panic
             at /rustc/098d4fd74c078b12bfc2e9438a2a04bc18b393bc/library/core/src/panicking.rs:144:5
   3: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::update_pivot
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:379:67
   4: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::optimize_stems
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:262:21
   5: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::optimize_stems
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:343:19
   6: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::optimize_stems
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:343:19
   7: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::optimize_stems
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:343:19
   8: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::optimize_stems
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:343:19
   9: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::optimize_stems
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:293:38
  10: kiddo::immutable::float::kdtree::ImmutableKdTree<A,T,_,_>::new_from_slice
             at /home/clayton/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.0.0/src/immutable/float/kdtree.rs:130:35

I was able to capture exactly the set of points that causes the assertion to fail, so this may be of some use for you.

It's a lot of points, but here's a complete repro below: https://gist.github.com/claytonwramsey/33222355472fef9aa14a002b2b16d58c

[sdd]

Hi Clayton, I'm hoping to have time to look into fixing this over the next week or so.

[sdd]

I got there in the end Clayton :-)

Will release as part of 4.1.0, sorry for the delay

[sdd]

Fix released in 4.2.0 👍🏼

[claytonwramsey]

Thanks!