This page describes how bfc is tested. This is primarily useful for contributors, but is also interesting for readers working on their own PL implementations.
You can run all bfc's unit tests with Cargo.
This runs basic unit tests, property-based tests, and LLVM snapshots tests.
bfc includes property-based tests using the Rust quickcheck library. These operate on the intermediate representation used in bfc, called BFIR.
These tests verify several properties for optimisations: runtime improvement, idempotence and behavioural equivalence.
bfc optimisation should never increase the number of BFIR instructions.
f(program) should have fewer (or the same) number of instructions as
All bfc optimisation passes are idempotent. Running an optimisation twice should produce the same output as running it once.
This property applies to individual peephole optimisations, as well as the combined optimiser. Testing this catches phase ordering issues, as well as optimisations that need to compute a fixpoint.
f(f(program)) should be the same as
Verifying Behavioural Equivalence
bfc opimisation passes should never change the semantics of a program.
eval(program) should give the same result as
eval(program) terminates within a specific number of
steps. bfc checks this by evaluating the code within a sandbox.
This same evaluator is also used during compilation, for compile-time evaluation of code!
program relies on runtime inputs, the test can verify the program
state prior to the first runtime input, or choose an arbitrary input.
Some tests also check the cell state after executing
should be the same as executing
f(program). This is not true of all
optimisation passes: dead code may modify cells that are unused.
Finding Interesting Programs
BFIR defines 7 different expressions. Randomly generated IR would only have a 1/7 chance of producing a loop, so only a 1/49 chance of producing a nested loop.
Nested loops, particularly including multiply loops, tend to expose interesting bugs. BFIR generation in tests overweights these kind of loops, so tests spend more time exercising more complicated loops.
LLVM Snapshot Tests
llvm_tests.rs tests that certain BF programs produce the
expected LLVM IR output.
These tests tend to be brittle, especially when upgrading major LLVM versions. They are useful for verifying that unrelated refactoring hasn't changed the compiled output.
This script compiles real BF programs, runs them, and verifies their
output matches the corresponding
This is the final step in bfc testing. It catches issues that only occur in larger, real-word BF programs.