perf(codegen): eliminate provably duplicate or subsumed pure parser alternatives

[tinovyatkin]

Context

Follow-up to #125 and blocked by #128.

Atfinity reported a 2% win after removing a parenthesized-expression alternative because another subrule already recognized the same form. The grammar-specific conclusion does not generalize directly: language inclusion/equivalence for arbitrary recursive context-free rules is not a safe heuristic, and two alternatives that accept the same tokens can still differ in parse-tree nodes, labels, actions, first-alternative bias, and recovery.

There is nevertheless a useful conservative subset: exact duplicate alternatives and alternatives whose token language is provably contained in an earlier pure alternative after bounded expansion of acyclic helper rules.

Examples of candidate shapes are:

r : A | A ;

r : LPAREN expression RPAREN | grouped ;
grouped : LPAREN expression RPAREN ;

The second form is removable only if expansion is finite and pure, ANTLR's earlier-alternative selection makes the later branch unreachable for every matching input, and the selected safety class permits any affected rule-node/API difference.

Goal

Add a grammar-agnostic pass that removes only parser alternatives for which duplication or subsumption is proven within a deliberately bounded structural fragment.

Do not attempt general CFG equivalence and do not use a sample corpus as the proof of language inclusion.

Proof boundary

The initial proof engine should be limited to combinations it can normalize exactly, such as:

• literals, token references, finite token sets/ranges, grouped alternatives, and bounded EBNF forms with exact structural comparison;
• calls to pure, acyclic parser rules that can be expanded under strict depth/node limits;
• exact duplicate sequences after normalization;
• containment where every normalized path of the candidate is covered by an earlier alternative without relying on predicates, action results, recovery, or semantic intent.

It must fail closed for:

• direct or indirect recursion, including left recursion;
• semantic predicates, actions, arguments/returns/locals, labels with distinct generated contexts, exception/finally clauses, or target-specific constructs;
• wildcard/not-set cases whose vocabulary boundary is not represented exactly;
• nullable cycles or unbounded expansion;
• alternatives where ordering, associativity, precedence, nongreedy behavior, or lexer priority is relevant;
• any proof that depends only on observed fixtures rather than the grammar model.

Lexer alternatives are out of scope because rule/alternative order and longest-match priority are observable tokenization semantics.

Rewrite behavior

• Preserve the first viable alternative and remove only a later proven duplicate/subset, matching ANTLR's ordered ambiguity resolution for the supported pure subset.
• Record the proof trace in codegen: complete the opt-in grammar optimization pipeline #128's optimization manifest: normalized candidate, covering alternative(s), expanded helper rules, bounds used, and affected labels/rule contexts.
• Classify exact unreachable duplicate removal separately from recognition-only nested-rule elimination. Do not claim tree/API preservation when a context/listener surface can change.
• Leave source formatting outside the removed span untouched.
• Make the pass deterministic and idempotent.
• Require a structural/runtime cost gate. ANTLR may already collapse or cheaply resolve a duplicate; skip rewrites that do not reduce ATN/generated decision cost or generated-Rust performance.

Correctness and performance gates

• Differential tests must cover every removed path, nearby non-covered paths, ambiguous prefixes, invalid tokens, missing delimiters, and recovery before/inside/after the decision.
• Compare accepted language, consumed input, first-alternative selection, syntax errors/recovery, and parse-tree/context/listener behavior according to the declared safety class.
• Add negative tests for recursive equivalence, semantic guards, distinct labels/actions, nullable cycles, precedence rules, and lexer alternatives; all must be declined.
• Run the full runtime testsuite with zero skipped cases.
• Benchmark generated Rust across multiple grammar families and publish generated size, packed ATN size, ATN states/decisions, adaptive-decision count, parse time, and peak memory.

Acceptance criteria

• Exact later duplicate pure parser alternatives can be detected and removed.
• Bounded acyclic helper expansion can prove a later alternative is structurally subsumed by an earlier one.
• The proof engine fails closed outside its documented finite fragment.
• First-alternative ordering is preserved.
• The manifest contains an auditable proof trace, safety class, and affected API/tree surfaces.
• Recursive, semantic, labeled, nullable-cycle, precedence, wildcard-uncertain, and lexer cases are skipped with reasons.
• The pass is opt-in, deterministic, idempotent, and cost gated.
• Differential valid/invalid-input tests and the zero-skip runtime testsuite pass.
• Multi-grammar Rust benchmarks demonstrate a material win for the enabled class without protected-grammar regression.

Non-goals

• General context-free-language equivalence or inclusion.
• Removing a syntactic form because a finite test corpus happened not to distinguish it.
• Changing which ambiguous alternative wins.
• Treating Atfinity's parenthesized-expression case as universally redundant.