IntsRefFSTEnum.seekCeil returns a term below the target when a negative int follows a term prefix

IntsRefFSTEnum.seekCeil promises the "smallest term that's >= target" (IntsRefFSTEnum.java:59 at 5adff78bb168), and IntsRef order is signed (IntsRef.java:104-114), so in a BYTE4 FST {[5] -> 1, [5, 3] -> 2} the ceiling of [5, Integer.MIN_VALUE] is [5, 3]. A fresh enum returns [5], a key below the target, with no exception and with assertions on or off. Inside the FST, the node after a key that is also a prefix of longer keys starts with a "fake" arc labelled FST.END_LABEL = -1 (FST.java:697-712). getTargetLabel hands the seek scan the target's raw int (IntsRefFSTEnum.java:91-98), and the scan compares it with that arc as if it were a normal label (FSTEnum.java:274-288): -1 is equal, any lower int is smaller, and either way the seek stops at the prefix. seekFloor and seekExact go wrong the same way. On a fresh enum, no target without a negative int was answered wrongly in the checks run (the separate LFV-1147 overflow on a reused enum aside). The code dates from 2011 (LUCENE-2843) and is in every release from 3.3 to 10.6.0. No Lucene code path seeks an IntsRefFSTEnum, and FST labels must be >= 0 (asserted when the FST is built), so only application-built seek targets reach it.

1. seekCeil stores the target and calls doSeekCeil (IntsRefFSTEnum.java:60-65); nothing checks the target's ints. getTargetLabel returns FST.END_LABEL once the target is used up and otherwise the raw int (IntsRefFSTEnum.java:91-98).
2. After matching label 5, the scan reads the next node with readFirstTargetArc (FSTEnum.java:285). Because [5] is a key, the arc is final, and readFirstTargetArc inserts a "fake" first arc with label END_LABEL = -1 (FST.java:697-712; FST.java:138-139: "If arc has this label then that arc is final/accepted"). The real arc 3 follows it.
3. The scan loop sends this end arc to the list scan (FSTEnum.java:147 and :159). doSeekCeilList (FSTEnum.java:274-288) compares the end arc's label -1 with the target int. For MIN_VALUE, -1 > MIN_VALUE takes the "ceiling found" branch (:286-288) and calls pushFirst(), which stops at once on an END_LABEL arc (:714-716): the enum is left on [5]. A target int of exactly -1 matches the arc (:277-282) and also ends on [5].
4. seekFloor: the walk-back in doSeekFloorList (FSTEnum.java:600-624) looks for an arc with a label below the target int and never finds the end arc below an int < -1, so it backs up past [5] (null here, or a smaller key). seekExact: findTargetArc(-1, ...) (FSTEnum.java:663) matches the end arc, and :674 reports success. With assertions on, assert upto == 1 + target.length (IntsRefFSTEnum.java:84) fires instead.
5. The same -1 shows outside the enum (context; fix A does not change it): Util.get passes each int to FST.findTargetArc (Util.java:47-67), which treats END_LABEL as a request for the end-of-key arc (FST.java:1013-1029), so Util.get(fst, [5, -1, 3]) returns 2, the output of [5, 3], instead of null, with assertions on and off.

A bounded-exhaustive check against a TreeMap oracle (8,191 BYTE4 FSTs over labels {0, 1, 2}, every target over {MIN, -2, -1, 0, 1, 2, 3, MAX} up to length 3, all three seeks, plus list, continuous, direct-addressing and binary-search node encodings; a fresh enum per seek; 14,376,393 checks): 0 mismatches for targets without a negative int, including positive ints outside the alphabet; mismatches exactly when the first negative int follows a prefix that is a key: seekCeil for every negative int, seekFloor for ints below -1, seekExact for -1; 0 mismatches when that prefix is not a key; the same for all four encodings. With fix A: 0 mismatches.

• Who. Application code that builds its own FST and seeks an IntsRefFSTEnum with a target that holds a negative int right after a prefix that is itself a key: for example Integer.MIN_VALUE as "the smallest possible next label" in a ceil-based prefix scan, or a -1 "unknown" sentinel. Two keys suffice; default FSTCompiler settings; no scale.
• Effect. A silent wrong lookup: a ceiling below its target, a floor that skips an existing key, an exact match for a key that is not there (assertions off). Ceiling and floor are wrong with assertions on too.
• Not affected. No Lucene code path: the only non-test IntsRefFSTEnum user, hunspell WordFormGenerator, calls only next() (WordFormGenerator.java:68-71 in lucene/analysis/common). BytesRefFSTEnum cannot hit it: its target labels are bytes & 0xFF (BytesRefFSTEnum.java:96). In the checks (a fresh enum per seek), targets without a negative int, and a negative int after a prefix that is not a key, were answered correctly; the separate LFV-1147 overflow on a reused enum aside.
• Opt-in part. IntsRefFSTEnum, FSTEnum and FST are @lucene.experimental (IntsRefFSTEnum.java:26, FSTEnum.java:28, FST.java:62).
• Likelihood: contrived. No valid key contains a negative int, no caller found builds such a target, and no public report of it was found since 2011. It is deterministic, though: whoever builds such a target after a key prefix gets the wrong answer every time.

