Lab 11: The Virtual Machine (Milestone 8)

Background

You will write src/vm.rs: the value stack, the frame stack, the dispatch loop, calls and returns, runtime errors with tracebacks, the instruction budget, and ember trace.

At the end of this lab, ember run executes bytecode by default and ember run --interp still works. Lab 12 then proves they agree.

Why This Lab Matters

  • The frame stack is where "a stack overflow is a Result" comes from. In the tree walker the script's recursion consumed the Rust stack; here it consumes a Vec, and the limit becomes a policy number rather than a proxy for a hardware constraint.
  • The budget check moves to the fetch position, and coverage becomes complete by construction rather than by audit.
  • ember trace is the instrument you will use for the rest of the curriculum. Every closure bug, table bug, and GC bug in Section 4 gets debugged by reading a trace.

Prerequisites

Predict First

  1. Where does the callee sit relative to its arguments when CALL executes? Why does that make calls allocation-free?
  2. fib(25) under the VM — what fraction of the tree walker's time? (You wrote a prediction in Lab 7. Look it up now, do not re-derive it.)
  3. while true do end with a budget of 1,000 — at which instruction does it stop?
  4. If you forget to sync ip before building an error, what is the symptom?
  5. A function's body falls off the end without return. What does the caller receive, and which instruction makes that happen?
  6. local function f() return f() end f() — which limit fires, and what is on the frame stack when it does?

Step 1: The VM State

#![allow(unused)]
fn main() {
pub struct Vm {
    stack:   Vec<Value>,        // operands AND locals — the same array
    frames:  Vec<CallFrame>,
    globals: GcRef<Table>,
    heap:    Heap,
    budget:  Budget,
    stats:   Stats,
    trace:   Option<Box<dyn Write>>,   // stderr, never stdout
}

pub struct CallFrame {
    closure: GcRef<Closure>,    // Lab 14; until then, Rc<Proto>
    base:    usize,             // stack index of this frame's slot 0
    ip:      usize,             // index into closure.proto.chunk.code
    ret_to:  usize,             // where results go: the callee's own stack slot
    want:    u8,                // how many results the CALLER wants (255 = all)
    call_span: Span,            // for the traceback
}
}

base is the whole idea. GET_LOCAL s is stack[base + s]. A frame owns stack[base .. base + proto.max_stack], and everything above that is its operand area. Calls do not copy arguments anywhere: they are the callee's first slots.

Checkpoint question. Why does CallFrame store want rather than the caller reading it from the CALL instruction when the callee returns?

Step 2: The Loop (Simple Version First)

Write the loop with state on self — option A. Get it correct, pass Lab 12, and only then hoist.

#![allow(unused)]
fn main() {
pub fn run(&mut self) -> Result<Vec<Value>> {
    loop {
        self.budget.tick().map_err(|e| self.attach_traceback(e))?;
        let ip = self.frame().ip;
        let op = self.chunk().code()[ip];
        self.frame_mut().ip = ip + 1;
        self.stats.instructions += 1;
        if self.trace.is_some() { self.trace_instruction(ip, op); }

        match op {
            Op::LoadInt(n)   => self.push(Value::Integer(n as i64)),
            Op::LoadConst(k) => { let v = self.chunk().constants[k as usize]; self.push(v) }
            Op::LoadNil      => self.push(Value::Nil),
            Op::LoadTrue     => self.push(Value::Boolean(true)),
            Op::LoadFalse    => self.push(Value::Boolean(false)),

            Op::GetLocal(s)  => { let b = self.frame().base; let v = self.stack[b + s as usize];
                                  self.push(v) }
            Op::SetLocal(s)  => { let b = self.frame().base; let v = self.pop();
                                  self.stack[b + s as usize] = v }
            Op::Pop(n)       => { let len = self.stack.len(); self.stack.truncate(len - n as usize) }

            Op::Add => self.binary(ip, arith::add)?,
            Op::Lt  => self.compare(ip, cmp::lt)?,
            // ... one arm per opcode, each a few lines

            Op::Jump(t)        => self.frame_mut().ip = t as usize,
            Op::JumpIfFalse(t) => { if !self.pop().is_truthy() { self.frame_mut().ip = t as usize } }
            Op::JumpIfFalseKeep(t) =>
                { if !self.peek(0).is_truthy() { self.frame_mut().ip = t as usize } }
            Op::JumpIfTrueKeep(t)  =>
                { if  self.peek(0).is_truthy() { self.frame_mut().ip = t as usize } }

            Op::Call(argc, want) => self.do_call(argc, want, ip)?,
            Op::Return(n)        => if let Some(results) = self.do_return(n)? { return Ok(results) },
            _ => return Err(self.rt(ip, "opcode not implemented yet")),
        }
    }
}

/// The shape every fallible binary opcode uses. The `ip` is threaded through so
/// the error carries the SPAN of the instruction that failed.
fn binary(&mut self, ip: usize, f: fn(Value, Value) -> ArithResult) -> Result<()> {
    let b = self.pop();
    let a = self.pop();
    // arith::add is THE SAME FUNCTION the tree walker calls. Shared code means
    // differential testing cannot check it — see Lab 12's blind-spot section.
    let v = f(a, b).map_err(|e| self.rt_arith(ip, e, a, b))?;
    self.push(v);
    Ok(())
}
}

