138. Arenas and typed indices

Pointers become numbers

Chapter 137 ended with three problems. A VM built from Rc<RefCell<..>> leaks every cycle, panics when a program aliases the wrong objects, and hands the question “when does this object die?” to reference counting instead of to the collector you wrote in chapter 58.

drip-rs’s answer is the first of its design notes: arenas and handles, not Rc<RefCell<..>>. No object owns another. One owner, the heap, holds them all. And a reference from one object to another stops being a pointer and becomes a number.

An arena is a Vec of slots

Here is the arena from drip-rs’s object.rs, slightly shortened:

pub struct Arena<T> {
    slots: Vec<Option<T>>,
    free: Vec<u32>,
}

impl<T> Arena<T> {
    pub fn insert(&mut self, o: T)
        -> Gc<T> {
        if let Some(i) = self.free.pop() {
            let i = i as usize;
            self.slots[i] = Some(o);
            return Gc::new(i);
        }
        self.slots.push(Some(o));
        Gc::new(self.slots.len() - 1)
    }
}

Each slot is an Option<T>: Some(object) while it is live, None once the collector frees it. free lists the empty slots, so insert fills a hole before it grows the Vec. remove(index, reuse) calls take() on the slot, which leaves None behind, and puts the index on the free list only if reuse is true. Step through it:

let a = arena.insert(A);
let b = arena.insert(B);
let c = arena.insert(C);
arena.remove(b.index(), reuse);
let d = arena.insert(D);
arena[b] // which object?

drip-rs’s heap has one arena per kind of object: strings, functions, upvalues, closures, classes, instances and so on. Asking the instances arena for slot 7 gives you an ObjInstance, or a panic if slot 7 is empty.

Typed indices

A slot number could be a bare usize. Then nothing stops you using a closure’s number to read the classes arena, and getting some unrelated class back. The fix is a type that wraps the number:

#[derive(Copy, Clone, PartialEq, Eq)]
pub struct ValueId(pub u32);

That is real: engine/rust’s IR keeps its instructions, blocks, functions and bindings in Vecs and names them with ValueId, BlockId, FuncId and BindingId, each a u32 in its own newtype. Pass a BlockId where a ValueId is wanted and it doesn’t compile.

drip-rs has eight object types, so it writes the wrapper once, as a generic:

pub struct Gc<T> {
    index: u32,
    marker: PhantomData<fn() -> T>,
}

The struct has to mention T somewhere, or Rust rejects the unused parameter. PhantomData is a standard-library marker that takes no space and says “act as if a T were involved”. So a Gc<ObjClass> is 4 bytes, just a u32, yet a different type from Gc<ObjClosure>. The arena implements the standard Index trait, which is what makes the arena[handle] syntax call your code, only for handles of its own type:

error[E0308]: mismatched types
   |     let oops = &insts[k];
   |                       ^ expected
   `Gc<Instance>`, found `Gc<Class>`

That error is from the program below, on rustc 1.97. Try uncommenting its last line.

use std::marker::PhantomData;
use std::mem::size_of;
use std::ops::{Index, IndexMut};

// Adapted from drip-rs's object.rs.
struct Gc<T> {
    index: u32,
    marker: PhantomData<fn() -> T>,
}

impl<T> Clone for Gc<T> {
    fn clone(&self) -> Self {
        *self
    }
}
impl<T> Copy for Gc<T> {}

struct Arena<T> {
    slots: Vec<Option<T>>,
}

impl<T> Arena<T> {
    fn insert(&mut self, t: T)
        -> Gc<T> {
        self.slots.push(Some(t));
        let i = self.slots.len() - 1;
        Gc {
            index: i as u32,
            marker: PhantomData,
        }
    }
}

impl<T> Index<Gc<T>> for Arena<T> {
    type Output = T;
    fn index(&self, h: Gc<T>) -> &T {
        let i = h.index as usize;
        match &self.slots[i] {
            Some(t) => t,
            None => panic!("freed"),
        }
    }
}

impl<T> IndexMut<Gc<T>> for Arena<T> {
    fn index_mut(&mut self, h: Gc<T>)
        -> &mut T {
        let i = h.index as usize;
        match &mut self.slots[i] {
            Some(t) => t,
            None => panic!("freed"),
        }
    }
}

