Outputs.skipFinalOutput's default skips a final output with the regular-output decoder, so FST lookups miss keys for an Outputs with its own final-output encoding

Outputs lets a subclass encode final outputs (the output of a key that is also a prefix of a longer key) differently from regular arc outputs: writeFinalOutput and readFinalOutput are public and default to write / read. skipFinalOutput is documented as "Skip the output previously written with writeFinalOutput; defaults to just calling readFinalOutput and discarding the result" (Outputs.java:76-79 at 5adff78bb168), but its body is skipOutput(in) (:80-82), which decodes with read. The list-node scan in FST.findTargetArc skips the final output of every arc it passes with skipFinalOutput (FST.java:1113). For a subclass whose final encoding has a different length, the scan skips the wrong number of bytes, reads the rest of the node out of step and gives up: Util.get and BytesRefFSTEnum.seekExact return null for a key that is in the FST, with no error, with assertions on and off. Three keys and the default FSTCompiler.Builder are enough. No Lucene FST is affected: the only in-tree Outputs with its own final encoding, ListOfOutputs, overrides skipFinalOutput. The mismatch dates from LUCENE-5670 (4.9.0); the silent lookup miss from #12692 (9.9.0), which moved findTargetArc's scan onto the skip methods.

1. The FST. The root has two arcs, a and b. Two arcs are below the fixed-length thresholds (5 arcs at depth <= 3, 10 deeper: FSTCompiler.java:77-87, :601-606), so the root is a list node. Arc a carries output 3 (common(5, 3)) and, because a is itself a key, the final output 2 (5 - 3), which FSTCompiler writes with writeFinalOutput (FSTCompiler.java:493): 8 bytes. Arc b carries output 7. The root's 15 bytes in reading order are 31 61 03 | 02 00 00 00 00 00 00 00 | 02 | 1f 62 07 (arc a: flags, label, output, final output, target; arc b: flags, label, output).
2. The right decoder. readArc decodes the final output with readFinalOutput (FST.java:949-950), so enumeration consumes 8 bytes and lands on arc b.
3. The scan. findTargetArc('b') on a list node (FST.java:1093-1119) reads arc a's flags and label, sees a < b, and skips the arc: its output with skipOutput (:1110), its final output with skipFinalOutput (:1113), its target with readUnpackedNodeTarget (:1116).
4. The wrong skip. The inherited skipFinalOutput is skipOutput(in), which is read(in), PositiveIntOutputs' VLong: it consumes 1 of the 8 bytes.
5. Out of step. Flags 0x31 have neither the stop-node nor the target-next bit, so readUnpackedNodeTarget (:1116, a VLong) reads the next zero byte as arc a's target, and the remaining six zero bytes form two bogus arcs (flags 0, label 0, target 0 each). Then the scan reads arc a's real target byte 02 as flags and 1f as the label. 0x02 is the last-arc bit, so it returns null (:1106-1107) without reaching b: 7 bytes misread, 1 as a target and 6 as two arcs.

The same inherited skip runs in readLastTargetArc (FST.java:664) and seekToNextNode (:1134). With a deeper FST (xa=5, xab=3, xb=7), a history probe saw seekFloor("y") throw ArrayIndexOutOfBoundsException in FST.readLastTargetArc (4.9.0, 9.8.0) or loop in FSTEnum.pushLast until a 1 GB heap ran out (9.12.3, 10.6.0, main). That failure is loud, on a different FST and call, and is not the claimed repro, which fails silently.

