Repository navigation
Documentation for sort_by (and related methods) is potentially self-contradictory #130122
Description
Location
Summary
Now that sort_by can panic when the ordering is not total, it seems confusing and misleading to me, if not technically wrong, to specifically provide a guarantee about the state of the slice after the operation:
...the resulting order of elements in the slice is unspecified. All original elements will remain in the slice and any possible modifications via interior mutability are observed in the input.
In general, I would assume that a guarantee like this only applies if the function returns normally rather than diverging, and thus that it implies the function will not diverge. I'm a bit confused about what the purpose of the guarantee even is; is the point just that, for the purpose of cleanup with drop and/or catch_unwind, the slice still contains all the same data? I can see how this would be important in the case of a Vec or other container with smart-pointer elements, but it also seems that in that case, the more straightforward guarantee is just that, if Vec::sort_by panics (for any reason), and this causes the Vec itself to be dropped, its drop method will still be able to properly drop all the elements it contains. Mentioning the "order of elements", though, seems to imply that a user might be able to continue using the slice (or vector) after the panic occurs, and I'm having a hard time thinking of a scenario where that would be useful.
And, of course, with panic=abort, control should never return to the caller at all when sort_by panics, so this guarantee is meaningless.
The other interpretation I can think of is that this is explaining what happens if the ordering is not total but the new logic doesn't catch it, so sort_by returns normally. If that's the case, this should be made explicit.
Activity
lolbinarycat commentedon Sep 9, 2024
note that it may panic if not given a total order. there's also a chance it won't "notice" the order isn't total, and thus it won't give an error, and returns a non-sorted array, in which case that guarantee applies
BatmanAoD commentedon Sep 9, 2024
I mentioned that in my last paragraph. I think that if that's what it means, it should be explicit.
lcnr commentedon Sep 9, 2024
The user has to be able to be able to freely continue to use the slice after a panic occurs as
catch_unwindis a safe function.sort_bysorts a slice, so it can't change the length, and it also has to handle values of any arbitrary typeT. This means it can't modify the values to their default value or create new dummy ones. The only way to guarantee that the slice will remain usable without undefined behavior is therefore to keep all the originally used elements. While this property isn't 'useful', it is necessary for soundness.BatmanAoD commentedon Sep 14, 2024
catch_unwindis safe, but the user already needs to jump through hoops to observe the vector state aftercatch_unwindreturns an error and the vector was mutated inside the call stack that panicked, because&mutisn't unwind-safe andMutexgets poisoned by the panic. At that point, the important thing for the user to know is that the slice will still contain all the same elements and...the thing about interior mutability, which I'm not sure I've wrapped my head around yet. The "order of elements" seems like, at best, a distraction; if the function panicked mid-sort, of course you can't assume the sorting succeeded!So the documentation as written still seems kind of indirect and confusing. Why not be explicit about the
panicin the same paragraph (instead of only in the section at the bottom), and distinguish the two cases? Something like:lolbinarycat commentedon Sep 14, 2024
it's not split into two cases because this bit:
appliest to both cases. the unspecified order also applies to the panic case (this fact is easier to intuit, but it's not impossible for the stdlib to restore the order, even if it would be wildly inefficient for most search algorithms)
BatmanAoD commentedon Sep 14, 2024
Okay, but isn't that guarantee implicit for every safe function that doesn't panic? My point isn't that the statement is wrong, it's that it's confusing, because, when calling
sort_byon a (subslice of a) vector, ifsort_bydoesn't panic, of course the vector must still be valid. Should we include that sentence in every single mutable method onVec? If not, what makes it worthwhile when describing the case where sorting doesn't panic?I don't think my proposed phrasing implies that the order is guaranteed when the function panics.
This is a side note, but I would argue that it is impossible for the stdlib to correctly "guess" what the order is supposed to be in all cases. Consider the case where
comparedoesn't actually provide any useful ordering information at all, such as|_, _| panic!("world's worst sort function")or even|_, _| Ordering::Less. (I do realize that the library could restore the original element order, though.)lolbinarycat commentedon Sep 14, 2024
your proposed wording drops the guarantee that, when there is a panic, no elements will be copied, even if
TisCopy.BatmanAoD commentedon Sep 14, 2024
No it doesn't: "all original elements will remain in the slice." If you mean something else, then I don't see where the original documentation makes any such guarantee, either.
lolbinarycat commentedon Sep 14, 2024
your wording isn't clear if that's guaranteed for both cases, or just the panic case. i think we can do better.
BatmanAoD commentedon Sep 14, 2024
Do you mean that the original wording is better, or are you just saying you'd like to keep workshopping?
lolbinarycat commentedon Sep 15, 2024
both the original and your suggestion are confusing in different ways.
i think just starting the second paragraph with "even if" instead of just "if" is enough to resolve the ambiguity, making it clear that those those guarantees also hold if it returns.
BatmanAoD commentedon Sep 15, 2024
Okay, so:
Shall I open a PR with that change?
lolbinarycat commentedon Sep 15, 2024
sure, give it a shot!
reword 'sort-by' edge-conditions documentation; resolves rust-lang#13…
reword 'sort-by' edge-conditions documentation; resolves rust-lang#13…
reword edge-conditions documentation on all slice 'sort' functions; r…
reword edge-conditions documentation on all slice 'sort' functions; r…
Rollup merge of rust-lang#130416 - BatmanAoD:130122-sort-by-docs, r=M…
Auto merge of rust-lang#130992 - matthiaskrgr:rollup-7zufwg5, r=matth…
Rollup merge of rust-lang#130416 - BatmanAoD:130122-sort-by-docs, r=M…
Auto merge of rust-lang#131012 - GuillaumeGomez:rollup-e9ovh3a, r=Gui…
Unrolled build for rust-lang#130416
Squashed 'library/' changes from 4f47132..771d77c