Files

C++ translation of Statement.closedForm

This directory contains a C++20 translation of Statement.closedForm from Statement.lean, an equivalent summarised implementation, a libFuzzer differential harness, and a nanobench comparison.

The Lean build is untouched.

Layout

Path Purpose
src/model.h Data model: borrowed input keys (std::string_view), owned result keys (std::string), WithTop Key = std::optional, ℕ∞ = NatInf.
src/literal.cpp Line-by-line transliteration of Statement.closedForm, including its repeated scans.
src/fast.cpp The same decision tree, but with a summary of the reported keys and lazily cached cardinalities.
oracle/gen.lean Deterministic generator of golden vectors by evaluating the real Lean closedForm.
tests/golden.cpp Checks the literal translation against the Lean golden vectors.
tests/diff_corpus.cpp Compares literal and fast on the sorted subset of the golden corpus.
tests/smt_cases.txt Curated readable cases found by SMT-assisted mutation analysis; run by the smt_cases CTest.
tests/readable_gen.h Readable-by-construction instance generator (owns the selector keys and reported keys, with borrowed views into them).
tests/extreme.cpp Regression test for offsets at the ends of the 32-bit input range.
tests/sweep.cpp Deterministic sweep over a finite class of small readable instances (also the coverage driver).
tests/fuzz_readable.cpp libFuzzer differential test: literal vs. fast on readable instances.
tests/corpus/readable/ Committed read-only seeds for fuzz_readable.
tests/fuzz_raw.cpp libFuzzer safety test on arbitrary instances under ASan/UBSan.
tests/bench.cpp nanobench literal-vs-fast benchmark.
run-fuzz.sh Rebuilds and runs both fuzzers for a fixed time.
run-coverage.sh Builds with Clang source-based coverage and requires 100% region, function, instantiation, line, branch, and MC/DC coverage of src/fast.cpp.
third_party/nanobench.h Vendored nanobench (commit 7252da9d96bd0d71f508e9b2813ab1f57fdfaec1).

Data model

Inputs borrow and results own. RangeRead selectors and the reported keys in Result are std::string_views (the reported keys via a std::span), so a caller can point them straight at existing storage and the implementation reads them in place. ConflictRange returns owned std::strings because the decision procedure can synthesise endpoints (keyAfter, clamp bounds) that are not present in the input.

Selector offsets are std::int32_t, matching the caller contract. The closed form converts the public RangeRead to detail::RangeRead, whose offsets are Int = std::int64_t, before deriving selectors (for example end.offset - residualT). All intermediate Int arithmetic assumes 64-bit signed integers do not overflow; with 32-bit input offsets and in-memory key counts that is far from the limit. The corpus parsers read offsets into a wider integer and reject values outside the 32-bit range before narrowing to Selector.

Scope of the two implementations

literal.cpp is the total transliteration: it is defined on arbitrary inputs, and golden_test compares it with Lean over the whole generated corpus, most of which is not readable. fast.cpp is the readable-only implementation: diff_corpus filters the corpus to readable cases, and the fuzzers and the finite sweep generate readable instances. The Lean anchor therefore covers literal on all inputs, while fast is anchored to literal on the readable subset.

Build

cd cpp
cmake -S . -B build -G Ninja -DCMAKE_CXX_COMPILER=clang++-21
cmake --build build

Run the registered tests with CTest:

ctest --test-dir build --output-on-failure

golden and diff_corpus read oracle/golden.txt; regenerate it first if it is missing (see below). smt_cases reads the committed tests/smt_cases.txt and needs no generated input.

Golden vectors from Lean

cd ..
lake env lean --run cpp/oracle/gen.lean > cpp/oracle/golden.txt
./cpp/build/golden_test cpp/oracle/golden.txt
# golden: 40000 cases, 0 mismatches

The golden test compares exact endpoints, because the literal translation reproduces Lean's interval encoding exactly (including empty intervals).

diff_corpus compares the literal and fast implementations on the generated cases that satisfy the readable sorting invariant:

./cpp/build/diff_corpus cpp/oracle/golden.txt

extreme_test checks both implementations on offsets from INT32_MIN to INT32_MAX, which the fuzzers do not generate:

./cpp/build/extreme_test
# extreme: 7574 cases, 0 mismatches

