MultiLevelSkipListWriter.bufferSkip throws ArrayIndexOutOfBoundsException for a one-level skip writer (maxSkipLevels = 1), a regression since 9.9.0

MultiLevelSkipListWriter is the public abstract base class (@lucene.experimental) for codec skip writers. Its constructor caps the number of levels at maxSkipLevels (when df > skipInterval; otherwise it uses 1), and init() allocates exactly that many level buffers. Since 9.9.0, bufferSkip(df) first checks df % windowLength == 0, where windowLength = skipInterval * skipMultiplier, and then raises the level count from 1 to 2 without comparing it with the cap; only the later increments are capped. So a writer built with maxSkipLevels = 1 throws ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1 at the first df that is a multiple of skipInterval * skipMultiplier, with assertions on and off. 9.8.0 wrote that entry to level 0, as a one-level skip list should.

The change was #12653, presented in its title and CHANGES entry as a speed-up. In practice only custom codecs with a single skip level are hit: Lucene's own skip writers use 4 levels (SimpleText) or 10 (backward codecs), and the default codec on main no longer uses this class. The failure is a loud exception while writing that term, not corruption.

1. The constructor caps the level count. :70-84: if df > skipInterval, numberOfSkipLevels = min(1 + log(df / skipInterval, skipMultiplier), maxSkipLevels), with the comment "also make sure it does not exceed maxSkipLevels" (:77), otherwise 1 (:80-82); and windowLength = skipInterval * skipMultiplier (:83). With maxSkipLevels = 1 the result is 1.
2. init() allocates exactly that many buffers. :95-99: skipBuffer = new ByteBuffersDataOutput[numberOfSkipLevels], here one.
3. The shortcut's first step is uncapped. bufferSkip(df) (:128-159) starts with numLevels = 1, then if (df % windowLength == 0) { numLevels++; df /= windowLength; while ((df % skipMultiplier) == 0 && numLevels < numberOfSkipLevels) { ... } } (:134-141). The first numLevels++ (:135) is the only increment with no cap. This is the fix site.
4. The level loop then reads past the array. for (int level = 0; level < numLevels; level++) { writeSkipData(level, skipBuffer[level]); ... } (:146-147) writes level 0 and then reads skipBuffer[1]: ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1.
5. Before 9.9.0 every increment was capped. 9.8.0: df /= skipInterval; while ((df % skipMultiplier) == 0 && numLevels < numberOfSkipLevels) { numLevels++; df /= skipMultiplier; }.

The exact condition is a writer with one level (numberOfSkipLevels == 1) called with a df that is a multiple of windowLength. The normal way to get one level is maxSkipLevels = 1. The other way, a constructor df below windowLength, reaches the line only if bufferSkip is later called with a df above the constructor's (for example 4, 2, 10 levels, constructor df 4, then bufferSkip(8)). Neither method checks that bound, but in-tree callers pass maxDoc as the constructor's df (SimpleTextSkipWriter.java:62), so a term's df cannot exceed it.

Not counted as a trigger: the backward-codecs Lucene99SkipWriter built with maxSkipLevels = 1 throws the same way (the refute-lens cross-model review drove it), but Lucene99PostingsReader always reads with 10 levels, so a one-level writer there would itself be a misuse. Not claimed: the constructor accepts maxSkipLevels <= 0 (a nonsense value that fails loudly).

• Who. Authors of a custom postings format whose skip writer extends MultiLevelSkipListWriter with one skip level. The class is public, abstract and @lucene.experimental, and invites subclassing ("subclasses must define the actual format of the skip data", MultiLevelSkipListWriter.java:47-48).
• Default vs opt-in. Opt-in only. SimpleText passes 4 levels (SimpleTextSkipWriter.java:40, :62), the backward-codecs Lucene90 and Lucene99 writers 10 (MAX_SKIP_LEVELS), and no core postings format on main subclasses the class.
• Effect. Deterministic, with assertions on and off: writing that term fails with an exception. In a postings writer it would surface while flushing the segment (by reading; not run through IndexWriter). No wrong results, no silent damage.
• Scale. None needed: the first bufferSkip call with a df of skipInterval * skipMultiplier (8 in the repro; 1,024 for 128 and 8, made at a term's 1,024th document by a writer that buffers skip entries as each block completes, like SimpleText, or at the 1,025th by one that buffers them when the next block starts, like the backward-codecs Lucene90 writer).
• Likelihood. Rare: no public report was found in the documented searches since 9.9.0 (2023).

TestSingleLevelSkipWriter (one method, extends LuceneTestCase, package org.apache.lucene.codecs of the lucene/core tests because resetSkip() is protected; Apache license header). It is the hunt's minimal repro, unchanged. The test draws no random values, so the outcome does not depend on the seed.

Without a fix it fails through gradle with assertions on and off; with fix A it passes with both. The same test fails on the main jars through a standalone JUnit runner. The release runs used the hunt's equivalent one-level tests (the reproducer's has the same input): 9.9.0, 9.12.3, 10.0.0, 10.5.2 and 10.6.0 fail with the same exception, and 9.8.0 passes.

cp $REPRO/TestSingleLevelSkipWriter.java $LUCENE/lucene/core/src/test/org/apache/lucene/codecs/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.codecs.TestSingleLevelSkipWriter -Ptests.seed=DEADBEEF   # add -Ptests.asserts=false: same failure

