testing

How BXM Was Tested With Two Million Damaged Inputs, Sixteen Processes and a Killed Run

Each BXM tool makes one main promise. Canon promises that every value has exactly one encoding. Memo promises that it never hands you a wrong or half-restored output. Most of the testing went into trying to break those two promises, and the results are recorded in the repository’s test/results folder by a script anyone can run again.

Canon

The property behind Canon is short to state: if the decoder accepts a byte string, encoding the decoded value gives back exactly the same bytes. If that holds, no value can have a second accepted spelling.

So the test feeds the decoder byte strings that are trying to be a second spelling. Half are short random strings built mostly from bytes that look like Canon tags and lengths, so they often almost parse. The other half start as valid encodings of random values and are then damaged: a flipped bit, a replaced byte, a dropped byte. That’s how a non-canonical encoding would actually show up, as something nearly right.

Four test results: 2,000,000 damaged byte strings with no second encoding accepted, 60 conformance vectors passing, 16 processes sharing one Memo cache, and no wrong output after a damaged cache, a killed run or an edited input

The recorded run tried 2,000,000 inputs. The decoder accepted 334,062 of them as valid values, and every one re-encoded to exactly the bytes it came from. The other 1,665,938 were rejected with a reason. The same run checked that the fast check path, which validates without building anything in memory, agreed with the full decoder on every input.

On top of that:

  • Conformance vectors. 30 values with their exact bytes and 30 byte strings that must be rejected, each with the expected error. They’re in the spec folder so other implementations can use them.
  • Round trips. Random values, including subnormal floats, the extremes of 64-bit integers and strings with emoji, go through bytes and back and through the text form and back.
  • The C API. A small C program is linked against the static library and checks that two spellings of the same JSON give the same bytes and hash, and that an overlong number is refused with the right error.
  • Limits. A string claiming to be 2^63 bytes long is rejected before anything is allocated, and nesting stops at 512 levels.

Memo

Memo’s tests aim at the ways a cache goes wrong.

  • A damaged cache. Every stored file is overwritten with garbage. The next run notices, says so, runs the command normally and stores a fresh result.
  • One bad file among several. Only the second of two output files is damaged. The restore fails without touching the outputs already on disk, and leaves no temporary files behind.
  • An input edited during the run. The command rewrites its own input. Memo sees the input changed under it and doesn’t store a result that might belong to neither version.
  • A killed run. bxm-memo is killed with SIGKILL halfway through a slow command. Afterwards there’s no cache entry for it, and the next run starts clean.
  • Leftovers of a killed store. Half-written temporary files and orphaned stored files are planted in the cache. They’re ignored and later cleaned up.
  • Sixteen processes at once. Sixteen separate bxm-memo processes, each in its own checkout, run the same job against one cache at the same time. Every one exits cleanly with the right output, and the cache ends with one good result. An earlier version of this test ran all sixteen in one folder, and it failed now and then: one run could store an output file while another was rewriting it. The tests-across-commits case study explains what that taught us.
  • The rest. Exit codes passing through, failing commands never cached, a missing output never cached, patterns that match nothing refused, executable bits restored, stale files removed from directory outputs, and garbage collection keeping the newest results.

The Go tests run under the race detector.

Where the numbers come from

All of this runs in CI on Linux and macOS for every change. The recorded run that the site quotes was on a 2-CPU Linux machine with BXM 0.1.0. Its full output, including the environment, is in test/results, and scripts/record-results.sh produces it again.

What these tests don’t cover yet: Windows is built and smoke-tested at release time but isn’t in the per-change test runs, and Memo’s tests use shell scripts as the wrapped commands, so they run on Linux and macOS only.