Note: self.stack.truncate(len - n) will panic if n > len. It cannot, because verify_stack_depth proved the chunk balances — but that is a claim about a pass you must actually run. Either call validate() before every run(), or use saturating_sub and return an internal error. Pick one, write down which, and make it a test. "It can't happen" without an enforcement mechanism is how a panic reaches a host.

Step 3: Calls and Returns

#![allow(unused)]
fn main() {
fn do_call(&mut self, argc: u8, want: u8, ip: usize) -> Result<()> {
    // The callee sits BELOW its arguments. No copying, no allocation.
    let callee_at = self.stack.len() - argc as usize - 1;
    let callee = self.stack[callee_at];

    let closure = match callee {
        Value::Closure(c) => c,
        Value::Native(n)  => return self.call_native(n, callee_at, argc, want, ip),
        other => return Err(self.rt(ip,
            format!("attempt to call a {} value", other.type_name()))),
    };

    if self.frames.len() >= self.limits.max_depth {
        return Err(self.limit(ip, format!(
            "stack overflow (call depth limit {} exceeded)", self.limits.max_depth)));
    }

    let proto = self.heap.closure(closure)?.proto.clone();
    // Lua 5.4 §3.4.11: missing arguments are nil, extras are kept for VARARG.
    let base = callee_at + 1;
    for _ in argc..proto.nparams { self.stack.push(Value::Nil); }
    // Reserve the frame's slot region so GET_LOCAL never reads past the top.
    self.stack.resize(base + proto.max_stack as usize, Value::Nil);

    self.frames.push(CallFrame { closure, base, ip: 0, ret_to: callee_at,
                                 want, call_span: self.chunk().span_at(ip) });
    Ok(())
}

fn do_return(&mut self, n: u8) -> Result<Option<Vec<Value>>> {
    let frame = self.frames.pop().expect("run() is only entered with a frame");
    let results_at = self.stack.len() - n as usize;
    let results: Vec<Value> = self.stack[results_at..].to_vec();

    // Lab 14 inserts: self.close_upvalues(frame.base);   ← BEFORE the truncate

    self.stack.truncate(frame.ret_to);                    // drop the frame's whole region
    if self.frames.is_empty() { return Ok(Some(results)); }

    // Adjust to what the CALLER asked for: pad with nil, or discard extras.
    match frame.want {
        255 => self.stack.extend_from_slice(&results),
        w   => { for i in 0..w as usize {
                     self.stack.push(results.get(i).copied().unwrap_or(Value::Nil)) } }
    }
    Ok(None)
}
}

Three things to get right:

  1. stack.resize(base + max_stack) before running the callee. Without it, GET_LOCAL 3 on a frame whose arguments only filled slots 0–1 reads whatever the previous frame left there. The validator proved slots are < max_stack; the VM must make that region exist.
  2. ret_to is the callee slot, not base. Results overwrite the function value itself, which is what makes the stack come back to exactly where it was before the call.
  3. The result adjustment is the one place multiple-return semantics live. Lab 17 extends it; putting it in one function now means Lab 17 edits one function.

