Environment matchers pay for captures they never read; key the traversal on what the caller consumes

Summary

Phonological-rule environment matching pays for capture bookkeeping it never reads. Making that explicit would let the traversal collapse redundant paths soundly, including for the alpha-variable grammars that PR #511's approach cannot safely cover.

What the callers actually need

RewriteRuleSpec.MatchSubrule reads exactly two things from an environment match (src/SIL.Machine.Morphology.HermitCrab/PhonologicalRules/RewriteRuleSpec.cs:83-107):

Match<Word, ShapeNode> leftEnvMatch = subruleSpec.LeftEnvironmentMatcher?.Match(match.Input, leftNode, varBindings);
if (leftEnvMatch == null || leftEnvMatch.Success)
{
    if (leftEnvMatch != null && leftEnvMatch.VariableBindings != null)
        varBindings = leftEnvMatch.VariableBindings;
    ...

Success, and the resulting VariableBindings. It never reads .Range and never reads a group. AllomorphEnvironment.IsMatch (AllomorphEnvironment.cs:90-93) needs even less — a boolean.

Why that matters

The cost driver in FSA traversal is TraversalMethodBase.Advance (src/SIL.Machine/FiniteState/TraversalMethodBase.cs:275-292), which forks an instance for every Optional annotation at the next offset. Instance count grows exponentially in the number of optional annotations and is independent of the FSA's state count — measured on a synthetic 2-state FSA: 20 optional annotations produced 2,097,150 instances popped.

Those forked instances differ only in their registers, which for an environment matcher are write-only. The existing dedup key in NondeterministicFsaTraversalMethod includes the registers, so it cannot collapse them.

Proposal

Make "captures not needed" a property of the matcher rather than inferring it from how many matches the caller wants:

1. Add a MatcherSettings flag (e.g. CapturesNotNeeded), or derive it from the compiled Fst having no groups beyond *entire*.
2. When set, let the FSA traversal methods skip any instance whose key was already pushed, where the key is (State, AnnotationIndex, VariableBindings) — reducing to (State, AnnotationIndex) when Fst.IgnoreVariables is true.
3. Set the flag on the rewrite-rule environment matchers (RewriteSubruleSpec.cs:21-32) and on AllomorphEnvironment.

Bindings must stay in the key because they filter: CheckInputMatch unifies against them, so two instances at the same state and position with different bindings are not interchangeable. Registers may leave the key precisely because these callers never read them.

Relationship to existing work

PR #511 proposes the same collapse but keys on (State, AnnotationIndex) alone and gates it on allMatches == false. A 20,000-case differential fuzz found 112 cases where that changes Match() results — 108 from ignored variable bindings, 4 from dropped/short capture ranges (see the discussion on that PR). Keying on what the caller actually consumes avoids both classes.

PR #490's rejected two-pass nondeterministic traversal merged on state + position + bindings and then rebuilt captures, and was measured negative largely on that rebuild cost (2.3x traversal instances, 27% more word clones). For environment matchers there is nothing to rebuild, so that objection does not apply here.

Open questions

• VariableBindings needs a usable equality/hash for the key; if adding one is expensive it could eat the win, and a cheaper canonical form may be needed.
• How much total parse time environment matching accounts for on alpha-variable grammars (Amharic, Mbugwe, Indonesian all use AlphaVariable; Sena and Aweti do not) has not been measured. That census should come before the implementation is tuned.

Suggested gates

Conformance fixtures unchanged; the differential fuzz at zero divergences; SIL.Machine.Tests and SIL.Machine.Morphology.HermitCrab.Tests green; and a microbenchmark showing the optional-annotation bound now applies to variable-bearing patterns.

Read RewriteRuleSpec.cs and AllomorphEnvironment.cs to confirm which match results callers consume, then trace Advance in TraversalMethodBase.cs and the keying in NondeterministicFsaTraversalMethod. Review RewriteSubruleSpec.cs and existing tests before deciding how bindings are compared. Done means zero differential-fuzz divergences, unchanged conformance fixtures, green SIL.Machine.Tests and SIL.Machine.Morphology.HermitCrab.Tests, and a benchmark validating the intended bound.