22. Smart pointers: Box, Rc, Arc, Cell, RefCell, Weak

22.1 Box for recursive types

#[derive(Debug)]
enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>),  // without Box, Expr would have infinite size
    Mul(Box<Expr>, Box<Expr>),
}

fn eval(e: &Expr) -> f64 {
    match e {
        Expr::Num(n) => *n,
        Expr::Add(a, b) => eval(a) + eval(b),
        Expr::Mul(a, b) => eval(a) * eval(b),
    }
}

fn main() {
    use Expr::*;
    let e = Add(Box::new(Num(2.0)), Box::new(Mul(Box::new(Num(3.0)), Box::new(Num(4.0)))));
    println!("2 + 3 * 4 = {}", eval(&e)); // 14
}

22.2 Rc, RefCell, and Weak: a tree with parent pointers

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

#[derive(Debug)]
struct Node {
    name: String,
    parent: RefCell<Weak<Node>>,        // Weak: a child must not keep its parent alive (no cycle)
    children: RefCell<Vec<Rc<Node>>>,   // Rc: the parent owns its children
}

fn node(name: &str) -> Rc<Node> {
    Rc::new(Node { name: name.into(), parent: RefCell::new(Weak::new()), children: RefCell::new(vec![]) })
}

fn main() {
    let root = node("/");
    let etc = node("etc");
    *etc.parent.borrow_mut() = Rc::downgrade(&root);
    root.children.borrow_mut().push(Rc::clone(&etc)); // Rc::clone only bumps a counter

    let parent_name = etc.parent.borrow().upgrade().map(|p| p.name.clone());
    println!("etc's parent = {parent_name:?}");
    println!("strong(root)={} weak(root)={} strong(etc)={}",
        Rc::strong_count(&root), Rc::weak_count(&root), Rc::strong_count(&etc)); // 1 1 2

    // RefCell enforces shared-XOR-mutable at RUNTIME:
    let _reading = root.children.borrow();
    let attempt = root.children.try_borrow_mut();       // borrow_mut() here would PANIC
    println!("second mutable borrow allowed? {}", attempt.is_ok()); // false
}

If both directions used Rc, the parent and child would keep each other's count above zero, and neither would ever be freed. That is a reference cycle, and it is a memory leak that safe Rust allows. Rust's rules prevent dangling pointers, not leaks. Use Weak for back-pointers, or use an arena with indices (Ch 27).

22.3 Interior mutability and why it exists

The borrow rules apply to &T versus &mut T. Some designs need mutation through a shared reference: a cache inside an otherwise read-only object, a reference count, or a mock that records calls. Cell, RefCell, Mutex, and atomics allow it by moving the shared-XOR-mutable check to runtime (or making it unnecessary, in Cell's case). All of them are built on UnsafeCell, the only legal way in Rust to mutate through a &.

Rc<RefCell<T>> everywhere is a sign that you are writing a garbage-collected object graph in Rust. It works, but every borrow_mut() can panic at runtime, and you lose the compile-time guarantees that made Rust worth choosing. See Ch 68.