rust - How should I restructure my graph code to avoid an "Cannot borrow variable as mutable more than once at a time" error?

Question

I have a simple graph that successfully compiles:

use std::collections::HashMap;

type Key = usize;
type Weight = usize;

#[derive(Debug)]
pub struct Node<T> {
    key: Key,
    value: T,
}
impl<T> Node<T> {
    fn new(key: Key, value: T) -> Self {
        Node {
            key: key,
            value: value,
        }
    }
}

#[derive(Debug)]
pub struct Graph<T> {
    map: HashMap<Key, HashMap<Key, Weight>>,
    list: HashMap<Key, Node<T>>,
    next_key: Key,
}
impl<T> Graph<T> {
    pub fn new() -> Self {
        Graph {
            map: HashMap::new(),
            list: HashMap::new(),
            next_key: 0,
        }
    }
    pub fn add_node(&mut self, value: T) -> &Node<T> {
        let node = self.create_node(value);
        node
    }

    fn create_node(&mut self, value: T) -> &Node<T> {
        let key = self.get_next_key();
        let node = Node::new(key, value);
        self.list.insert(key, node);
        self.map.insert(key, HashMap::new());
        self.list.get(&key).unwrap()
    }

    fn get_next_key(&mut self) -> Key {
        let key = self.next_key;
        self.next_key += 1;
        key
    }
}

But it fails to compile when I use it:

fn main() {
    let mut graph = Graph::<i32>::new();
    let n1 = graph.add_node(111);
    let n2 = graph.add_node(222);
}

Error:

error[E0499]: cannot borrow `graph` as mutable more than once at a time
  --> src/main.rs:57:14
   |
56 |     let n1 = graph.add_node(111);
   |              ----- first mutable borrow occurs here
57 |     let n2 = graph.add_node(222);
   |              ^^^^^ second mutable borrow occurs here
58 | }
   | - first borrow ends here

I have seen all similar questions. I know that is failing because method Graph::add_node() uses &mut self. In all similar questions, the general answer is "restructure your code". I can't understand what should I do? How should I restructure this code?

Answer 1

By returning a &Node<T> from add_node, you are effectively locking the whole Graph<T> object, because you're borrowing from it. And for a good reason; try running this main:

fn main() {
    let mut graph = Graph::<i32>::new();
    let n1 = graph.add_node(111) as *const _;
    let mut inserts = 0;
    loop {
        inserts += 1;
        graph.add_node(222);
        let n1bis = graph.list.get(&0).unwrap() as *const _;
        if n1 != n1bis {
            println!("{:p} {:p} ({} inserts)", n1, n1bis, inserts);
            break;
        }
    }
}

Here's a possible output from this program:

0x7f86c6c302e0 0x7f86c6c3a6e0 (29 inserts)

This program adds a first node and stores its address as a raw pointer (raw pointers don't have a lifetime parameter, so the borrow on Graph is released). Then, it adds more nodes, one at a time, then fetches the address of the first node again. If the address of the first node changed, it prints both addresses as well as the number of additional nodes that were inserted into the graph.

HashMap uses a randomized hash, so the number of inserts will vary on each execution. However, it will eventually need to reallocate memory to store more entries, so eventually, the address of the nodes in the map change. If you tried to dereference an old pointer (such as n1) after this happened, then you'd be accessing freed memory, which may return garbage data or cause an error (usually a segmentation fault).

Knowing all this, it should be clear that add_node should not return a &Node<T>. Here are a few alternatives:

• Make add_node return nothing, or return the Key, and provide a separate method to obtain a &Node<T> given a key.
• Wrap your nodes in Rc<T> or Arc<T>. That is, instead of list being a HashMap<Key, Node<T>>, it would be a HashMap<Key, Rc<Node<T>>>. You can clone() an Rc or Arc to copy the pointer and increment the reference count; store one copy in the HashMap and return the other copy from add_node.
  • If you also need to mutate the nodes while retaining the ability to mutate the graph, you may need to combine Rc with RefCell, or Arc with Mutex.