Intervals.overlapping, nonOverlapping and notWithin skip the disjunction rewrite, so a word can be both within and not within n positions of or(york, "new york")

Intervals queries can filter a source by a reference that is an or() of alternatives. The default Intervals.or() keeps only minimal intervals, so an alternative such as "new york" [1,2] is dropped when it contains another one, york [2,2]. Since LUCENE-8477 (8.1.0), containedBy and therefore within pull such a reference apart and test every alternative; overlapping, nonOverlapping and notWithin were built without that rewrite and read the minimized or(). For one and the same reference the relations then contradict each other: on "visit new york", within(visit, 1, or(york, "new york")) and notWithin(visit, 1, or(york, "new york")) both return visit; on "new york", containedBy(new, R) matches but overlapping(new, R) does not, nonOverlapping(new, R) keeps new, and maxgaps(0, overlapping(new, R)) matches again because the nested form does split the reference. The same happens from fn: query text. With or(false, ...) every relation agrees. Every release from 8.1.0 to 10.5.2, 10.6.0 (its intervals sources at 4ae946e5a9b) and main is affected; 8.0.0 is consistent. Rewriting the disjunctions in the three factories (for overlapping on both operands, as its nested form already does) fixes it and passes the queries and queryparser test suites.

• Interval: the positions a source matches, [start,end]. In "visit new york", york is [2,2] and the phrase "new york" is [1,2].
• Minimal intervals: the default Intervals.or() drops an interval that contains another interval of the same or(). So or(york, "new york") yields only york [2,2] on "visit new york".
• Disjunction rewrite (LUCENE-8477, 8.1.0): for operators where that loses matches, Lucene builds one copy of the operator per alternative and ORs the copies (Disjunctions.pullUp). Alternatives with minExtent() 1 are grouped into one or(); extend raises the extent, so within / notWithin with n >= 1 split even an or() of single words. or(false, ...) turns the rewrite off; the javadoc offers it for when you "care more about speed than about accuracy".
• The relations: within(x, n, r) = containedBy(x, extend(r, n, n)); notWithin(x, n, r) = nonOverlapping(x, extend(r, n, n)); overlapping(x, r) keeps x intervals that overlap an r interval.

// ContainedByIntervalsSource.java:28-30: the reference is split, one filter per alternative
return Intervals.or(Disjunctions.pullUp(big, s -> new ContainedByIntervalsSource(small, s)));

// Intervals.java:508-511
within(source, n, reference)    -> containedBy(source, Intervals.extend(reference, n, n))
// Intervals.java:493-497, 467-470, 478-480: plain constructors, the reference is read as one or()
notWithin(minuend, n, subtrahend) -> new NonOverlappingIntervalsSource(minuend, Intervals.extend(subtrahend, n, n))
nonOverlapping(minuend, subtrahend) -> new NonOverlappingIntervalsSource(minuend, subtrahend)
overlapping(source, reference)    -> new OverlappingIntervalsSource(source, reference)

// DisjunctionIntervalsSource.java:230-236: the or() iterator drops queued intervals that contain the current one
while (intervalQueue.size() > 0 && contains(intervalQueue.top(), start, end)) { ... pop ... }

// OverlappingIntervalsSource.java:78-83: the split exists, but only a parent (maxgaps, phrase, ...) calls it
public Collection<IntervalsSource> pullUpDisjunctions() {
  return Disjunctions.pullUp(Arrays.asList(source, reference), ss -> new OverlappingIntervalsSource(ss.get(0), ss.get(1)));
}

On "visit new york" with R = or(york, "new york"):

1. within(visit, 1, R) tests visit [0,0] against extend(york) = [1,3] and extend("new york") = [0,3]. The second contains it: 1 hit.
2. notWithin(visit, 1, R) reads extend(R) as one source. The minimized or() yields only york, widened to [1,3], which does not touch visit [0,0]: visit is kept, 1 hit.
3. On "new york", overlapping(new, R) compares new [0,0] with york [1,1] only: 0 hits, although new overlaps the alternative "new york" [0,1], which containedBy(new, R) finds. nonOverlapping(new, R) and notWithin(new, 0, R) keep new.
4. maxgaps(0, overlapping(new, R)) asks its source for its alternatives (FilteredIntervalsSource.java:31-36), which splits the reference: 1 hit. A filter that can only remove intervals adds one.
5. With or(false, ...) nothing is split anywhere, every relation sees york only, and they agree: within 0, notWithin 1, containedBy 0, overlapping 0.

