Intervals.atLeast stops early when the sub-iterator it just used runs out

Intervals.atLeast(k, sources...) with k below the number of sources keeps k sub-iterators in a proximity queue and the others in a background queue. To move past the interval it just returned it pops the front sub-iterator and, as its class comment says, should replace it with the top of the background queue. The first loop of nextInterval() does that only when the popped sub-iterator still has an interval; when it is exhausted nothing is brought in, the proximity queue is short and the iterator ends while background sub-iterators still hold intervals. With k = 1 this happens whenever the source of the last interval runs out; with k >= 2 it can happen when a sub-source spans several positions or tokens are stacked. The same hand-over never advances waiting sub-iterators past the current start, so a stale one can come back with an earlier, non-minimal interval. At top level the document still matches with fewer intervals (fewer highlights, lower scores); nested, documents can be missed; under negation, documents that should be excluded are kept. Every release from 8.0.0 to 10.6.0 (10.6.0 by reading) and main; no error is raised.

• Interval: a [start, end] range of token positions in one field of one document. Intervals.term("a") gives one interval per occurrence of a.
• Intervals.atLeast(k, sources...): "Return intervals that span combinations of intervals from minShouldMatch of the sources" (Intervals.java:562). Every source exposes "the minimum intervals" (IntervalsSource.java:36-37); for the sources in these examples that means no returned interval contains another (extend is an exception near position 0: it clamps starts at 0, so extend(a, 1, 0) on "a a" returns [0,0], [0,1], executed). The factory rewrites k = n to unordered and k > n to no match; anything else, including k = 1 with two or more sources, builds MinimumShouldMatchIntervalsSource (Intervals.java:564-576).

1. The iterator keeps a proximity queue of k sub-iterators, ordered by start (equal starts: the larger end first), and a background queue of the rest, ordered by end (equal ends: the larger start first) (:186-195). reset(), which nextDoc() and advance() call, moves each sub-iterator positioned on the current document to its first interval and puts the k with the smallest end into the proximity queue (:270-290, :309-321).
2. The class comment: "when an iterator is popped from the proximity queue, it is inserted back into the background queue, and replaced by the top iterator from the background queue" (:146-156).
3. First loop of nextInterval() (:216-227): while the proximity front still starts at the last returned start, pop it, and only if it.nextInterval() != NO_MORE_INTERVALS (:220) put it back and pop a replacement (:221-225). An exhausted iterator is dropped and not replaced, and if (proximityQueue.size() < minShouldMatch) return start = end = NO_MORE_INTERVALS; (:228-229) ends the iteration with background iterators unread.
4. The minimising loop below does draw a replacement after an exhausted lead (:242-251); only the first loop skips it.
5. When the first loop runs: the minimising loop returns at once when the front's end equals the window's right edge (:239-241), and the next call then starts in the first loop. With k = 1 that is every call after the first (the first call skips the loop, as start is -1 after reset()), so the iterator ends as soon as the source of the last interval runs out. With k >= 2 the front must reach the right edge: stacked tokens, or a multi-position sub-source such as ordered(a, c) = [0,2] around b = [1,1]. With single-position terms at distinct positions the minimising loop does the hand-over, and the exhaustive harness's level-1 run over plain terms (documents up to 5 positions) found no k = 2 failure.
6. Hand trace, atLeast(1, a, b) on "a b": proximity {a@[0,0]}, background {b@[1,1]}. Call 1 returns [0,0]. Call 2 pops a; a is exhausted, nothing is drawn, size 0 < 1, so NO_MORE_INTERVALS.
7. Second symptom: no code advances background iterators past the current start. atLeast(1, b, phrase(a, b)) on "a b b": call 1 returns b@[1,1]; call 2 retires b (now at [2,2]), and the background pop returns the phrase at [0,1] (smallest end), which starts before [1,1] and contains it; call 3 retires the exhausted phrase with no replacement, so b@[2,2] is lost.

Not affected: atLeast(2, a, b, c) on "a b c" gives [0,1], [1,2], as expected.

