157. Functions and call frames in Rust

A frame you can’t hold

Chapter 56 gave the TypeScript VM call frames. Each one is a small object, and the loop keeps the running one in a local variable:

interface CallFrame {
  closure: ObjClosure;
  ip: number; slots: number;
}
// in run(): hold the top frame
let frame =
  this.frames[this.frames.length - 1];
case OP.CALL: // ...
  this.callValue(
    this.peek(argCount), argCount);
  reload(); // frame = the new top

frame is a reference to an object in the array, so frame.ip++ updates the frame itself. Here is the same shape on a toy Rust VM:

let frame = self.frames.last_mut()
    .unwrap();
frame.ip += 1;
self.call(0);
frame.ip += 1;

rustc 1.97 (trimmed):

error[E0499]: cannot borrow `*self` as
  mutable more than once at a time
13 | let frame = self.frames.last_mut()...
   |             ----------- first mutable
   |                borrow occurs here
15 | self.call(0);
   | ^^^^ second mutable borrow occurs here
16 | frame.ip += 1;
   | ------------- first borrow later used

call pushes onto self.frames, the very Vec that frame points into. A push can reallocate the Vec and move every frame in it ^[2], so the borrow checker is right to refuse. Chapter 150 showed drip-rs’s answer: the running frame’s ip, chunk and stack base live in fields of the Vm, the registers. This chapter is about the frames behind them.

The frames are a Vec

Adapted from src/vm.rs:

struct CallFrame {
    closure: Gc<ObjClosure>,
    chunk: Rc<Chunk>,
    ip: usize,
    slots: usize,
}

Three differences from TypeScript. The closure is a handle, not a reference. The frame carries its function’s chunk, an Rc clone: this is where the README’s one Rc gets used. When fib has called itself 20 deep, 20 frames hold clones of one chunk, and each clone only bumps a count ^[3]. And ip in a frame is meaningful only while the frame is paused. Vm::new reserves room with Vec::with_capacity(FRAMES_MAX), so the frame Vec never reallocates. self.stack.len() plays the part of TypeScript’s sp.

use std::rc::Rc;

struct Chunk {
    code: Vec<u8>,
}

struct Frame {
    chunk: Rc<Chunk>,
    ip: usize,
}

fn main() {
    // The function owns its chunk.
    let fib = Rc::new(Chunk {
        code: vec![7, 8, 9],
    });
    let mut frames: Vec<Frame> =
        Vec::with_capacity(64);
    // fib calls itself, three deep.
    for depth in 0..3 {
        frames.push(Frame {
            chunk: Rc::clone(&fib),
            ip: depth * 4,
        });
        println!(
            "{} frames, count {}",
            frames.len(),
            Rc::strong_count(&fib)
        );
    }
    // The register: one more owner.
    let top = &frames[2].chunk;
    let reg = Rc::clone(top);
    println!("byte {}", reg.code[1]);
    println!(
        "count {}",
        Rc::strong_count(&fib)
    );
    // Return: the frame moves out...
    let done = frames.pop().unwrap();
    println!("its ip was {}", done.ip);
    drop(done);
    // ...and its clone goes with it.
    println!(
        "count {}",
        Rc::strong_count(&fib)
    );
}

Call: save, push, load

Adapted from call, after its two checks: a wrong argument count, and frames.len() == FRAMES_MAX (64), which is "Stack overflow.".

fn call(&mut self, closure: Gc<ObjClosure>,
        argc: usize) -> Run {
    // ...checks. Save the caller's ip:
    let caller = self.frames.last_mut();
    if let Some(caller) = caller {
        caller.ip = self.ip;
    }
    // Push the callee, then load it.
    let func = self.heap[closure].function;
    let chunk = Rc::clone(
        &self.heap[func].chunk);
    let slots = self.stack.len() - argc - 1;
    self.frames.push(CallFrame {
        closure, ip: 0, slots,
        chunk: Rc::clone(&chunk) });
    self.ip = 0;
    self.chunk = chunk;
    self.slots = slots;
    Ok(())
}

caller borrows self.frames while self.ip is read. They are different fields, so that’s allowed. slots points at the callee itself: slot 0 of every frame holds the closure being called, and the arguments follow it. Because call loads the registers itself, the Call arm is one line, self.call_value(self.peek(argc), argc)?, with no reload.

