Lab 12: Differential Testing (Milestone 8)

Background

Eight lines of new test code. That is the whole lab.

Because Lab 8's harness is backend-agnostic, adding a second Backend impl and one comparison test turns every test you have ever written, and every test you will ever write, into a two-implementation test. This is the payoff for ADR-003, written four weeks ago, before you knew whether it would be worth it.

Then you build a program generator, find the divergences you did not think of, and write down precisely what this technique cannot catch.

Why This Lab Matters

• Every feature from here to the capstone is checked by two independent implementations. Closures, upvalues, GC, metatables, multiple returns — all of Section 4's hard parts land with this net already under them.
• It is the least glamorous lab and the highest-leverage one. Nothing new runs. What changes is the cost of every future bug, which drops from "find it by reading code" to "the test names the program".
• Knowing the blind spot is half the value. A technique you trust beyond its scope is worse than one you do not have.

Prerequisites

• Lab 11 complete: the VM runs the corpus.
• The Reference Implementation re-read — especially §8, the blind spot.

Predict First

1. How many of your ~27 golden programs will disagree between the backends on the first run? Write a number.
2. Which category will disagree first: arithmetic, scope, control flow, or functions?
3. print(1/0) — will the two backends print the same text? What about print(0/0)?
4. Which of these bugs would differential testing catch: (a) a wrong jump target, (b) Lua's modulo sign rule implemented incorrectly, (c) local x = x binding before evaluating in the compiler only, (d) the lexer mis-lexing ..?
5. If both backends print the same wrong answer, what is the only thing that can tell you?

Step 1: The Eight Lines

#![allow(unused)]
fn main() {
// tests/differential.rs
#[test]
fn backends_agree_on_the_whole_corpus() {
    for case in corpus() {
        let a = TreeBackend::new().run(&case.src, &Limits::test_defaults());
        let b = VmBackend::new().run(&case.src, &Limits::test_defaults());
        match (a, b) {
            (Ok(x), Ok(y))   => assert_eq!(x, y, "OUTPUT differs in {}", case.name),
            (Err(x), Err(y)) => assert_eq!(x.kind, y.kind, "ERROR KIND differs in {}", case.name),
            (a, b) => panic!("{}: one backend succeeded and the other failed\n\
                              interp: {a:?}\nvm:     {b:?}", case.name),
        }
    }
}
}

Three rules, each of which you would get wrong on the first attempt if it were not written down:

1. Compare stdout, not internal state. The backends' internals are supposed to differ. The contract is observable behavior.
2. Compare ErrorKind, not messages. The VM's message knows an instruction pointer; the tree walker's knows an AST node. Requiring identical text would be pointless churn and would push you toward making the messages worse — the same distinction Section 5 makes for hosts, where kind is the API and the message is presentation.
3. A one-sided failure is the loudest case. One backend succeeding while the other errors is almost always a real bug, and it deserves its own arm with both results printed.

Run it. Record the number of failures before you fix anything — that number is data about your own error rate and you will want it in docs/learning/06-vm.md.

Step 2: Read the First Divergence Properly

When a case fails, do not immediately edit the VM. Follow the procedure, because which backend is wrong is genuinely not obvious:

# 1. Isolate. Shrink the program by hand until one line differs.
ember run --interp /tmp/min.ember
ember run          /tmp/min.ember

# 2. Which representation? Look at the artifact between them.
ember ast          /tmp/min.ember
ember disassemble  /tmp/min.ember
ember trace        /tmp/min.ember

# 3. Consult the SPECIFICATION, not your memory.
grep -n 'RULE' docs/architecture.md | grep -i <the-construct>

# 4. Ask the third oracle.
lua /tmp/min.ember

Step 3 is the one people skip and the one that matters. The question is not "which backend do I prefer?" — it is "which one matches docs/architecture.md?" If neither does, you have found the most valuable kind of bug: the specification is wrong or silent, and both implementations guessed. Fix the document first, then both backends.

