Tracking issue for `HashSet` entry APIs

[cuviper]

Feature gate: #![feature(hash_set_entry)]

This is a tracking issue for Entry and entry-like methods on HashSet.

Public API

impl<T, S> HashSet<T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    pub fn get_or_insert(&mut self, value: T) -> &T {...}
    pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
    where
        T: Borrow<Q>,
        Q: Hash + Eq,
        F: FnOnce(&Q) -> T,
    {...}

    pub fn entry(&mut self, value: T) -> Entry<'_, T, S> {...}
}

pub enum Entry<'a, T, S> {
    Occupied(OccupiedEntry<'a, T, S>),
    Vacant(VacantEntry<'a, T, S>),
}
pub struct OccupiedEntry<'a, T, S> {...}
pub struct VacantEntry<'a, T, S> {...}

impl<T: fmt::Debug, S> fmt::Debug for Entry<'_, T, S> {...}
impl<T: fmt::Debug, S> fmt::Debug for OccupiedEntry<'_, T, S> {...}
impl<T: fmt::Debug, S> fmt::Debug for VacantEntry<'_, T, S> {...}

impl<'a, T, S> Entry<'a, T, S> {
    pub fn insert(self) -> OccupiedEntry<'a, T, S>
    where
        T: Hash,
        S: BuildHasher,
    {...}
    pub fn or_insert(self)
    where
        T: Hash,
        S: BuildHasher,
    {...}
    pub fn get(&self) -> &T {...}
}

impl<T, S> OccupiedEntry<'_, T, S> {
    pub fn get(&self) -> &T {...}
    pub fn remove(self) -> T {...}
}

impl<'a, T, S> VacantEntry<'a, T, S> {
    pub fn get(&self) -> &T {...}
    pub fn into_value(self) -> T {...}
    pub fn insert(self)
    where
        T: Hash,
        S: BuildHasher,
    {...}
}

The get_or_insert[_with] methods provide a simplification of the Entry API for HashSet, with
names chosen to match the similar methods on Option. The full Entry API mimics that
of HashMap, though without methods for the map value (which is just () in a set).

Steps / History

• Initial methods: Add entry-like methods to HashSet #60894
• Fuller Entry API: Add Set entry API  #120077
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• None yet.

See also #133549 for BTreeSet.

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[bluss]

(For get_or_insert_with) Even though there is a borrow relation, there is no guarantee that the lookup key and inserted key are equivalent, I guess that's an acceptable loss? But it would be important to point out in that case.

Consider s[..1].to_string() as function

[cuviper]

Even though there is a borrow relation, there is no guarantee that the lookup key and inserted key are equivalent, I guess that's an acceptable loss?

Borrow does require equivalence, stating, "In particular Eq, Ord and Hash must be equivalent for borrowed and owned values: x.borrow() == y.borrow() should give the same result as x == y." So I think that's fine for get_or_insert, at least.

For get_or_insert_with, yes, it's trickier -- the user-provided function could return anything. We could choose to (debug) assert that the value returned is still equal. Or we can just make this part of the documented contract, on your honor, just like the relationship between Borrow, Eq, etc. There's no concern with memory safety if you violate this, but the collection will probably act strangely having inserted a different value in that place.

[lnicola]

We could choose to (debug) assert that the value returned is still equal.

That might not be too useful if std is compiled without debug assertions. Agreed otherwise, it's the user's responsibility to do something sane.

[cuviper]

That might not be too useful if std is compiled without debug assertions.

AIUI generic code gets the debug-assertion setting of the place where it's monomorphized.

[RustyYato]

@cuviper that doesn't sound right because macros are expanded way before monomorphozation

[cuviper]

Oh, maybe it's only overflow checks that are affected that way. Nevermind then.

[bluss]

It seems like a misuse of the entry, to insert a different key than was looked up for (a misuse std should not allow). But I can't find a way to "break" this using some test code. From a cursory look I think the current implementation can't be fooled, it hashes and inserts it as if it is a new key.

Is that intended? It seems like that fact supercharges this API - get_or_insert_with, but it depends on implementation details. I'd assume the vacant entry should be allowed to cache the hash and bucket location if it wanted to? @Amanieu

[Amanieu]

You can abuse this to insert the same element multiple times in a set: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=c4d27e6b11b646030d1370351887ebc1

Although this may arguably be a bug in RawEntry which allows you to do it.

[Amanieu]

We have two options here:

• Add an assert which checks that the new key is equal to the key used for the lookup.
• Allow sets to contain duplicate keys but consider it a logic error (the underlying hashmap handles duplicate keys just fine).

[bluss]

The current implementation has a benign behaviour in this scenario, and that's a problem, because users can rely on it, and then we are locked in to the implementation specific behaviour (and can no longer change the hashmap impl).

The following should also be an option on the table:

• Remove get_or_insert_with because it makes it easy to do the wrong thing to the hashmap, and/or accidentally rely on implementation details

An assert that defends against relying on implementation details is also an option. (Exact handling of duplicate keys or if this insert overwrites or makes a new key).

[Amanieu]

Note that HashMap is required to safely handle duplicate keys since it needs to at least not trigger UB if the key has a broken Eq or Hash implementation (which only uses safe code).