struct Class {
    name: String,
}
struct Instance {
    class: Gc<Class>,
    hp: f64,
}

fn main() {
    let mut classes =
        Arena { slots: Vec::new() };
    let mut insts =
        Arena { slots: Vec::new() };
    let k = classes.insert(Class {
        name: "Ship".to_string(),
    });
    let a = insts.insert(Instance {
        class: k,
        hp: 10.0,
    });
    let b = insts.insert(Instance {
        class: k,
        hp: 4.0,
    });
    // a.heal(b), then a.heal(a): copy
    // the number out, then write.
    for other in [b, a] {
        let hp = insts[other].hp;
        insts[a].hp += hp / 2.0;
    }
    let c = insts[a].class;
    println!("{} instance, hp {}",
        classes[c].name, insts[a].hp);
    println!("handle size: {} bytes",
        size_of::<Gc<Class>>());
    // Uncomment for E0308:
    // let oops = &insts[k];
}

One wrinkle: drip-rs writes impl<T> Copy for Gc<T> {} by hand. A #[derive(Clone, Copy)] would add the bounds T: Clone and T: Copy, and an ObjClass is neither. The handle should be copyable whatever it points at.

Borrowing one heap

There is still a borrow checker. insts[i] borrows the whole arena, so this is rejected even though the elements differ:

let src = &insts[1];
let dst = &mut insts[0];
dst.hp += src.hp / 2.0;

error[E0502]: cannot borrow `insts` as
  mutable because it is also borrowed
  as immutable

But look at the difference from chapter 137. This is a compile error, and the fix is always the same: copy what you need out first. Handles and drip-rs’s Values are Copy, so copying is cheap. In the program above, a.heal(a) simply works. drip-rs’s GetProperty does it the same way, reading let class = self.heap[instance].class; (a copy of a handle, so the borrow ends at the semicolon) before calling a method that needs &mut self.

The collector uses the idea at a larger scale. Its mark bits don’t live inside the objects; they live in a separate Marks bitmap, one Vec<bool> per arena, so tracing can read the heap through a shared & borrow while marking writes the bits through a &mut to the bitmap.

Side by side with the TypeScript VM

               TypeScript VM  drip-rs
a reference    JS reference   Gc<T>, a u32
mark bit       isMarked field Marks bitmap
find them all  next list      walk arenas
free           unlink, poison slot = None
stale use      throws (debug) panics (debug)

The TypeScript objects carry a header (isMarked, and next for the list of every object, from chapter 50), and sweep follows that list. drip-rs needs no list: an arena already holds every object of its kind, so sweep walks each arena’s slots and frees the live, unmarked ones.

Your turn

// A typed index into an Arena.
#[derive(Clone, Copy, PartialEq, Debug)]
struct Id(u32);

struct Arena<T> {
    slots: Vec<Option<T>>,
    free: Vec<u32>,
}

impl<T> Arena<T> {
    fn new() -> Self {
        Arena {
            slots: Vec::new(),
            free: Vec::new(),
        }
    }

    fn insert(&mut self, t: T) -> Id {
        todo!()
    }

    fn remove(&mut self, id: Id)
        -> Option<T> {
        todo!()
    }

    // None if the slot has been freed.
    fn get(&self, id: Id)
        -> Option<&T> {
        let i = id.0 as usize;
        self.slots[i].as_ref()
    }
}

#[derive(Clone, Copy, PartialEq, Debug)]
struct Id(u32);

// A linked list whose nodes live in
// one Vec: nodes[id.0] is node id.
struct Node {
    val: i32,
    next: Option<Id>,
}

fn push_front(nodes: &mut Vec<Node>,
    head: Option<Id>, val: i32) -> Id {
    todo!()
}

fn sum(nodes: &[Node],
    head: Option<Id>) -> i32 {
    todo!()
}

What you learned

• An arena is a Vec of slots that owns every object of one kind. Objects refer to each other by index, so cycles are just numbers.
• A free list lets new objects reuse freed slots; a stale index then reads the wrong object, which is why test modes turn reuse off.
• A typed index like ValueId(u32) or Gc<T> stops indices for different arenas being mixed up, at no run-time cost.
• In an arena the borrow checker still applies, at compile time: copy handles and values out, then write.
• drip-rs keeps mark bits in a separate bitmap and sweeps by walking its arenas, where the TypeScript VM uses object headers and a linked list.