Intervals.before matches a source at the first position against a reference that also starts there

Intervals.before(source, reference) "Returns intervals from the source that appear before intervals from the reference"; fn:before in the flexible StandardQueryParser calls it and is documented the same way. It is built as containedBy(source, extend(PRECEDING(reference), Integer.MAX_VALUE, 0)), where PRECEDING is a package-private helper that places a one-position pseudo-interval just before each reference interval, at Math.max(0, pos - 1). For a reference starting at p > 0 the window is [0, p-1], strictly before. For p = 0 there is no position before it, but the clamp gives the window [0, 0], so a source exactly on the first token counts as before a reference that starts on the same token. before(york, york) therefore matches the one-word document york, and before(new, phrase(new york)) matches new york and new york city; moved one position right (x york, x new york), the same texts correctly do not match, and ordered() and after() give the expected answers. before() itself only gains hits, never loses one (under a negating outer query, such as a MUST_NOT clause, the extra interval can hide a document instead); Weight#matches reports the extra [0, 0] interval too, which is what Matches-based highlighting reads. No special settings are needed (StandardAnalyzer or the test framework's whitespace analyzer, the default IndexWriterConfig, a plain or the test framework's randomized searcher; several random test codecs gave the same result). The code dates from LUCENE-8629, which added before(), so every release from 8.0.0 to 10.5.2 and main is affected (12 releases run). Skipping reference intervals that start at position 0 fixes it; two variants were validated with the repro and the whole lucene/queries module.

• Intervals: org.apache.lucene.queries.intervals matches positions inside a field. An interval is a range of token positions [start, end]; the first token of a field is position 0. IntervalQuery(field, source) matches a document when the source has at least one interval in it. The package is marked "experimental classes" (package-info.java:21).
• before(): Intervals.before(source, reference) "Returns intervals from the source that appear before intervals from the reference" (Intervals.java:580). fn:before(source reference) in the flexible StandardQueryParser (since 9.1.0) calls it (intervalfn/Before.java:37) and says "Matches intervals from the source that appear before intervals from the reference" (intervalfn/package-info.java:425).
• How it is built (Intervals.java:581-584): containedBy(source, extend(PRECEDING(reference), Integer.MAX_VALUE, 0)). containedBy "Returns intervals from the small query that appear within intervals of the big query" (:554). PRECEDING is the package-private OffsetIntervalsSource with before = true: "a pseudo-interval that appears ... one position before ... each interval from the reference" (OffsetIntervalsSource.java:28-31).

1. The marker. For a reference interval starting at pos, PRECEDING returns start() = end() = Math.max(0, pos - 1) (OffsetIntervalsSource.java:51-65, the clamp at :63; end() at :94-97). The Matches path (highlighting) wraps the same iterator (:143).
2. The window. extend(marker, Integer.MAX_VALUE, 0) stretches it back to position 0 (ExtendedIntervalIterator.java:61): [0, pos-1] for pos > 0, which is exactly "strictly before".
3. The boundary. For pos = 0, Math.max(0, -1) is 0, so the window is [0, 0] instead of absent. containedBy keeps a source interval a when a window b has b.start <= a.start and b.end >= a.end (ContainedByIntervalsSource.java:52-61), so a source at [0, 0] passes.
4. Why the clamp is there (presumably). A positioned iterator must not return -1 (it means "not positioned yet", IntervalIterator.java:46-52); the history gives no reason. But an iterator may skip such a reference: "it is possible for a document to return NO_MORE_INTERVALS on the first call to nextInterval()" (IntervalIterator.java:35-36).

Both must hold: the source has a one-position interval exactly at [0, 0] (a wider source starting at 0, such as a phrase, does not fit in [0, 0]), and the reference has at least one interval in the document and every one of them starts at 0 (any later reference makes [0, 0] legitimately before it). Position 0 is absolute: normally the field's first token, but a first token behind a removed leading stopword sits at position 1 (FilteringTokenFilter.java:50-58), and a token in a later value of a multi-valued field normally sits after 0; neither triggers it. Typical shapes: before(X, X) with one leading X; before(term, phrase or disjunction that starts with that term) at the start of a field; synonyms stacked on the first token, also with two distinct terms (before(a, b) with a and b stacked at position 0 matches; the same stack one position later does not); and a reference that starts at 0 without sharing a token with the source, such as extend(b, 1, 0) on a b (seen in the finder's harness). An exhaustive check over all 363 documents of 1-5 tokens over {a, b, c} and 36 before() queries (13,068 checks) found 366 extra matches, every one with the source and the earliest reference at position 0, and 0 missed.

Intervals.after is not affected: for a positioned reference interval, FOLLOWING saturates only when end + 1 reaches Integer.MAX_VALUE (OffsetIntervalsSource.java:66-83), above the highest position IndexWriter accepts; its other branches only pass the "not positioned" and "exhausted" sentinels through.

