Language vision regarding safety guarantees

dlight:

If it actually triggering UB is not a sensible future direction for this API, it seems much better to just remove the unsafe tag from it (existing callers won't be negatively affected, but they may drop the unsafe block if they wish)

I guess the complexity here is something that @scottmcm brought up in another thread:

The Hashtable Problem: A Litmus Test for External Impl Proposals

It's really important to me that for HashSet<TrustedType>, if someone gives me one it actually works. I don't want to ever let someone give me a garbage HashSet<u32>, for example. I want to be able to trust it because I trust u32 and I trust HashSet.

I think there's a core tension here between the desirable requirements "a BTreeMap<K,V> for which I know that K's Ord implementation is correct should always be ordered", and "BTreeMap<K,V> should be memory-safe regardless of how badly behaved K's Ord implementation is". Both of these requirements are potenitally important to avoid memory-safety vulnerabilitiies: the latter requirement is required if someone writes a broken Ord, and the former requirement is required if unsafe code relies on a BTreeMap<u32,V> to be correctly ordered.

For the first requirement to hold, btree_map::CursorMut::insert_before_unchecked needs to be unsafe, which effectively declares having an unordered BTreeMap<u32> to be library UB.

For the second requirement to hold, btree_map::CursorMut::insert_before_unchecked needs to be safe: otherwise, giving a BTreeMap a K with a broken Ord implementation is library UB, because it leads to an unsafe method being called without actually upholding its safety requirements.

As such, we basically have a weird case of specialisation here: the implication is that btree_map::<K,V>::CursorMut::insert_before_unchecked is safe whenever K is a downstream type (and that having an incorrectly sorted BTreeMap is library UB in this case), but unsafe whenever K is a standard library type (and that having an incorrectly sorted BTreeMap is not library UB in this case, just a logic error).

I'm not sure that there's any sensible way to cover this gap. (It almost seems as though the "safety level" or "trust level" should be some sort of generic parameter, but I can't think of a way to make that work.)