ConjunctionUtils.createConjunction sorts the caller's TwoPhaseIterator list in place, so List.of(a, b) can throw UnsupportedOperationException

The finding in 30 seconds

A conjunction checks its two-phase iterators cheapest first. It gets that order by sorting the very list you passed in, in place.

Two-phase iterators in 20 seconds

A TwoPhaseIterator has a cheap approximation (a DocIdSetIterator that may over-match) and a matches() check that confirms each candidate document.
matchCost() estimates what one matches() call costs. A conjunction of several two-phase iterators calls matches() cheapest first, so it orders them by matchCost().
ConjunctionUtils.createConjunction(allIterators, twoPhaseIterators) is the public factory that builds such a conjunction from two lists the caller supplies.

Diagram of the bug: the caller passes two lists to ConjunctionUtils.createConjunction. The first list, allIterators, is copied and only the copy is sorted. The second list, List.of(a, b) with matchCost 2 and 1, is sorted in place by matchCost to become [b, a]; the swap is refused by the immutable list, so the call throws UnsupportedOperationException. The fix copies the second list to an array first, sorts the array and sums the match costs over it. — `createConjunction` copies `allIterators` before sorting it, but sorts your `twoPhaseIterators` list where it lies. `List.of(a, b)` with match costs 2 and 1 has to become `[b, a]`; the immutable list refuses the swap and the call throws. Select the still to open it at full size. Generated with AI, checked against the code.

The finding, step by step

Make two two-phase iterators over a one-document range (DocIdSetIterator.all(1)) that both match doc 0: a with matchCost() 2, b with matchCost() 1.
Call ConjunctionUtils.createConjunction(List.of(a.approximation(), b.approximation()), List.of(a, b)).
You expect a conjunction whose nextDoc() is 0. That is what you get when the same list is already cheapest first, List.of(b, a).
Instead it throws UnsupportedOperationException, with assertions on and off: to check b before a, the factory sorts your list itself, and List.of refuses the write.
Other lists: a LinkedList throws IllegalArgumentException ("can only sort random access lists in-place") in either order; an ArrayList works but comes back as [b, a].

Who is affected

Only code that calls the public ConjunctionUtils.createConjunction itself with two or more two-phase iterators in an immutable list (List.of, List.copyOf, Collections.unmodifiableList) whose match costs are not in non-decreasing order, or with two or more in a LinkedList. Lucene's own queries pass fresh ArrayLists or an empty list and are not hit. The failure is loud; nothing wrong is returned.

Mechanism, terms and numbers488 words

ConjunctionUtils.createConjunction(List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) is a public factory whose javadoc calls both arguments "a list of ... to combine" and says nothing else about them (ConjunctionUtils.java:65-77 at 5adff78bb168). To run the cheapest matches() first, the conjunction orders the two-phase iterators by matchCost(), and it does so by sorting the caller's list itself, in place, before copying it (ConjunctionDISI.java:354-357), while the same method copies allIterators before sorting that one (:114-133). So an immutable list of two or more whose match costs are not already in non-decreasing order, such as List.of(a, b) with costs 2 and 1, makes the call throw UnsupportedOperationException, with assertions on and off; Collections.unmodifiableList fails the same way, a LinkedList of two or more throws IllegalArgumentException in any order, and a mutable ArrayList comes back reordered. Lucene's own queries pass fresh ArrayLists or an empty two-phase list and are not hit. The in-place sort dates from LUCENE-6276 (2015), when only lists built inside ConjunctionDISI reached it; #148 (LUCENE-9204, 2021, first released in 9.0.0) made the factory public without a copy. Every release from 9.0.0 through 10.6.0 and main are affected. Fix: sort the array the constructor already copies, as BitSetConjunctionDISI does, and sum the match costs over that array.

Where the caller's list is written (main `5adff78bb168`)

ConjunctionUtils.java:74-77: the public createConjunction forwards both lists unchanged to the package-private ConjunctionDISI.createConjunction.
ConjunctionDISI.java:114-133: allIterators is copied into new ArrayLists, and only the copy is sorted by cost (:132). The caller's first list is never written.
ConjunctionDISI.java:140-143: the caller's twoPhaseIterators list itself goes to new ConjunctionTwoPhaseIterator(disi, twoPhaseIterators).
ConjunctionDISI.java:354-355: the constructor runs CollectionUtil.timSort(twoPhaseIterators, by matchCost) on that list and only then copies it with toArray (:357). This is the fix site.
CollectionUtil (@lucene.internal) sorts "directly on the supplied lists" (CollectionUtil.java:24-29): it rejects a list that is not RandomAccess with "CollectionUtil can only sort random access lists in-place." (:80-82) and swaps through Collections.swap, that is List.set (:94), which an immutable list refuses. The TimSort reverses a descending run with swaps and writes nothing in a list that is already in non-decreasing order, equal costs included (TimSorter.java:110-123), so List.of(b, a) passes; a one-element list returns before any check (CollectionUtil.java:165).

