Lab 10: The Compiler (Milestone 7)

Background

You will write src/compiler.rs: AST in, Chunk out. Names become slot numbers, literals become constant indices, and control flow becomes jump targets.

Nothing executes this lab. You read the disassembly. That is deliberate — the compiler is one new subsystem, and debugging it against a VM that is also new is debugging two things at once.

Why This Lab Matters

• This is where Claim 3 becomes code. The scope-chain search the tree walker did on every variable read happens here, once, at compile time. Everything Section 3 claims about performance reduces to that.
• Jump patching is the highest-density bug region in the curriculum. Four control-flow shapes, each with its own way to be off by one.
• verify_stack_depth from Lab 9 is your compiler test suite. Run it on every chunk you produce, and most of your bugs are caught before you ever execute anything.

Prerequisites

• Lab 9 complete: disassembler works, validate() passes on hand-written chunks.
• Code Generation read.
• docs/architecture.md open — you are implementing it a second time.

Predict First

1. local a = 1 do local b = 2 end do local c = 3 end — which slot does c get?
2. 1 + 1 — how many constants in the pool? What about 1 + 1.0?
3. if a then b() end with no else — how many jumps?
4. while a do break end — how many jumps, and where does each go?
5. local a = false and f() — what is the stack depth at the instruction after the whole expression, on each path?
6. A break inside do local x = 1 ... break ... end — what must be emitted before the jump?
7. local function f() return f() end — is f a local, an upvalue, or a global inside the body?

Step 1: The Compiler and Its Invariants

#![allow(unused)]
fn main() {
pub struct Compiler<'p> {
    chunk: Chunk,
    locals: Vec<Local>,
    scope_depth: usize,
    breaks: Vec<Vec<usize>>,       // one pending list per enclosing loop
    stack_depth: i32,              // current, tracked at every emit
    max_stack: u16,
    parent: Option<&'p Compiler<'p>>,   // Lab 14: upvalue resolution walks this
    name: Option<String>,
}
}

Enforce the two invariants with debug assertions, not comments:

#![allow(unused)]
fn main() {
fn compile_expr(&mut self, e: &Expr) -> Result<()> {
    let before = self.stack_depth;
    self.compile_expr_inner(e)?;
    debug_assert_eq!(self.stack_depth, before + 1,
                     "compile_expr must leave exactly one value: {e:?}");
    Ok(())
}

fn compile_stmt(&mut self, s: &Stmt) -> Result<()> {
    let before = self.stack_depth;
    self.compile_stmt_inner(s)?;
    debug_assert_eq!(self.stack_depth, before,
                     "compile_stmt must be stack-neutral: {s:?}");
    Ok(())
}
}

Tip: Write these two wrappers first, before any code generation. They will fire dozens of times over the next few hours and each firing names the exact node that is wrong. Without them the same bugs appear as "the VM returns nil sometimes", four hours later, in Lab 11.

stack_depth is tracked in emit, using the same documented_effect table from Lab 9 — so the compiler and the validator agree by construction:

#![allow(unused)]
fn main() {
fn emit(&mut self, op: Op, span: Span) -> usize {
    if let Some((pops, pushes)) = documented_effect(op) {
        self.stack_depth += pushes as i32 - pops as i32;
    } // variable-effect opcodes adjust stack_depth explicitly at their call sites
    self.max_stack = self.max_stack.max(self.stack_depth.max(0) as u16);
    self.chunk.emit(op, span)
}
}

Step 2: Expressions

