Why can't I have mutable references in if-else branches of a HashMap?

[mayurdzk]

Hey!

I'm curious about an error reported by the Rust compiler. Here's a sample piece of code:

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<String, u32> = HashMap::new();
    
    let key = "Key".to_string();
    if let Some(number) = map.get_mut(&key) {
        *number += 1;
    } else {
        map.insert(key, 1);
    }
}

The compiler complains with:

error[E0499]: cannot borrow map as mutable more than once at a time
--> src/main.rs:10:9
|
7 | if let Some(number) = map.get_mut(&key) {
| --- first mutable borrow occurs here
...
10 | map.insert(key, 1);
| ^^^ second mutable borrow occurs here
11 | }
| - first borrow ends here

Here's a link to a playground with the same code.

---

It doesn't seem obvious to me why this error would occur? Both the branches in this if-else statement are entirely distinct. Why does the Rust compiler interpret the insert as a second mutable borrow?

[leonardo]

On Nightly #![feature(nll)] fixes this problem.

[krdln]

Also, check out the entry method. The example is almost the same as your usecase

[leonardo]

fn main() {
    use std::collections::HashMap;

    let mut map = HashMap::new();
    let key = "Key".to_string();
    *map.entry(key).or_insert(0) += 1;
}

[Bert-Proesmans]

What you typed is syntax sugar. This means that the compiler will expand it (like a macro) to properly handle the operation you're trying to perform.
Consider the following expansion, which results in the exact same error.
Note: This is not exact, since i have not looked into the compiler but it shows the problem more clearly.

let key = "Key".to_string();
{
    let value_opt: Option<&mut u32> = map.get_mut(&key);
    if value_opt.is_some() {
        *value_opt.unwrap() += 1;
    } else {
        map.insert(key, 1);
    }
}

Rust Playground

Do you see the issue now?
Firstly the match construct is expanded into a new scope, containing the borrows of map and key.
Then the returned optional is checked if it actually contains a value.

If yes, update that value... So far OK!