Step 4: Errors and Tracebacks

#![allow(unused)]
fn main() {
fn rt(&self, ip: usize, msg: impl Into<String>) -> EmberError {
    EmberError {
        kind: ErrorKind::Runtime,
        message: msg.into(),
        span: Some(self.chunk().span_at(ip)),      // ← the LINE TABLE, earning its keep
        traceback: self.traceback(),               // ← captured HERE, at creation
    }
}

fn traceback(&self) -> Vec<Frame> {
    let mut out: Vec<Frame> = self.frames.iter().rev().map(|f| Frame {
        name: self.proto_of(f).name.clone().unwrap_or_else(|| "?".into()),
        // The frame's CURRENT ip, resolved through ITS chunk's line table.
        span: self.proto_of(f).chunk.span_at(f.ip.saturating_sub(1)),
    }).collect();
    out.push(Frame { name: "main chunk".into(), span: Span::EMPTY });
    truncate_traceback(out)          // first 10, "...", last 11 — as Lua does
    }
}

The span comes from chunk.lines[ip]. That is the payoff for the invariant enforced in Lab 9: one span per instruction, no exceptions. If the line table had drifted by one, every runtime error in Ember would point at the neighbouring instruction's source, and nothing would tell you.

Step 5: The Budget, in the Fetch Position

Already in Step 2, one line, before the fetch. Confirm the coverage argument holds:

ember run --max-instructions 1000 -e 'while true do end'                    # Limit
ember run --max-instructions 1000 -e 'local function f() return f() end f()' # Limit (depth first)
ember run --max-instructions 0    -e 'return 1'                             # Limit, immediately

That third case is the off-by-one test: a budget of zero must permit zero instructions, not infinitely many.

Step 6: ember trace

#![allow(unused)]
fn main() {
fn trace_instruction(&mut self, ip: usize, op: Op) {
    let out = self.trace.as_mut().unwrap();      // STDERR — stdout is what golden tests compare
    let depth = self.frames.len();
    let window: Vec<String> = self.stack.iter().rev().take(4).rev()
        .map(|v| short_value(*v)).collect();
    let _ = writeln!(out, "{:>3} {:04}  {:<24} [{}]",
                     depth, ip, render_op(op, self.chunk()), window.join(", "));
}
}

Rules, from the teaching method: stderr not stdout, switchable at run time, cheap when off (if self.trace.is_some() around the formatting, not a formatted string thrown away), and replayable.

Step 7: Hoist, and Re-run the Tests

Only after Lab 12 passes. Move ip, base, and the chunk into locals per the dispatch chapter, add the sync!() discipline, and re-run the differential suite. If it still passes, benchmark. If the numbers did not move, revert — and record that you reverted, which is a result.

The Trace

$ ember trace -e 'local x = 10 + 20 * 3 return x'

dep  ip    op                       stack after
  1  0000  LOAD_INT     10          [10]
  1  0001  LOAD_INT     20          [10, 20]
  1  0002  LOAD_INT     3           [10, 20, 3]
  1  0003  MUL                      [10, 60]
  1  0004  ADD                      [70]
  1  0005  GET_LOCAL    0    ; x    [70, 70]
  1  0006  RETURN       1
70

Put that next to Lab 3's evaluation-order diagram. The post-order numbering of the tree — ①10 ②20 ③3 ④Mul ⑤Add — is exactly the instruction order. The tree walker's recursion and the VM's linear code are the same traversal, one implicit in the Rust call stack and one explicit in the instruction stream. That equivalence is the single clearest thing you will see in Section 3.

Now a call, and watch the frame stack:

$ ember trace -e 'local function add(a,b) return a+b end return add(10, 20)'

