Difference in behavior of HashMap::get and get_mut


#1

I’m attempting to update a hash map entry and have been running into lifetime issues. My hash map has a key type with a lifetime parameter and the key value that I’m attempting use to probe into the table has a lesser value for the lifetime.

Since both lifetimes, 'a and 'b, last at least as long as the body of do_stuff, I would think that Foo<'b> would be acceptable for use with both get and get_mut, even though the key type is Foo<'a>. However what I’m seeing is that it works for get, but the compiler rejects its use for get_mut. Aside from self and the return references being mutable in the get_mut version, I don’t see a difference between the two functions which would account for what I’m seeing.

Can anyone explain the difference between the two functions which causes this behavior?

use std::borrow::Cow;
use std::collections::HashMap;

#[derive(Hash, Eq, PartialEq)]
struct Foo<'a> {
    v: Cow<'a, str>,
}

fn do_stuff<'a: 'b, 'b>(map: &mut HashMap<Foo<'a>, i32>, key: &Foo<'b>) {
    map.get(key); // works!
    map.get_mut(key); // does not work, expects &Foo<'a> got &Foo<'b>
}

fn main() {
    let mut map = HashMap::new();
    let name = "bessie";
    let entry = Foo {
        v: name.into()
    };
    do_stuff(&mut map, &entry);
}

HashMap keys of different composite types
#2

I think it might have something to do with variance, but I don’t understand those rules well. It’s happy if you reverse the 'a and 'b lifetimes, or if you use a single 'a lifetime.


#3

More specifically, I think it’s that &T is variant over T, but &mut T is invariant over T.

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
    where K: Borrow<Q>, Q: Hash + Eq

A Foo<'b> can’t act like a Foo<'a> because it doesn’t live long enough. But because it is variant, a &HashMap<Foo<'a>, i32> can act like a &HashMap<Foo<'b>, i32>, and then accept K = Q = Foo<'b> for the key.

fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
    where K: Borrow<Q>, Q: Hash + Eq

But here &mut HashMap<Foo<'a>, i32> is invariant, so it can’t be subtyped. And since Foo<'b> still can’t subtype the other way, we’re stuck with an error.

The intuitive reason is that in theory, a &mut HashMap could do something like try to store your Foo<'b> somewhere inside itself where it’s expecting only Foo<'a>, and then it wouldn’t actually live long enough. Even though we know get_mut doesn’t do this, the compiler can’t tell from the interface alone.


#4

That makes sense, thank you.

The point that I missed with the get case was that it was the hashmap’s lifetime parameter which was being coerced into a lesser lifetime, not the function parameter’s lifetime being somehow ignored.


#5

I keep staring at K: Borrow<Q> in particular. It feels like even under the invariant get_mut, K = Foo<'a> should be able to use its &K variance and Borrow<Q> to get down to a &Foo<'b>. I think the Borrow trait just isn’t set up for this, but I don’t know how it would be written any differently. K itself is locked into 'a from the &mut HashMap invariance.

At first I wanted to write impl<'a: 'b, 'b> Borrow<Foo<'b>> for Foo<'a>, but this collides with the core impl<T> Borrow<T> for T, even though the lifetimes in mine should technically distinguish T. Maybe that’s a bug, not sure.

However, since Foo is just a shell around Cow, with the same Hash and Eq, it’s possible to cheat this!

impl<'a: 'b, 'b> Borrow<Cow<'b, str>> for Foo<'a> {
    fn borrow(&self) -> &Cow<'b, str> {
        &self.v
    }
}

fn do_stuff<'a: 'b, 'b>(map: &mut HashMap<Foo<'a>, i32>, key: &Foo<'b>) {
    map.get(key); // works!
    map.get_mut(&key.v); // index by `Cow` -- works!
}

It only works because that custom impl Borrow spells out the lifetime reduction. If it were written with a single lifetime, then we’d still be stuck in the same trap.


#6

This is perhaps even better, although it gets dubious to assure that Hash stays the same. But you could always implement a manual Hash to be sure it’s the same as &str.

impl<'a> Borrow<str> for Foo<'a> {
    fn borrow(&self) -> &str {
        &self.v
    }
}

fn do_stuff<'a: 'b, 'b>(map: &mut HashMap<Foo<'a>, i32>, key: &Foo<'b>) {
    map.get(key); // works!
    map.get_mut(&*key.v); // index by &str -- works!
}