137. Box, Rc and RefCell

Who owns the upvalue?

Here is a variation on chapter 57’s counter, in Drip:

fn makeCounter() {
  let n = 0;
  fn inc() { n = n + 1; }
  fn get() { return n; }
  inc();
  return get;
}

inc and get both capture n. In the TypeScript VM, both closures hold a reference to one ObjUpvalue, and nobody asks which closure owns it: JavaScript’s collector frees it once nothing can reach it.

Rust asks that about every value: one owner, and borrows that end (chapter 124). A VM’s heap breaks both rules constantly. Closures share upvalues; a field can hold a bound method whose receiver is the instance itself. The standard library has three tools for data that doesn’t fit the rules. Let’s see how far they get.

Box: one owner, on the heap

Try to write chapter 31’s syntax tree as a Rust enum:

enum Expr {
    Num(f64),
    Add(Expr, Expr),
}

Rust 1.97 (trimmed):

error[E0072]: recursive type `Expr`
  has infinite size
3 |     Add(Expr, Expr),
  |         ---- recursive without
  |              indirection
help: insert some indirection (e.g.,
  a `Box`, `Rc`, or `&`)

An Expr holding two Exprs would contain itself, so it has no finite size. A Box<Expr> is a pointer, 8 bytes on this machine, so Add(Box<Expr>, Box<Expr>) has a fixed size; the children live on the heap.

A tree is the perfect case: each node has one parent, which owns it.

Rc: shared, counted ownership

The upvalue has two owners, so a Box won’t do.

Rc::new(v) puts v on the heap next to a counter set to 1. Rc::clone(&r) doesn’t copy v: it copies the pointer and adds 1. Dropping an Rc subtracts 1, and when the count reaches 0, v is dropped^[2].

There is a catch. Try to change the upvalue through one owner:

let up = Rc::new(Upvalue { value: 0.0 });
let a = Rc::clone(&up);
a.value += 1.0;

error[E0594]: cannot assign to data in
  an `Rc`

Of course: a and up point at the same value, and chapter 125 said many readers or one writer. An Rc only gives out shared access.

RefCell: the borrow checker, at run time

A RefCell<T> holds a value and a little borrow counter. borrow() gives you a reader, borrow_mut() a writer, and each call first checks the rules from chapter 125. Put one inside an Rc and you have shared, mutable data: Rc<RefCell<Upvalue>>, the textbook way to share mutable state^[1].

use std::cell::RefCell;
use std::rc::Rc;

// A captured variable, shared by
// two closures (chapter 57).
struct Upvalue {
    value: f64,
}

struct Closure {
    name: &'static str,
    up: Rc<RefCell<Upvalue>>,
}

fn main() {
    let up = Rc::new(RefCell::new(
        Upvalue { value: 0.0 },
    ));
    let inc = Closure {
        name: "inc",
        up: Rc::clone(&up),
    };
    let get = Closure {
        name: "get",
        up: Rc::clone(&up),
    };
    println!("owners: {}",
        Rc::strong_count(&up));
    inc.up.borrow_mut().value += 1.0;
    inc.up.borrow_mut().value += 1.0;
    let v = get.up.borrow().value;
    println!("{} sees {}", get.name, v);
    drop(inc);
    drop(get);
    println!("owners: {}",
        Rc::strong_count(&up));
}

It prints owners: 3 (the original plus two closures), get sees 2, and then owners: 1. It works.

But “checked at run time” means failing at run time too. Drip happily runs a.heal(a): heal a using its own hit points. Here is that method written with RefCell:

fn heal(me: &RefCell<Instance>,
    other: &RefCell<Instance>) {
    let mut m = me.borrow_mut();
    let o = other.borrow();
    m.hp += o.hp / 2.0;
}

heal(&a, &b) is fine. Then heal(&a, &a), built with cargo and rustc 1.97 (the panic line is wrapped here):

a: 12

thread 'main' (24945) panicked at
  src/main.rs:12:19:
RefCell already mutably borrowed

The compiler saw two parameters and no broken rule. The rule was broken by which objects were passed, and in a VM the Drip program makes that choice. Any VM code that holds a borrow while it touches another object is one aliasing program away from a panic.

Cycles never reach zero

Give each object a field that can hold another, and a Drop that prints. Then build a chain and a cycle:

// Obj { name, field }, with a Drop
// that prints "free" and the name
{
    let a = new("a");
    let b = new("b");
    a.borrow_mut().field =
        Some(Rc::clone(&b));
}
{
    let c = new("c");
    let d = new("d");
    c.borrow_mut().field =
        Some(Rc::clone(&d));
    d.borrow_mut().field =
        Some(Rc::clone(&c));
    println!("c has {} owners",
        Rc::strong_count(&c));
}
println!("end of main");

Run with rustc 1.97, it prints:

free a
free b
c has 2 owners
end of main

The chain is freed. c and d never are. Step through the counts:

{
    let c = new("c");
    let d = new("d");
    c.borrow_mut().field =
        Some(Rc::clone(&d));
    d.borrow_mut().field =
        Some(Rc::clone(&c));
} // c and d go out of scope

The standard library is blunt: a cycle between Rc pointers will never be deallocated^[2]. The Rust book adds that a leak is still memory safe^[1]. The usual fix is Weak, a non-owning pointer for the edge that points “back”.

A VM can’t use that fix. let a = Node(); a.me = a; is a one-line cycle, and a recursive local function captures itself through an upvalue. The program decides which edges point back. A VM needs the question mark-and-sweep asks (chapter 58): what can the roots reach?

Your turn

use std::cell::RefCell;
use std::rc::Rc;

// One captured variable, shared.
type Up = Rc<RefCell<f64>>;

struct Closure {
    up: Up,
}

// Share `up`; don't copy it.
fn capture(up: &Up) -> Closure {
    todo!()
}

impl Closure {
    // Add 1 to the captured variable.
    fn bump(&self) {
        todo!()
    }

    fn read(&self) -> f64 {
        todo!()
    }
}

enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
}

fn add(a: Expr, b: Expr) -> Expr {
    todo!()
}

fn mul(a: Expr, b: Expr) -> Expr {
    todo!()
}

fn eval(e: &Expr) -> f64 {
    todo!()
}

What you learned

• A Box<T> puts a value on the heap with exactly one owner. It makes recursive types like syntax trees possible.
• An Rc<T> shares a value among owners with a strong count, and drops it when the count reaches 0. It only gives shared access.
• A RefCell<T> checks the borrowing rules at run time, and panics when they are broken: RefCell already mutably borrowed.
• Cycles of Rc never reach a count of 0, so they leak. A VM’s object graph is full of cycles that the program, not you, decides.
• drip-rs uses Box and Rc only where ownership is simple, and gives its objects to its own collector instead.