Guarantee that values in hash map are disjoint from each other and the HashMap struct.

fec9956
Opened by Pyry Kontio at 2021-06-10 11:31:14

There was some discussion about the unsafe guarantees of HashMap on Reddit[1] which inspired me to write this issue.

The current HashMap implementation has its entries at memory locations that are disjoint from each other and from the HashMap struct. That means that in principle, there could simultaneously exist multiple mutable references to different, disjoint values contained in hash map without aliasing happening. This idea is similar in principle to the reason why split_at_mut API on mutable slices can exist.

However, as the HashMap currently provides no guarantees for supporting the disjointness of its entries, no unsafe code is allowed to trust it – especially because HashMap is a part of the std, and we can't currently pin version dependencies to std; the implementation of HashMap is allowed to "silently" change and break unsafe code.

I think it would make sense to document what the current implementation does in practice as a guarantee: the values stored in hash map are disjoint from each other and from the HashMap struct. In practice, this disallows the following situations:

  • The HashMap struct containing some of its values "inline", inside the struct.
  • Some value v1 containing an instance of another value v2 (for example, a boxed struct that contains more boxed structs of the same type), and HashMap returning a reference to v2 as a reference to "separate" value from v1.

To be sure, I don't mean that HashMap should necessarily guarantee that each key maps to a separate value – just that separate values don't alias. Also I don't propose an API that allows multiple unaliased mutable references to the values in hash map; but this guarantee can be seen as a preliminary requirement for such an API to exist in future.

[1] https://www.reddit.com/r/rust/comments/5ofuun/multi_mut_multiple_mutable_references_to_hashmap/

  1. Not sure if the guarantee should be written more formally as an implication: if the values inserted in hash map are disjoint before inserting, it's guaranteed that they are disjoint when inserted or something like that.

    Pyry Kontio at 2017-01-18 14:05:52

  2. The HashMap iterators that return mutable references to values sort of imply this already.

    Andrew Paseltiner at 2017-01-18 17:01:13

  3. Good point! However, to pick nits, that implies it strictly only during the lifetime of the iterator.

    Pyry Kontio at 2017-01-18 17:58:48

  4. This data structure has changed significantly since this issue was raised, to a more well-documented if also even more... individualistic implementation. Does this remain an issue?

    Jubilee at 2021-06-10 05:52:39

  5. @workingjubilee I believe it does, as this issue concerns itself with the (unsafe) API guarantees, not the implementation.

    Pyry Kontio at 2021-06-10 11:31:14