Repository navigation
HermitCrab: copy-agreement prune keeps matches with an empty copy, re-running the whole search #634
Description
The copy-agreement prune from #519 keeps a match in which one copy of a part is non-empty and another copy of the same part is empty, so every word gets a spurious whole-word candidate at each point of the unapplication search, and the whole remaining search runs again under it. Parses are unchanged; synthesis rejects the candidate. This is an efficiency defect, not a correctness one.
This is the shape FieldWorks exports for full reduplication, X => X X: a single zero-or-more variable part (minimum 0) copied twice. When the capture of the first copy is the whole word, the second capture is empty. An empty group becomes Range.Null, GroupCapture.Success is false, TryGetSegmentCopies returns false, and HasDisagreeingCopies does not report a disagreement, so the match is kept.
Measured on a synthetic grammar (39 non-reduplicated words, prune on):
| C# trace count | no reduplication rule | rule with min 1 | rule with min 0 |
|---|---|---|---|
| rule unapplications | 40 | 40 | 172 |
| lexical lookups | 79 | 79 | 211 |
| word syntheses | 43 | 43 | 128 |
Treating an empty capture as a zero-length copy returns all three counts to the no-rule baseline, and the six reduplication probe words parse identically. A real-grammar port of the same behaviour (PanGloss) pays about +84% parser work on a 4,279-word set from the same cause.
Proposed fix: in TryGetSegmentCopies, treat !capture.Success as a zero-length copy rather than "undecidable". Soundness: synthesis writes every copy from one input, so a non-empty copy cannot equal an empty one, unless the non-empty copy consists only of optional segments (the existing alignment already lets such a copy line up with nothing). Refuse the match otherwise.
Secondary point: every one of the n-1 splits of a shape is still enumerated before the Acceptable predicate runs, so the cost is quadratic in word length even when nothing leaks.
Next: a fix PR against this issue with a trace-count regression test; the PanGloss side is tracked separately and will link here.
Where it happens (source)
AnalysisMorphologicalTransform.cs:91-93:TryGetSegmentCopiesreturns false when!capture.Success;HasDisagreeingCopies(:69-72) then does not report disagreement, so the match is kept.Matcher.cs:184-195:CreatePatternMatchturns an empty group range intoRange.Null.GroupCapture.cs:15:SuccessisRange != Range.Null.- FieldWorks side:
HCLoader.cs:1389-1394maps a phonological variable input part tonew Pattern(i, AnyStar());AnyStar(HCLoader.cs:2356-2359) is a quantifier with minimum 0 and no maximum. A repro with minimum 1 hides the leak. - The enumeration of all n-1 splits:
AllSubmatches(Matcher.cs:313);Acceptableruns only at an accepting state (TraversalMethodBase.cs:166), after the whole path was walked.
Repro (synthetic grammar and words)
Master at 74ee09b (3.9.6, contains #519), prune on (the default, Morpher.cs:60). Load a HermitCrabInput XML grammar with the XML language loader, parse the word list with a trace attached, and count rule unapplications, lexical lookups and word syntheses.
Grammar: one stratum, one part of speech V, ten segments p t k s m n l a i u each with a unique place value (so nothing unifies by accident), natural classes Any (no constraints), C (cons +), V (voc +). Fourteen stems, all V: salum patik nusak tilam sakin munat kalip patikus nusakil tilamas sakinun patikusal nusakilun tilamasip; only patik and salum carry the rule feature REDSYN. Two plain suffix rules (-an, -un) with input (Any){1,-1}, copy then insert the suffix. The reduplication rule:
<MorphologicalRule id="mrRedup" requiredPartsOfSpeech="posV" outputPartOfSpeech="posV"><Name>redup</Name>
<MorphologicalSubrules><MorphologicalSubrule id="mrRedups">
<MorphologicalInput requiredMPRFeatures="mprRedsyn">
<PhoneticSequence id="rp"><OptionalSegmentSequence min="0" max="-1"><SimpleContext naturalClass="ncAny"/></OptionalSegmentSequence></PhoneticSequence>
</MorphologicalInput>
<MorphologicalOutput><CopyFromInput index="rp"/><CopyFromInput index="rp"/></MorphologicalOutput>
</MorphologicalSubrule></MorphologicalSubrules><MorphemeId>REDUP</MorphemeId></MorphologicalRule>Change min="0" to min="1" to see the control row. Words (45):
salum patik nusak tilam sakin munat kalip patikus nusakil tilamas sakinun patikusal nusakilun tilamasip
saluman patikan nusakan tilaman sakinan munatan kalipan patikusan nusakilan tilamasan sakinunan patikusalan nusakilunan tilamasipan
kalipanun patikusanun nusakilanun tilamasanun sakinunanun patikusalanun nusakilunanun tilamasipanun salumanun patikanun nusakanun
patikpatik patikpatikan nusaknusak salumsalm salumsalum salumsalumanun
The first 39 are non-reduplicated (the trace counts above); the last six are reduplication probes. Expected for patik: zero reduplication-rule unapplications (a non-empty copy cannot equal an empty one). Observed: one, and the full remaining search runs under it.
Method and limits
Tracing disables MergeEquivalentAnalyses (AnalysisStratumRule.cs:131), so trace counts are comparable only within one table. The fix was tried in a scratch copy only: with it, the six probes parse identically (1,1,0,0,1,1), and with an additional deletion rule also identically (1,1,0,1,0,0). Elapsed time per pass of the word list went 129.6 to 106.8 ms (noisy, loaded machine; the remaining gap is the split enumeration). The scratch change was not run against the SIL.Machine test suite or the conformance suite. No existing issue or comment in this repository covers the empty-copy case (searched #519, #599 to #611).
Activity
johnml1135 commentedon Nov 11, 2026
PanGloss side, with the optional-segment leak that is specific to it: sillsdev/PanGloss#235.
johnml1135 commentedon Nov 13, 2026
Fix PR opened as a draft: #645 (closes this issue). Treats an empty capture as a zero-length copy; words holding optional nodes stay undecidable. HermitCrab test project: 185 passed. PanGloss reference: sillsdev/PanGloss#247.