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);
}
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.
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.
3 Likes
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.
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.
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!
}