A nested Intervals.ordered(a, a) or unordered(a, a) passes its inner gap to its parent, so maxgaps misses matches

Intervals.ordered and Intervals.unordered fold equal sub-sources into an internal RepeatingIntervalsSource. When every argument is equal (ordered(a, a), unordered(a, a)), the whole operator is replaced by that repeat source, whose iterators compute width() per copy (1 + 1 = 2 for the two one-position copies in a x a) instead of over the interval's span (3). Counting per copy is right for a run inside a larger operator (ordered(a, a, b)), but when the repeat stands for a whole operator nested in another ordered or unordered, the parent, which computes its gaps as its span minus its children's widths, counts the child's inner gap as its own. maxgaps(0, ordered(ordered(a, a), a)) therefore misses a x a a while maxgaps(0, ordered(ordered(a, b), a)) matches a x b a; ordered(unordered(a, a), b) misses a x a b in every release since 8.5.0. Weight#matches agrees with the scorer, used as an exclusion the query keeps documents it should remove, and a no-op maxwidth(100, ...) around the pair restores the hit. Not fixed upstream; a role-aware width() plus role-aware equals/hashCode in one class fixes it.

1. The collapse. OrderedIntervalsSource.build passes its arguments through deduplicate (OrderedIntervalsSource.java:29-38), which turns each run of equal sub-sources into RepeatingIntervalsSource.build(source, count) (:40-57). When everything collapses into one repeat source, it gets ris.setName("ORDERED") (:53-55) and is returned as the whole operator (:34-35). UnorderedIntervalsSource does the same with a count map (UnorderedIntervalsSource.java:33-57, setName("UNORDERED") at :53-55). The name is read only by toString() (RepeatingIntervalsSource.java:123-125).
2. The summed width. The class javadoc: the iterators have "a specialized IntervalIterator#width() implementation that sums up the widths of the individual sub-iterators, rather than just returning the full span of the iterator" (RepeatingIntervalsSource.java:38-40). DuplicateIntervalIterator.width() adds one term per copy (:156-164): cache[pos * 2] - cache[pos * 2 + 1] + 1 (:161), that is start - end + 1, which is the copy's width only for a one-position copy such as a term (for longer copies the sign is wrong: the separate LFV-306; the repro uses terms, so its numbers do not depend on it). DuplicateMatchesIterator.width() sums end - start + 1 per copy for Weight#matches (:315-322); neither looks at the name.
3. The parent reads child widths. The ordered iterator starts from end - start + 1 and subtracts every child's width() (OrderedIntervalsSource.java:166-172); gaps() returns the result (:185-186). The unordered iterator does the same (UnorderedIntervalsSource.java:158-161), and so does atLeast (MinimumShouldMatchIntervalsSource.java:235-238, from reading only).
4. Equality hides the nesting too. hashCode/equals ignore the name (RepeatingIntervalsSource.java:103-114): ordered(x, ordered(a, a)).equals(ordered(x, a, a)) is true, while the (a, b) pair is not equal. A query cache cannot tell the nested query from the flat one.
5. Why wrappers hide it. IntervalFilter (behind maxwidth and maxgaps) does not override width(), so a filtered child reports its span. or() and extend() hide it too: their interval iterators (DisjunctionIntervalIterator, DisjunctionIntervalsSource.java:154, and ExtendedIntervalIterator) do not override width() either, so they report the span, and maxgaps(0, ordered(or(ordered(a, a), z), a)) and maxgaps(0, ordered(extend(ordered(a, a), 0, 0), a)) both find a x a a (executed). Only the matches iterator of extend() passes the child's width through (ExtendedIntervalsSource.java:70).

Same root, part of the fix scope: a top-level ordered(a, a) reports width() 2 for [0,2], where ordered(a, b) reports 3, against IntervalIterator#width's "The width of the current interval" (IntervalIterator.java:73). For intervals that are evaluated as matches, scoring and maxwidth use end - start + 1 (IntervalScorer.java:65, FilteredIntervalsSource.java:67-69), not width(); the bug changes whether a document matches at all.

