Repository navigation
HermitCrab: one partial rule switches off the final-template prune for the whole grammar; Mbugwe chaanjiyɛ never finishes #643
Description
Start here: one partial rule switches the final-template prune off for the whole grammar, and Mbugwe chaanjiyɛ then never finishes. It is not an infinite loop. It is a finite search that the merged #491 prune would cut, 26 times larger than needed.
Morpher.HasPartialRules is true when any non-LexEntry morpheme is partial. Mbugwe has one (o-5, 3SG.SP, partial="true"). While it is true, analysis never refuses to unapply a final template after a non-template rule. It explores final template <- derivational rule <- final template <- derivational rule <- template stacks that synthesis rejects unless a partial rule is involved. Nothing in hc.dll bounds that: MaxAlternatives is off by default, MaxApplicationCount bounds depth not breadth, MaxStemCount covers compounding only. With the prune on, chaanjiyɛ parses in 77.5 s on one core, 336 MB, one analysis (7.SP believe ANT). Unpatched it passes 29.5 M rule calls and 2.7 GB in 5.5 min and is still growing. PanGloss has the same guard and the same blow-up (26.3x the work), so the cause is in the shared algorithm.
The guard can be much narrower and stay result-identical. A word is partial at a final template only if a partial rule applied earlier, and a partial rule leaves no obligation behind. So prune a final template that no partial word can reach (computed at load), and for the rest record that the analysis owes a partial rule and drop it once its shape shows none can still be unapplied. Measured on the reference grammars: zero changed analyses, Mbugwe 76 % less work, Sena 60 %, Aweti 68 %.
Next: PR to follow, with the proof, the adversarial grammars and a conformance-suite PR. #607 holds the remaining Mbugwe cost, which is not partial-related.
Related: #606 (86 Mbugwe words at the step cap, causes not examined; this is a cause for some), #590 (rejected for zero effect under the grammar-wide guard), #553 and #551 (narrowed the guard from any partial morpheme to any partial rule), #491 (the prune).
Evidence: the hang
Mbugwe chaanjiyɛ, master plus the conformance runner, one core, counting rule-selector calls.
| setting | rule calls | analyses (+alternatives) | template depth | analysis time | peak |
|---|---|---|---|---|---|
| default | > 29.5 M, unfinished | > 272 k | 2 | > 5.5 min | 2.7 GB and rising |
AlwaysEnforceFinalTemplates |
416 k | 4,623 (10,532) | 1 | 18.6 s | 332 MB |
o-5 not partial |
416 k | 4,623 (10,532) | 1 | 17.7 s | 335 MB |
The two pruned runs are identical, so the single partial rule is the trigger. Stack samples were all in analysis, nested ApplyTemplates -> ApplyMorphologicalRules -> ApplyTemplates -> ... -> AnalysisAffixTemplateRule.ParallelApplySlots: a final template inside a derivation. Memory grew about 7 MB/s with no plateau.
PanGloss 0.16.2, one thread: prune on 50.8 M steps in 6.8 s; default 1,334,644,618 steps in 325 s, same single analysis.
FieldWorks maps MakePartialsFinal to AlwaysEnforceFinalTemplates, default false, so FieldWorks users hit this too. MakePartialsFinal is not a fix: it changes results for words that need a partial-rule rescue (fixtures final-template-partial-discriminators, final-template-partial-trace, morphotactic-attribute-breadth).
Why the narrower guard is sound
Synthesis refuses a non-template, non-clitic rule R after a final template unless input.IsPartial || R.IsPartial. So a pruned analysis path is a synthesis derivation that is refused unless:
- R is partial. Fix: unapplying a partial rule leaves the analysis state at
None. - The word is partial when the template applies. A partial root takes no template, so a partial affix rule must have applied before the template, in its stratum or an earlier one.
Case 2 gives two exact conditions. Load time: a final template is prunable when no partial word can reach it (the closure of the part-of-speech set a partial rule can leave, over every rule of the stratum, carried across strata). Run time: when a final template is unapplied right after a non-template rule, the analysis owes a partial rule below it. The owed flag is part of Word equality, hash and AnalysisMergeKey. An analysis that still owes a partial rule at lexical lookup is dropped. It is dropped earlier when its shape shows that no partial rule can still be unapplied: every rule of the stratum uses only copy and insert-segments actions, so every later shape is made of clones of current nodes plus nodes rebuilt from deleted or possibly empty parts, and each segment a partial rule inserts must unify with one of them.
Evidence: 28 adversarial grammars, 361 words, zero lost or changed analyses; two deliberately wrong look-ahead variants each lose exactly the predicted parses.
Caveat: lexical families
CheckBlocking and ChooseInflectionalStem return a fresh Word for a family member that drops the pending rule list. In a grammar with lexical families, the existing #491 prune can drop a duplicate analysis (same morphemes and shape) that the unpruned search finds through that replacement. No distinct analysis was lost in the search. FieldWorks never writes Family, so no FieldWorks grammar is affected; hand-written grammars with families are. The narrowing does not change this. It will be stated in the PR.
Not pursued (measured)
Root gate (sound under two grammar conditions, 3-6 % of allocation on Mbugwe, offered for #607), skipping repeated analysis states (unsound as a plain skip; the sound form is the cascade memo #522 removed), a non-final-template-last check (unsound as stated, at most 0.2 % of work), finer static reachability (Mbugwe is already exact).
🤖 Generated with Claude Code
Activity