Bring `hashbrown::Equivalent` into std

[ChayimFriedman2]

Proposal

Problem statement

HashMap supports querying with a borrowed variant of the key type via the std::borrow::Borrow trait. However, it is very limited: it only allows key transformations from a reference to a reference. It is enough to implement borrowing for a container (String -> str) or based on a field, but not enough when you have a newtype you need to wrap, or if you want to borrow multiple fields (e.g. a tuple ((String, String) -> (&str, &str)).

Motivating examples or use cases

As I said, querying a hashmap without an allocation for a newtype or any other type whose structure does not rigidly match a reference.

Solution sketch

hashbrown has long included a more flexible version of Borrow called Equivalent. Its signature is:

pub trait Equivalent<K>
where
    K: ?Sized,
{
    fn equivalent(&self, key: &K) -> bool;
}

Basically, instead of requiring the method to return the borrowed key, we give it the owned key to compare.

The trait has a blanket impl for Borrow, and I believe introducing it will be backwards compatible.

Alternatives

• Do nothing, of course.
• There is a pattern that can sometimes be used to workaround the limitations of Borrow:

   // See explanation (1).
   trait KeyPair<A, B> {
       /// Obtains the first element of the pair.
       fn a(&self) -> &A;
       /// Obtains the second element of the pair.
       fn b(&self) -> &B;
   }
   
   // See explanation (2).
   impl<'a, A, B> Borrow<dyn KeyPair<A, B> + 'a> for (A, B)
   where
       A: Eq + Hash + 'a,
       B: Eq + Hash + 'a,
   {
       fn borrow(&self) -> &(dyn KeyPair<A, B> + 'a) {
           self
       }
   }
   
   // See explanation (3).
   impl<A: Hash, B: Hash> Hash for dyn KeyPair<A, B> + '_ {
       fn hash<H: Hasher>(&self, state: &mut H) {
           self.a().hash(state);
           self.b().hash(state);
       }
   }
   
   impl<A: Eq, B: Eq> PartialEq for dyn KeyPair<A, B> + '_ {
       fn eq(&self, other: &Self) -> bool {
           self.a() == other.a() && self.b() == other.b()
       }
   }
   
   impl<A: Eq, B: Eq> Eq for dyn KeyPair<A, B> + '_ {}
   
   // Boring stuff below.
   
   impl<A, B> KeyPair<A, B> for (A, B) {
       fn a(&self) -> &A {
           &self.0
       }
       fn b(&self) -> &B {
           &self.1
       }
   }
   impl<A, B> KeyPair<A, B> for (&A, &B) {
       fn a(&self) -> &A {
           self.0
       }
       fn b(&self) -> &B {
           self.1
       }
   }

  Mentioned in this Stack Overflow answer, although I don't know the origin. This pattern is cute, but:
  • It's a hack.
  • It's obscure.
  • It may carry the perf overhead of dynamic dispatch, if the compiler doesn't inline everything.

Links and related work

hashbrown::Equivalent

How to get value from HashMap with two keys via references to both keys? - Stack Overflow

An Internals thread discussing this idea.

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[cuviper]

See also rust-lang/rust#144506, since Equivalent and Comparable are a pair akin to Eq and Ord.

[Amanieu]

This was discussed in the @rust-lang/libs-api meeting. We would like to introduce both the Equivalent and Comparable traits to the standard library. However we would like the traits to be defined slightly differently:

pub trait Equivalent<Q> {
    fn equivalent(&self, key: Q) -> bool;
}
pub trait Comparable<Q> {
    fn compare(&self, key: Q) -> Ordering;
}

This would allow us to introduce blanket implementations of these traits for tuples, which will allow common use cases to just work, for example indexing a HashMap<(String, String)> with a (&str, &str) key.

impl<'a, Q: ?Sized, K: ?Sized> Equivalent<&'a Q> for K
where
    Q: Eq,
    K: Borrow<Q>,
{
    #[inline]
    fn equivalent(&self, key: &'a Q) -> bool {
        PartialEq::eq(self.borrow(), key)
    }
}

impl<'a, Q1: ?Sized, K1, Q2: ?Sized, K2> Equivalent<(&'a Q1, &'a Q2)> for (K1, K2)
where
    Q1: Eq,
    K1: Borrow<Q1>,
    Q2: Eq,
    K2: Borrow<Q2>,
{
    #[inline]
    fn equivalent(&self, key: (&'a Q1, &'a Q2)) -> bool {
        PartialEq::eq(self.0.borrow(), key.0) && PartialEq::eq(self.1.borrow(), key.1)
    }
}

Implementation-wise, it would be easier to start experimenting with Comparable on BTreeMap since HashMap support would require changes to hashbrown which is maintained as a separate crate. rust-lang/rust#144506 has an initial implementation but the PR seems abandoned (cc @conradludgate).

The tracking issue has already been created at rust-lang/rust#145986, so I'm going to close this ACP as accepted.

[conradludgate]

Happy to drive the implementation forward now. Seems we have a clear path forward