#![allow(unused)]
fn main() {
fn compile_expr_inner(&mut self, e: &Expr) -> Result<()> {
    match e {
        Expr::Nil { span }              => self.emit(Op::LoadNil, *span),
        Expr::Bool { value: true, span } => self.emit(Op::LoadTrue, *span),
        Expr::Bool { value: false, span }=> self.emit(Op::LoadFalse, *span),

        Expr::Int { value, span } => {
            // The hybrid from the encoding chapter: small ints go INLINE.
            if let Ok(v) = i32::try_from(*value) { self.emit(Op::LoadInt(v), *span) }
            else { let k = self.chunk.add_constant(Value::Integer(*value))?;
                   self.emit(Op::LoadConst(k), *span) }
        }
        Expr::Float { value, span } => {
            let k = self.chunk.add_constant(Value::Float(*value))?;
            self.emit(Op::LoadConst(k), *span)
        }
        Expr::Str { value, span } => {
            let s = self.intern(value);                 // interned, so the pool dedups by handle
            let k = self.chunk.add_constant(Value::Str(s))?;
            self.emit(Op::LoadConst(k), *span)
        }

        Expr::Name { name, span } => match self.resolve_local(name) {
            Some(slot) => self.emit(Op::GetLocal(slot), *span),
            // Lab 14 inserts an upvalue lookup here, between local and global.
            None => { let k = self.name_constant(name)?; self.emit(Op::GetGlobal(k), *span) }
        },

        // and/or are NOT ordinary binary operators — they compile to jumps.
        Expr::Binary { op: BinOp::And, lhs, rhs, .. } => return self.compile_and(lhs, rhs),
        Expr::Binary { op: BinOp::Or,  lhs, rhs, .. } => return self.compile_or(lhs, rhs),

        Expr::Binary { op, lhs, rhs, span } => {
            self.compile_expr(lhs)?;                    // LEFT first: Ember's guaranteed order
            self.compile_expr(rhs)?;
            self.emit(binop_code(*op), *span);
        }
        Expr::Unary { op, operand, span } => {
            self.compile_expr(operand)?;
            self.emit(unop_code(*op), *span);
        }
        // Call, Index, Function, Table: Steps 5–6 and Labs 13–14
        _ => return Err(compile_error_at(e.span(), "not supported yet")),
    };
    Ok(())
}
}

The and/or arms must come before the general Binary arm, exactly as they did in the tree walker. Same rule, second implementation, and it is the kind of thing Lab 12 exists to check.

Checkpoint question. Expr::Name resolves local-then-global. What is the third case it will need in Lab 14, and where does it go in that match?

Step 3: Scopes and Slots

Write begin_scope, end_scope, declare_local, and resolve_local from the concept chapter. Then:

#![allow(unused)]
fn main() {
Stmt::Local { names, exprs, span } => {
    // ORDER: compile all initializers FIRST (they see the OUTER scope),
    // then declare. This is `local x = x` reading the outer x — the same
    // ordering rule as the tree walker's, implemented in a different place.
    self.compile_exprlist(exprs, names.len())?;
    for name in names { self.declare_local(name, *span)?; }
    // No SET_LOCAL is emitted! The values are ALREADY in the right slots,
    // because slots are allocated at the current stack top. That is the whole
    // trick of a stack machine's local allocation, and it surprises everyone.
}
}

Warning: That last comment is the single most confusing thing in Lab 10. local a, b = 1, 2 emits LOAD_INT 1; LOAD_INT 2 and nothing else — because slots 0 and 1 are, by definition, the two stack positions those values now occupy. SET_LOCAL exists only for assignment to an existing local (a = 5), not for declaration. Check it in the disassembly before moving on; if you emit a SET_LOCAL here you will have an extra value on the stack and every subsequent slot number will be wrong.

Step 4: Control Flow

Write compile_if, compile_while, compile_break, compile_and, compile_or, and compile_numeric_for from the concept chapter.

The numeric for is the fiddly one, because the four control values live in hidden slots:

#![allow(unused)]
fn main() {
Stmt::NumericFor { var, start, stop, step, body, span } => {
    self.begin_scope();
    self.compile_expr(start)?;                       // hidden slot i
    self.compile_expr(stop)?;                        // hidden slot limit
    match step { Some(e) => self.compile_expr(e)?, None => self.emit(Op::LoadInt(1), *span) };
    self.declare_hidden("(for i)")?;                 // three hidden locals so that
    self.declare_hidden("(for limit)")?;             // end_scope pops them correctly
    self.declare_hidden("(for step)")?;
    let prep = self.emit_jump(Op::ForPrep, *span);   // pushes the count; jumps past the body

    let top = self.chunk.code().len() as u32;
    self.begin_scope();
    self.declare_local(var, *span)?;                 // the VISIBLE loop variable — a fresh
    self.breaks.push(Vec::new());                    // binding, copied by FOR_LOOP each pass
    self.compile_block(body)?;
    self.end_scope(*span);

    self.emit(Op::ForLoop(top), *span);
    self.patch_jump(prep);
    for b in self.breaks.pop().unwrap() { self.patch_jump(b); }
    self.end_scope(*span);
}
}

