Elamur Groupants⌕
☰

annot-ann-bfs-checks

The groupant beside annot/src/ann.rs.groupant/checks.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Implementation material. A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

Components

componentlabelwhere
approximantpartialapproximant
astpartialsyntax.json
descriptantpresentdescriptant
evidenceexecuted bounded checksevidence
invariantpartialinvariant
testsexecuted bounded checkstests

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

idtypelabelwhere
behavior-complementbehavior_complementpartial source derived modelbehavior-complement
reverse-reconstructionreverse_reconstructionpartial source derived modelreverse-reconstruction
reachability-preimagereachability_preimagepartial source derived modelreachability-preimage
error-precedencefailure_precedencepartial source derived modelerror-precedence
representation-equivalencerepresentation_equivalencepartial source derived modelrepresentation-equivalence
resource-refinementresource_refinementpartial source derived modelresource-refinement

Model text

descriptant

annot-ann-bfs-checks

Bounded exact annotation gate differential checks and an ignored manual benchmark.

Mathematical combiner

Combine source-bound partial syntax, the forward relation, typed obernants, invariants and finite checks. Restrict the forward relation by stage guards; compose the guarded graph adapter with BFS and project the first unreachable token. Use observed disagreement to revise the adapter or model. The source is authoritative; missing macro expansion, name resolution and full legacy semantic coverage remain explicit.

Epoch 2026-10-30

Prospective prediction: preserve exact errors and reduce worst-case cycle-phase work, paying linear memory. Original code is retained externally and in the test-only baseline. Exhaustive head maps, named precedence fixtures, actual compiled semantic mutants, and paired syntax projections are used; see tests.md for completed evidence. Timings remain deferred to a serial run. No earlier file-model epoch existed; legacy behavior is summarized rather than claimed fully verified.

Hybrid correction after exploratory timing

The initial unconditional-BFS implementation preserved semantics but root's baseline-first exploratory pilot observed converter star regressions of 1.95–4.21x and n=8/32 chain regressions of 3.33x/2.03x. Those observations motivated an amendment, not a final performance claim. The original epoch remains recorded. The amended hybrid retains old small and cheap walks, then applies BFS only after a linear work budget. Benchmark methodology now uses three warmup pairs and seven alternating-order samples; no amended timings are claimed here.

approximant

Forward approximant

The old check body is retained as baseline; 126126 head vectors for n=0..6 compare exact Result values. Named precedence and long-shape tests exercise negative controls. An ignored benchmark compares full production and baseline gates on preconstructed chain/star fixtures; it is not run by ordinary test commands.

For the transferred gate, after earlier predicates pass, let H(i) be the head and H(0)=0. Success iff every i in 1..=n reaches 0 under iteration of H. Otherwise return the least i whose orbit never reaches 0. Reversed adjacency satisfies G[h]={i:H(i)=h}. Reachability from 0 in G is equivalent to termination under H. Correct leaves alone do not establish the adapter; exhaustive differential checks test its wiring.

Scope remains partial for unmodified parsing/formatting/action details; no semantic AST or full application proof is claimed.

Hybrid amendment 2026-10-30

For n<=64 the original ordered cycle walks run unchanged. For n>64, ordered walks share a saturating 4*n step budget. A detected cycle returns the original diagnostic immediately. Completion returns Ok without BFS. Exhaustion discards partial reachability work and invokes the exact reverse-head BFS adapter over the whole input, preserving the least failing start even when exhaustion happened on an earlier rooted prefix. Prior input/head/root predicates are unchanged. Budget exhaustion is not an error and never implies a cycle.

Cost: tiny input work is bounded by 65n; larger prefixes perform at most 4n head steps before O(n) BFS. Thus worst-case cycle-phase time is O(n). Auxiliary space is constant for the walk-only branch and O(n) on fallback; converter's preexisting heads vector remains O(n). Saturation cannot increase work beyond the mathematical 4*n bound. Stars complete their walks without adjacency allocation. No universal throughput gain follows from this bound.

invariant

Harness invariant

Both implementations receive the same immutable fixture and exact Result values are compared. Annotation registry is initialized once in exhaustive comparisons. Base-(n+1) enumeration visits each head vector once including empty input; named malformed cases lie outside that enumeration. A copied old implementation can share legacy bugs, so these checks establish regression agreement rather than overall linguistic correctness. The ignored benchmark must run serially and checks output agreement before timing.

Hybrid amendment 2026-10-30

For n<=64 the original ordered cycle walks run unchanged. For n>64, ordered walks share a saturating 4*n step budget. A detected cycle returns the original diagnostic immediately. Completion returns Ok without BFS. Exhaustion discards partial reachability work and invokes the exact reverse-head BFS adapter over the whole input, preserving the least failing start even when exhaustion happened on an earlier rooted prefix. Prior input/head/root predicates are unchanged. Budget exhaustion is not an error and never implies a cycle.

Cost: tiny input work is bounded by 65n; larger prefixes perform at most 4n head steps before O(n) BFS. Thus worst-case cycle-phase time is O(n). Auxiliary space is constant for the walk-only branch and O(n) on fallback; converter's preexisting heads vector remains O(n). Saturation cannot increase work beyond the mathematical 4*n bound. Stars complete their walks without adjacency allocation. No universal throughput gain follows from this bound.

catalog

Typed obernants

behavior-complement

