Intervals.within and notWithin are documented as opposites, but a phrase only partly inside the window matches neither

Intervals.within(source, n, reference) and Intervals.notWithin(source, n, reference) are documented as opposites: one returns source intervals that "appear within a set number of positions" of the reference, the other those that "do not appear within" it, and the fn:within / fn:notWithin query-parser docs give both the same "maximum positions" parameter. Both widen each reference interval by n positions on both sides, but within keeps a source interval only if it lies entirely inside that window (containedBy), while notWithin drops it if it touches the window at all (non-overlap).

A single term cannot touch the window without lying inside it, so it never falls in this gap (against a single-term reference the pair splits it exactly; with a nested disjunctive reference the hunt's separate LFV-828 can make it match both). For a phrase or near query, an interval that overlaps the window without lying inside it fails both: on "the new york times", within(phrase(new, york), 1, times) and notWithin(...) both count 0, and within needs n = 2. The code has done this since within was added in 8.0.0 and looks deliberate, so this is a documentation / API-contract defect: the proposed fix states the two relations and the gap in the javadoc and the fn: docs, with a one-line behaviour change only as an option.

1. Both factories widen the reference the same way. within returns containedBy(source, Intervals.extend(reference, positions, positions)) (Intervals.java:508-511); notWithin returns new NonOverlappingIntervalsSource(minuend, Intervals.extend(subtrahend, positions, positions)) (Intervals.java:493-497). extend moves each reference interval's start back by n (clamped at 0, ExtendedIntervalIterator.java:61) and its end forward by n. For "times" at position 3 and n = 1 the window is 2-4.
2. within tests whole containment. ContainedByIntervalsSource returns a source interval a only when the window b it finds has b.end() >= a.end() (ContainedByIntervalsSource.java:53) and b.start() <= a.start() (:59). "new york" is 1-2 and the window starts at 2, so it is dropped.
3. notWithin tests no contact. NonOverlappingIterator returns a only when the next window with b.end() >= a.start() (NonOverlappingIntervalsSource.java:72) has b.start() > a.end() (:78). The window starts at 2 and "new york" ends at 2, so it is dropped too.
4. Partly inside means neither. A single position is either inside a window or apart from it, so a single-term source never falls in this gap; against "times" the pair splits it exactly (executed: the, new, york and times, n = 0 to 3, within + notWithin = 1 every time). Over the same window of a single-term reference, overlapping / nonOverlapping and containedBy / notContainedBy are each exact complements; on the repro document overlapping = 1, nonOverlapping = 0, containedBy = 0, notContainedBy = 1. Only the mixed pair that within / notWithin use leaves a gap. With a disjunctive reference, separate defects change this: with nesting alternatives (LFV-828) notWithin reads fewer reference intervals than within, so a single term can match both (executed: on "visit new york", within(visit, 1, or(york, phrase(new, york))) = 1 and notWithin(...) = 1), and for some or() references LFV-291 breaks containedBy / notContainedBy.

• A source that straddles the window edge, as above: a phrase directly before or after the reference at n = 1. within(phrase(new, york), 2, times) = 1, so within needs n = 2 where the documented single-term examples use n = 1 for a term right next to the reference ("dog" after "lazy", intervalfn/package-info.java:533-535).
• A source that contains the reference and sticks out more than n positions past it. On "new york", within(phrase(new, york), 0, york) and notWithin(phrase(new, york), 0, york) both count 0, and MUST(phrase) MUST_NOT(within(...)) counts 1 while notWithin counts 0, so two common ways of writing "X but not near Y" disagree. A containing source that sticks out by at most n is within (within(phrase(new york), 0, phrase(new york)) = 1). So, for one occurrence of the reference, a source that contains it falls in the gap exactly when it starts more than n positions before the reference interval or ends more than n positions after it; any source wider than 2n + 1 around a single-position reference is one such case.

fn:within and fn:notWithin call the same factories (Within.java:38, NotWithin.java:38). On the docs' own example sentence, "The quick brown fox jumps over the lazy dog", fn:within(fn:phrase(brown fox) 1 jumps) and fn:notWithin(fn:phrase(brown fox) 1 jumps) both count 0; at n = 0 only fn:notWithin matches and at n = 2 only fn:within.

• Who. Callers of Intervals.within / Intervals.notWithin with IntervalQuery, and users of fn:within / fn:notWithin in the flexible StandardQueryParser (since 9.1.0), who pass a multi-position source: a phrase, or an ordered or unordered near. A single-term source never falls in this gap; the upstream tests use single-term sources and the fn: doc examples a disjunction of single terms, so none has a multi-position source.
• Downstream. The Solr 10.1 intervals query parser exposes within / not_within with the same opposite-pair wording; the Elasticsearch and OpenSearch intervals queries do not offer these two filters.
• Default vs opt-in. Default analyzer, codec and searcher; the relation is decided per source interval inside one document, so index size plays no part (the repro uses one document). The intervals package is opt-in (the queries module) and labelled "experimental classes" (intervals/package-info.java:21).
• What goes wrong. Fewer hits than the docs describe; splitting a source's matches into "near Y" and "not near Y" silently loses the partly-near ones; an exclusion written two common ways returns different documents. No error, deterministic, nothing written to the index.
• Age and likelihood. The gap is present from 8.0.0 (2019) through 10.6.0 and on main; the recorded searches found no public report, which suggests that accidental hits are rare (a judgement, not measured).
• Scope of the evidence. The repro uses a single-term reference with one occurrence; disjunctive, nested or repeated references are not part of this claim (for nesting or() alternatives see the separate LFV-828).

• Seed-independent. One fixed document and fixed queries, a plain IndexSearcher, the default codec pinned, so the result does not depend on the seed: the test framework still randomizes locale, time zone and similarity, and the tie-break's seeds 7EB4EA11 and 0DA0DA01 give the same failure as DEADBEEF. Assertions on and off fail the same way.
• It transcribes the complement reading of the docs. No Java API text promises that complement in so many words, so the test demonstrates the documentation ambiguity, not a code defect. Under the recommended javadoc fix it becomes obsolete, because the documented contract becomes "a partly-near interval matches neither". A test is unusual for a javadoc-only change; if upstream wants one, keep this same test as a characterization test with the expectation the clarified docs give, assertEquals("within + notWithin", 0, within + notWithin), and the comment "new york [1,2] overlaps the widened times [2,4] but is not inside it, so it matches neither". It passes with the javadoc fix, with assertions on and off. Under the behaviour change (option B) the test as written passes unchanged.
• Releases. The same file fails unchanged on the 9.1.0, 9.12.3, 10.0.0, 10.5.2 and 10.6.0 release jars; with only the package line and the test-framework imports adapted it fails on 8.0.0, 8.1.1, 8.2.0, 8.11.4 and 9.0.0. 7.7.3 has no within.

cp $REPRO/TestWithinNotWithinPartlyNear.java $LUCENE/lucene/queries/src/test/org/apache/lucene/queries/intervals/
cd $LUCENE
./gradlew :lucene:queries:test --tests org.apache.lucene.queries.intervals.TestWithinNotWithinPartlyNear -Ptests.seed=DEADBEEF -Ptests.asserts=true
# assertions off: -Ptests.asserts=false (same failure)

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.asserts=true
TestWithinNotWithinPartlyNear > testPhraseNextToReferenceIsWithinOrNotWithin FAILED
    java.lang.AssertionError: within + notWithin expected:<1> but was:<0>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:3A90972F4189603B]:0)
        at junit@4.13.2/org.junit.Assert.fail(Assert.java:89)
        at junit@4.13.2/org.junit.Assert.failNotEquals(Assert.java:835)
        at junit@4.13.2/org.junit.Assert.assertEquals(Assert.java:647)
        at org.apache.lucene.queries.intervals.TestWithinNotWithinPartlyNear.testPhraseNextToReferenceIsWithinOrNotWithin(TestWithinNotWithinPartlyNear.java:48)