The hidden locals exist so that end_scope accounts for them. Lua does the same thing and even gives them those names — luac -l -l on a for loop shows (for state) entries in the locals table. Go look.

Step 5: Functions and Protos

#![allow(unused)]
fn main() {
Expr::Function { name, params, is_vararg, body, span } => {
    let mut sub = Compiler::new_child(self, name.clone());
    sub.begin_scope();
    for p in params { sub.declare_local(p, *span)?; }     // params are slots 0..n
    sub.compile_block(body)?;
    sub.emit(Op::LoadNil, *span);                          // implicit `return` for a body
    sub.emit(Op::Return(1), *span);                        // that falls off the end
    let proto = sub.finish(*params.len() as u8, *is_vararg)?;
    validate(&proto)?;                                     // ← validate EVERY proto you build
    let idx = self.chunk.add_proto(proto)?;
    self.emit(Op::Closure(idx), *span);
}
}

Three notes:

• Every function ends in a RETURN, always, even if the body already returned. Validator rule 8 requires it and it removes a "what happens if ip runs off the end" case from the VM entirely.
• validate runs on every proto as it is built, in debug builds at minimum. This is your compiler's test suite and it costs microseconds.
• new_child carries a parent pointer that is unused until Lab 14. Putting it in now is cheaper than threading it through later.

The three definition forms desugar as they did in Lab 7 — and local function f must declare f before compiling the body, or f inside the body resolves as a global:

#![allow(unused)]
fn main() {
Stmt::LocalFunction { name, func, span } => {
    let slot = self.declare_local(name, *span)?;   // FIRST — so the body can see it
    self.compile_expr(func)?;                      // the CLOSURE lands in that slot
    debug_assert_eq!(slot as i32, self.stack_depth - 1);
}
}

Step 6: Compile-Time Errors

Every limit produces a diagnostic with a span. Test each with a generated file:

The Trace

Four programs. Run each, read each, check each by hand.

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

constants: (none — all three fit in LOAD_INT)
0000     1  LOAD_INT     10
0001     |  LOAD_INT     20
0002     |  LOAD_INT     3
0003     |  MUL
0004     |  ADD                                    ← slot 0 is now x, by position
0005     |  GET_LOCAL    0          ; x
0006     |  RETURN       1

Notice there is no SET_LOCAL. x is stack position 0. And notice MUL before ADD — the tree shape from Lab 2 became instruction order.

$ ember disassemble -e 'local a = 1 do local b = 2 end do local c = 3 end return a'

0000     1  LOAD_INT     1                         ; a → slot 0
0001     |  LOAD_INT     2                         ; b → slot 1
0002     |  POP          1                         ← end of first block
0003     |  LOAD_INT     3                         ; c → slot 1   ← REUSED
0004     |  POP          1
0005     |  GET_LOCAL    0          ; a
0006     |  RETURN       1

Slot reuse, visible. b and c are both slot 1. If yours gives c slot 2, end_scope is not popping locals.

$ ember disassemble -e '
local n = 0
while n < 3 do
  local doubled = n * 2
  if doubled > 2 then break end
  n = n + 1
end
return n'

0000     2  LOAD_INT     0                         ; n → slot 0
0001     3  GET_LOCAL    0          ; n            ← 0001 is the loop TOP
0002     |  LOAD_INT     3
0003     |  LT
0004     |  JUMP_IF_FALSE 0016      ; exit
0005     4  GET_LOCAL    0          ; n
0006     |  LOAD_INT     2
0007     |  MUL                                    ; doubled → slot 1
0008     5  GET_LOCAL    1          ; doubled
0009     |  LOAD_INT     2
0010     |  GT
0011     |  JUMP_IF_FALSE 0014
0012     |  POP          1                         ← THE BREAK'S POP: discards `doubled`
0013     |  JUMP         0016       ; break
0014     6  GET_LOCAL    0          ; n
0015     |  LOAD_INT     1
0016     |  ADD
0017     |  SET_LOCAL    0          ; n
0018     |  POP          1                         ← end of loop body scope: `doubled`
0019     |  JUMP         0001 (back)
0020     8  GET_LOCAL    0          ; n
0021     |  RETURN       1

