Hunspell spell-checker: simplified compound joins after the first part are rejected or overflow the stack

CHECKCOMPOUNDPATTERN endchars beginchars replacement lets a Hunspell dictionary accept a simplified spelling at a compound join: with ff f ff, a written ff stands for ff|f, as in pre-reform German Schiffahrt (Schiff + Fahrt). Lucene's Hunspell.spell splits a compound left to right and works on the rest of the word as a slice of the same array. To try a simplified join in that slice, CheckCompoundPattern.expandReplacement writes the long form into a new array that starts with the whole word (kept so the FORCEUCASE check can see the first letter) but returns it with offset 0, while its callers count positions from the start of the slice. At the first join the two agree; at a later join the next part is read from the start of the whole word. So dampfschiffahrt and donaudampfschiffahrt are rejected (native Hunspell accepts both), and schiffschiffahrt, or the 3-letter auu with CHECKCOMPOUNDPATTERN u u u, makes spell() and suggest() throw StackOverflowError. Only the opt-in spell-checker is affected, with dictionaries that use the replacement field, in every release from 8.9.0 to 10.6.0 (10.6.0 by reading); the fix is one changed return in one method.

• Compound checking: when a word is not in the dictionary, Hunspell.spell tries to split it into dictionary words that may be compounded (here, words with the COMPOUNDFLAG). It finds a first part, then splits the rest the same way, recursively, so a word can have any number of parts (COMPOUNDWORDMAX defaults to unlimited).
• Simplified join (CHECKCOMPOUNDPATTERN endchars beginchars replacement, hunspell(5): "The optional replacement parameter allows simplified compound form"): with ff f ff, the two letters ff written at a join stand for ff|f, so schiffahrt is read as schiff + fahrt.
• The slice: from the second part on, the code works on the rest of the word as a slice of the same array, an offset (where the rest starts) and a length.

1. For each position in the current slice, checkCompounds also tries the simplified joins (Hunspell.java:241): expandReplacement writes the long form, new String(word.chars, 0, word.offset + breakPos) + endChars + beginChars + rest (CheckCompoundPattern.java:96-100). The string starts at position 0 of the whole word, because LUCENE-9775 kept the earlier parts for the FORCEUCASE check, and new CharsRef(String) gives it offset 0.
2. The caller looks up the next part as findStem(expanded.chars, expanded.offset, breakPos, ...) with breakPos = pos + endLength, a length counted inside the slice (Hunspell.java:255-257); checkCompoundsAfter then reads or recurses on the rest at offset + breakPos (:270-275, :284).
3. At the first join the slice starts at 0 and all is right. At a later join the next part is read from the start of the whole word, and the rest re-includes the earlier parts.
4. If those first letters are not a word, that split fails, and for dampfschiffahrt every other split fails too, so the valid compound is rejected. If they happen to be one (the first part again) and the pattern matches again, the rest is longer than before; nothing limits the depth by default (compoundMax = Integer.MAX_VALUE, Dictionary.java:152, checked at Hunspell.java:214), so the recursion ends in StackOverflowError.

dampfschiffahrt (15 letters, positions 0-14) with the dictionary dampf, schiff, fahrt, donau:

schiffschiffahrt (16 letters): at the second join the long form is schiffschifffahrt (17); the next part is read as [0, 6) = schiff, the first part again, and the rest is [6, 17) = schifffahrt, 11 letters instead of 10. The next level gives schiffffahrt (12), then 13, and so on, one more f each time, until the stack overflows. An executed trace of the lookups shows exactly these letters, on main and with the fix ([6, 12) = schiff, [12, 17) = fahrt: accepted).

The same shape gives a 3-letter overflow: one word au with CHECKCOMPOUNDPATTERN u u u makes spell("auu") find au again at every level. C Hunspell expands the current part in a copy and recurses on its substring (affixmgr.cxx:1641-1646, :2084), so its positions stay relative to the part.

