Repeating a multi-word piece in Intervals.ordered or unordered breaks maxgaps: the width is computed with the sign flipped

Intervals.ordered (for equal sub-sources next to each other) and Intervals.unordered (for equal sub-sources anywhere) merge them into one RepeatingIntervalsSource, so that two copies of the same piece cannot match the same occurrence. Its iterator reports, as width(), the sum of the copies' widths, and gaps() is the interval's span minus that sum: the positions between the copies. The iterator caches each copy's start and end and adds start - end + 1 per copy instead of end - start + 1. For a single word the two agree (both 1), so repeated words work; for a piece of len positions each copy adds 2 - len instead of len, and gaps() is too large by 2 * (len - 1) per copy. Two back-to-back copies of the phrase "new york" in "new york new york" report width 0 and gaps 4 instead of width 4 and gaps 0, so maxgaps(0, ordered(ny, ny)) and maxgaps(0, unordered(ny, ny)) find nothing, and a parent ordered/unordered that contains the repeated piece inherits the error. The Matches path of the same class, written in the same commit, uses the right formula, so Weight#matches reports a match for the document the scorer rejects. Intervals.analyzedText builds the shape from plain text with a stop-word hole or a multi-word synonym, and the flexible query parser from fn:maxgaps(0 fn:ordered("new york" "new york")). The line dates from LUCENE-9099 (2020) and every release since 8.5.0 has it. Swapping the two operands fixes it (validated with the repro, a new TestIntervals test and the whole lucene/queries module).

• Interval: a run of positions [start, end] in a field; IntervalIterator#width() is by default end() - start() + 1 (IntervalIterator.java:73-76).
• Gaps: IntervalIterator#gaps() "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:62-71). Intervals.maxgaps(n, source) keeps an interval when gaps() <= n (FilteredIntervalsSource.java:47-50).
• Repeating source: Intervals.ordered merges consecutive equal sub-sources, Intervals.unordered equal sub-sources anywhere, into one RepeatingIntervalsSource (OrderedIntervalsSource.java:40-57, UnorderedIntervalsSource.java:44-57). Its iterator "sums up the widths of the individual sub-iterators, rather than just returning the full span" (RepeatingIntervalsSource.java:38-40), and its gaps() is the span minus that sum (:166-169).

1. The cache. For each copy the iterator stores cache[2i] = start and cache[2i + 1] = end (RepeatingIntervalsSource.java:197-198).
2. The flipped subtraction. width() adds cache[pos * 2] - cache[pos * 2 + 1] + 1, that is start - end + 1, per copy (:156-164, line 161). A copy of len positions adds 2 - len instead of len.
3. Gaps too large. gaps() = span - width (:166-169) is too large by 2 * (len - 1) per copy: +4 for two copies of a two-word phrase, +8 for a three-word phrase (where the width is -2). It is never too small. The width is negative only when the copies are long enough: a three-position copy next to a one-position copy (equal sources such as an or of a phrase and a word can emit both) gives 0.
4. Who reads it. maxgaps directly, and any parent ordered/unordered/atLeast, which computes its own gaps as its span minus each child's width() (OrderedIntervalsSource.java:166-171, UnorderedIntervalsSource.java:158-161, MinimumShouldMatchIntervalsSource.java:235-237).
5. Matches disagrees. DuplicateMatchesIterator, the Matches side of the same class, adds endPosition - startPosition + 1 (:306-322), so Weight#matches keeps what the scorer drops.

"new york new york": ny matches [0, 1] and [2, 3]. ordered(ny, ny) is one repeating source with interval [0, 3], span 4. Correct width: (1 - 0 + 1) + (3 - 2 + 1) = 4, gaps 0. Computed width: (0 - 1 + 1) + (2 - 3 + 1) = 0, gaps 4. maxgaps(0) rejects the interval, so the document is not a hit.

Not affected: repeats of single words (start = end) and maxwidth (FilteredIntervalsSource.java:66-69, which uses end - start + 1). The scorer does not read this width either (IntervalScorer.java:65), but it sums its frequency over the intervals that survive the filter (IntervalScorer.java:60-68), so where intervals are dropped, a document that still matches through other intervals scores differently. Without a gaps consumer the hits are unchanged; only the reported gaps and width are wrong.

