rust - Returning a reference from a HashMap or Vec causes a borrow to last beyond the scope it's in?

Question

I've got a persistent compile error where Rust complains that I have an immutable borrow while I'm trying to mutably borrow, but the immutable borrow is from another scope, and I'm not bringing anything across from it.

I have some code that checks for a value in a map, and if it's present, returns it, otherwise it needs to mutate the map in various ways. The problem is that I can't seem to find a way to get Rust let me do both, even though the two operations are totally separate.

Here's some nonsensical code that follows the same structure as my code and exhibits the problem:

use std::collections::BTreeMap;

fn do_stuff(map: &mut BTreeMap<i32, i32>, key: i32) -> Option<&i32> {
    // extra scope in vain attempt to contain the borrow
    {
        // borrow immutably
        if let Some(key) = map.get(&key) {
            return Some(key);
        }
    }

    // now I'm DONE with the immutable borrow, but rustc still thinks it's borrowed

    map.insert(0, 0); // borrow mutably, which errors
    None
}

This errors out with:

error[E0502]: cannot borrow `*map` as mutable because it is also borrowed as immutable
  --> src/lib.rs:14:5
   |
3  | fn do_stuff(map: &mut BTreeMap<i32, i32>, key: i32) -> Option<&i32> {
   |                  - let's call the lifetime of this reference `'1`
...
7  |         if let Some(key) = map.get(&key) {
   |                            --- immutable borrow occurs here
8  |             return Some(key);
   |                    --------- returning this value requires that `*map` is borrowed for `'1`
...
14 |     map.insert(0, 0); // borrow mutably, which errors
   |     ^^^^^^^^^^^^^^^^ mutable borrow occurs here

This doesn't make any sense to me. How does the immutable borrow outlive that scope?! One branch of that match exits the function via return, and the other does nothing and leaves the scope.

I've seen this happen before where I was mistakenly smuggling the borrow out of the scope in some other variable, but that's not the case here!

True, the borrow is escaping the scope via the return statement, but it's ridiculous that that blocks borrowing farther down in the function -- the program cannot possibly return AND keep going! If I return something else there, the error goes away, so I think this is what the borrow checker is getting hung up on. This feels like a bug to me.

Unfortunately, I've been unable to find any way to rewrite this without hitting the same error, so it's a particularly nasty bug if that's the case.

Answer 1

This is a known issue that will be solved by a future iteration of non-lexical lifetimes, but is not currently handled as of Rust 1.51.

If you are inserting to the same key that you are looking up, I'd encourage you to use the entry API instead.

You can add a smidgen of inefficiency to work around this for now. If the inefficiency is unacceptable, there are deeper workarounds.

HashMap

The general idea is to add a boolean that tells you if a value was present or not. This boolean does not hang on to a reference, so there is no borrow:

use std::collections::BTreeMap;

fn do_stuff(map: &mut BTreeMap<i32, i32>, key: i32) -> Option<&i32> {
    if map.contains_key(&key) {
        return map.get(&key);
    }

    map.insert(0, 0);
    None
}

fn main() {
    let mut map = BTreeMap::new();
    do_stuff(&mut map, 42);
    println!("{:?}", map)
}

Vec

Similar cases can be solved by using the index of the element instead of the reference. Like the case above, this can introduce a bit of inefficiency due to the need to check the slice bounds again.

Instead of

fn find_or_create_five<'a>(container: &'a mut Vec<u8>) -> &'a mut u8 {
    match container.iter_mut().find(|e| **e == 5) {
        Some(element) => element,
        None => {
            container.push(5);
            container.last_mut().unwrap()
        }
    }
}

You can write:

fn find_or_create_five<'a>(container: &'a mut Vec<u8>) -> &'a mut u8 {
    let idx = container.iter().position(|&e| e == 5).unwrap_or_else(|| {
        container.push(5);
        container.len() - 1    
    });
    &mut container[idx]
}

Non-Lexical Lifetimes

These types of examples are one of the primary cases in the NLL RFC: Problem case #3: conditional control flow across functions.

Unfortunately, this specific case isn't ready as of Rust 1.51. If you opt in to the experimental -Zpolonius feature in nightly, each of these original examples compile as-is:

use std::collections::BTreeMap;

fn do_stuff(map: &mut BTreeMap<i32, i32>, key: i32) -> Option<&i32> {
    if let Some(key) = map.get(&key) {
        return Some(key);
    }

    map.insert(0, 0);
    None
}

fn find_or_create_five(container: &mut Vec<u8>) -> &mut u8 {
    match container.iter_mut().find(|e| **e == 5) {
        Some(element) => element,
        None => {
            container.push(5);
            container.last_mut().unwrap()
        }
    }
}

See also:

• How to update-or-insert on a Vec?

  This is the same problem without returning the reference, which does work with the implementation of NLL available in Rust 1.32.

• Double mutable borrow error in a loop happens even with NLL on

  This problem but in a slightly more complicated case.

• When is it necessary to circumvent Rust's borrow checker?

  The ultimate escape hatch.