I'm currently in the process of researching sort implementations. And have ideas I want to and am already upstreaming into the standard library. One important concept is something I call observable_is_less. The user can provide a custom comparison function either by implementing Ord or by calling sort_by
. For types that allow interior mutability as marked by containing an UnsafeCell
, this user provided comparison function could mutate the stack value. No matter what path the execution takes, or even if Ord is implemented incorrectly. One invariant that needs to be upheld by the sort implementations is that every possible write to the stack value of the type, has to be 'observed' in the user provided slice when the sort function returns, either normally or via panic. This gets tricky when working with temporary memory, eg. for merging. Certain optimisations would be invalid for such types, for example they may compare two values, but might skip writing one of them into temporary memory because it has already been written before. And then later write that temporary memory over parts of the input slice. In that case one or more 'writes' as per calls to is_less
would have been missed. This leads to unexpected behaviour and even possibly UB.
Right now, I'm using Copy
via specialisation to determine what types these optimisations are safe to do for, but it would be great and benchmarks suggest beneficial even for types such as String
to allow such optimisations. However I'm not aware of any way to write such a function fn has_interior_mutability<T>() -> bool
. The compiler already has this information, it would be great to somehow get access to that information. IIRC there is a way to 'check' if a type has interior mutability by seeing if a function compiles that would be invariant over a shared reference to such type. But such check can only cause a compiler error, not provide runtime/compile-time branching.