A reused IntsRefFSTEnum returns a wrong seekCeil/seekFloor after a term with label Integer.MAX_VALUE

IntsRefFSTEnum.seekCeil and seekFloor begin with FSTEnum.rewindPrefix(), which keeps the part of the current term that the new target shares and decides, label by label, whether to seek forward or reset to the node's first arc. It decides with final int cmp = getCurrentLabel() - getTargetLabel(); (FSTEnum.java:79 at 5adff78bb168). Once the target is used up, getTargetLabel() returns FST.END_LABEL, -1 (IntsRefFSTEnum.java:91-97). If the current label there is Integer.MAX_VALUE, a legal BYTE4 label, 2147483647 - (-1) wraps to Integer.MIN_VALUE, the code takes the "seek forward" branch and keeps the MAX arc. In the BYTE4 FST {[3] -> 1, [3, MAX] -> 2}, an enum positioned on [3, MAX] answers seekCeil([3]) with [3, MAX] and seekFloor([3]) with null; a fresh enum answers both correctly. The line dates from 2011 (LUCENE-2843) and is in every release from 3.3 to 10.6.0. No Lucene component builds a BYTE4 FST with that label; the fix is one Integer.compare.

1. IntsRefFSTEnum.seekCeil (IntsRefFSTEnum.java:60-65) stores the target and calls doSeekCeil, which first calls rewindPrefix() (FSTEnum.java:136) "to match the shared prefix between current term and target term" (:66).
2. rewindPrefix (FSTEnum.java:67-94) walks positions upto = 1, 2, ... of the current term and at :79 (the fix site) computes cmp = getCurrentLabel() - getTargetLabel(). cmp < 0 ("seek forward") breaks and keeps the current arc (:80-83); cmp > 0 ("seek backwards") resets this position to the node's first arc (:84-89).
3. Current term [3, MAX], target [3]. Position 1: 3 - 3 = 0, go on. Position 2: the target is used up, so getTargetLabel() returns FST.END_LABEL = -1 (IntsRefFSTEnum.java:93-94; FST.java:139). The right answer is MAX > -1, reset. But 2147483647 - (-1) = 2147483648 does not fit in an int and wraps to -2147483648, so cmp < 0 and the MAX arc is kept.
4. doSeekCeil's scan (FSTEnum.java:139-161) continues from the kept arc with target label -1. On this list-encoded node doSeekCeilList sees label MAX > -1 and calls pushFirst() (:286-288), which completes [3, MAX]. After a reset, the node's first arc would be the final (END_LABEL) arc, which matches -1 and gives [3].
5. doSeekFloor calls the same rewindPrefix (:328): seekFloor([3]) returns null (executed). doSeekExact also calls it (:653) but then finds the arc with findTargetArc, so seekExact is correct (executed). Positioning on [3, MAX] with two next() calls instead of seekCeil triggers it too (executed).

The labels an FST stores are >= 0 (asserted in FSTCompiler.java:581 and :1109; Java asserts only, so nothing checks it with assertions off), and a target made of such labels adds only END_LABEL = -1 as a negative value, so the subtraction can overflow only for Integer.MAX_VALUE - (-1). With label 0x7ffffffe the same reused-enum sequence is correct: reusedCeil=[3]/1 reusedFloor=[3]/1; with 0x7fffffff: reusedCeil=[3 7fffffff]/2 reusedFloor=null. BytesRefFSTEnum labels are 0-255 and cannot overflow.

Out-of-range targets. seekCeil/seekFloor do not check the target: getTargetLabel() returns the caller's own ints (IntsRefFSTEnum.java:96), and no javadoc states a label range for seek targets. A target label at least 2^31 below the current label wraps the same line. On the BYTE4 FST {[1] -> 1, [3] -> 2} (no MAX label), an enum first positioned by seekCeil([3]) answers seekCeil([Integer.MIN_VALUE]) and seekCeil([-2147483645]) with [3]/2, while a fresh enum gives [1]/1; -2147483644 (no wrap) is correct; the Integer.compare line fixes both (executed). A side remark, not a second repro.

