algorithm-aho-corasick-tests

The groupant beside algorithms/src/aho_corasick/tests.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

component	label	where
approximant	bounded checked	Forward
ast	partial	`syntax.json`
cost	symbolic unmeasured	Cost
descriptant	present	descriptant
invariant	source derived	Invariant
tests	bounded executed	evidence

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.

id	type	label	where
`nonbehavior`	behavior_complement	partial source derived	nonbehavior
`preimages`	reverse_reconstruction	partial source derived	preimages
`oracle-agreement`	correspondence_relation	partial source derived	oracle-agreement
`premise-boundary`	metamorphic_relation	partial source derived	premise-boundary
`mutation-detection`	distinguishability_relation	partial source derived	mutation-detection

Model text

descriptant

aho_corasick tests.rs epoch memory

2026-10-30. Original std-only code, no copied source. Prospective model preceded code in mod.rs.groupant/prospective.md. Classical citations appear in implementation documentation; variant complexity is explicit.

Four tests: 225 ordered pattern pairs, each with duplicate first pattern, across 127 binary texts (28,575 oracle comparisons); full byte range; failure-output/empty/duplicate boundaries; injective relabel and ID permutation; five compatible predecessors and prefix extension. Compiled production mutant removing inherited outputs fails boundaries_failure_outputs_and_duplicates.

The combiner relates authoritative source and its SHA-256, partial syntax, forward relation, typed obernants, invariant, cost and finite evidence. Models preserve ambiguity in compatible predecessors. Missing semantic AST analysis, universal proof, allocator exhaustion and downstream composition remain explicit. Exact production algorithms need no fabricated executable approximation. Any future approximate profile must honor supported 1%, 2%, 5%, 10% caps and bind source and evidence.

2026-11-01: Reviewed the test oracle's ordered observation. Removed suffix-array material accidentally included in this Aho test model. Equal match multisets do not imply equal vectors: reversing IDs at a shared boundary is rejected. The compiled inherited-output mutant is historical evidence, not an operation performed by the tests themselves.

model

aho_corasick tests.rs model

Forward

Run deterministic independent byte oracles, boundary cases, transformation laws and compatible-output fibers; assert exact values and explicit false-premise counterexamples. Passing finite checks does not establish universal correctness.

Invariant

Oracle logic does not use production failure links. All fixtures are deterministic; comparisons include output order, offsets and multiplicity. Historical external mutation evidence is separate from the tests.

Cost

Bounded exhaustive fixture enumeration; the oracle scans each pattern at each boundary and compares the corresponding byte window. Test cost is intentionally independent of production claims.

nonbehavior

Type: behavior_complement. Domain: Finite deterministic fixtures and test executions; no arbitrary programs or hidden production state.

Exclude acceptance when an asserted production output differs from the independent oracle, a stated conditional law fails under its premises, or a compatible-output fiber differs from direct constraints. Unvisited inputs are outside this finite acceptance claim.