Wado

WEP: Eval — Compiling and Running Wado Source from a Test

Context

A code generator is tested by compiling what it generates and running it. Gale does this today one grammar at a time. Each test file names its grammar at a use ... with site, the generated parser is written to a generated/ directory, and the test calls into it:

use wa from "./grammars/wado_action.g4"
    with {
        generator: { module: "../src/generator.wado", output_dir: "./generated/action_emit" },
    };

test "wado actions emit into ParseResult.output in execution order" {
    assert wa::parse("a b").output == "hi!";
}

In package-gale/tests/, 316 files carry such a use site, and tests/generated/ holds the 740 parsers they produce. The ANTLR4 descriptor corpus is the worst fit. It is data: a grammar, an input and the expected output, many times over. Yet a script has to write it out as test files, one use site and one output directory per descriptor, because a use site is the only way to turn source text into a program.

What these tests want is a function. It takes generated source, compiles it as a program, runs it, and returns what the program printed. Rust's trybuild answers the same need.

Decision

core:eval compiles and runs a program

core:eval exports one function and the types it takes and returns:

pub struct Output {
    pub stdout: String,
    pub stderr: String,
    pub status: Status,
}

pub variant Status {
    Exited(i32),
    Trapped(TrapKind),
    OutOfFuel,
    OutOfMemory,
}

pub enum TrapKind { ... }     // one case per trap the engine reports

pub struct CompileFailure {
    pub rendered: String,     // the report `wado compile` would print
    pub codes: List<String>,  // the `Code` of each error, in report order
}

pub variant EvalError {
    CompileFailed(CompileFailure),
    CompileTimedOut,
    Unavailable(String),      // the import the host refused to link
}

impl Display for Status { ... }
impl Display for TrapKind { ... }
impl Display for EvalError { ... }
impl Error for EvalError;

pub global DEFAULT_FUEL: u64 = /* chosen by the implementation */;

pub fn eval(source: String, fuel: u64 = DEFAULT_FUEL) -> Result<Output, EvalError>;

A test uses it like any other function:

use { eval } from "core:eval";

test "a generated parser accepts its input" {
    let parser = generate(grammar);  // the generator under test, called as a library
    let program = `use { println, Stdout } from "core:cli";
${parser}
export fn run() with Stdout { println(parse("a b").output); }`;
    let out = eval(program).unwrap();
    assert out.status matches { Exited(0) }, `${out.status}\n${out.stderr}`;
    assert out.stdout == "hi!\n";
}

CompileFailure carries a failure the way an e2e fixture states one: as the whole report or as the codes it was raised under. A test can then check that a generator rejects bad input with the right error, not only that good input runs.

The split between Ok and Err is whether the program ran. Err means it never started, so there is no output to read. Ok means it ran, however it ended: Status says how, and stdout and stderr hold everything it wrote before then. A trap is where that matters most. What a failing program printed is what explains the failure, and a panic writes its message to stderr before it traps.

EvalError implements Display and Error, as every standard library error type does, so ${e} renders the compile report or the missing import. Status and TrapKind implement Display too, for an assertion's message.

The host does only what Wado cannot

The host import is kept to what Wado code cannot do: compile the source, run it, and cache the outcome. It returns the outcome as raw data. Captured output crosses as bytes, a trap as a TrapKind case, and a compile failure as the rendered report and its codes.

core:eval does the rest in Wado. It decodes stdout and stderr with String::from_utf8_lossy, so a program writing bytes that are not UTF-8 still yields a String, with U+FFFD where the invalid bytes were. It shapes the raw outcome into Result<Output, EvalError>, and it holds every Display impl.

The program is one module

source is the whole program, compiled as a single module. Its use items may name core:*, which resolves to the standard library. Any other specifier fails to compile, a relative path included, since the module has no directory. Nothing on the host's disk is read.

This is enough for Gale, which emits one module per grammar with its runtime inside. A program spread over several modules, and one that imports the calling package's dependencies, are known gaps.

The program runs as a command and gets nothing

The program is compiled for wasi:cli/command, so it exports run() and uses that world's bump allocator. Only stdout, stderr and exit are linked, and the first two are captured. It receives no arguments, no stdin, no environment, no preopened directory, no clock, no randomness and no network.

A program that imports anything else is not linked. eval returns Unavailable naming the import, instead of trapping the calling test.

Giving the program nothing is what makes its result a function of its source. The result cache below depends on that.

Every resource is bounded

The run is bounded by fuel and by a memory ceiling the runner sets, which covers every memory and table. A program that uses up either stops with OutOfFuel or OutOfMemory. Neither bound is wall-clock time, so where a program stops is deterministic too.

The compile is bounded by wall-clock time, because a compiler bug can make it loop. Past the runner's limit, eval returns CompileTimedOut. How far a compile gets in that time depends on the machine, so this outcome is never cached.

These bounds replace the calling test's timeout inside eval. A first run compiles every program it evaluates, and that alone can exceed the default 5000 ms, so time spent inside eval does not count against the test's deadline.