• Who. Application code that builds its own BYTE4 FST containing the label Integer.MAX_VALUE and reuses one IntsRefFSTEnum to seekCeil or seekFloor to a proper prefix of its current term whose next label is that MAX label. Two keys suffice; no scale, default settings. Outside the label range, also code that seeks a reused IntsRefFSTEnum with a target holding a huge negative label (seekCeil, executed).
• Effect. A silent wrong lookup: seekCeil returns a term (and its output) that is not the ceiling; seekFloor returns null for a target that exists. Same with assertions on and off.
• Not affected. Lucene's BYTE4 FSTs hold code points <= 0x10FFFF (SynonymMap.java:244, StemmerOverrideFilter.java:214, hunspell Dictionary.java:648 in lucene/analysis/common). The only non-test IntsRefFSTEnum user, hunspell WordFormGenerator.java:68-71, calls next() only. The codecs' term readers use BytesRefFSTEnum (byte labels). A fresh enum and seekExact are correct.
• Opt-in part. FST, FSTCompiler and IntsRefFSTEnum are @lucene.experimental (FST.java:62, FSTCompiler.java:68, IntsRefFSTEnum.java:26).
• Likelihood: rare. No caller found does it and no public report of it was found since 2011. It is deterministic, though: whoever uses MAX as a label, reuses the enum and then seeks to a proper prefix whose next current label is MAX gets the wrong answer every time; other in-range seeks after a MAX term compare without overflow.

TestFSTEnumSeekAfterMaxLabel (one method, extends LuceneTestCase, package org.apache.lucene.util.fst of the lucene/core tests). It uses the public FSTCompiler, FST and IntsRefFSTEnum and builds its keys as IntsRef, which is @lucene.internal but is the type the enum's seek methods take. It builds {[3] -> 1, [3, Integer.MAX_VALUE] -> 2} with FSTCompiler.Builder(BYTE4, PositiveIntOutputs), calls seekCeil([3, MAX]) and then asserts that seekCeil([3]) on the same enum returns [3].

As the regression test, the same method fits in TestFSTs. seekFloor([3]) on the same enum returns null too; the test asserts only the seekCeil result. IntsRef.toString prints labels in hex, so 7fffffff is Integer.MAX_VALUE.

cp $REPRO/TestFSTEnumSeekAfterMaxLabel.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/fst/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.fst.TestFSTEnumSeekAfterMaxLabel -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: the same failure

TestFSTEnumSeekAfterMaxLabel > testSeekCeilToPrefixAfterMaxLabel FAILED
    java.lang.AssertionError: expected:<[3]> but was:<[3 7fffffff]>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:40F03DFA408425C1]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:120)
        at org.junit.Assert.assertEquals(Assert.java:146)
        at org.apache.lucene.util.fst.TestFSTEnumSeekAfterMaxLabel.testSeekCeilToPrefixAfterMaxLabel(TestFSTEnumSeekAfterMaxLabel.java:36)

(gradle on main 5adff78bb168, seed DEADBEEF, assertions on; with -Ptests.asserts=false the same assertion)

