FSTCompiler throws ArrayIndexOutOfBoundsException on BYTE4 nodes whose labels span 2^31-8 or more

FSTCompiler writes a node with at least 5 arcs at depth 3 or less, or at least 10 arcs anywhere, with fixed-length arcs, and then chooses binary search or direct addressing. Direct addressing stores one presence bit per label between the node's first and last label, and the compiler sizes that table as getNumPresenceBytes(labelRange) = (labelRange + 7) >> 3 with labelRange = last - first + 1, both in 32-bit int (FSTCompiler.java:540, FST.java:575). No narrower BYTE4 label range is documented, and the writer accepts any non-negative int. When last - first >= 2^31 - 8 the addition overflows: for the root labels {0, 1, 2, 3, 2147483646} the table needs 268,435,456 bytes, and the computation gives -268,435,456. That makes direct addressing look cheaper than binary search's 35 bytes, so it is chosen (FSTCompiler.java:642-647), the writer's buffer offset goes negative (:742) and the first copy throws ArrayIndexOutOfBoundsException: arraycopy: destination index -268435436 out of bounds for byte[11] (:751), with assertions on and off. directAddressingMaxOversizingFactor(-1), documented to disable direct addressing (:321-322), fails the same way. Introduced in 8.4.0 by LUCENE-8920 (068b6babac3); every release from 8.4.0 to 10.6.0 fails, and main is unchanged. Computing the range in long and using binary search when it does not fit fixes it (validated); allowFixedLengthArcs(false) is a workaround. Low impact: no in-tree producer can reach it, and a corrupt FST is never returned.

• FSTCompiler (org.apache.lucene.util.fst, @lucene.experimental) builds an FST from sorted IntsRef keys. FST.INPUT_TYPE "Specifies allowed range of each int input label" (FST.java:68): BYTE1, BYTE2 or BYTE4. BYTE4 labels are written as a vInt; the writer only asserts v >= 0 (FSTCompiler.java:580-591), and no narrower range is documented.
• Fixed-length arcs: chosen when allowFixedLengthArcs is true (the default) and the node has at least 5 arcs at depth <= 3 or at least 10 arcs (FSTCompiler.java:601-606).
• Direct addressing: one presence bit per label in [first, last], so its table has (labelRange + 7) >> 3 bytes with labelRange = last - first + 1 (FST.java:573-576). shouldExpandNodeWithDirectAddressing compares its size with binary search's (FSTCompiler.java:617-650).

1. int labelRange = last - first + 1 (FSTCompiler.java:540), guarded only by assert labelRange > 0 (:541).
2. getNumPresenceBytes computes (labelRange + 7) >> 3 in int (FST.java:575). For labelRange >= 2^31 - 7, that is last - first >= 2^31 - 8, the addition overflows and the result is about -2^28.
3. sizeForDirectAddressing is then negative (:624-627), expansionCost <= 0 (:632) and direct addressing is chosen (:642-647) for the default factor and for -1.
4. writeNodeForDirectAddressingOrContinuous computes a negative bufferOffset (:742) for the repro's node; ensureCapacity does not grow the buffer for a negative size (:743, :1176-1182), and the first scratchBytes.writeTo (:751) throws from System.arraycopy.

Root labels {0, 1, 2, 3, 2147483646}, output 1 each. Each arc is 1 flag byte, a vInt label (1 byte, or 5 for 2147483646) and a 1-byte output, so maxBytesPerArc = 7 and maxBytesPerArcWithoutLabel = 2. labelRange = 2,147,483,647 (still positive). Presence bytes: 2,147,483,647 + 7 wraps to -2,147,483,642, and >> 3 gives -268,435,456 instead of 268,435,456. Direct addressing size -268,435,456 + 1 + 2 x 5 = -268,435,445; binary search 7 x 5 = 35; expansion cost -268,435,480 (default) or -268,435,410 (factor -1), both <= 0. Writer: bufferOffset = 11 - 268,435,456 + 11 = -268,435,434, minus 2 for the last arc = -268,435,436, the index in the exception.

The exact boundary (a Z3 proof and an executed sweep): with last = Integer.MAX_VALUE, first = 0..7 fails and first = 8 or 9 builds. With first = 0 and last = Integer.MAX_VALUE, labelRange itself wraps to Integer.MIN_VALUE, so -ea stops at the assert (:541) and -da gives the same exception; the repro uses Integer.MAX_VALUE - 1 so both modes match.