eval shares the runner's CPU budget, the --parallel permits every stage and package draws on. The calling test gives its permit back on entering eval and takes one again on leaving. Inside, eval takes a permit for each piece of work it does itself: one for the compile, then one for the AOT compile and the run. Nothing waiting inside eval holds a permit, whether it waits for one or for another call's slot, so the runner neither deadlocks on its own budget nor runs more work than the budget allows.

A compile past its time limit cannot be stopped, so it keeps running after the test has moved on, and it keeps its permit until it ends. Compiles left running and the tests after them share the one budget.

Compiles left running keep at most one fewer permit than the budget holds. A compile that never ends would otherwise keep its permit forever, and enough of them would stall the run with no test left to report why. One past that gives its permit back and runs outside the budget.

Only wado test supports it

eval is a testing tool, not a general capability. A program built for any world other than the test world that reaches core:eval is a compile error. Without that check, the component would build and then fail to instantiate wherever it runs.

wado test is the only host that supports it. No other host supplies the import: not the LSP, not jco, and not another runtime handed the .wasm. A component reaching core:eval fails to instantiate on any of them. The LSP still type-checks a call to eval, since that needs no host, but it never runs one. core:eval's own tests are ordinary stdlib tests, run by wado test like the rest.

eval declares no effect, as log_stdout declares none. In a test, an effect row would say nothing the world has not already said.

The program compiles as the test does

The program is compiled at the calling test's optimization level and with its -f flags. A CI job that runs a package's tests at -O2 then checks the generated code at -O2 too.

--allocator is not carried over, because the program is a command and uses the command world's allocator. --no-cache makes eval skip reading the cache below, as it makes a compile skip Kiln's.

Every outcome is cached

wasmtime's AOT compile is most of an evaluation's cost, and running the result takes almost no time. So the cache holds the outcome: the raw data the host import returns, before core:eval decodes it. A hit does not compile, instantiate or run anything.

The key covers everything the outcome depends on:

Every ingredient is known before anything runs, so the key is exact on the first run. Kiln's cache is exact for the same reason.

The binary is known by its size and modification time, as ccache knows a compiler by default, not by a hash of its contents. Hashing a 300 MB dev build takes close to two seconds, paid before the first outcome of every run, hit or miss. A rebuild changes the contents, and with them the modification time, so the hash would tell apart nothing the modification time does not. The trade is a miss after the binary is touched or copied, and a stale hit from a binary whose contents change while its size and modification time stay the same. Both are rare, and only the second is wrong. std::fs::Metadata reports both fields on every platform, where an inode or a change time would be Unix only.

The compiler is part of the key, although Kiln leaves it out of its own. What a test checks with eval is that the current compiler builds and runs the generated code. If a stale hit survived a compiler change, the test would stop checking that.

The cache never leaves the machine that wrote it, so an outcome has to repeat only on that machine. It does so even where Wasm leaves a result to the host, such as a Relaxed SIMD instruction or the payload of a NaN, because the same engine on the same machine decides the same way each time.

Outcomes live in build/eval/ under the calling file's package root, or under the calling file's directory when it is in no package. The directory is not committed. The key moves with every compiler change, so a committed cache would miss after nearly every commit. Losing the cache is never an error.

Within one wado test run, calls that share a key while it is being evaluated share one slot. The first call evaluates, and the others wait for its outcome, so the same program is never compiled twice at once.

Alternatives considered

Keep one use site per program

This is how the tests work today. It fits a hand-written test well, but it cannot iterate over data, and it adds a generated directory for every case.

Spawn wado run from the test

The test world has no process API, and adding one would give every test far more than it needs. It would also pay the AOT compile on every run, with no cache to skip it.

Evaluate inside a Kiln generator

A generator is already a Wado program, so anything eval could compute there, the generator can compute directly. The one new thing eval would give it is a check that its output compiles, and the compiler makes that check right after the generator returns.

Know the binary by its contents

Hashing the binary is exact, but it costs time in proportion to the binary's size on every run. Remembering the hash under the binary's size and modification time, as Bazel remembers file digests, pays that cost again after each rebuild. It gains over the modification time alone only when a binary is rewritten with the same contents, which a rebuild does not do.

Read the linker's build ID

An ELF NT_GNU_BUILD_ID note or a Mach-O LC_UUID identifies a binary by its contents at no cost, but whether one is written depends on the linker and its flags, and Windows has no equivalent derived from the contents.

Cache the compiled component only

This caches the cheap half. The AOT compile, which is the expensive half, would still run on every call.

Roadmap

  1. [x] core:eval: the host import and its raw outcome, the types, eval with its decoding and Display impls, and the compile error for a program outside the test world.
  2. [x] The host, in the wado test runner: compile the source under a time limit and on the runner's CPU budget, link stdout, stderr and exit only, run under fuel and a memory ceiling, and return the raw outcome. The limit is 120 s, the ceiling 1 GiB per memory and 1 GiB of pointers per table, and DEFAULT_FUEL is 10⁹.
  3. [x] The outcome cache: the key, build/eval/, --no-cache, and one slot per key within a run.
  4. [x] The deadline: time inside eval stops counting against the calling test.
  5. [ ] The pilot: rewrite Gale's ANTLR4 descriptor tests as a loop over the corpus, in place of the test files the extract script writes, and remove the output directories they no longer need.

Known gaps

References