HermitCrab: one partial rule switches off the final-template prune for the whole grammar; Mbugwe chaanjiyɛ never finishes

Offen
  • Stimmt etwas nicht?
#643 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

@johnml1135 arbeitet bereits daran.

Seit 12.11.2026.

  • #644 von @johnml1135 — offen

Bewertung

Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Anfängerfreundlichkeit
25/100
Issue-Typ
Bug
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
csharp
Bereich
backend

Rechercherichtung

Start by reading the shared analysis and template-pruning logic around Morpher.HasPartialRules, ApplyTemplates, and AnalysisAffixTemplateRule.ParallelApplySlots; the issue does not name source files or tests. The proposed fix needs load-time reachability and run-time tracking of owed partial rules, with equality and merge-key changes. Use the cited 28 adversarial grammars and 361 words as the validation target; done means zero changed analyses and reduced search work on Mbugwe, Sena, and Aweti.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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:

  1. R is partial. Fix: unapplying a partial rule leaves the analysis state at None.
  2. 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

Vorherrschende Sprache
C#
Sterne
29
Forks
16
Ø Merge
4 T. 11 Std.
Gemergte PRs (30 T.)
14

Entwicklungsumgebung

  • Kein Dockerfile und keine Docker-Compose-Datei
  • Hat eine Pull-Request-Vorlage
  • Kein Beitragsleitfaden

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus sillsdev/machine

Alle Issues in sillsdev/machine

Ähnliche Issues

Weitere Issues zu C#

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.