Interior mutability reflection

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.

In Rust this concept is called Freeze.

1 Like

Caveat: Freeze does not indicate that a type exposes no shared mutability. It only indicates that a type does not have any UnsafeCell before indirection. Box<Mutex<_>> is Freeze.

But that would be exactly what I need, no? The stack value must not be modified, modification vai indirection should be fine.

1 Like

Related thread which proposed an auto trait for types which have no interior mutability: Autotrait to mark types without interior mutability