Fix a performance bug in NarrowAnalysisRewriteRuleSpec

[jtmaxwell3]

Quick summary

This fixes a performance bug in Unapply in NarrowRewriteRuleSpec. This fix speeds up parsing with the Amharic grammar, from taking 45 minutes to parse 36 words to taking 45 seconds to parse 654 words.

The performance problem comes from phonological rules of the form a b -> c. Amharic uses Fidel characters, which mix consonants and vowels. But internally it sometimes uses separate characters for consonants and vowels. So the last phonological rules convert consonants and vowels into Fidel characters (c v -> F).

During unapplication, every Fidel character is optionally split into a consonant and vowel. Phonological rules don't split the processing into two paths to handle the two alternatives; the two alternatives have to be represented in the same output. There is no way to encode {c v | F} directly in a Word, since a Word can only have optional elements. So it is encoded as (F) (c) (v). This is not a problem if there is only one rule like this, but every character in the input is a Fidel character, so this produces a lot of optional elements. Furthermore, there is another rule for morpheme breaks: c + v -> F. So each Fidel character becomes (F) (c) (+) (v) (c) (v). Unfortunately, the downstream matching algorithm is exponential in the number of optional elements.

The fix is to convert phonological rules of the form a b -> c to union(a, c) (b). This only has one optional element. union(a, c) can match either a or c, so union(a, c) (b) encodes both "a b" and "c". In general, l1 l2 l3 -> r1 r2 r3 r4 gets encoded as union(l1, r1) union(l2, r2) union(l3) (r4).

This change also makes expansion (a -> b c) more like epenthesis. I don't know of any grammars that use this.

---

This change is 

[johnml1135]

We tried this in PanGloss, our Rust port of HermitCrab, and it appeared to work, with a few alterations. It is on PanGloss main as 51599ba9 (released in 0.8.1), with the reasoning in divergence 087. Here is what we changed and why. What do you think? If any of these is wrong, we will update PanGloss to follow your correction.

What we kept: your union encoding. Each LHS segment is unioned into the surface node it matched and only the leftovers are inserted as optional. That is the speedup, and on the Amharic corpus it gives exactly the same parses as master on every word both finish (587 of 587) while also finishing the words master times out on.

What we changed:

1. No dirty marks. Narrowing runs through SimultaneousPhonologicalPatternRule, which never resets them, so a rule unapplied later on those nodes (feature, epenthesis, metathesis) can no longer match its Modified=Clean target. On Amharic, 17 of 673 words lost every parse, all long-consonant verbs (want, begin, ask, beg), because "remove consonant length" was blocked. Deletion was hit too: expanding is true for an empty target, so deletion marked its re-inserted nodes dirty.
2. Expansion left on its old Simultaneous + Deletion path. With the new path, a Simultaneous expansion rule did not terminate for us (see the thread on AnalysisRewriteRule.cs), and an Iterative one undid only one of two overlapping sites.
3. Only segments are unioned; a boundary is always a leftover. In a grammar with no phonological features, union(m, +) became a mandatory node no segment could consume: + b -> m / [+nas] _ lost kan+bo for kanmo. The Amharic shape (c + v -> F, boundary as a leftover) is unaffected.

In C#, those three changes come to one condition in Unapply (union only Segment-typed constraints) and two removals (the SetDirty calls and the AnalysisRewriteRule expansion change).

Tests: 14 fixtures for these cases are now on #480's branch under conformance/edge-cases/ (simultaneous-expansion-terminates, feature-rule-before-merge, epenthesis-fed-merge, geminate-under-merge, default-symbol-after-merge, deletion-reinserted-feature-unapply, expansion-overlapping-targets, merge-then-metathesis, and the boundary-*-in-narrowing-lhs* set). At this head 11 of the 14 fail or hang; with the changes all 14 give master's parses. boundary-leftover-in-narrowing-lhs-strrep then differs only in its traced rules (master tries a junk candidate the union never generates), so its declared rules would need updating.

Related: while testing we also found an older bug in the same spec, independent of this PR: the .Next walk can land on an optional node or boundary inside a multi-segment match. That fix is #540; this PR's targetNode.Next walk would need the same group read-back.

This review was assisted by Claude Opus 5.5.

[codecov-commenter]

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 74.38%. Comparing base (b9e7db4) to head (4294d2e).
⚠️ Report is 2 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #539      +/-   ##
==========================================
+ Coverage   74.35%   74.38%   +0.02%     
==========================================
  Files         456      456              
  Lines       38283    38301      +18     
  Branches     5245     5246       +1     
==========================================
+ Hits        28467    28490      +23     
+ Misses       8666     8662       -4     
+ Partials     1150     1149       -1     

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[claude]

1. Verdict: approve.
2. Most important: nothing open. Since 8746450, the only change is 4294d2e, which reformats AlphaAgreementMergeFindsAbbaFromApa (RewriteRuleTests.cs:598-606) and changes no behavior.
3. Counts: Critical 0, Important 0 open, Low 0 open. F1-F4 and F7 addressed, F5 and F6 withdrawn. No new findings.
4. I read the 4294d2e diff by hand and did not rerun /code-review over a formatting-only commit. I ran dotnet test tests/SIL.Machine.Morphology.HermitCrab.Tests -c Release: 110 passed, 0 failed. I could not run ./local_check.sh or dotnet csharpier check, because they needed approval this session did not have. The branch is human-authored, so --agent-strict does not apply.
5. Not verified: that 4294d2e satisfies CSharpier (CI runs that check), and the Amharic timing, which I did not rerun myself.

Public API, target framework, package: none changed. The analysis output of narrowing rules changes. machine.py parity: None verified (HermitCrab is not in machine.py).

Findings: F1 addressed; F2 addressed; F3 addressed; F4 addressed; F5 withdrawn; F6 withdrawn; F7 addressed.

Reviewed at 4294d2e