Why doesn't non-lexical lifetimes work here?

use std::collections::HashMap;

fn lookup<'a>(map: &'a mut HashMap<String, String>, key: &str) -> &'a mut String {
    if let Some(s) = map.get_mut(key) {
        return s;
    }
    let value = generate(map);
    map.insert(key.into(), value);
    map.get_mut(key).unwrap()
}

fn generate(_map: &mut HashMap<String, String>) -> String {
    // expensive operation
    todo!()
}

The above code produces the following error:

error[E0499]: cannot borrow `*map` as mutable more than once at a time
 --> src/lib.rs:8:26
  |
4 | fn lookup<'a>(map: &'a mut HashMap<String, String>, key: &str) -> &'a mut String {
  |           -- lifetime `'a` defined here
5 |     if let Some(s) = map.get_mut(key) {
  |                      --- first mutable borrow occurs here
6 |         return s;
  |                - returning this value requires that `*map` is borrowed for `'a`
7 |     }
8 |     let value = generate(map);
  |                          ^^^ second mutable borrow occurs here

s is not live during the call to generate. Is there a way to make this work without more than one map lookup in the common case when key is present in the map?

If I'm correct, this is a case which NLL was revised to not handle, as it was too hard. There's an issue on it here: https://github.com/rust-lang/rust/issues/58910.

If your generation didn't require access to the map, I'd suggest the entry API - something like map.entry(key.into()).or_insert_with(|| generate()). Unfortunately, that won't work if you need to access the map in between looking up the value & inserting the new value.

As it stands, the best I can come up with is to do a duplicate lookup:

fn lookup<'a>(map: &'a mut HashMap<String, String>, key: &str) -> &'a mut String {
    if map.contains_key(key) {
        return map.get_mut(key).unwrap();
    }
    let value = generate(map);
    map.insert(key.into(), value);
    map.get_mut(key).unwrap()
}

Ideally we would avoid that, but I couldn't find a way to.

We can make one more slight improvement, though! Using the entry API in the "not found" branch allows merging the insert and get_mut lookups:

fn lookup<'a>(map: &'a mut HashMap<String, String>, key: &str) -> &'a mut String {
    if map.contains_key(key) {
        map.get_mut(key).unwrap()
    } else {
        let value = generate(map);
        map.entry(key.into()).or_insert(value)
    }
}

This has subtly different behavior if generate modifies the map such that key is populated - the old code would replace that old value, this new code keeps it and discards the new value. If old behavior is necessary, I'd suggest:

fn lookup<'a>(map: &'a mut HashMap<String, String>, key: &str) -> &'a mut String {
    if map.contains_key(key) {
        map.get_mut(key).unwrap()
    } else {
        let value = generate(map);
        match map.entry(key.into()) {
            hash_map::Entry::Vacant(e) => e.insert(value),
            hash_map::Entry::Occupied(e) => {
                e.insert(value);
                e.into_mut()
            }
    }
}
2 Likes

That is unfortunate. I looks like I'll have to rework my API to be less flexible (ie without access to the map) to avoid the second lookup.

Thanks for the help and suggestions!

1 Like

Did you check to see if the compiler optimized away the second lookup? It seems possible, since lifetimes don't affect the generated code.

2 Likes

The next-generation borrow checker Polonius will be able to compile your original code. You can try the experimental version in the nightly toolchain by compiling with rustc -Z polonius.

4 Likes

The stable compiler is not able to optimize away the second lookup. https://rust.godbolt.org/z/R_iLW6

It is probably pretty hard for the compiler to figure out get() is idempotent, given all the unsafe SSE and pointer manipulation hashbrown does.

FWIW, hashbrown even repeats lookups itself:
https://gankra.github.io/blah/hashbrown-insert/

But you could save on the time to compute the actual hash value by providing that manually, using raw_entry/raw_entry_mut.

1 Like

I had forgotten about that article, thanks!

Good to know that raw_entry allows using precomputed hashes.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.