• Contract. IntsRefFSTEnum.java:59: "Seeks to smallest term that's >= target"; :67: "Seeks to biggest term that's <= target". The package doc says the enumerators "behave like SortedMap iterators" (package-info.java:30-32) and "Like TermsEnum, this also supports seeking (advance)" (:73).
• Legal label. FST.java:68: INPUT_TYPE "Specifies allowed range of each int input label for this FST". FSTCompiler.writeLabel asserts BYTE1 <= 255 and BYTE2 <= 65535 but for BYTE4 only v >= 0, written as a vInt (FSTCompiler.java:580-590; Java asserts, not run-time checks). Input order is IntsRef.compareTo, a signed Arrays.compare (IntsRef.java:106-107), so MAX is just the largest label. Michael McCandless described the input type the same way on LUCENE-3695 (#4769): "The "INPUT_TYPE" really describes the allowed range of the input int labels", and "FST is just like a SortedMap".
• Backward seeks. rewindPrefix exists to reuse the current position and has a "seek backwards -- reset this arc to the first arc" branch (FSTEnum.java:84-89). FSTTester in the test framework reuses one IntsRefFSTEnum for seekCeil, seekFloor and seekExact on random targets in random order (FSTTester.java:420-520), only with byte and code-point labels, so it never reaches the overflow.
• History. Before LUCENE-2843 the forward-only advance(target) (never released) said "NOTE: target must be >= where we are already positioned"; LUCENE-2843 replaced it with seekCeil/seekFloor without such a note. No commit, issue or PR since calls the subtraction deliberate.

The strongest case for "intended": the Builder javadoc says strings are represented as BYTE4 "full unicode codepoints" (FSTCompiler.java:253-255), every in-tree BYTE4 FST stays <= 0x10FFFF, the API is @lucene.experimental, and IntsRef itself is @lucene.internal (IntsRef.java:25); so labels near 2^31 are off-label.

Why it fails: the same javadoc says the input type "Can be anything from INPUT_TYPE enumeration"; the code-points sentence is an example of use, and no narrower BYTE4 range is documented or enforced. @lucene.experimental allows API changes, not wrong answers; IntsRefFSTEnum's public seek methods take an IntsRef, so every caller of them builds one; and the failure is silent rather than a clear rejection. The cross-model reviewer rated this case moderate and rejected it, as did the independent reproducer, the devil's-advocate verifier and the adjudication. A maintainer who prefers to restrict labels has fix B.

Fix A was built and checked through gradle on 5adff78bb168; B was not run. Open PR #14477 ("Use Arrays#mismatch in FSTEnum#rewindPrefix", a performance change) keeps getCurrentLabel() - getTargetLabel() for the first mismatching label, so the same change belongs there if it lands first. Open PR #12688 copies the compare into a new PrimitiveLongFSTEnum that only sees byte labels and cannot overflow, so a change there would only be for consistency. Scope: fix A covers the in-range case (MAX against END_LABEL) and the executed out-of-range negative-target case (a list-encoded root node). On array-encoded nodes the seek code does more label arithmetic on the target (FSTEnum.java:166, :196, :362, :393, :507, :529; FST.java:1047, :1068, :1085; Util.java:917), which was not tested with such targets; whether seek targets must hold labels >= 0 is for the maintainers to state, as nothing documents or checks it today.

In FSTEnum.rewindPrefix (FSTEnum.java:79), replace the subtraction with Integer.compare.

-      final int cmp = getCurrentLabel() - getTargetLabel();
+      final int cmp = Integer.compare(getCurrentLabel(), getTargetLabel());

Trade-offs

No functional change for any pair of labels that does not overflow: the sign is the same as before. Not benchmarked; the JMH FSTEnumSeekBenchmark of open PR #16095 could measure it.

What the checks validated

• Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on, and -Ptests.asserts=false) and passes with it (both).
• With the fix, the org.apache.lucene.util.fst test classes in core (the repro, TestFSTs 22, TestUtil 5, TestFSTDirectAddressing 3 and 5 more classes) and, in codecs, TestFSTPostingsFormat, TestVarGapDocFreqIntervalPostingsFormat, TestVarGapFixedIntervalPostingsFormat and TestUniformSplitPostingFormat (30 each, 2 skipped each) ran, plus TestSimpleTextPostingsFormat, which is @Nightly, so all 30 of its tests were skipped: 188 tests, 0 failures, 43 skipped (also both 2B tests), so 145 ran and passed. checkGoogleJavaFormat on core passes. These suites are regression evidence only: the codec suites use BytesRefFSTEnum (labels 0-255), which cannot reach the overflow. The full core suite was not run, and only OpenJDK 25.0.3 on Linux aarch64 was used.
• Earlier: the hunt's shadow-class runs of the same line pass the repro (assertions on and off); the independent reproducer's and the cross-model reviewer's own tests pass with it; on the 3.3.0 jar the same one-line change turns the failure into a pass.
• The fact check's out-of-range probe (seekCeil([Integer.MIN_VALUE]) on a reused enum over {[1], [3]}) gives [1]/1 with the fix, as a fresh enum does (executed, assertions off).

Document BYTE4 labels as < Integer.MAX_VALUE (or as code points) and reject larger labels in FSTCompiler.

Trade-offs

An API restriction instead of a bug fix: it breaks applications that already use MAX, does nothing for FSTs already written with it, and is more code than A.

What the checks validated

Not run.

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

• The finder checked rewindPrefix against the obligation that seekCeil/seekFloor on a reused enum equal the fresh-enum answer for every label BYTE4 accepts (any v >= 0) and found that cmp = getCurrentLabel() - getTargetLabel() changes sign for Integer.MAX_VALUE - (-1).
• The finder then wrote a JUnit test and the one-line Integer.compare fix that makes it pass; the repro was later cut to a single method with two keys.
• An independent reproducer, an executed cross-model review and a devil's-advocate verifier reproduced it with their own tests, and an adjudication re-ran the finder's and the reproducer's tests ("Prior reports, history and checks").
• The audit took target labels to be >= 0 as well. The doc's fact check later ran a reused enum with a huge negative target label (Integer.MIN_VALUE) and showed that it wraps the same line; the same fix covers that run.