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

[johnml1135]

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.

[johnml1135]

Measured this before building it, and the numbers say don't. Recommend closing.

Environment matchers are a rounding error

I added caller attribution to FSA traversal (a ProbeLabel on the compiled Fst, set at each Matcher construction site) and counted instances by category over the first 10 words of each grammar:

grammar	env-matcher share of traversal instances	ceiling if all env-matcher redundancy were removed
Amharic (80 AlphaVariable)	0.20%	0.12% of total pushes
Mbugwe (24 AlphaVariables)	1.18%	0.004%
Aweti (no variables, contrast)	0.002%	~0

Amharic's left-environment matcher does collapse 83% of its own pushes — but its own pushes are 0.14% of the total. The proposal would touch four hot traversal loops to buy about a tenth of a percent.

One useful negative from the same run: keeping VariableBindings in the key costs nothing. collapsedWithBindings == collapsed on every row of both grammars, with a distinct-signature counter confirming the signature function discriminates (33 distinct signatures on Mbugwe's target matcher), so the equality/hash concern raised above is moot.

Where the redundancy looked like it was, and why that is also dead

The unlabelled remainder held nearly all the volume and all the apparent opportunity: on Amharic, 2,801,478 of 2,808,088 pushes with 93.95% collapsible under a (State, AnnotationIndex) key; Mbugwe 14.44%. Labelling the remaining construction sites showed that entire figure is exactly two matchers — AnalysisAffixProcessRule and AnalysisCompoundingRule — with RootAllomorphTrie's lookup FST contributing 0% collapse despite ~62k pushes (a prefix trie is already maximally state-shared, so there is nothing left to collapse at runtime).

Both of those matchers are built with AllSubmatches = true and call AllMatches precisely to enumerate every distinct morph-boundary placement. So the "collapse" is alternate boundary placements, not duplicates. Comparing registers at each would-be collapse:

	collapses with identical registers	with differing registers
Amharic analysis-affix	7,446 (0.29%)	2,573,312 (99.71%)
Amharic analysis-compound	16 (0.03%)	50,920 (99.97%)
Mbugwe analysis-affix	3,022 (5.49%)	52,056 (94.51%)
Mbugwe analysis-compound	1,886 (2.93%)	62,396 (97.07%)

The genuinely free slice is 0.28% of collapses on Amharic and 4.11% on Mbugwe — at most 0.6% of total traversal instances on either grammar, and only reachable by adding a per-instance register-equality guard.

Note the labelled totals reconcile exactly against the earlier unlabelled run (2,808,088 total; 2,801,478 in the remainder; 2,631,694 collapses), so this is the same population counted two ways.

Conclusion

Real volume, real-looking collapse percentage, no sound win underneath it. The same shape as PR #511: the redundancy that a (State, AnnotationIndex) key finds is overwhelmingly alternate captures, which is exactly what makes dropping it unsafe. Closing unless someone has a grammar or word class where these ratios look different.

🤖 Analysis performed with Claude Code