Util.readCeilArc returns a wrong arc or null when follow and arc are the same Arc object

Util.readCeilArc(label, fst, follow, arc, in) reads "the first arc greater or equal than the given label into the provided arc in place" (Util.java:810 at 5adff78bb168) from the arcs leaving follow. It first calls fst.readFirstTargetArc(follow, arc, in) (:827), which writes the first arc of follow's target node into arc. When follow and arc are the same object, follow now describes that child arc. The fixed-length branches (:828-871) read only arc's node header and still answer correctly, but a list-encoded node falls through to fst.readFirstRealTargetArc(follow.target(), arc, in) (:875), and follow.target() is by then the child's target, so the scan runs over the node one level down. For the one-key FST ab, the aliased call on the start arc returns b instead of a, silently, with assertions on and off; with keys ab, ac, x the ceiling of 'w' is null instead of x; with a final start arc, or (keys x) when the root's first arc has no outgoing arcs, the call reads FST address -1 and throws ArrayIndexOutOfBoundsException. The two lines date from the method's first version (LUCENE-3846, released in 4.1.0). No Lucene production code passes the same object twice; the two test calls that do pass leaf arcs, where the method returns early.

1. Util.java:824-826: if follow has no target arcs, return null. Leaf arcs stop here.
2. Util.java:827: fst.readFirstTargetArc(follow, arc, in) writes the first arc of follow's target into arc (FST.java:687-692, "this changes the provided arc (2nd arg) in-place"). With follow == arc, follow is now that child arc. readFirstTargetArc itself reads each field of follow before it overwrites that field, so it is alias-safe.
3. A list-encoded node gets bytesPerArc = 0 (FST.java:738-741), so the if at Util.java:828 is skipped. The fixed-length branches inside it (direct addressing, continuous, binary search) read only arc's node header and are unaffected.
4. Util.java:875 (the fix site): fst.readFirstRealTargetArc(follow.target(), arc, in). follow.target() is now the child's target, so the linear scan (:877-887) runs over the node one level down and returns its first arc >= label, or null. If that child arc has no outgoing arcs (it ends a key and nothing continues past it, so its target() is FINAL_END_NODE, -1), :875 reads address -1 and throws as in step 5, although the start arc is not final.
5. Final follow: readFirstTargetArc turns the shared object into the virtual END arc with target = FINAL_END_NODE (FST.java:697-708; FINAL_END_NODE = -1, FST.java:132). The END label skips the if at :828, and :875 reads address -1: ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 32768 at ReverseBytesReader.readByte:30 <- FST.readFirstArcInfo:722 <- FST.readFirstRealTargetArc:746 <- Util.readCeilArc:875 (executed on an on-heap FST with a list-encoded root, and also with a continuous and a binary-search root: a final follow throws whatever the encoding).

• Keys ab (the repro): aliased ceiling of 'a' on the start arc is b (98) instead of a (97).
• Keys ab, ac, x (root list-encoded, bytesPerArc 0): distinct arcs give a for 'a' and x for 'w'; aliased gives b and null.
• Keys "", ab (final start arc): distinct arcs give a; aliased throws the index -1 exception.
• Keys x (start arc not final; the root's one arc x ends the key, target() -1): distinct arcs give x for 'a'; aliased throws the same index -1 exception. Keys a, b: the same.
• Keys ab, ac, b, c, d, e (5 root arcs): with default settings the root is fixed-length (bytesPerArc 2) and the aliased call gives a; with allowFixedLengthArcs(false) it is a list (bytesPerArc 0) and gives b. (The keys above give a list root with either setting.)

When a node is list-encoded: FSTCompiler uses fixed-length arcs only for nodes with >= 5 arcs at depth <= 3 or >= 10 arcs anywhere (FSTCompiler.java:77-87, :601-606), so with default settings most small nodes are lists.

• Who. Application code that calls Util.readCeilArc directly and passes one Arc object as both follow and arc on a non-leaf arc whose target node is list-encoded, or that is final. Default FSTCompiler settings, tiny input (one key in the repro); no scale or configuration needed.
• Not affected. Lucene's two non-test callers pass distinct objects: FSTTermsReader.java:675 (lucene/codecs, top.fstArc and frame.fstArc) and FSTUtil.java:105 (lucene/suggest, path.fstNode and scratchArc). The downstream callers found by code search (for example Apache Pinot's RegexpMatcher) also pass distinct arcs.
• Effect. A wrong arc, taken from the wrong level, or null, silently: a walk built on it takes a wrong path or stops early. Or an ArrayIndexOutOfBoundsException (index -1) when follow is final or when the first arc of its target node has no outgoing arcs (for example the one-key FST x). Same with assertions on and off.
• Opt-in part. Util is marked @lucene.experimental (Util.java:38-42); the trigger is the caller's own aliasing.
• Likelihood: rare. No caller found does it and no prior report was found, but whoever does it gets a wrong answer for most labels on a list-encoded node: for the one-key FST ab, 67 of the 95 printable ASCII labels (the scan of the wrong node gives the right answer only by coincidence).