:lucene:queries:test (FAILURE): 1 test, 1  failure
# -Ptests.asserts=false: the same failure
# documentation fix (option A): changes no code; the same test expecting 0 passes
# behaviour change (option B): BUILD SUCCESSFUL, 1 test

• The summaries use the file's own complement vocabulary. In Intervals.java, "appear within" / "do not appear within" describe containedBy (:554) and notContainedBy (:541-542), an exact complement pair for a non-disjunctive reference (the separate LFV-291 breaks it for some or() references); within and notWithin use the same words (:500-501, :485-486), and so does the package overview (intervals/package-info.java:68-70).
• The query-parser docs differ only by an emphasized not. fn:within: "Matches intervals of the source that appear within the provided number of positions from the intervals of the reference"; fn:notWithin: the same with "do <em>not</em> appear within" (intervalfn/package-info.java:515-516, :544-545). Both take "an integer number of maximum positions between source and reference" (:526, :555), and the source is a "term or other function" (:524, :553), so a phrase is a documented input.
• Intent at introduction. #9675 / LUCENE-8629 lists "a WITHIN b - inverse of the already available NOT_WITHIN" and, in the same list, "a OVERLAPPING b - inverse of the already available NOT_OVERLAPPING" (as @romseygeek wrote there). Over a non-disjunctive reference, overlapping and nonOverlapping are exact complements.
• Nothing documents the gap. No javadoc, overview, fn: doc, CHANGES entry or test says that within needs the whole source inside the widened window, that notWithin rejects any contact, or that a partly-near interval matches neither. The upstream tests use single-term sources only (TestIntervals.java:915-922, TestIntervalQuery.java:182-186), and the fn: doc examples a disjunction of single terms (fn:or(fox dog), intervalfn/package-info.java:533-538), so every exercised source is single-position.
• The parameter text is ambiguous for a phrase. By the docs' single-term convention ("dog" right after "lazy" matches at 1), "brown fox" right before "jumps" would match at 1; it needs 2. That follows only if the distance is measured to the farthest position of the source, which no doc says.

