Do you really need a _by version, as opposed to a _by_key version? What exactly is fallible? If it's really fallible in the comparator that feels like it'd be really easy to not be a legal comparator, as it could return inconsistent things if it fails sometimes.
I think try_sort_by_cached_key would be very reasonable, though. Then it would call the fallible key generator once per item -- in which it could load a file or deserialize something or whatever -- then re-use the same logic that sort_by_cached_key already has to do the sorting now that it has the impl Ord keys.
(And that method does about the same amount of allocation that sort_by does, since they're both one O(n) allocation for temporary space.)
The context is an ASN.1 DER library and an implementation of SET OF, where elements of the set need to be lexicographically sorted by their DER encodings.
The comparison effectively performs a partial encoding of DER productions (namely their tag+length headers), and the encoder is fallible. The main thing that can go wrong is integer overflow when computing the lengths of nested data structures. The entire library is written with checked arithmetic with the goal of avoiding both overflows and panic-on-overflow.
I can't use the *_by_key versions because creating the "key" would involve serializing the entire message which is something I'm definitely trying to avoid.
The error in this case is being returned from the compare function. So similar reasoning, assume an error means don't change the current observed order. Which isn't going to help if the error is inconsistent, but nothing was going to help that.
I agree on that part. The bit that I objected to was "an error means don't change the current observed order", because then the "same" items could be in different relative orders after a sort, which feels like it doesn't meet any reasonable postcondition.
But that would be resolvable by just saying "if it returns Err, the only constraint is that the slice will be a permutation of the original". I don't really know that we could offer anything specific when comparers error.