• Who is hit. Code that builds an FST with FST.INPUT_TYPE.BYTE4 and uses labels as arbitrary non-negative ints (ids, hashes, ordinals, Integer.MAX_VALUE or MAX_VALUE - 1 as a sentinel), when one node with fixed-length arcs holds a label in [0, 7] and a label at least 2^31 - 8 higher.
• Who is not hit. Every in-tree BYTE4 FST uses Unicode code points (<= 0x10FFFF): SynonymMap, StemmerOverrideFilter and hunspell Dictionary. Postings and the terms index use BYTE1, and BYTE1/BYTE2 labels (at most 65,535) cannot span 2^31 - 8.
• What happens. compile() throws an unchecked ArrayIndexOutOfBoundsException (the repro), or add() does when a later key freezes such a node; the FST cannot be built.
• What does not happen. No corrupt FST is returned: for every wrapping input the presence-byte count is exactly -268,435,456, so the copy offsets go below zero before the node is written and a copy always throws. For the repro, and any such node whose arcs total less than about 256 MiB, it is the first copy, with no buffer growth; a node with larger arcs first grows the buffer (to less than its own arc bytes) and fails at a later copy. No hang.
• Default vs opt-in, scale. The builder's defaults trigger it; the opt-in part is using the FST API directly with BYTE4 and huge labels. Five keys suffice. Deterministic, assertions on and off.
• Workarounds. allowFixedLengthArcs(false) builds and finds every key (a smaller but slower FST, per its javadoc). directAddressingMaxOversizingFactor(-1) does not help. Keeping labels below 2^31 - 8 also avoids it.
• How likely. Rare: no report in the almost seven years since 8.4.0.

TestFSTByte4WideLabelSpan builds a BYTE4 FST with PositiveIntOutputs and the default builder, adds the five single-label keys 0, 1, 2, 3 and Integer.MAX_VALUE - 1 in order (output 1 each) and calls compile(). Five arcs is the smallest root that gets fixed-length arcs. Integer.MAX_VALUE - 1 rather than MAX_VALUE keeps labelRange itself from wrapping, so assertions on and off give the same exception. The try/catch turns the exception into an AssertionError that states expected and actual, with the original as its cause. Public API only (the test sits in org.apache.lucene.util.fst, like Lucene's own FST tests); no randomness of its own (seed DEADBEEF with assertions on and off, and 5EED1234 with assertions off, gave the same failure). It compiles on 9.1 and later.

As the regression test: this same test, for example as a new method in TestFSTDirectAddressing. With the fix it passes, and ./gradlew :lucene:core:check -x test passes with it as a new test file.

cp TestFSTByte4WideLabelSpan.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/fst/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.fst.TestFSTByte4WideLabelSpan -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same result)

TestFSTByte4WideLabelSpan > testNodeLabelsSpanningAlmostAllInts FAILED
    java.lang.AssertionError: expected compile() to build the FST, but it threw java.lang.ArrayIndexOutOfBoundsException: arraycopy: destination index -268435436 out of bounds for byte[11]
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:DD7E200A57D2D931]:0)
        at org.apache.lucene.util.fst.TestFSTByte4WideLabelSpan.testNodeLabelsSpanningAlmostAllInts(TestFSTByte4WideLabelSpan.java:34)

        Caused by:
        java.lang.ArrayIndexOutOfBoundsException: arraycopy: destination index -268435436 out of bounds for byte[11]
            at java.base/java.lang.System.arraycopy(Native Method)
            at org.apache.lucene.util.fst.GrowableByteArrayDataOutput.writeTo(GrowableByteArrayDataOutput.java:92)
            at org.apache.lucene.util.fst.FSTCompiler.writeNodeForDirectAddressingOrContinuous(FSTCompiler.java:751)
            at org.apache.lucene.util.fst.FSTCompiler.addNode(FSTCompiler.java:549)
            at org.apache.lucene.util.fst.FSTSuffixNodeCache.add(FSTSuffixNodeCache.java:154)
            at org.apache.lucene.util.fst.FSTCompiler.compileNode(FSTCompiler.java:388)
            at org.apache.lucene.util.fst.FSTCompiler.compile(FSTCompiler.java:1014)
            at org.apache.lucene.util.fst.TestFSTByte4WideLabelSpan.testNodeLabelsSpanningAlmostAllInts(TestFSTByte4WideLabelSpan.java:31)

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on; the same with assertions off.
# 10.6.0, 10.5.2 and 9.12.3: the same exception and index (10.5.2: FSTCompiler.java:750 <- addNode:548).