Step through one call and one return:

Return: pop, restore, truncate

The Return arm, adapted:

OpCode::Return => {
    let result = self.pop();
    self.close_upvalues(self.slots);
    let Some(frame) = self.pop_frame()
    else {
        self.pop(); // the script's closure
        return Ok(());
    };
    self.stack.truncate(frame.slots);
    self.push(result);
}

pop_frame takes the top frame out of the Vec by value, copies the caller’s ip, chunk and slots into the registers, and returns Some(frame). With no caller it returns None, and that is how run knows the script has finished, where TypeScript checks frames.length === 0. truncate(frame.slots) drops the callee and its arguments and locals in one step. When frame goes out of scope, its Rc<Chunk> clone is dropped with it. close_upvalues is chapter 158.

Natives and stack traces

call_value matches on the callee’s Value. A closure goes to call. Classes and bound methods come in chapters 160 and 161. A native is called right there:

Value::Native(native) => {
    let ObjNative { arity, function } =
        self.heap[native]; // ...check arity
    let start = self.stack.len() - argc;
    let result =
        function(&self.stack[start..]);
    self.stack.truncate(start - 1);
    self.push(result);
    Ok(())
}

function is a NativeFn, a plain function pointer, fn(&[Value]) -> Value ^[4]. It gets the arguments as a slice of the stack, borrowed, where TypeScript’s this.stack.slice(...) copies them into a new array.

The stack trace is where the stale ip matters. runtime_error walks the frames innermost first, and for the top frame it must read the register:

let top = self.frames.len()
    .saturating_sub(1);
for (depth, frame) in
    self.frames.iter().enumerate().rev()
{
    let ip = if depth == top { self.ip }
             else { frame.ip };
    let line = frame.chunk.lines[ip - 1];
    // "[line {line}] in f()" or "script"
}

On fn f() { return -nil; } fn g() { f(); } g();, spread over five lines, drip-rs prints Operand must be a number., then [line 2] in f(), [line 4] in g(), [line 5] in script, as the TypeScript VM does.

Your turn

#[derive(Debug, PartialEq)]
struct Frame {
    func: usize,
    ip: usize,
    slots: usize,
}

struct Func {
    arity: usize,
}

const FRAMES_MAX: usize = 64;

struct Vm {
    funcs: Vec<Func>,
    stack: Vec<f64>,
    frames: Vec<Frame>,
    // The registers:
    ip: usize,
    slots: usize,
}

impl Vm {
    fn new(funcs: Vec<Func>) -> Vm {
        Vm {
            funcs,
            stack: Vec::new(),
            frames: Vec::new(),
            ip: 0,
            slots: 0,
        }
    }

    fn push(&mut self, v: f64) {
        self.stack.push(v);
    }

    fn pop(&mut self) -> f64 {
        self.stack.pop().unwrap()
    }

    // Call funcs[func]. The callee and
    // its argc arguments are on top of
    // the stack.
    fn call(
        &mut self,
        func: usize,
        argc: usize,
    ) -> Result<(), String> {
        todo!()
    }

    // Return from the running frame.
    // false: there was no caller.
    fn ret(&mut self) -> bool {
        todo!()
    }
}

use std::rc::Rc;

struct Frame {
    // "" for the top-level script
    name: &'static str,
    // the chunk's line table
    lines: Rc<Vec<u32>>,
    ip: usize,
}

struct Vm {
    frames: Vec<Frame>,
    // The running frame's ip.
    ip: usize,
}

impl Vm {
    // The message, then one line per
    // frame, innermost first:
    // "[line 2] in f()" or
    // "[line 5] in script".
    fn trace(&self, msg: &str)
        -> Vec<String> {
        todo!()
    }
}

What you learned

• drip-rs keeps a Vec of call frames. Each CallFrame has a closure handle, an Rc<Chunk> clone, a saved ip and slots.
• The loop can’t hold &mut CallFrame across a call, so the running frame’s state lives in registers. call saves the caller’s ip, pushes the callee and loads it; pop_frame loads the caller back.
• A running frame’s own ip field is stale. The stack trace reads the register for the top frame.
• pop_frame returns Option<CallFrame>: None means the script ended. truncate(frame.slots) drops the callee’s slots.
• Natives get their arguments as a borrowed slice of the stack.