153. Heap objects in an arena

Three hops

When the TypeScript VM prints a closure, it follows three object references (chapter 50):

case 'closure': return formatValue(v.fn);
// ...which prints `<fn ${v.name.chars}>`

v.fn is a pointer to the function, .name a pointer to a string, .chars the text. drip-rs has no pointers between objects. Chapter 138 showed why: every object lives in an arena, and a reference is a Gc<T>, a typed slot number. So each hop becomes a trip to the heap. Adapted from src/value.rs:

Value::Closure(c) => {
    let func = heap[c].function;
    match heap[func].name {
        Some(name) => write!(f, "<fn {}>",
            heap.str(name)),
        None => f.write_str("<script>"),
    }
}

This chapter is about the Heap behind those square brackets.

One arena per kind

Here is the heap, adapted from src/gc.rs:

pub struct Heap {
    pub strings: Arena<ObjString>,
    pub functions: Arena<ObjFunction>,
    pub natives: Arena<ObjNative>,
    pub upvalues: Arena<ObjUpvalue>,
    pub closures: Arena<ObjClosure>,
    pub classes: Arena<ObjClass>,
    pub instances: Arena<ObjInstance>,
    pub bound_methods:
        Arena<ObjBoundMethod>,
    interned: Table,
    // ...GC bookkeeping
}

The TypeScript heap keeps one linked list of every object, threaded through a next field in each object’s header, and each object says what it is in a type field. drip-rs’s objects have neither. The arena an object sits in says what it is, and sweeping walks the arenas, so no list is needed. Mark bits live outside the objects too (chapter 159). What is left is just the fields. Compare a closure:

interface ObjClosure extends ObjHeader {
  type: 'closure'; fn: ObjFunction;
  upvalues: (ObjUpvalue | null)[];
}

pub struct ObjClosure {
    pub function: Gc<ObjFunction>,
    pub upvalues: Vec<Gc<ObjUpvalue>>,
}

There is no null in the Rust upvalue list. The TypeScript VM allocates the closure first and fills its upvalues in afterwards. drip-rs captures them into a Vec first and only then allocates the closure, so the list is never half-filled (chapter 158).

One alloc for eight kinds

The TypeScript heap has eight constructors, newClass, newClosure and so on, and a table of sizes keyed by type. drip-rs has one generic alloc. It works because every object type implements a trait that says which arena is its own:

pub trait HeapObject: Sized {
    fn arena(heap: &Heap) -> &Arena<Self>;
    fn arena_mut(heap: &mut Heap)
        -> &mut Arena<Self>;
    fn size(&self) -> usize {
        size_of::<Self>()
    }
    // ...and which mark bits are its own
}

impl HeapObject for ObjClass {
    fn arena(heap: &Heap) -> &Arena<Self> {
        &heap.classes
    }
    // ...
}

pub fn alloc<T: HeapObject>(
    &mut self, object: T) -> Gc<T> {
    self.bytes_allocated += object.size();
    T::arena_mut(self).insert(object)
}

ObjString overrides size to add the length of its text, which is how the collector knows a long string costs more. Six of the eight impls are identical apart from names, so gc.rs stamps them out with a small macro_rules! macro: a template that writes the same code for each type it is given.

Then indexing. The standard Index trait is what heap[handle] calls: container[index] is shorthand for *container.index(index) ^[2]. drip-rs implements it once, for every handle type:

impl<T: HeapObject> Index<Gc<T>> for Heap {
    type Output = T;
    fn index(&self, h: Gc<T>) -> &T {
        &T::arena(self)[h]
    }
}

IndexMut is the same with &mut, and it is what makes self.heap[function].arity += 1 in the compiler work. Step through printing a closure:

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

// A handle: a typed slot number.
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 Str {
    chars: String,
}
struct Class {
    name: Gc<Str>,
}

// One arena per kind of object.
#[derive(Default)]
struct Heap {
    strings: Vec<Str>,
    classes: Vec<Class>,
}

trait HeapObject: Sized {
    fn arena(h: &Heap) -> &Vec<Self>;
    fn arena_mut(h: &mut Heap)
        -> &mut Vec<Self>;
}
impl HeapObject for Str {
    fn arena(h: &Heap) -> &Vec<Self> {
        &h.strings
    }
    fn arena_mut(h: &mut Heap)
        -> &mut Vec<Self> {
        &mut h.strings
    }
}
impl HeapObject for Class {
    fn arena(h: &Heap) -> &Vec<Self> {
        &h.classes
    }
    fn arena_mut(h: &mut Heap)
        -> &mut Vec<Self> {
        &mut h.classes
    }
}

impl Heap {
    fn alloc<T: HeapObject>(
        &mut self,
        object: T,
    ) -> Gc<T> {
        let arena = T::arena_mut(self);
        arena.push(object);
        let i = arena.len() - 1;
        Gc {
            index: i as u32,
            marker: PhantomData,
        }
    }
}

