The same OR passed twice to Intervals.unordered or ordered skips the disjunction rewrite, so maxgaps and phrase miss real matches

Intervals.or promises that a disjunction under a gap-sensitive parent (maxgaps, phrase) is rewritten into one branch per combination of alternatives, because a disjunction drops any of its intervals that contains another one and a longer alternative would otherwise vanish (LUCENE-8477). Intervals.ordered and Intervals.unordered merge equal arguments into one RepeatingIntervalsSource (LUCENE-9099), and that source's pullUpDisjunctions() returns only itself, so the rewrite never reaches an or passed twice. With X = or(b, phrase(c, b)), maxgaps(0, unordered(X, X)) and maxgaps(0, ordered(X, X)) miss c b c b, phrase(a, ordered(X, X)) misses a c b c b, maxgaps(1, unordered(X, X)) misses b x c b, Intervals.analyzedText("york york", ...) (unordered, max gaps 0) with a synonym york => "new york" misses new york new york, and the flexible query parser's fn:maxgaps(0 fn:unordered(fn:or(b "c b") fn:or(b "c b"))) returns nothing; an equivalent but unequal second argument, or phrase(X, X), is rewritten and matches. It has shipped in every release since 8.5.0 (2020) and is not fixed upstream. A 15-line change that lets a whole repeat also expose its alternatives as ordered sequences, applied together with the LFV-807 fix (drop the ordered deduplication), fixes every whole-call case run and passes the repro and the queries, queryparser and highlighter test suites. On its own the change can add a false hit (executed), so the pair needs design review before it is proposed; a repeat inside a longer unordered still misses and needs a design decision. The ordered and phrase cases are also fixed by dropping the ordered deduplication (the sibling bug LFV-807); the unordered and analyzedText cases are unique to this bug.

• Interval and gaps. An interval is a run of positions [start, end]. gaps() counts the positions between an interval's immediate pieces, not inside them (IntervalIterator.java:62-71). Intervals.maxgaps(n, source) keeps an interval when gaps() <= n (FilteredIntervalsSource.java:47-50).
• Minimization. A disjunction's iterator skips any interval that contains the current one (DisjunctionIntervalsSource.java:222-247). So in or(b, phrase(c, b)) on c b, the interval of c b [0, 1] contains b [1, 1] and is dropped.
• The disjunction rewrite (LUCENE-8477). Because minimization can drop a longer alternative that a gap filter needs, gap-sensitive sources rewrite their sub-sources so that disjunctions are pulled up: maxgaps(0, ordered(X, Y)) becomes an or of maxgaps(0, ordered(x_i, y_j)) over the alternatives (Intervals.java:47-54, :118-122; FilteredIntervalsSource.java:31-36; Disjunctions.java:33-62). Each source exposes its alternatives through pullUpDisjunctions().
• The repeat (LUCENE-9099). ordered merges runs of consecutive equal arguments, unordered all equal arguments, into one RepeatingIntervalsSource, so that unordered(a, a) needs two different as (OrderedIntervalsSource.java:40-57, UnorderedIntervalsSource.java:44-57).

1. RepeatingIntervalsSource.pullUpDisjunctions() returns Collections.singleton(this) (RepeatingIntervalsSource.java:98-101). The rewrite sees one piece and leaves the or inside the repeat.
2. Inside the repeat, X is minimized: its long alternative is dropped wherever it contains the short one.
3. The repeat takes consecutive intervals of the minimized X, so it can only pair short alternatives that are further apart; the gap filter then rejects them.

c b c b (positions 0-3), X = or(b, phrase(c, b)). X's intervals are b [1, 1], c b [0, 1], b [3, 3], c b [2, 3]; minimization keeps [1, 1] and [3, 3]. The repeat pairs them into [1, 3] with width 1 + 1 = 2, so 1 gap, and maxgaps(0) drops it. The valid pair b [1, 1] + c b [2, 3] (width 3, 0 gaps) was never produced. With an unequal second argument, ordered(X, X2) is rewritten into four branches, one of them maxgaps(0, ordered(b, phrase(c, b))), which matches [1, 3] with 0 gaps.

Not affected: repeats of single words or of an or of single words (one piece after the split, Disjunctions.java:76-95), and phrase(X, X), which does not merge equal arguments and is rewritten.

