The entry API (as in BTreeMap::entry) is sweet, but requires the key to be given to entry, not just a reference. Sadly, if cloning the key is expensive (as in, requires a heap allocation), then this impacts the happy path where a value is already in a cache. It'd be neat to have a lazy version of that, maybe only for keys that implement Clone.
Somewhat related: Head-Desking on Entry API 4.0
I think the main problem is to have ergonomic usage with an API that enforces consistency for "trusted" types. Let's say you have BTreeMap<String, Box<T>>. Unsafe code can rely on the fact that all returned mutable references &mut T obtained from get_mut are different as long as the keys are different.
If you mirror the get signature you get
fn entry_ref(&mut self, key: &Q) -> EntryRef<String, usize> where
String: Borrow<Q> + Ord,
Q: Ord + ?Sized + ToOwned<Owned=String>
Which would allow you to use some type for Q with broken Ord implementation. If you go the safe route you get
fn entry_ref(&mut self, key: &String) -> EntryRef<String, usize>
which is unusable with &str, Arc<str>, etc.
There are more low level interfaces in nightly like CursorMut in std::collections::btree_map - Rust for BTreeMap and RawEntryBuilderMut in std::collections::hash_map - Rust for HashMap which have to solve the same problem.
Since lookup is still always comparing against the comparison on the key type, it doesn't matter how broken you make the table contents with raw_entry, lookup with trusted K and Q is still guaranteed to return distinct objects.
This is technically a guarantee that isn't provided by std (docs permit arbitrary safe misbehavior once inconsistent comparison is observed), but any implementation that does comparison in a deterministic fashion will provide it.
Careful: yes, they will be distinct items, but extending the lifetimes of the references is quite likely unsound because the collection makes no promises not to reborrow arbitrary non looked up items (e.g. something like &[(K, V); B]), which will likely invalidate &mut V into that referenced region. (Pending dynamic borrow model specifics, but effectively a given for references to fixed size.)
Ah true, my example was wrong. I think this one which assumes that keys are unique is correct though?: Rust Playground
I guess that this guarantee is also not explicitly written down. But if it wouldn't hold sound code would be much harder to write.
I intentionally tried to avoid borrowing details 
ptr::copy_nonoverlapping should be enough to get immediately observable UB. But as you pointed out, the determinism of lookup with trusted types is enough to ensure injectivity.
HashMap::entry has the same problem.
As I remember there was at least 3 RFC to fix this, but they are not accepted.
The current one attempt is raw_entry,
based on this idea.
And of note is that raw_entry is not unsafe, therefore you cannot assume a HashMap even with known types is "correct" in unsafe code. AFAIK this has never been a guarantee either map type has attempted to provide.
I actually looked at HashMap::raw_entry, looked at the use cases, and decided that it was not for me. Had I have looked at HashMap::raw_entry_mut, I would have indeed found my use case listed there.
Nevertheless, this seems like a scary interface for my very benign (and maybe common?) use case. And, there is no such interface for my favorite map data structure, BTreeMap.
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.