145. Planning drip-rs

A working VM, and a blank file

In Part IV you built a bytecode VM for Drip in TypeScript. It lives in companion/ts/src/vm, about 1,500 lines across nine files, and it runs every program in the test corpus. Part X rebuilds it in Rust. The result already exists: drip-rs, in companion/rust. These chapters walk you through it file by file, next to the TypeScript you wrote.

Here is the goal, stated as a test. For every corpus program, drip-rs must print the same output, the same error messages with the same line numbers, and exit with the same code. Not “close”. The same bytes.

Most of the port is translation. One part is not, and it shapes everything else, so this chapter is about that part.

The map

The port keeps the TypeScript VM’s shape: one Rust module per TypeScript file, in pipeline order. Step through the pairs, and what changed in each:

The module map, from drip-rs’s README:

• scanner.rs: tokens borrow their text from the source.
• chunk.rs: the #[repr(u8)] OpCode enum and Chunk.
• value.rs and object.rs: Value, a Copy enum, and the heap object structs, arenas and handles. Together they are object.ts.
• table.rs, gc.rs: the hash table, and the heap with its collector.
• compiler.rs, vm.rs, debug.rs: the same jobs as their twins.

lib.rs declares the modules with pub mod, and above them sits #![forbid(unsafe_code)]: no unsafe block can appear anywhere in the crate. And Cargo.toml lists no dependencies, so it is the standard library and nothing else.

Objects that point at each other

In TypeScript, a closure object holds its function, an instance holds its class, and a class holds a table of closures. Any object can point at any other, and cycles are normal. JavaScript’s own collector sorts it out.

Rust’s first offer for shared, mutable objects is chapter 137’s Rc<RefCell<T>>:

struct ObjClosure {
    function: Rc<RefCell<ObjFunction>>,
    // ...
}

That compiles, and it is wrong for a VM, for three reasons. Reference counting would decide when objects die, so chapter 58’s mark and sweep would have nothing to do. A cycle of Rcs never reaches a count of zero, so it leaks^[1]. And every borrow_mut() is a check at run time, on the hottest paths of the interpreter.

So drip-rs does what chapter 138 showed: arenas and typed handles. Each kind of object lives in its own Arena<T>, a Vec of slots. A reference to an object is a Gc<T>, a u32 index tagged with the type it points at. The heap owns every object; everyone else holds handles, which are Copy and own nothing. Here is the idea in miniature, with a class and an instance that point at each other:

struct ClassRef(u32);
struct InstRef(u32);

struct Class {
    name: String,
    newest: Option<InstRef>,
}
struct Instance {
    class: ClassRef,
}

// A class and an instance that point at
// each other: a cycle, with no Rc and
// no RefCell. Each kind has an arena.
#[derive(Clone, Copy, Debug)]
struct ClassRef(u32);
#[derive(Clone, Copy, Debug)]
struct InstRef(u32);

struct Class {
    name: String,
    // a back edge: the newest instance
    newest: Option<InstRef>,
}

struct Instance {
    class: ClassRef,
}

struct Heap {
    classes: Vec<Class>,
    insts: Vec<Instance>,
}

impl Heap {
    fn class(&self, r: ClassRef)
        -> &Class {
        &self.classes[r.0 as usize]
    }
    fn inst(&self, r: InstRef)
        -> &Instance {
        &self.insts[r.0 as usize]
    }
}

fn main() {
    let mut h = Heap {
        classes: Vec::new(),
        insts: Vec::new(),
    };
    h.classes.push(Class {
        name: String::from("Point"),
        newest: None,
    });
    let c = ClassRef(0);
    h.insts.push(Instance { class: c });
    let p = InstRef(0);
    // close the loop: c -> p -> c
    h.classes[0].newest = Some(p);

    let mut at = c;
    for _ in 0..3 {
        let k = h.class(at);
        let i = k.newest.unwrap();
        println!("{} {:?}", k.name, i);
        at = h.inst(i).class;
    }
    // h.inst(c) would not compile:
    // a ClassRef is not an InstRef.
    use std::mem::size_of;
    let n = size_of::<InstRef>();
    println!("handle: {} bytes", n);
}

