Undocumented assumption: HashMap breaks if `Key::clone()` does not preserve `Hash` and `Eq`

[gewitternacht]

If the Clone implementation of a HashMap's key produces a key with a different hash, or if key.clone() == key does not hold, then this can result in a broken HashMap after map.clone() (same for HashSet).

For example, consider this struct with a custom Clone implementation:

#[derive(PartialEq, Eq, Hash, Debug)]
struct FakeInt(u64);

impl Clone for FakeInt {
    fn clone(&self) -> Self {
        FakeInt { 0: 0 }
    }
}

fn test_fake_int() {
    let mut map = HashMap::new();
    map.insert(FakeInt { 0: 1 }, 1);
    map.insert(FakeInt { 0: 2 }, 2);
    let c = map.clone();
    println!("{:?}", c); // gives {FakeInt(0): 1, FakeInt(0): 2}
    assert!(c.get(&FakeInt { 0: 0 }).is_none());
}

After cloning, FakeInt(0) is in the map twice in a way, but at the same time cannot be queried or removed. This playground link contains the above example and an additional one, where Hash is preserved, but x.clone() == x does not hold, which still leads to weird behaviour due to duplicate keys.

The underlying cause seems to be that HashMap::clone() relies on Key::clone() to preserve the key's Hash, placing the cloned value in the same bucket as the original one, and also assumes that key.clone() == key, not checking for duplicate keys after cloning. However, these assumptions don't seem to be documented anywhere: Clone does not require x.clone() == x, and I couldn't find any notes on this in the Hash, Eq, HashMap or HashSet documentation, or any discussions or issues on this topic at all.

Being fairly new to Rust, I don't know whether HashMap and HashSet should be able to handle such weird Clone implementations, but I would at least expect these assumptions to be made explicit somewhere – perhaps as another "logic error" for HashMap and HashSet?

(How I came across this issue: I wanted to write a specification for HashSet::clone() with Verus, and for this tried to figure out which guarantees HashSet::clone() can provide. Digging into the implementation, I realized that RawTable::clone_from_impl() seems to silently assume that cloning a key preserves its hash and produces a key equal to the original one.)

[clarfonthey]

You're right that this is technically not documented, although it's basically assumed across all of the Rust ecosystem (and every similar one with cloning functionality) that a clone is equal to its original. If a clone creates a different value, then why would you consider it a clone?

While it is true that this cannot cause undefined behaviour (and I believe we still honour this here), it's expected that your code will break if you have mismatched implementations of Clone.

Perhaps it would be worth updating the standard library documentation to clarify this interaction between Eq and Clone, however. We can leave Hash out of this since it must match Eq, and therefore would be transitively unaffected.

[Amanieu]

We do currently make the assumption that Clone preserves the "value" of a key and the result should compare equal and produce the same hash.

The documentation currently say this:

/// It is a logic error for a key to be modified in such a way that the key's
/// hash, as determined by the [`Hash`] trait, or its equality, as determined by
/// the [`Eq`] trait, changes while it is in the map. This is normally only
/// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.

Perhaps this should be extended to also cover Clone (PRs are welcome, both here and in the standard library).

[gewitternacht]

Thanks for your quick responses!

it's basically assumed across all of the Rust ecosystem (and every similar one with cloning functionality) that a clone is equal to its original. If a clone creates a different value, then why would you consider it a clone?

Not being very familiar with Rust or cloning, it's hard for me to judge whether x.clone() == x is an assumption that can be reasonably made of every Clone implementation, but I now realized that other collections (such as BTreeMap etc.) seem to also rely on this. So if this is indeed a universal assumption, then I think it would best be made explicit in the documentation of the Clone trait. I can try to make a PR there. (Not sure if I'm familiar enough with all the concepts/terminology that go into this, though.)

[clarfonthey]

I think it's understandable to make this mistake, and I agree that it should be documented, although I guess my main assumption is that by definition, a clone is the same as the original object. The only way we can define sameness is via PartialEq, so, it would make sense that this version of sameness holds.

You're right that this is an obvious hole in documentation, because I don't think that anything should be left implicit here, although I also understand why everyone had implicitly held this assumption before now.

Your example of counting upward is an entirely valid implementation of Clone, but it probably isn't correct for an implementation of Eq; it's why, for example, Arc and Rc don't consider the actual copies to differ in their Eq implementations.

[gewitternacht]

Thanks, Arc and Rc are interesting examples.

The only way we can define sameness is via PartialEq, so, it would make sense that this version of sameness holds.

I thought about this again and realized that due to PartialEq not necessarily being reflexive, e.g., NaN != NaN in floating point numbers, it is not generally true that x.clone() == x, e.g., when cloning NaN.
But I think the following could be a good representation of a universal requirement/assumption about Clone:
"If x == x, then it must also hold that x.clone() == x."
For all x implementing Eq, this implies x.clone() == x (as Eq requires reflexivity). And with Eq being a bound for keys of a HashMap, this universal assumption about Clone would be enough to guarantee the implicit assumptions made by HashMap.

[gewitternacht]

With this addition to the Clone documentation, I think this can be closed now.