Rust multiple mutable self borrowing from method calls

Question

I am learning Rust. For my first program, I wrote this code to maintain data about a partial ordering:

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

struct Node {
    num_before: usize,
    successors: HashSet<String>,
}

impl Node {
    fn new() -> Node {
        Node {
            num_before: 0,
            successors: HashSet::new(),
        }
    }
}

pub struct PartialOrdering {
    node: HashMap<String, Node>,
}

impl PartialOrdering {
    pub fn new() -> PartialOrdering {
        PartialOrdering {
            node: HashMap::new(),
        }
    }

    pub fn get_node(&mut self, name: &String) -> &mut Node {
        self.node.entry(name.clone()).or_insert_with(Node::new)
    }

    pub fn add_order(&mut self, before: &String, after: &String) {
        let mut before_node = self.get_node(before);
        if after != before {
            let mut after_node = self.get_node(after);
            if before_node.successors.insert(after.clone()) {
                after_node.num_before += 1;
            }
        }
    }
}

Compiling this code produces this error:

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> main.rs:35:25
   |
33 |         let before_node = self.get_node(before);
   |                           ---- first mutable borrow occurs here
34 |         if after != before {
35 |             let mut after_node = self.get_node(after);
   |                                  ^^^^ second mutable borrow occurs here
36 |             if before_node.successors.insert(after.clone()) {
   |                ---------------------- first borrow later used here

Admittedly I am new to the Rust borrowing rules, but this problem has me stumped. Please tell me what I am doing wrong, and how can I fix it?

That your nodes hold references to their "successors", and a count of their "predecessors" (thus how many references are held to them—presumably so that no node is dropped while a predecessor still holds a reference to it?), is strikingly reminiscent of Rc, the standard library's ref-counted pointer. Using that instead would enable you to take ownership of cheap copies of the node pointers, and thus not hold onto mutable borrows. — eggyal
However, mutating the data pointed at by an Rc requires "interior mutability" (i.e. run-time, rather than compile-time, borrow checking) which can be achieved with RefCell. Putting it together, you'd have Rc<RefCell<Node>> (albeit Node itself would no longer need to contain the fields shown in your example above). — eggyal
@eggyal RwLock and Mutex also provide run-time borrow-checking at a bit of a higher level. These types are implemented using UnsafeCell, as is RefCell---when it comes to interior mutability in rust, all roads point to UnsafeCell. — Emerson Harkin
To clarify the purpose of the num_before field, this code is from a Rust version of the tsort utility. The partial ordering of the tokens is created by calling add_order for each pair of tokens read from input. For each token, the num_before field is basically a count of the number of tokens known to be before it in the partial ordering, which is useful for generating the tsort output. — Frank Lhota

Emerson Harkin Emerson Harkin · Accepted Answer · 2020-07-22T22:53:54

The problem is that in Rust it is forbidden to take more than one mutable reference (&mut) to an object at a time (see here for details). Your get_node() takes &mut self and uses it to obtain an &mut Node contained in self (where self is a PartialOrdering). This causes the mutable borrow of self to exist for as long as the value returned by get_node() exists, preventing other calls to get_node(). This means that you can't have before_node: &mut Node and after_node: &mut Node in the same scope, unfortunately.

Rust multiple mutable self borrowing from method calls

1 Answers