A Way to Understand RefCell in Rust

Rust is great. All the rules around references prevent bad things from happening. Then something confused me (obviously one of many times this happens, Rust is confusing to untrained brains): RefCell.

There is a Rust rule saying that mutable references shouldn't have any alias, what's the point if RefCell just bypassing all that restrictions? All the terms like interior mutability are great. But I still couldn't intuitively understand why that's the case until recently. But recently I figured out a link that make things fit together better.

Assume that we have a graph-like data structure and we need to perform updates through the edges.

// Version 1
struct Node<'t> {
    val: i32,
    neighbors: Vec<&'t mut Node<'t>>,
}

fn update_neighbors(node: &mut Node) {
    for neighbor in node.neighbors.iter_mut() {
        neighbor.val = neighbor.val + 1;
    }
}

fn main() -> (){
    let mut node0 = Node { val: 4, neighbors: vec![] };
    let mut node1 = Node { val: 5, neighbors: vec![] };
    node1.neighbors.push(&mut node0);
    node0.neighbors.push(&mut node1); // Error! borrowing `node1.neighbors` as mutable more than once
    update_neighbors(&mut node2);
}

Naturally a graph are allowed to have cycles, but here it cannot work because the code contains circular mutable references. The cycle cannot be closed because it needs mutability in two places.

A way to get around this is to use an integer index to represent each node, instead of a reference. And separate the "reference" part of the type definition into a different type.

// Version 2
struct NodeContent {
    val: i32,
}

struct Node {
    neighbors: Vec<usize>,
}

fn update_neighbors(node: &Node, contents: &mut Vec<NodeContent>) {
    for neighbor in node.neighbors.iter() {
        contents[*neighbor].val = contents[*neighbor].val + 1;
    }
}

fn main() -> () {
    let mut node0 = Node { neighbors: vec![] };
    let mut node1 = Node { neighbors: vec![] };
    let mut contents = vec![ NodeContent { val: 4 }, NodeContent { val: 5 }];
    node1.neighbors.push(0);
    node0.neighbors.push(1);
    update_neighbors(&node1, &mut contents);
}

The only problem with this solution is that now everytime a Node is passed around, the contents vector needs to follow it. Parallel array should not be the best we can do in year 2024. Now a RefCell version of the solution.

// Version 3
use std::cell::RefCell;

struct NodeInner<'t> {
    val: i32,
    neighbors: Vec<&'t RefCell<NodeInner<'t>>>,
}
type Node<'t> = RefCell<NodeInner<'t>>;

fn update_neighbors(node_cell: &Node) {
    let node = node_cell.borrow();
    for neighbor_cell in node.neighbors.iter() {
        let mut neighbor = neighbor_cell.borrow_mut();
        neighbor.val = neighbor.val + 1;
    }
}

fn main() -> (){
    let node1 = RefCell::new(NodeInner { val: 4, neighbors: vec![] });
    let node2 = RefCell::new(NodeInner { val: 5, neighbors: vec![] });
    node2.borrow_mut().neighbors.push(&node1);
    node1.borrow_mut().neighbors.push(&node2);
    update_neighbors(&node2);
}

Node is now represented as a RefCell. The version 3 structurally looks like the version 1 of the program, but in spirit it's closer to vesion 2. The RefCell references are analogous to the indices in version 2, and borrow_mut is analogous to using the indices to mutate the content vector.

Now let's go back to the question: the intuitive reason that it is perfectly fine to get mutable references out of immutable ones is the existence of techniques shown in version 2, where mutability is decomposed. RefCell can be thought of a simpler way to write such code without doing parallel arrays.

Parallel array and RefCell are still not quite equivalent in this context. One such difference would be self-references and weak-references. But let's not focus on those details :).