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 摘要。