Replace (`Partial`)`Ord` for `EntityGeneration` with corrected standalone method by urben1680 · Pull Request #19432 · bevyengine/bevy

urben1680 · 2025-05-29T16:17:12Z

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 ⚠️
if (1u32 << 31) is less than a.wrapping_sub(b), then a is newer than b ⚠️

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.

ElliottjPierce

Wow! Good catch, and I like the new constant! Test looks good too. Very helpful.

One is not a real contributor until they break bevy lol.

urben1680 · 2025-05-30T01:18:48Z

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. 👋

Victoronz · 2025-05-30T01:48:08Z

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 · 2025-05-30T02:48:05Z

@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 · 2025-05-30T11:13:05Z

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 · 2025-05-30T13:25:38Z

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 · 2025-05-30T14:50:43Z

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 · 2025-05-30T17:36:17Z

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 · 2025-05-30T17:41:19Z

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

ElliottjPierce · 2025-05-30T17:43:10Z

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.

ElliottjPierce

Everything looks good to me!

urben1680 · 2025-05-30T17:47:57Z

Renamed it to cmp_approx.

…lone method (bevyengine#19432) # Objective bevyengine#19421 implemented `Ord` for `EntityGeneration` along the lines of [the impl from slotmap](https://docs.rs/slotmap/latest/src/slotmap/util.rs.html#8): ```rs /// 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` ⚠️ - if `(1u32 << 31)` is less than `a.wrapping_sub(b)`, then `a` is newer than `b` ⚠️ 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 added 2 commits May 29, 2025 18:12

fix impl Ord for EntityGeneration

d7daa9e

docs

bee2f6e

alice-i-cecile requested review from ElliottjPierce, ItsDoot, Jondolf and Victoronz May 29, 2025 17:12

alice-i-cecile added C-Bug An unexpected or incorrect behavior A-ECS Entities, components, systems, and events S-Needs-Review Needs reviewer attention (from anyone!) to move forward labels May 29, 2025

alice-i-cecile added this to the 0.17 milestone May 29, 2025

ci fix

9ca2110

ElliottjPierce approved these changes May 29, 2025

View reviewed changes

urben1680 and others added 2 commits May 30, 2025 19:14

replace PartialOrd and Ord impl with standalone method

2955111

Merge branch 'main' into entity_generation_ord_fix

ad9c160

urben1680 changed the title ~~fix impl Ord for EntityGeneration~~ Replace Ord for EntityGeneration with fixed standalone method May 30, 2025

urben1680 changed the title ~~Replace Ord for EntityGeneration with fixed standalone method~~ Replace (Partial)Ord for EntityGeneration with fixed standalone method May 30, 2025

urben1680 requested a review from ElliottjPierce May 30, 2025 17:36

ElliottjPierce approved these changes May 30, 2025

View reviewed changes

rename method

e7fa859

urben1680 changed the title ~~Replace (Partial)Ord for EntityGeneration with fixed standalone method~~ Replace (Partial)Ord for EntityGeneration with corrected standalone method May 30, 2025

urben1680 and others added 2 commits May 31, 2025 14:23

made cmp_approx align to usual cmp functions

1221e87

Merge branch 'main' into entity_generation_ord_fix

476d592

alice-i-cecile approved these changes Jun 7, 2025

View reviewed changes

alice-i-cecile added this pull request to the merge queue Jun 7, 2025

alice-i-cecile added S-Ready-For-Final-Review This PR has been approved by the community. It's ready for a maintainer to consider merging it and removed S-Needs-Review Needs reviewer attention (from anyone!) to move forward labels Jun 7, 2025

Merged via the queue into bevyengine:main with commit 76b8310 Jun 7, 2025
34 checks passed

Uh oh!

Conversation

urben1680 commented May 29, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Objective

Solution

Testing

Uh oh!

ElliottjPierce left a comment

Choose a reason for hiding this comment

Uh oh!

urben1680 commented May 30, 2025

Uh oh!

Victoronz commented May 30, 2025

Uh oh!

ElliottjPierce commented May 30, 2025

Uh oh!

urben1680 commented May 30, 2025

Uh oh!

Victoronz commented May 30, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ElliottjPierce commented May 30, 2025

Uh oh!

urben1680 commented May 30, 2025

Uh oh!

urben1680 commented May 30, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ElliottjPierce commented May 30, 2025

Uh oh!

ElliottjPierce left a comment

Choose a reason for hiding this comment

Uh oh!

urben1680 commented May 30, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

urben1680 commented May 29, 2025 •

edited

Loading

Victoronz commented May 30, 2025 •

edited

Loading

urben1680 commented May 30, 2025 •

edited

Loading