Unexpected lifetime issue with HashMap remove()

help
1

Hey! I have just run into the following borrow checker issue:

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

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

fn main() {
    let key = Key { a: Cow::Owned("test".to_string()) };
    let mut map = HashMap::new();
    
    map.insert(key.clone(), 3i32);
    remove(&mut map, &key)
}

fn remove(map: &mut HashMap<Key, i32>, key: &Key) {
    map.remove(key);
}

error: lifetime may not live long enough
  --> src/main.rs:18:5
   |
17 | fn remove(map: &mut HashMap<Key, i32>, key: &Key) {
   |           ---                          --- has type `&Key<'1>`
   |           |
   |           has type `&mut HashMap<Key<'2>, i32>`
18 |     map.remove(key);
   |     ^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'2`

Playground link

The issue occurs with other methods that have an &mut self receiver like get_mut but not with methods that have a &self receiver like get.

I'm not sure why Rust would disallow forwarding the call to the HashMap. Calling remove directly from within main works.

2

You can fix this by specifying that map and key use the same Key<'a> type:

fn remove<'a>(map: &mut HashMap<Key<'a>, i32>, key: &Key<'a>) {
    map.remove(key);
}

or more generally by ensuring that the type in key is at least as long-lived as the type in map:

fn remove<'a, 'b>(map: &mut HashMap<NodeKey<'a>, i32>, key: &NodeKey<'b>)
where 'b: 'a {
    map.remove(key);
}
1 Like
3

Don't swallow lifetime parameters in generics. You'll only confuse yourself. Always write out the lifetime parameters of user-defined types.

4

I'm not sure I understand why this bound is required. The key is only used to fetch the element being removed (just like in get) why does it need to have an internal lifetime that matches that of the map keys?

5

A more complete example of how I ran into this looks like this: playground.

Requiring the key argument's contents to have the same lifetime as that of the map's keys' contents seems excessive. Do you know why the compiler requires it?

6

remove<Q>(&mut self, k: &Q) requires K: Borrow<Q>. In this case your K is Key<'k> and your Q is, let's say, Key<'q>.

These are your own types, and you haven't implemented Borrow<_> for them, so there must be a blanket implementation in play. And indeed, it's this one:

impl<T> Borrow<T> for T
where
    T: ?Sized,

But types that differ only by lifetime are still different types, and type parameters like T can only resolve to a single type. So that's why the lifetimes have to be the same: Key<'k>: Borrow<Key<'k>> is satisfiable, but Key<'k>: Borrow<Key<'q>> is not, unless 'k == 'q.

Moreover, the blanket implementation conflicts with naively writing a more general implementation for lifetime-carrying structs like Key<'_>.

// Fails: Conflicting implementation
impl<'a: 'b, 'b> std::borrow::Borrow<Key<'b>> for Key<'a> {
    // ..
}

However, you can perhaps borrow something else.

impl std::borrow::Borrow<str> for Key<'_> {
    fn borrow(&self) -> &str {
        &*self.a
    }
}
// ...
impl Map {
    fn remove(&mut self, key: &Key<'_>) {
        self.map.remove(&*key.a);
    }
}

But be sure you meet the logical invariants expected of Borrow implementors.

More extreme solutions may also apply.

2 Likes
7

That's exactly the answer I was looking for! Thank you so much :slight_smile:

8

The question is already answered, but I'd like to provide another point of view.

One of the reasons why the code in OP is forbidden is invariance of exclusive references. If we were using get, which requires only a shared reference to HashMap, and not remove, the otherwise-same signature would allow the code to compile - playground.

To see why the invariance is necessary here, let's think about what happens when one inserts something in the HashMap first. Consider the following code:

fn main() {
    let mut map = HashMap::new();
    
    {
        let key_string = String::from("42");
        let key = NodeKey { a: Cow::Borrowed(&key_string) };
        get(&map, &key);
        map.insert(key, 42);
    }
    
    println!("{:?}", map);
}

fn get(map: &HashMap<NodeKey, i32>, key: &NodeKey) {
    map.get(key);
}

In this case, allowing to insert key would lead to a use-after-free on println, since key borrows from key_string, and key_string is dropped by the end of the block. Now, your remove function can't lead to the same use-after-free, but compiler doesn't know it - all it sees is the signature, and the signature wouldn't change if you replaced remove with insert. Therefore, this call has to be prohibited, too.

And finally, note that the call to get function is not problematic here, even though the key's (inner) lifetime is shorter then map's - since get uses only shared references, not exclusive ones, compiler can shrink the inner lifetime accordingly.

1 Like
9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.