The cycle costs nothing: there are no counts to keep and nothing to leak, because the heap owns both. Freeing is the collector’s job, as in clox^[2]. And the types still help. Pass a ClassRef where an InstRef belongs and rustc says (1.97, trimmed):

error[E0308]: mismatched types
  h.inst(c);
         ^ expected `InstRef`,
           found `ClassRef`

Roots are passed in

The TypeScript heap starts a collection by itself, inside allocate. To find the roots it calls back into the VM, which registered itself with this.heap.vm = this. Try that shape in Rust, with the heap taking the VM:

impl Vm {
    fn gc(&mut self) {
        self.heap.collect(self);
    }
}

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

The VM owns the heap. Collecting needs &mut to the heap, which is part of the VM, while the VM is lent out whole: chapter 125’s rule, one &mut or many &, never both. So drip-rs turns it around. Allocating never collects. The VM asks heap.should_collect(), and if so it borrows the fields that hold roots, one by one, and hands them over (adapted from vm.rs):

let roots = VmRoots {
    stack: &self.stack,
    frames: &self.frames,
    globals: &self.globals,
    // ...
};
self.heap.collect(&[&roots]);

Borrowing self.stack and self.heap at once is fine: they are different fields, and the borrow checker can see that. collect takes &[&dyn Trace], so the compiler can pass its half-built functions the same way (chapter 131).

The one Rc

There is exactly one Rc in drip-rs: Rc<Chunk>. When the compiler finishes a function, it freezes the chunk with Rc::new(chunk), and nothing changes it again. The VM keeps the running function’s chunk in a field of its own, a register, and reads bytes with self.chunk.code[self.ip].

Why not a plain &Chunk? That reference would point into the heap, keeping the heap borrowed while the VM pushes values and allocates. An Rc clone is the VM’s own pointer to the same chunk, so the heap stays free. And because the chunk never changes, it needs no RefCell. The README reports that keeping these registers made fib about 1.4× faster.

The same bytes

How do you know the port is right? Chapter 112’s answer: run one corpus through both and compare. drip-rs’s tests/corpus.rs runs the 246 programs the VM is meant to run, and checks each against the expectations written in the program’s comments, with a Rust port of check() from the TypeScript runner. Two real ones, the second wrapped here to fit:

print 2 + 3 * 4; // expect: 14
true.foo; // expect runtime error:
          // Only instances have properties.

cargo test also runs 95 programs with a collection before every allocation, which makes a forgotten root crash at once.

Chapter 148 adds one more check, on the bytecode itself: the two disassemblers print identical listings for every corpus program that compiles.

The road ahead

The next chapters follow the pipeline: tokens (146), the scanner (147), chunks and opcodes (148), values (149) and the dispatch loop (150), then the compiler, the heap, closures, the collector and classes. Each one shows the TypeScript, then the Rust, and explains every difference the rules forced.

Your turn

fn expect_output(line: &str)
    -> Option<&str> {
    todo!()
}

fn expected(src: &str) -> Vec<&str> {
    todo!()
}

const RT: &str =
    "// expect runtime error: ";
// Compile errors the VM expects.
const CE: [&str; 3] = [
    "// Error",
    "// [line ",
    "// [c line ",
];

/// The exit code a corpus program's
/// comments ask for.
fn expected_exit(src: &str) -> i32 {
    todo!()
}

What you learned

• drip-rs is a module-by-module port of the TypeScript VM: std only, #![forbid(unsafe_code)], tested against the same corpus.
• Heap objects live in arenas owned by the heap. References are Gc<T> handles, typed u32 indices, so cycles are free and the collector, not reference counting, frees objects.
• The heap can’t reach the VM that owns it, so roots are passed in: the VM borrows its root fields and calls collect(&[&roots]).
• Compiled chunks never change, so they are frozen in Rc<Chunk>, the crate’s only Rc.
• “Correct” means the same output, errors, line numbers and exit codes as the TypeScript VM, on every corpus program.