• Who is exposed. Users of Intervals.before, directly or nested in other interval functions, through IntervalQuery; and of fn:before in the flexible StandardQueryParser (since 9.1.0). The API is public in lucene-queries since 8.2.0 (lucene-sandbox in 8.0.0 and 8.1.x). Downstream engines expose it too: Elasticsearch's intervals query maps its before filter to Intervals.before (read in its source, not run).
• When it shows. A query whose source can match position 0 (normally the field's first token), on a document whose reference matches all start there: before(X, X); before(term, phrase that starts with it); synonyms stacked on the first token, also two distinct stacked terms (before(a, b) with a and b both at position 0); a reference that starts at 0 for another reason, such as extend(b, 1, 0) on a b. before(a, b) with two distinct single terms, no stacked synonyms and no extension never triggers it.
• Silent. No exception. Extra hits in IntervalQuery, an extra [0, 0] interval from the iterator and from Weight#matches (its MatchesIterator reports [0, 0], so a Matches-based highlighter would mark it; no highlighter was run), and an extra interval fed into any enclosing interval operator. Under a negating outer query (a MUST_NOT clause; by the same logic the negating interval operators) the extra interval removes a hit instead.
• No special setup. StandardAnalyzer or a whitespace analyzer, the default IndexWriterConfig, a plain IndexSearcher or the test framework's randomized newSearcher; one document is enough; assertions on or off; several random test codecs gave the same result.
• How likely. Rare: it needs source and reference to overlap at position 0. For such a query, the affected documents match every time. How often such queries meet such documents in real applications is unknown.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: 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.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.queries.intervals.TestBeforeAtFirstPosition.testTermIsNotBeforeItself(TestBeforeAtFirstPosition.java:43)

• The contract is strict. "Returns intervals from the source that appear before intervals from the reference" (Intervals.java:580); fn:before: "Matches intervals from the source that appear before intervals from the reference" (intervalfn/package-info.java:425). No first-position exception, and at every other position the code is strict ([0, p-1]).
• Not shift invariant. york matches and x york does not; new york matches and x new york does not. No reading of "appear before" makes york precede itself in one document and not in the other.
• The design says "ordered". LUCENE-8629, which added before(), describes it as "similar to an ordered near, but returning only intervals from 'a' rather than an interval spanning both a and b" (#9675). ordered() is strict (OrderedIntervalsSource.java:151) and gives the expected answer on the same texts.
• Precedent. LUCENE-9099 (7c1ba1aebee, 2020, "Correctly handle repeats in ORDERED and UNORDERED intervals") lists "UNORDERED(a, a) will match on documents that just containg a single a" as "somewhat confusing behaviour" and changes it: a source matching relative to itself.
• No test covers it. TestIntervals#testBefore (TestIntervals.java:909-913) uses before(cold, twelve), and twelve is never at position 0 in its corpus; the fn:before examples in the parser docs, TestStandardQPEnhancements and TestMatchHighlighter never put a reference at position 0.

The strongest case for "intended" (rated moderate by the intended-lens reviewer from another model family): the clamp is deliberate code, because -1 means "not positioned"; TestIntervals#testOffsetIntervals (TestIntervals.java:541-577), added in the same commit, asserts the helper's clamped [0, 0] output; extend() also clamps at 0 by a recorded decision (LUCENE-8612, #9658: a positional filter was removed because "it ends up breaking notWithin in certain circumstances"); and the package is experimental.

Why it fails: the helper test covers only the package-private helper, never before(). The helper's own javadoc promises a pseudo-interval "one position before" each reference, and none exists before position 0. Skipping such a reference is legal (IntervalIterator.java:35-36) and is what the fix does. The extend() clamp only drops positions below 0 and still contains the reference start; the PRECEDING clamp instead adds the reference's own first position to the "before" window. "Experimental" allows API changes, not wrong answers. LUCENE-8629's only review comment is "+1, the patch looks good"; position 0 was never discussed. Left for the reviewer to weigh: both fixes remove hits that every release since 8.0.0 has returned for the affected documents (a compatibility change of unknown practical reach), and they make an existing iterator-state quirk more frequent (see Fixes). Verdict: not intended, a defect.

Both validated fixes stop PRECEDING from producing a pseudo-interval for a reference interval that starts at position 0, so a document whose every reference starts there has no "before" window. The first option adds a mode that only before() uses and leaves TestIntervals#testOffsetIntervals unchanged; the second changes the helper's PRECEDING mode for every caller (before() is its only production user; after() uses FOLLOWING, which neither fix touches) and updates three rows of that test. Both remove hits that every release since 8.0.0 has returned for the affected documents. Documenting the boundary instead is possible but leaves the shift variance. Until a fix ships, Intervals.ordered(source, reference) gives the expected documents for match/no-match filtering (it gave them in the repro's controls); its intervals span both sources, so highlighting and interval scores differ.

In OffsetIntervalsSource, add a skipFirstPosition flag (a 3-argument constructor; the 2-argument one passes false; the flag joins equals/hashCode), and in the PRECEDING iterator override nextInterval() to skip reference intervals that start at 0 when the flag is set. Intervals.before constructs the helper with the flag. The finder's sketch, with its comment reworded to fit 100 columns.

   private final IntervalsSource in;
   private final boolean before;
+  // Set by Intervals.before: a reference interval that starts at position 0 has no position
+  // before it, so it produces no pseudo-interval instead of one clamped to position 0
+  private final boolean skipFirstPosition;
 ...
+        @Override
+        public int nextInterval() throws IOException {
+          int pos = in.nextInterval();
+          while (skipFirstPosition && pos == 0) {
+            pos = in.nextInterval();
+          }
+          return start();
+        }

Trade-offs

• No existing test changes; the price is a flag that only matters in PRECEDING mode: the only PRECEDING construction with the flag off is TestIntervals#testOffsetIntervals (after() also passes false through the 2-argument constructor, with no effect, though the flag now takes part in equals/hashCode). toString() stays PRECEDING(...). Cost: one comparison per reference interval.
• Side effect: no wrong matches or interval contents were found, but iterator-state protocol violations become more frequent. In a document whose every reference starts at 0, the reference side now has no interval, so FilteringIntervalIterator.start()/end() return NO_MORE_INTERVALS instead of -1 before the first nextInterval() (FilteringIntervalIterator.java:36-50, reset() at :57-60). That pre-existing quirk is already reachable whenever a filter has no interval in a document; the fix makes it happen in more documents: in the finder's harness the before() protocol-check failures rise from 4,668 to 11,436 (documents of up to 4 positions) and from 11,973 to 35,568 (up to 3 positions with stacked synonyms). Worth stating in the PR.
• Compatibility: the affected documents stop matching, a change of results every release since 8.0.0 has returned; how many applications see such documents is unknown.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: stock + the new test, 2 of 3 fail with assertions on and off; + the fix, assertions on: :lucene:queries:check (ecjLint, forbiddenApis, checkGoogleJavaFormat and all 52 suites, 515 tests of the module, including TestIntervals 43 and the new test 3) plus TestStandardQPEnhancements (23) and TestMatchHighlighter (6), both of which use fn:before: 544 tests, 5 skipped, 0 failures; assertions off: the same tests, 6 skipped, 0 failures.
• Standalone runner: 3 of 3 pass with assertions on and off.
• Earlier, on ea57360912ed: the finder's, the independent reproducer's, the reviewer's and the devil's advocate's tests and the security probe pass with the finder's version; the exhaustive mismatches drop from 366 to 0; the finder's harness finds no extra before() interval in two before()-only re-runs (1,408,044 checks) and in a smaller re-run with all six of the unit's candidate fixes (287,753,697 checks).

Override nextInterval() in the PRECEDING iterator to skip reference intervals that start at 0 unconditionally, say so in the class javadoc, and drop the first 0, 0 pair from the three non-empty PRECEDING rows of TestIntervals#testOffsetIntervals (+11/-1, and +4/-3 in the test).

+        @Override
+        public int nextInterval() throws IOException {
+          int pos = in.nextInterval();
+          while (pos == 0) { // nothing precedes the first position
+            pos = in.nextInterval();
+          }
+          return start();
+        }

Trade-offs

Smaller (no flag, constructor or equals/hashCode change) and makes the helper match its javadoc. before() is the only production user of PRECEDING (Intervals.java:583), the only mode it changes; after() (:590) uses FOLLOWING. So results are identical to the first option. It changes an assertion a reviewer may read as deliberate; the same compatibility change and FilteringIntervalIterator side effect apply.

What the checks validated

Same worktree: assertions on, the whole module's tests and the two fn:before suites, 544 tests, 5 skipped, 0 failures (TestIntervals 43 of 43 with the updated rows), and :lucene:queries:check -x test passes; assertions off, the same 544 tests, 6 skipped, 0 failures. Standalone runner: 3 of 3 pass with assertions on and off.

State in the before() and fn:before javadoc that a source at position 0 counts as before a reference that starts at position 0.

Trade-offs

Changes no code, but keeps the shift variance and the disagreement with ordered(). Not built; not recommended.

Method: bounded-exhaustive translation validation of the stock main jar against an independent reference semantics (the hunt's "semi-formal" tier).

• The hunt unit on spans and intervals wrote a reference semantics for the interval operators (IvRef) and a harness (IvTV) that runs the real iterators on every document of up to 6 positions over {a, b, c} and up to 4 positions with stacked synonyms, for every 1- and 2-level expression over 24 interval operators: 1,401,702,324 checks.
• The exact-interval check reported extra intervals for 206,037 of 7,200,414 before() checks (alone, under extend, with repeated sources, or both). With PRECEDING skipping reference intervals that start at position 0, none remain in two before()-only re-runs (1,408,044 checks, documents of up to 4 positions and up to 3 with stacked synonyms) and in a smaller re-run with all six of the unit's candidate fixes (287,753,697 checks; it did not cover the whole first run).
• The finder reports that it first noticed the clamp while reading OffsetIntervalsSource to build the model; the harness then witnessed it, and it was reduced to a public-API JUnit. Independent AI tools reproduced, reviewed and judged it (see the checks).