Strongest case for "intended" (the study's devil's advocate and a cross-model reviewer, OpenAI GPT-5.6): read pointwise, the Java @param texts describe the code: within's "the maximum distance that intervals of the source may occur from intervals of the reference" (Intervals.java:504-505) means every position at most n away, i.e. containment; notWithin's "the minimum distance ..." (:489-490) is a bound on every position, i.e. no contact (the code keeps a position only if it is more than n away). LUCENE-8629 changed notWithin's @param from "maximum" to "minimum" in the same commit that added within. notWithin equals SpanNotQuery(include, exclude, n, n) (executed, n = 0 to 3). The package is experimental, the tests are single-term, and the recorded searches found no complaint since 2019. The reviewer: "within and notWithin are deliberately different endpoint-distance filters, not Boolean negations."

Why it fails: it shows that the code is intended, which is why this is classed as documentation and not as wrong results; it does not show that the documentation describes the behaviour. The gap follows from one reading of the Java @params only, and even under that reading the notWithin text is off by one: "dog" right after "lazy" is 1 position away, yet fn:notWithin(dog 1 fn:or(quick lazy)) drops it (executed in the tie-break; the fn:notWithin doc example shows the same), so the smallest distance notWithin keeps is n + 1, not the stated minimum n. The fn: docs, which document the query-string route, have no maximum / minimum distinction. Before LUCENE-8629, notWithin's @param said "the maximum distance" (LUCENE-8196, 2018); read literally, that describes what within keeps, not what notWithin keeps. The reviewer itself wrote that the parser docs' "symmetric 'maximum positions' wording could reasonably be clarified to state whole containment for within, no contact for notWithin, and that partial intersections match neither": that clarification is the proposed fix. Confidence: high on the behaviour and the documentation gap, medium on how upstream will want to resolve it (a javadoc clarification is the most likely outcome).

Two options; both were applied in a scratch worktree of main 645d4fe14a20 and run with gradle. The documentation fix is the proposal, because the code looks deliberate and has behaved this way since 8.0.0.

In the javadoc of Intervals.within / notWithin and in the fn:within / fn:notWithin docs, say that the reference is widened by n positions on both sides, that within needs the whole source interval inside, that notWithin needs no overlap, and that an interval only partly inside matches neither. Replace the "distance" / "maximum positions between" parameter text.

