Some well-formed hyphenation grammars, such as the current TeX Afrikaans patterns, fail to load with ArrayIndexOutOfBoundsException

HyphenationTree.loadPatterns (used by both HyphenationCompoundWordTokenFilter.getHyphenationTree overloads and by the factory's hyphenator file) ends with TernaryTree.trimToSize(), which de-duplicates the tree's stored key tails through a helper TernaryTree in compact(). Those inserts go through insert(char[] key, int start, char val), whose capacity check reserves strlen(key) + 1 node slots counted from index 0, while the insert itself works from key[start]. In compact()'s key array index 0 is always an empty string, so the check always reserves one slot. When one insert needs more new nodes than are left before the end of a 2,048-slot block, it writes past the arrays and loading fails with ArrayIndexOutOfBoundsException: Index 2048 out of bounds for length 2048.

The current TeX Afrikaans patterns (10,349) trigger it; all 71 OFFO grammars the Lucene docs link to load without this exception. The failure is loud and at setup time, and the loaders return no tree. Every release from 2.4.0 (2008) to 10.6.0, and main, is affected. The one-line fix, strlen(key, start) + 1, is the bound the String overload already uses.

1. Arrays grow in blocks. BLOCK_SIZE = 2048 (:96); init() allocates lo, hi, eq, sc with 2,048 slots and sets freenode = 1 (:102-111).
2. Each public insert grows the arrays first, if needed. The String overload reserves key.length() + 1, "maximum number of nodes that may be generated" (:120). The char[] overload reserves strlen(key) + 1 (:131), and strlen(key) is strlen(key, 0) (:251-253), but the insert works from key[start] (:135, :140).
3. The recursive insert has no check of its own. It creates up to one node per character from start, plus one: a new branch node (:145) or a decompression node (:164) per level, recursing with start + 1 (:197).
4. In Lucene's source the only caller with start > 0 is TernaryTree itself (the overload is public, so outside code could pass one). trimToSize() (:382-396) makes a key vector with kx.alloc(1) (:391), so kx[0] is the empty string, and a helper TernaryTree map (:392). compact() (:398-418) copies each new tail to kx at an offset k >= 1 and calls map.insert(kx.getArray(), k, (char) k) (:408). strlen(kx.getArray()) is 0, so the check always reserves 1 slot, and the helper's arrays grow only when freenode is exactly at the block end.
5. Reached on every grammar load: getHyphenationTree(InputSource) calls loadPatterns (HyphenationCompoundWordTokenFilter.java:180; the String overload wraps its file name, :166-168), the factory loads its hyphenator file that way (HyphenationCompoundWordTokenFilterFactory.java:119), and loadPatterns calls trimToSize() (HyphenationTree.java:109).

Patterns a x 2100 + 1 and b + a x 2100 + 1c give the keys a x 2100 and b + a x 2100 + c. After balance() the main tree stores the compressed tails a x 2100 and a x 2100 + c, which compact() copies to kx at k = 1 and k = 2102.

• Insert 1 (k = 1): the check reserves 0 + 1 = 1 slot; the empty helper stores the tail as one compressed node; freenode goes from 1 to 2.
• Insert 2 (k = 2102): the check reserves 1 slot; 2 + 1 <= 2048, so nothing grows. The tail shares 2,100 letters with the first, so the insert splits one node per shared letter (2,101 new nodes needed). After 2,046 recursive calls it takes slot 2,048 and lo[pp] = lo[p] (:165) throws.
• Full stack: getHyphenationTree:180 -> loadPatterns:109 -> trimToSize:393 -> compact:414 -> compact:408 -> insert(char[], int, char):135 -> 2,046 x insert:197 -> insert:165.
• With strlen(key, start) + 1: insert 1 reserves 2,101 slots (1 + 2101 > 2048), the arrays grow to 4,096, insert 2 (2,102 reserved) fits, freenode ends at 2,103, and the grammar loads.

Real grammars get there with short tails: when the helper's freenode sits a few slots before 2,048 (or 4,096, ...), an insert that needs more new nodes than the slots left overruns, because only 1 was reserved. The Afrikaans list throws at :146, a new branch node at slot 2,048.

The repro, DTD-valid and Afrikaans rows ran on 645d4fe14a20; the others on main a9779ef3c193, whose compound/ sources are identical. The TeX project publishes plain pattern lists; the hunt wrapped them in a patterns-only XML file, which Lucene's loader accepts (its parser does not validate). The bundled hyphenation.dtd also asks for <classes>, which none of the 71 OFFO 2.2 grammars has either. These runs check loading and findPattern values only: without classes hyphenate() knows no letters, so end-to-end hyphenation with the fix was checked only on the DTD-valid file. No unmodified OFFO grammar hits this exception; OFFO af.xml does only with the 7 TeX patterns added.

The pattern count alone does not decide it; the grammar's shape and where the boundaries fall do. Random 2-6-letter grammars failed 0 of 80 times at up to 2,000 patterns, 6 of 20 at 3,000, 11 of 20 at 5,000 and 14 of 20 at 8,000. A given grammar fails or loads the same way every time: balance() rebuilds the tree from sorted keys first, so pattern order does not matter.

• Who is exposed. Applications that use HyphenationCompoundWordTokenFilter with a tree from either getHyphenationTree overload or HyphenationTree.loadPatterns, or HyphenationCompoundWordTokenFilterFactory (its hyphenator grammar is mandatory). No Lucene analyzer uses the filter by default.
• What it takes. A well-formed grammar whose compressed key tails make one insert into compact()'s helper tree need more new nodes than are left before a 2,048-slot boundary. Known real trigger: the current TeX Afrikaans list. For custom grammars there is only one measurement, a random generator of 2-6-letter patterns: none of 80 grammars failed at up to 2,000 patterns, 6 of 20 at 3,000, 11 of 20 at 5,000; how often real custom grammars hit it is not measured.
• What happens. ArrayIndexOutOfBoundsException from the loader on every load of that grammar (the hyphenation package has no assert statements; the repro fails the same with assertions on and off); the message does not say why. getHyphenationTree and the factory return no tree, so nothing is indexed wrong. One case differs: code that calls loadPatterns on its own tree, catches the exception and keeps the object holds a half-compacted tree (TernaryTree.java:410 has already re-pointed visited nodes, but the key array is replaced only at :394); on the repro grammar it reports size() 2, but findPattern of the first pattern returns an empty string.
• Scale. Far below the documented size: the helper fails at 2,048 slots, and the whole Afrikaans tree builds 20,457 nodes while loading (18,848 after balance()), about a third of the javadoc's "about 65000".
• How likely. Rare: all 71 OFFO grammars load without this exception, of 75 current TeX lists only Afrikaans hits this exception, and the recorded searches found no report of it in Lucene or in the other copies of this code.
• Workaround. No setting avoids it, and factory users can only change the grammar (for Afrikaans, OFFO's af.xml without the 7 newer patterns loads). Code that builds the tree itself can load it into a HyphenationTree subclass whose trimToSize() only calls balance(), and pass that tree to the filter's public constructor. This is unofficial and skips the compaction (more memory); it loads the repro grammar, the Afrikaans list and 9 of 9 failing random grammars with every value right.

Copy the file into lucene/analysis/common/src/test/org/apache/lucene/analysis/compound/ and run the command. The test is deterministic (no randomness; the framework's randomization does not touch this path). Pass -Ptests.asserts explicitly, because by default the build picks it from the seed. It is the suggested regression test as it stands.

For a 2-pattern grammar the shared tail must be at least 2,046 letters (2,045 loads); 2,100 leaves a margin. The test's grammar has only a <patterns> element, which Lucene's loader accepts; with a DOCTYPE and <classes>aA bB cC</classes> added it validates against the bundled hyphenation.dtd and fails the same way, assertions on and off. With short realistic patterns the same crossing takes on the order of a thousand patterns or more (the finder's 1,310, or the 10,349-pattern TeX Afrikaans list, the real-world trigger). Long patterns are not typical.

./gradlew :lucene:analysis:common:test --tests "org.apache.lucene.analysis.compound.TestHyphenationGrammarLongPatternsLoad" -Ptests.seed=DEADBEEF -Ptests.asserts=true

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.asserts=true (the same with false)
TestHyphenationGrammarLongPatternsLoad > testTwoPatternsSharingA2100LetterTailLoad FAILED
    java.lang.AssertionError: loading a 2-pattern grammar threw java.lang.ArrayIndexOutOfBoundsException: Index 2048 out of bounds for length 2048
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:8FE4FEC642477207]:0)
        at org.apache.lucene.analysis.compound.TestHyphenationGrammarLongPatternsLoad.testTwoPatternsSharingA2100LetterTailLoad(TestHyphenationGrammarLongPatternsLoad.java:34)

        Caused by:
        java.lang.ArrayIndexOutOfBoundsException: Index 2048 out of bounds for length 2048
            at org.apache.lucene.analysis.compound.hyphenation.TernaryTree.insert(TernaryTree.java:165)
            at org.apache.lucene.analysis.compound.hyphenation.TernaryTree.insert(TernaryTree.java:197)
            ... (the JVM keeps the top 1,024 frames by default; the full stack has 2,046 frames at TernaryTree.java:197)

# with the recommended fix, assertions on and off: the test passes
BUILD SUCCESSFUL

• The check exists to grow the arrays before an insert, and its sibling does it right (TernaryTree.java:120 vs :131). The char[] overload passes start to the recursive insert (:135), which measures the key from there (:140); only the bound ignores it.
• No misuse by applications. In Lucene's source the only caller with start > 0 is TernaryTree.compact() (:408; the overload is public, so outside code could pass one), reached from loadPatterns on every load. The other char[] caller passes start = 0 (HyphenationTree.java:384).
• No documented limit. loadPatterns documents only "IOException In case the parsing fails" (HyphenationTree.java:95-100), getHyphenationTree only IOException. The class javadoc's "room for about 65000 nodes" (:44) is a design note, not a contract, and the helper fails at 2,048. Lucene's char[] overload has no javadoc; Apache FOP's copy documents start as "offset into key array".
• Tests. Upstream tests load only small grammars (da_UTF8.xml, 7,352 bytes, and two files of about 1 KB), far below 2,048 helper nodes; none asserts anything about this exception.
• Precedent. A data-dependent failure in this package was fixed as a bug before: LUCENE-8124 (#9172, hyphenation values of 7 or more), fixed in 7.3.

The strongest case for "intended": the code is an import from Apache FOP, unchanged in Lucene since 2008 and the same in FOP today; the class javadoc says patterns are "usually small (from 2 to 5 characters)"; every OFFO grammar the docs link to loads without this exception, so the code works for the documented grammars; and the minimal test needs 2,100-letter patterns in a patterns-only file. The cross-model reviews of the hunt rated this case weak and verifiers rejected it; a later cross-model fact check of this doc rated it moderate.

Why it fails: age shows the path was rarely exercised, not that it is intended. The docs offer OFFO as a place to find grammars ("You can find the XML based grammar files at ..."), not as the only allowed input. A published list fails, and so does a grammar of 1,310 random 4-8-letter patterns, fewer than the javadoc's "from 5000 to 15000 hyphenation patterns" per language. The long test patterns are only a shortcut to the same boundary; a file that validates against the bundled DTD fails the same way, and the OFFO 2.2 grammars are patterns-only too. A capacity check that ignores the offset its own method uses is an oversight. Expect a maintainer to call the reach narrow, not the behaviour intended.

Option A was applied in scratch worktrees of main 645d4fe14a20 and run through gradle; the worktrees were removed afterwards. Option B was run only through the repro harness on the hunt's commit; option C was not run.

One line in TernaryTree.java:131. The recursive insert creates at most one node per character from start, plus one, so strlen(key, start) + 1 is the right bound; start == 0 callers are unchanged.

   public void insert(char[] key, int start, char val) {
-    int len = strlen(key) + 1;
+    int len = strlen(key, start) + 1;
     if (freenode + len > eq.length) {
       redimNodeArrays(eq.length + BLOCK_SIZE);
     }

Trade-offs

• No cost on the analysis path: only grammar loading inserts into the tree.
• Not covered (untested, out of scope): redimNodeArrays grows by one 2,048-slot block per insert, so a single key needing more than about 2,000 new nodes could still overflow, in either overload (option C). Option A is deliberately scoped to this bug, not general long-key hardening.
• The separate 16-bit key-offset bug in the same class (LFV-897) is not fixed by this and still reproduces with it.

What the checks validated

• Gradle in a scratch worktree of main 645d4fe14a20, seed DEADBEEF (this doc): stock, the repro fails; with the fix, the repro and every upstream org.apache.lucene.analysis.compound.* suite (TestCompoundWordTokenFilter, TestHyphenationCompoundWordTokenFilterFactory, TestDictionaryCompoundWordTokenFilterFactory, TestPatternParser) pass, assertions on and off (5 classes, 26 tests, 0 failures each way).
• An earlier gradle run the same day, also on 645d4fe14a20: all of :lucene:analysis:common:test with the fix (340 classes, 1,910 tests, 18 skipped, 0 failures), and :lucene:analysis:common:check -x test (google-java-format, ecjLint, forbiddenApis) with the fix and the test file added.
• In the repro harness: the finder's 1,310-pattern JUnit, an independent 4-test JUnit and the real TeX Afrikaans list (10,349 patterns, 0 wrong values) pass with it, and so do 25 random scale runs and 2.4.0 with the same line changed.

FOP-2569 (Apache FOP, open since 2016, a different report) carries a 2020 patch that adds if (freenode + strlen(key, start) > eq.length) redimNodeArrays(...) at the top of the recursive insert. Applied alone to Lucene main it also makes the finder's and an independent reproducer's tests pass.

Trade-offs

It re-checks capacity at every level of every insert to compensate for a bound that stays wrong at :131. In FOP it is part of a larger change, which also widens the node pointers to int, that was never applied: its author, Chris Bowditch, wrote that "the unit tests are failing and so it needs more work" and later "I never applied the patch". Fixing the bound is the root-cause fix.

On top of A, let both public overloads grow to at least freenode + len, e.g. redimNodeArrays(Math.max(eq.length + BLOCK_SIZE, freenode + len)).

Trade-offs

Closes the long-key gap noted under A; not needed for this bug. It does not lift the 16-bit char node and key offsets (:66-72, :90-92, :151, :410), so trees grown past 65,535 slots run into LFV-897.

• Method (semi-formal): bounded-exhaustive translation validation on the stock main jars, public API only, in a sweep of analysis-common APIs no earlier hunt had named. Every insert sequence of depth 3 or less (9,723 of them) over 21 keys (including a lone high surrogate), checked after insert, clone, balance and trimToSize against a TreeMap: 3,305,820 find/knows checks, 0 mismatches.
• Signal. A scale phase with 2,000-6,000 random keys threw ArrayIndexOutOfBoundsException at exactly 2,048 or 4,096 inside trimToSize. The finder traced it to the capacity check by reading the code.
• Reach. The finder loaded 75 current TeX pattern lists through getHyphenationTree: only Afrikaans hits this exception. A devil's-advocate checker then loaded all 71 OFFO grammars (all load) and showed that OFFO's af.xml plus the 7 newer TeX patterns fails.
• The finder's public-API JUnit used 1,310 random patterns; the repro was later minimized to one 2-pattern test.