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

Ouverte
  • Quelque chose ne va pas ?
#643 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

@johnml1135 y travaille déjà.

Depuis le 12/11/2026.

  • #644 par @johnml1135 — ouverte

Évaluation

Difficulté
5/5
Temps estimé
Plus d'une semaine
Accessibilité débutants
25/100
Type d'issue
Bug
Clarté
Clairement spécifiée
Activité
Active
Stack technique
csharp
Domaine
backend

Piste de recherche

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.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

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:

  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

Langage dominant
C#
Étoiles
29
Forks
16
Merge moyen
4 j 11 h
PR mergées (30 j)
14

Préparer son environnement

  • Aucun Dockerfile ni fichier Docker Compose
  • Propose un modèle de pull request
  • Aucun guide de contribution

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de sillsdev/machine

Toutes les issues de sillsdev/machine

Issues similaires

Plus d'issues C#

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.