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

未關閉
  • 哪裡不對？
#643 0 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

@johnml1135 已經在處理了。

開始於 2026年11月12日。

  • #644 來自 @johnml1135 —— 未關閉

評估

難度
5/5
預估耗時
一週以上
新手友好度
25/100
Issue 類型
缺陷
描述清晰度
描述清楚
活躍度
活躍
技術堆疊
csharp
領域
backend

研究方向

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.

由索引模型根據 Issue 內容生成。

描述

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

主要語言
C#
星號
29
分支
16
平均合併
4 天 11 小時
30 天內合併 PR
14

環境準備

  • 沒有 Dockerfile 或 Docker Compose 檔案
  • 有 Pull Request 範本
  • 沒有貢獻指南

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

sillsdev/machine 的其他 Issue

查看 sillsdev/machine 的全部 Issue

相似的 Issue

更多 C# Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。