Write the outcome of your first three divergences in docs/learning/06-vm.md in this shape:

DIVERGENCE 1
  program:      local x = 1; local x = x + 1; return x
  interp:       2
  vm:           nil
  spec says:    RULE:local-init-order — the initializer is evaluated before the binding exists
  who was wrong: VM (the compiler declared the local before compiling the initializer)
  fix:          compiler.rs — move declare_local after compile_exprlist
  invariant:    a golden case now pins it in BOTH backends

That last line is the important one. Every divergence you fix must leave a corpus case behind, or you have fixed the instance and not the class.

Step 3: Generate Programs You Would Not Have Written

Hand-written cases test what you understood. A generator tests what you did not.

#![allow(unused)]
fn main() {
// tests/property.rs
proptest! {
    #[test]
    fn generated_programs_agree(p in arb_program(4)) {
        let limits = Limits { instructions: 200_000, depth: 32, ..Limits::test_defaults() };
        let a = TreeBackend::new().run(&p, &limits);
        let b = VmBackend::new().run(&p, &limits);
        match (a, b) {
            (Ok(x), Ok(y))   => prop_assert_eq!(x, y, "source:\n{}", p),
            (Err(x), Err(y)) => prop_assert_eq!(x.kind, y.kind, "source:\n{}", p),
            _ => prop_assert!(false, "one-sided failure on:\n{}", p),
        }
    }
}
}

The generator is the work. Build it in layers, and start at layer 1 — a generator that emits everything at once will produce programs that error immediately and test nothing:

#![allow(unused)]
fn main() {
fn arb_program(layer: u8) -> impl Strategy<Value = String> {
    // Two properties matter more than expressiveness:
    //  * TERMINATION — bound every loop with a literal count; use the budget
    //    as a backstop, not as the primary guarantee.
    //  * OBSERVABILITY — every program must end in `print(...)` of something,
    //    or the comparison compares two empty strings and always passes.
    // A generator that produces silent programs is the most common way this
    // technique is deployed and does nothing.
}
}

Warning: The observability rule is not optional and it is easy to violate silently. Add a meta-test: assert that a sample of generated programs produce non-empty output. A property test that passes because both backends printed nothing is worse than no test — it reports confidence you have not earned.

Step 4: Write Down the Blind Spot

Differential testing cannot find a bug in code the two backends share. Ember's backends share:

• lexer.rs and parser.rs — the entire front end
• value.rs — raw_eq, ordering, truthiness, type_name
• arith::* — every arithmetic and comparison helper
• strings.rs, table.rs, heap.rs (from Section 4)
• error.rs and the Span/SourceMap machinery

So:

Put that table in docs/learning/06-vm.md. The difference between "we have differential testing" and understanding what the sentence buys is exactly this table.

Then add the mitigation — the third oracle:

#![allow(unused)]
fn main() {
// tests/lua_compat.rs — behind `--features lua-compat`, since it needs `lua` installed.
#[test]
fn corpus_agrees_with_real_lua_where_we_do_not_diverge() {
    for case in corpus().iter().filter(|c| !c.diverges_from_lua) {
        let ours = VmBackend::new().run(&case.src, &Limits::none()).unwrap();
        let theirs = run_reference_lua(&case.src).unwrap();
        assert_eq!(ours, theirs, "{} differs from Lua 5.4", case.name);
    }
}
}

diverges_from_lua is a flag in the corpus case header, and every case that sets it must name the entry in appendix/lua-differences.md that justifies it. That coupling is what keeps the divergence list honest: you cannot skip a Lua comparison without documenting why.

The Trace

$ cargo test --test differential
running 1 test
test backends_agree_on_the_whole_corpus ... FAILED

---- backends_agree_on_the_whole_corpus stdout ----
OUTPUT differs in scope/shadowing
  left:  "1\n2\n3\n1\n"
  right: "1\n2\nnil\n1\n"

