Lab 9: Bytecode and the Disassembler (Milestone 6)
Background
You will define Op, Chunk, and Proto, build the constant pool with correct deduplication,
write the line table, and produce a disassembler — before there is a compiler to feed it or a VM
to run it.
That ordering is the point of the lab. By the end you can hand-write a tiny Chunk in a test,
print it, and read it. When Lab 10's compiler produces something wrong, you will see it in the
listing rather than infer it from a wrong answer three layers later.
Why This Lab Matters
- A disassembler written after the VM is a disassembler you debug with a broken VM. Written first, it is the instrument you debug everything else with.
- The constant pool has two float bugs that pass every casual test: NaN never deduplicating, and
0.0collapsing with-0.0. - The
code.len() == lines.len()invariant is the difference between error messages that point at the right source and error messages that lie. It is enforced by makingemitthe only door.
Prerequisites
- Section 2 complete;
docs/architecture.mdwritten. - The opcode reference read — keep it open.
- Constant Pools and Encoding read.
Predict First
size_of::<Op>()for the enum in the reference. Why?local a = 0.0; local b = -0.0— how many constants, if you dedup with==? How many should there be?local a = 0/0; local b = 0/0— same question.- How large is
linesrelative tocode, in bytes? Guess before computing. - If a jump placeholder were
0and you forgot to patch it, what would the program do? - What is the total memory of a
Chunkfor a 1,000-instruction function?
Step 1: Op, Chunk, Proto
Goal. The types compile and size_of::<Op>() is asserted.
Write them exactly as in the reference. Then:
#![allow(unused)] fn main() { // The size is a DECISION (ADR: encoding), not an accident. If someone adds a // variant with a u64 payload, every chunk in the system doubles. Make it a // compile error. const _: () = assert!(std::mem::size_of::<Op>() == 8); }
Checkpoint question. Which variant is the widest, and what would Op become if you added
LoadConstLong(u32)?
Step 2: The Constant Pool, With the Float Bugs Fixed
#![allow(unused)] fn main() { #[derive(PartialEq, Eq, Hash)] enum ConstKey { Nil, Bool(bool), Int(i64), FloatBits(u64), Str(GcRef<EmberStr>) } impl ConstKey { fn of(v: Value) -> ConstKey { match v { Value::Nil => ConstKey::Nil, Value::Boolean(b) => ConstKey::Bool(b), Value::Integer(i) => ConstKey::Int(i), // to_bits(), NOT the float itself: // * NaN != NaN → keying by value adds a constant per occurrence // * 0.0 == -0.0 → keying by value MERGES them, and 1/0.0 is +inf // while 1/-0.0 is -inf. They are not the same value. Value::Float(f) => ConstKey::FloatBits(f.to_bits()), Value::Str(s) => ConstKey::Str(s), // interned: the handle IS the identity _ => unreachable!("tables and closures cannot be constants"), } } } }
Verify the second bullet against the reference implementation before you believe it:
lua -e 'print(1/0.0, 1/-0.0)' # inf -inf
lua -e 'print(0.0 == -0.0)' # true ← equal, but NOT interchangeable
Warning:
Value::Integer(1)andValue::Float(1.0)must be different constants, even though1 == 1.0is true in the language. They print differently (1vs1.0) andmath.typedistinguishes them.ConstKeykeeps them apart becauseIntandFloatBitsare different variants — but if you ever "simplify" it to a single numeric key, you will silently turn every1.0literal into1. Add the test.
Step 3: emit Is the Only Door
#![allow(unused)] fn main() { pub struct Chunk { code: Vec<Op>, // ← PRIVATE lines: Vec<Span>, // ← PRIVATE pub constants: Vec<Value>, pub protos: Vec<Rc<Proto>>, const_index: HashMap<ConstKey, u16>, } impl Chunk { pub fn emit(&mut self, op: Op, span: Span) -> usize { self.code.push(op); self.lines.push(span); debug_assert_eq!(self.code.len(), self.lines.len()); self.code.len() - 1 } pub fn code(&self) -> &[Op] { &self.code } pub fn span_at(&self, ip: usize) -> Span { self.lines[ip] } pub fn patch(&mut self, at: usize, op: Op) { self.code[at] = op; } // jump patching only } }
The fields are private and emit is the only way to append. That is the entire enforcement
mechanism for the invariant, and it is worth more than any assertion: a code path that pushes to
code without a span cannot be written.
Step 4: The Disassembler
Goal. Chunk → a listing a human can read and check by hand.
#![allow(unused)] fn main() { pub fn disassemble(chunk: &Chunk, name: &str, src: &SourceFile, out: &mut impl Write) -> Result<()> { writeln!(out, "== {name} == ({} instructions, {} constants, {} protos)", chunk.code().len(), chunk.constants.len(), chunk.protos.len())?; writeln!(out, "constants:")?; for (i, c) in chunk.constants.iter().enumerate() { writeln!(out, " [{i:>3}] {}", debug_value(*c))?; // quoted strings, 1 vs 1.0 distinct } writeln!(out, "\noffs line {:<20} {:<10} comment", "op", "operands")?; let mut prev_line = u32::MAX; for (ip, op) in chunk.code().iter().enumerate() { let line = src.location(chunk.span_at(ip).start).0; // Print the line number only when it CHANGES — the same convention Lua // and CPython use, and it makes statement boundaries visible. let lc = if line == prev_line { " |".to_string() } else { format!("{line:>4}") }; prev_line = line; writeln!(out, "{ip:04} {lc} {}", render_op(*op, chunk))?; } for (i, p) in chunk.protos.iter().enumerate() { writeln!(out, "\n--- proto [{i}]: {} ---", p.name.as_deref().unwrap_or("<anonymous>"))?; disassemble(&p.chunk, "", src, out)?; // RECURSE into nested functions } Ok(()) } }
Four rendering rules, each of which you will be grateful for in Lab 10:
- Jump targets are printed as absolute four-digit offsets —
JUMP 0016— so you can find the target with your eyes. Also mark backward jumps:JUMP 0004 (back). - Constant operands get a comment with the value.
LOAD_CONST 3 ; "score". Nobody can readLOAD_CONST 3. - Local slot operands get the local's name from
proto.local_names, when debug info is present:GET_LOCAL 2 ; n. This is the single most useful column in the listing. - Line numbers only when they change. A hundred consecutive instructions from line 12 should
show
12once.
Checkpoint question. Why does the disassembler take a &SourceFile, when Chunk already stores
spans?
Step 5: Hand-Write a Chunk and Read It
There is no compiler yet. Build one by hand — this is the test that proves the disassembler works before anything can feed it garbage.
#![allow(unused)] fn main() { #[test] fn hand_written_chunk_disassembles() { // The bytecode for: return 10 + 20 * 3 let mut c = Chunk::new(); let k10 = c.add_constant(Value::Integer(10)).unwrap(); let k20 = c.add_constant(Value::Integer(20)).unwrap(); let k3 = c.add_constant(Value::Integer(3)).unwrap(); let s = Span::new(0, 11); c.emit(Op::LoadConst(k10), s); c.emit(Op::LoadConst(k20), s); c.emit(Op::LoadConst(k3), s); c.emit(Op::Mul, s); c.emit(Op::Add, s); c.emit(Op::Return(1), s); let listing = disassemble_to_string(&c, "hand", &SourceFile::new("t", "10 + 20 * 3")); assert!(listing.contains("LOAD_CONST 0")); assert!(listing.contains("; 10")); assert_eq!(c.constants.len(), 3); } }
Then write the bytecode for an if by hand, including the jumps, and read your own listing to
check the targets. Twenty minutes, and Lab 10's jump patching stops being mysterious:
#![allow(unused)] fn main() { // if c then A else B end — write this out by hand, then disassemble it. // 0000 <c> // 0001 JUMP_IF_FALSE 0004 // 0002 <A> // 0003 JUMP 0005 // 0004 <B> // 0005 ... }
Step 6: The Stack-Effect Test
Implement documented_effect and the test from
the opcode reference. This is the test that keeps
the reference page and the implementation from drifting, and it must exist before the VM does — so
that when Lab 11 implements each arm, the effect is already specified.
Step 7: The Validator
#![allow(unused)] fn main() { pub fn validate(proto: &Proto) -> Result<()> { let c = &proto.chunk; if c.code().len() != c.lines_len() { return Err(invalid("line table length mismatch")); } if !matches!(c.code().last(), Some(Op::Return(_))) { return Err(invalid("chunk does not end in RETURN")); } for (ip, op) in c.code().iter().enumerate() { match *op { Op::LoadConst(k) | Op::GetGlobal(k) | Op::SetGlobal(k) | Op::GetField(k) | Op::SetField(k) | Op::SelfField(k) => { let v = c.constants.get(k as usize) .ok_or_else(|| invalid_at(ip, "constant index out of range"))?; // Name operands MUST be strings, so the VM never has to check. if matches!(*op, Op::GetGlobal(_) | Op::SetGlobal(_) | Op::GetField(_) | Op::SetField(_) | Op::SelfField(_)) && !matches!(v, Value::Str(_)) { return Err(invalid_at(ip, "name operand is not a string constant")); } } Op::Jump(t) | Op::JumpIfFalse(t) | Op::JumpIfFalseKeep(t) | Op::JumpIfTrueKeep(t) | Op::ForPrep(t) | Op::ForLoop(t) => { if t as usize > c.code().len() { return Err(invalid_at(ip, "jump target out of range")); } if t == u32::MAX { return Err(invalid_at(ip, "unpatched jump")); } } Op::GetLocal(s) | Op::SetLocal(s) => { if s as u16 >= proto.max_stack { return Err(invalid_at(ip, "slot out of range")); } } Op::Closure(p) if p as usize >= c.protos.len() => return Err(invalid_at(ip, "proto index out of range")), _ => {} } } verify_stack_depth(proto)?; // rule 9 — see below for p in &c.protos { validate(p)?; } Ok(()) } }
Rule 9, the stack-depth abstraction, is the interesting one and the one to write carefully:
#![allow(unused)] fn main() { /// Abstract-interpret the stack depth. At every instruction the depth is a /// single number; at every join point the incoming depths must AGREE. /// This is what the JVM and WebAssembly verifiers do, and it is only tractable /// because Ember is a stack machine. fn verify_stack_depth(proto: &Proto) -> Result<()> { let code = proto.chunk.code(); let mut depth_at: Vec<Option<i32>> = vec![None; code.len() + 1]; depth_at[0] = Some(0); let mut work = vec![0usize]; while let Some(ip) = work.pop() { let d = depth_at[ip].expect("queued only when known"); let (after, targets) = step_depth(code[ip], d, proto)?; // uses documented_effect if after < 0 { return Err(invalid_at(ip, "stack underflow")); } if after as u16 > proto.max_stack { return Err(invalid_at(ip, "stack overflow in frame")); } for t in targets { match depth_at[t] { None => { depth_at[t] = Some(after); work.push(t); } Some(existing) if existing != after => return Err(invalid_at(ip, "inconsistent stack depth at join")), Some(_) => {} // already visited with the same depth } } } Ok(()) } }
Note: Run this on every chunk your own compiler produces, in tests, not only on untrusted input. It is the single best compiler-bug detector you have: a
breakthat forgot itsPOP, anandwhose two paths disagree, a mis-patched jump — all of them show up as an inconsistent join before you ever execute a single instruction.
The Trace
$ ember disassemble -e 'local x = 10 + 20 * 3 return x'
Once Lab 10 exists this comes from the compiler; today you build the Chunk by hand in a test and
print it. Either way, the listing is the artifact:
== <argv> == (7 instructions, 3 constants, 0 protos)
constants:
[ 0] 10
[ 1] 20
[ 2] 3
offs line op operands comment
0000 1 LOAD_CONST 0 ; 10
0002 | LOAD_CONST 1 ; 20
0004 | LOAD_CONST 2 ; 3
0006 | MUL
0007 | ADD
0008 | SET_LOCAL 0 ; x
0010 | GET_LOCAL 0 ; x
0012 | RETURN 1
Now the one to study — control flow, by hand:
$ ember disassemble -e 'local n = 0 while n < 3 do n = n + 1 end return n'
offs line op operands comment
0000 1 LOAD_INT 0
0001 | SET_LOCAL 0 ; n
0002 | GET_LOCAL 0 ; n ← 0002 is the loop TOP
0003 | LOAD_INT 3
0004 | LT
0005 | JUMP_IF_FALSE 0011 ; exit
0006 | GET_LOCAL 0 ; n
0007 | LOAD_INT 1
0008 | ADD
0009 | SET_LOCAL 0 ; n
0010 | JUMP 0002 (back) ← the back-edge targets the CONDITION
0011 | GET_LOCAL 0 ; n
0012 | RETURN 1
Check three things by hand, every time you read a loop listing:
- The back-edge targets the condition (0002), not the body (0006). Targeting the body gives you an infinite loop that runs.
JUMP_IF_FALSE's target (0011) is the instruction after the back-edge, not the back-edge itself. Off by one here and the loop runs one extra iteration.- The stack depth is 0 at 0002 and 0 at 0011. Both paths into 0011 must agree — which is exactly
what
verify_stack_depthasserts, and you can now check it by eye.
And and, whose balance is the subtle one:
$ ember disassemble -e 'local a = false and error_never_called'
0000 1 LOAD_FALSE depth 0 → 1
0001 | JUMP_IF_FALSE_KEEP 0004 depth 1 → 1 (keeps!)
0002 | POP 1 depth 1 → 0
0003 | GET_GLOBAL 0 ; error_never_called
0004 | SET_LOCAL 0 ; a ← arrives at depth 1 from BOTH paths
Expected Output
$ cargo test --lib bytecode
test bytecode::float_constants_dedup_by_bits ... ok
test bytecode::int_and_float_constants_are_distinct ... ok
test bytecode::emit_keeps_the_line_table_in_step ... ok
test bytecode::implementation_matches_the_documented_stack_effect ... ok
test bytecode::validate_rejects_unpatched_jumps ... ok
test bytecode::validate_rejects_inconsistent_join_depth ... ok
Debugging Steps
size_of::<Op>() is 12 or 16
A variant with a payload wider than 6 bytes, or a u64/usize operand. SetList(u16, u32) is the
intended widest.
Every NaN literal adds a constant
You are deduplicating with PartialEq on f64. Use to_bits().
1 and 1.0 share a constant
Your ConstKey collapses numeric variants. They must be distinct — math.type and print
distinguish them.
The disassembly's line numbers are all 1
You are printing span.start instead of resolving it through the SourceFile, or the compiler is
passing Span::EMPTY.
verify_stack_depth reports underflow on correct code
Your documented_effect for a variable-effect opcode (CALL, RETURN, SET_LIST, VARARG) is
wrong. Those need their operands to compute the effect; they cannot use the fixed table.
verify_stack_depth loops forever
You are re-queueing an already-visited target. Only queue when depth_at[t] was None.
Experiment
CLAIM. The line table is as large as the code, and delta-encoding it would shrink it by roughly 8×.
METHOD. Compile (or hand-build) your largest golden program. Print
size_of::<Op>() * code.len() and size_of::<Span>() * lines.len(). Then compute what a Lua-style
encoding would cost: one signed byte per instruction, plus an absolute checkpoint every N
instructions. Count how many instructions in your chunk have the same line as their predecessor.
PREDICTION. Before measuring: what fraction of instructions share a line with the previous one? What does that imply for delta encoding?
RESULT. Record it in docs/learning/05-bytecode.md. Do not implement the compression —
the reasoning for deferring it
is that it is invisible outside Chunk, which makes it a safe thing to do later and a waste of time
to do now. The measurement is the deliverable.
Test
#![allow(unused)] fn main() { #[test] fn float_constants_dedup_by_bits_not_by_value() { let mut c = Chunk::new(); let nan1 = c.add_constant(Value::Float(f64::NAN)).unwrap(); let nan2 = c.add_constant(Value::Float(f64::NAN)).unwrap(); assert_eq!(nan1, nan2, "NaN must dedup — PartialEq says NaN != NaN, bits say equal"); let pos = c.add_constant(Value::Float(0.0)).unwrap(); let neg = c.add_constant(Value::Float(-0.0)).unwrap(); assert_ne!(pos, neg, "0.0 and -0.0 are == but NOT interchangeable: 1/0.0 vs 1/-0.0"); } #[test] fn int_and_float_constants_are_distinct() { let mut c = Chunk::new(); let i = c.add_constant(Value::Integer(1)).unwrap(); let f = c.add_constant(Value::Float(1.0)).unwrap(); assert_ne!(i, f, "1 and 1.0 print differently and math.type distinguishes them"); } #[test] fn emit_keeps_the_line_table_in_step() { let mut c = Chunk::new(); for i in 0..100 { c.emit(Op::LoadNil, Span::new(i, i + 1)); } assert_eq!(c.code().len(), 100); assert_eq!(c.span_at(42), Span::new(42, 43)); } #[test] fn too_many_constants_is_a_clean_error() { let mut c = Chunk::new(); for i in 0..=u16::MAX as i64 { let _ = c.add_constant(Value::Integer(i)); } let e = c.add_constant(Value::Integer(999_999)).unwrap_err(); assert!(e.message.contains("too many constants")); } #[test] fn validate_rejects_unpatched_jumps() { let mut c = Chunk::new(); c.emit(Op::Jump(u32::MAX), Span::EMPTY); c.emit(Op::Return(0), Span::EMPTY); assert!(validate(&proto_of(c)).unwrap_err().message.contains("unpatched")); } #[test] fn validate_rejects_inconsistent_join_depth() { // Two paths reaching one instruction with different stack depths. This is // the check that catches a `break` which forgot its POP. let c = build_chunk_with_mismatched_join(); assert!(validate(&proto_of(c)).unwrap_err().message.contains("inconsistent stack depth")); } }
Challenge Extensions
- Delta-encode the line table. Implement Lua's
lineinfo+abslineinfoscheme. Measure the size before and after on your largest chunk, and the lookup cost. Was the prediction from the experiment right? - A textual assembler. Parse the disassembly format back into a
Chunk. Now you can write bytecode tests in text, and — more usefully — you can hand-craft malformed chunks to test the validator. This makes Lab 11 much easier to test. - A serialized format. Write
Chunkto bytes with a version header and a hash of the opcode table; read it back; reject mismatches. This is what Section 5's module cache will need. - Fuzz the validator.
cargo fuzza target that builds arbitraryChunks from random bytes and callsvalidate. Assert: no panic, and anything that passes validation can be executed by Lab 11's VM without panicking. That pairing is the actual security property. - Compare listings. Disassemble the same program with
luac -l -l,dis.dis, and yours. Write down three things each listing shows that the others do not.
Deliverables
-
Op,Chunk,Protodefined;size_of::<Op>() == 8asserted at compile time. -
Constant pool deduplicates, keyed by bits for floats, with
1and1.0distinct. -
codeandlinesare private;emitis the only way to append. -
A
u16constant overflow is a clean compile error naming the limit. - The disassembler renders constants, absolute jump targets (marking back-edges), local names, and line numbers only on change — and recurses into nested protos.
-
Hand-written chunks for
10 + 20 * 3and anif/else, disassembled and read by hand. -
documented_effect+ the stack-effect test, matching the reference. -
validate()implementing all nine rules, including the stack-depth abstraction, with a test per rule. -
The line-table size experiment recorded in
docs/learning/05-bytecode.md.
Validation / Self-check
- Why is the disassembler written before the compiler and the VM?
- Give the two float constant-pool bugs and the one-line fix for both.
- Why must
1and1.0be different constants when1 == 1.0is true? - What enforces
code.len() == lines.len(), and why is that stronger than an assertion? - Give the four disassembler rendering rules and the debugging problem each one solves.
- In a
whilelisting, name the three things to check by hand and the bug each catches. - What does
verify_stack_depthcheck at a join point, and which compiler bugs does it catch before execution? - Why is rule 9 only tractable for a stack machine?
Next: Lab 10 — The Compiler.