• Who is hit. Code that subclasses Outputs (public, @lucene.experimental, Outputs.java:31), overrides writeFinalOutput / readFinalOutput with an encoding whose length differs from write, and keeps the inherited skipFinalOutput. Then any lookup that scans a list node (a node below the fixed-length thresholds, as here) past an arc carrying a final output (a key that is a prefix of a longer key) reads the rest of the node out of step and can miss its key, as in the repro. Default FSTCompiler settings and three keys are enough.
• Silent. Util.get and seekExact return null for keys that are in the FST, with assertions on and off; enumeration with next(), seekCeil and seekFloor still show the key on the repro's FST, so tests that only iterate the FST pass.
• Narrow reach. No in-tree FST is affected: ListOfOutputs (misc), the only in-tree Outputs with its own final encoding, overrides skipFinalOutput; FSTOrdsOutputs (codecs) overrides it with the same body and no final-encoding change; every other built-in keeps writeFinalOutput == write. A GitHub code search for writeFinalOutput outside apache/lucene: the first 100 of its 249 hits are all copies of Lucene's own classes, with no third-party subclass among them (the other 149 were not inspected).

TestSkipFinalOutputDefault (one method, extends LuceneTestCase, package org.apache.lucene.util.fst of the lucene/core tests). The anonymous Outputs<Long> delegates every method to PositiveIntOutputs except writeFinalOutput / readFinalOutput (writeLong / readLong) and inherits skipFinalOutput. It builds a -> 5, ab -> 3, b -> 7 with new FSTCompiler.Builder<>(BYTE1, outputs).build() and asserts Util.get(fst, "b") == 7.

The test uses no randomness, so the seed does not matter (it failed with DEADBEEF, 5EED1701, 5EED1702 and random seeds). Before 9.10 only the FST-construction line changes, to compiler.compile(), because FST.fromFSTReader is 9.10+ API; that variant fails on 9.9.0 and 9.9.2 and passes on 9.8.0. As the regression test, the same method fits into TestFSTs or TestUtil as is.

cp $REPRO/TestSkipFinalOutputDefault.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/fst/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.fst.TestSkipFinalOutputDefault -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false (the production setting)

# -Ptests.asserts=false (the same with assertions on)
TestSkipFinalOutputDefault > testLookupPastArcWithFinalOutput FAILED
    java.lang.AssertionError: expected:<7> but was:<null>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:A03750B16BECD232]:0)
        ...
        at org.apache.lucene.util.fst.TestSkipFinalOutputDefault.testLookupPastArcWithFinalOutput(TestSkipFinalOutputDefault.java:89)

# byte probe on main, assertions off (evidence, not the repro; labels in decimal: 97 = 'a', 31 = byte 0x1f)
arc 'a': output=3 finalOutput=2 flags=0x31 isLast=false
arc 'b': output=7 finalOutput=0 flags=0x1f isLast=true
arc 'a' flags=0x31: output bytes=1, final output: skipFinalOutput consumes 1 byte(s), readFinalOutput consumes 8 byte(s) (value 2)
scan step 1: flags=0x31 label=97 ('a') -> skip this arc
scan step 2: flags=0x0 label=0 -> skip this arc
scan step 3: flags=0x0 label=0 -> skip this arc
scan step 4: flags=0x2 label=31 -> last-arc flag set: return null
Util.get(b) = null