• Who is exposed. Users of the intervals API (lucene/queries, opt-in; the package "contains experimental classes"), of the flexible query parser's interval functions (the fn: syntax exists since 9.1.0), and of Intervals.analyzedText with a query analyzer that gives a repeated word a multi-word alternative containing it. The query must pass the same disjunction twice or more to unordered (in any positions) or to ordered as neighbouring arguments (ordered merges only runs of equal neighbours, so ordered(X, d, X) is not affected), under maxgaps or phrase, and the document's only valid match must use a longer alternative. Downstream servers that expose interval queries were not run.
• Shapes that reach it (all executed). maxgaps(0, unordered(X, X)) and maxgaps(0, ordered(X, X)) on c b c b; phrase(a, ordered(X, X)) on a c b c b; maxgaps(1, unordered(X, X)) on b x c b; maxgaps(0, ordered(X, X, d)) and maxgaps(0, unordered(X, X, d)) on c b c b d; three copies; analyzedText("york york", ...) with a SynonymGraphFilter rule york => "new york" (keep original): unordered with max gaps 0 misses new york new york, and with max gaps 1 ordered and unordered miss new york x new york (ordered with max gaps 0 takes the phrase path and matches); and the query string fn:maxgaps(0 fn:unordered(fn:or(b "c b") fn:or(b "c b"))).
• What goes wrong. In the executed probes a positive query only lost hits: the repeated default or behaves like the documented opt-out or(false, ...), which "can miss valid hits due to minimization". A negation of such a query (MUST_NOT, notContaining) keeps documents it should drop (executed).
• Silent, default settings. No exception. A plain program with StandardAnalyzer, the default IndexWriterConfig and codec, a ByteBuffersDirectory and a plain IndexSearcher misses the document; the JUnit runs with the test framework's randomized codec, similarity and locale miss it too, with assertions on and off. Every run indexed one ordinary document (no crafted index); only one-document indexes were run, and the cause is in how the query is built, not in the index.
• How likely. Rare: the same multi-position or twice under a gap filter, plus a document whose only gap-free match mixes the alternatives. No report was found although the code has shipped since 8.5.0 (2020). For such a query and document the miss happens every time.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: f:MAXGAPS/0(UNORDERED(or(BLOCK(c,b),b),or(BLOCK(c,b),b))) on 'c b c b' expected:<1> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.queries.intervals.TestUnorderedRepeatedOrMaxGaps.testMaxGapsRewritesOrRepeatedInUnordered(TestUnorderedRepeatedOrMaxGaps.java:44)