Line 0012 is the whole lab. Without that POP 1, the break leaves doubled on the stack, the stack is one deeper than the compiler believes, and GET_LOCAL 0 after the loop reads the wrong slot. It is silent, it needs a loop body with a local and a break to trigger, and verify_stack_depth catches it instantly — because 0016 would be reached at two different depths.

(The offsets above are illustrative; yours will differ if your POP placement or for lowering differs. What must match is the structure: a POP before every break jump that leaves a scope, a back-edge to the condition, and consistent depths at each join.)

$ ember disassemble -e 'local a = false and f() return a'

0000     1  LOAD_FALSE                             depth 0 → 1
0001     |  JUMP_IF_FALSE_KEEP 0005                depth 1 → 1
0002     |  POP          1                         depth 1 → 0
0003     |  GET_GLOBAL   0          ; f
0004     |  CALL         0 1                       depth 1 → 1
0005     |  GET_LOCAL    0          ; a            ← depth 1 from BOTH paths ✔
0006     |  RETURN       1

Write the depths in the margin yourself for one of these. Doing it by hand once is what makes verify_stack_depth's failures legible for the rest of the curriculum.

Expected Output

$ cargo test --lib compiler
test compiler::every_golden_program_compiles_and_validates ... ok
test compiler::constants_are_deduplicated ... ok
test compiler::sibling_blocks_reuse_slots ... ok
test compiler::break_pops_the_scopes_it_leaves ... ok
test compiler::and_or_balance_on_both_paths ... ok
test compiler::too_many_locals_is_a_clean_error ... ok

$ ember disassemble tests/golden/programs/fizzbuzz.ember | head -5
$ for f in tests/golden/**/*.ember; do ember disassemble "$f" >/dev/null || echo "FAILED $f"; done

Debugging Steps

compile_expr must leave exactly one value fires

Read the node it names. Usually an arm that forgot to emit, or an and/or reaching the general binary path.

Slot numbers are off by one after a local

You emitted a SET_LOCAL for a declaration. Declarations do not need one — see the warning in Step 3.

The loop runs one iteration too many

JUMP_IF_FALSE's target is the back-edge instead of the instruction after it.

The loop never exits

The back-edge targets the body instead of the condition, or a jump is still u32::MAX and validate was not run.

verify_stack_depth reports an inconsistent join in a loop with a break

The break did not pop the locals declared since the loop started. This is the bug the trace above is about.

A nested function sees the enclosing function's locals

Compiler::new_child is sharing locals instead of starting a fresh vector. Each function has its own slot space.

local function f — f inside the body compiles to GET_GLOBAL

You compiled the function expression before declaring the local.

Experiment

CLAIM. The compiler does the tree walker's scope search once instead of once per execution, and you can count the difference exactly.

METHOD. Instrument resolve_local with a counter. Compile tests/golden/programs/fib25.ember and record how many times it ran. Then take the tree walker's probe counter from Lab 5's experiment and record how many times it ran on the same program.

PREDICTION. Write the ratio before you look. (For fib(25), the compiler resolves each name a handful of times; the tree walker resolves them once per call, and there are ~243,000 calls.)

RESULT. Record both numbers in docs/learning/05-bytecode.md. This ratio is the honest answer to "why is a bytecode VM faster?", and it has nothing to do with the word "compiled".

Test