The same holds without a single-word alternative: with or("new york", "new york city") on "new york city hall", within(hall, 1, ...) and notWithin(hall, 1, ...) both match, because "new york city" [0,2] contains "new york" [0,1] and is dropped for notWithin.

• Who. Callers of Intervals.overlapping, Intervals.nonOverlapping and Intervals.notWithin, and of fn:overlapping, fn:nonOverlapping and fn:notWithin in the flexible StandardQueryParser, whose reference is a default Intervals.or() with alternatives that contain one another: a word and a phrase that starts or ends with it (york / "new york"), or a phrase and a longer phrase ("new york" / "new york city"). Synonym or place-name lists can have this shape.
• Settings. Default IndexWriterConfig settings and codec and a plain IndexSearcher, with StandardAnalyzer or the test framework's MockAnalyzer; assertions on and off. Every run used one-document indexes; the mechanism works per document, so index size should not matter (reasoning, not run). The rewrite is on by default (Intervals.or(...) = or(true, ...)).
• Effect. Silent wrong match sets in both directions: overlapping misses documents (0 instead of 1 on "new york"); nonOverlapping and notWithin used as exclusion filters keep documents they should drop (1 instead of 0 on "visit new york" and on "new york city hall"). Adding an alternative to the reference removes overlapping hits and adds nonOverlapping / notWithin hits, and wrapping the filter in maxgaps or phrase adds hits back.
• Not affected. References with one alternative, or()s of single words (two different single-position intervals never contain one another, so the minimized or() drops nothing: 0 violations in 1,452 relation checks over all 363 documents of up to 5 words, executed), or(false, ...), and within / containedBy themselves.
• How likely. Rated rare: it needs one of these three filters, a reference whose alternatives contain one another, and text where only the longer alternative decides. No report was found since 8.1.0 (2019). For such a query and document the wrong answer comes every time. The intervals package is marked experimental.
• Workaround on stock Lucene. Spell the alternatives out with the public factories, the structure the fix builds: or(overlapping(x, york), overlapping(x, "new york")) (1 on "new york"), nonOverlapping(nonOverlapping(x, york), "new york") (0) and notWithin(notWithin(visit, 1, york), 1, "new york") (0 on "visit new york"), all executed on main. Or use or(false, ...) everywhere for consistent minimized answers.
• Downstream (code and documentation reading only, not executed). Elasticsearch's intervals query builds any_of with Intervals.or and its overlapping / not_overlapping filters with Intervals.overlapping / Intervals.nonOverlapping; Solr's intervals query parser exposes within, not_within, overlapping, not_overlapping and any_of.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: within=1, notWithin=1 expected:<1> but was:<2>
       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.TestWithinNotWithinDisjunction.testWithinAndNotWithinAreComplements(TestWithinNotWithinDisjunction.java:50)

