TopDocs.merge(start, topN, ...) returns a page of null hits when start + topN overflows int

TopDocs.merge(int start, int topN, TopDocs[] shardHits) and its Sort and tie-breaker siblings merge sorted per-shard hits into one page, skipping the top start hits. The shared mergeAux sizes the page correctly, min(topN, availableHits - start), but bounds its copy loop by start + topN computed in int. For start >= 1 and topN > Integer.MAX_VALUE - start, for example topN = Integer.MAX_VALUE as "no limit" on any page after the first, with more than start hits to merge, the sum wraps negative, the loop never runs, and merge returns a page of the right length and the right totalHits whose every hit is null, without an exception. Callers usually fail with a NullPointerException soon after. The defect came with the paging overload itself (LUCENE-5515, 2014) and is in every release from 4.8.0 through 10.6.0 and on main; the fix is two lines.

• TopDocs.merge: a static utility that combines several already sorted result lists (one per shard or slice) into one, by score or by a Sort. The paging overloads take start and topN: skip the top start hits of the merged order, then return up to topN.
• mergeAux: the private method all paging overloads call (called from TopDocs.java:216-272, defined at :278-354).

1. mergeAux counts the available hits, availHitCount (TopDocs.java:291-306).
2. It sizes the page correctly: hits = new ScoreDoc[Math.min(size, availHitCount - start)] (:313). For the repro, min(2147483647, 2 - 1) = 1.
3. It computes the loop bound in int: int requestedResultWindow = start + size; (:314). 1 + 2,147,483,647 = 2,147,483,648 does not fit and becomes -2,147,483,648; numIterOnHits = Math.min(availHitCount, requestedResultWindow) (:315) is that negative number.
4. while (hitUpto < numIterOnHits) (:317) starts with hitUpto = 0 and exits at once, so no hit is copied into hits[hitUpto - start] (:333-335). The new array keeps its default nulls.
5. totalHits is summed from the shards' own totals (:289-301, :348) and is right, so the result looks normal until someone reads a hit.

With start = 0 the sum cannot overflow, so the start-less merge(topN, shardHits) is safe.

• Who is exposed. Code that calls one of the four paging overloads (TopDocs.java:216, :228, :254, :266, all @lucene.experimental) with start >= 1 and topN > Integer.MAX_VALUE - start, when more than start hits are available (with start or fewer, TopDocs.java:310-311 returns the correct empty page). Deterministic; any number of shards from 1 up; no setting or data shape needed.
• Lucene's own paths are not affected. TopScoreDocCollectorManager.reduce calls TopDocs.merge(0, numHits, topDocs) (TopScoreDocCollectorManager.java:109), TopFieldCollectorManager.reduce calls TopDocs.merge(sort, 0, numHits, topDocs) (TopFieldCollectorManager.java:156), and AbstractKnnVectorQuery (:429) and grouping's TopGroups.merge (TopGroups.java:241, :247) use the start-less overloads.
• What the caller sees. A page of the right length and the right totalHits, no exception from merge, and only null hits. Reading hit.doc or hit.score throws a NullPointerException; code that skips nulls shows an empty page while totalHits says otherwise. It never returns a wrong or extra hit.
• Why Integer.MAX_VALUE is a natural input. Lucene commonly accepts Integer.MAX_VALUE as an upper bound meaning "all hits" in related search and collector APIs, where it is clamped to a finite limit: BooleanPerceptronClassifier calls indexSearcher.search(q.build(), Integer.MAX_VALUE) (BooleanPerceptronClassifier.java:140), IndexSearcher.searchAfter, which search(query, n) calls, caps numHits at maxDoc (IndexSearcher.java:587-597, :623-624), and the sibling TopDocsCollector.topDocs(start, howMany) accepts it. Nothing documents it as a sentinel for TopDocs.merge paging in particular.
• Downstream, by code reading only (nothing run). Elasticsearch and OpenSearch call TopDocs.merge(from, size, ...) but check from + size in long arithmetic against index.max_result_window first, so their main search path does not reach it. Their top_hits aggregation adds from() + size() in int before widening it (the pattern behind elastic/elasticsearch#158635), but builds the shard collector from the same wrapped int, which Lucene's collector managers reject (numHits <= 0, TopScoreDocCollectorManager.java:62-64, TopFieldCollectorManager.java:62-64), so when a shard has a match that path fails earlier and does not reach this bug. Solr's distributed grouping (group.query with group.limit=-1, which it maps to Integer.MAX_VALUE, and group.offset >= 1) appears to.
• Likelihood: rare. A direct call with start >= 1 and a "no limit" topN is unusual, and focused searches found no public report or by-design discussion.

The test sits in org.apache.lucene.search, next to upstream's TestTopDocsMerge; it uses only public classes (TopDocs, ScoreDoc, TotalHits). The test body draws no random values, and the path it tests uses none of the settings LuceneTestCase randomizes (codec, locale, time zone), so the result does not depend on the seed (it fails with DEADBEEF, 5EED2621 and 5EED2622).

The same file fails unchanged on the 10.6.0, 10.5.2, 9.12.3 and 9.1.0 release jars (assertions on). Older releases need small edits (before 9.1.0 the test framework is in another package, before 8.0.0 there is no TotalHits, and 4.8.0 to 5.0.0 and 6.5.0 to 8.11.4 have a different paging merge signature); a version-portable probe covers them (see the version history).

It is also the suggested regression test, as written.

TestTopDocsMergeWindowOverflow > testMergeSecondPageWithMaxValueTopN FAILED
    arrays first differed at element [0]; expected:<doc=1 score=1.0 shardIndex=-1> but was:<null>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:E9808A3EC0C1DC45]:0)
        at app//org.junit.internal.ComparisonCriteria.arrayEquals(ComparisonCriteria.java:78)
        at app//org.junit.internal.ComparisonCriteria.arrayEquals(ComparisonCriteria.java:28)
        at app//org.junit.Assert.internalArrayEquals(Assert.java:534)
        at app//org.junit.Assert.assertArrayEquals(Assert.java:285)
        at app//org.junit.Assert.assertArrayEquals(Assert.java:300)
        at app//org.apache.lucene.search.TestTopDocsMergeWindowOverflow.testMergeSecondPageWithMaxValueTopN(TestTopDocsMergeWindowOverflow.java:29)

