> But even if we insist on getting in harm's way, safe Rust promises to protect us anyway. For example if I make an array of a thousand misfortunate::OnewayGreater<u8>s they're only one byte each, yet they all insist they're Ordered greater than each other and even than themselves, Rust's sort() doesn't cause Undefined Behaviour on this input. It may never succeed, since all the elements to be "sorted" insist they're greater than each other, but it definitely won't segfault, trash unrelated memory or cause chaos.
This argument feels like a difference in semantics, rather than any actual added safety.
Rust will happily let you run the sort with an unstable comparator, which then leads to undefined behavior in the sense that the final sorting order, or whether the sort completes at all, is not defined by the standard and is instead dependent on the internal implementation. The fact that this is not called "undefined behavior" in Rust is a difference in semantics only.
Added safety would be if Rust could detect the fact that the comparator is unstable and tell the user so they could fix the bug in their comparator.
What is perhaps more relevant here than any safety provided by the Rust language is that there is only one Rust compiler. Relying on internal implementation details of that compiler is much more accepted, and the distinction between "internal compiler implementation detail" and "behavior defined by the standard" is a lot less relevant than it is in C or C++, which have many different implementations.
"Undefined behaviour" has a very specific meaning (perhaps ironically) in programming language design. It means anything could happen, including crashing during the undefined operation (i.e. crashing during the sort() in this case), appearing to work but then crashing afterwards, or even crashing before the undefined operation starts! (Or doing other weird things, not just crashing - but a time travelling crash is already plenty weird enough for this discussion.)
If Rust is able to define its sort() as only ever affecting the array passed to it, with the possibility of looping forever, then that is very well defined behaviour in comparison.
Yup. If the only potential variation is on the resulting ordering, C/C++ would call this implementation-defined or unspecified than undefined.
One example of unspecified behaviour is the order in which function call parameters are evaluated (meaning any order is OK, and it could vary from call to call).
One example of implementation-defined behaviour is the value of sizeof(int).
> Rust will happily let you run the sort with an unstable comparator, which then leads to undefined behavior in the sense that the final sorting order, or whether the sort completes at all, is not defined by the standard and is instead dependent on the internal implementation. The fact that this is not called "undefined behavior" in Rust is a difference in semantics only.
You can't avoid allowing this in a general purpose sort. If Rust wanted to insist that the comparator must be "stable" in this sense, it would have to do that by defining an unsafe trait (maybe "ReallyReallyOrdered") implementations of which promise they're correct (hence the "unsafe" requirement, a safe trait like Ord can't promise anything the compiler can't prove).
There's no difference in semantics at work. In C++ sort() with a bad comparator has Undefined Behaviour and so might do absolutely anything, in Rust its behaviour is defined in a way you simply don't like.
> Added safety would be if Rust could detect the fact that the comparator is unstable and tell the user so they could fix the bug in their comparator.
This could only be a best-efforts check, since if you were to try a.cmp(b) a million times, nothing stops a's comparator from counting and giving a different answer on the next try after your millionth check.
I always meant to get around to writing some sort of misfortunate::RandomOrder (but with a cleverer name, maybe Tombola or ManekiNeko ?) which would exhibit completely random ordering, again this isn't methodically detectable, a detector can only have probabilistic success.
Unlike C++, all Rust's built-in types have proper behaviour here, so if you run into trouble either you're using a third party type, or a third party comparator for the sort itself, and since there is never Undefined Behaviour you can track down the problem.
This argument feels like a difference in semantics, rather than any actual added safety.
Rust will happily let you run the sort with an unstable comparator, which then leads to undefined behavior in the sense that the final sorting order, or whether the sort completes at all, is not defined by the standard and is instead dependent on the internal implementation. The fact that this is not called "undefined behavior" in Rust is a difference in semantics only.
Added safety would be if Rust could detect the fact that the comparator is unstable and tell the user so they could fix the bug in their comparator.
What is perhaps more relevant here than any safety provided by the Rust language is that there is only one Rust compiler. Relying on internal implementation details of that compiler is much more accepted, and the distinction between "internal compiler implementation detail" and "behavior defined by the standard" is a lot less relevant than it is in C or C++, which have many different implementations.