• Documented as opposites. Intervals.java:500: within "Returns intervals of the source that appear within a set number of positions of intervals from the reference"; :485: notWithin "Returns intervals of the minuend that do not appear within a set number of positions of intervals from the subtrahend query". fn:notWithin: "Matches intervals of the source that do not appear within the provided number of positions from the intervals of the reference". LUCENE-8629 (#9675) proposed within and overlapping as the "inverse of the already available NOT_WITHIN" and "NOT_OVERLAPPING". The repro uses single-position sources, so the separate question of a partly-near multi-position interval (LFV-830) does not arise.
• Set logic. containedBy ("appear within intervals of the big query", :554) implies overlapping ("overlap with intervals from another source", :473; fn:overlapping: "overlap with at least one interval of the reference") and excludes nonOverlapping ("do not overlap with intervals from the subtrahend", :462).
• The default is the mode the javadoc presents as accurate. The class note, written about gap-sensitive sources ("e.g. PHRASE and MAXGAPS"), says the rewrite ensures documents "are matched" and "if you care more about speed than about accuracy you can use" or(false, ...) (:47-54); or(false, ...) "can miss valid hits due to minimization" (:131). LUCENE-8477's CHANGES entry: "Interval disjunctions could miss valid hits if some of the clauses of the disjunction are minimized away". Here the default is the inconsistent path. The note does not promise in so many words that every top-level relation expands its operands; a maintainer may read it that narrowly.
• The same filter answers differently under a parent. maxgaps(0, overlapping(new, R)) and phrase(overlapping(new, R), york) match "new york" although overlapping(new, R) alone has no interval there. maxgaps and phrase rewrite their child at construction, as documented for gap-sensitive sources, so the difference itself is expected from the design; what it shows is that the module's own expansion finds a hit that the top-level filter misses.
• Maintainers on the rewrite (#10244): romseygeek, "Intervals automatically rewrite disjunctions (and have done since LUCENE-8477) so that queries behave as your or I would expect them to"; jimczi, "If it's not correct, it's a bug, not a feature".
• Tests. No upstream test uses these filters with a reference whose alternatives contain one another: TestDisjunctionRewrites has no case for them, and the other uses (in TestIntervals, TestIntervalQuery, the match-highlighter tests and TestStandardQPEnhancements) have a single word, a phrase, an ordered / unordered pair, an extend, or an or() of single words (single words never contain one another, so minimization drops nothing there).

Intervals use minimal-interval semantics ("These sources implement minimum-interval algorithms", Intervals.java:43), under which or(york, "new york") is york. The rewrite is documented for gap-sensitive sources ("e.g. PHRASE and MAXGAPS"); LUCENE-8477's commit message lists PHRASE, MAXGAPS and the four containment filters, not the overlap filters. In its review jimczi wrote "I am not sure if the rewriting should be the default option since minimum interval semantic is the basis of the paper", and earlier in #9523 "IMO we should document this unintuitive behavior rather than rewriting all queries in a non-optimal form". The fn: docs say "the algorithm is not required to return or highlight all matching interval alternatives", and the package is experimental. Two narrower readings follow: the nested-versus-top-level overlapping difference is the documented construction-time rewrite of gap-sensitive parents at work, and standalone overlapping / nonOverlapping are complementary over the minimized reference.

Why it fails: that explains overlapping or nonOverlapping taken alone, not the contradiction. within itself uses the non-minimized alternatives, so under either reading one of within and notWithin is wrong, and with or(false, ...) everything agrees, so the inconsistency lives only on the default path. romseygeek answered jimczi in the same thread ("I think we still need to make it possible to get accurate hits", "My suggestion is that we automatically rewrite things to match accurately"), and the rewrite was committed that way; #10244 later defends it. The fn: caveat is about which intervals a matching document returns or highlights; this bug changes which documents match, and notWithin returns an extra interval rather than missing one. The earlier cross-model reviews rated the argument moderate and rejected it, and the intended-behaviour checker built it and rejected it. The cross-model fact check (reading only) rated the intended reading weak for within / notWithin and strong for the two narrower cases taken alone. A maintainer could still choose either consistent fix (rewrite the overlap filters, or minimize in within / containedBy too, which would undo LUCENE-8477), which is why the adjudication's confidence is medium.

Option A2 is recommended: validated with gradle on a9779ef3c193 (tests with assertions on, static checks) and with the repro runner (assertions off). The finder's sketch, option A, passes the same tests but loses a nested match that stock Lucene finds, which a cross-model fact check found and a later run confirmed. Options B and C were not run.

In Intervals.java (+20/-4): overlapping is built exactly as its nested form already is (OverlappingIntervalsSource.pullUpDisjunctions): one OverlappingIntervalsSource per combination of a source alternative and a reference alternative, ORed. So top-level and nested overlapping agree on both operands. nonOverlapping and notWithin become a chain of one NonOverlappingIntervalsSource per reference alternative ("overlaps no alternative"), the AND that the LFV-291 fix also uses for notContainedBy. A reference with nothing to split gives one filter, as before, and or(false, ...) is never split. The guard test (1 test, public API) passes on stock main and with A2 and fails with option A.

   public static IntervalsSource nonOverlapping(
       IntervalsSource minuend, IntervalsSource subtrahend) {
-    return new NonOverlappingIntervalsSource(minuend, subtrahend);
+    return nonOverlappingAll(minuend, subtrahend);
+  }
+
+  // A minuend interval must overlap no alternative of a disjunctive subtrahend. Like
+  // containedBy/containing (LUCENE-8477), look at every alternative instead of the minimized
+  // disjunction, and combine the exclusions as a conjunction.
+  private static IntervalsSource nonOverlappingAll(
+      IntervalsSource minuend, IntervalsSource subtrahend) {
+    IntervalsSource result = minuend;
+    for (IntervalsSource s : Disjunctions.pullUp(subtrahend, s -> s)) {
+      result = new NonOverlappingIntervalsSource(result, s);
+    }
+    return result;
   }
 ...
   public static IntervalsSource overlapping(IntervalsSource source, IntervalsSource reference) {
-    return new OverlappingIntervalsSource(source, reference);
+    // overlap with any alternative of a disjunctive source or reference, as the nested form
+    // (OverlappingIntervalsSource.pullUpDisjunctions) already does
+    return Intervals.or(
+        Disjunctions.pullUp(
+            Arrays.asList(source, reference),
+            ss -> new OverlappingIntervalsSource(ss.get(0), ss.get(1))));
   }
 ...
   public static IntervalsSource notWithin(
       IntervalsSource minuend, int positions, IntervalsSource subtrahend) {
-    return new NonOverlappingIntervalsSource(
-        minuend, Intervals.extend(subtrahend, positions, positions));
+    return nonOverlappingAll(minuend, Intervals.extend(subtrahend, positions, positions));
   }

Trade-offs

• Like every LUCENE-8477 rewrite it trades speed for accuracy (not benchmarked): overlapping builds one filter per combination of source and reference alternatives, each with its own iterators; the nonOverlapping / notWithin chain builds the minuend iterator once, plus one iterator per reference alternative.
• Expansion limit: A2's overlapping uses the list pull-up, which throws IllegalArgumentException("Too many disjunctions to expand") above IndexSearcher.getMaxClauseCount() combinations, as the nested form and phrase already do. Top-level overlapping over an or() of 1,025 phrases now throws where stock main builds it (executed; maxgaps(0, ...) of it throws on stock main too). The chain uses the single-source pull-up, which has no limit, like containedBy and notContainedBy today.
• The chain's order is a hash set's iteration order, so toString, equals and hashCode of the chain depend on it, though results do not (NON_OVERLAPPING(NON_OVERLAPPING(xx,EXTEND(bb,1,1)),EXTEND(aa,1,1)), executed); a PR could sort the alternatives (reasoning, not run).
• It changes results for existing queries (that is the fix): top-level overlapping with a disjunctive source or reference, nonOverlapping / notWithin with a disjunctive reference. The source side of nonOverlapping / notWithin needs no split at the document level: if a longer source interval overlaps nothing, the shorter one inside it overlaps nothing either (reasoning, not run).

What the checks validated

• Gradle on a9779ef3c193 in a scratch worktree, seed DEADBEEF, assertions on: the finder's 4 tests, the nested-filter probe and the 2 query-text tests pass, and so do the whole :lucene:queries (517 tests in 53 classes) and :lucene:queryparser (535 tests in 31 classes) test tasks and the 48 match-highlighter tests: 1,100 tests, 0 failures (1,093 upstream).
• Gradle static checks of :lucene:queries with A2 and the guard test: checkGoogleJavaFormat, forbiddenApisMain, forbiddenApisTest, ecjLintMain and ecjLintTest pass, and the guard test passes.
• The repro runner, assertions off: the 4 + 2 repro tests, 117 upstream interval tests and 23 upstream query-parser tests pass. The guard test passes with assertions on and off.
• The probe with A2: every count in this doc consistent; the source-side case (overlapping(or(new, "new york"), york) on "new york") is 1 at top level and 1 nested.
• Bounded differential (10 x 10 operand pairs, 120 documents, top level and under maxgaps(0, ...), maxgaps(1, ...) and phrase(..., cc)): A2 leaves all 300 nested overlapping expressions as on stock main, while option A loses documents in 15 of them.

In Intervals.java (+17/-4): the same nonOverlapping / notWithin chain as A2, but overlapping = Intervals.or(Disjunctions.pullUp(reference, r -> new OverlappingIntervalsSource(source, r))), so only the reference is split. That loses a nested match that stock Lucene finds: maxgaps(0, overlapping(or(new, "new york"), or(york, "zzz qqq"))) on "new york" is 1 on stock main and with A2, but 0 with A, because the parent now maps over A's outer or() and no longer splits the source (executed, assertions on and off). In the bounded differential, A loses documents in 15 of the 300 nested overlapping expressions. It also leaves the source side of top-level overlapping alone.

   public static IntervalsSource overlapping(IntervalsSource source, IntervalsSource reference) {
-    return new OverlappingIntervalsSource(source, reference);
+    // overlap with any alternative of a disjunctive reference, as containedBy does
+    return Intervals.or(
+        Disjunctions.pullUp(reference, r -> new OverlappingIntervalsSource(source, r)));
   }
 (nonOverlapping and notWithin: as in A2)

Trade-offs

Smaller than A2, but it regresses the nested case above, which none of the 1,100 tests covers (the guard test fails with A). It moves the clause limit: maxgaps(0, overlapping(new, or(1,025 phrases))) builds with A, where stock main throws (executed).

What the checks validated

• Gradle on a9779ef3c193 in a scratch worktree, seed DEADBEEF: the finder's 4 tests, the nested-filter probe and the 2 query-text tests pass, and so do the whole :lucene:queries (517 tests in 53 classes) and :lucene:queryparser (535 tests in 31 classes) test tasks and the 48 match-highlighter tests: 1,100 tests, 0 failures (1,093 upstream).
• Assertions off: the intervals tests (122 in 9 classes) and the flexible standard query-parser tests (127 in 8 classes) pass.
• Static checks of :lucene:queries with A: forbiddenApisMain and ecjLintMain pass; checkGoogleJavaFormat does not flag Intervals.java (only line wraps in the copied test files, now applied to the repro test, which still fails 4 of 4 on main and passes with A).
• Earlier, with the standalone runner: the finder's, the independent reproducer's and both reviewers' own tests pass; in the law-checking harness the within / notWithin "both" class and the inclusion-law failures disappear.

Make every relation read the minimized or(), as in 8.0.0.

Trade-offs

Consistent, but it undoes LUCENE-8477 for the containment filters and brings back the missed containedBy hits that LUCENE-8477 fixed. Not run.

State that the overlap filters read a disjunctive reference as minimized.

Trade-offs

Leaves within and notWithin both matching, and the same filter answering differently at top level and when nested.

Method: reference-free law checking (translation validation) of the real jar, the hunt's semi-formal tier: no model checker, solver or prover produced the signal.

• The harness ran real interval sources on an index of all 1,364 documents of up to 5 positions over a 4-letter alphabet and checked laws that need no reference semantics: each minimal interval of X is returned by exactly one of a relation and its negation; containedBy(X, Y) is a subset of overlapping(X, Y); or() is commutative and idempotent.
• Bounded-exhaustive over a 116-shape pool (116 x 116 pairs), plus 30,000 random depth-3 pairs per random leg, with the known interval fixes shadowed (the LFV-287 and LFV-291 sketches and seven earlier switches), so only new violation classes remained.
• The residual class "within and notWithin both return an alternative's interval" and the inclusion-law failures were reduced by hand to the public-API JUnit; with the fix added, both classes disappear from every leg.
• An earlier unit of the hunt had noted the nonOverlapping half alone and judged it a design question; the complement and inclusion laws turn it into a contradiction between documented relations.