sweep_test is exhaustive over a specific bounded class rather than sampling it: every sorted database of at most four stored keys drawn from a fixed universe of boundary keys, every selector key (including ⊥ and ⊤) with offsets in [-3, 5], both traversal directions, and every readable result shape (the complete traversal, each nonempty truncated prefix, or the empty result when the traversal is empty):

./cpp/build/sweep_test
# sweep: 13565772 cases, 0 mismatches

It runs in about a second and is also the coverage driver. It is exhaustive only within those bounds; the class is not all readable inputs, and the guarantee is that every instance in this family agrees. In particular, branch coverage cannot exercise a predicate operand that the implementation no longer contains: the coverage gate describes the code as written, it is not a proof of equivalence with literal.cpp.

Coverage

./cpp/run-coverage.sh

The script configures a Clang source-based-coverage build with MC/DC instrumentation, runs sweep_test, and fails unless src/fast.cpp has 100% region, function, instantiation, line, branch, and MC/DC coverage. sweep_test alone covers every region, function, instantiation, line, branch side, and MC/DC condition of the summarised implementation. MC/DC instrumentation requires Clang 18 or newer. The totals are not recorded here: they change with the implementation, and the coverage run reports the current ones.

Because equivalence is only promised on readable inputs, src/fast.cpp deletes both unreachable control-flow branches and predicate operands that an enclosing dispatch invariant fixes. Examples include the complete-closed family, the offset-one total/any wrappers, the hoisted and specialised end.offset <= 1 / revTruncLeOneLow path split, the crossedCompleteEndLeOne guard, and the repeated !c.r->reverse/!o.more/offset tests inside subtrees that are only entered after those tests succeeded. literal.cpp keeps the full Lean conditions so the translation can still be audited line by line.

Fuzzing

cd cpp
mkdir -p /tmp/cr-corpus/readable /tmp/cr-corpus/raw
./build/fuzz_readable -max_total_time=300 /tmp/cr-corpus/readable tests/corpus/readable
./build/fuzz_raw      -max_total_time=300 /tmp/cr-corpus/raw

or simply ./cpp/run-fuzz.sh (optionally ./cpp/run-fuzz.sh build 600). tests/corpus/readable holds committed seeds; the first directory above is the writable corpus where libFuzzer stores newly discovered units. The CMake fuzz targets compile the implementation sources directly so that the decoder code, not just the harness, is covered by ASan/UBSan.

fuzz_readable builds a sorted, duplicate-free database, resolves both selectors against it, and reports either the complete traversal or a nonempty prefix. This makes every generated pair genuinely Readable. The differential check treats all encodings of the empty interval as equivalent and otherwise requires exact endpoints.

fuzz_raw only checks memory safety and undefined behaviour for arbitrary (possibly unreadable) inputs.

extreme_test covers offsets the fuzzers deliberately avoid (they draw offsets from [-256, 255]). Both implementations decide the closed form's keyAfterN n k < upper test from the key lengths (keyAfterNLt) rather than materialising n zero bytes, so an end.offset near INT32_MAX stays constant-time instead of attempting a 2 GiB allocation.

Benchmark

cr_bench compares the literal translation with the summarised implementation across small and long complete, truncated, and crossed reads in both traversal directions:

./cpp/build/cr_bench

It reports timings and instruction and branch counts per case. Absolute numbers vary with the machine, compiler, and frequency scaling, so run it for current figures.

Why the fast implementation is equivalent

The fast implementation replays the same decision tree on readable inputs. The only changes are:

  • reportedBelowBegin and residualT are summarised once. On readable inputs the reported keys are sorted in traversal order, so both counts are binary searches. The summaries depend only on the read and on the multiset of reported keys, so they survive the reversed-view normalisation.
  • Interval cardinalities (intervalCard) are cached lazily.
  • Complete observations are not copied: a forward result borrows the caller's span, and a reversed result is viewed backwards in place.
  • allBelowEnd is residualT == 0 and anyAtOrAboveEnd is residualT != 0.

No branch condition or returned endpoint is otherwise changed on readable inputs; branches that Readable makes unreachable are omitted. Equivalence is therefore only claimed for readable inputs, and fuzz_raw deliberately does not compare outputs on arbitrary inputs.