• Who is exposed. Users of the intervals API (lucene/queries, opt-in, marked experimental) and of the flexible query parser's interval functions, when ordered repeats a piece wider than one position back to back (it merges only consecutive equal sub-sources, so ordered(ny, nj, ny) is not affected), or unordered repeats it anywhere, under maxgaps, directly or above a parent that contains it. Downstream servers that expose interval queries with a max-gaps option were not run.
• Shapes that reach it (all executed). The same phrase twice; a repeated nested ordered/unordered (repeated inside ordered only since 10.1.0, when #13819 stopped flattening nested sources); Intervals.analyzedText with maxGaps > 0 or unordered on text whose repeated word follows a stop-word hole ("rock and roll and roll" becomes rock, extend(roll, 1, 0), extend(roll, 1, 0)) or with a repeated multi-word synonym ("ny ny" with ny => new york); and the query string fn:maxgaps(0 fn:ordered("new york" "new york")).
• What goes wrong. Gaps are only ever too large, so the built-in maxgaps, directly or above a parent, only rejects intervals it should keep: every positive query run lost hits (custom filters and deeper compositions were not analysed). A negation over such a query keeps documents it should drop (executed for a MUST_NOT clause and notContainedBy; other negating operators were not run). Weight#matches, which the highlighters use, disagrees with the hit list (neither highlighter was run end to end). Scores are not computed from the bad width but change where intervals are dropped. Code that reads gaps()/width() sees wrong values even without maxgaps.
• How big. The error is fixed: +4 for two copies of a two-word phrase. So for the non-overlapping "new york" copies run here, maxgaps(0) to maxgaps(3) never match; maxgaps(5) still catches true gaps 0-1 and misses 2-5, so spot checks can pass. Copies that overlap (not run) would have a shorter span.
• Silent, default settings. No exception. A plain main() with IndexWriterConfig on StandardAnalyzer (the no-argument default), the default codec, a ByteBuffersDirectory and a plain IndexSearcher misses the document, with assertions on and off; the JUnit runs with the test framework's randomized codec, similarity and locale miss it too. One document is enough; nothing is written to the index.
• How likely. Rare: it needs a repeated multi-position piece plus maxgaps, and no report was found in the recorded searches although the code has shipped for about six and a half years; but for such a query the affected documents are missed every time.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: f:MAXGAPS/0(UNORDERED(BLOCK(new,york),BLOCK(new,york))) on 'new york new york' 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.TestRepeatedPhraseMaxGaps.testMaxGapsZeroOverRepeatedPhrase(TestRepeatedPhraseMaxGaps.java:28)

• The class javadoc. "The generated 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); a width is end() - start() + 1 (IntervalIterator.java:73-76).
• The gaps contract. gaps() counts "the gaps between the immediate sub-intervals of this interval" (IntervalIterator.java:62-71); two back-to-back copies have none.
• The twin uses the right sign. DuplicateMatchesIterator (:306-322), added in the same commit, sums endPosition - startPosition + 1; IntervalMatchesIterator#gaps()/width() refer to the IntervalIterator definitions, and Weight#matches must return null "if the document does not match the parent query" (Weight.java:67-69).
• The introducing commit's own goals. LUCENE-9099: "RepeatingIntervalsSource instead returns the sum of the widths of its child iterators. This preserves maxgaps filtering on ordered and unordered sources that contain repeats", and checks were added "to ensure that the same intervals are returned by both iterator and matches". The bug breaks both.
• An internal optimization decides. maxgaps(0, ordered(ny, maxwidth(2, ny))), whose copies are not equal and so not merged, matches (executed).
• Nothing pins the current value. Every upstream repeat test repeats single words, and checkIntervals compares iterator and Matches on start and end only; all 117 upstream intervals tests pass with the fix.

The strongest case for "works as designed" (rated weak by the devil's advocate and by the reviews from another model family): the package "contains experimental classes" (package-info.java:21), the class is package-private, its javadoc says it "is useful for repeated terms within an unordered interval" (RepeatingIntervalsSource.java:34-36), and LUCENE-9099's examples and every repeat test use single words. On that reading, repeating multi-word pieces was outside the design, and the width is an internal detail.

Why it fails: "experimental" covers API stability, not wrong results. The public ordered/unordered factories merge any equal sub-sources without a word about terms, analyzedText and the query parser build multi-position repeats from plain text, and the same commit wrote the correct formula for the Matches side. The class promises a sum of widths, and a negative width has no meaning. The fix changes nothing for single-word repeats.

The fix is one line: the iterator's width() gets the formula of IntervalIterator#width() and of the Matches twin, so iterator and Matches agree again and gaps() counts only the positions between the copies. Summing each copy's own width() instead (cached next to the endpoints, which start() and end() still need) would count the inner gaps of a repeated nested repeat, against the gaps() contract and the Matches twin. Merging only single-position sources would bring back what LUCENE-9099 fixed: unmerged equal copies can match the same occurrence. Until a fix ships, an ordered query can make its copies unequal with a no-op filter (ordered(ny, maxwidth(2, ny))); there is no such workaround for unordered.

In RepeatingIntervalsSource.DuplicateIntervalIterator.width() (line 161), add end - start + 1 per copy instead of start - end + 1 (+1/-1 in one file). Add a regression test that repeats a multi-position source; no upstream test does. A 12-line test for TestIntervals (after testMaxGapsWithOnlyRepeats) reuses that suite's fixture: maxgaps(1, ordered(phrase(pease, porridge), phrase(pease, porridge))) and the unordered twin must give intervals [0, 4] and [3, 7] with gaps 1 in documents 1, 2 and 4.

       int width = 0;
       for (int i = 0; i < cacheLength; i++) {
         int pos = (cacheBase + i) % cacheLength;
-        width += cache[pos * 2] - cache[pos * 2 + 1] + 1;
+        width += cache[pos * 2 + 1] - cache[pos * 2] + 1;
       }
       return width;
     }

Trade-offs

• Same arithmetic, no cost.
• Results change only for repeated multi-position sources, where they were wrong: gaps only go down, so with the built-in maxgaps the positive queries run here gain their missing hits and the negations run here exclude more (custom filters and deeper compositions were not analysed), and the scores of documents whose intervals were dropped change. Single-word repeats give the same value as before.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: stock + the new test, 6 of 7 fail with assertions on and off; stock + the TestIntervals test, it fails ("wrong number of endpoints in doc 1 expected:<4> but was:<0>") and the other 43 TestIntervals tests pass.
• + the fix: the whole lucene/queries module, 52 suites, 520 tests (125 in the intervals package, 8 of them new), 0 failures with assertions on and off (5 and 6 tests skipped); :lucene:queries:check -x test (checkGoogleJavaFormat, ecjLint, forbiddenApis) passes.
• Standalone runner: 7 of 7 with assertions on and off.
• Earlier: the finder's, the reproducer's and a reviewer's tests, the devil's advocate's probe, an 8-test reach probe and the portable history probe (on 8.5.0 and main) all pass with the same change.

Cache in.width() per copy as well as its start and end (the composite start() and end() still need the cached endpoints after the single delegated iterator moves on), and sum those. Not built.

Trade-offs

A literal reading of the class javadoc ("sums up the widths of the individual sub-iterators") supports it; it costs one more cached value and one width() call per copy. Identical for phrases and words. It differs when the repeated piece itself reports a summed width (a repeated nested repeat): it would then count the inner gaps in the parent's gaps, against IntervalIterator#gaps() ("does not include the gaps inside those sub-intervals") and against the Matches twin, which uses the span, so the Matches side would need the same decision.

Leave phrases and other multi-position pieces unmerged. Not built.

Trade-offs

Brings back what LUCENE-9099 fixed ("UNORDERED(a, a) will match on documents that just containg a single a"): unordered(ny, maxwidth(2, ny)), whose copies are not merged, matches the document "new york" alone (executed). It is also hard to build: IntervalsSource exposes only a minimum extent (minExtent()), so neither source equality nor the existing API tells whether every interval a sub-source emits is one position wide (an or of a word and a phrase emits both).

Make the copies unequal with a no-op filter: maxgaps(0, ordered(ny, maxwidth(2, ny))) finds "new york new york" and not "new york x new york" (executed).

Trade-offs

Not for unordered: unmerged copies can match the same occurrence, so maxgaps(0, unordered(ny, maxwidth(2, ny))) also matches "new york" alone and "new york x new york" (executed).

Method: code reading, then bounded-exhaustive translation validation on the stock main jars.

• The hunt unit on spans and intervals noticed that DuplicateIntervalIterator.width() and DuplicateMatchesIterator.width() in the same file subtract in opposite directions.
• Its harness (IvTV) ran the stock interval iterators against an independently written reference semantics (IvRef) on every document of up to 6 positions over {a, b, c} and up to 4 positions with stacked synonyms, for every one- and two-level expression over 24 interval operators: 1,401,702,324 checks.
• The check that the Matches API agrees with the iterator, gaps and width included, failed 59,751 times for ordered over a repeated source and 59,751 times for unordered; Matches was non-null where the iterator had no interval 7,653 times under maxgaps(0) and 8,301 times under maxgaps(1). These categories are 0 in a smaller re-run (287,753,697 checks) with all six fixes of that unit applied. The only gap/width disagreements without a repeated source were a separate tie-break between OR branches on stacked synonyms (47,642 and 2,020 checks), where both values are valid witnesses; it is not reported and stays with all fixes applied.
• The finder reduced it to a one-document public-API JUnit; independent AI tools then reproduced, reviewed and judged it (see the checks).