Intervals.ordered(X, X) lets the two copies of X overlap when X's own intervals can share a position

Intervals.ordered(X, X) asks for X and then X again, and as in every ordered interval query the two parts must not overlap. When the two arguments are equal (by equals(), so also two identically built sources), OrderedIntervalsSource.build replaces them with one RepeatingIntervalsSource, the repeat handling LUCENE-9099 added in 8.5.0. Its iterator joins consecutive intervals of a single X iterator, [first start, last end], and never checks that they are disjoint. For a single term with one token per position that is harmless, since its consecutive intervals are different positions; but when X spans several positions and can overlap itself, the copies share a position: ordered(unordered(a, b), unordered(a, b)) matches a b a (one b), ordered(phrase(a, a), phrase(a, a)) matches a a a, and the same happens through Intervals.unorderedNoOverlaps(X, X) and the query parser's fn:ordered and fn:unorderedNoOverlaps. A term stacked twice at one position (position increment 0) overlaps the same way: ordered(cat, cat) matches the one-word document cat indexed through KeywordRepeatFilter and a stemmer that leaves the word unchanged. Matching documents get wrong intervals too ([0,2], [1,3] instead of [0,3]), and Weight#matches reports them. With an equivalent but unequal second argument the query correctly finds nothing, and so did 8.4.1. Every release from 8.5.0 to 10.6.0 and main are affected with default settings. Dropping the deduplication from OrderedIntervalsSource.build fixes it; the repro and the queries, queryparser and highlighter suites pass with it.

• Interval: a span of positions [start, end] in a field where a sub-query matches. Intervals.term("a") on a b a gives [0,0] and [2,2]; Intervals.unordered(a, b) ("a and b in any order, as close as possible") gives [0,1] and [1,2], which share position 1; Intervals.phrase("a", "a") on a a a gives [0,1] and [1,2].
• Stacked token: two tokens at one position (position increment 0), for example a word and its unchanged stem from KeywordRepeatFilter and a stemmer. If both are a, the postings keep both and Intervals.term("a") gives [0,0] twice.
• ordered(X, Y): an interval that contains an X interval followed by a Y interval that starts after the X interval ends. fn:ordered in StandardQueryParser maps to it; unorderedNoOverlaps(X, Y) is built as or(ordered(X, Y), ordered(Y, X)).

1. OrderedIntervalsSource.build calls deduplicate (OrderedIntervalsSource.java:29-38), which turns each run of consecutive equals() sub-sources into RepeatingIntervalsSource.build(source, runLength) (:40-57); a single run is returned on its own, renamed "ORDERED" (:53-55).
2. RepeatingIntervalsSource.intervals wraps one iterator of the sub-source in a DuplicateIntervalIterator (RepeatingIntervalsSource.java:66-72). It caches n consecutive intervals of that iterator and reports the first cached start and the last cached end (:145-154, :172-200). Nothing compares one cached interval's start with the previous one's end.
3. For ab = unordered(a, b) on a b a the cache holds [0,1] and [1,2], so ordered(ab, ab) reports [0,2]: 1 hit with a single b.
4. For unequal sub-sources each gets its own iterator, and OrderedIntervalIterator advances each one while currentStart <= prevEnd (OrderedIntervalsSource.java:144-151), so the copies can never share a position. That is why ordered(ab, or(ab, zzz)) gives 0.
5. RepeatingIntervalsSource.matches combines the sub-matches the same way (:75-86), so Weight#matches reports the same wrong interval (executed); highlighters built on it would show it too (read, not run).
6. A single term is safe only while each position holds it once. TermIntervalsSource returns every posting position (TermIntervalsSource.java:114-120, 127-135), so a term stacked twice at position 0 yields [0,0] twice, the cache joins them into [0,0], and ordered(a, a) matches a document with a single position.