Let U consist of a candidate pair of gate implementations, the fixed fixture schedule, and tagged harness observations (normal assertion completion or assertion failure). The forward harness relation R reports completion exactly when every scheduled comparison and named expected-value assertion holds; C=U\R excludes reporting completion with a violated assertion or failure when all assertions hold, assuming successful fixture construction and allocation. This finite operational model does not exclude bugs outside the schedule.

reverse-reconstruction

Pre(completion) contains every candidate gate agreeing with the retained baseline on all enumerated inputs and the named expected values. It includes arbitrarily wrong behavior on untested inputs. Failure preimages retain every candidate whose first mismatching assertion produces the observed diagnostic. No candidate is uniquely reconstructed.

reachability-preimage

The fixture generator maps integer code in 0..(n+1)^n to a unique head vector by base-(n+1) digits. Its converse recovers that integer from the ordered digits. Empty n contributes one vector. This fixture relation is exact for n<=6; it does not recover lexical annotations from a gate result.

error-precedence

The explicit tail-first fixture distinguishes ascending first failure from the reverse-scan mutant. The metamorphic intervention changes production scan order while retaining fixtures and the old baseline. This models the effect of an implementation intervention, not an inverse proof.

representation-equivalence

Reordering independent fixture comparisons preserves whether all comparisons hold, but may change the first failure diagnostic. Fixtures and original inputs are borrowed by both gates; benchmark black_box does not certify optimization resistance beyond the executed compiler/runtime.

resource-refinement

Exhaustive fixture count is sum(n=0..6)(n+1)^n=126126. Baseline head chasing dominates long chains quadratically. The ignored benchmark constructs fixtures once and measures repeated full gate calls, excluding setup and registry construction. Passing functional checks supplies no timing result.

Hybrid amendment 2026-10-30

For n<=64 the original ordered cycle walks run unchanged. For n>64, ordered walks share a saturating 4*n step budget. A detected cycle returns the original diagnostic immediately. Completion returns Ok without BFS. Exhaustion discards partial reachability work and invokes the exact reverse-head BFS adapter over the whole input, preserving the least failing start even when exhaustion happened on an earlier rooted prefix. Prior input/head/root predicates are unchanged. Budget exhaustion is not an error and never implies a cycle.

Cost: tiny input work is bounded by 65n; larger prefixes perform at most 4n head steps before O(n) BFS. Thus worst-case cycle-phase time is O(n). Auxiliary space is constant for the walk-only branch and O(n) on fallback; converter's preexisting heads vector remains O(n). Saturation cannot increase work beyond the mathematical 4*n bound. Stars complete their walks without adjacency allocation. No universal throughput gain follows from this bound.

tests

Checks

2026-10-30: three transfer tests per consumer: exhaustive 126126 head maps (n=0..6), precedence fixtures and long chain/star/cycle-tail shapes (n=8,64,1024). Compare exact production Result to the retained old implementation. Debug and release execute twice; existing ann and convert unit tests execute twice. Source mutant reverses the final scan, causing the tail-first fixture to report word/token 4 instead of 1; reject the compiled mutant and restore source before passing the named test again. Evidence hashes are recorded after execution. Paired syntax JSON outputs must match byte-for-byte. These finite checks are not a proof for arbitrary inputs.

Manual benchmark only: cargo test -p annot --release bfs_transfer_benchmark -- --ignored --nocapture --test-threads=1, then equivalent -p en. It compares full gates on fixed synthetic chains/stars, with setup outside timing and black_box inputs/results. No model or corpus access. Timing remains deferred; no performance result is asserted.

Hybrid checks

A fourth active-fallback test per consumer covers the 64/65 threshold and a long rooted prefix exhausting the budget before a later cycle. Reverse-projection mutants run this test rather than the small precedence fixture, which now correctly takes the old-walk branch. Eight tests pass twice debug/release; original focused tests pass twice. The ignored benchmark uses 3 warmup pairs and 7 alternating-order samples at n=8,32,64,65,128,512,2048; setup is excluded. No timings run by this worker.

evidence

Evidence 2026-10-30

Six new tests pass twice in debug and release: each consumer exhausts 126126 head maps, checks exact precedence, and covers nine long-shape fixtures. Two manual benchmarks remain ignored and unmeasured. Existing converter tests: 14 pass twice; existing annotation tests: 1 passes twice. Normalized named test outcomes match across repeated runs (elapsed time and compiler output excluded). Each reverse-scan production mutant compiles, fails the tail-first assertion with exit 101 (4 versus 1), and restored source passes. Groupant validation reported valid=true and no diagnostics, with legacy missing coverage retained. No teacher/model/database/corpus/GPU actions.

Source and baseline hashes:

Runtime logs and original source snapshots remain outside the repository. Hashes identify the evidence, not an analytical proof. Larger safe follow-up candidates are all en library unit tests and annot ann/repair unit tests; model-dependent or live integration suites were not run.

Hybrid evidence 2026-10-30

Eight transfer tests pass twice in debug/release (four per consumer, plus two ignored manual benchmarks). The old exhaustive 126126 vectors per consumer exercise the small-input branch. New cases exercise 64/65 boundaries, rooted chains and stars through n=129, and a 129-word rooted prefix followed by a tail entering a cycle: the budget expires before the first failing token 100. Both compiled reverse-projection mutants are rejected on this active BFS branch (exit 101); restored tests pass. Existing 14 converter and one annotation tests pass twice. Normalized test names/outcomes match in both repetitions. No timing was executed for this amendment.

Current source/evidence hashes:

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/annot/src/ann.rs.groupant/checks.rs.groupant/