The Problem

Let's say we have the following types:

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
enum Kind {
    Foo,
    Bar,
}

type Map<T> = HashMap<(Kind, String), T>;

The Map<T> type can be indexed by &(Kind, String), but how could we index it by a &(Kind, &str) if we don’t want to clone the string?

Most methods that manipulate keys have the following signature:

impl<K, V> HashMap<K, V> {
    fn func<Q>(&self, probe: &Q) 
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized;
}

Using &(Kind, String) works because there is a blanket implementation for Borrow of this form:

impl<T: ?Sized> Borrow<T> for &T {
    fn borrow(&self) -> &T {
        self
    }
}

So if we want to index our map with a &(Kind, &str) we need some way of implementing Borrow for this type, so let’s try:

impl<'a> Borrow<(Kind, &'a str)> for (Kind, String) {
    fn borrow(&self) -> &(Kind, &'a str) {
        &(self.0, &self.1)
    }
}

So everything is good! Not so fast… This does not compile! We are returning a reference to a local variable, this is not valid Rust. The definition of the Borrow trait requires us to produce a reference which is "derived" from self, i.e. which references a smaller part of it.

The Solution

In order to make this work we are going to need some more boilerplate (the following snippet is largely based on a post on the Rust community Discord which I have lost)

// Trait which will allow to index the Map<T>
trait BorrowedKey {
    fn as_borrow(&self) -> (Kind, &str);
}

// Implementation for the borrowed query
impl BorrowedKey for (Kind, &str) {
    fn as_borrow(&self) -> (Kind, &str) {
        (self.0, self.1)
    }
}

// Implementation for the key
impl BorrowedKey for (Kind, String) {
    fn as_borrow(&self) -> (Kind, &str) {
        (self.0, &self.1)
    }
}

// Hash implementation of the query
impl<'a> Hash for dyn BorrowedKey + 'a {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let (kind, s) = self.as_borrow();
        kind.hash(state);
        s.hash(state);
    }
}

impl<'a> PartialEq for dyn BorrowedKey + 'a {
    fn eq(&self, other: &Self) -> bool {
        self.as_borrow() == other.as_borrow()
    }
}

impl<'a> Eq for dyn BorrowedKey + 'a {}

// Borrow implementation which will be used to compare the key
impl<'a> Borrow<dyn BorrowedKey + 'a> for (Kind, String) {
    fn borrow(&self) -> &(dyn BorrowedKey + 'a) {
        self
    }
}

This will now allow us to do what we wanted:

fn has_key<T>(query: (Kind, &str), map: &Map<T>) -> bool {
    let borrowed = &query as &dyn BorrowedKey;

    map.contains_key::<dyn BorrowedKey + '_>(borrowed)
}

Note that specifying the lifetimes is very important! If they are omitted the compiler will raise errors like:

error[E0521]: borrowed data escapes outside of function
  --> src/lib.rs:56:5
   |
53 | pub fn has_key<T>(query: (Kind, &str), map: &Map<T>) -> bool {
   |                   -----         - let's call the lifetime of this reference `'1`
   |                   |
   |                   `query` is a reference that is only valid in the function body
...
56 |     map.contains_key::<dyn BorrowedKey + '_>(borrowed)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |     |
   |     `query` escapes the function body here
   |     argument requires that `'1` must outlive `'static`

How does it work?

Let's call values of type Q the query and values of type K the key.

I’m going to give a "simple" explanation that skips a number of optimizations present in the real HashMap.

When we insert a key we use K::hash in order to locate a bucket, then we add the tuple (K, T) in the bucket.

When we want to look up a query we first use Q::hash to locate a bucket. Note that this requires the Hash implementation of K and Q to "agree" in that they return compatible hashes. We then iterate over the bucket entries, and call <K as Borrow<Q>>::borrow on each entry to compare it with our query, using <Q as PartialEq>::eq. This will allow us to locate the previously inserted entry.

This procedure explains why we need two ways to create a &dyn BorrowedKey, we need the owned from the owned tuple in the HashMap implementation and the one from the borrowed tuple in our queries.

The reason a &dyn BorrowedKey works is that the Borrow implementation is not simply taking a reference to a part of the input value, we are building a fat pointer containing the VTable. This is what allows us to side-step the "limitation" of the Borrow trait that we first encountered.