# the same with -Ptests.asserts=false; the standalone runner: 1 of 1 failed on main (-ea, -da), 10.6.0, 10.5.2, 9.12.3, 9.1.0

• The contract. "Returns a new TopDocs, containing topN results across the provided TopDocs" (TopDocs.java:197) and "Same as merge(int, TopDocs[]) but also ignores the top start top docs. This is typically useful for pagination." (:208-209). No bound on topN or start + topN is stated, and merge checks neither.
• The method treats topN as a cap. It sizes the page as min(topN, availHitCount - start) (:313). The introducing commit's message says the point was a "merged ScoreDoc array with length of at most equal to the specified size".
• The sibling handles the same input. TopDocsCollector.topDocs(start, howMany) documents that only the available documents are returned (TopDocsCollector.java:118-122) and clamps howMany before it adds start (:153, :160). On a 5-doc index it returns the 4 remaining hits for (1, Integer.MAX_VALUE) where TopDocs.merge returns nulls; with the fix both agree.
• The sibling rejects invalid input with an exception. topDocs(start, howMany) throws IllegalArgumentException for a negative start or howMany (TopDocsCollector.java:138-146). merge itself validates nothing (a negative start also leaves null slots: over 2 hits, merge(-1, 1) returns [null]), a separate input-validation question; but (1, Integer.MAX_VALUE) is valid input, which the sibling accepts and answers with the remaining hits.
• No test pins it. Upstream TestTopDocsMerge draws from and size inside the hit count (TestTopDocsMerge.java:123-124, :279-280, :302-303); the LUCENE-5515 review discussed < versus <= and javadoc wording, never large sizes.

The intended-behaviour checker built the strongest case: the API is @lucene.experimental; Lucene's own callers always pass start = 0; LUCENE-5515 moved the caller's from + size sum into merge, and callers had bounded that sum themselves; grouping's TopGroups still adds docOffset + docTopN in int. So Lucene "assumes" start + topN fits in an int.

Why it fails: nothing (javadoc, CHANGES.txt, MIGRATE.md, a test or a review comment) states that bound; @lucene.experimental allows the API to change, not a page of nulls; merge itself treats topN as an upper bound, and the sibling topDocs(start, howMany) handles the same pair. Every verifier and the adjudication said real; the one cross-model "not real" was procedural (it could not run code) and rated the intended argument weak. Verdict: not intended, a defect.