# gradle, scratch worktree at 5adff78bb168, -Ptests.seed=DEADBEEF (assertions on; -Ptests.asserts=false gives the same)
TestSingleLevelSkipWriter > testSingleLevelSkipList FAILED
    java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:E9607C52B90717C8]:0)
        at org.apache.lucene.codecs.MultiLevelSkipListWriter.bufferSkip(MultiLevelSkipListWriter.java:147)
        at org.apache.lucene.codecs.TestSingleLevelSkipWriter.testSingleLevelSkipList(TestSingleLevelSkipWriter.java:38)

# with fix A
BUILD SUCCESSFUL (1 test, 0 failures; assertions on and off)

• The cap is the class's own contract. The field javadoc calls numberOfSkipLevels the "number of levels in this skip list" (MultiLevelSkipListWriter.java:54-55); the constructor caps it on purpose (:77-79); init() allocates exactly that many buffers (:95-99); writeSkip iterates numberOfSkipLevels - 1 down to 0 (:172-179); the while guard caps every other increment (:138). An ArrayIndexOutOfBoundsException is not a documented outcome.
• One level is a designed mode. LUCENE-866 (#1941, 2007), which added multi-level skip lists, says the format "does not change for maxSkipLevels=1", and its first commit kept reading older index formats as single-level skip lists (87ba4a12584, SegmentTermEnum: maxSkipLevels = 1; // use single-level skip lists for formats > -3). MultiLevelSkipListReader on main sizes its arrays by maxSkipLevels and caps at it (MultiLevelSkipListReader.java:77-92, :207-209); an independent write-then-read test with one level passes on 9.8.0 and with the fix, and fails on main and 10.6.0.
• The change was presented as speed only. #12653's title and CHANGES entry (9.9.0, Optimizations: "Optimize computing number of levels in MultiLevelSkipListWriter#bufferSkip") describe only speed, and its 4 comments, 11 reviews and 10 review comments never mention one level. No javadoc, test, CHANGES or MIGRATE entry sets a minimum of 2 for maxSkipLevels, and no test builds a skip writer with fewer than 4 levels.

The strongest counter-argument (from the verifiers): "The class is experimental and named *Multi*Level; every in-tree writer uses at least 4 levels, so one level is unsupported territory."

Why it does not settle it. @lucene.experimental says the API may change, not that an accepted argument may crash. The constructor accepts 1 without complaint, the reader supports it, the class's own code treats the level count as a hard cap, and 9.8.0 handled it correctly. The argument does bound reach, which is why the priority is Low.

Fix A was built and checked through gradle on 5adff78bb168 in a scratch worktree, seed DEADBEEF: the repro with assertions on and off, core's TestMultiLevelSkipList (it indexes with the default postings format, which no longer uses this class, so it does not run the changed line), TestSimpleTextPostingsFormat (a 4-level subclass; the class is @Nightly, so it was run with -Ptests.nightly=true), backward-codecs' TestLucene90PostingsFormat and TestLucene99PostingsFormat (they write through the test-only Lucene90RWPostingsFormat and Lucene99RWPostingsFormat with 10-level skip writers; the production formats are read-only), and :lucene:core:checkGoogleJavaFormat. With the same change, the other checks' own tests passed too (the independent reproducer's, the devil's-advocate verifier's write-then-read test and the cross-model reviews' tests), and so did the finder's test and SimpleText's testDocsAndFreqs* (nightly). Option B was run once by the independent fact check: the repro passes through gradle with assertions on.

In MultiLevelSkipListWriter.bufferSkip (:134) add numberOfSkipLevels > 1 && to the shortcut's condition. One line.

if (numberOfSkipLevels > 1 && df % windowLength == 0) {

Trade-offs

Restores the 9.8.0 result for one level and changes nothing for 2 or more levels (the while loop already caps the rest). No file-format change. One extra int compare per call; writing df % windowLength == 0 && numberOfSkipLevels > 1 instead keeps the common non-boundary case at a single modulo, as #12653 intended (equivalent, not run separately).

What the checks validated

Gradle, scratch worktree at 5adff78bb168, seed DEADBEEF: the repro passes with assertions on and off; the repro plus TestMultiLevelSkipList: 2 tests, 0 failures (TestMultiLevelSkipList runs the default postings format, which no longer uses this class); TestSimpleTextPostingsFormat with -Ptests.nightly=true: 30 tests, 0 failures, 1 skipped; TestLucene90PostingsFormat and TestLucene99PostingsFormat (through their test-only RW formats): 65 tests, 0 failures, 4 skipped; :lucene:core:checkGoogleJavaFormat passes with the fix and the test in place.

Write the shortcut as if (df % windowLength == 0 && numLevels < numberOfSkipLevels), the same guard the while loop uses.

Trade-offs

Equivalent here (numLevels is 1 at that point) and reads like the existing loop guard.

What the checks validated

Run once by the independent fact check: the repro passes through gradle with assertions on (seed DEADBEEF).

Throw IllegalArgumentException for maxSkipLevels < 2.

Trade-offs

It would turn a designed, formerly working mode into an error, while the reader still accepts one level.

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 took the invariant the class states and keeps: the level count is capped at numberOfSkipLevels (the field javadoc :54-55, the constructor cap :77-79, the buffer allocation :95-99, the while guard :138).
• It checked every increment of numLevels in bufferSkip against that cap and found one, the first step of the shortcut (:134-135), that is not guarded, so the obligation fails exactly when numberOfSkipLevels is 1.
• A one-test JUnit with a one-level subclass witnessed it on main with assertions on and off and on the 10.6.0 and 9.9.0 jars, and showed 9.8.0 passing; the verifiers, the adjudication and a separate re-run all reproduced it.