Skip to content

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

@golddranks

Description

@golddranks

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/

Metadata

Metadata

Assignees

No one assigned

    Labels

    C-enhancementCategory: An issue proposing an enhancement or a PR with one.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions