Large hyphenation grammars load without error but silently lose patterns: TernaryTree key-array offsets wrap at 65,536

TernaryTree, the tree behind HyphenationCompoundWordTokenFilter's grammars, stores the unshared end of each pattern (its tail) in one key array and keeps the tail's start offset in a 16-bit char (lo[p] = (char) kv.alloc(len + 1)), with no range check. Once the key array passes 65,535 chars, offsets wrap and new tails overwrite old ones. The grammar loads without error, but some patterns then return wrong values or are not found. The Norwegian grammars from the OFFO download that Lucene's docs point to are hit (nb.xml/nn.xml: 1,158 of 27,448 patterns wrong; OFFO 1.2 no.xml: 309 of 26,017, and 29 of 104 real words hyphenate differently), far below the documented node capacity. In every release from 2.4.0 to 10.6.0 and on main; not fixed upstream.

1. Storage. TernaryTree keeps four parallel char[] node arrays and a char freenode (TernaryTree.java:66 lo, :69 hi, :72 eq, :85 sc, :92 freenode). For a compressed node (sc[p] == 0xFFFF) lo[p] holds the offset of the key's tail in the key array kv, not a node pointer (the lo javadoc, :62-65).
2. The narrowing. insert allocates the tail with lo[p] = (char) kv.alloc(len + 1) (:151) and copies it with strcpy(kv.getArray(), lo[p], key, start) (:152). CharVector.alloc returns an int and has no 16-bit check; repeated allocations grow the array past 65,535 (CharVector.java:102-112), so only the stored offset is cut to 16 bits: offset 65,600 becomes 64. The new tail is written at 64, over an earlier key's tail, and the slot reserved at 65,600 stays empty.
3. What lookups see. find compares the rest of the query with the tail at lo[p] (:272), so the earlier key now reads a foreign tail: it is not found, or another string matches. Later inserts that split such a node read the wrong characters (:169). The first lost key appears exactly at the first insert whose offset exceeds 0xFFFF (key lengths 12, 40 and 100); with plain insert and no compaction, 327 of 2,000 keys are already lost.
4. Loading makes it permanent. loadPatterns (HyphenationTree.java:101-115) ends with trimToSize() (:109), which rebuilds the tree from the keys it can read back (balance(), TernaryTree.java:354-372; from the code, some corrupted keys now read the same, which is why size() drops to 27,358) and compacts the key array (compact(), :398-418). compact() narrows again at :408 (map.insert(kx.getArray(), k, (char) k)) and :410 (lo[p] = (char) k): the repro's compacted array is 66,302 chars, so it wraps a second time.
5. No check. Nothing compares an offset with 0xFFFF; the loaders document only IOException (HyphenationTree.java:99, HyphenationCompoundWordTokenFilter.java:164, :175).
6. The other 16-bit limits. Node indexes are chars as well (freenode++, :145, :164): past 65,535 nodes they wrap, and the four TeX lists that get there fail with StackOverflowError, the symptom Apache FOP's FOP-2569 reports. HyphenationTree.addPattern stores the value offset as (char) k (HyphenationTree.java:415, :417); a probe for the fix shows that it also loses values silently on a synthetic grammar (790 of 5,832 patterns, value space 75,817 bytes), while Norwegian nb.xml needs only 6,045 bytes.

The trigger is the length of the key array that holds the stored tails, not the number of patterns.

• Who is hit. Applications that use the opt-in HyphenationCompoundWordTokenFilter (in no default analyzer) directly, through getHyphenationTree or HyphenationTree.loadPatterns, or through HyphenationCompoundWordTokenFilterFactory, whose mandatory hyphenator file is documented as "path to the FOP xml hyphenation pattern" with a link to OFFO (:38-39, loaded at :119).
• Which grammars. In practice Norwegian: OFFO 2.2 nb.xml and nn.xml, OFFO 1.2 no.xml, and the TeX hyph-nb/hyph-nn lists. 69 of the 71 OFFO 2.2 grammars, 20 of 21 OFFO 1.2 grammars and 68 of 75 TeX lists load correctly.
• What goes wrong. Wrong decompounding with no error. With OFFO 1.2 no.xml, 29 of 104 real Norwegian words hyphenate differently and the filter emits different subwords (forfatter adds forf, atter, at; altertavle splits alt-er-tav-le instead of al-ter-tav-le). Some of those words contain no lost pattern: overwritten tails also create false matches. With the TeX nb list in a grammar with classes, 32 of 235 words from Lucene's own Norwegian stemmer test data differ.
• Consistent, so easy to miss. Index time and query time use the same corrupted tree. After a fix, already indexed documents keep the old subwords until they are reindexed (inference, not run).
• Masked case. None of the 71 OFFO 2.2 files has the <classes> element that Lucene's parser needs to hyphenate anything, so with 2.2 nb.xml the loss shows only through findPattern (0 of 300 words differ end to end). That missing-classes gap is a separate issue.
• Louder neighbours. Grammars past 65,535 nodes (the newer TeX German and Hungarian lists) fail at load time with StackOverflowError (FOP-2569); TeX Afrikaans throws the related LFV-894 exception.
• Workaround. Only a grammar whose tails stay under 65,535 chars, e.g. split or trimmed (not tried).