• The default promises the rewrite. Class javadoc: "by default, sources that are sensitive to internal gaps (e.g. PHRASE and MAXGAPS) will rewrite their sub-sources so that disjunctions of different lengths are pulled up ... to ensure that documents containing "b c" are matched"; the opt-out is for when "you care more about speed than about accuracy" (Intervals.java:47-54). Intervals.or: "Automatically rewrites if wrapped by an interval source that is sensitive to internal gaps" (:118-122). Only or(false, ...) "can miss valid hits due to minimization" (:127-135).
• CHANGES calls the miss a bug. LUCENE-8477: "Interval disjunctions could miss valid hits if some of the clauses of the disjunction are minimized away. We now rewrite intervals if a source contains a disjunction and the internal gaps matter for matching" (lucene/CHANGES.txt:6502-6506). No javadoc, CHANGES entry or test exempts equal arguments.
• Equal objects decide. ordered(X, X2) with X2 = X plus an alternative that never occurs is rewritten and matches; phrase(X, X) matches; the hand-expanded rewrite matches. Users cannot see the deduplication.
• A side effect, not a decision. RepeatingIntervalsSource and its singleton(this) came with LUCENE-9099 (2020), a fix for repeated terms. Its commit message (also its PR body; one approving review, no inline comments) mentions disjunctions only for a separate fix to DisjunctionIntervalIterator#matches(), and its one repeated-or test, testMaxGapsWithOnlyRepeats (maxgaps(1, ordered(or(pease, hot), or(pease, hot)))), uses single-term alternatives, where the rewrite has nothing to do. None of them mentions the LUCENE-8477 rewrite or a disjunction whose alternatives have different lengths. Before it, 8.4.1 rewrote and matched the two-argument ordered and phrase cases.
• Maintainers on the rewrite (LUCENE-9204, #10244): "Intervals automatically rewrite disjunctions (and have done since LUCENE-8477) so that queries behave as your or I would expect them to"; and "there's nothing else to compare with since it's the key for correctness ... If it's not correct, it's a bug, not a feature".
• Nothing pins the current behaviour. Upstream repeat tests use single terms or an or of single terms; all 117 upstream intervals tests pass with fix A, and with A together with the LFV-807 fix.

The strongest case for "works as designed" (built or weighed by the cross-model reviews, the intended-behaviour check and the adjudication; the cross-model reviews rated it moderate): intervals use minimal-interval semantics (the class javadoc cites the Vigna paper); during LUCENE-8477 a reviewer warned that "we can find other pathological cases due to minimum interval semantics" and suggested documenting rather than rewriting; the rewrite was never total (atLeast is also opaque); the query parser docs say "the algorithm is not required to return or highlight all matching interval alternatives"; and keeping the repeat closed avoids a k^n expansion.

Why it fails: the merged design rewrites by default, and later maintainer statements treat a miss as a bug; the parser note is about which intervals of a matching document are reported, while here the document is not matched at all; unequal arguments and phrase(X, X) are already expanded, bounded by the clause limit; and the answer should not depend on whether two equivalent arguments are equal objects. The unordered half has a real design question (may the copies share positions?), which shapes the fix, not whether c b c b should match: its witness pair does not overlap. Verdict: a defect (adjudication: confirmed, high).

The candidate change makes a whole ordered(X, X) / unordered(X, X) behave like its unequal twin under a gap-sensitive parent: the parent sees the repeat itself plus every sequence of the copies' alternatives built as ordered. The copies stand for distinct occurrences, so, as long as each sequence is a real ordered (whose sub-intervals never overlap), these sequences are exactly "n occurrences without overlap", the construction Intervals.unorderedNoOverlaps uses. That condition needs the LFV-807 fix: without it, ordered folds a sequence of two equal alternatives back into a repeat whose copies may overlap. With W = or(b, unordered(a, b)), phrase(z, ordered(W, W)) then matches z a b a, although no two occurrences of W there are disjoint (stock 0, the change alone 1, the change with the LFV-807 fix 0; executed with assertions on and off). With both fixes, keeping the repeat itself keeps every match it has today, and the added sequences should only add documents that the unfiltered query also matches (reasoning, checked on the cases below). These runs cover the listed examples and the existing test suites, not the general semantics.

With A alone the three-copy case stays 0 because the sequence ordered(b, c b, c b) regroups the two c b into a repeat whose width has the LFV-306 sign error; with LFV-306's one-line fix also applied it gives 1. Two copies of or("a b", "b c") on a b c, which share the b, give the same as main under every fix. The phrase(z, ordered(W, W)) row is the over-match of A alone described above. With A + LFV-807 every row gives the expected value except unordered(X, X, d).

Not covered by any fix tried: a run of copies inside a longer unordered, such as unordered(X, X, d). Expanding it needs "the copies must not overlap each other but may overlap d": rebuilding the copies with unordered over-matches, and nesting an ordered of the copies hides that ordered's inner gaps from the parent, which would match b x c b d. No existing operator expresses this; it is the design question to raise upstream.

Workaround until a fix ships: make the second argument unequal with an alternative that never occurs and use ordered: maxgaps(0, ordered(X, or(b, "c b", zzz))) matches c b c b and not c b or b x b. Not with unordered: unequal unordered arguments may share a position, so that form also matches a lone b.

In RepeatingIntervalsSource.pullUpDisjunctions(), for a repeat that is a whole ordered/unordered call (name != null), return the repeat plus Disjunctions.pullUp(nCopies(childCount, in), OrderedIntervalsSource::build) when that yields more than one sequence (+15 lines in one method, comment included; abridged below). Apply it together with option B (the LFV-807 fix); alone it can over-match (trade-offs). Under maxgaps each returned source gets its own filter; under phrase the pieces of extent 1 (the repeat itself and, without B, the folded ordered(b, b)) are grouped into one or first. An or of single words still splits into one piece, so the tested single-word case builds exactly as before. The diff's comment ("ordered sub-intervals never overlap", "only adds matches") holds only with B.

What was run (the listed examples and the existing suites; not a proof of the general semantics):

• Scratch worktree of a9779ef3c193, gradle, JDK 25: stock + the new test, 4 of 5 fail with assertions on and off.
• + A: lucene/queries 52 suites, 517 tests (122 in the intervals package, 5 of them new), 0 failures with assertions on and off (5 and 6 skipped); lucene/queryparser 30 suites, 533 tests, and lucene/highlighter 34 suites, 722 tests, 0 failures (assertions on); :lucene:queries:check -x test (checkGoogleJavaFormat, ecjLint, forbiddenApis) passes.
• + A + B: the same three suites, 0 failures (lucene/queries with assertions on and off); :lucene:queries:check was not re-run for the pair. Standalone runner: the new test 5 of 5 and the over-match probe as expected on every line, with assertions on and off.
• Standalone runner, A alone: the new test 5 of 5 (on and off), the finder's 3 of 3 (on and off), the reproducer's 7 of 8 (only the longer-ordered scope test fails), the real-synonym probe all 1, and the fn: query string matches with Weight#matches agreeing. The multi-case query-parser probe it comes from still reports 5 failing lines, all from other bugs (they fail on stock too).

  public Collection<IntervalsSource> pullUpDisjunctions() {
    if (name != null) { // a whole ordered() or unordered() of equal sub-sources
      List<IntervalsSource> sequences =
          Disjunctions.pullUp(Collections.nCopies(childCount, in), OrderedIntervalsSource::build);
      if (sequences.size() > 1) {
        List<IntervalsSource> pulledUp = new ArrayList<>(sequences.size() + 1);
        pulledUp.add(this); // keep every match the repeat has today
        pulledUp.addAll(sequences);
        return pulledUp;
      }
    }
    return Collections.singleton(this);
  }

Trade-offs

• Over-match without B (executed). OrderedIntervalsSource.build folds a sequence of equal alternatives back into a repeat, and that repeat lets its copies overlap (LFV-807). With W = or(b, unordered(a, b)), phrase(z, ordered(W, W)) on z a b a gives 1 with A alone, 0 on stock and 0 with A + B; the unequal control gives 0. Found by the cross-model fact check from the source, then run with assertions on and off.
• Open: name and equals. A lets name decide what pullUpDisjunctions() returns, but RepeatingIntervalsSource.equals and hashCode ignore name, so a named whole-call repeat and an otherwise equal unnamed repeat inside a longer ordered/unordered compare equal but rewrite differently. Resolve before proposing (read, not executed).
• Cost, like the documented rewrite of unequal arguments: k^n + 1 branches for n copies of k pieces, with the clause limit applied at query construction. An or of 32 two-word phrases passed twice builds 1,025 branches; 33 throw IllegalArgumentException: Too many disjunctions to expand, where today the repeated form builds unexpanded and the unequal form already throws from 32. So a query that builds today can be rejected.
• Does not cover a run inside a longer ordered (fixed by LFV-807's change) or a longer unordered (open design question).
• Scores and Weight#matches see the extra branches only where they add intervals; no benchmark was run.

The ordered iterator already keeps sub-intervals from overlapping, so equal ordered arguments need no repeat. Fixes the ordered and phrase cases, ordered(X, X, d) and LFV-807.

Trade-offs

Alone it does nothing for unordered, which keeps the repeat so that unordered(a, a) does not match one a: with it the unordered and analyzedText tests still fail (executed). Together with A it also removes A's over-match, because A's sequences are then real ordered sources (executed).

Distribute the alternatives over the copies and rebuild with unordered for an unordered repeat.

Trade-offs

Passes the three headline cases but adds false hits under the filter: maxgaps(0, unordered(X, X)) matches c b and b x c b, and three copies match c b c b, none of which the unfiltered query matches (executed). Rebuilt unordered lets c b pair with the b inside it. It also gives 1 for phrase(z, ordered(W, W)) on z a b a and for maxgaps(0, unordered(W, W)) on a b a (executed).

Say in the Intervals.or and ordered/unordered javadocs that equal arguments are not rewritten.

Trade-offs

Keeps silent misses for analyzedText and query-parser users, who cannot see or control the deduplication.

Method: modelling with a reference semantics, then bounded-exhaustive translation validation on the stock main jars (the hunt's "semi-formal" tier).

• A hunt unit on interval repeats and disjunction pull-ups wrote a reference semantics for interval queries from the javadoc (IvRef290). While modelling an earlier lead (how or is distributed under gap-sensitive parents, with repeat groups taken from the user's arguments), the finder noticed that a repeated disjunction is never distributed and confirmed it with a direct probe.
• Its harness (IvTV290) ran the stock interval iterators against the reference on every non-empty document of 1 to 4 positions over a three-symbol alphabet (120 documents), for 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: 1,100,295 checks and 23,917 failures on stock main. With switchable shadow fixes for known bugs and for the unit's other candidates, applied one by one (1,100,515 to 1,100,533 checks per configuration), the failures fell to 17,058, 13,789, 13,469, 3,596 and 1,098, and the last 1,098 went to 0 only with this fix site.
• The finder reduced it to a one-document public-API JUnit; independent AI tools then reproduced, reviewed and judged it (see the checks).