88. Testing compilers

The worst kind of bug

When your code has a bug, you read your code. When the compiler has a bug, your code is fine and the program still does the wrong thing. Viscosity rewrites your arrays into columns. If the rewritten program ever prints something different, or fails differently, Viscosity is broken, however fast it is.

Writing expected outputs by hand for every test program would be slow and error-prone. Chapter 15 showed the way out: you don’t need the right answer if you have two programs that must agree.

Original against compiled

The repository’s test corpus is a folder of small JavaScript programs, each built to probe one case: an escape, a shape mismatch, an out-of-bounds read. The first line says what Viscosity should decide:

// viscosity: ps=aos
const ps = [];
for (let i = 0; i < 100; i++)
  ps.push({ x: i, y: i });
for (let i = 0; i < ps.length; i++)
  ps[i].x += 1;
console.log(ps[3]);

The test, from test/differential.test.ts, simplified:

for (const f of corpusFiles) {
  it(f, () => {
    const src = read(f);
    const r = compile(src, jsPlugin());
    expect(layouts(r.plan))
      .toEqual(header(src));
    const before = runIsolated(src);
    const after = runIsolated(r.code);
    expect(after).toEqual(before);
  });
}

runIsolated, in test/run.ts, runs code in a brand-new Node VM context, with its own globals, and records what happened:

const out = [];
const context = vm.createContext({
  console: { log: (...a) =>
    out.push(fmt(a)) } });
try {
  new vm.Script(code)
    .runInContext(context);
  return { out, error: null };
} catch (e) {
  const name = e.constructor.name;
  return { out,
    error: name + ': ' + e.message };
}

Step through one corpus program, and then the bug this catches:

The last step is a real experiment, not a test in the repository: compiling that file with --bounds assume produces code that prints 0 where the original threw a TypeError. Comparing errors as well as output is what catches it. And the header check catches the opposite failure. A compiler that never transforms anything passes every behaviour test, so the corpus also pins down what Viscosity should decide.

Two parsers, one answer

Viscosity has two JavaScript parsers: acorn, a popular library, and a small hand-written one. mini-parser.test.ts is differential too. For every corpus program and every end-to-end benchmark program, both must give byte-identical compiled code and explanations:

const a = compile(src,
  jsPlugin({ parser: 'acorn' }));
const m = compile(src,
  jsPlugin({ parser: 'mini' }));
expect(m.code).toBe(a.code);
expect(m.explain).toBe(a.explain);

Round trips

There is a third trick for front-ends. Parse a program, print the tree back to source, and parse that: you must get the same tree. Any difference means the parser or the printer lost something.

Viscosity doesn’t print from a tree; it edits only the parts of the source it changes. So its round trip is the identity: a program with nothing to transform must come back byte for byte, comment included:

const src = 'const a = [1, 2, 3];\n' +
  '// a comment\n' +
  'console.log(a.length);\n';
expect(compile(src, jsPlugin()).code)
  .toBe(src);

Part VII returns to round-trip testing the front-end in detail.

The Drip corpus

Your own interpreters are tested the same way. The companion’s corpus has 265 Drip programs with their expected output written beside the code, as // expect: comments. The tree-walker and the VM run the same files (each skips a handful, such as the benchmarks), and a sample also runs under stress GC, which collects on every allocation, so a missing root shows up at once. Both suites, run for this chapter:

$ npx vitest run packages/frontend-js
      Tests  64 passed (64)

$ npx vitest run   # book/companion/ts
      Tests  583 passed (583)

Fuzzing

The corpus only contains programs someone thought of. Fuzzing lets the computer think of them: generate random programs, run each through both implementations, and keep any that disagree. Viscosity doesn’t fuzz yet; this is the next step. Here is the idea at toy size: random expressions, and an “optimizer” with algebraic rules, one of them wrong:

// Seeded randomness: one seed always
// gives the same programs, so a failure
// can be reproduced exactly.
let seed = 7;
function rand(k) {
  seed = (seed * 16807) % 2147483647;
  return seed % k;
}

// A random expression over x: a number,
// 'x', or [op, left, right].
function gen(d) {
  const r = rand(4);
  if (d === 0 || r === 0) {
    return rand(4);
  }
  if (r === 1) return 'x';
  const op = ['+', '-', '*'][rand(3)];
  return [op, gen(d - 1), gen(d - 1)];
}

function run(e, x) {
  if (e === 'x') return x;
  if (typeof e === 'number') return e;
  const a = run(e[1], x);
  const b = run(e[2], x);
  if (e[0] === '+') return a + b;
  if (e[0] === '-') return a - b;
  return a * b;
}

// The "optimizer": algebraic rules.
function fold(e) {
  if (!Array.isArray(e)) return e;
  const op = e[0];
  const a = fold(e[1]);
  const b = fold(e[2]);
  const na = typeof a === 'number';
  const nb = typeof b === 'number';
  if (na && nb) return run([op, a, b]);
  const zero = a === 0 || b === 0;
  if (op === '*' && zero) return 0;
  if (op !== '*' && a === 0) return b;
  if (op !== '*' && b === 0) return a;
  return [op, a, b];
}

let bad = false;
for (let t = 1; t <= 2000; t++) {
  const e = gen(3);
  const x = rand(10);
  const want = run(e, x);
  const got = run(fold(e), x);
  if (got !== want) {
    console.log('program', t, 'x =', x);
    console.log(JSON.stringify(e));
    console.log('want', want);
    console.log('got', got);
    bad = true;
    break;
  }
}
if (!bad) console.log('2000 agreed');
// Find the wrong rule and fix it.

The hard part is generating programs worth running. A random string of characters doesn’t parse, and a random program that parses may read uninitialized memory or loop forever. Then a disagreement means nothing.

Your turn

function diffTest(f, g, gen, n) {
  for (let i = 0; i < n; i++) {
    const x = gen(i);
    if (f(x) !== g(x)) return x;
  }
  return undefined;
}

function shrink(xs, fails) {
  // your code here
  return xs;
}

// Fails whenever 3 and 5 are both in.
const fails = (ys) =>
  ys.includes(3) && ys.includes(5);
console.log(
  shrink([1, 3, 8, 5, 2], fails));

What you learned

• Differential testing compares two implementations on the same inputs. Viscosity compares each program before and after compiling, output and errors, in fresh VM contexts.
• Behaviour checks alone pass a compiler that does nothing, so the corpus headers also check each layout decision.
• Two parsers that must agree, byte for byte, is differential testing too.
• Round-trip testing checks that opposite operations undo each other. Viscosity’s version: nothing to transform means identical output.
• Fuzzing generates random programs. Seed it, keep the programs valid, and reduce what fails. The repository doesn’t fuzz yet.