dep  ip    op                       stack after
  1  0000  CLOSURE      0           [<fn add>]
  1  0001  GET_LOCAL    0    ; add  [<fn add>, <fn add>]
  1  0002  LOAD_INT     10          [<fn add>, <fn add>, 10]
  1  0003  LOAD_INT     20          [<fn add>, <fn add>, 10, 20]
  1  0004  CALL         2 1         → push frame: base=2, ret_to=1
  2  0000  GET_LOCAL    0    ; a    [<fn add>, <fn add>, 10, 20, 10]
  2  0001  GET_LOCAL    1    ; b    [<fn add>, <fn add>, 10, 20, 10, 20]
  2  0002  ADD                      [<fn add>, <fn add>, 10, 20, 30]
  2  0003  RETURN       1           → pop frame, truncate to 1, push 30
  1  0005  RETURN       1           [<fn add>, 30]
30

Read the CALL line carefully. The arguments 10 and 20 were pushed by the caller, and the callee's GET_LOCAL 0 reads 10 — the same stack cell, no copy. base = 2 is the index of the first argument. ret_to = 1 is where the function value sits, and that is where the result lands. Trace that once by hand on paper; it is the mechanism the whole calling convention rests on.

And the limit:

$ ember run -e 'local function f() return f() end return f()'
<argv>:1:34: error: stack overflow (call depth limit 200 exceeded)

   1 │ local function f() return f() end return f()
     │                                   ^^^

stack traceback:
  in function 'f'   <argv>:1
  ... (189 more)
  in function 'f'   <argv>:1
  in main chunk     <argv>:1
$ echo $?
1

Same message as the tree walker's. That is not a coincidence — it is the property Lab 12 is about to make automatic.

Expected Output

$ ember run tests/golden/programs/fizzbuzz.ember | head -5
1
2
Fizz
4
Buzz

$ ember run --stats -e 'local n=0 for i=1,100000 do n=n+i end return n'
5000050000
--- stats ---
instructions executed: <your number>
max stack depth:       <n>
max call depth:        1

Debugging Steps

The VM executes the caller's next instruction inside the callee