• The input is legal. FST.INPUT_TYPE: "Specifies allowed range of each int input label for this FST." (FST.java:68); BYTE4 has no narrower documented range. add() documents only the sort order (FSTCompiler.java:840-847). writeLabel writes BYTE4 labels as a vInt with only assert v >= 0 (:580-591), and the only reserved label is END_LABEL = -1 (FST.java:139). On #4769 (LUCENE-3695) a maintainer wrote "The INPUT_TYPE really describes the allowed range of the input int labels".
• The documented escape hatch fails. Builder.directAddressingMaxOversizingFactor: "Setting this factor to a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created." (FSTCompiler.java:321-322). The same javadoc scopes the factor to nodes already chosen for fixed-length arcs (:324-326), which this node is (it is not continuous). With -1 the node is still written with direct addressing (addNode:549) and the build throws (executed).
• The code assumes the range never wraps. assert labelRange > 0 (FSTCompiler.java:541) and assert labelRange >= 0 (FST.java:574) are internal invariants, not input limits. The first direct-array code (LUCENE-8781, 5c9e7d53511, 2019-05) checked labelRange > 0 explicitly; apache/lucene-solr#950 removed that encoding, and LUCENE-8920 brought direct addressing back with only the assert.
• Nearby inputs work. The span 2^31 - 9 builds and every lookup is right; the same five keys build with allowFixedLengthArcs(false) (executed). The failure is internal arithmetic, not a limit of the format.
• No sign of intent. The LUCENE-8920 thread (#9963) and the review of apache/lucene-solr#980 discuss the oversizing heuristic and the bit tables, never an int wrap; no upstream FST test uses BYTE4 labels near Integer.MAX_VALUE.

The strongest case for "not a bug" (the cross-model reviewer's, which it rated weak): the FST package is @lucene.experimental (FST.java:62, FSTCompiler.java:68), IntsRef is @lucene.internal (IntsRef.java:25), and the Builder javadoc describes BYTE4 as "full unicode codepoints" (FSTCompiler.java:253-255), so labels near Integer.MAX_VALUE could be called outside the intended use.

Why it fails: "experimental" marks the API as unstable, not this input as unsupported; IntsRef is the type add() itself takes; the code-point sentence says how strings are represented and states no upper bound, while INPUT_TYPE is documented as the allowed label range; and even if maintainers consider such spans unsupported, an explicit validation error (for example an IllegalArgumentException) would be clearer than an index error from internal arithmetic. Residual: a maintainer might prefer to document and reject such spans instead of falling back to binary search; that is a choice of fix (option D), and the repro would then use expectThrows.

Fix A was validated through gradle in a scratch worktree of 645d4fe14a20. It is the study verifier's patch with its comment reworded. B is an alternative shape, C a workaround for users today, D the option that narrows the contract.

In addNode, compute last - first + 1 as a long and only call shouldExpandNodeWithDirectAddressing when it is at most Integer.MAX_VALUE - 7; otherwise the node falls through to binary search.

--- a/lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java
@@ -537,15 +537,20 @@
       assert maxBytesPerArc > 0;
       // 2nd pass just "expands" all arcs to take up a fixed byte size
 
-      int labelRange = nodeIn.arcs[nodeIn.numArcs - 1].label - nodeIn.arcs[0].label + 1;
-      assert labelRange > 0;
-      boolean continuousLabel = labelRange == nodeIn.numArcs;
+      // BYTE4 labels can span more than an int: compute the range in 64 bits, and consider direct
+      // addressing only when its presence-byte count (labelRange + 7) >> 3 cannot overflow.
+      long labelRangeL = (long) nodeIn.arcs[nodeIn.numArcs - 1].label - nodeIn.arcs[0].label + 1;
+      assert labelRangeL > 0;
+      boolean labelRangeFits = labelRangeL <= Integer.MAX_VALUE - 7;
+      int labelRange = (int) labelRangeL; // only used when labelRangeFits or the node is continuous
+      boolean continuousLabel = labelRangeL == nodeIn.numArcs;
       if (continuousLabel && version >= FST.VERSION_CONTINUOUS_ARCS) {
         writeNodeForDirectAddressingOrContinuous(
             nodeIn, maxBytesPerArcWithoutLabel, labelRange, true);
         continuousNodeCount++;
-      } else if (shouldExpandNodeWithDirectAddressing(
-          nodeIn, maxBytesPerArc, maxBytesPerArcWithoutLabel, labelRange)) {
+      } else if (labelRangeFits
+          && shouldExpandNodeWithDirectAddressing(
+              nodeIn, maxBytesPerArc, maxBytesPerArcWithoutLabel, labelRange)) {
         writeNodeForDirectAddressingOrContinuous(
             nodeIn, maxBytesPerArcWithoutLabel, labelRange, false);
         directAddressingNodeCount++;

Trade-offs

• No format or reader change: such a node becomes a binary-search node. With the true size (268,435,456 bytes for the repro's node, against 35 bytes for binary search) the heuristic would reject direct addressing anyway.
• Nothing changes for nodes whose span is below 2^31 - 8, so BYTE1, BYTE2 and code-point FSTs are untouched. Factor -1 then behaves as documented for these nodes.
• A continuous node's span equals its arc count, so the int cast is safe there. One long subtraction per fixed-length node at build time; no read-path cost.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, 2026-11-01: without the fix the repro fails with assertions on and off; with it, it passes with assertions on and off.
• Every core test class in org.apache.lucene.util.fst with the fix: 9 classes, 38 tests, 0 failures, 5 skipped (including TestFSTs 22, TestFSTDirectAddressing 3 and the repro).
• analysis-common TestSynonymGraphFilter (56) and TestStemmerOverrideFilter (5), two in-tree BYTE4 builders: 61 tests, 0 failures.
• ./gradlew :lucene:core:check -x test with the fix and the repro as a new test file: passes (google-java-format, ecj lint of main and test code, forbidden APIs; error-prone skipped). The full Lucene test suite was not run.
• Earlier, with the same logic shadowed into the stock jars: 4 supporting checks pass with assertions on and off (factor -1 and the default builder build and every key is found; two controls), and the cross-model reviewer's own tests, TestFSTDirectAddressing and TestFSTs pass.

Compute the label range and the direct-addressing size as long in shouldExpandNodeWithDirectAddressing and getNumPresenceBytes, so the heuristic sees the true 256 MiB and rejects the node. Not validated.

Trade-offs

• A single size check instead of a special case, but it changes two signatures and still needs a guard for the full span (first 0, last Integer.MAX_VALUE), whose range 2^31 cannot be written as the node header's int (FSTCompiler.java:771).
• Option A gives the same encoding for every node with less code.

Not a fix. The five keys build and every key is found (executed); the FST is smaller but slower to traverse, per the javadoc. directAddressingMaxOversizingFactor(-1) is not a workaround (executed).

Trade-offs

Slower lookups for every node of the FST, not only the wide one.

Throw an IllegalArgumentException for a node whose labels span 2^31 - 8 or more.

Trade-offs

Narrows the BYTE4 label range that INPUT_TYPE documents, although the encoder already has a valid fallback (binary search).

• Method: SMT (Z3) over bit-vector and float arithmetic, the study's formal tier (2026-10-22, main 7cecf79523). The model transcribes the fixed-length-arc encoding decision: the label range, the presence-byte count, the binary-search and direct-addressing sizes, the oversizing factor and the credit rule.
• Q1 asked whether direct addressing can be chosen with a size that does not match the real table: SAT in 0.63 s, the first query run, with first label 6, last label Integer.MAX_VALUE and 5 arcs. Q2 proved the trigger is exactly last - first >= 2^31 - 8. Q3/Q4 proved the direct-addressing size arithmetic exact, whenever direct addressing is chosen, for BYTE1, BYTE2 and smaller BYTE4 spans, within the model's bounds (up to 65,536 arcs, 4,096 bytes per arc, any factor).
• Witness: the counterexample became a JUnit on the stock jar; an independent verifier wrote its own 8-test JUnit (5 fail, 3 controls pass) and a boundary sweep that matched Q2 exactly.
• Later: reruns on two later mains (b83101cdd2, a9779ef3c193), a one-test minimal repro (2026-10-29), a candidate re-verification and a cross-model review (2026-11-01), an executed history sweep over every release from 7.7.3 to 10.6.0, and this doc's gradle validation.