• Trigger paths (executed). The Java factories (ordered(ordered(a, a), a), ordered(x, ordered(a, a)), ordered(unordered(a, a), b), unordered(ordered(a, a), b)); StandardQueryParser strings such as fn:maxgaps(0 fn:ordered(fn:ordered(a a) a)), which misses a x a a; Intervals.analyzedText of a phrase with a repeated word and maxGaps -1, which returns a bare ORDERED(bora,bora) (IntervalBuilder.java:143-146), so maxgaps(0, ordered(analyzedText("bora bora", ..., -1, true), island)) misses bora x bora island while the stricter maxGaps 5 finds it; Intervals.unorderedNoOverlaps(a, a), which builds ORDERED(a,a) (Intervals.java:445-447).
• Default settings. Default codec, analyzer and searcher, assertions on and off (the runs used a one-document in-memory index). Nothing is written to the index; only query results change.
• Silent and consistent. No exception; Weight#matches returns null like the scorer, which is consistent with match-based highlighters also seeing no match (no highlighter was run).
• Both directions. As a filter it loses documents; as an exclusion it keeps them: MatchAll MUST plus IntervalQuery(maxgaps(0, ordered(ordered(a, a), a))) MUST_NOT, and Intervals.notContainedBy(x, maxgaps(0, ordered(ordered(a, a), a))), return 1 hit on a x a a instead of 0.
• How likely. Rare: it needs a nested whole repeat, a gap limit above it and non-adjacent repeats (on a a b there is no inner gap to leak). The recorded searches found no report of it, although it has shipped since 8.5.0 (2020). For such a query and document the miss happens every time.

The test sits in org.apache.lucene.queries.intervals only for locality; it uses only public API (Intervals, IntervalQuery). ByteBuffersDirectory, core StandardAnalyzer (no stop words), one document, a plain IndexSearcher, nothing random: deterministic, single thread. The same test is the suggested regression test.

Why this shape and not ordered(ordered(a, a), a): the sibling bug LFV-807's fix (no deduplication in ordered) would also remove the ordered(a, a)-as-child shapes, but unordered must keep deduplicating, so this test keeps failing until this bug is fixed (run with LFV-807's fix alone: still fails; with both fixes: passes).

On 9.0.0 and earlier, LuceneTestCase lives in org.apache.lucene.util: change that one import. On 8.4.1 the test passes for another reason: there unordered(a, a) matched a single a (the bug LUCENE-9099 fixed), so the hit came from [2,3].

cp $REPRO/TestNestedRepeatMaxGaps.java $LUCENE/lucene/queries/src/test/org/apache/lucene/queries/intervals/
cd $LUCENE
./gradlew :lucene:queries:test --tests org.apache.lucene.queries.intervals.TestNestedRepeatMaxGaps -Ptests.seed=DEADBEEF
# production setting (assertions off): add -Ptests.asserts=false

# gradle, main 5adff78bb168, seed DEADBEEF, assertions on (the same with -Ptests.asserts=false)
TestNestedRepeatMaxGaps > testMaxGapsZeroOverNestedRepeat FAILED
    java.lang.AssertionError: f:MAXGAPS/0(ORDERED(UNORDERED(a,a),b)) on 'a x a b' expected:<1> but was:<0>

# with the recommended fix: BUILD SUCCESSFUL, assertions on and off

# JUnit runner, seed DEADBEEF, assertions on: the same failure on 10.6.0, 10.5.2, 10.1.0, 10.0.0, 9.12.3, 9.1.0,
# 9.0.0, 8.11.4 and 8.5.0; 8.4.1 passes (unordered(a, a) then matched a single a)