One-document index, main a9779ef3c193, assertions on and off (the tests use the test framework's randomized config; the probes use a plain IndexWriterConfig and give the same answers):

Two separately built unordered(a, b) sources are equal, so they take the same path; fn:ordered("a a" "a a") builds two equal phrases from query text.

• Who. Users of Intervals.ordered or Intervals.unorderedNoOverlaps (Java API since 8.5.0) or of StandardQueryParser's fn:ordered / fn:unorderedNoOverlaps (query text since 9.1.0) whose query gives the same sub-source twice in a row, where that sub-source spans several positions and its consecutive intervals can share one: a near pair (unordered(a, b)), a phrase whose words repeat (phrase(a, a); phrase(ha, ha) on ha ha ha also matches), or a nested ordered / unordered. ordered(X, X) is a direct way to ask for "X twice". Also anyone who repeats a single word that their analysis chain stacks twice at one position, for example KeywordRepeatFilter before a stemmer that leaves the word unchanged, without RemoveDuplicatesTokenFilter: ordered(cat, cat) then matches the one-word document cat.
• Effect. Silent extra hits, and wrong intervals on documents that do match. Weight#matches returns the same wrong positions (executed), which can carry over into match-based highlighting and enclosing interval filters; of those only maxgaps was tested directly (containing, containedBy, notContaining follow from the intervals, read). No exception, no hang, nothing written to the index.
• Default vs opt-in. Nothing to enable: a plain IndexWriterConfig with the default codec, the default searcher, any index size, assertions on and off (executed by the probes); the JUnit tests use the test framework's randomized config and fail the same way.
• Not affected. Repeats of single words when each position holds the word once (ordered(a, a) on a a a), phrases that cannot overlap themselves (phrase(new, york): not by this overlap, though their gaps are still wrong through LFV-306), and unordered(P, P) matching a a a, which is correct because unordered sources "may overlap" (Intervals.java:432).
• How likely. It needs that query shape and a document where two of its intervals share a position; for such a pair the false hit happens every time. The trigger is structurally narrow and no report was found although it has shipped since 8.5.0 (2020); how often it happens in practice is unknown.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: f:ORDERED(BLOCK(a,a),BLOCK(a,a)) on 'a a a' expected:<0> but was:<1>
       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.TestOrderedRepeatedPhraseOverlap.testOrderedCopiesOfPhraseMustNotOverlap(TestOrderedRepeatedPhraseOverlap.java:44)

• The contract. fn:ordered: "Source intervals must not overlap", with the example fn:ordered(fn:phrase(brown fox) fn:phrase(fox jumps)) "(Sources overlap, no matches.)" (intervalfn/package-info.java:328-356, LUCENE-10223, 9.1.0); upstream TestMatchHighlighter asserts no hit for it and for fn:unorderedNoOverlaps of the same phrases (TestMatchHighlighter.java:396-397). Intervals.unorderedNoOverlaps: "Returns intervals in which both the subsources appear and do not overlap" (Intervals.java:440-447).
• The cited algorithm. The Intervals class javadoc says "These sources implement minimum-interval algorithms taken from the paper Efficient Optimally Lazy Algorithms for Minimal-Interval Semantics" (Boldi and Vigna, Intervals.java:43-45); there the ordered operator is the "ordered non-overlapping conjunction operator" and "the intervals must be nonoverlapping".
• Design note. LUCENE-8828 (#9872, 2019, by the later author of LUCENE-9099): "NO_OVERLAPS(a, a) will end up as ORDERED(a, a)".
• Self-consistency. ordered(ab, or(ab, zzz)) (0) and ordered(ab, ab) (1) differ on a b a though their sub-intervals are the same; ordered(a, a, a, a) gives 0 on a a a; the span analogue (SpanNearQuery in order over two near(a a)) gives 0.
• History. No evidence was found that LUCENE-9099 (#10141, lucene-solr#1097, 7c1ba1aebee) considered this case. It fixed two term cases: ORDERED(a, a, b) returning an extra interval and UNORDERED(a, a) matching a single a. Its CHANGES entry says "repeated subterms", the class javadoc "repeated terms within an unordered interval", and every test it added repeats a single-position source: a term, or in testMaxGapsWithOnlyRepeats the disjunction or(pease, hot) (TestIntervals.java:739-749). One approving review, no inline comments; nothing relaxes the no-overlap rule. 8.4.1 gives 0, 8.5.0 gives 1, and 8.5.0 with only the deduplicate() call removed gives 0 again.

The intended-behaviour checker, the second cross-model review and the adjudication built the strongest "intended" case: the Intervals.ordered javadoc alone says only "intervals in which the subsources all appear in the given order" (Intervals.java:415-421), not "non-overlapping"; LUCENE-9099 sent equal sources through RepeatingIntervalsSource on purpose, which could mean "N consecutive occurrences of X" with its own semantics; and the package is experimental.

Why it fails: the paper the class javadoc cites, the fn:ordered docs, the unorderedNoOverlaps javadoc and LUCENE-8828 all state the no-overlap rule; the equal and unequal forms of one query disagree; no record shows LUCENE-9099 discussing sub-sources whose intervals can overlap each other; and "experimental" is about API stability, not wrong results. Verdict: not intended, a regression. Expect the bare ordered javadoc to come up first; answer with the fn:ordered sentence and the unequal-copy control.

One fix was applied in a scratch worktree at a9779ef3c193 and run through gradle; the alternatives were not run. Land it before, or together with, the fix for the repeat width sign (LFV-306): that one-line fix alone makes maxgaps(0, ordered(P, P)) match a a a, because the overlapping interval's gaps turn from 3 to -1.

deduplicate() goes away; build returns new OrderedIntervalsSource(new ArrayList<>(sources)) for two or more sources. Equal sub-sources then get separate iterators like unequal ones. UnorderedIntervalsSource keeps its own use of RepeatingIntervalsSource. The copy keeps what the old code passed (a fresh list, not the caller's varargs view). The hunt's version passed sources directly: the same results in every run, but it keeps the Arrays.asList view of the caller's array (Intervals.java:422-424), so changing that array later would change the query. The code comment's "multi-position source" could also name a term stacked at one position.

  static IntervalsSource build(List<IntervalsSource> sources) {
    if (sources.size() == 1) {
      return sources.get(0);
    }
    // No deduplication: OrderedIntervalIterator gives every sub-source its own iterator and never
    // lets two sub-intervals overlap, so equal sub-sources need no special handling. Merging them
    // into a RepeatingIntervalsSource would let the copies of a multi-position source overlap.
    return new OrderedIntervalsSource(new ArrayList<>(sources));
  }

Trade-offs

• ordered(t, t) of a term now opens two postings iterators instead of one (small, not benchmarked). toString stays ORDERED(...), and TestSimplifications (unorderedNoOverlaps(term, term) equals ordered(term, term)) still passes.
• LUCENE-9099's own examples keep their answers: ordered(a, a, b) on a a b gives only [0,2], and containing(ordered(x, y), ordered(a, a, b)) on a x a b y gives 0.
• It also removes the ordered() half of LFV-306 (repeat width sign) and the ordered manifestations of three sibling findings in the same class (minExtent, nested width, disjunction rewrite); their unordered() halves need their own fixes.
• A PR also needs a CHANGES entry; no benchmark was run.

What the checks validated

• In a scratch worktree at a9779ef3c193, gradle: the 7 repro tests pass with assertions on and off, and 50 of 50 plus 20 of 20 over 10 iterations (seed C0FFEE34); lucene/queries 517 tests (including TestIntervals 43 and TestSimplifications 12), lucene/queryparser 535 and lucene/highlighter 722 (including TestMatchHighlighter), 0 failures, the same skips as stock; on stock the same suites fail only on the 7 repro tests; ecjLint, checkGoogleJavaFormat and renderJavadoc pass; tidy changes nothing.
• Earlier, by shadowing the class on main: the hunt's repro, the independent reproducer's 11 tests and upstream TestIntervals 43 of 43 pass; in the hunt's bounded-exhaustive harness the ordered-repeat mismatches disappear only with this fix.
• The stacked-term probe with the patched class shadowed on main: 0 of 12 checks bad, assertions on and off.
• The full validation is on main only; the 8.5.0 A/B ran only the four bug checks, so a backport to an older branch needs its own test run.

A serious alternative a committer may prefer: deduplicate only sub-sources whose intervals are always one position wide, such as terms, keeping the one-iterator saving for ordered(a, a). On its own it does not fix the stacked-term case, whose intervals are one position wide: the repeat iterator would also have to skip a cached interval that starts at or before the previous one ends.

Trade-offs

Needs a reliable "single-position" test; minExtent() is only a lower bound (or(a, phrase(b, c)) has minExtent 1 and two-position intervals), plus the same-position skip. More code for a small saving.

Advance the shared iterator until the next cached interval starts after the previous one ends.

Trade-offs

With one shared iterator it cannot go back to an interval it skipped, which the next match may need, so it would need a buffer: a re-implementation of what OrderedIntervalIterator already does with separate iterators.

A javadoc note on Intervals.ordered.

Trade-offs

Contradicts the fn:ordered docs and the unorderedNoOverlaps javadoc, and keeps the equal-vs-unequal disagreement.

Make the second copy unequal but equivalent: ordered(X, or(X, term-that-never-occurs)) (executed as the control in every test).

Trade-offs

Relies on an implementation detail (equality); an extra disjunction per query.

Method: bounded-exhaustive translation validation on the real jar (semi-formal tier), in two hunt units on interval queries.

• First signal (2026-10-26): a unit on span and interval queries ran the stock main jar's interval iterators against an independently written reference semantics on every small document and recorded extra and missing intervals for ordered with repeated arguments as a lead: "ordered(X, X) is built as a RepeatingIntervalsSource, which lets the two X intervals overlap".
• Reduction (2026-10-27, main a9779ef3c193): a second unit wrote its own reference and harness: 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, on every document of up to 6 positions over a 3-letter alphabet, with switchable fixes for every suspected fix site. At 4 positions (about 1.1 million checks per run) the mismatches fell from 3,596 to 1,098 when this fix was added to the others, and to 0 with all of them; at 6 positions (11,287,592 checks) 0 remained with all seven fixes.
• Then a public-API JUnit test on the stock jar, controls first; checked by an independent reproducer, an intended-behaviour devil's advocate, reading-only reviews by a model from another family (OpenAI GPT-5.6) and an adjudication, then a history sweep and a prior-report search.
• The stacked-term case (2026-10-28) came from a cross-model fact check of this doc, which inferred it from the code; a public-API probe then executed it on main, 8.4.1, 8.5.0 and 10.5.2. The harness's documents hold one token per position, so it could not reach this case.