Can get() take an AsRef/Borrow?

[FauxFaux]

LruCache isn't quite a drop-in replacement for HashMap for me, as I'm using HashMap<String, i64>. For this type, .get("some &str") works. This avoids the copy/allocation of to_string().

For LruCache, you instead get this error:

    |
103 |     if let Some(id) = cache.get(val) {
    |                                 ^^^ expected struct `std::string::String`, found str
    |
    = note: expected type `&std::string::String`
               found type `&str`

I had a go at changing the code to be more like HashMap's (and take a Borrow), but I got lost. Here's my thoughts: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0e81344c5da15c2b7c5f24e3135e7551

The issue is the KeyRef, where a KeyRef<String> isn't similar enough to a KeyRef<str>. I believe a String is only similar-enough to a str due to pointer abuse, eventually inside:

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
    &*(v as *const [u8] as *const str)
}

The same construct appears inside e.g. PathBuf -> Path's implementation. 😱

Can anyone think of a way to make this work?

[jeromefroe]

Hi, this is a great question! I tried playing around to see what I could come up with, but I'm currently stumped. Following your lead on KeyRef I took a look at the get method more closely and immediately saw a problem. We don't pass the key directly to internal hashmap, but instead construct a KeyRef first:

pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
    let key = KeyRef { k };  // <-- Need to make this step unnecessary
    let (node_ptr, value) = match self.map.get_mut(&key) {
    ...
}

I tried to solve that problem first, since it seemed to me that if we aren't able to pass the reference to the key directly to the internal map then passing a reference to a different certainly won't be possible. By implementing Borrow<K> for KeyRef<K> I was able to eliminate the intermediate step of constructing the KeyRef:

impl<K> Borrow<K> for KeyRef<K> {
    fn borrow(&self) -> &K {
        unsafe { &(*self.k) }
    }
}

pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
    let (node_ptr, value) = match self.map.get_mut(k) {
    ...
}

From there, I tried to make the Borrow implementation more generic, so that one could pass not
only a reference to they key, which one can do already, but any borrowed form of the key. My first step, therefore, was to get the type of the Borrow implementation correct. But it's there that I ran into a problem:

// This fails to compile with the following error:
// conflicting implementations of trait `std::borrow::Borrow<KeyRef<_>>` for type `KeyRef<_>`:
//
// note: conflicting implementation in crate core:
//
//   - impl<T>; std::borrow::Borrow<T>; for T
//     where T: ?Sized;
impl<J, K: Borrow<J>> Borrow<J> for KeyRef<K> {
    fn borrow(&self) -> &J {
        unimplemented!()
    }
}

pub fn get<'a, Q>(&'a mut self, k: &Q) -> Option<&'a V>
where
    K: Borrow<Q>,
    Q: Hash + Eq,
{
    let (node_ptr, value) = match self.map.get_mut(k) {
    ...
}

The compiler can't accept the implementation of Borrow because it conflicts with the implementation of Borrow for one's own type in the standard library:

impl<'_, T> Borrow<T> for &'_ mut T 
where
    T: ?Sized

I think I can understand the conflict because if J is KeyRef<K> then we are implementing the same trait again. I'm not quite sure how to get around this. I think it may be a case where specialization is required, but based on the tracking issue it doesn't appear that it will be available in the immediate future (and I'm not even sure it would apply here).

I put up my current work in #27 if you get a chance to take a look. I would certainly welcome any feedback.