Documentation for `sort_by` (and related methods) is potentially self-contradictory

[BatmanAoD]

Location

slice::sort_by

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.

[lolbinarycat]

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]

I mentioned that in my last paragraph. I think that if that's what it means, it should be explicit.

[lcnr]

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.

The user has to be able to be able to freely continue to use the slice after a panic occurs as catch_unwind is a safe function. sort_by sorts a slice, so it can't change the length, and it also has to handle values of any arbitrary type T. 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]

catch_unwind is safe, but the user already needs to jump through hoops to observe the vector state after catch_unwind returns an error and the vector was mutated inside the call stack that panicked, because &mut isn't unwind-safe and Mutex gets 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 panic in the same paragraph (instead of only in the section at the bottom), and distinguish the two cases? Something like:

If the comparison function compare does not implement a total order, the function may panic; even if the function exits normally, the resulting order of elements in the slice is unspecified.

If sort_by panics for any reason, all original elements will remain in the slice and any possible modifications via interior mutability are observed in the input. This ensures that recovery code (for instance inside of a Drop or following a catch_unwind) will still have access to all the original elements. For instance, if the slice belongs to a Vec, the Vec::drop method will be able to dispose of all contained elements.

[lolbinarycat]

it's not split into two cases because this bit:

all original elements will remain in the slice and any possible modifications via interior mutability are observed in the input

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]

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_by on a (subslice of a) vector, if sort_by doesn't panic, of course the vector must still be valid. Should we include that sentence in every single mutable method on Vec? 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 compare doesn'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]

I don't think my proposed phrasing implies that the order is guaranteed when the function panics.

your proposed wording drops the guarantee that, when there is a panic, no elements will be copied, even if T is Copy.

[BatmanAoD]

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]

No it doesn't: "all original elements will remain in the slice."

your wording isn't clear if that's guaranteed for both cases, or just the panic case. i think we can do better.