Two options were built and validated through gradle on 645d4fe14a20; a third is listed, not built. Workaround until fixed (for start >= 0 and topN >= 0): clamp before calling, TopDocs.merge(start, (int) Math.min(topN, (long) Integer.MAX_VALUE - start), shardHits), or pass the number of hits left after start (available hits minus start), not Integer.MAX_VALUE and not the total number of available hits, which can itself make start + topN overflow.

2 lines in TopDocs.mergeAux (:314-315). numIterOnHits is at most availHitCount, an int, so the cast is safe. Independent verifiers wrote the same change.

-      int requestedResultWindow = start + size;
-      int numIterOnHits = Math.min(availHitCount, requestedResultWindow);
+      long requestedResultWindow = (long) start + size;
+      int numIterOnHits = (int) Math.min(availHitCount, requestedResultWindow);

Trade-offs

None known; no behaviour change for any start + topN <= Integer.MAX_VALUE.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF: the repro fails on stock and passes with A, assertions on and off.
• The closest suites with A and the repro (TestTopDocsMerge, TestMultiSliceMerge, TestTopDocsRRF, TestSortOptimization, TestTopDocsCollector, TestTopFieldCollector): 7 suites, 72 tests, 0 failures.
• Every test in org.apache.lucene.search.* of lucene/core with A and the repro: 215 suites, 2,340 tests, 0 failures, 49 skipped.
• :lucene:core:check -x test (checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain, forbiddenApisTest): passes.
• Earlier, the same change made every verifier's test pass on ea57360912ed (the finder's 2, the independent reproduction's 7, the cross-model review's 5, the intended-behaviour check's probe), upstream TestTopDocsMerge, TestMultiSliceMerge and TestTopDocsRRF passed 12 of 12, and the exhaustive harness found 0 of 4,308 big-window mismatches.

1 line: int numIterOnHits = start + hits.length;. Since hits.length = min(size, availHitCount - start), the sum is at most availHitCount and equals the old bound whenever that fits. This is the clamp-before-add pattern of TopDocsCollector.topDocs(start, howMany) (TopDocsCollector.java:153, :160).

-      int requestedResultWindow = start + size;
-      int numIterOnHits = Math.min(availHitCount, requestedResultWindow);
+      // hits.length <= availHitCount - start, so this sum cannot overflow
+      int numIterOnHits = start + hits.length;

Trade-offs

One line and no long arithmetic, but it ties the loop bound to the array length, which a reviewer has to see is equivalent (hence the comment). A is the one every verifier ran.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF: the repro passes with B, assertions on and off.
• The same 7 closest suites: 72 tests, 0 failures; :lucene:core:check -x test passes.
• Not run: the full org.apache.lucene.search.* package and the verifiers' tests (A only).

Validate start + topN and throw.

Trade-offs

Loud instead of silent, but Integer.MAX_VALUE as "no limit" is a legitimate input that the sibling topDocs(start, howMany) accepts; callers would have to clamp themselves. A or B gives the documented result instead.

Method: semi-formal (a Dafny model plus bounded-exhaustive translation validation of the real jar).

• The finder, an AI tool, transcribed mergeAux into a Dafny model (Merge.dfy). Its postcondition "the page is the sorted window and every slot is filled" verified only under the precondition start + size <= Integer.MAX_VALUE and failed without it (a designed counterexample, MergeAuxNoWindowBound); Dafny reports 30 verified and 2 errors, both designed (this counterexample and a separate tie-breaker check, TwoShardsTie); 3 of 3 vacuity mutants killed. So the hypothesis came from reading the code while modelling it, not from a blind search.
• A bounded-exhaustive harness then ran the stock main jar against "sort the union, take [start, start + size)": every shape up to 3 shards x 3 tied hits, every start and size in [0, total + 1], plus size = Integer.MAX_VALUE - 1 and Integer.MAX_VALUE. With assertions on and off: 0 mismatches in 12,265,680 in-range checks, 1,726,010 null-slot mismatches in 3,118,984 big-window checks.
• The finder then wrote a public-API JUnit test; independent reproducers wrote their own tests from the claim alone. The one-test repro was cut from the finder's test on 2026-10-29.