Replace (`Partial`)`Ord` for `EntityGeneration` with corrected standalone method

[urben1680]

Objective

#19421 implemented Ord for EntityGeneration along the lines of the impl from slotmap:

/// Returns if a is an older version than b, taking into account wrapping of
/// versions.
pub fn is_older_version(a: u32, b: u32) -> bool {
    let diff = a.wrapping_sub(b);
    diff >= (1 << 31)
}

But that PR and the slotmap impl are different:

slotmap impl

• if (1u32 << 31) is greater than a.wrapping_sub(b), then a is older than b
• if (1u32 << 31) is equal to a.wrapping_sub(b), then a is older than b
• if (1u32 << 31) is less than a.wrapping_sub(b), then a is equal or newer than b

previous PR impl

• if (1u32 << 31) is greater than a.wrapping_sub(b), then a is older than b
• if (1u32 << 31) is equal to a.wrapping_sub(b), then a is equal to b :warning:
• if (1u32 << 31) is less than a.wrapping_sub(b), then a is newer than b :warning:

This ordering is also not transitive, therefore it should not implement PartialOrd.

Solution

Fix the impl in a standalone method, remove the Partialord/Ord implementation.

Testing

Given the first impl was wrong and got past reviews, I think a new unit test is justified.

[urben1680]

What we also missed is that Ord needs to be transitive. This is not the case with a wrapping number however.

When a < b and b < c, then a < c must be true. However if b - a < DIFF_MAX, c - b < DIFF_MAX but c - a > DIFF_MAX this is violating this principle because suddenly a > c. The test I added so far shows that behavior.

Tick for example does not implement Ord, it only has a Tick::is_newer_than method.

The solution here can be to do the same, add a method that is not an Ord impl and move the ordering documentation from EntityGeneration to that new method and make it clear this is not transitive.

Please tell me if you think this is not a good solution and point out alternatives. :wave:

[Victoronz]

Ah, that is my mistake, I had misunderstood the impl being an Ord impl from slotmap, so had assumed transitivity to be a given. In that case, this should not be the behavior of the Ord impl, and should be a dedicated method instead.

[ElliottjPierce]

@urben1680

Yeah, I think a new method is the best. I would personally want cmp_age_approx (or similar) that gives an Ordering, and then some utility methods like is_newer_than, etc built on it. That way, users could still, for example, sort a list with it.

The other thing is the Ord impl; it should still be Ord. We just need to document that the implementation does not respect age. It just produces a deterministic order.

[urben1680]

some utility methods like is_newer_than, etc built on it

Ordering has these utility methods itself though, if you are fine with having to interpret greatness as recentness.

The other thing is the Ord impl; it should still be Ord. We just need to document that the implementation does not respect age. It just produces a deterministic order.

Based on the raw interger I assume? I think this is controversial. Tick also does not implement Ord. It could do with the same argument but would be a footgun for those who do not stumble on the documentation.

When a type can have different kinds of ordering, like ordering books by their release date or their title, they should not implement Ord to make the decision how to order them explicit.

EntityGeneration is such a case too if you have both the non-transitive and the raw-value ordering.

[Victoronz]

some utility methods like is_newer_than, etc built on it

Ordering has these utility methods itself though, if you are fine with having to interpret greatness as recentness.

The other thing is the Ord impl; it should still be Ord. We just need to document that the implementation does not respect age. It just produces a deterministic order.

Based on the raw interger I assume? I think this is controversial. Tick also does not implement Ord. It could do with the same argument but would be a footgun for those who do not stumble on the documentation.

When a type can have different kinds of ordering, like ordering books by their release date or their title, they should not implement Ord to make the decision how to order them explicit.

EntityGeneration is such a case too if you have both the non-transitive and the raw-value ordering.

We already have precedent for this weirdness though, and that is Entity. Entity can be ordered multiple ways, including ones that are non-transitive, raw-value, or otherwise. We haven't decided on the semantics of the type yet, so we do not make any guarantees about the meaning of the ordering. Even if the ordering is meaningless, the ability to be ordered is useful. Even if we expose other ways of ordering EntityGeneration, we can define the default order to be meaningless.

Meaning we can decide either way!

Arguably, Rust floats are a bit similar to this, where f32 implements a PartialOrd (no Ord) that does not fulfill the common float ordering needs by itself. To mend this, there exists a f32::total_cmp method (based on the IEEE float standard order) that produces a total order, but that does not agree with the PartialOrd impl.

If we do not want this generation type to implement Ord, we should then expose a way of converting it to a value that does (properly documented), otherwise we will have removed capability people may have previously relied on, with no API-based recourse.

Sidenote: I see the after_versions and after_versions_and_could_alias methods take u32, yet I see no way to get a u32 out of EntityGeneration itself, is that intended?

[ElliottjPierce]

My vote then is to remove the Ord impl in this pr and revisit it later. That sounds like the most controversial part of this.

We should fix the bug and unblock avian quickly; then we can debate over if and how it should be implemented in a followup pr.

[urben1680]

I removed (Partial)Ord and introduced cmp_age_approx. While the type is Copy, I still used &Self for the argument to make it easier to use for places that expects an ordering function.

On a personal note, I cannot see how you could guarantee that in some specific context the ordering is correct. But this is probably a close-enough matter for many use cases.

[urben1680]

Thinking of it this probably should have the returned ordering reversed or not be called "cmp_age_approx". :thinking: First is "older" than First + 1.

[ElliottjPierce]

Thinking of it this probably should have the returned ordering reversed or not be called "cmp_age_approx". 🤔 First is "older" than First + 1.

That's fair. I don't have a strong opinion.

[urben1680]

Renamed it to cmp_approx.