TestIntsRefFSTEnumNegativeTarget (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, the type the enum's seek methods take. It builds {[5] -> 1, [5, 3] -> 2} with FSTCompiler.Builder(BYTE4, PositiveIntOutputs) and asserts that seekCeil([5, Integer.MIN_VALUE]) on a fresh enum returns [5, 3].

The target uses Integer.MIN_VALUE rather than -1 on purpose: -1 is the value of FST.END_LABEL, and any int below -1 shows the same wrong answer without it. As the regression test, the same method fits in TestFSTs. seekFloor([5, -7]) (null instead of [5]) and seekExact([5, -1, 9]) ([5] instead of null, assertions off) show the same defect and have no tests of their own here.

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

TestIntsRefFSTEnumNegativeTarget > testSeekCeilNegativeIntAfterTermPrefix FAILED
    java.lang.AssertionError: expected:<[5 3]> but was:<[5]>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:E60ACA35E1B7E3E0]: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.TestIntsRefFSTEnumNegativeTarget.testSeekCeilNegativeIntAfterTermPrefix(TestIntsRefFSTEnumNegativeTarget.java:32)

(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"; :76: "Seeks to exactly this term, returning null if the term doesn't exist". None states a precondition on the target's ints. The package doc says the enumerators "behave like SortedMap iterators" (package-info.java:30-32), and IntsRef.compareTo is "Signed int order comparison" (IntsRef.java:104), so the expected answers are well defined for every IntsRef.
• Other off-alphabet targets work. BYTE1 seekCeil([5, 300]), BYTE4 Integer.MAX_VALUE and every positive out-of-alphabet target of the exhaustive check were answered correctly. No mismatch was found for them in that corpus or those probes, which fits the mechanism: the -1 marker sits below every int >= 0 and at or above every negative int.
• Tests. FSTTester (test framework) checks IntsRefFSTEnum seeks against the sorted key list (FSTTester.java:420-484), but only with in-alphabet targets, so it never reaches this case.
• History. The marker, the fake end arc and the raw-int getTargetLabel all arrived together in 1cab313a2b8 (LUCENE-2843, 2011); its issue (#3917) does not discuss negative seek targets. Dawid Weiss remarked in 2011 that END_LABEL "makes having -1 label on a transition impossible" (commit 931c8294064) and that marker values from the domain range made them nervous (#4370): a design concern about labels, not a decision about seek targets.

The strongest case for "intended" (made by the cross-model reviewer): INPUT_TYPE "Specifies allowed range of each int input label for this FST" (FST.java:68); BYTE4 represents strings as "full unicode codepoints" (FSTCompiler.java:253-255); FSTCompiler asserts v >= 0 and label >= 0 (FSTCompiler.java:581, :1109); END_LABEL = -1 is public, and findTargetArc treats it as the end-of-key marker on purpose (FST.java:1013-1029); the class is experimental with no in-tree seek caller. So a negative target int is garbage in.

Our answer, a judgement call the code does not settle: those lines describe the labels an FST is built from and how arcs are marked, not seek targets, and a ceiling or floor target is normally not a key. The label rule is a build-time Java assert and is never checked on the seek path. Ints below -1 are not END_LABEL and fail too. And "unsupported input" would justify an IllegalArgumentException, not a ceiling below its target. The independent reproducer, the devil's-advocate verifier and the tie-breaker rejected the case; the adjudication called the bug disputed only on this question, and the cross-model reviewer was not persuaded. Whether negative targets are in contract is the maintainer's call; if they are not, this is a hardening request, and fixes B and C fit.

Fix A was built and checked through gradle on 5adff78bb168; B and C were not run. The hunt's first version of fix A had one comment line over 100 columns, which failed checkGoogleJavaFormat; the version here only shortens its two comments. Open PR #14477 ("Use Arrays#mismatch in FSTEnum#rewindPrefix", a performance change) edits FSTEnum.java and adds a getMismatch override to IntsRefFSTEnum.java on other lines; it keeps the fresh-enum path of this repro and neither causes nor fixes it. The sibling LFV-1147 (a reused enum after a key with label Integer.MAX_VALUE) has its own one-line fix in FSTEnum.rewindPrefix; this repro still fails with that fix in place. Util.get has the same -1 collision (Util.get(fst, [5, -1, 3]) returns 2); none of the three options changes it.

In the three seek methods of IntsRefFSTEnum, find the first negative int of the target. Because every key label of a valid FST is >= 0 (FSTCompiler asserts it), a target p ++ [x] ++ rest with x < 0 has the same ceiling as p ++ [0], the same floor as p, and no exact match. So seekCeil seeks p ++ [0], seekFloor seeks p, and seekExact returns null. +25 lines, one file.

diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/IntsRefFSTEnum.java b/lucene/core/src/java/org/apache/lucene/util/fst/IntsRefFSTEnum.java
index a14c135dc3c..1582b6eefeb 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/IntsRefFSTEnum.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/IntsRefFSTEnum.java
@@ -58,6 +58,13 @@ public final class IntsRefFSTEnum<T> extends FSTEnum<T> {
 
   /** Seeks to smallest term that's &gt;= target. */
   public InputOutput<T> seekCeil(IntsRef target) throws IOException {
+    // FST labels are >= 0, so p ++ [x] ++ rest with x < 0 has the same ceiling as p ++ [0]
+    int neg = firstNegative(target);
+    if (neg != -1) {
+      int[] ints = ArrayUtil.copyOfSubArray(target.ints, target.offset, target.offset + neg + 1);
+      ints[neg] = 0;
+      target = new IntsRef(ints, 0, ints.length);
+    }
     this.target = target;
     targetLength = target.length;
     super.doSeekCeil();
@@ -66,6 +73,11 @@ public final class IntsRefFSTEnum<T> extends FSTEnum<T> {
 
   /** Seeks to biggest term that's &lt;= target. */
   public InputOutput<T> seekFloor(IntsRef target) throws IOException {
+    // FST labels are >= 0, so p ++ [x] ++ rest with x < 0 has the same floor as p
+    int neg = firstNegative(target);
+    if (neg != -1) {
+      target = new IntsRef(target.ints, target.offset, neg);
+    }
     this.target = target;
     targetLength = target.length;
     super.doSeekFloor();
@@ -78,6 +90,10 @@ public final class IntsRefFSTEnum<T> extends FSTEnum<T> {
    * found.
    */
   public InputOutput<T> seekExact(IntsRef target) throws IOException {
+    if (firstNegative(target) != -1) {
+      // no term has a negative label
+      return null;
+    }
     this.target = target;
     targetLength = target.length;
     if (doSeekExact()) {
@@ -88,6 +104,15 @@ public final class IntsRefFSTEnum<T> extends FSTEnum<T> {
     }
   }
 
+  private static int firstNegative(IntsRef target) {
+    for (int i = 0; i < target.length; i++) {
+      if (target.ints[target.offset + i] < 0) {
+        return i;
+      }
+    }
+    return -1;
+  }
+
   @Override
   protected int getTargetLabel() {
     if (upto - 1 == target.length) {

Trade-offs

Preserves the tested behaviour for FSTs that satisfy the non-negative-label invariant, and changes nothing for targets without a negative int. It adds an extra O(target length) scan per seek, which the seek itself may not need: a seek stops at the first label where the target leaves the FST (FSTEnum.java:286-306), and seekExact short-circuits (:664-670), as its javadoc says (IntsRefFSTEnum.java:76-78); not benchmarked. It allocates once only when a negative int is present. A seekExact rejected this way leaves the enum at its previous position; the javadoc does not specify the position after a miss either way. No negative target int reaches FSTEnum's label comparisons any more; the internal END_LABEL (-1) that getTargetLabel returns at the end of the target still does (IntsRefFSTEnum.java:93-94). Caveat: the label rule is only a Java assert (FSTCompiler.java:581, :1109). With assertions off, FSTCompiler accepts a negative label (a BYTE4 key [-2] was built and found by Util.get and next(); with assertions on the build fails). On such an FST, outside the documented label range, main's seekExact([-2]) matches the -2 arc (by FST.findTargetArc), while fix A returns null (fix B would throw). The repro's FST has only labels 5 and 3, so its assertions-off runs build a valid FST and only the seek differs. Fix A is sound for FSTs built within the label range; a maintainer may prefer B, or a build-time check that does not rely on asserts.

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, every org.apache.lucene.util.fst test class in core ran: the repro, TestFSTs (22, which runs FSTTester's random IntsRefFSTEnum seeks), TestUtil 5, TestFSTDirectAddressing 3 and 5 more classes: 38 tests, 0 failures, 5 skipped (among them both 2B tests). :lucene:core:checkGoogleJavaFormat passes with the fix and the repro in place. 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 change pass the repro (assertions on and off), the independent reproducer's and the cross-model reviewer's own tests, and the 14,376,393-check exhaustive probe (0 mismatches).

Throw IllegalArgumentException from seekCeil, seekFloor and seekExact when a target int is negative.

Trade-offs

The same scan cost as A; a loud failure instead of a silent wrong answer; changes behaviour for any caller that passes such ints today (none in tree). Not run.

Add a javadoc line to the three seek methods (or the class) saying that target ints must be >= 0.

Trade-offs

No code change; the silent wrong answer stays for callers who miss the line. A documentation-only resolution is a possible maintainer answer. Not run.

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

• The finder checked IntsRefFSTEnum's seeks against the obligation that, for every IntsRef target, seekCeil, seekFloor and seekExact return the SortedMap answers in signed IntsRef order, and found that getTargetLabel's raw int is compared with the end-of-key arc's label -1.
• The finder wrote a JUnit test (target [5, -1]) and the boundary fix; the adjudication replaced -1 with Integer.MIN_VALUE so the target does not contain END_LABEL, and a final repro check kept that single method.
• An independent reproducer, an executed cross-model review and a devil's-advocate verifier reproduced it with their own tests; the tie-breaker added the bounded-exhaustive check ("Prior reports, history and checks").