An exact PhraseQuery loops forever, and a sloppy one matches wrongly, when a query position plus a document position overflows int

PhraseQuery.Builder#add(Term, int) accepts any query position that is >= 0 and in order, and MultiPhraseQuery.Builder#add(Term[], int) any int. The phrase matchers add a document position and such a query offset in int. When the sum passes Integer.MAX_VALUE it wraps negative: with slop 0, ExactPhraseMatcher#nextMatch stops making progress and loops forever inside one document (ExactPhraseMatcher.java:159-171 on main a9779ef3c193), and IndexSearcher#setTimeout cannot end it because the timeout is checked between windows of documents; with slop 1 or more, SloppyPhraseMatcher gets a negative span that passes matchLength <= slop, so a document about 2^31 positions away matches. The smallest trigger is a@0 b@Integer.MAX_VALUE on the one-document index x a b; b@IndexWriter.MAX_POSITION hangs once a is at position 129, and a gap of 300 hangs against legal indexed positions near 2^31. No codec or searcher option is needed (the runs used the default codec and plain IndexSearchers; the overflowing sums are in the matchers); one document is enough; phrases parsed from ordinary text on default analysis never do this. The hang came with LUCENE-6260 in 5.1.0 (2015); the sloppy false hit reproduces on every executed release from 1.9.1. Computing the two sums in long (two small hunks) fixes every PhraseQuery case that was run except slop Integer.MAX_VALUE, where the clamped span still matches. Executed with the fix, an exact MultiPhraseQuery whose lowest position is negative still hangs when the lead's document position minus that position passes Integer.MAX_VALUE (for example a@-200 b@0 with a at 2,147,483,448), and MultiPhraseQuery positions more than 2^31 apart still give false hits; rebasing MultiPhraseQuery positions to 0 would cover both (not built).