You hoisted ip and did not re-hoist after CALL. (Or, without hoisting: do_call incremented the wrong frame's ip.)

Runtime errors point at the wrong line

ip was incremented before the span was read, or sync!() is missing. The span must come from the instruction that failed, i.e. ip before the increment.

GET_LOCAL reads a stale value from a previous call

stack.resize(base + max_stack) is missing in do_call.

The stack grows across a loop until memory runs out

A POP is missing in the compiler, or an opcode's implementation does not match its documented stack effect. Run validate() on the chunk — it will name the instruction.

RETURN from the main chunk panics

self.frames.pop() on an empty frame stack, because run() was entered without pushing the main frame.

The traceback is empty

Built where the error is caught rather than where it is created. Same bug as Lab 7, second backend.

--trace breaks the golden tests

Trace output is going to stdout. It goes to stderr.

Experiment

CLAIM. Most of the VM's speedup over the tree walker comes from name resolution and call overhead, not from "being compiled".

METHOD. Run all four benchmarks from Lab 8 under both backends. For each, compute the ratio. Then use --stats to get the executed-instruction count for the VM, and reason about where the tree walker's extra time went.

BenchmarkIsolatesInterpVMRatio
locals_deepname resolution
fib_25calls
loop_10mdispatch + arithmetic
globalsthe global path (a hash lookup in both)

PREDICTION. Which row has the largest ratio? Which has the smallest, and why? (The last row is the control: both backends do a hash lookup, so it should improve least.)

RESULT. Fill in the table, put it in docs/learning/06-vm.md next to your Lab 7 predictions, and write one sentence on which prediction was most wrong and why.

Test

#![allow(unused)]
fn main() {
#[test]
fn vm_runs_the_whole_golden_corpus() {
    let mut b = VmBackend::new();
    let failures: Vec<_> = corpus().iter().filter_map(|c| check(&mut b, c)).collect();
    assert!(failures.is_empty(), "{} failures:\n{}", failures.len(), failures.join("\n\n"));
}

#[test]
fn calls_do_not_copy_arguments() {
    // A white-box check on the calling convention: after CALL, the callee's
    // slot 0 must be the SAME stack cell the caller pushed.
    let vm = run_to_first_call("local function f(a) return a end return f(42)");
    assert_eq!(vm.stack[vm.frames.last().unwrap().base], Value::Integer(42));
    assert_eq!(vm.frames.last().unwrap().base, vm.frames.last().unwrap().ret_to + 1);
}

#[test]
fn budget_of_zero_permits_nothing() {
    let e = run_with_budget("return 1", 0).unwrap_err();
    assert_eq!(e.kind, ErrorKind::Limit);
}

#[test]
fn infinite_loop_and_infinite_recursion_both_terminate() {
    for src in ["while true do end",
                "local function f() return f() end return f()",
                "local a, b b = function() return a() end a = function() return b() end return a()"] {
        let e = run_with_limits(src, 1_000_000, 200).unwrap_err();
        assert_eq!(e.kind, ErrorKind::Limit, "{src} must hit a limit, not run forever");
    }
}

#[test]
fn runtime_errors_carry_the_failing_instructions_span() {
    let e = run_err("local t = nil\nreturn t + 1");
    assert_eq!(e.kind, ErrorKind::Runtime);
    let (line, _) = source_of(&e).location(e.span.unwrap().start);
    assert_eq!(line, 2, "the span must point at the failing instruction's source line");
}

#[test]
fn stack_is_balanced_after_every_golden_program() {
    // If a program leaves values on the stack, the compiler emitted an
    // unbalanced sequence — and it will corrupt the NEXT call's slots.
    for case in corpus() {
        let mut vm = Vm::new();
        let _ = vm.run_str(&case.src);
        assert!(vm.stack.len() <= vm.initial_reserved(),
                "{}: stack not unwound, {} values left", case.name, vm.stack.len());
    }
}
}

Challenge Extensions

  1. Hoist the loop state (Step 7) and measure. Report the speedup, and whether adding the sync!() discipline introduced a bug the differential tests caught. Both outcomes are results.
  2. A function-pointer dispatch table. Implement option D and benchmark against the match. It will probably lose. Report by how much, and say why.
  3. Measure branch mispredictions. Run perf stat -e branches,branch-misses on fib25 and compute misses per executed VM instruction. Does dispatch dominate your VM?
  4. Superinstruction experiment. Find the most common two-instruction sequence with --stats (probably GET_LOCAL, GET_LOCAL). Fuse it into one opcode. Measure. Then decide whether to keep it, and record the decision either way. This is Section 7's method, rehearsed.
  5. ember trace --frames showing every frame push and pop with base, ret_to, and want. You will want this in Lab 17.

Deliverables

  • The VM executes the whole golden corpus; ember run uses it by default.
  • ember run --interp still works and is still tested.
  • Calls are allocation-free: arguments are the callee's slots, verified by a white-box test.
  • stack.resize(base + max_stack) on call; a test proves a fresh frame's slots are nil.
  • Runtime errors carry the failing instruction's span and a traceback captured at creation.
  • Tracebacks are truncated as Lua's are.
  • The budget is in the fetch position; while true do end, infinite recursion, mutual recursion, and --max-instructions 0 all produce ErrorKind::Limit and exit 1.
  • ember trace prints depth, ip, opcode, and a stack window — to stderr.
  • ember --stats reports instructions executed, max stack depth, max call depth.
  • The four-row benchmark table filled in and compared against Lab 7's predictions.
  • docs/learning/06-vm.md and 07-call-frames.md updated.

Validation / Self-check

  1. Draw the value stack across a call: where are the callee, the arguments, base, and ret_to?
  2. Why must do_call resize the stack, and what is the symptom of omitting it?
  3. Why is the error's span read from ip before the increment?
  4. Where does the budget check live, and give the three programs that prove its coverage.
  5. Why does trace output go to stderr?
  6. Put the VM trace of 10 + 20 * 3 next to the tree walker's post-order diagram. What is the relationship, in one sentence?
  7. Which benchmark improved least between the backends, and why is that the expected control?
  8. stack.truncate(len - n) cannot underflow. What enforces that, and what happens if the enforcement is not run?

Next: Lab 12 — Differential Testing.