impl<T: HeapObject> Index<Gc<T>>
    for Heap
{
    type Output = T;
    fn index(&self, h: Gc<T>) -> &T {
        let i = h.index as usize;
        &T::arena(self)[i]
    }
}
impl<T: HeapObject> IndexMut<Gc<T>>
    for Heap
{
    fn index_mut(&mut self, h: Gc<T>)
        -> &mut T {
        let i = h.index as usize;
        &mut T::arena_mut(self)[i]
    }
}

fn main() {
    let mut heap = Heap::default();
    let chars = String::from("Point");
    let s = Str { chars };
    let name = heap.alloc(s);
    let c = Class { name };
    let class = heap.alloc(c);

    // TypeScript: klass.name.chars
    let n = heap[class].name;
    println!("{}", heap[n].chars);

    // IndexMut: change it in place.
    heap[n].chars.push_str("3D");
    let n = heap[class].name;
    println!("{}", heap[n].chars);
    // Uncomment for E0502:
    // heap[heap[class].name]
    //     .chars.push('!');
}

Read one, write another

All eight arenas live in one Heap, and heap[h] borrows the whole Heap. So reading one object while writing another doesn’t compile, even when they are different objects. Here is a first try at Inherit, which copies the superclass’s methods into the subclass:

let from = &self.heap[superclass].methods;
self.heap[subclass].methods.add_all(from);

rustc 1.97 (trimmed):

error[E0502]: cannot borrow `self.heap`
  as mutable because it is also
  borrowed as immutable
19 | let from = &self.heap[superclass]...
   |             --------- immutable
   |                borrow occurs here
20 | self.heap[subclass].methods.add_...
   | ^^^^^^^^^ mutable borrow occurs here

The fix is chapter 138’s rule, copy out then write. A handle is copied for free; a whole method table is cloned:

let methods = self.heap[superclass]
    .methods.clone();
self.heap[subclass].methods
    .add_all(&methods);

Nesting has the same trap. heap[heap[class].name] is fine for reading, but writing through it fails, and rustc’s help suggests a local. Uncomment the last line of the program above to see it.

Your turn

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

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 Str {
    chars: String,
}
struct Class {
    name: Gc<Str>,
    arity: u32,
}

#[derive(Default)]
struct Heap {
    strings: Vec<Str>,
    classes: Vec<Class>,
}

trait HeapObject: Sized {
    fn arena(h: &Heap) -> &Vec<Self>;
    fn arena_mut(h: &mut Heap)
        -> &mut Vec<Self>;
}

impl HeapObject for Str {
    fn arena(h: &Heap) -> &Vec<Self> {
        &h.strings
    }
    fn arena_mut(h: &mut Heap)
        -> &mut Vec<Self> {
        &mut h.strings
    }
}

impl HeapObject for Class {
    fn arena(h: &Heap) -> &Vec<Self> {
        todo!()
    }
    fn arena_mut(h: &mut Heap)
        -> &mut Vec<Self> {
        todo!()
    }
}

impl Heap {
    // Store an object in its arena.
    fn alloc<T: HeapObject>(
        &mut self,
        object: T,
    ) -> Gc<T> {
        todo!()
    }
}

impl<T: HeapObject> Index<Gc<T>>
    for Heap
{
    type Output = T;
    fn index(&self, h: Gc<T>) -> &T {
        todo!()
    }
}

impl<T: HeapObject> IndexMut<Gc<T>>
    for Heap
{
    fn index_mut(&mut self, h: Gc<T>)
        -> &mut T {
        todo!()
    }
}

use std::ops::{Index, IndexMut};

#[derive(Clone, Copy)]
struct Gc(usize);

struct Class {
    methods: Vec<String>,
}

struct Heap {
    classes: Vec<Class>,
}

impl Index<Gc> for Heap {
    type Output = Class;
    fn index(&self, h: Gc) -> &Class {
        &self.classes[h.0]
    }
}

impl IndexMut<Gc> for Heap {
    fn index_mut(&mut self, h: Gc)
        -> &mut Class {
        &mut self.classes[h.0]
    }
}

// Add sup's methods to sub's.
fn inherit(
    heap: &mut Heap,
    sub: Gc,
    sup: Gc,
) {
    todo!()
}

What you learned

• drip-rs’s Heap holds one arena per object type. Objects have no header: no type, no next, no mark bit.
• An object handle Gc<T> stands for an object. heap[handle] reads it and heap[handle].field = ... writes it.
• The HeapObject trait tells generic code which arena belongs to each type, so one alloc and one Index impl serve all eight.
• A TypeScript chain like v.fn.name becomes a chain of lookups, with each handle copied out on the way.
• heap[h] borrows the whole heap: to read one object and write another, copy or clone what you need first.