diff --git a/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java b/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java
index f79d8bf0e10..33fe265df05 100644
--- a/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java
+++ b/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java
@@ -485,9 +485,15 @@ public final class Intervals {
    * <p>Returns intervals of the minuend that do not appear within a set number of positions of
    * intervals from the subtrahend query
    *
+   * <p>Each subtrahend interval is widened by {@code positions} on both sides, and a minuend
+   * interval is returned only if it does not overlap any widened interval. A minuend interval that
+   * overlaps a widened interval but lies entirely inside none of them, for example a two-term
+   * phrase directly before the subtrahend when {@code positions} is 1, is returned neither by this
+   * source nor by {@link #within(IntervalsSource, int, IntervalsSource)}.
+   *
    * @param minuend the {@link IntervalsSource} to filter
-   * @param positions the minimum distance that intervals from the minuend may occur from intervals
-   *     of the subtrahend
+   * @param positions the number of positions by which each subtrahend interval is widened on both
+   *     sides
    * @param subtrahend the {@link IntervalsSource} to filter by
    */
   public static IntervalsSource notWithin(
@@ -500,9 +506,15 @@ public final class Intervals {
    * Returns intervals of the source that appear within a set number of positions of intervals from
    * the reference
    *
+   * <p>Each reference interval is widened by {@code positions} on both sides, and a source interval
+   * is returned only if it lies entirely inside a widened interval. A source interval that overlaps
+   * a widened interval but lies entirely inside none of them, for example a two-term phrase
+   * directly before the reference when {@code positions} is 1, is returned neither by this source
+   * nor by {@link #notWithin(IntervalsSource, int, IntervalsSource)}.
+   *
    * @param source the {@link IntervalsSource} to filter
-   * @param positions the maximum distance that intervals of the source may occur from intervals of
-   *     the reference
+   * @param positions the number of positions by which each reference interval is widened on both
+   *     sides
    * @param reference the {@link IntervalsSource} to filter by
    */
   public static IntervalsSource within(
diff --git a/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/nodes/intervalfn/package-info.java b/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/nodes/intervalfn/package-info.java
index e8abe61644b..038cc1c3d34 100644
--- a/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/nodes/intervalfn/package-info.java
+++ b/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/nodes/intervalfn/package-info.java
@@ -513,7 +513,10 @@
  * <h3>fn:within</h3>
  *
  * <p>Matches intervals of the source that appear within the provided number of positions from the
- * intervals of the reference.
+ * intervals of the reference. Each reference interval is widened by that number of positions on
+ * both sides, and a source interval matches only if it lies entirely inside a widened interval. A
+ * source interval that only partly overlaps a widened interval (with 1 position, the phrase "brown
+ * fox" directly before "jumps") matches neither fn:within nor fn:notWithin.
  *
  * <dl class="dl-horizontal narrow">
  *   <dt>Arguments
@@ -523,7 +526,8 @@
  *         <dt><code>source</code>
  *         <dd>source sub-interval (term or other function)
  *         <dt><code>positions</code>
- *         <dd>an integer number of maximum positions between source and reference
+ *         <dd>an integer number of positions by which each reference interval is widened on both
+ *             sides
  *         <dt><code>reference</code>
  *         <dd>reference sub-interval (term or other function)
  *       </dl>
@@ -542,7 +546,9 @@
  * <h3>fn:notWithin</h3>
  *
  * <p>Matches intervals of the source that do <em>not</em> appear within the provided number of
- * positions from the intervals of the reference.
+ * positions from the intervals of the reference. Each reference interval is widened by that number
+ * of positions on both sides, and a source interval matches only if it does not overlap any widened
+ * interval (see <code>fn:within</code> for a source that only partly overlaps one).
  *
  * <dl class="dl-horizontal narrow">
  *   <dt>Arguments
@@ -552,7 +558,8 @@
  *         <dt><code>source</code>
  *         <dd>source sub-interval (term or other function)
  *         <dt><code>positions</code>
- *         <dd>an integer number of maximum positions between source and reference
+ *         <dd>an integer number of positions by which each reference interval is widened on both
+ *             sides
  *         <dt><code>reference</code>
  *         <dd>reference sub-interval (term or other function)
  *       </dl>

Trade-offs

• No behaviour change, so no existing query moves.
• It replaces parameter wording that is ambiguous for a phrase source with what the code does, and states the partly-near case once per function.
• Optional, not run: a sentence in the intervals package overview (intervals/package-info.java:68-70) and a CHANGES entry.
• Limits of the wording: the examples assume one occurrence of the reference (a second occurrence whose widened window contains the phrase would make within return it), and with a disjunctive reference whose alternatives nest the separate LFV-828 currently makes notWithin read fewer reference intervals than within, so "does not overlap any widened interval" does not hold there today.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF: :lucene:queries:checkGoogleJavaFormat, :lucene:queryparser:checkGoogleJavaFormat, :lucene:queries:renderJavadoc and :lucene:queryparser:renderJavadoc pass, and the rendered Intervals.html and intervalfn/package-summary.html show the new text.
• The intervals suite (org.apache.lucene.queries.intervals.*: the 117 upstream tests plus the minimal test in its documented form, expecting 0) passes, 118 tests, and the flexible-parser suite (org.apache.lucene.queryparser.flexible.standard.*) passes, 125 tests with 1 skipped as on stock main, assertions on; the documented-form test also passes with assertions off.
• The minimal test as written was not re-run with it: the fix changes only comments, so it keeps failing as on stock main.

One line: within tests overlap with the widened reference instead of containment, so within and notWithin become overlapping / nonOverlapping over the same window, an exact complement pair for a non-disjunctive reference.

diff --git a/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java b/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java
index f79d8bf0e10..f186518343a 100644
--- a/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java
+++ b/lucene/queries/src/java/org/apache/lucene/queries/intervals/Intervals.java
@@ -507,7 +507,7 @@ public final class Intervals {
    */
   public static IntervalsSource within(
       IntervalsSource source, int positions, IntervalsSource reference) {
-    return containedBy(source, Intervals.extend(reference, positions, positions));
+    return overlapping(source, Intervals.extend(reference, positions, positions));
   }
 
   /**

Trade-offs

• Changes results for every existing within query with a multi-position source: within(phrase(brown fox), 1, jumps) goes from 0 to 1, and a source that merely touches the window counts as within. It needs a CHANGES entry as a behaviour change, probably on main only.
• The converse, notWithin = notContainedBy(minuend, extend(subtrahend, n, n)), is worse: today notWithin matches SpanNotQuery(include, exclude, n, n), and the open #16820 proposes moving span users to intervals. Not run.
• With a disjunctive reference (or(...)), the hunt's separate overlap-filters finding (LFV-828, another root cause) also applies to overlapping.

What the checks validated

• Gradle, the same worktree and seed: the minimal test passes with assertions on and off (1 test each); the intervals suite (117 tests) and the flexible-parser suite (125 tests, 1 skipped) pass, and :lucene:queries:checkGoogleJavaFormat passes.
• The result change is real: with the change, within(phrase(brown fox), 1, jumps) on the docs' example sentence goes from 0 to 1 (tie-break probe). No upstream test pins either behaviour for multi-position sources.

• Step 1, the documented relation. The unit first settled from the docs which pairs are presented as opposites: within / notWithin ("appear within" / "do not appear within"), containedBy / notContainedBy, overlapping / nonOverlapping.
• Bounded-exhaustive leg. FilterLawsExhaustive fed every pair of minimal interval sets inside positions 0-6 (1,430 x 1,430 pairs, 32,695,520 filter evaluations) through the real filter classes via a public custom IntervalsSource. containedBy / notContainedBy and overlapping / nonOverlapping over a widened reference were exact complements; apart from a separately registered notContaining defect, the only violations were within / notWithin "neither" (2,530,558 / 645,023 / 106,025 intervals for n = 0 / 1 / 2). That put the gap in the two factories, not in the filter iterators.
• Real-source harness. ComplementLawsTV (116 x 116 source shapes over all 1,364 documents of up to 5 positions over a 4-letter alphabet, plus 60,000 random pairs), with every other known interval fix shadowed, left the same class as the only residual besides extend() clamp artifacts.
• Reduction and verification. Reduced by hand to the public-API JUnit; then an independent reproducer, cross-model reviews (OpenAI GPT-5.6), an intended-behaviour devil's advocate, an adjudication, a credibility audit, a re-verification and a second adjudication. No model checker, SMT solver or prover produced the signal.