The numbers

With the repro's two iterators (a: matchCost 2, b: matchCost 1, both matching doc 0 of DocIdSetIterator.all(1)), on main with assertions on and off:

two-phase list	result	list afterwards
`List.of(a, b)`	`UnsupportedOperationException` at `ConjunctionDISI.java:354`	`[a, b]`
`List.of(b, a)`	works, `nextDoc()` = 0	`[b, a]`
`Collections.unmodifiableList(...)` of `[a, b]`	`UnsupportedOperationException`	`[a, b]`
`new LinkedList<>(...)`, either order	`IllegalArgumentException: CollectionUtil can only sort random access lists in-place.`	unchanged
`new ArrayList<>(...)` of `[a, b]`	works, `nextDoc()` = 0	`[b, a]` (reordered)

For comparison, BitSetConjunctionDISI in the same file copies first and sorts the copy (ConjunctionDISI.java:240-242).

Exposure and likelihood199 words

Not hit: Lucene's own queries. intersectScorers and intersectIterators (ConjunctionUtils.java:38-44, :56-62) and ConjunctionSpans.intersectSpans (lucene/queries, ConjunctionSpans.java:117-124) fill fresh ArrayLists. VectorScorer.java:65, :115, :143 (through ConjunctionUtils) and AbstractVectorSimilarityQuery.java:353 (through the package-private ConjunctionDISI.createConjunction) pass List.of(...), but with an empty two-phase list, which is never sorted.
No scale or configuration: two iterators and one document. The exception comes at construction, so no query runs with a wrong conjunction.
Can be data-dependent: whether it throws depends only on the order of the matchCost() values. Where a caller derives them from per-segment statistics, as PhraseQuery.termPositionsCost does (PhraseQuery.java:446-451), the same code can pass on one segment and throw on another; no such external caller was found.
Side effect: a mutable list (an ArrayList, or the array behind Arrays.asList) comes back reordered by match cost. No consequence of that was shown.
Reach: code searches found two direct callers outside Lucene: an Elasticsearch test with an empty two-phase list, and BlackLab's BLConjunctionSpans, a copy of ConjunctionSpans that fills fresh ArrayLists. Neither is affected. No public report of it was found since 9.0.0 (2021). Likelihood rare (an assessment from this evidence), priority Low.

Minimal repro

One JUnit test method on the public API: two always-matching two-phase iterators with match costs 2 and 1 in List.of, then createConjunction. No index, deterministic, single thread; it fails with assertions on and off.

TestConjunctionTwoPhaseListOf.java (lucene/core, package org.apache.lucene.search, 1 test)48 lines

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.search;

import java.io.IOException;
import java.util.List;
import org.apache.lucene.tests.util.LuceneTestCase;

public class TestConjunctionTwoPhaseListOf extends LuceneTestCase {

  private static TwoPhaseIterator matchAll(float matchCost) {
    return new TwoPhaseIterator(DocIdSetIterator.all(1)) {
      @Override
      public boolean matches() {
        return true;
      }

      @Override
      public float matchCost() {
        return matchCost;
      }
    };
  }

  public void testImmutableTwoPhaseList() throws IOException {
    TwoPhaseIterator a = matchAll(2), b = matchAll(1);
    // expected: a conjunction matching doc 0
    // actual: UnsupportedOperationException (List.of is sorted in place)
    DocIdSetIterator conjunction =
        ConjunctionUtils.createConjunction(
            List.of(a.approximation(), b.approximation()), List.of(a, b));
    assertEquals(0, conjunction.nextDoc());
  }
}

Command

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

Expected: createConjunction returns a conjunction whose nextDoc() is 0.
Observed: java.lang.UnsupportedOperationException from ImmutableCollections at ConjunctionDISI$ConjunctionTwoPhaseIterator.<init>(ConjunctionDISI.java:354).

All files of this repro: repro/LFV-1177/

More files, environment, full output189 words

TestConjunctionTwoPhaseListOf (one method, extends LuceneTestCase, package org.apache.lucene.search of the lucene/core tests). It is the hunt's minimal test with its comment line split in two so that checkGoogleJavaFormat passes. The test draws no random values; it failed on every recorded seed. Under gradle the test method takes about 0.02 s. The input is legal: both approximations are also in allIterators, and all iterators start on the same document, which the factory checks (ConjunctionDISI.java:97-113).

As a regression test the same method fits in TestConjunctionDISI.

Environment

lucene	`main 5adff78bb168 (12.0.0-SNAPSHOT): fails; 9.0.0, 9.1.0, 9.12.3, 10.0.0, 10.5.2, 10.6.0: the same or an equivalent test fails; 8.11.4: the API does not exist`
jdk	`OpenJDK 25.0.3 (build 25.0.3+9-LTS)`
os	`Linux aarch64 (nothing platform-specific)`