The test sits in org.apache.lucene.analysis.compound like the module's own tests but uses only public API. Each pattern is written as x1yyyy... (a hyphen after the first letter), so every one must return 01 followed by 29 zeros. The grammar comes from its own java.util.Random(7), so the result does not depend on the test seed. Single thread, deterministic, about 1 s; compiles against 9.1 and later (org.apache.lucene.tests first exists in 9.1.0; against 9.0.0 it does not compile); for 2.4.0 to 9.0.0 a version-portable main() with the same grammar covers the older releases.

The loaded tree has 4,771 nodes (the javadoc promises room for about 65,000) and, even after compaction, a key array of 66,302 chars. The same test is the suggested regression test; it passes with the recommended fix.

Lucene's build picks tests.asserts at random from the seed when it is not given: for -Ptests.seed=DEADBEEF on :lucene:analysis:common it is off (the failure's "Reproduce with" line prints -Ptests.asserts=false), so add -Ptests.asserts=true for a run with assertions on; it fails the same way.

# gradle, main 5adff78bb168, seed DEADBEEF (assertions off by this seed's randomization)
TestHyphenationTreeLongKeyArray > testEveryPatternKeepsItsValues FAILED
    java.lang.AssertionError: patterns that lost their values expected:<0> but was:<556>
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.apache.lucene.analysis.compound.TestHyphenationTreeLongKeyArray.testEveryPatternKeepsItsValues(TestHyphenationTreeLongKeyArray.java:59)

# gradle with -Ptests.asserts=true: the same failure
# JUnit runner, seed DEADBEEF: the same failure on main (-ea and -da), 10.6.0 (-ea and -da), 9.12.3 and 9.1.0 (-ea)
# main with the recommended fix: passes (gradle, assertions off and on; JUnit runner -ea)