• Who is exposed. Applications that build Intervals.atLeast directly, or through StandardQueryParser's fn:atLeast (since 9.1.0, #11259 / LUCENE-10223; the node calls Intervals.atLeast, intervalfn/AtLeast.java:39), with k = 1 over two or more sources, or k >= 2 when a sub-source spans several positions (ordered, phrase, unordered, ...) or tokens are stacked (index-time synonyms, word-delimiter output); these shapes make it possible, not certain: the front interval must reach the window's right edge and a remaining interval must matter.
• Downstream (read, not run). Solr's new intervals query parser (SOLR-13764, on Solr main and branch_10x, not in the 10.0.0 release) maps its at_least rule to Intervals.atLeast. Elasticsearch and OpenSearch do not expose atLeast. That says nothing about private code.
• Default or opt-in. atLeast is an opt-in operator of the intervals package, which calls itself experimental (intervals/package-info.java:21). Nothing else is needed: a default IndexWriterConfig (so the default codec, as in the release sweep's port) and searcher, assertions on or off. The JUnit fails the same way under the test framework's randomized codec and directory.
• Scale and frequency. One document of 2 to 5 tokens; deterministic. No prevalence was measured. In the finder's bounded synthetic enumeration (every tiny document over {a, b, c}, with empty positions, a stacked-token tier and source lists with repeats such as atLeast(1, a, a, b)) the exact interval list was wrong in 131,652 of 221,130 k = 1 checks (60%) and in 20,070 of 110,565 k = 2 checks: a rate over the enumeration, not over real queries or text.
• What you see. No error. Top level: fewer intervals, so Weight#matches and highlights lose spans (executed), and IntervalScorer freq, which sums over every interval (IntervalScorer.java:60-69), and with it the score drop: atLeast(1, a, b) on "a b" scores 0.5 against 0.6666666 for or(a, b) and for atLeast with the fix (executed). Nested under ordered, containing and similar operators: documents can be missed. Under negation: documents that should be excluded are kept (see the Downstream note). No hang, crash or index change.

# Lucene main 645d4fe14a20, assertions on (-ea), seed 5EED0286: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<[[0,0], [1,1]]> but was:<[[0,0]]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.queries.intervals.TestAtLeastOneLosesLastInterval.testAtLeastOneOfTwoTerms(TestAtLeastOneLosesLastInterval.java:49)

• The contracts. IntervalsSource#intervals: "Create an IntervalIterator exposing the minimum intervals defined by this IntervalsSource" (IntervalsSource.java:36-37). Intervals.atLeast: "Return intervals that span combinations of intervals from minShouldMatch of the sources" (Intervals.java:562). The Intervals class: "These sources implement minimum-interval algorithms taken from the paper ... Minimal-Interval Semantics" (Intervals.java:43-45). CHANGES for LUCENE-8622: "Adds a minimum-should-match interval function that produces intervals spanning a subset of a set of sources." (lucene/CHANGES.txt:6767-6768).
• The code contradicts itself. The class comment describes the replacement (MinimumShouldMatchIntervalsSource.java:146-156); the minimising loop draws it after an exhausted lead (:242-251); the first loop skips it (:220-229).
• k = 1 should behave like or(). That follows from the minimal-interval reading of the javadoc; no javadoc states the equivalence outright. The factory accepts k = 1 unchanged (Intervals.java:564-576). The author, @romseygeek, described atLeast on dev@ in 2020 as "a mixture of a disjunction and an unordered interval". The test's or() controls return exactly the intervals atLeast loses.
• Upstream tests. TestIntervals.testMinimumShouldMatch (:770, 5 sources, k = 3) expects complete minimal-interval lists; none of the four atLeast tests (it, :813, :837, :853), nor any other of the 117 upstream interval tests, pops an exhausted sub-iterator while another one is still waiting in the background queue (an instrumented run: testMinShouldMatch2 reaches the exhausted pop once, at its natural end, with the background queue empty). All 117 pass with the fix, so none pins the truncated output.
• History. The loop was copied in 2019 from the unordered iterator (LUCENE-8196), where stopping on an exhausted sub-iterator is correct because every sub-iterator is required; LUCENE-8622 made both loops swap through the background queue, but only the second draws a replacement when the popped iterator is exhausted; the first kept the unordered iterator's guard. Its one review (by @dsmiley) was about naming and comments.
• Precedent. #12213 / #12214 (9.6.0) fixed a lost interval after minimisation in OrderedIntervalsSource as a bug.

The strongest case for "intended" was built by the devil's advocate and reviews by an independent reviewer from another model family (OpenAI GPT-5.6, reading only): the intervals package is experimental; atLeast(1, ...) is degenerate and users should write or(); Intervals.or(false, ...) documents that it "can miss valid hits due to minimization" (Intervals.java:131, :147); the fn:atLeast parser doc illustrates overlapping intervals, one of them [1,8] (intervalfn/package-info.java:241-246); the parser docs say the algorithm "is not required to return or highlight all matching interval alternatives" (intervalfn/package-info.java:347-349, :381-383); no javadoc states that intervals come in start order; and a top-level atLeast still matches the document.

Why it fails: experimental status allows API changes, not wrong results, and the package keeps getting correctness fixes (#12213, LUCENE-9099, LUCENE-10140). The factory and the parser accept k = 1 unchanged (LUCENE-9744's "malformed" remark was about atLeast(1, singleTerm), which the factory now rewrites), and k = 2 fails too. The or(false) caveat is for or(false) only: ordered(c, or(false, a, b)) still matches "a c b", and the lost intervals are minimal. Neither stock nor the fix produces [1,8] for the parser example (both give [1,7], [2,8]), and the upstream highlighter tests for it pass with the fix. Start order is indeed not stated, so only the out-of-order wording rests on it: [0,1] is still not minimal and [2,2] is still lost (the devil's advocate's confidence is high for the truncation, moderate for this symptom alone). The parser docs' "not required to return ... all matching interval alternatives" is about fn:ordered and fn:unordered over an fn:or, where the alternative left out is the longer, non-minimal match; the lost intervals here are minimal. Scores and highlights still change, and some nested and negated uses go wrong (the executed ordered, containing, MUST_NOT and negation cases), even when the top-level document matches. On the other side: the atLeast javadoc is a single sentence, nobody reported this in the seven years since 8.0.0, and a fix changes the highlights and scores of existing atLeast queries.

One fix was validated in a scratch worktree at ea57360912ed; option B was run and is not enough on its own; option C was not run. Until a fix ships, users can write Intervals.or(...) for k = 1, and, when the sources are pairwise distinct, an or of unordered subsets for k >= 2 (the number of subsets grows quickly). With a repeated source the two differ: unordered() folds equal sources into one that needs separate occurrences, while atLeast gives every argument its own iterator, so atLeast(2, a, a, b) matches a document with a single "a" and or(unordered(a, a), unordered(a, b), unordered(a, b)) does not (executed).

The finder's sketch (+29/-3, MinimumShouldMatchIntervalsSource.java only). The first loop draws the replacement even when the popped iterator is exhausted, and both loops take it through pollBackground(start), which advances (or drops, when exhausted) background iterators whose interval starts at or before the current start. Why skipping is safe (by reasoning under an assumption, not a proof): if each sub-source returns intervals with strictly increasing starts and ends, as minimal-interval sources do, every part of a later answer starts after the current start. IntervalIterator does not promise that order, and extend near position 0 breaks it; on that shape the fix still agrees with or() (atLeast(1, extend(a, 1, 0), b) on "a a b": [0,0], [2,2] with the fix and with or(), [0,0] on stock; executed). The bounded tests support the fix; they do not prove it.

// first loop: replace the popped iterator even if it is exhausted
if (it != null && it.nextInterval() != NO_MORE_INTERVALS) backgroundQueue.add(it);
IntervalIterator next = pollBackground(start); // was: backgroundQueue.pop(), inside the if
if (next != null) { proximityQueue.add(next); updateRightExtreme(next); }

private IntervalIterator pollBackground(int minStart) throws IOException {
  while (true) {
    IntervalIterator it = backgroundQueue.pop();
    if (it == null || it.start() > minStart) return it;
    while (it.start() <= minStart) {
      if (it.nextInterval() == NO_MORE_INTERVALS) { it = null; break; }
    }
    if (it != null) backgroundQueue.add(it);
  }

Trade-offs

• Cost. pollBackground may call nextInterval() on waiting iterators earlier than today, but every call moves an iterator forward, so the work per document stays bounded by the sub-sources' intervals. No benchmark was run.
• Highlights change with it. The Matches path drives the same iterator (MinimumShouldMatchIntervalsSource.java:80-91); the upstream match highlighter tests pass, and the devil's advocate's Weight#matches probe passes with the fix.
• The assertion becomes a null check. pollBackground may return the iterator just put back (valid) or null when nothing waits any more, so assert next != null turns into if (next != null). Which sub-iterator Matches report when two have exactly equal intervals was not reviewed separately.
• Not reviewed by a committer. The window's right edge (queueEnd) is still only ever raised, as today. The bounded-exhaustive harness found no failure with the fix, but it covers documents of at most 6 positions.
• Not covered. A separate Weight#matches exception under some atLeast shapes (lead M2) has a different fix site and is not fixed by this patch.

What the checks validated

• Stock: the test fails 4 of 4 with assertions on and off.
• Fix: every interval suite of lucene/queries, 8 classes, 121 tests (117 upstream plus the 4 new), 0 failures.
• Fix, the whole :lucene:queries:test: 52 classes, 516 tests, 0 failures, with assertions on and off (5 and 6 randomized skips).
• Fix, the match and interval highlighter suites (164 tests) and TestStandardQPEnhancements (23 tests, fn:atLeast parsing): 0 failures.
• :lucene:queries:tidy leaves the fix and the test unchanged; :lucene:queries:check -x test passes (google-java-format, ecjLint, forbiddenApis).
• Standalone harness with the fix shadowed in: the test 4/4 (assertions on and off), the independent reproducer's 13 tests 13/13, the devil's advocate's probe 6/6, the k = 2 parser test 4/4, the security probe 6/6.
• Bounded-exhaustive harness: the atLeast-only tiers go from 15,840 and 8,082 failing checks to 0, and the local atLeast failures of three random depth-3 seeds disappear.

Move backgroundQueue.pop() out of the if in the first loop and null-check it.

Trade-offs

Smallest diff. Fixes the truncation and the missed nested matches (3 of the 4 tests pass), but leaves the stale re-entry: atLeast(1, b, phrase(a, b)) on "a b b" then gives [1,1], [0,1], [2,2], still with the non-minimal, out-of-order [0,1].

What the checks validated

Executed with the variant shadowed in: 4 run, 1 failed (expected:<[[1,1], [2,2]]> but was:<[[1,1], [0,1], [2,2]]>).

Intervals.atLeast already rewrites k = n and k > n; it could also map k = 1 to or(sources).

Trade-offs

Fixes the k = 1 cases, the most common trigger, without touching the iterator, but leaves every k >= 2 case. It also changes toString(), equals() and hashCode() of such queries, and since or() can hand its branches to a parent's rewrite (pullUpDisjunctions()) while atLeast returns only itself, parents may rewrite differently and Matches may report different sub-matches; minExtent() stays the same. A complement to option A at most.

Method: bounded-exhaustive translation validation (the hunt's semi-formal tier; no model checker, SMT solver or prover was involved).

• A hunt unit (spans and intervals), 2026-10-26. The harness ran the real interval sources of the stock main jars over every document of up to 6 positions over {a, b, c}, and up to 4 positions with stacked tokens, against every expression of the harness's grammar (level 1: every operator over terms; level 2: one child from a fixed pool of composite sources, the others terms; and binary operators with both children from that pool), and compared each interval list with an independent exact reference semantics: 1,401,702,324 checks.
• The exact-list check failed for atLeast: k = 1 in 131,652 of 221,130 checks, k = 2 in 20,070 of 110,565. Random depth-3 expressions with local-failure attribution added the stale-iterator cases.
• The finder, an AI tool, located the root cause by reading the code and wrote a deterministic public-API JUnit. With its fix sketch shadowed in, the atLeast-only tiers of the harness drop to 0 failures.