Unable to mutably borrow the contents inside a RefCell, even after the scope of the previous mutable borrow has ended

Question

Consider the following bit of code

use std::{cell::RefCell, rc::Rc};

type NodeRef = Rc<RefCell<_Node>>;

#[derive(Debug)]
struct _Node {
    id: usize,
    data: Option<NodeRef>,
    edges: Vec<NodeRef>,
}

impl _Node {
    fn add(&mut self, other: NodeRef) {
        println!("at {}", self.id);

        self.data = match self.data.take() {
            Some(current_data) => {
                {
                    let mut current_data_raw = current_data.borrow_mut();
                    current_data_raw.id += other.borrow().id;
                }
                Some(current_data)
            }
            None => Some(Rc::clone(&other)),
        };

        for e in &self.edges {
            e.borrow_mut().add(Rc::clone(&other));
        }

        println!("done {}", self.id);
    }
}

#[derive(Debug)]
struct Node(NodeRef);

impl Node {
    fn new(id: usize) -> Node {
        Node(Rc::new(RefCell::new(_Node {
            id,
            data: None,
            edges: vec![],
        })))
    }

    fn add_edge(&self, other: &Node) {
        self.0.borrow_mut().edges.push(Rc::clone(&other.0));
    }

    fn add(&self, other: Self) {
        self.0.borrow_mut().add(other.0);
    }
}

fn main() {
    let a = Node::new(0);
    let b = Node::new(1);
    let c = Node::new(2);
    let d = Node::new(3);
    let e = Node::new(4);
    let f = Node::new(5);

    d.add_edge(&a);
    d.add_edge(&b);

    e.add_edge(&b);
    e.add_edge(&c);

    f.add_edge(&d);
    f.add_edge(&e);

    f.add(Node::new(6));
}

The output generated on running this is

at 5
at 3
at 0
done 0
at 1
done 1
done 3
at 4
at 1
thread 'main' panicked at 'already mutably borrowed: BorrowError', src/libcore/result.rs:1009:5

This creates a graph of the form

F--E--A 
 \  \
  \   B
   \ /
    D
     \ 
      C

I am trying to propagate a value through the entire graph, so it starts from F, and goes to E and D. From E it goes to A and B without any error. Then from D, the runtime panics saying the RefCell constraint for mutable borrows has been broken.

It seems that it is considering the mutable borrow from the previous invocation of the callback with B, however, the mutable borrow (current_data_raw) inside _Node::add has a limited scope, and after the scope ends, I should be allowed to mutably borrow the value again. From the output, when the function is called for node B for the second time, the entire first invocation of the function and not just the mutable borrow scope has exited.

What am I missing here?

Idiomatic Rust uses a leading underscore to indicate that a variable or type is unused. That's not the case here, so you should not name your type _Node. — Shepmaster

Shepmaster Shepmaster · Accepted Answer · 2019-01-20T15:59:18

What am I missing here?

Your algorithm is broken. You can see this by adding this debugging code inside of the Some arm of the match:

{
    let a = current_data.borrow();
    let b = other.borrow();

    assert_ne!(a.id, b.id);
}

This fails:

thread 'main' panicked at 'assertion failed: `(left != right)`
  left: `6`,
 right: `6`', src/main.rs:23:25

You are trying to borrow the exact same node twice at the same time.

Unable to mutably borrow the contents inside a RefCell, even after the scope of the previous mutable borrow has ended

1 Answers