If no, insert that key with a new value.. But this cannot work:
We need a mutable borrow of map to insert, but the borrow rule is that we CAN NOT have multiple mutable borrows at the same time. The compiler tells us there is still a mutable borrow in scope (it hasn't been dropped yet).

-> The first borrow is made by calling get_mut() and the compiler inferred there that a mutable borrow is necessary.
-> That borrow is actually re-borrowed to create variable value_opt. For the re-borrow to be valid it's necessary that its 'parent borrow' is still alive (in scope).
-> Dropping value_opt will also drop the borrow of map.

So to make this work we need to break the outer scope, which starts right after

let key = "Key".to_string();

You could do this by inserting a return; as last statement of the IF-TRUE block, but this is not always possible and requires a function context.
Alternatively you could set a local boolean value to true and end the scope. Underneath you could test the boolean and insert if necessary.
Or specifically built for HashMap; the Entry API.

OK, but can't the compiler infer that i'm not using value_opt within the ELSE block? This example is perfectly valid!
Yes, it's a situation where there are actually no issues with the logic.
No, the compiler cannot infer this because the language we use to talk to it (the Rust syntax) is not expressive enough to literally indicate we stopped using a variable. We can only tell the compiler which variables are valid for the entirety of its scope, so the compiler drops these variables only when their scope is closed.

! There have been made improvements with a new feature called NLL (Non-lexical-lifetimes). It does exactly what it sounds like; it internally tests if variables are still used or not and can drop them before their ACTUAL SCOPE ends. Using this NLL feature will allow the example from your original post to compile.

[vitalyd]

As was already mentioned, this particular scenario is one of the original examples/motivations for introducing NLL: problem case 2.

[mayurdzk]

@Leonardo, @krdln thank you so much for writing in! I'm using entry to solve my problem for now.
@Bert-Proesmans thanks for the explanation. It makes sense if what I wrote is just syntactic sugar.

It's good to learn about NLL and I'm happy we can get rid of such problems in an upcoming version of Rust. Thanks for the link @vitalyd!

[mayurdzk]

I have another question that relates to this one. Say I'm trying to create an iterator for my type Store that is internally backed by a HashMap. When a caller calls next(), the value comes from the map underneath and it's removed from the map. Here's what it looks like:

use std::collections::HashMap;

struct Store {
    map: HashMap<String, i32>
}

impl Iterator for Store {
    type Item = i32;

    // Remove a key-value from the map and return it out in arbitrary order.
    fn next(&mut self) -> Option<i32> {
        let mut first_key: Option<&String> = None;

        for key in self.map.keys() {
            first_key = Some(key);
            break;
        }

        if first_key.is_some() {
            let next_key = self.map.remove(
                first_key.unwrap()
            ).unwrap();
            return Some(next_key);
        } else {
            return None;
        }
    }
}

fn main() { }

The error here is clear to me, given the knowledge I've gained from this thread. for key in self.map.keys() has a borrow, and self.map.remove is attempting to get a mutable borrow. That isn't allowed.

But how about when I change the next function to look like this:

// Remove a key-value from the map and return it out in arbitrary order.
    fn next(&mut self) -> Option<i32> {
        let mut first_key: Option<&String> = None;
        
        {
            for key in self.map.keys() {
                first_key = Some(key);
                break;
            }
        }

        if first_key.is_some() {
            let next_key = self.map.remove(
                first_key.unwrap()
            ).unwrap();
            return Some(next_key);
        } else {
            return None;
        }
    }

I've moved the first borrow into its own scope. That a borrow occurs in self.map.keys() should be invisible to self.map.remove? But I still see the same problem occur.
Playground link to the code above.

---

The way this problem is fixed is by making first_key a Option<String> like so:

// Remove a key-value from the map and return it out in arbitrary order.
    fn next(&mut self) -> Option<i32> {
        let mut first_key: Option<String> = None;

        {
            for key in self.map.keys() {
                first_key = Some(key.to_string());
                break;
            }
        }

        if first_key.is_some() {
            let next_key = self.map.remove(
                &first_key.unwrap()
            ).unwrap();
            return Some(next_key);
        } else {
            return None;
        }
    }

So I'm assuming the borrow to map is somehow tying in with the lifetime of first_key. I fail to understand why though?
My best guess:

1. Rust sees first_key as being a reference to an object and assigns a lifetime to it.
2. When the compiler sees first_key = Some(key), it assumes it needs to keep the reference to map alive as long as first_key.
3. When self.map.remove in encountered, the compiler denies the mutable borrow because a reference to map is already alive.

Is that correct? (If my explanation is correct, NLL fixes this too, right?)

[vitalyd]

@mayurdzk

So I’m assuming the borrow to map is somehow tying in with the lifetime of first_key . I fail to understand why though?
My best guess:

1. Rust sees first_key as being a reference to an object and assigns a lifetime to it.
2. When the compiler sees first_key = Some(key) , it assumes it needs to keep the reference to map alive as long as first_key .
3. When self.map.remove in encountered, the compiler denies the mutable borrow because a reference to map is already alive.

Is that correct? (If my explanation is correct, NLL fixes this too, right?)

first_key holds a reference into the HashMap, and that reference is still alive and used when you call self.map.remove() - NLL does not fix this because there’s no real issue to fix here . Imagine the map’s internal storage is cleared or reallocated as part of remove() - compiler doesn’t know what remove() does exactly. If it did allow that, you’d be left holding a dangling reference while remove() is executing.

To your use case, take a look at HashMap in std::collections - Rust

[mayurdzk]

@vitalyd Crap, you're right. Thanks for clearing this up for me.

I'd tried Drain before coming up with my cockamamy solution but it didn't work for me and I didn't spend as much time trying to get it to work. I'll have to spend more time with it.