search

georust / rstar

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

Revert back to min/max representation of empty AABB #184

Closed adamreichold closed 3 weeks ago

adamreichold commented 3 weeks ago

This reverts back to the min/max representation of empty AABB due to regressions introduced by the numerically more tame but not invariant for merging representation.

To avoid regressing #161, it also adds a single check to avoid computing the distance to an empty envelope (of the root node of an empty tree). Integer coordinates are always prone to overflow but in the empty case we are forcing this onto the caller whereas every non-empty tree will have AABB that the caller supplied and where we can reasonably ask them to control for overflow or use a custom Point impl based on saturating arithmetic.

Fixes #183

adamreichold commented 3 weeks ago

This would be my personally preferred alternative to #181 and #182 trying to keep #161 working.

Generally speaking, I am really unsure whether the problems caused by fixed-precision integer coordinates are worth it, but this fix seems to be rather targeted and should not add measurable costs to the majority of floating-point coordinate users.

adamreichold commented 3 weeks ago

(Whatever choice we make, we should probably yank 0.12.1 after releasing 0.12.2 to crates.io.)

urschrei commented 3 weeks ago

OK – shall we merge this, release a patch version, and yank?

adamreichold commented 3 weeks ago

OK – shall we merge this, release a patch version, and yank?

If there are no objections from elsewhere, yes, I think that would be best to provide a quick resolution for affected projects.

I think the risk of an error in the fix is small for most users (as we are going back to the previous behaviour) and we'll just have to deal with any fallout from fixed-precision integer coordinate users. I tried to avoid it but I am admittedly not confident that it can be avoided.

urschrei commented 3 weeks ago

0.12.1 is yanked

adamreichold commented 3 weeks ago

0.12.1 is yanked

I think it is customary to yank only after an upgrade is available. Otherwise, the degree of eyebrow raising can be problematic. But I suspect you'll push 0.12.2 soon as well?

urschrei commented 3 weeks ago

Released!

michaelkirk commented 3 weeks ago

I think it is customary to yank only after an upgrade is available.

At first I thought this made sense, but now I'm not sure.

Assuming the fix is patch compatible (0.0.x++), if you wait to have the fix published before running cargo yank, it seems like the only practical consequence of cargo yank is to annotate what's shown on crates.io (and other indexes).

Screenshot 2024-11-05 at 14 09 07

If you already have the patch-compatible version published, cargo update will update to that fixed version, skipping the broken one anyway, right?

So it can be used to prevent people from updating. But it's not useful for "skipping" the broken one, since cargo already installs the most recent semver compatible one when running cargo update.

michaelkirk commented 3 weeks ago

To summarize, it's my conclusion that cargo yank should be used precisely in the time after you know you have a problem, but before a fix is available.

urschrei commented 3 weeks ago

Delightfully, we can unyank.

adamreichold commented 3 weeks ago

A lot of CI runs tools like cargo audit or cargo deny which will warn about yanked dependencies. Warnings which are not actionable because no semver-compatible replacement is available is what I was referring to. Admittedly, this is not so bad if an earlier patch release is available because you can most likely downgrade successfully, but for example yanking 0.12.0 is significantly worse.

adamreichold commented 3 weeks ago

Delightfully, we can unyank.

I would not recommend that due to as written, cargo update is not the only concern. Yanking sends a relevant signal to different tools and also users with existing locked dependencies.

michaelkirk commented 3 weeks ago

It's my conclusion that cargo yank should be used precisely in the time after you know you have a problem, but before a fix is available.

I phrased this poorly — In case there was confusion, I'm not recommending unyanking in this case.

I'll try again:

You should yank as soon as you know there is a problem, to keep people from updating to the broken version, even before a fix is available, ensuring legacy users stay on the old version until the fix is available.

yanking after a fix is published isn't harmful it's just not very useful.

As @adamreichold points out, there is some utility to yanking, even if you've already shipped the fix.