Borrow two mutable values from the same HashMap

问题:

I have the following code:

use std::collections::{HashMap, HashSet};

fn populate_connections(
    start: i32,
    num: i32,
    conns: &mut HashMap<i32, HashSet<i32>>,
    ancs: &mut HashSet<i32>,
) {
    let mut orig_conns = conns.get_mut(&start).unwrap();
    let pipes = conns.get(&num).unwrap();

    for pipe in pipes.iter() {
        if !ancs.contains(pipe) && !orig_conns.contains(pipe) {
            ancs.insert(*pipe);
            orig_conns.insert(*pipe);
            populate_connections(start, num, conns, ancs);
        }
    }
}

fn main() {}

The logic is not very important, I'm trying to create a function which will itself and walk over pipes.

My issue is that this doesn't compile:

error[E0502]: cannot borrow `*conns` as immutable because it is also borrowed as mutable
  --> src/main.rs:10:17
   |
9  |     let mut orig_conns = conns.get_mut(&start).unwrap();
   |                          ----- mutable borrow occurs here
10 |     let pipes = conns.get(&num).unwrap();
   |                 ^^^^^ immutable borrow occurs here
...
19 | }
   | - mutable borrow ends here

error[E0499]: cannot borrow `*conns` as mutable more than once at a time
  --> src/main.rs:16:46
   |
9  |     let mut orig_conns = conns.get_mut(&start).unwrap();
   |                          ----- first mutable borrow occurs here
...
16 |             populate_connections(start, num, conns, ancs);
   |                                              ^^^^^ second mutable borrow occurs here
...
19 | }
   | - first borrow ends here

I don't know how to make it work. At the beginning, I'm trying to get two HashSets stored in a HashMap (orig_conns and pipes).

Rust won't let me have both mutable and immutable variables at the same time. I'm confused a bit because this will be completely different objects but I guess if &start == &num, then I would have two different references to the same object (one mutable, one immutable).

Thats ok, but then how can I achieve this? I want to iterate over one HashSet and read and modify other one. Let's assume that they won't be the same HashSet.

回答1:

If you can change your datatypes and your function signature, you can use a RefCell to create interior mutability:

use std::cell::RefCell;
use std::collections::{HashMap, HashSet};

fn populate_connections(
    start: i32,
    num: i32,
    conns: &HashMap<i32, RefCell<HashSet<i32>>>,
    ancs: &mut HashSet<i32>,
) {
    let mut orig_conns = conns.get(&start).unwrap().borrow_mut();
    let pipes = conns.get(&num).unwrap().borrow();

    for pipe in pipes.iter() {
        if !ancs.contains(pipe) && !orig_conns.contains(pipe) {
            ancs.insert(*pipe);
            orig_conns.insert(*pipe);
            populate_connections(start, num, conns, ancs);
        }
    }
}

fn main() {}

Note that if start == num, the thread will panic because this is an attempt to have both mutable and immutable access to the same HashSet.

Safe alternatives to RefCell

Depending on your exact data and code needs, you can also use types like Cell or one of the atomics. These have lower memory overhead than a RefCell and only a small effect on codegen.

In multithreaded cases, you may wish to use a Mutex or RwLock.

回答2:

If you can guarantee that your two indices are different, you can use unsafe code and avoid interior mutability:

fn get_mut_pair<'a, K, V>(conns: &'a mut HashMap<K, V>, a: &K, b: &K) -> (&'a mut V, &'a mut V)
where
    K: std::fmt::Debug + Eq + std::hash::Hash,
{
    unsafe {
        assert_ne!(a, b, "`a` ({:?}) must not equal `b` ({:?})", a, b);
        let a = conns.get_mut(a).unwrap() as *mut _;
        let b = conns.get_mut(b).unwrap() as *mut _;
        (&mut *a, &mut *b)
    }
}

This code tries to have an abundance of caution. An assertion enforces the fact that the two keys are distinct and we explicitly add lifetimes to the returned variables.

You should understand the nuances of unsafe code before blindly using this solution.

---

Note that this function doesn't attempt to solve the original problem, which is vastly more complex than verifying that two indices are disjoint. The original problem requires:

• tracking three disjoint borrows, two of which are mutable and one that is immutable.
• tracking the recursive call
  • must not modify the HashMap in any way which would cause resizing, which would invalidate any of the existing references from a previous level.
  • must not alias any of the references from a previous level.

Using something like RefCell is a much simpler way to ensure you do not trigger memory unsafety.