New panics from sort detecting Ord/PartialOrd violations

[Mark-Simulacrum]

1.81 brings the new sort implementations, added in #124032. The new implementations will panic if they detect that Ord doesn't deliver a total order (with new # Panics sections added to documentation:

May panic if the implementation of Ord for T does not implement a total order.

These panics represent "bugs" in user code, but it seems plausible that the new source of panics in user programs may be rather unexpected. At minimum, it seems likely that we want some mention of this in the compatibility notes section of 1.81's release notes, but I'm not sure how to best phrase it; "total order violations" is probably considerably too opaque for most of our audience.

I didn't see any discussion of these panics in the PR landing this work, though it may have happened elsewhere, so opening this to (a) make T-libs-api aware, if they weren't already and (b) ask for guidance on the right way to communicate this and any longer-form advice we can recommend/provide on what to do when such a panic is encountered. (Note that this affected at least one sort in our own code, encountered during the bootstrap bump: #128083 (comment)).

I'd also love some clarity on the PR description's phrasing of "detecting strict weak ordering violations with a high chance" -- what does high chance here mean?

cc @Voultapher @orlp

[orlp]

These panics represent "bugs" in user code, but it seems plausible that the new source of panics in user programs may be rather unexpected.

I mean, you can remove the quotes, they can only occur if the user implemented Ord in a way that violates the requirements specified in the Ord docs.

I'd also love some clarity on the PR description's phrasing of "detecting strict weak ordering violations with a high chance" -- what does high chance here mean?

I believe @Voultapher wrote that, and that he meant 'with high probability'. That said, I don't think we've ever properly evaluated the probability of the panic occurring if there's a bug in the Ord implementation, and obviously not all bugs have the same chance. So I think it should probably be reworded to "there's a good chance" to highlight the informality of that claim.

In essence, if your Ord implementation is incorrect, there's a good chance that the new sorting algorithm will end up in a state where we can't progress the sort due to an invariant being broken. We had two choices in this scenario: return knowingly unsorted data, or throw a panic. We chose the latter.

I do remember asking people for advice which of the two we should choose, but not where or if the entire T-libs-api team was involved. At least @thomcc and @workingjubilee are aware, from the top of my head.

any longer-form advice we can recommend/provide on what to do when such a panic is encountered

The advice is to fix the Ord implementation so that it provides a proper total order. I'm not sure what the best method is to teach people what that means, or what the most common mistakes are. At the very least you can mention that the operation needs to be transitive, so if you return a < b and b < c you better make sure a < c.

[Voultapher]

There is an open PR #129003 that aims to improve the Ord documentation, including examples of common anti-patterns found in real code that gets Ord wrong.

[workingjubilee]

"total order violations" is probably considerably too opaque for most of our audience.

"failure to comply with the requirements of Ord".
"failure to correctly implement Ord".
"incorrectly implementing Ord".

The first time that the relnotes mention these requirements, they should also mention something like "and PartialOrd (which must be consistent with Ord)".

[Amanieu]

This has been included in the release notes and libs is satisfied with the wording, closing.

[Turbo87]

FWIW I'm a bit surprised by this new behavior and worried that it will cause quite a few crashes in production where it was previously just returning buggy output.

Did we consider shipping with a debug-only assertion for a couple of versions before going into full panic mode?

[workingjubilee]

@Turbo87 I am not sure if you are aware of the following, so apologies if I am belaboring you with things you already know:

We cannot enable normal cfg!(debug_assertions) in core/std due to its precompiled nature. At least, not ones that are visible to people compiling code by linking std in, instead of, well, compiling std itself. The form of debug_assert! in std that works in a way that would make it useful for what you describe is modeled by assert_unsafe_precondition!. It is... not as nice as normal panic!s due to a few details, like how it simply aborts, and because not everything relevant has #[track_caller] to show you what caused the issue because of binary size / compile time concerns. It is easy for a situation to become complex enough to make it hard to hunt down the crashes caused by assert_unsafe_precondition!, much harder than any ordinary panic message. I once spent a week just trying to tease apart a crash introduced by such because it happened under a few different layers.

I do not mean to bag on any of Saethlin's work by saying this! We've wanted this power for some time, and we're rapidly getting comfortable with the idea it is an option, but it is still not a peer option with "simply put an assert! in the code" in terms of diagnostics. I believe we can rapidly make this much better if we have a mind to do so (we may have to decide to accept other tradeoffs, like binary size, compile time, etc.). I am just saying that assert_unsafe_precondition! in its current form is mostly justified by the fact that the alternative is compiling code with undefined behavior, which is capable of doing far more than just "buggy output".

So, my personal opinion is if I were maintaining a codebase that was gotcha'd by this, I'd rather just get the current situation. Maybe it's a punch in the mouth, but at least I could clearly see it coming.

[Turbo87]

I see, thanks for the explanation! :)

[mitsuhiko]

I am maintaining a codebase that kinda intentionally abused this. The crate in question is insta which just needed some mostly stable order for snapshots. I was assuming that the incorrect implementation from Ord is not an issue because sort_by also only documented that at worst what happens as a violation from total order is bad output, but not crashes.

I am obviously going to change this, but from my experience there is a lot of code that relies on this behavior (for not ideal reasons). From my experience a lot of this comes from PartialOrd being able to do something that you cannot do yourself today (getting the discriminant of an enum that also implements Ord. See #106418)

I do think that it's acceptable to make this change but I believe that at least the change to sort_by is a break in backwards compatibility. The function did not panic before, was not documented as panic and did not imply that the behavior could change in this way.

Old documentation:

The comparator function must define a total ordering for the elements in the slice. If the ordering is not total, the order of the elements is unspecified.

New documentation:

Panicks: May panic if compare does not implement a total order.

From where I'm standing this is a backwards incompatible change that I did not expect.

[orlp]

@mitsuhiko If we're being pedantic, you were violating the contract as well in the old wording. It doesn't say "you may use a non-total ordering, in such a scenario the order is unspecified", it says "the comparator function must define a total ordering for the elements in the slice".

How I see it is that you were always using library UB, and the order of the elements being unspecified was just a clarification on what this could entail, not a guarantee that the library UB will always solely consist of this effect.