Borrow two mutable values from the same HashMap

Solution 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.

Solution 2:

Use hashbrown::HashMap

If you can switch to using hashbrown, you may be able to use a method like get_each_mut:

use hashbrown::HashMap; // 0.11.2 features=["nightly"]

fn main() {
    let mut map = HashMap::new();
    map.insert(1, true);
    map.insert(2, false);

    dbg!(&map);

    if let [Ok(a), Ok(b)] = map.get_each_mut([&1, &2]) {
        std::mem::swap(a, b);
    }

    dbg!(&map);
}

Unsafe code

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

use std::collections::HashMap;

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: Eq + std::hash::Hash,
{
    unsafe {
        let a = conns.get_mut(a).unwrap() as *mut _;
        let b = conns.get_mut(b).unwrap() as *mut _;
        assert_ne!(a, b, "The two keys must not resolve to the same value");
        (&mut *a, &mut *b)
    }
}

fn main() {
    let mut map = HashMap::new();
    map.insert(1, true);
    map.insert(2, false);

    dbg!(&map);

    let (a, b) = get_mut_pair(&mut map, &1, &2);
    std::mem::swap(a, b);

    dbg!(&map);
}

Similar code can be found in libraries like multi_mut.

This code tries to have an abundance of caution. An assertion enforces that the two values are distinct pointers before converting them back into mutable references and we explicitly add lifetimes to the returned variables.

You should understand the nuances of unsafe code before blindly using this solution. Notably, previous versions of this answer were incorrect. Thanks to @oberien for finding the unsoundness in the original implementation of this and proposing a fix. This playground demonstrates how purely safe Rust code could cause the old code to result in memory unsafety.

An enhanced version of this solution could accept an array of keys and return an array of values:

fn get_mut_pair<'a, K, V, const N: usize>(conns: &'a mut HashMap<K, V>, mut ks: [&K; N]) -> [&'a mut V; N]

It becomes more difficult to ensure that all the incoming keys are unique, however.

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.