core: automata engine #14
Loading…
Reference in a new issue
No description provided.
Delete branch "core"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Closes #12. Resolves #5 (ε encoding).
What changed
Fulfills the
[friend] corebrief in docs/TASKS.md.rgxr-corestays pure: no IO, and its only dependencies are stillserde+thiserror. The types and serde attributes are unchanged; the wire format is byte-stable.run— ε-closed active set per step, step 0symbol: nullto_dfa— subset construction from the initial closure; only reachable subsets are builtminimize— Hopcroft partition refinement after dropping unreachable statesunion/intersection(n-ary),difference— reachable product of ε-free, completed operandsconcatenation— disjoint union, with ε from each operand's accepting states to the next initial statecomplement— flips accepting states on a total DFAregex_to_nfa— recursive-descent parser (no regex crate) + Thompson constructionfa_to_regex— state elimination with fresh start/accept nodes and a simplifying AST; output re-parsesModules:
nfa(closure, naming, ε-removal, completion),run,dfa,ops,regex.docs/CONTRACT.mdandopenapi.yamldocument ε and the naming table.Gates
Acceptance tests (
crates/rgxr-core/tests/acceptance.rs)Black-box, public API only. The oracles are independent of engine code: a separate set simulator, brute-force string enumeration up to length 6–8, Moore table-filling, and a seeded xorshift generator for random automata.
a*bexample:runon "ab", "aab", "b", "", with the exact trace JSON including"symbol":null(a|b)*abb→to_dfa→minimize: 4 states, matchesends_with("abb")on every string up to length 8fa_to_regex(regex_to_nfa(r))≡rover a 24-regex battery (edge cases, escapes, Unicode) and on 150 random ε-NFAsto_dfagolden; all constructions byte-identical across runs; serde round-trip byte-identicalNotADeterministicFacontaining "run to_dfa first"; existingvalidate()rejections unchangedSemantic decisions
""(#5). It is never inalphabet.validate()accepts it as a transition key and rejects""insidealphabet(new rejection,FaError::Other). Any ε-transition makes the Fa nondeterministic.runempty the active set: the input is rejected, but no error is returned.invalid_fawhen alphabets differ, asopenapi.yamlstates.concatenationmerges alphabets instead (no rule for it in openapi).∅first. That makes union on NFAs correct, and union/intersection/difference of DFAs return DFAs.difference(a, b)=a ∩ complement(to_dfa(b)).q0,q1with∅for the empty subset; products(s1,…,sn); concatenation keeps original names (#kon collision); minimize names each class after its smallest member, so minimizing an already-minimal DFA returns it unchanged;#ksuffixes for every collision.regex_to_nfanames statesq0…qnby BFS rank. This deviates from the brief's literal "neverq{counter}" rule. Thompson states have no semantic content, and BFS rank over a deterministic graph depends only on the regex, so names stay stable across runs, which is what the rule protects. Recorded in CONTRACT.md.a**is valid: postfix operators stack,a**≡a*, anda*+?parses."",(),a|and|all parse.FaError::Regex(→invalid_regex) naming a 1-based position: unclosed(, unmatched), nothing to repeat, dangling\.fa_to_regex→FaError::Other(→invalid_fa), because the syntax has no ∅. An ε-only language prints as the empty string.fa_to_regexreadability: elimination runs on the ε-free automaton and, for inputs of 16 states or fewer, also onminimize(to_dfa(fa)). The shorter result wins, with ties going to ε-free. Elimination order is fewest new edges first, ties broken by state-name order. The simplifier folds ∅/ε identities,r r* → r+,r* r* → r*,ε|r+ → r*, absorption (r*absorbsrandr+), and nullable?.fa_to_regexignores them, becauseruncan never consume them.Follow-ups (other owners)
crates/rgxr-api/src/engine.rswith the commented one-line call sites (issue opened separately)""edges asε""symbol) as ε #16caaa6837a3b53fd97c15status: rebased on master (render + web merged) and review fix pushed (
cfd914b).Independent review (fuzzed 3000 random NFA pairs with hostile state names like
a,b,∅and(a,b), plus 695 random regex round trips): no wrong languages, no panics, no merged states, and Hopcroft refinement is correct. Every simplifier rewrite was checked by hand and preserves the language. One confirmed bug, now fixed:fa_to_regexgrew exponentially on ε-heavy NFAs.((a|b)*|())+exhausted memory, and(()())*(|())*(()|b()*)*produced a 475k-char regex forb*. Fix: eliminate on the minimal DFA first (subset construction capped at 512 states), then on the ε-free automaton, each under a 4096-node budget per edge. These inputs now produce(a|b)*andb*exactly; they are a regression test now.FaError::Other→ 400invalid_fa("too large to build") instead of exhausting memory. Recorded in CONTRACT.md.Gates on
cfd914b: fmt clean · clippy 0 warnings ·cargo test --workspace90 passed (api 40, core 11 + 27, render 12).CI: "Set up job" fails on runner egress to
code.forgejo.org(infra; see !11 → runner-image work).docs-html/is not regenerated in this PR: tern's TUI does not run in a headless sandbox. Needs onenix develop path:. --command ternfrom a real terminal.cfd914bcc1d21a0348a5