Command (environment)

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

Observed output

TestConjunctionTwoPhaseListOf > testImmutableTwoPhaseList FAILED
    java.lang.UnsupportedOperationException
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:D3DA6C8FE693B965]:0)
        at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:159)
        at java.base/java.util.ImmutableCollections$AbstractImmutableList.set(ImmutableCollections.java:281)
        at java.base/java.util.Collections.swap(Collections.java:525)
        at org.apache.lucene.util.CollectionUtil$ListTimSorter.swap(CollectionUtil.java:94)
        at org.apache.lucene.util.Sorter.reverse(Sorter.java:180)
        at org.apache.lucene.util.TimSorter.nextRun(TimSorter.java:115)
        at org.apache.lucene.util.TimSorter.sort(TimSorter.java:204)
        at org.apache.lucene.util.CollectionUtil.timSort(CollectionUtil.java:166)
        at org.apache.lucene.search.ConjunctionDISI$ConjunctionTwoPhaseIterator.<init>(ConjunctionDISI.java:354)
        at org.apache.lucene.search.ConjunctionDISI.createConjunction(ConjunctionDISI.java:141)
        at org.apache.lucene.search.ConjunctionUtils.createConjunction(ConjunctionUtils.java:76)
        at org.apache.lucene.search.TestConjunctionTwoPhaseListOf.testImmutableTwoPhaseList(TestConjunctionTwoPhaseListOf.java:44)
1 test completed, 1 failed

# with -Ptests.asserts=false: the same exception and frames

Why it looks unintended

The javadoc calls both arguments only "a list of ... to combine", with no mutability or RandomAccess requirement; ConjunctionUtils has no @lucene.internal tag.
The same method copies allIterators before sorting it; BitSetConjunctionDISI also sorts a copy.
The in-place sort (2015) predates the public factory (2021); in-tree code passes List.of(...) to this method (with an empty two-phase list).

The full argument174 words

Contract. ConjunctionUtils is a public final class with no @lucene.internal or @lucene.experimental tag. The javadoc of createConjunction says only "@param allIterators a list of DocIdSetIterators to combine" and "@param twoPhaseIterators a list of TwoPhaseIterators to combine" (ConjunctionUtils.java:65-73).
Two parameters, two behaviours. allIterators is copied before it is sorted (ConjunctionDISI.java:114-133); BitSetConjunctionDISI copies first too (:240-242).
History. LUCENE-6276 (0ed54b3105c, 2015-11-13, "Added TwoPhaseIterator.matchCost()") added the in-place sort when the list-taking createConjunction was private and only lists built inside ConjunctionDISI reached it (git show 5e0e7a5479b^: private static DocIdSetIterator createConjunction). #148 made the factory public without a copy; #148, its issue #10244 and the later rewrite #12328 never discuss the sort or the caller's list.
Idiom. In-tree code does pass immutable List.of(...) lists to this very method (VectorScorer), though only with an empty two-phase list: immutable lists are a form Lucene itself uses for these parameters.
Tests. No test asserts the reordering; TestConjunctionDISI builds conjunctions only through intersectIterators and intersectScorers, which use their own lists.

The devil's-advocate check102 words

The strongest case for "intended" (the cross-model reviewer rated it moderate): the intended pattern is to fill caller-owned ArrayLists with the public addIterator / addTwoPhaseIterator helpers (ConjunctionUtils.java:79-98), which works; CollectionUtil documents in-place sorting; TwoPhaseIterator is @lucene.experimental.

Why it fails: the javadoc never says the helpers or a mutable list are required; CollectionUtil is @lucene.internal, and nothing on the public class passes its note on; @lucene.experimental is about API stability, not about throwing on a legal argument, and ConjunctionUtils itself has no tag. The pattern argument makes the trigger rare, not illegal. Verdict: not intended, a small defect.

Suggested fix

Recommended Copy first, sort the copy (fix A)