Now the procedure:

$ cat > /tmp/min.ember <<'EOF'
do
  local x = 2
  local x = x + 1
  print(x)
end
EOF
$ ember run --interp /tmp/min.ember      # 3
$ ember run          /tmp/min.ember      # nil
$ lua /tmp/min.ember                     # 3

$ ember disassemble /tmp/min.ember
0000     2  LOAD_INT     2                    ; x → slot 0
0001     3  GET_LOCAL    1          ; x       ← slot 1?! It was declared before the initializer.
0002     |  LOAD_INT     1
0003     |  ADD

There it is. GET_LOCAL 1 reads the new, uninitialized x instead of the outer one — the compiler called declare_local before compile_expr. The tree walker got it right because Lab 5 put the ordering in the right place there, and docs/architecture.md says which is correct.

One rule, two implementations, one of them wrong, found by a test nobody wrote for it. That is the entire argument for ADR-003, demonstrated on your own code.

After the fix:

$ cargo test --test differential
test backends_agree_on_the_whole_corpus ... ok
$ cargo test
test result: ok. NN passed; 0 failed

Expected Output

$ cargo test
test golden::tree_interpreter_matches_the_corpus ... ok
test golden::vm_matches_the_corpus ... ok
test differential::backends_agree_on_the_whole_corpus ... ok
test property::generated_programs_agree ... ok
test property::generated_programs_produce_output ... ok

$ cargo test --features lua-compat --test lua_compat
test corpus_agrees_with_real_lua_where_we_do_not_diverge ... ok

Debugging Steps

Zero failures on the first run

Suspicious, and usually one of three things: the corpus is too small, the programs produce no output, or check is not actually comparing. Add a deliberate bug to the VM (change ADD to SUB) and confirm the test fails. A test you have never seen fail is not a test.

The property test passes instantly and always

Your generator produces programs with no print. See the warning in Step 3.

1/0 prints differently between backends

Both call the same Display, so this cannot happen — unless one backend formats through a different path. Check for a to_string in the VM's print that the tree walker's does not use. This is a shared-code assumption you should verify rather than assume.

The property test fails with a 400-line program

proptest shrinks; look at the shrunk case, not the original. If shrinking is not producing something small, your generator's shrink strategy is missing — write it, it is worth the hour.

Error kinds differ: Limit vs Runtime

The two backends account for recursion differently. The tree walker counts FrameInfo pushes; the VM counts CallFrame pushes. If one counts native calls and the other does not, deep recursion hits different limits. Make both count the same events and add a corpus case.

Both backends agree and both are wrong

The only thing that can tell you is an independent oracle: lua, the manual, or the warm-up experiments. This is the blind spot, live.

Experiment

CLAIM. Differential testing finds bugs that hand-written tests do not, and the ratio is large.

METHOD. Count three things:

1. How many bugs your hand-written unit tests found while building Labs 9–11.
2. How many the golden corpus found once the VM ran it.
3. How many the differential test and the generator found afterwards.

Then, for each bug in category 3, ask: would I have written a test for this? Be honest.

PREDICTION. Before tallying: what fraction of your VM bugs do you think category 3 caught?

RESULT. Put the tally in docs/learning/06-vm.md. It is the empirical justification for the ~1,000 lines of tree walker you are now maintaining forever, and it is the number to quote when someone asks why you have two interpreters.

Test