• Query offset: the position a term has inside the phrase. PhraseQuery.Builder#add(Term, int) checks only position >= 0, the order, the field and setMaxTerms (PhraseQuery.java:126-155); MultiPhraseQuery.Builder#add(Term[], int) checks only the field (MultiPhraseQuery.java:125-140), and negative MultiPhraseQuery positions are a tested feature.
• Lead: the exact matcher walks the positions of the first query term (offset 0 after PhraseQuery#rewrite) and checks that every other term sits at lead position + its offset.
• IndexWriter.MAX_POSITION = Integer.MAX_VALUE - 128 (IndexWriter.java:211): the largest indexed position. It bounds documents only; its 128 of headroom does not cover adding a query offset.

ExactPhraseMatcher#nextMatch (ExactPhraseMatcher.java:149-180), for a@0 b@2147483647 on x a b (a at 1):

1. phrasePos = lead.pos - lead.offset = 1 (:159); expectedPos = phrasePos + posting.offset = 1 + 2147483647, which wraps to -2147483648 (:162).
2. advancePosition(b, -2147483648) (:165) moves to the first position at or after the target; b's current position, -1, is not below it, so it returns true without moving (:135-146).
3. b is not at the expected position, so the lead is re-targeted to b.pos - b.offset + lead.offset = -1 - 2147483647, which also wraps to -2147483648 (:170); the lead does not move either.
4. continue advanceHead (:171) starts again from the same state. Nothing ever changes, so this is a true infinite loop, and it makes no postings or reader calls.

Why a timeout cannot help. With IndexSearcher#setTimeout, IndexSearcher wraps the bulk scorer in TimeLimitingBulkScorer (IndexSearcher.java:846-848), which checks the timeout only before each window of documents (TimeLimitingBulkScorer.java:72-83). The loop never leaves one document's TwoPhaseIterator#matches, although QueryTimeout's javadoc says that with setTimeout "bulk scoring will be time-bound" (QueryTimeout.java:20-23).

PhrasePositions#nextPosition stores position = postings.nextPosition() - offset (PhrasePositions.java:55); SloppyPhraseMatcher#nextMatch measures matchLength = end - pp.position (SloppyPhraseMatcher.java:212, 226, 228) and matches when matchLength <= slop (:236). For a@0 b@2147483647 slop 1 on b x x a: position(a) = 3, position(b) = 0 - 2147483647, end = 3, so the span is 2147483650, which wraps to -2147483646 and passes <= 1. MultiPhraseQuery a@Integer.MIN_VALUE b@0 slop 1 on a x x b gives the same false hit through PhrasePositions.java:55.

The lead's document position plus a query offset must pass 2,147,483,647:

• offset Integer.MAX_VALUE with the lead at position 1 or later (at 0 the sum is exactly Integer.MAX_VALUE and the result is correct);
• offset MAX_POSITION with the lead at position 129 or later (128 gives the correct 0);
• a small gap, such as the 300 that the classic QueryParser builds from a quoted phrase with 299 stopwords between two words, against a legal indexed position within 300 of 2^31 (for example from a huge position-increment gap).

MultiPhraseQuery with slop 0 reaches the same exact-matcher loop. Its positions are not rebased and may be negative, so it also triggers when lead.pos - lead.offset itself passes Integer.MAX_VALUE (ExactPhraseMatcher.java:159): the lead's document position minus a negative lowest query position, for example a@-200 b@0 with a at 2,147,483,448 (executed by the fact check; still hangs with the fix below).

• Who is hit. Applications that run a PhraseQuery or MultiPhraseQuery whose query offset, added to the document position of the phrase's first term, passes 2^31 - 1 (for a MultiPhraseQuery with a negative lowest position, also that document position minus the negative position): an application that maps its own values (not token positions) to phrase positions, or uses a sentinel such as Integer.MAX_VALUE for "far away"; an application that exposes explicit phrase positions to its clients without a bound; an index whose analysis puts positions within a few hundred of 2^31 (a huge getPositionIncrementGap) together with a phrase gap above 128, which the classic QueryParser builds from a quoted phrase with that many stopwords.
• Default vs opt-in. Nothing to opt into. The runs used the default codec, plain IndexSearchers, the default analyzer and similarity; the overflowing sums are in the matchers, not behind a codec or searcher option (code reading); other codecs and searcher configurations were not run.
• Scale. One document that contains the phrase's terms, with the first term at position 1 or later.
• Effect, slop 0. The search thread spins at 100% CPU forever on the first such document (still spinning after 60 s in an independent run); IndexSearcher#setTimeout does not end it, so a request handler that relies on the timeout loses the thread. Repeated requests could use up a search thread pool (inferred, not executed). That Thread#interrupt and ExitableDirectoryReader would not stop it either is code reading only.
• Effect, slop > 0. Silent false hits (count 1 instead of 0), no exception.
• How likely: rare. Phrases that the query parsers build from ordinary text on default analysis never have such offsets.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 2 failed
    => java.lang.Exception: Test timeout exceeded (>= 5000 msec).
  JUnit Vintage:TestPhraseQueryPositionOverflow
    ClassSource [className = 'org.apache.lucene.search.TestPhraseQueryPositionOverflow', filePosition = null]
    => org.opentest4j.MultipleFailuresError: Multiple Failures (3 failures)
	java.lang.AssertionError: The test or suite printed 16388 bytes to stdout and stderr, even though the limit was set to 8192 bytes. Increase the limit with @Limit, ignore it completely with @SuppressSysoutChecks or run with -Dtests.verbose=true
	com.carrotsearch.randomizedtesting.ThreadLeakError: 1 thread leaked from SUITE scope at org.apache.lucene.search.TestPhraseQueryPositionOverflow: 
   1) Thread[id=41, name=TEST-TestPhraseQueryPositionOverflow.testExactPhraseWithHugePositionTerminates-seed#[DEADBEEF]-worker, state=RUNNABLE, group=TGRP-TestPhraseQueryPositionOverflow]
        at org.apache.lucene.search.ExactPhraseMatcher.nextMatch(ExactPhraseMatcher.java:171)
        at org.apache.lucene.search.PhraseScorer$1.matches(PhraseScorer.java:68)
        at org.apache.lucene.search.Weight$DefaultBulkScorer.scoreTwoPhaseIterator(Weight.java:311)
        at org.apache.lucene.search.Weight$DefaultBulkScorer.score(Weight.java:282)
        at org.apache.lucene.search.LRUQueryCache.cacheIntoBitSet(LRUQueryCache.java:617)
        at org.apache.lucene.search.LRUQueryCache.cacheImpl(LRUQueryCache.java:588)
        at org.apache.lucene.search.LRUQueryCache.tryPopulateCache(LRUQueryCache.java:609)

• Legal input. PhraseQuery.Builder#add(Term, int): the position "must be greater than or equal to that of the previously added term", and the code checks position < 0, the order, the field and setMaxTerms (PhraseQuery.java:119-155). MultiPhraseQuery.Builder#add(Term[], int) checks only the field (MultiPhraseQuery.java:121-140). IndexWriter.MAX_POSITION is the "Maximum value of the token position in an indexed field" (IndexWriter.java:210-211). No javadoc, MIGRATE.md, CHANGES entry or package doc bounds query positions. #15332 added setMaxTerms, whose javadoc says "This helps prevent excessive memory usage for very long phrases" (PhraseQuery.java:99-105); no position bound was discussed. The builders' lack of a bound is not an explicit promise about extreme positions, but nothing tells a caller to avoid them.
• Meaningful offsets. The control test (a@0 b@MAX_POSITION on a document with b at MAX_POSITION) matches, count 1; the same query hangs on a document with a at 129. A gap of only 300 hangs against legal indexed positions near 2^31, so the trigger is not limited to absurd query values.
• The slop contract. "The slop defines the maximum edit distance for a document to match" (PhraseQuery.java:268-283). TestPhraseQuery.java:339 builds a phrase with slop Integer.MAX_VALUE, so extreme values are expected to work.
• Termination. A query its builder accepts that spins forever inside one document is not plausibly intended; no test, comment, PR or list thread treats such offsets as unsupported.
• Upstream treats this class as a bug. LUCENE-8034 (#9082) fixed SpanNotQuery's overflow near Integer.MAX_VALUE in 7.2.0 with a test (TestBasics#testSpanNotNoOverflowOnLargeSpans); ExtendedIntervalIterator guards end += after with an // overflow check (LUCENE-8612); IndexingChain rejects "position overflowed Integer.MAX_VALUE" at index time.
• History. LUCENE-6260 (#7322), which wrote the overflowing exact-matcher lines in 2015, discusses only performance. The scorer it replaced computed document position minus query position, which cannot overflow, and returned the correct 0.

The strongest case for "works as designed": a phrase offset near 2^31 is garbage in, garbage out; Lucene's SECURITY.md (lines 28 and 38) makes the application responsible for bounding input passed straight to Lucene APIs; the matchers are @lucene.internal; and the query timeout is cooperative by design, checked between documents.

Why it fails: the public builders accept the offsets and some are meaningful (MAX_POSITION matches a legal document); the small-gap variant needs no large query offset at all; the matchers are reached through the public PhraseQuery and MultiPhraseQuery; and a wrong hit or a query that never terminates on accepted input is a correctness bug whatever the threat model says (the threat model decides only the security label). The timeout point is right, so the timeout bypass is a consequence of the in-document loop, not a second defect. Verdict: not intended, a defect.

One fix was built and validated; three alternatives were not built.

Two hunks, 2 files, +15/-4 (the finder's fix). Exact: compute phrasePos + posting.offset in long and end the search in this document when it passes Integer.MAX_VALUE; later lead positions only grow, so no later match is possible. For PhraseQuery every offset is >= 0 and the lead has the smallest (the postings are sorted by position, PhraseQuery.java:381-383, 543-545), so lead.pos - lead.offset and the lead re-target stay inside int (code reading; PhraseQuery#rewrite also rebases the first offset to 0). Sloppy: a span(pp) helper replaces the three end - pp.position; a clamped span is larger than any slop below Integer.MAX_VALUE.

// ExactPhraseMatcher#nextMatch
final long expected = (long) phrasePos + posting.offset;
if (expected > Integer.MAX_VALUE) {
  // no document position is that large: no match at this or any later lead position
  break advanceHead;
}
final int expectedPos = (int) expected;

// SloppyPhraseMatcher: matchLength = span(pp) instead of end - pp.position
private int span(PhrasePositions pp) {
  long d = (long) end - pp.position;
  return d > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) d;
}

Trade-offs

• One long add and compare per term per lead position in the exact matcher's inner loop, a hot path. Lucene's SECURITY.md asks that robustness fixes not slow down hot paths (line 46). Not benchmarked.
• Does not cover (executed by the fact check): an exact MultiPhraseQuery with a negative lowest position whose lead document position minus that position passes Integer.MAX_VALUE, because phrasePos = lead.pos - lead.offset (ExactPhraseMatcher.java:159) is not guarded: a@-200 b@0 with a at 2,147,483,448 still spins (option B covers it); MultiPhraseQuery positions more than 2^31 apart (option B); slop Integer.MAX_VALUE, where a@0 b@Integer.MAX_VALUE counts 1 on b x x a with the fix (comparing the span with the slop in long would cover it; not built).
• Not executed: the other int position expressions, pp.position + pp.offset in SloppyPhraseMatcher.java:244, 259, 269, 615 (the Matches API and repeated terms) and PostingsAndFreq#compareTo (PhraseQuery.java:381-383, reached by option B's case).
• The open PR #16913 changes SloppyPhraseMatcher and PhrasePositions (match offsets of repeated terms) without touching this arithmetic; a fix PR would need a rebase if it lands first.
• A CHANGES "Bug Fixes" line would be usual; none is drafted.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle: the new test fails 6 of 7 on the stock tree and passes 7 of 7 with the fix, with assertions on and off.
• 20 suites (the 8 *Phrase* suites of org.apache.lucene.search, TestMatchesIterator, the two search-equivalence suites, the five explanation suites, TestPositionIncrement, TestTimeLimitingBulkScorer, the phrase test of TestBooleanSimilarity and the new test): 365 tests, 0 failures, assertions on and off.
• The whole lucene/core module: 749 suites, 8,896 tests, 0 failures, assertions on and off. :lucene:core:check -x test (google-java-format, ecjLint, forbiddenApis) passes.
• Earlier, by the hunt: the finder's 5 of 5, the independent reproducer's 12 of 13 (the one left is the withdrawn toString case), a cross-model reviewer's 3 of 3, the QueryParser document-side test, and 88 + 50 focused upstream phrase tests.
• The fact check's edge probes: a repeated term a@0 a@Integer.MAX_VALUE (exact on x a a, slop 1 on a x x a) and three terms a@0 b@1 c@Integer.MAX_VALUE on x a b c return 0 with the fix (stock: the two exact cases hang).
• Not run: a benchmark, nightly tests.

Two MultiPhraseQuery cases stay open with the fix above. (1) Executed by the fact check: an exact MultiPhraseQuery whose lowest position is negative hangs when the lead's document position minus that position passes Integer.MAX_VALUE (ExactPhraseMatcher.java:159), because MultiPhraseQuery does not rebase its positions (MultiPhraseQuery.java:182-195): a@-200 b@0 with a at 2,147,483,448 and a@-2147483000 b@0 with a at 1000 do not return within 5 s, stock and with the fix. (2) An executed probe, stock and with the fix above (same results): an exact MultiPhraseQuery a@Integer.MIN_VALUE b@Integer.MAX_VALUE counts 1 on b a, a@Integer.MAX_VALUE b@Integer.MIN_VALUE counts 1 on a b, and the first with slop 1 counts 1 on b a; expected 0 each (the first query correctly gives 0 on a b). MAX_VALUE - MIN_VALUE = 2^32 - 1 is -1 in int, so the matcher looks for b one position before a; PhraseQuery.PostingsAndFreq#compareTo also subtracts positions in int (PhraseQuery.java:381-383). Options: rebase MultiPhraseQuery positions to start at 0, as PhraseQuery#rewrite does, and reject positions whose spread does not fit in an int; with the fix above this covers both cases, since every offset is then >= 0 and the lead's is 0 (code reading). Or carry PhrasePositions.position and the exact matcher's phrasePos and re-target in long, with Integer.compare in compareTo.

Trade-offs

Case (2) needs explicit positions more than 2^31 apart; case (1) needs only a negative lowest position and indexed positions near 2^31 (a spread of 200 is enough). No query parser was surveyed for either shape. Rejecting spreads is an API change; long positions touch more of the sloppy matcher.

Reject PhraseQuery offsets above IndexWriter.MAX_POSITION and MultiPhraseQuery spreads that do not fit in an int.

Trade-offs

Removes the absurd shapes and the MultiPhraseQuery spread case, but not a MultiPhraseQuery with a negative lowest position and a small spread (a@-200 b@0 passes a spread bound and still hangs near 2^31), nor the hang from a small gap (300) against legal indexed positions near 2^31, so the matcher arithmetic must still be fixed. It also turns accepted queries into exceptions. Not built.

Make TwoPhaseIterator#matches of phrase scorers consult the QueryTimeout.

Trade-offs

Turns the hang into a timeout but keeps the wrong loop and the false hits, and adds work to every match call. Not a substitute. Not built.

Method: non-formal (the hunt's hunt unit on phrase matching, 2026-10-26, main ea57360912ed).

• Signal. While writing the model-to-line map of a shared positional harness for phrase and span queries, the finder recorded the documented limits as preconditions and checked the int expressions document position +/- query offset in both matchers against them by hand. No solver was needed: phrasePos + offset with an offset up to Integer.MAX_VALUE overflows. The harness's exhaustive scope (offsets up to 9, positions up to 8) cannot reach these values, which is why the tier stays non-formal.
• Witness. A 5-test public-API JUnit on the stock jars: 5 of 5 fail with assertions on and off, on main, 10.5.2 and 9.12.3.