Equivalent trait

[timothee-haudebourg]

This PR introduces an Equivalent trait, as requested in #345, to customize lookup operations without requiring a Borrow implementation. It provides a blanket implementation that covers the Borrow case so it should not break anything.

The hash_map::EntryRef API, although it uses the Borrow trait, remains unchanged as this would introduce some breaking changes.

[timothee-haudebourg]

I said that the EntryRef API is unchanged, but the HashMap::entry_ref method uses the Equivalent trait. Maybe it would be better to continue using the Borrow trait for this method, since the resulting EntryRef will probably be unusable without a Borrow implementation anyway.

[timothee-haudebourg]

I've found some typos in the doc of Equivalent, I'll wait for some feedback before I commit the fix so it won't unnecessarily run new checks.

[Amanieu]

LGTM! Let me know once you have fixed the typo so I can merge this.

[Amanieu]

ping @timothee-haudebourg, is this ready to merge?

[timothee-haudebourg]

Sorry I forgot about this, I just pushed some typo fixes, it should be ready to merge!

[Amanieu]

Could you add a test for this? Perhaps just copy one from indexmap: https://github.com/bluss/indexmap/blob/master/tests/equivalent_trait.rs

[Amanieu]

@bors r+

Thanks!

[bors]

📌 Commit f9df820 has been approved by Amanieu

It is now in the queue for this repository.

[bors]

⌛ Testing commit f9df820 with merge 22c7dbc...

[bors]

☀️ Test successful - checks-actions
Approved by: Amanieu
Pushing 22c7dbc to master...

[dhedey]

Just to give a heads up for anyone else hitting this problem.

When I upgraded hashbrown past 1.3.1 which released this feature, I got some compile errors on code I'd previously written. The error was:

the trait `Borrow<&K>` is not implemented for `K`
= note: required for `&K` to implement `hashbrown::Equivalent<K>`

It transpires that we previously had double references: let k = &abc; let value = hashmap.get(&k) - and the code previously was happy with them, but I get the above compile error with the new version. Perhaps the inference with the blanket impl of Equivalent doesn't give the compiler enough hints as with the Borrow bound.

I'm not quite sure why, but the compiler is unable to use auto-deref, and you either have to manually tell it Q = K or manually deferenced (remove an extra & if you can or add a *).

---

Separately, from a hashbrown compatibility perspective, is this an issue? For us at least it means the build passed fine using std::HashMap, but broke using hashbrown as a stand in replacement when building for no-std.

[mrcnski]

Thanks @dhedey, we hit the same error, and simply removing an extra & worked to resolve it!

[mattklein123]

@Amanieu sorry for the late drive by on this PR: would you accept a PR which makes the default implementation of Equivalent gated behind a feature which defaults to on? I have a use case where I would like to implement Equivalent on top of a generic structure and I can't figure out a way to prevent this from conflicting with the default implementation. Thank you!

[Amanieu]

Note that in the next release we will use the trait from the equivalent crate instead (#442). Would this help in your case?

[Amanieu]

Unfortunately I don't think we can disable the Equivalent trait: it's needed by HashMap to support Borrow.

[mattklein123]

Note that in the next release we will use the trait from the equivalent crate instead (#442). Would this help in your case?

I'm not sure. I can take a look once it releases.

Unfortunately I don't think we can disable the Equivalent trait: it's needed by HashMap to support Borrow.

I wasn't suggesting disabling the equivalent trait, I was thinking more that we could allow the blanket implementation to be disabled and force the user to implement it however they want? It's the blanket implementation that is getting me.

[Amanieu]

Can you show the impl you are trying to write? I would think the Rust coherence rules would always prevent you from implementing a conflicting impl.

[mattklein123]

Can you show the impl you are trying to write? I would think the Rust coherence rules would always prevent you from implementing a conflicting impl.

Let me try to come up with a working example when I have some time. Basically I just want this code removed from my build:

hashbrown/src/lib.rs

Lines 149 to 157 in 40ab9e6

	impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
	where
	Q: Eq,
	K: core::borrow::Borrow<Q>,
	{
	fn equivalent(&self, key: &K) -> bool {
	self == key.borrow()
	}
	}

The coherence rules are preventing me from implementing a conflicting impl. :)

[Amanieu]

I believe the coherence rules would prevent you regardless of whether this impl exists in hashbrown. The problem is that your crate doesn't "own" the trait, so you cannot write blanket impls.