• Documented design. The class javadoc is a design note, not an error contract, but what it describes is a map ("All said, this is a map with strings as keys and char as value", TernaryTree.java:48) with one capacity, in nodes: "Using java's char type as pointer ... This gives room for about 65000 nodes" (:42-45). The Norwegian tree peaks at 52,404 nodes while loading (47,375 once loaded); the repro's has 4,771. No javadoc, package doc, CHANGES or MIGRATE entry mentions a key-array limit or that wrong values can result. loadPatterns: "@throws IOException In case the parsing fails" (HyphenationTree.java:99).
• Lucene points to these files. "You can find the XML based grammar files at the ... (OFFO) Sourceforge project (direct link to download the pattern files: ...offo-hyphenation.zip). The files you need are in the subfolder offo-hyphenation/hyph/" (package-info.java:88-96). That zip is OFFO 2.2 and contains the affected nb.xml and nn.xml.
• Silent by construction. CharVector.alloc returns an int with no 16-bit check, so the array grows past 65,535 (CharVector.java:102-112); the (char) cast is the only limit, and nothing checks it.
• Precedent. LUCENE-8124 (#9172, fixed in 7.3.0): grammars the parser accepts but that gave wrong values (pattern values >= 7) were fixed as a bug.
• Tests. The module's compound tests load only small grammars (da_UTF8.xml and two small LUCENE-8124/8183 grammars); they all pass with the fix.

The strongest case for "intended": the 2008 javadoc deliberately trades generality for 16-bit pointers, expects "from 5000 to 15000 hyphenation patterns" that "are usually small (from 2 to 5 characters)" and says "Pretty limited!" (TernaryTree.java:38-48); the lo javadoc says lo also holds the pointer "to rest of the key" and lo is a char[], so a careful reader could infer 16-bit key offsets; a committer of Apache FOP (where the class comes from) wrote on FOP-2569 that it is designed "for a maximum number of hyphenation patterns of around 65535"; and downstream docs say to use OFFO v1.2 files only.

Why it fails: the only stated capacity is in nodes, and the corrupted trees are inside it (and inside "around 65535 patterns"); "usually small (from 2 to 5 characters)" is the 2008 author's expectation of typical patterns, followed by their own test numbers ("so I think we are safe"), not a documented precondition or limit; the "v1.2 only" notes are about the missing <classes> element, and v1.2 no.xml is affected too; and a size limit would justify an exception at load time, not a tree that loads and then answers wrongly. The works-as-designed reviewer rated the argument "moderate" and rejected it. A maintainer may still answer "documented as limited"; the fix is the same either way: widen, or throw.

Three options. A was built and validated on main 5adff78bb168; a key-offset guard like B's was run by a verifier as a cause check; C was not built. All of them run at grammar load time only.

lo becomes int[], so the offset from kv.alloc is stored whole; reads of lo as a node pointer are cast back to char. compact() dedupes tails with a HashMap<String, Integer> instead of a TernaryTree with char values. Two guards replace the remaining silent wraps: the node index (in both public insert methods; exact on the loader path, see the caveats below) and the value-space offset in HyphenationTree.addPattern. +35/-19 in TernaryTree.java and HyphenationTree.java.

protected int[] lo; // was char[]: lo also holds offsets into the key array kv
lo[p] = kv.alloc(len + 1); // insert(): was (char) kv.alloc(len + 1)
HashMap<String, Integer> map = new HashMap<>(); // compact(): offsets kept as int
// node pointers read from lo are cast back: insert((char) lo[p], ...), p = (char) lo[p]
if (freenode + len > Character.MAX_VALUE) { // insert(String, char) and insert(char[], int, char)
  throw new IllegalStateException("TernaryTree is full: it can hold at most 65535 nodes"); // caveat 1
}
if (k > Character.MAX_VALUE) { // HyphenationTree.addPattern, before (char) k
  throw new IllegalStateException(
      "Hyphenation values do not fit: value space offset " + k + " exceeds 65535");
}

Trade-offs

• lo grows from 2 to 4 bytes per node (about 100 KB more for the Norwegian tree at its 52,404-node peak while loading), at load time only; the analysis path only gains casts. No benchmark was run.
• lo is a protected field of the public TernaryTree, and HyphenationTree is public and subclassable, so the type change is an API change for subclasses that read lo (a MIGRATE note on main; consider B for a 10.x backport).
• Grammars past 65,535 nodes still cannot be loaded, but now fail with a clear message.
• Caveat 1: freenode starts at 1 and the guard is freenode + len > Character.MAX_VALUE, so the tree stops at 65,534 nodes; the message's "at most 65535 nodes" is an upper bound. Say 65534, or "node indexes must fit in a char", in the final patch.
• Caveat 2: in insert(char[], int, char) the new guard, like that method's existing capacity check, sizes the key with strlen(key) instead of strlen(key, start) (the LFV-894 defect, TernaryTree.java:131 on main). It is exact on the loader path (insert(String, char)); direct callers with a NUL before start still need LFV-894's own fix.

What the checks validated

• Gradle in a clean scratch worktree of 5adff78bb168, OpenJDK 25.0.3, seed DEADBEEF: stock, the repro fails (556) with assertions off (this seed's default) and on (-Ptests.asserts=true); with the fix it passes with assertions off and on. The assertions-on gradle runs were made by the independent fact check (2026-11-04) in its own scratch worktree; the JUnit runner with the fix and -ea passes too.
• org.apache.lucene.analysis.compound.* with the fix: 5 classes, 26 tests (the repro included), 0 failures, assertions off and on; the whole :lucene:analysis:common:test: 1,910 tests, 18 skipped, 0 failures (assertions off by the seed); :lucene:analysis:common:check -x test (formatting, ecj lint, forbidden APIs, license headers) passes.
• The OFFO nb.xml and nn.xml load with 0 wrong patterns (stock: 1,158 each); the TeX hyph-de-1996 list now throws TernaryTree is full: it can hold at most 65535 nodes instead of StackOverflowError (fixed classes over main's jars, assertions off).
• A probe grammar whose value space passes 65,535 bytes now throws instead of loading with 790 of 5,832 patterns wrong; a 40,000-pattern probe grammar written to pass 65,535 nodes (the probe prints no node count), which on stock throws ArrayIndexOutOfBoundsException: Index 40000 out of bounds for length 40000 while loading, now stops at the node guard with TernaryTree is full.
• Side effect: compact() no longer calls insert(char[], int, char), so the related LFV-894 repro passes too. That public method itself is not fixed by this (caveat 2).

Throw a clear exception when kv.alloc (:151) or compact()'s kx.alloc returns more than 0xFFFF, plus A's two guards. A verifier's guard of this kind makes OFFO 1.2 no.xml fail with "key-array offset 65536 does not fit in a char" while its node-index guard never fires, and nl.xml and en_GB.xml still load.

Trade-offs

No API change and easy to backport, but the Norwegian grammars then fail to load at all instead of loading about 96% right.

lo, hi, eq, root, freenode and the value offset become int, so grammars of any size load, including the newer TeX German and Hungarian lists. Apache FOP's unapplied FOP-2569 patch does most of this but keeps the key-offset casts, so it would have to be extended.

Trade-offs

A node grows from 8 to 14 bytes (lo, hi, eq become int; sc stays a char, as in FOP-2569's patch; root, freenode and the value offset are not per node), about 0.3 MB more at the Norwegian tree's 52,404-node peak; touches TernaryTree, its iterator and HyphenationTree.searchPatterns. Not built.

Method: semi-formal (translation validation against an exact reference).

• A bounded-exhaustive phase compared TernaryTree/HyphenationTree with an exact reference on small inputs: 3,305,820 checks, 0 mismatches (small trees never reach the limit).
• The same exact oracle was then run on the stock jar with 75 real TeX pattern lists loaded through the public API: every pattern's findPattern was compared with the values written in the pattern text. The Norwegian nb and nn lists returned 1,158 wrong values with no load error; four large lists threw StackOverflowError.
• A same-package measurement probe (node count and key-array length during insertion) tied the loss to the key array passing 65,535 chars (Norwegian at the end of insertion: a 70,280-char key array and 52,404 nodes).
• It was then reduced to a public-API JUnit test on a synthetic grammar.

The first signal came from the exact oracle on real lists, not from the bounded-exhaustive phase itself.