• Contract. skipFinalOutput's javadoc names readFinalOutput as the default and calls itself the counterpart of writeFinalOutput (Outputs.java:76-79). writeFinalOutput and readFinalOutput are public, non-final and documented as defaults (:52-58, :68-74). No javadoc, package doc, MIGRATE.md or CHANGES.txt entry says that overriding them also requires overriding skipFinalOutput.
• Tests. No test in lucene/*/src/test or the test framework mentions skipFinalOutput.
• History. LUCENE-5670 (#6732, 2014) added the javadoc and the body in one commit; its 11 comments discuss only skipOutput and DataInput.skipBytes. #12692 (9.9.0) moved findTargetArc's scan from readNextRealArc, which decodes with readFinalOutput, to the skip methods; its review threads discussed only arc flags. Nobody discussed what the default should call.

The argument. The skip-without-decode body is a deliberate optimisation for the built-ins that override only skipOutput, and only the javadoc is wrong: the contributor's patch had the body without javadoc (the committer wrote it), the same commit gave ListOfOutputs a paired override, the API is experimental, and no report of it was found in 12 years.

Why it fails. A subclass that follows the method's documentation gets wrong lookups, silently, and no document states the rule it broke. The optimisation does not need the default: each built-in can override skipFinalOutput itself, as FSTOrdsOutputs (LUCENE-5819, 2014) already does with exactly the default body, which suggests the documented default was the authors' mental model (an interpretation).

What survives. Keeping the body and fixing the javadoc (option B) is a legitimate API-contract choice, and a maintainer may well prefer it.

Option A+ makes the documented contract true while every built-in keeps the skip code it runs today (no slowdown expected; not benchmarked). Option A is the same default change alone; option B keeps the code and documents the rule instead.

Outputs.skipFinalOutput calls readFinalOutput(in). ByteSequenceOutputs, CharSequenceOutputs, IntSequenceOutputs, PairOutputs and FSTTermOutputs (codecs) get skipFinalOutput overrides that call skipOutput(in), which is what they run today, since their final encoding is their regular one. PositiveIntOutputs, NoOutputs and UpToTwoPositiveIntOutputs do not override skipOutput, so they behave the same either way; ListOfOutputs and FSTOrdsOutputs already override skipFinalOutput. 6 files, +26/-1.

// Outputs.java: the default does what its javadoc says
   public void skipFinalOutput(DataInput in) throws IOException {
-    skipOutput(in);
+    readFinalOutput(in);
   }
// ByteSequenceOutputs, CharSequenceOutputs, IntSequenceOutputs, PairOutputs, FSTTermOutputs:
// keep skipping without decoding (their final encoding is their regular one)
+  @Override
+  public void skipFinalOutput(DataInput in) throws IOException {
+    skipOutput(in);
+  }

Trade-offs

The built-ins keep the skip code they run today: no behaviour change, and no slowdown expected (not benchmarked). A custom subclass that relies on the default now decodes its final output when skipping: correct, and it may override skipFinalOutput for speed, as before. It is not a universal fix for subclasses of an optimised built-in: a subclass of PairOutputs (public, not final) or of FSTTermOutputs (not final, package-private) that changes the final encoding inherits the new skipOutput-based override and must override skipFinalOutput itself, the same rule as today.

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: :lucene:core:test --tests 'org.apache.lucene.util.fst.*' (9 classes, 38 tests), :lucene:misc:test --tests 'org.apache.lucene.misc.util.fst.*' (TestFSTsMisc, 3), :lucene:codecs:test for codecs.memory.* and codecs.blocktreeords.* (3 classes, 97) and :lucene:suggest:test (31 classes, 236): 374 tests, 18 skipped, 0 failures; checkGoogleJavaFormat passes for core and codecs.

The one-line change to Outputs.skipFinalOutput, without the built-in overrides.

   public void skipFinalOutput(DataInput in) throws IOException {
-    skipOutput(in);
+    readFinalOutput(in);
   }

Trade-offs

Correct for everyone, but the five built-ins above would then decode, and usually allocate an object for, every final output the scan passes instead of skipping it, which partly undoes #12692's purpose. Not measured.

What the checks validated

By the hunt: the repro passes with assertions on and off, and TestFSTs plus fst.TestUtil (25 tests) pass; the cross-model reviewer ran TestFSTs (20) and TestFSTsMisc (3) with it (pass).

Keep skipOutput(in) and document that a subclass overriding writeFinalOutput / readFinalOutput must also override skipFinalOutput.

Trade-offs

No code change, but the trap stays silent for anyone who misses the sentence. Not run.

The audit took each overridable default of Outputs and checked its body against its javadoc and its callers. For skipFinalOutput the obligation "skip what writeFinalOutput wrote" holds only if writeFinalOutput and write produce the same number of bytes, which the class does not require. The callers in FST showed where a mismatch is read: the list-node scans.

An executable repro on the public API witnessed it on main with assertions on and off. An independent reproducer, an executed cross-model review (OpenAI GPT-5.6, refute lens), a devil's-advocate verifier and an adjudication then confirmed it, and a version sweep placed the silent miss in 9.9.0 and the mismatch in 4.9.0.