#![allow(unused)]
fn main() {
#[test]
fn every_golden_program_compiles_and_validates() {
    for case in corpus() {
        let ast = parse(&case.src).expect(&case.name);
        let proto = Compiler::compile_chunk(&ast).expect(&case.name);
        validate(&proto).unwrap_or_else(|e| panic!("{}: {e:?}", case.name));
    }
}

#[test]
fn constants_are_deduplicated() {
    let c = compile("return 1000000 + 1000000 + 1000000");   // too big for LOAD_INT? no — i32 fits
    let c = compile("return 1e300 + 1e300");                 // floats DO go in the pool
    assert_eq!(c.constants.len(), 1, "the same float literal must pool once");
}

#[test]
fn sibling_blocks_reuse_slots() {
    let c = compile("local a=1 do local b=2 end do local d=3 end");
    let slots: Vec<u8> = c.code().iter().filter_map(|op| match op {
        Op::SetLocal(s) | Op::GetLocal(s) => Some(*s), _ => None }).collect();
    assert!(c.max_stack <= 2, "sibling blocks must share a slot, got max_stack={}", c.max_stack);
}

#[test]
fn break_pops_the_scopes_it_leaves() {
    // The bug this catches is SILENT without the validator.
    let p = compile_proto("while true do local x = 1 break end");
    validate(&p).expect("break must pop `x` before jumping");
}

#[test]
fn and_or_balance_on_both_paths() {
    for src in ["local a = f() and g()", "local a = f() or g()",
                "local a = 1 and 2 or 3"] {
        validate(&compile_proto(src)).unwrap_or_else(|e| panic!("{src}: {e:?}"));
    }
}

#[test]
fn local_function_can_see_itself() {
    let c = compile("local function f() return f() end");
    // `f` inside the body must be a LOCAL access, not a global.
    assert!(!c.code().iter().any(|op| matches!(op, Op::GetGlobal(_))),
            "local function must resolve its own name as a local");
}

#[test]
fn too_many_locals_is_a_clean_error() {
    let src: String = (0..300).map(|i| format!("local v{i} = {i}\n")).collect();
    let e = try_compile(&src).unwrap_err();
    assert_eq!(e.kind, ErrorKind::Compile);
    assert!(e.message.contains("too many local"));
    assert!(e.span.is_some(), "limit errors must point at the offending declaration");
}
}

Challenge Extensions

1. Constant folding. Fold Binary(op, literal, literal) at compile time. Then find the case where folding is wrong: 1 // 0. Lua folds and refuses to fold anything that would raise — read constfolding in lcode.c. Measure the effect on your corpus's instruction count.
2. Loop rotation. Compile while with the condition at the bottom and a single jump into it, saving one jump per iteration. Measure it in Lab 11 and report whether the disassembly became harder to read.
3. Peephole: LOAD_INT 1; ADD → ADD_IMM 1. Lua has OP_ADDI. Implement it, then hold the change until Section 7 gives you a benchmark to justify it — and note in your journal how it felt to write an optimization you were not allowed to keep.
4. Slot-liveness reporting. Emit a warning for a local that is declared and never read. This is a real linter feature and it falls out of the information the compiler already has.
5. Compile-time assert of the two invariants in release too. Measure the cost. Is it small enough to keep on always? (For a compiler that runs once per script, almost certainly yes — and that is a different answer from the VM's hot loop, which is worth noticing.)

Deliverables

• compile_expr (+1) and compile_stmt (0) wrappers with debug assertions, written first.
• stack_depth/max_stack tracked in emit using the same table as the validator.
• All of Section 2's language compiles: locals, assignment, blocks, if/elseif/else, while, numeric for, break, return, and/or, functions, calls, recursion.
• Every golden program compiles and validates.
• local x = x reads the outer x; local function f sees itself. Both tested.
• Sibling blocks reuse slots; break pops the scopes it leaves.
• All four compile-time limits produce diagnostics with spans.
• validate() is called on every proto in debug builds.
• The resolve_local-vs-tree-walker-probes ratio recorded in docs/learning/05-bytecode.md.
• The four traces above reproduced and read by hand.

Validation / Self-check

1. State the two stack invariants and the exact assertion that enforces each.
2. Why does local a, b = 1, 2 emit no SET_LOCAL? What does SET_LOCAL exist for?
3. How does the compiler make local x = x read the outer x? Where is the same rule in the tree walker?
4. Draw the instruction layout of while c do body end and mark the two jump targets.
5. What must compile_break emit before its jump? Which validator rule catches its absence?
6. Trace the stack depth through a and b on both paths and show they agree at the join.
7. Where do the numeric for's hidden control values live, and why are they declared as locals?
8. Give the ratio from the experiment, and use it to explain why a bytecode VM is faster — without using the word "compiled".

Next: Lab 11 — The Virtual Machine.