# the 11-test probe of the independent reproducer on 5adff78bb168 (seed 5ADFF78B, assertions on and off): 4 of 11 fail
ordered(ordered(a,a),a) on 'a x a a'     expected 0-3/0 | maxgaps0.hits=1 matches=non-null, got 0-3/1 | hits=0 matches=null
ordered(x,ordered(a,a)) on 'x a y a'     same
ordered(unordered(a,a),b) on 'a x a b'   same
unordered(ordered(a,a),b) on 'a x a b'   same
controls (the four with (a,b)/(a,c), the no-op maxwidth wrapper, flat ordered(x,a,a), top-level ordered(a,a)): correct
EQUALITY repeated nested.equals(flat)=true [ORDERED(x,ORDERED(a,a)) vs ORDERED(x,a,a)]; unequal nested.equals(flat)=false

• Contract. "Note that this returns the number of gaps between the immediate sub-intervals of this interval, and does not include the gaps inside those sub-intervals." (IntervalIterator.java:65-66). Package docs: maxgaps "Filters out intervals that have more than a set number of gaps between their constituent sub-intervals" (package-info.java:55-57).
• Design text. LUCENE-8597 (#9643), which added gaps(): ordered/unordered combinations "would return the number of positions separating their immediate children. Note that this does not include the gaps within any of those children themselves."
• Maintainer intent for nesting. #13819 (jimczi, merged 2024-10-03): "ordered(\"a\", ordered(\"b\", \"c\")) should result in a different gap compared to ordered(\"a\", \"b\", \"c\")"; "The flattening that is currently applied prevent some valid queries to match". Its tests testOrderedWithNoGap and testUnorderedWithNoGap (TestIntervalQuery.java:375-385, :341-351) use distinct terms; TestIntervals#testNestedMaxGaps (TestIntervals.java:751-768) treats a nested ordered as one sub-interval of its full span.
• LUCENE-9099's own issue text (#10141): rewriting UNORDERED(a, b, c, a, b) to UNORDERED(ORDERED(a, a), ORDERED(b, b), c) "then breaks MAXGAPS filtering", i.e. a nested ORDERED(a, a) hides its inner gaps from the parent.
• No consistent semantics explains the current answers. The unequal twin matches; a filter that removes nothing (maxwidth(100, ...), maxgaps(1000, ...)) around the pair flips 0 hits to 1; a stricter analyzedText (maxGaps 5) finds a document the unrestricted one (-1) misses; and whether two arguments compare equal changes the result.
• No upstream test pins the current value. The repeat tests (TestIntervals.java:729-749, TestSimplifications.java:41-68) cover runs inside a larger operator and top-level repeats; all 1,768 tests of the queries, queryparser and highlighter modules pass with the fix.

The strongest case for "intended": the RepeatingIntervalsSource javadoc sums the widths on purpose, and the LUCENE-9099 commit says this "preserves maxgaps filtering on ordered and unordered sources that contain repeats"; when LUCENE-9099 landed, nested ordered sources were flattened anyway, so ordered(ordered(a, a), a) meaning ordered(a, a, a) was the semantics of the day; the package is "experimental" (package-info.java:21); #13819's tests use only distinct terms; and a user could write ordered(a, a, a).

Why it fails: the javadoc is on a package-private class and describes the run role (ordered(a, a, b), where each copy is an immediate sub-interval of the parent); the class cannot tell that role from the whole-operator role, whose only marker, the name, nothing reads. #13819 replaced the flattening semantics with exactly the rule this violates. Flattening never crossed operator types, so ordered(unordered(a, a), b) leaking while ordered(unordered(a, c), b) did not was inconsistent even before 10.1.0, and that query has no flat equivalent. "Experimental" is about API stability, not wrong hit counts. The reviews did not all agree in form: the devil's-advocate verifier, which ran its own probes, rejected the argument (real, high confidence that it is not intended); read-only reviews by an independent reviewer from another model family (OpenAI GPT-5.6), which could not run code, both rated the argument moderate. The intended-behaviour review rated the bug real (medium); the refute review returned "not real" (low) because no test could run, and noted that the static evidence favours a defect.

Three options. A was built and validated on main 5adff78bb168; B was not built; C (the sibling LFV-807's fix) was run and fixes only part of this bug. Any fix should also update the RepeatingIntervalsSource class javadoc, and it composes with LFV-306's one-line sign fix in the same width() loop (that fix alone leaves this bug).

A repeat source with a name (it stands for a whole ordered/unordered) passes wholeSource = true to its iterators: DuplicateIntervalIterator.width() returns super.width() (the span) and gaps() keeps subtracting the copies' widths; DuplicateMatchesIterator.width() returns endPosition() - startPosition() + 1. equals adds (this.name != null) == (o.name != null) and hashCode adds name != null. The class javadoc explains the two roles. One file, +31/-12.

@Override
public int width() {
  return wholeSource ? super.width() : copyWidths(); // copyWidths(): the old summing loop
}

@Override
public int gaps() {
  return super.width() - copyWidths();
}

Trade-offs

• The equality part is needed: with a width-only change and the test framework's query cache on, ordered(x, ordered(a, a)) was served the cached result of the equal flat ordered(x, a, a) and still had 0 hits.
• Keeps the collapse and what TestSimplifications asserts (ordered(a, a) still equals unorderedNoOverlaps(a, a)); relies on the name, set after construction, as the role marker.
• A top-level ordered(a, a) now reports width() 3 for [0,2] instead of 2. width() is read only by parent operators (ordered, unordered, atLeast) and by matches iterators (every .width() call in the intervals package); scoring and maxwidth use end - start + 1.
• What the validation does not show: the runs show that the change makes the repro pass and breaks none of the module tests; they say nothing about how maintainers will judge the approach (a role flag set after construction), about API compatibility beyond these tests, or about performance (no benchmark was run).

What the checks validated

• Gradle in a scratch worktree of 5adff78bb168, OpenJDK 25.0.3, seed DEADBEEF: stock, the repro fails with assertions on and off; with the fix it passes, on and off.
• All tests of the queries, queryparser and highlighter modules pass with the fix and the repro in place: 116 classes, 1,768 tests, 0 failures, 6 skipped.
• checkGoogleJavaFormat, ecjLint, forbiddenApisMain and renderJavadoc of lucene/queries pass.
• The independent reproducer's 11-test probe passes 11 of 11 with the same approach applied.

When deduplicate returns a single repeat source, wrap it in an OrderedIntervalsSource / UnorderedIntervalsSource with that one child instead of returning it, so the wrapper reports its span and the repeat its inner gaps.

Trade-offs

No role flag, and ordered(x, ordered(a, a)) stops equalling ordered(x, a, a) without touching equals. But it adds an iterator layer per nested repeat, the one-child conjunction path is untested, and the toString/equality assertions in TestSimplifications need checking.

Removing deduplicate from OrderedIntervalsSource.build (proposed for LFV-807) removes the ordered(a, a)-as-child shapes, but unordered must keep deduplicating so that unordered(a, a) does not match a single a.

Trade-offs

Fixes LFV-807 and part of this bug; use it together with A, not instead of it.

What the checks validated

Run on 5adff78bb168: the repro still fails with C alone and passes with A and C together.

Method: semi-formal (bounded-exhaustive translation validation). A reference semantics for intervals was written from the javadoc, independently of Lucene's code. A test program enumerated every document of 1 to 4 positions over {a, b, U+10428} and 6,856 expressions of depth up to 3 over term, ordered, unordered, or, phrase, maxgaps(0|1) and atLeast(2 of 3), with repeated arguments, and compared exact minimal intervals, gaps, IntervalQuery hits and Weight#matches with the stock main jar: 1,100,295 checks.

• The mismatches were then attributed with switchable fixes: with the fixes of the related repeat bugs applied, 13,469 mismatches remained; adding this fix brought them down to 3,596 (the rest belong to other defects).
• The case was reduced to a public-API JUnit test on the stock jar, which failed with assertions on and off.