• Who. Callers of the spell-checker API: Hunspell.spell, Hunspell.suggest, and Suggester (a public class from 9.5.0), which creates an internal speller (Suggester.java:184-185) and validates candidates with its spell (:215, :298, :301); before 9.5.0 the same code is reached through Hunspell.spell and suggest. Executed: spell and suggest both throw.
• Opt-in twice. The spell-checker is a separate API that no analyzer calls, and the dictionary must use the optional replacement field of CHECKCOMPOUNDPATTERN. Compounds of three or more parts are the default once compounding is on, since COMPOUNDWORDMAX is unlimited by default.
• Real dictionaries. None of 191 public .aff files surveyed (LibreOffice and wooorm/dictionaries) uses the replacement field. A dictionary author reported using it to native Hunspell (hunspell/hunspell#950, 2023, a Sanskrit rule). Both documented examples, the ChangeLog's ff f ff and the u/B u/B u of native's Telugu test checkcompoundpattern4, reach the overflow.
• Effect. Valid compounds whose simplified join is not the first join are reported as misspelled, silently. Words in which the expanded letters line up with an earlier part throw StackOverflowError: an Error, so catch (Exception e) does not catch it, and the default suggest time limit (250 ms, return partial result) does not stop it. Each call fails on its own: after the overflows, the same Hunspell instance answered five checked words like a fresh instance.
• Not affected. HunspellStemFilter uses Stemmer.stem, which does not compound (HunspellStemFilter.java:86, :111), and getRoots returns no roots for compounds (Hunspell.java:300). Executed: the stem filter returns the triggering words unchanged with all three triggering dictionaries, and getRoots("schiffschiffahrt") is [].
• Workarounds. A small COMPOUNDWORDMAX in the dictionary stops the overflow but not the false negatives (with COMPOUNDWORDMAX 3, barfozar is still rejected); a large one is finite but costly (with 1024, spell("auu") made about a million stem lookups and allocated about 1.5 GB); a checkCanceled hook with a budget can stop the recursion, since it runs on every stem lookup (Hunspell.java:165).
• Likelihood: rare. It needs such a dictionary; then ordinary three-part compounds hit the false negative. No scale is needed: one word triggers it.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.StackOverflowError
       org.apache.lucene.analysis.hunspell.Dictionary.hasFlag(Dictionary.java:1506)
       org.apache.lucene.analysis.hunspell.Hunspell.acceptCase(Hunspell.java:187)
       org.apache.lucene.analysis.hunspell.Hunspell.lambda$findStem$0(Hunspell.java:175)
       org.apache.lucene.analysis.hunspell.Stemmer.doStem(Stemmer.java:245)
       org.apache.lucene.analysis.hunspell.Hunspell.findStem(Hunspell.java:169)
       org.apache.lucene.analysis.hunspell.Hunspell.checkCompoundPatternReplacements(Hunspell.java:257)
       org.apache.lucene.analysis.hunspell.Hunspell.checkCompounds(Hunspell.java:241)
       org.apache.lucene.analysis.hunspell.Hunspell.checkCompoundsAfter(Hunspell.java:285)
       org.apache.lucene.analysis.hunspell.Hunspell.checkCompoundPatternReplacements(Hunspell.java:260)
       [...]

• Contract. hunspell(5): "CHECKCOMPOUNDPATTERN endchars[/flag] beginchars[/flag] [replacement] ... The optional replacement parameter allows simplified compound form." No limit on the position or the number of parts, and "COMPOUNDWORDMAX ... (Default is unlimited.)". Hunspell.spell: "@return whether the given word's spelling is considered correct according to Hunspell rules" (Hunspell.java:71-74): a boolean result; not a formal promise that no Error escapes, but no limitation or expected failure is documented. The class "can be used in place of native Hunspell for many languages" (:35-36); its examples of unsupported cases ("For example:" Hungarian, non-BMP characters, PHONE, :37-44) do not mention this directive. hunspell(5) warns right after the directive that "COMPOUNDMIN doesn't work correctly with the compound word alternation" (man/hunspell.5:494-495); that does not explain this bug, since every repro uses COMPOUNDMIN 1.
• Tests. Lucene's ported fixtures checkcompoundpattern2 and checkcompoundpattern3 list only two-part simplified forms (fozar, fur, bozan), so no test reaches a later join (TestSpellChecking.java:97-106). TestHunspellRepositoryTestCases does not exclude native's checkcompoundpattern4 (:38-46), so Lucene expects to conform on it; that fixture's own words are two-part and pass (checked with the verifiers' own tests on that dictionary; the repository-wide test needs a Hunspell source checkout and was not run).
• History. The feature commit (LUCENE-9717, d0ae2bd2b9c, 2021-02-03) built the long form relative to the part and handled later joins (barfozar, barfur accepted, spell("auu") false). Two weeks later LUCENE-9775 (902cb93db22) changed only that expression in expandReplacement so the FORCEUCASE check could see the word's first letter, and left the offset at 0; the author's review note says "Include all compounds parts from the very beginning for the case check to work later". That commit with only this line reverted is correct again. Nothing in it mentions simplified joins after the first part.
• Reference. Native Hunspell 1.3.2 and 1.7.2 accept barfozar, barfur, barbozan, dampfschiffahrt and donaudampfschiffahrt, answer auu with "misspelled, suggestion au", and never crash on the words tried.
• Precedents. LUCENE-9729 fixed an earlier offset/length slip in the same class; native Hunspell fixed CHECKCOMPOUNDPATTERN failing in compounds of more than two parts as a bug in 2010 (hunspell/hunspell#126).

The strongest case: the class promises to replace native Hunspell only for many languages, the ported fixtures show only two-part simplified forms, and native Hunspell is itself position-dependent (it rejects fozarbar and schiffschiffahrt), so behaviour beyond two parts is unspecified.

Why it fails: the manual sets no position or count limit; the original code handled later joins, and the loss came from an unrelated FORCEUCASE change; the javadoc's examples of unsupported cases do not mention this directive; the asserted cases are exactly those where native Hunspell, the manual and the fixed code agree; and nothing documents a StackOverflowError from spell() on a 16-letter, or 3-letter, word as expected. Every reviewer that rated the intended-behaviour case rated it weak; the refute review gave no verdict. Verdict: not intended, a defect.

One fix was built and run in a scratch worktree at a9779ef3c193; the finder and the independent reproducer produced textually different patches that make the same correction. It keeps what LUCENE-9775 wanted (the array still starts with the whole word) and makes every part-relative reader see the current part at the offset it expects. It does not bound the recursion for every possible pattern (option C). For the regression test, the primary test class covers both symptoms; the 3 fixture lines are smaller but cover only the false negatives.

Build the long form as today, then wrap it with word.offset instead of 0.

-      return new CharsRef(
+      String expanded =
           new String(word.chars, 0, word.offset + breakPos)
               + endChars
               + beginChars
-              + word.subSequence(breakPos + replacement.length(), word.length));
+              + word.subSequence(breakPos + replacement.length(), word.length);
+      // keep the preceding compound parts in the array, but keep positions relative to word.offset
+      return new CharsRef(expanded.toCharArray(), word.offset, expanded.length() - word.offset);

Trade-offs

Changes verdicts only for dictionaries that use the replacement field: valid later-join simplified forms are accepted, and the overflow words of these examples return a verdict. Native Hunspell's verdicts depend on the position and the pattern in ways hunspell(5) does not describe: with the checkcompoundpattern2/3 patterns it rejects fozarbar, furbar and bozanbar; with ff f ff it accepts schiffahrtdampf but rejects schiffschiffahrt. The fix accepts all of these words, so it also accepts some words native rejects (furfur, bozanbozan, schiffschiffahrt); stock Lucene already accepts first-join forms native rejects (fozarbar, furbar). It allocates what today's code allocates (new CharsRef(String) also copies the string). Not benchmarked.

What the checks validated

• Scratch worktree at a9779ef3c193, gradle, seed DEADBEEF: stock plus the fixture lines fails 16 of 72 (five repro classes and TestSpellChecking), with assertions on and off; the primary test alone fails 2 of 3 both ways.
• With the fix and the fixture lines: --tests 'org.apache.lucene.analysis.hunspell.*' plus the five repro classes, 51 classes, 177 tests, 0 failures, 13 skipped (TestPerformance 10 and TestAllDictionaries 1 need external dictionaries or word corpora, TestAllDictionaries 1 is @Ignored, TestHunspellRepositoryTestCases 1 needs a Hunspell source checkout), so 164 ran and passed, with assertions on and off; TestSpellChecking's forceucase, checkcompoundpattern and simplifiedtriple cases included.
• :lucene:analysis:common:check -x test (google-java-format, ecj lint, forbidden APIs) passes with the fix, the fixture lines and the primary test.
• Earlier, with the fix shadowed on ea57360912ed: the finder's 3 of 3, the independent reproducer's 7 of 7, the devil's advocate's tests and Lucene's hunspell test classes 146 of 146 pass; the lookup trace reads schiff at the right offset.
• Later, by probe on a9779ef3c193, assertions on and off: a simplified join followed by a regular part (dampfschiffahrtdampf, donaudampfschiffahrtdampf) is false on main and true with the fix, as native Hunspell 1.3.2 and 1.7.2 answer. No test covers a pattern for which the fix does not shrink the tail (option C).

Revert to word.subSequence(0, breakPos) + ... (offset 0 is then right) and pass the whole word's first character, or the original array, to hasForceUCaseProblem separately.

Trade-offs

Same verdicts as A in principle, a larger diff in Hunspell.java. Not run. Reverting the line alone is not enough: for a simplified compound the FORCEUCASE check would read the current part's first letter (Hunspell.java:279, :290).

Stop when the remaining tail is not shorter than the current slice, or cap the depth by the word length.

Trade-offs

Prevents the StackOverflowError but not the false negatives. Not run. Not made redundant by A: after A the tail left after a simplified join is shorter than the slice only when the match position plus the replacement's length exceeds the length of beginchars, and the parser allows any lengths (CheckCompoundPattern.java:29-45). Executed: CHECKCOMPOUNDPATTERN x yx x with COMPOUNDMIN 1 and the words yx, z makes spell("yxz") throw StackOverflowError on main and with A, assertions on and off. The match is at the first join, where the offset is right, so this is a separate, contrived edge; native Hunspell 1.3.2 and 1.7.2 answer "misspelled".

Add a small COMPOUNDWORDMAX to the dictionary, or pass a checkCanceled hook with a budget to the Hunspell constructor.

Trade-offs

Stops the overflow (executed with COMPOUNDWORDMAX 3), not the false negatives. A large value is finite but costly: with 1024, spell("auu") made about a million stem lookups and allocated about 1.5 GB.

Method: differential testing against another implementation (the hunt counts this as testing, not as checking against an exact reference semantics).

• A generator built word lists from the 131 Hunspell 1.7.2 conformance fixtures: fixture words, every generated form, case variants, edits, two-part and three-part concatenations. A small C driver called Hunspell_spell per word, and the results were compared with the stock Lucene jar.
• On the checkcompoundpattern4 (Telugu sandhi) dictionary, Lucene threw StackOverflowError on 11 words, such as pErupErupEru and sUrya-pEru; the fixture's own two-part words pass.
• Code reading of expandReplacement and its callers found the offset; a shadow fix confirmed it. Three-part words on Lucene's own checkcompoundpattern2/3 content (barfozar, barfur, barbozan) showed the silent false negatives, and the finder reduced both to a public-API JUnit.
• An independent reproducer, two cross-model stages, a devil's advocate (who added the ChangeLog's German example), an adjudication and a credibility audit then checked it (see the checks).