#![allow(unused)]
fn main() {
#[test]
fn the_differential_test_can_actually_fail() {
    // A meta-test. Run a program under a DELIBERATELY broken backend and assert
    // the comparison reports it. Without this, a comparison that silently does
    // nothing looks exactly like a comparison that passes.
    let mut broken = VmBackend::with_sabotage(Sabotage::AddIsSub);
    let case = Case::inline("print(2 + 3)", "5\n");
    assert!(check(&mut broken, &case).is_some(), "the harness must detect a wrong result");
}

#[test]
fn generated_programs_produce_output() {
    // The property test is worthless if the programs print nothing.
    let sample: Vec<String> = sample_programs(50, 4);
    let silent = sample.iter().filter(|p| !p.contains("print")).count();
    assert_eq!(silent, 0, "{silent}/50 generated programs produce no observable output");
}

#[test]
fn every_lua_divergence_is_documented() {
    // A corpus case may opt out of the Lua comparison ONLY by naming the
    // documented divergence that justifies it. This is what keeps
    // appendix/lua-differences.md from rotting.
    let documented = divergence_ids_in_appendix();
    for case in corpus().iter().filter(|c| c.diverges_from_lua) {
        assert!(documented.contains(&case.divergence_id),
                "{} opts out of the Lua comparison with undocumented id {:?}",
                case.name, case.divergence_id);
    }
}

#[test]
fn both_backends_reach_the_same_limit_kinds() {
    for src in ["while true do end",
                "local function f() return f() end return f()",
                "local t = {} for i=1,1e9 do t[i]=i end"] {
        let limits = Limits { instructions: 100_000, depth: 64, memory: 1 << 20 };
        let a = TreeBackend::new().run(src, &limits).unwrap_err();
        let b = VmBackend::new().run(src, &limits).unwrap_err();
        assert_eq!(a.kind, b.kind, "limit kind differs for: {src}");
    }
}
}

Challenge Extensions

1. Fuzz the pair. A cargo-fuzz target that feeds arbitrary bytes as source to both backends and asserts they agree (including agreeing that it is a parse error). Cheap, and it finds front-end bugs the generator cannot express.
2. Shrink better. Write a custom proptest shrinker for your program AST that removes statements, simplifies expressions, and reduces literals. A good shrinker turns a 300-line failure into a 3-line one, and that ratio is why property testing is worth the setup.
3. Metamorphic properties. Assert relations rather than values: wrapping any statement in if true then ... end must not change output; do ... end around a block must not; adding an unused local must not. Each is a one-line property and each catches scope bugs directly.
4. Coverage-guided corpus growth. Run cargo llvm-cov over the corpus. Which vm.rs arms and which compiler.rs branches are never taken? Write cases until the VM's dispatch match is fully covered — the uncovered arms are exactly the opcodes nobody has tested.
5. A third backend. Once Section 7's JIT exists, add it to the same comparison. The harness needs zero changes, which is the entire reward for the design decision made in Lab 8.

Deliverables

• tests/differential.rs compares the whole corpus under both backends: output for successes, ErrorKind for failures, and a loud one-sided-failure arm.
• The meta-test proving the harness can detect a wrong result.
• Every divergence found is fixed and left behind a corpus case.
• The first three divergences written up in docs/learning/06-vm.md in the given shape.
• A layered program generator, with the "produces output" meta-test.
• tests/lua_compat.rs behind a feature flag, with diverges_from_lua cases required to name a documented divergence.
• The blind-spot table written in docs/learning/06-vm.md.
• The bug-source tally from the experiment.
• Milestone 8 complete: two implementations, one answer.

Validation / Self-check

1. Why compare stdout rather than internal state? Why ErrorKind rather than the message?
2. Give the four-step procedure for investigating a divergence. Which step do people skip, and what does skipping it cost?
3. What must every fixed divergence leave behind, and why?
4. Name the two properties a program generator must have. What is the symptom of missing the second?
5. List four bug locations differential testing catches and four it cannot. What covers the latter?
6. Why must a corpus case that opts out of the Lua comparison name a documented divergence?
7. What is a meta-test, and why does this lab need one?
8. Both backends print the same wrong answer. What are your options, in order?

Next: Section 4 — Objects, the Heap, and the Collector. You now have two implementations that agree. Everything Section 4 builds lands with that net underneath it.