Sort the array the constructor already copies, not the caller's list: move the sort after toArray, use ArrayUtil.timSort as BitSetConjunctionDISI does, and sum the match costs over that array. The repro passes, and 77 core tests and 232 spans tests pass with it.

      this.twoPhaseIterators = twoPhaseIterators.toArray(TwoPhaseIterator[]::new);
      ArrayUtil.timSort(
          this.twoPhaseIterators, (o1, o2) -> Float.compare(o1.matchCost(), o2.matchCost()));
      ...
      for (TwoPhaseIterator tpi : this.twoPhaseIterators) { // was: twoPhaseIterators (the caller's list)

All options and trade-offs3 options · 498 words

Fix A was built and checked through gradle in a scratch worktree at 5adff78bb168; B and C were not run.

Copy first, sort the copy (fix A) (validated by the checks) (recommended)

In the ConjunctionTwoPhaseIterator constructor (ConjunctionDISI.java:354-365), drop CollectionUtil.timSort on the list, sort the array that toArray already produces, and let the matchCost sum (:363) read that sorted array instead of the caller's list (3 lines added, 4 removed).

      this.twoPhaseIterators = twoPhaseIterators.toArray(TwoPhaseIterator[]::new);
      ArrayUtil.timSort(
          this.twoPhaseIterators, (o1, o2) -> Float.compare(o1.matchCost(), o2.matchCost()));
      ...
      for (TwoPhaseIterator tpi : this.twoPhaseIterators) { // was: twoPhaseIterators (the caller's list)

Trade-offs

No new allocation: the constructor already copies the list. It is the same stable TimSort with the same comparator, so the conjunction checks its iterators in the same order as before, and the total matchCost() is summed over the sorted array in the same order as today. That is why the loop changes too: float addition depends on order, and with the sum left on the caller's unsorted list, three iterators with costs 1e8, 4 and 4 in an ArrayList gave matchCost() 1.0E8 instead of main's 1.0000001E8; with the loop change it is 1.0000001E8, as on main (executed in the fact check). The only visible change left is that a caller's mutable list is no longer reordered; no in-tree caller reads its list after the call (ConjunctionUtils.java:34-63, ConjunctionSpans.java:117-124).

What the checks validated

Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on and off) and passes with it (assertions off).
With the fix and assertions on: the repro (1), TestConjunctionDISI (12), TestConjunctions (2), TestTwoPhaseIterator (6), TestPhraseQuery (26) and TestBooleanQuery (30): 77 tests, 0 failures. All 22 spans suites of lucene/queries, where ConjunctionSpans passes a non-empty two-phase list: 232 tests, 0 failures, 2 skipped. :lucene:core:checkGoogleJavaFormat passes. The full core suite was not run, and only OpenJDK 25.0.3 on Linux aarch64 was used.
The matchCost() sum: a probe with three iterators (costs 1e8, 4, 4) gives 1.0000001E8 on main and with this fix, and 1.0E8 with the first version of the diff that left the loop on the caller's list.
Earlier: the first version of the diff (without the loop change) passed the same gradle runs and made the hunt's tests pass (the independent reproducer's and the adjudication's runs, a separate re-run and the final repro check).

Document the in-place sort (not run)

Say in the createConjunction javadoc that the two-phase list is sorted in place and must be mutable and RandomAccess.

Trade-offs

No code change, but the trap stays, the two parameters stay inconsistent, and List.of(...), a form in-tree callers use for this method (with empty lists), is still rejected. Not recommended.

What the checks validated

Not run.

Copy in ConjunctionUtils.createConjunction (not run)

ConjunctionDISI.createConjunction(allIterators, new ArrayList<>(twoPhaseIterators)) in the public factory.

Trade-offs

Protects public callers only, at one extra list per call; fix A covers every path at no extra cost.

What the checks validated

Not run.

Downstream note

Downstream products are affected only where their own code calls ConjunctionUtils.createConjunction with an immutable or linked two-phase list; queries and documents alone cannot make the sort fail, because Lucene's own callers always pass it a fresh ArrayList (or no two-phase iterators at all).

How it was found

A proof-obligation audit of ConjunctionUtils's contract: the public factory's javadoc against what it does with its two list arguments. It copies one list and sorts the other in place, so an immutable or linked two-phase list cannot be sorted; a public-API JUnit test then witnessed the exception.

The method in full92 words

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

The finder checked each public ConjunctionUtils method against its javadoc and followed both list arguments of createConjunction into ConjunctionDISI: allIterators is copied before it is sorted, twoPhaseIterators is sorted where it lies.
The finder then wrote a public-API JUnit test and sketched the copy-then-sort fix.
An independent reproducer and an executed cross-model review reproduced it with their own tests; a devil's-advocate verifier re-ran the finder's test and an adjudication re-ran the reproducer's ("Prior reports, history and checks").

Prior reports, history and checks

Prior reports

No matching prior report found in apache/lucene issues, PRs and commits (incl. the JIRA archive), the mailing lists, downstream trackers or the web (searched 2026-11-03). Nearest: #148 (made the factory public) and #7338 (added the sort), history rather than reports.

Searches3 searches

No matching public report was found in the documented searches. ConjunctionTwoPhaseIterator has no issue or PR hits. History, not reports of this bug: #148 (LUCENE-9204, made the factory public; its discussion never mentions the sort), #7338 (LUCENE-6276, added the matchCost sort), #12328 (rewrote createConjunction and left the two-phase list uncopied). Related but different: #10581 (LUCENE-9541, "Ensure sub-iterators of ConjunctionDISI are on the same document", which added the factory's same-document check) and #16377 (a failure of that check, "Sub-iterators of ConjunctionDISI are not on the same document!"). No open PR touches ConjunctionDISI.java, ConjunctionUtils.java, CollectionUtil.java or TwoPhaseIterator.java. Limits: keyword search; GitHub search does not index every review comment (read directly for #148 and #12328); private reports are not visible.

What was searched, when, and what turned up
Where	When	How	Found
GitHub issues, PRs and commits (apache/lucene incl. the migrated JIRA archive)	2026-11-03; re-checked the same day	three scripted prior-report searches (names and the exception; descriptions such as "defensive copy", "modifies the input list", LinkedList, "can only sort random access lists in-place"), 36 manual searches, comment reads of #148, #12328, #7338, #10244 and others	no report; #148, #7338 and #12328 are history
Open PRs	2026-11-03	the changed files of the 100 most recently updated open apache/lucene PRs, and of the 27 updated since 2026-11-01	none touches the four files
Mailing lists, downstream, web	2026-11-03	dev@, java-user@, issues@ and commits@; apache/solr, elastic/elasticsearch, opensearch-project/OpenSearch and apache/lucenenet; a downstream code search; 3 web searches	nothing about this bug; two direct downstream callers (an Elasticsearch test with an empty two-phase list, and BlackLab's copy of ConjunctionSpans with fresh ArrayLists), neither affected

History

Introduced by #148 (LUCENE-9204, 5e0e7a5479b, 2021-05-25), first released in 9.0.0, which exposed the 2015 in-place sort through a public factory. Every executed release since fails, through 10.6.0 and main; 8.x has no such API. Not fixed upstream.

Versions tested6 rows

Introduced by #148 "Make ConjunctionDISI package-private and add ConjunctionUtils factory class" (LUCENE-9204, issue #10244, by @romseygeek, 5e0e7a5479b, 2021-05-25, main line only). It added the public ConjunctionUtils.createConjunction(List, List), which hands the caller's lists on unchanged; before it, the list-taking createConjunction was private. The in-place sort is older: LUCENE-6276 (0ed54b3105c on trunk, 9576c06156a on branch_5x, 2015-11-13), safe while every caller was internal.

9.0.0 and 8.11.4 ran a core-only main() with the repro's logic (their test frameworks differ); later releases ran a JUnit test. All 34 9.x and 10.x release tags contain 5e0e7a5479b and still sort the list uncopied. Upstream main 1c2072f0284 (2026-11-02) still sorts the caller's list at ConjunctionDISI.java:354.

Versions and branches executed, with results
Version or commit	Verdict	Result
8.11.4	main() probe	API absent (compile error); `ConjunctionDISI.intersectIterators` with the same `List.of` passes, because it copies
9.0.0	main() probe, -ea and -da	fails, same exception (`ConjunctionDISI.java:325`)
9.1.0, 9.12.3, 10.0.0, 10.6.0	JUnit	fails, same exception
10.5.2	independent reproducer's JUnit	fails, same exception
main 5adff78bb168	JUnit (gradle), -ea and -da	fails, same exception
main 5adff78bb168 + fix A	JUnit (gradle)	passes

Independent checks

A finder, an independent reproducer, an executed cross-model review (OpenAI GPT-5.6, real, high), a devil's-advocate verifier, an adjudication, separate re-runs and a final repro check reproduced it. This doc's gradle runs reproduced it on main and validated fix A.

Checks and verdicts245 words

The cross-model review ran on the older main ea57360912ed, where the three files involved are byte-identical to 5adff78bb168; a separate re-run repeated its test on 5adff78bb168 (fails). Every other check ran on 5adff78bb168 or release jars.

Each independent check and its verdict
Check	Verdict	What it found
finder	reproduced	Own test (costs 100 and 1, ten documents) fails on main (assertions on and off), 10.6.0, 9.12.3 and 9.1.0.
independent reproducer	real	Own test outside the package fails on main (on, off), 10.6.0, 10.5.2 and 9.12.3; a side probe on main and 9.0.0 shows ascending `List.of` works, `unmodifiableList` and `LinkedList` throw, `ArrayList` is reordered; fix A passes.
cross-model review, refute lens (OpenAI GPT-5.6, executed)	real (high)	Own test (`List.copyOf`, four documents) fails with assertions on and off and more seeds; ascending and mutable controls pass; `LinkedList` fails; the intended-behaviour case is moderate and rejected.
devil's-advocate verifier	real (high), low severity	"Helper pattern", "documented in CollectionUtil" and "experimental" all fail ("Why it is a bug, not intended").
adjudication	confirmed (high), Low	The reproducer's test fails on clean main (on, off) and passes with fix A.
separate re-runs, final repro check	reproduced; confirmed, Low	Fresh seeds fail on main; pass with fix A; the cross-model test fails on `5adff78bb168` too; one minimal test.
this doc	reproduced; fix A validated	Gradle: fails without the fix (on, off), passes with fix A; 77 core and 232 spans tests pass.

Diagram file

The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.

PNG 462 KB

Sources and provenance

Finding record, Lucene and upstream sources, repro files and diagram notes1,515 words

Finding record

LFV-1177, snapshot of 2026-11-06

Registry title: ConjunctionUtils.createConjunction sorts the caller's list of TwoPhaseIterators in place, so an immutable list such as List.of(a, b) whose match costs are not in ascending order throws UnsupportedOperationException, and a LinkedList throws IllegalArgumentException (since 9.0.0)
Area: core / search: conjunction iterators (ConjunctionUtils.createConjunction, ConjunctionDISI.ConjunctionTwoPhaseIterator)
Priority: Low, rank 708: Since 9.0.0 the public expert factory ConjunctionUtils.createConjunction throws on an immutable list of two-phase iterators whose match costs are not ascending, or on any non-random-access list, and reorders a mutable list in place. Only custom query code that calls the factory directly is hit, Lucene's own queries never are, and the failures are loud with nothing wrong returned.
Impact class: minor
Impact note: Only applications or custom queries that call the public factory ConjunctionUtils.createConjunction directly with two or more TwoPhaseIterators in an immutable list (List.of, List.copyOf, Collections.unmodifiableList) whose matchCost values are not ascending, or in any non-RandomAccess list such as a LinkedList, are hit: building the conjunction throws UnsupportedOperationException (or IllegalArgumentException) with -ea and -da [exec], and a mutable list comes back reordered by matchCost [exec]; Lucene's own queries are not affected (in-tree callers pass fresh ArrayLists or an empty List.of()), nothing wrong is returned silently, no scale is needed, and every release from 9.0.0 through 10.6.0 is affected.
Summary: You combine two TwoPhaseIterators with the public ConjunctionUtils.createConjunction(List.of(a.approximation(), b.approximation()), List.of(a, b)), where a has matchCost 100 and b has matchCost 1. You expect a conjunction iterator over their common documents, which is what you get when the same list happens to be in ascending cost order: the javadoc describes both arguments only as lists 'to combine', and the method copies its first list before sorting it. Instead it throws UnsupportedOperationException, because the private ConjunctionTwoPhaseIterator constructor sorts the caller's second list in place by matchCost (CollectionUtil.timSort) before copying it; a LinkedList makes the same call throw IllegalArgumentException 'CollectionUtil can only sort random access lists in-place.' in any order, and a mutable ArrayList comes back reordered.
Introduced: 5e0e7a5479bca798ccfe385629a0ca2ba5870bc0: apache/lucene#148 (LUCENE-9204, migrated issue #10244) 'Make ConjunctionDISI package-private and add ConjunctionUtils factory class' by @romseygeek (Alan Woodward), main line only (not cherry-picked to branch_8x). It added the public final ConjunctionUtils, whose createConjunction(List<DocIdSetIterator>, List<TwoPhaseIterator>) hands the caller's lists to ConjunctionDISI unchanged; before it, the list-taking ConjunctionDISI.createConjunction was private and only fresh internal ArrayLists reached the sort [read: git show 5e0e7a5479b^ in the history clone; exec: 9.0.0 fails, 8.11.4 has no such API]. The in-place sort itself is older: LUCENE-6276 (0ed54b3105c on trunk, 9576c06156a on branch_5x, Adrien Grand, 2015-11-13, first release 5.4.0) made the two-phase conjunction constructor CollectionUtil.timSort its List<TwoPhaseIterator> argument, which was safe while every caller was internal. (2021-05-25 (author date 2021-05-25T12:07:20+01:00, commit date identical; PR #148 merged 2021-05-25T11:07:20Z); first release 9.0.0)
First affected version: 9.0.0 [exec: a core-only main() with the repro's logic fails on the 9.0.0 jars with -ea and -da, UnsupportedOperationException at ConjunctionTwoPhaseIterator.<init>(ConjunctionDISI.java:325) <- ConjunctionUtils.createConjunction(ConjunctionUtils.java:76)]; 8.x is not affected [exec: on 8.11.4 the repro does not compile because ConjunctionUtils does not exist, and the closest public 8.x entry point, ConjunctionDISI.intersectIterators with the same List.of, passes because it copies into fresh ArrayLists]
Affected versions: Every 9.x and 10.x release, 9.0.0 through 10.6.0 (released 2026-10-29, 4ae946e5a9b), and main 5adff78bb168 (12.0.0-SNAPSHOT); never fixed. [exec, JDK 25.0.3, Linux aarch64] the finder's one-test JUnit fails on main with -ea and -da (finder, the intended-behaviour check, history step and the re-run of 2026-11-03) and on the 10.6.0 (finder, the intended-behaviour check, history step), 10.0.0, 9.12.3 and 9.1.0 jars (-ea); the independent reproduction's own public-API test fails on main (-ea, -da; also the adjudication's re-run), 10.6.0 (-ea), 10.5.2 (-ea) and 9.12.3 (-ea, -da); a core-only main() fails on 9.0.0 (-ea, -da). [read] all 34 9.x/10.x release tags contain 5e0e7a5479b, and each still passes the two-phase list uncopied into the in-place sort. Not affected: 8.x and older (API absent; 8.11.4 executed). Not new in 10.6 (10.5.2 fails too). Not fixed upstream: main 1c2072f0284 (2026-11-02) still calls CollectionUtil.timSort(twoPhaseIterators, ...) at ConjunctionDISI.java:354 before toArray at :357 (contents API, 2026-11-03).
Status: documented (brief, checks and a per-finding doc exist)
Verification: Confirmed by AI-run checks: an independent repro, a cross-model review that agreed, an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
Found by: semi-formal: proof-obligation audit
Upstream and prior reports: none found (2026-11-03, on top of the finder's run and the independent reproduction's, the intended-behaviour check's and the adjudication's searches; rechecked the same day): three scripted prior-report searches (class and method names and the exception; how the behaviour would be described, such as 'defensive copy', 'modifies the input list', LinkedList and 'can only sort random access lists in-place'; each 16 apache/lucene issue and PR queries, 3 commit queries, 2 downstream-repo queries over Elasticsearch, OpenSearch and Solr, 20 queries over the dev@, java-user@, issues@ and commits@ lists and 4 JIRA-archive queries; every high and medium hit read), 36 manual GitHub searches (apache/lucene issues and PRs, open and closed, including date-limited ones; apache/solr, elastic/elasticsearch, opensearch-project/OpenSearch, apache/lucenenet and all of GitHub), the changed files of the 100 most recently updated open apache/lucene PRs (none touches ConjunctionDISI.java, ConjunctionUtils.java, CollectionUtil.java or TwoPhaseIterator.java), the comments and review comments of #148, #12328, #7338, #10244, #14357, #16377, #16146 and others, a downstream code search (the only direct createConjunction call found, an Elasticsearch test, passes an empty two-phase list), the commit history with author dates, and 3 web searches. The same-day recheck (11 searches, the changed files of the 27 open PRs updated since 2026-11-01, upstream commits and file contents) found nothing new: 'ConjunctionTwoPhaseIterator' has no issue or PR hits, no issue or PR about conjunctions was updated since 2026-11-01, none of those open PRs touches the four files, and upstream main 1c2072f0284 still sorts the caller's list at ConjunctionDISI.java:354. Related history, not reports: #148 (LUCENE-9204, made the factory public; its discussion never mentions the sort), #7338 (LUCENE-6276, added the matchCost sort when only internal lists reached it), #12328 (createConjunction rewrite, left the two-phase list uncopied), #16377 and #10581 (other createConjunction failures: sub-iterators not on the same document), #4063 (LUCENE-2989, the RandomAccess message in a 2011 test failure).
Lucene commit tested: main 5adff78bb168 (12.0.0-SNAPSHOT): this doc's gradle runs (repro without and with the fix, the closest core suites and the spans suites of lucene/queries) and the runs of the hunt, the verifiers and a separate re-run; release jars 9.0.0, 9.1.0, 9.12.3, 10.0.0, 10.5.2 and 10.6.0 (all fail) and 8.11.4 (API absent); the cross-model review ran on main ea57360912ed, where the three files involved are byte-identical. OpenJDK 25.0.3, Linux aarch64.

Lucene and upstream sources

Finding record: lucene/core/src/java/org/apache/lucene/search/ConjunctionUtils.java:65-77 (at 5adff78bb168) (public final class without @lucene.internal; createConjunction javadoc: '@param allIterators a list of DocIdSetIterators to combine', '@param twoPhaseIterators a list of TwoPhaseIterators to combine'; nothing about mutation, mutability or RandomAccess), :79-98 (addTwoPhaseIterator / addIterator add to the provided lists), :38-44 and :56-62 (intersectScorers / intersectIterators build fresh ArrayLists)
lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java:94-145 (at 5adff78bb168) (createConjunction copies allIterators into new ArrayLists before sorting them, :114-133, but passes the caller's twoPhaseIterators list to new ConjunctionTwoPhaseIterator, :138-142), :349-357 (constructor: CollectionUtil.timSort(twoPhaseIterators, by matchCost) on the caller's list at :354-355, then toArray at :357: the fix site), :240-242 (BitSetConjunctionDISI copies to an array first and sorts the copy)
lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java:24-29 (at 5adff78bb168) ('Sort methods work directly on the supplied lists', @lucene.internal), :78-84 (ListTimSorter rejects a non-RandomAccess list: 'CollectionUtil can only sort random access lists in-place.'), :94 (swap through List.set), :155-167 (timSort(List, Comparator) sorts in place)
lucene/core/src/java/org/apache/lucene/search/VectorScorer.java:65, (at 5adff78bb168) :115, :143 (ConjunctionUtils.createConjunction(List.of(...), List.of())) and lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java:353 (at 5adff78bb168) (ConjunctionDISI.createConjunction(List.of(...), List.of())): in-tree List.of idiom for these parameters, always with an empty two-phase list, so no sort is reached
lucene/queries/src/java/org/apache/lucene/queries/spans/ConjunctionSpans.java:117-124 (at 5adff78bb168) (fresh ArrayLists filled with addSpans, then ConjunctionUtils.createConjunction)
The finding in 30 seconds: lucene/core/src/java/org/apache/lucene/search/ConjunctionUtils.java:65-77 (at 5adff78bb168) (javadoc and the public factory), :74-77
lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java:114-133 (at 5adff78bb168) (allIterators copied, the copy sorted at :132), :140-143 (twoPhaseIterators passed on), :240-242 (BitSetConjunctionDISI copies first), :349-357 (the in-place sort, then toArray)
lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java:24-29, (at 5adff78bb168) :78-95, :155-167
lucene/core/src/java/org/apache/lucene/util/TimSorter.java (at 5adff78bb168) (nextRun) and Sorter.java (reverse, binarySort): descending runs are reversed by swaps
Who is affected: lucene/core/src/java/org/apache/lucene/search/ConjunctionUtils.java:34-63 (at 5adff78bb168) (fresh ArrayLists)
lucene/queries/src/java/org/apache/lucene/queries/spans/ConjunctionSpans.java:117-124 (at 5adff78bb168)
lucene/core/src/java/org/apache/lucene/search/VectorScorer.java:65, (at 5adff78bb168) :115, :143; AbstractVectorSimilarityQuery.java:353 (empty two-phase List.of())
lucene/core/src/java/org/apache/lucene/search/PhraseQuery.java:446-451 (at 5adff78bb168) (termPositionsCost uses docFreq and totalTermFreq)
Minimal repro: lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java:97-113 (at 5adff78bb168) (all sub-iterators must be on the same document)
Why it looks unintended: lucene/core/src/java/org/apache/lucene/search/ConjunctionUtils.java:65-73, (at 5adff78bb168) :79-98
lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java:114-133, (at 5adff78bb168) :240-242, :354-357
lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java:24-29 (at 5adff78bb168) (@lucene.internal)
lucene/core/src/test/org/apache/lucene/search/TestConjunctionDISI.java (at 5adff78bb168) (only intersectIterators / intersectScorers)
https://github.com/apache/lucene/pull/148, https://github.com/apache/lucene/issues/10244, https://github.com/apache/lucene/pull/12328
Suggested fix: lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java:240-242 (at 5adff78bb168) (BitSetConjunctionDISI: toArray, then ArrayUtil.timSort), :349-367 (the constructor; the matchCost sum at :363-365)
lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java:577-579 (at 5adff78bb168) (timSort(T[], Comparator))
Prior reports: https://github.com/apache/lucene/pull/148, https://github.com/apache/lucene/issues/7338, https://github.com/apache/lucene/pull/12328
https://github.com/apache/lucene/issues/10581, https://github.com/apache/lucene/pull/16377; https://github.com/instituutnederlandsetaal/BlackLab (engine/.../spans/BLConjunctionSpans.java:57-67, read 2026-11-03)
Diagrams: lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java:114-143, (at 5adff78bb168) :349-357

Other statements trace to the hunt's working files (models, logs, reviews and briefs), which are not published.

Repro files

TestConjunctionTwoPhaseListOf.java (lucene/core, package org.apache.lucene.search, 1 test): repro/LFV-1177/TestConjunctionTwoPhaseListOf.java (48 lines)

About the diagrams

The diagram follows the repro's two iterators and the list contents a probe on main prints (ConjunctionDISI.java:114-143, :354-357).

assets/LFV-1177/bug.png (462 KB)

Built 2026-11-06 from the hunt's record of this finding and its doc file. Lucene main under test in this hunt: ea57360912ed. Every listed finding was re-run on Lucene main e1faeba08bde on 2026-11-02.

The finding in 30 seconds

Two-phase iterators in 20 seconds

The finding, step by step

Who is affected

Where the caller's list is written (main 5adff78bb168)

The numbers

Minimal repro

Environment

Observed output

Why it looks unintended

Suggested fix

Copy first, sort the copy (fix A) (validated by the checks) (recommended)

Document the in-place sort (not run)

Copy in ConjunctionUtils.createConjunction (not run)

Downstream note

How it was found

Prior reports, history and checks

Prior reports

History

Independent checks

Diagram file

Sources and provenance

Finding record

Lucene and upstream sources

Repro files

About the diagrams

Where the caller's list is written (main `5adff78bb168`)