HermitCrab analysis: skip template partials whose required slot material is absent #561

A template partial in the HermitCrab analysis walk pays for every optional slot before it dies at a required slot whose material is absent from the word. The smallest trigger is a Mbugwe verb template such as anteriors ([REQ -iyɛ, opt 22 object markers, opt 1, REQ 22 subject prefixes, opt 1]) parsing a word with no iyɛ. The cost is that 63.8% of Mbugwe analysis events are template partials that never reach lexical lookup, so Try-a-Word and batch parses spend most of their steps on them.

Problem (census, steps)

Source: B2-analysis-census.md in the round inputs. Share of analysis events in template partials that never reach lookup (the ceiling): Mbugwe 63.8%, Sena 22.1%, Aweti 11.7%, conformance 3.5%, Amharic 0.1%, Indonesian 0. The rows S/anteriors/slot0/-iyɛ and S/relative anteriors/slot0/-iyɛ are 100% no-lookup, and T/tam1 is 94.5% no-lookup. AnalysisAffixTemplateRule.ApplySlots unapplies slots last to first and returns only after trying a required slot, so a partial dies at the first required slot with no rule that unapplies.

Proposed change

For a partial at walk index i, and each remaining required slot j (AffixTemplateSlot.Optional read live; an empty slot reads optional, see #542): the partial can only complete if some rule and allomorph of slot j has every inserted affix segment (the analysis pattern's top-level Constraint nodes) unifying with some Segment node of the current shape. If no allomorph of any rule in slot j passes, prune the partial. Check at template entry (Apply), after each successful slot unapplication (ApplySlots), and in ParallelApplySlots. The test for j runs only when every rule in slots j+1..i is pure. On prune, emit the same EndUnapplyTemplate(... false, FailureReason.None) that an existing partial death emits.

Treated as "may apply" (no prune): allomorphs with no inserted segment (null affixes), rule types other than affix process and realizational affix process, rules switched off by RuleSelector, constraints carrying symbolic (alpha) variables.

Soundness

Call a slot rule pure if, for every allomorph, every LHS part is captured by a CopyFromInput and none by ModifyFromInput. Then AnalysisMorphologicalTransform.GenerateShape only copies input nodes and Untruncate never inserts a segment. Unification matching can only narrow a copied node's feature structure, so if an inserted constraint unifies with no node now, it unifies with no node after any number of pure unapplications. The stratum's phonological rules were unapplied before the template battery, and inside one template walk only that template's slot rules run. Optional shape nodes count as present (sound over-approximation). No lexicon is consulted, so guessRoot, lexical patterns and partial entries (#551) do not affect soundness. Mbugwe's segment-restoring slot rules (n-1, n-2, ke-3, i-2, -y) are only in noun and *** templates, so the verb templates keep the check.

Memory bound

One array of feature-structure references per allomorph and one bool per slot, built in the constructor. Mbugwe: about 25 templates x 6 slots x 22 rules x a few allomorphs, well under 100 KB. Nothing per word, no cache.

Expected value

Presence is a weak test for one-segment affixes (Mbugwe -a, tense a-3; Sena R[a]; Aweti slots with null allomorphs), so the saving is well under the ceilings. Estimates, to be replaced by measurement: Mbugwe 15-35%, Sena 3-10%, Aweti 1-5%, others under 1%; stress fixture at least 50%. Template begin/end events (Mbugwe 12.3%) also drop. Under tracing it removes the same number of trace nodes, so it also reduces trace memory on Mbugwe-type words.

Cost of the check: constraint unifications, at most (required slots left) x (allomorph constraints) x (shape length) with short-circuit. They are counted and reported beside the savings, not netted (different unit).

Measurement plan

1. Implement behind an internal Morpher mode Off | Shadow | On (product default On). Shadow evaluates the predicate, never prunes, and reports fired, violated (a rule of a fired slot later unapplied under that partial) and completed-under-fired. Shadow plumbing in its own commit so a later PR can drop it.
2. Per-grammar steps in census mode (traced, unmerged, sequential) and censusmerge mode on conformance, Indonesian (all 70), Aweti (stride 2), Amharic (limit 28), Mbugwe (stride 40) and Sena (stride 100). Words aborted in either arm are dropped from both and listed.
3. Stress fixture "Bantu TAM position classes": one unordered stratum, 12 verb templates of 5-6 slots, distinct multi-segment required markers, a 20-rule optional object-marker slot, a 15-rule required subject slot, 30 roots, 60 words (half lacking the rarer markers).
4. Gates: HermitCrab tests on branch and master, conformance verdicts identical, parses identical, dotnet csharpier check ., comment hygiene.

Kill criterion

Any shadow violation (a template completion under a fired check) is a soundness bug: stop. Close if the shadow saving is under 5% of analysis events on every one of Mbugwe, Sena and Aweti and under 25% on the stress fixture. Also close if check unifications exceed 3x the events saved on the grammar with the largest saving (the archived row-22 edge prefilter measured about 2.9 arc checks per pattern attempt on Sena).

Overlaps and dependencies

• Not ledger row 10/27 (no lexicon consulted), not Filter final templates in analysis #491 final-template pruning (blocks templates by final state), not row 22 (cheaper attempts; this removes whole partial subtrees), not E3.
• Overlaps PR perf(hermitcrab): share trailing analysis template slot batches #546 (shares trailing slot batches in untraced sequential walks; inert under tracing). This issue targets both walks. The composition is measured in HermitCrab analysis: measure required-slot look-ahead on the #546 shared walk #566, which depends on this issue and on perf(hermitcrab): share trailing analysis template slot batches #546. The ordered and anchored v2 is HermitCrab analysis: ordered and anchored required-slot look-ahead (v2) #567, which depends on this issue.
• Related: Analysis search is nogood-dominated on a template-heavy Bantu grammar; memoization yields ~6%, and the HasReachableRoot prune is absent from all refs #485 (nogood-dominated search on a template-heavy Bantu grammar; asks for a reduce-the-search lever), PR Trace HermitCrab failure reasons and template slot outcomes #534 (trace nodes and failure reasons; the pruned partial keeps the existing end event).

Related

• PR HermitCrab optimization round record: what was tried, and a faster package that is not mergeable #490: HermitCrab optimization round record (ledger rows cited above are in it).
• PR Add a conformance suite for HermitCrab, with its adequacy argument #480: HermitCrab conformance suite. Conformance per-fixture verdicts must be identical with and without the change.
• Units: deterministic analysis events and synthesis steps, never ms. "% less work" = (off - on) / off per grammar, never pooled. Census figures are ceilings unless stated. Ranges marked "est." are estimates that the shadow phase replaces with measurements.
• Owner constraint: no memo or cache; any new structure must be grammar-sized and at most a few MB.

🤖 Generated with Claude Code