TestReadCeilArcSameFollowAndArc (one method, extends LuceneTestCase, package org.apache.lucene.util.fst of the lucene/core tests). It builds the FST with FSTCompiler.Builder(BYTE1, NoOutputs) and default settings, takes the start arc and asserts that Util.readCeilArc('a', fst, arc, arc, in) returns label 'a'.

As the regression test, the same method fits in TestUtil. Line 12 is longer than 100 characters, which ./gradlew tidy reformats.

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

TestReadCeilArcSameFollowAndArc > testSameFollowAndArc FAILED
    java.lang.AssertionError: expected:<97> but was:<98>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:E0B3699405501700]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.junit.Assert.assertEquals(Assert.java:633)
        at org.apache.lucene.util.fst.TestReadCeilArcSameFollowAndArc.testSameFollowAndArc(TestReadCeilArcSameFollowAndArc.java:16)

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

• Contract. Util.java:809-818: "Reads the first arc greater or equal than the given label into the provided arc in place and returns it iff found"; @param follow "the arc to follow reading the label from", @param arc "the arc to read into in place". No javadoc, package doc, CHANGES or MIGRATE entry requires distinct objects.
• Siblings. FST.findTargetArc "Finds an arc leaving the incoming arc, replacing the arc in place" (FST.java:1006-1008); Util.get calls fst.findTargetArc(label, arc, arc, fstReader) (Util.java:57, :84); FST.readFirstTargetArc "changes the provided arc (2nd arg) in-place" (FST.java:687-692). Both are alias-safe; the devil's-advocate verifier counted 18 non-test call sites in main that pass one arc twice to them.
• Tests. TestUtil.java:63 and :101 call Util.readCeilArc(label, fst, arc, arc, in), but only on leaf arcs, where the early return at Util.java:824-826 hides the defect: the call shape Lucene's own test uses, not proof of a tested contract.
• History. Both lines are in the method's first version (LUCENE-3846, 2012); the only later change to either is the rename follow.target -> follow.target() (760f2dbdcb2, LUCENE-8920). No commit, issue or PR found in the searches discusses aliasing.

The strongest case for "intended": the method has two separately named parameters with different roles, Util is @lucene.experimental, no production caller aliases them, and TestUtil's aliased calls only reach the leaf early return; so the rule is "pass two arcs".

Why it fails: that rule is written nowhere; the same-object idiom is established by in-tree use of the sibling methods with the same (follow, arc) pair (18 call sites) and safe for them; Lucene's own test uses the call shape; and the aliased call is right or wrong depending only on the node encoding. 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 may still prefer to document the rule (fix B).

Fix A was built and checked through gradle on 5adff78bb168; B changes only the javadoc and was not run. Open PR #12688 adds a PrimitiveLongFST copy of readCeilArc with the same call order, so the same change applies there.

In Util.readCeilArc, store follow.target() in a local before fst.readFirstTargetArc(follow, arc, in) (Util.java:827) and pass that local to readFirstRealTargetArc at :875.

    // follow and arc may be the same object: read follow's target before arc is overwritten
    final long followTarget = follow.target();
    fst.readFirstTargetArc(follow, arc, in);
    ...
    fst.readFirstRealTargetArc(followTarget, arc, in);

Trade-offs

One local long. Callers with distinct arcs read the same node as before. It also fixes both exception cases (a final follow, and a first child arc with no outgoing arcs): the local is the real node (targetHasArcs checked it is > 0), so the scan reads the real arcs instead of address -1 (executed: every one-object answer equals the two-object answer).

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 repro (1), TestUtil (5), TestFSTs (22), TestFSTDirectAddressing (3), TestFuzzySuggester (14), TestAnalyzingSuggester (23) and TestFSTPostingsFormat (30, lucene/codecs): 98 tests, 0 failures, 5 skipped, assertions on. checkGoogleJavaFormat on core passes. 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 finder's probe and TestUtil; the cross-model reviewer's own test passes with it.

Add the rule to the readCeilArc javadoc and, for consistency, change the two aliased TestUtil calls (:63, :101), which pass today only because they hit the leaf early return.

Trade-offs

No runtime change, but anyone who uses the in-place idiom of the sibling methods still gets a silent wrong answer.

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 readCeilArc against the obligation that its result does not depend on whether follow and arc are distinct, the in-place idiom of findTargetArc, Util.get and TestUtil, and found that :875 reads follow.target() after :827 may have overwritten follow.
• The finder then wrote a public-API JUnit test (keys ab, ac, x: b instead of a), a probe for the null and index -1 cases, and the 2-line fix that makes them pass; the test was later reduced to the one-key FST ab.
• An independent reproducer, an executed cross-model review, a devil's-advocate verifier and an adjudication reproduced it with their own tests ("Prior reports, history and checks").