Derived `PartialOrd` implementations don't match originals

[djkoloski]

This is a nasty one.

The builtin PartialOrd implementation compares enums by discriminant first, and uses that to determine whether entire variants are greater or less than each other. This is a problem because the discriminants for the original and archived enums may not be ordered the same way, so even if we could compare the discriminants of the two, they wouldn't be guaranteed to provide the same ordering between original and archived values.

Right now we manually assign a new discriminant that may not be the same as the true discriminant, and use that to determine whether two enums are greater or less. This still doesn't provide the same orderings between original and archived values, but it's what we can do.

[tephrocactus]

@djkoloski

Please, clarify how this bug affects library users. Thank you!

[djkoloski]

Sure! I'll break this up so anyone who runs across this one can see the big picture:

Explanation of the problem

Here's a rust playground link, select Tools > Expand macros. This will show the builtin derive for PartialOrd.

The builtin implementation of PartialOrd gets the discriminants of the two values to compare using discriminant_value, a core intrinsic. This has a stabilized version, mem::discriminant that can be used on stable.

When calculating the partial_cmp of an enum, the discriminants of the enums are first compared for equality. We can still do this on stable because Discriminant implements PartialEq. However, if the discriminants do not match, they are compared with partial_cmp which is not implemented for the stabilized Discriminant type. So we couldn't replicate the same behavior with just stable APIs.

How it interacts with rkyv

The Archive derive allows users to generate comparison operators between their original and archived types by specifying #[archive(compare(...))]. This is mostly for convenience, since many users end up needing to compare them for tests or in functional code. One of the comparison operators supported is PartialOrd, so we need to generate some impl PartialOrd<Archived<T>> for T.

Because archived types are supposed to be perfectly interchangeable with their unarchived counterparts, we need to guarantee that the PartialOrd implementation we generate perfectly matches the builtin one, just with the enum type switched out. This is important because having implementations of PartialOrd that produce different outputs would mean that operations like sorting and containers like BTreeMaps would also give different outputs with unarchived versus archived types (or a mix).

To match the builtin implementation, we need to compare the discriminants of the enums first. This isn't great, but we can bound the Discriminants to be the same type and implement PartialOrd. They won't ever be able to satisfy the second part, but that could be fixed pretty easily in the standard library. However, then we run into the real problem: we don't know how the discriminants are ordered! In order to guarantee that the two orderings are the same, we'd have to translate the archived discriminant back to the original discrimants, and we can't do that without an unarchived value to get the discriminant of. So we're stuck until we get a builtin macro to produce an enum discriminant without a corresponding type.

What it means for library users

Right now, rkyv produces implementations of PartialOrd for enums that should but are not guaranteed to match the implementations generated by the builtin derive macro. There may be particular tricky cases where they do not match, such as explicit enum discriminants listed out-of-order, as well as subtle ones that are not known. There's also enough wiggle room that compiler updates could feasibly break them for some enums even though they work right now.

It's important to note that this problem only applies to enums, and using rkyv to generate PartialOrd implementations for structs is guaranteed to be sound.

[djkoloski]

Partially mitigated by bc5b2f4. This uses the generated tag enum as a stand-in for the discriminant value for the archived enum. There's no guarantee that this tag will have the same relationships between its enum variants as the discriminants of the archived enum, but it should be the same in all the cases I can think of.

[AaronKutch]

The language may be providing a way to fix this soon: rust-lang/rfcs#3607