GraphTokenStreamFiniteStrings.getFiniteStrings: a TokenStream read after the iterator fetches another path replays wrong tokens

The finding in 30 seconds

Background: token graphs and their paths

A synonym filter can put several tokens at one place. For "new york" with the synonym ny, the token graph has new (position 0), ny (also position 0, position length 2, so it spans both words) and york (position 1). The tokens form a graph, not a line. Each token gets an id in the order it arrives: the repro feeds new, ny, york, while Lucene's SynonymGraphFilter emits ny first.
GraphTokenStreamFiniteStrings turns that graph into an automaton. getFiniteStrings() returns an Iterator<TokenStream> with one plain, linear TokenStream per path: here [new, york] and [ny]. Lucene's query builders use it to build one clause per path.

The finding, step by step

Feed GraphTokenStreamFiniteStrings three tokens in this order, as the repro's CannedTokenStream does: new (position 0), ny (also position 0, position length 2, so it spans both words) and york (position 1). This is the graph of "new york" with the synonym ny; it has two paths, [new, york] and [ny].
Build new GraphTokenStreamFiniteStrings(stream), collect every path's TokenStream with getFiniteStrings().forEachRemaining(list::add), then read each stream.
You expect [new, york] and [ny], which is what you get when you read each stream before asking the iterator for the next one.
Instead you get [ny, york] and [ny], with no error; [ny, york] is no path of the graph. With the token order of Lucene's SynonymGraphFilter, which emits ny first, the same pattern gives [new] and [new, york] instead: the ny path is lost.
Why: both streams read the same buffer of token ids, numbered in arrival order (new 0, ny 1, york 2). Stream 1 was made for 2 ids, [new, york]; fetching path 2 wrote ny into slot 0, and stream 1 still reads 2 slots: ny plus the left-over york.

Who is affected

Only code that calls getFiniteStrings() itself and keeps a returned stream unread while the iterator fetches another path: it collects the streams first, calls next() twice, or peeks with hasNext(). Lucene's QueryBuilder and IntervalBuilder read each stream at once, so their queries are right. Every release from 6.5.0 to 10.6.0.

Mechanism, terms and numbers547 words

GraphTokenStreamFiniteStrings.getFiniteStrings() returns an Iterator<TokenStream> with one stream per path of a token graph. Each next() creates a new stream, but all streams of one iterator wrap the same IntsRef: for every non-empty path, FiniteStringsIterator.next() returns its builder's one reused IntsRef ("just valid until the next call of this method", FiniteStringsIterator.java:97 at 5adff78bb168), and the wrapper passes it on without a copy (GraphTokenStreamFiniteStrings.java:154). The stream reads its token ids from that buffer only when it is read (:72), so a later hasNext() or next() that fetches another path overwrites (part of) the ids of a stream that has not been read yet. For the tokens new, ny (spanning both positions), york, fed in that order, collecting both streams and then reading them gives [ny, york] and [ny] instead of [new, york] and [ny], silently, with assertions on and off; with the token order of Lucene's SynonymGraphFilter (ny first) the same pattern loses the ny path. LUCENE-7638 introduced this in 6.5.0 (2017), when it replaced the 6.4 API, which copied each path, with the lazy iterator; every release run since then has it. Lucene's own callers (QueryBuilder, IntervalBuilder) read each stream before they advance, so only application code that calls the helper itself and holds a stream is hit. A one-line copy fixes it. Priority Low.

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/`)

The iterator pre-fetches into a reused buffer. getFiniteStrings(start, end) wraps a FiniteStringsIterator (util/graph/GraphTokenStreamFiniteStrings.java:132-158). hasNext() fetches the next path, current = it.next() (:139-147). FiniteStringsIterator.next() returns string.get() (util/automaton/FiniteStringsIterator.java:132, :144), the same IntsRef object of its one builder for every non-empty path (only the empty string gets a static EMPTY, :102-105), and documents that "The return value is just valid until the next call of this method!" (:97).
No copy (the fix site). next() returns new FiniteStringsTokenStream(current) (GraphTokenStreamFiniteStrings.java:154).
The stream reads late. FiniteStringsTokenStream keeps that object (this.ids = ids, :63), fixes end = offset + length once (:65) and reads ids.ints[offset] on every incrementToken() (:72).
The numbers (the repro's token order). Token ids: new = 0, ny = 1, york = 2. The first path is [0, 2], length 2, so stream 1 gets end = 2. The next hasNext() writes 1 into slot 0 and sets the length to 1; slot 1 still holds 2. The third hasNext() finds no more paths and only sets the length to 0, which no stream reads. Read now, stream 1 emits slots 0 and 1, [ny, york]; stream 2 emits [ny].
Always in bounds. The builder's array only grows, and every id is a label of the graph's automaton, so the stream never throws: the result is a silently wrong token sequence.

Which call patterns break (all executed on main)

pattern	first stream reads
collect all streams (`forEachRemaining`, or `while (it.hasNext()) list.add(it.next())`), then read	the wrong tokens
`a = it.next(); b = it.next();`, then read `a`	the wrong tokens
`a = it.next(); it.hasNext();`, then read `a` (a bare peek)	the wrong tokens
read each stream before the next `hasNext()`/`next()`, as Lucene's callers do	its own path

Exposure and likelihood318 words

Who. Application code that calls the public getFiniteStrings() or getFiniteStrings(start, end) itself and holds a returned stream unread while the iterator fetches another path (the next hasNext() or next() does, unless the iteration has ended), for example to count or cap the paths before building clauses.
Not affected (by reading). QueryBuilder.analyzeGraphBoolean builds each side-path query inside its lazy Iterator<Query>.next() (util/QueryBuilder.java:520-538; the default newGraphSynonymQuery takes them one at a time, :618-622); QueryBuilder.analyzeGraphPhrase reads each stream before the next hasNext() (:575-581); IntervalBuilder.analyzeGraph does the same (lucene/queries, IntervalBuilder.java:216-234). So these in-tree callers, and query parsers that use these QueryBuilder methods unchanged, get the right paths; a subclass that overrides them was not checked. The two downstream match-query parsers that were read also consume each stream at once.
Effect. The held stream silently replays a later path's tokens, or a mix of two paths that is no path of the graph. Which wrong tokens depends on the token order, because token ids follow the order the tokens arrive in. For the repro's order (new, ny, york), a caller that builds clauses from the collected streams would search for ny york and never for new york. Lucene's SynonymGraphFilter emits the synonym first (it adds the original tokens last, SynonymGraphFilter.java:504-519): for "new york" with the synonym ny it emits ny, new, york, and the same collect-then-read pattern gives [new] and [new, york], so such a caller would search for new and new york and never for ny (read at once: [ny] and [new, york]; executed on main, assertions on and off).
Scale. Token graphs with two or more paths can trigger it; three tokens in the repro. No configuration involved.
Likelihood: rare. No public report since 6.5.0 (2017), and every in-tree caller (and the two downstream parsers that were read) consumes each stream at once.

Minimal repro

One JUnit test method on the public API plus the test framework's CannedTokenStream: three tokens, collect the streams, read them, compare the set of paths. Deterministic, single-threaded and independent of iteration order; it fails with assertions on and off.

TestGraphTokenStreamFiniteStringsHeldStreams.java (lucene/core, package org.apache.lucene.util.graph, 1 test)40 lines

package org.apache.lucene.util.graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
import org.apache.lucene.tests.analysis.CannedTokenStream;
import org.apache.lucene.tests.analysis.Token;
import org.apache.lucene.tests.util.LuceneTestCase;

public class TestGraphTokenStreamFiniteStringsHeldStreams extends LuceneTestCase {

  public void testStreamsReadAfterIterating() throws Exception {
    GraphTokenStreamFiniteStrings graph =
        new GraphTokenStreamFiniteStrings(
            new CannedTokenStream(
                new Token("new", 1, 0, 3, 1),
                new Token("ny", 0, 0, 8, 2),
                new Token("york", 1, 4, 8, 1)));
    List<TokenStream> streams = new ArrayList<>();
    graph.getFiniteStrings().forEachRemaining(streams::add);

    Set<List<String>> paths = new HashSet<>();
    for (TokenStream ts : streams) {
      CharTermAttribute term = ts.addAttribute(CharTermAttribute.class);
      List<String> path = new ArrayList<>();
      ts.reset();
      while (ts.incrementToken()) {
        path.add(term.toString());
      }
      ts.end();
      ts.close();
      paths.add(path);
    }
    // expected the graph's two paths {[new, york], [ny]}; actual {[ny, york], [ny]}
    assertEquals(Set.of(List.of("new", "york"), List.of("ny")), paths);
  }
}

Command

cp $REPRO/TestGraphTokenStreamFiniteStringsHeldStreams.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/graph/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.graph.TestGraphTokenStreamFiniteStringsHeldStreams -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: the same failure

Expected: The set of replayed paths is {[new, york], [ny]}, the graph's two paths.
Observed: It is {[ny, york], [ny]}: AssertionError: expected:<[[new, york], [ny]]> but was:<[[ny], [ny, york]]>, with no other error.

All files of this repro: repro/LFV-1117/

More files, environment, full output192 words

TestGraphTokenStreamFiniteStringsHeldStreams (one method, extends LuceneTestCase, package org.apache.lucene.util.graph of the lucene/core tests). Tokens are Token(term, posInc, startOffset, endOffset, posLength): new (1, 0, 3, 1), ny (0, 0, 8, 2), york (1, 4, 8, 1). It collects the streams with forEachRemaining, reads each with reset()/incrementToken()/end()/close(), and asserts that the set of term lists is {[new, york], [ny]}. About 1 s.

The order inside a printed Set.of(...) changes from JVM to JVM, so the expected side may print as [[ny], [new, york]]; the sets are the same. As the regression test, the same method fits in TestGraphTokenStreamFiniteStrings.

Environment

lucene	`main 5adff78bb168 (12.0.0-SNAPSHOT): fails; 9.12.3, 10.5.2, 10.6.0: the same or an equivalent test fails; 6.5.0 to 10.0.0 (7 releases): a core-only form fails; 6.4.2: clean`
jdk	`OpenJDK 25.0.3 (build 25.0.3+9-LTS)`
os	`Linux aarch64 (nothing platform-specific)`

Command (environment)

cp $REPRO/TestGraphTokenStreamFiniteStringsHeldStreams.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/graph/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.graph.TestGraphTokenStreamFiniteStringsHeldStreams -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: the same failure

Observed output

TestGraphTokenStreamFiniteStringsHeldStreams > testStreamsReadAfterIterating FAILED
    java.lang.AssertionError: expected:<[[new, york], [ny]]> but was:<[[ny], [ny, york]]>
        at org.apache.lucene.util.graph.TestGraphTokenStreamFiniteStringsHeldStreams.testStreamsReadAfterIterating(TestGraphTokenStreamFiniteStringsHeldStreams.java:38)

# with -Ptests.asserts=false:
    java.lang.AssertionError: expected:<[[ny], [new, york]]> but was:<[[ny], [ny, york]]>

Why it looks unintended

No javadoc says a returned stream expires; each is a new TokenStream with its own attributes. Comparable iterators document reuse (FiniteStringsIterator.next(), BytesRefIterator.next()).
The 6.4 API copied every path; the 6.5 rewrite to a lazy iterator dropped the copy without discussion.
In the repro the wrong [ny, york] is no path of the graph, and a bare hasNext() triggers it.

The full argument203 words

Contract. The class javadoc (GraphTokenStreamFiniteStrings.java:42-47), both methods (:126 "Get all finite strings from the automaton.", :131) and util/graph/package-info.java state no lifetime rule. The class is public, exported (module-info.java:49) and has no @lucene.internal or @lucene.experimental tag. Each element is a fresh TokenStream with its own cloned attributes (:61). Comparable Lucene iterator APIs document their reuse: FiniteStringsIterator.next() (:97) and BytesRefIterator.next() ("The returned BytesRef may be re-used across calls to next", BytesRefIterator.java:26).
Tests. Lucene's own test of FiniteStringsIterator honours that warning and deep-copies every result before keeping it (TestFiniteStringsIterator.java:181-185). The class's original tests (LUCENE-7603) collected all streams into a List and then read get(0), get(1). No test asserts the sharing; today's TestGraphTokenStreamFiniteStrings always reads each stream at once.
History. LUCENE-7603 (0a5300af6cf on branch_6x, released in 6.4.0; a81ebce8049 on the main line, first released in 7.0.0) added the class with a static getTokenStreams(TokenStream) that built each stream from IntsRef.deepCopyOf(ids). LUCENE-7638 (#8689; 5386116e9a3, released in 6.5.0, and e764d3e0590 on the main line) replaced it with the lazy iterator, whose next() passes current without the copy. Neither the LUCENE-7638 discussion nor its CHANGES entry mentions the copy or a lifetime rule.

The devil's-advocate check136 words

The strongest case for "intended": java.util.Iterator promises no snapshots, the class is a query-parsing helper, and every caller reads each stream before advancing, so the rule is "consume before you advance".

Why it fails: that rule is written nowhere; a bare hasNext(), which callers do not expect to change anything, already corrupts the stream handed out before; the held stream then shows neither its own path nor the iterator's current one (in the repro, [ny, york] is no path of the graph); and the API this replaced copied each path. The devil's-advocate verifier rated the case weak to moderate and rejected it; the cross-model reviewer rated it moderate and judged it outweighed. A maintainer may still read the result as an undocumented cursor-backed view and prefer a javadoc note to the copy (fix option C).

Suggested fix

Recommended Copy the path in next() (fix A)

Copy the path when the iterator hands out a stream: new FiniteStringsTokenStream(IntsRef.deepCopyOf(current)) (one line). It restores the 6.4 per-path copy for one small int[] per path. The repro passes with assertions on and off, and 69 tests of the closest suites pass.

        TokenStream next = new FiniteStringsTokenStream(IntsRef.deepCopyOf(current));

All options and trade-offs3 options · 343 words

Fix A was built and checked through gradle on 5adff78bb168; B is the same copy in another place and was not run; C changes only the javadoc.

Copy the path in next() (fix A) (validated by the checks) (recommended)

In getFiniteStrings(start, end), next() wraps a copy of the iterator's IntsRef (GraphTokenStreamFiniteStrings.java:154), as the 6.4 API did. Each stream then owns its ids, however the iterator is driven.

        TokenStream next = new FiniteStringsTokenStream(IntsRef.deepCopyOf(current));

Trade-offs

One int[] of the path's length per returned stream, next to the cloneAttributes() every stream already does (:61). Callers that read each stream at once, such as QueryBuilder and IntervalBuilder, see the same tokens as before.

What the checks validated

Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on, and -Ptests.asserts=false) and passes with it (both).
With the fix: the repro (1), TestGraphTokenStreamFiniteStrings (15), TestQueryBuilder (26), TestIntervalBuilder (12, lucene/queries) and TestFixedShingleFilter (15, lucene/analysis/common): 69 tests, 0 failures. checkGoogleJavaFormat on core passes. The full core suite was not run, and only OpenJDK 25.0.3 on Linux aarch64 was used.
Earlier: the hunt's shadow-class runs of the same change pass the repro with assertions on and off; the cross-model reviewer's run passes its own test and the 15 upstream tests.

Copy in the FiniteStringsTokenStream constructor (not run)

this.ids = IntsRef.deepCopyOf(ids) at :63, with offset and end taken from the copy. Same effect and cost as A, and it also covers any future use of the inner class.

Trade-offs

Same allocation as A.

What the checks validated

Not run.

Document the lifetime instead (not run)

State on both getFiniteStrings methods that each returned TokenStream is valid only until the next hasNext() or next() call.

Trade-offs

No cost, but it keeps the trap, makes even a bare hasNext() a documented hazard (unusual for an Iterator), and keeps the impossible mixed path as the failure mode. The alternative a maintainer may prefer, not the main proposal.

What the checks validated

Not executed (documentation only).

Downstream note

For the repro's token order, a downstream query parser that collected the paths before building its clauses would search for ny york instead of new york; with SynonymGraphFilter's order (ny first), for new instead of ny. Either way it would silently miss matches. The downstream match-query parsers that were checked read each stream at once.

How it was found

A proof-obligation audit of GraphTokenStreamFiniteStrings' contract: every stream that getFiniteStrings() returns must replay its own path however the iterator is driven. That obligation fails against FiniteStringsIterator.next()'s documented buffer reuse, which the wrapper passes on without a copy; a public-API JUnit test then witnessed the wrong tokens.

The method in full109 words

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

The finder checked getFiniteStrings against the obligation that each returned element replays its own path whatever the caller does with the iterator, and found that next() (:154) wraps the IntsRef that FiniteStringsIterator.next() documents as valid only until its next call.
The finder then wrote a public-API JUnit test (paths [A, C] and [B]; the first stream gives [B, C]) and the one-line copy that makes it pass.
An independent reproducer, an executed cross-model review, a devil's-advocate verifier and an adjudication reproduced it with their own tests ("Prior reports, history and checks").

Prior reports, history and checks

Prior reports

No matching prior report found in apache/lucene issues, PRs and commits (incl. the JIRA archive), the mailing lists, downstream trackers or the web (searched 2026-11-02). Nearest: #9959 (LUCENE-8916), the same inner class with a different defect, and #8689 (LUCENE-7638), where the copy was dropped.

Searches3 searches

No matching public report was found in the documented searches. Nearest items, none a report of this bug: #9959 (LUCENE-8916: the streams' attribute classes; its fix left the iterator as it was), #8689 (LUCENE-7638: the change that dropped the copy, never discussed there), #8654 (LUCENE-7603: added the class, with the copy), #7425 (LUCENE-6365: created FiniteStringsIterator and its documented reuse), #16239 (open PR, articulationPoints only) and a 2021 java-user@ thread about a different assertion in this class. Limits: keyword search, 50 results per GitHub query; private reports are not visible.

What was searched, when, and what turned up
Where	When	How	Found
GitHub issues, PRs and commits (apache/lucene incl. the migrated JIRA archive)	2026-11-02	a scripted prior-report search (16 issue and PR queries, 3 commit queries, 4 JIRA-archive queries) and about 25 manual searches: class and method names, IntsRef reuse, shared or reused buffers, activity since 2026-10-31	no report; #9959 and #8689 are the nearest
Open and recent PRs	2026-11-02	the changed files of the 31 apache/lucene PRs updated since 2026-10-31, and every open PR that names the class	only #16239, which changes articulationPoints only
Mailing lists, downstream, web	2026-11-02	20 queries over dev@, java-user@, issues@ and commits@; apache/lucene-solr, apache/solr, apache/lucenenet, Elasticsearch and OpenSearch trackers; 6 web queries; GitHub code search for the copying call	nothing about this bug

History

Introduced by LUCENE-7638 (5386116e9a3, 2017-02-07) and first released in 6.5.0; 6.4.2, whose API copied each path, is clean. Every release run since then fails, through 10.6.0 and main. Not fixed upstream.

Versions tested5 rows

Introduced by LUCENE-7638 "Query parsers now analyze the token graph for articulation points (or cut vertices) ..." (Jim Ferenczi, author date 2017-02-07; a JIRA patch, no GitHub PR; migrated as #8689): 5386116e9a3 on branch_6x, first released in 6.5.0, and e764d3e0590 on the main line, first released in 7.0.0. It replaced the 6.4 API of LUCENE-7603 (Matt Weber; 0a5300af6cf on branch_6x, released in 6.4.0, and a81ebce8049 on the main line, first released in 7.0.0), which built each stream from IntsRef.deepCopyOf(ids); whether the copy was dropped on purpose is not recorded. git log --all -S 'IntsRef.deepCopyOf(ids)' matches only the two LUCENE-7603 commits (added) and the two LUCENE-7638 commits (removed).

By reading, all 75 release tags from 6.5.0 to 10.6.0 in the history clone have the uncopied next() (the clone has no 8.9-8.11 tags; 8.11.4 was run from its release jar). The newest commit on the file is f394c9418e1 (2024-05-27), already in 5adff78bb168. 6.5.0, 6.6.6, 7.0.0, 7.7.3, 8.11.4, 9.0.0 and 10.0.0 ran only a core-only main() form with the same graph and oracle; the JUnit repro needs org.apache.lucene.tests.*, so it compiles only on 9.0 and later.

Versions and branches executed, with results
Version or commit	Verdict	Result
main `5adff78bb168`	affected	gradle: fails with assertions on and off; passes with fix A
9.12.3, 10.5.2, 10.6.0	affected	the JUnit test or an equivalent fails: `[ny, york]` instead of `[new, york]`
6.5.0, 6.6.6, 7.0.0, 7.7.3, 8.11.4, 9.0.0, 10.0.0	core-only form	the same wrong output
6.5.0 with the copy restored	shadow class	passes
6.4.2	not affected	its only API, `getTokenStreams`, copies each path: passes with all streams collected first

Independent checks

A finder, an independent reproducer, an executed cross-model review (OpenAI GPT-5.6, real, high), a devil's-advocate verifier, an adjudication, an audit and a final repro check reproduced it. This doc's gradle runs reproduced it on main and validated fix A.

Checks and verdicts239 words

The cross-model review ran on the older main ea57360912ed, where GraphTokenStreamFiniteStrings.java and FiniteStringsIterator.java are byte-identical to 5adff78bb168; its test was then re-run on 5adff78bb168 and fails with assertions on and off. Every other check ran on 5adff78bb168 or release jars.

Each independent check and its verdict
Check	Verdict	What it found
finder	reproduced	Own test (paths `[A, C]`, `[B]`) fails on main (assertions on and off), 10.6.0 and 9.12.3: `expected:<[A, C]> but was:<[B, C]>`; the copy fixes it.
independent reproducer	real	Own order-independent test fails on main (on, off), 10.6.0, 10.5.2 and 9.12.3; its read-at-once control passes; the copy fixes it.
cross-model review, refute lens (OpenAI GPT-5.6, executed)	real (high)	Own test with a custom TokenStream (paths `[left, right]`, `[bridge]`): `[bridge, right]` with assertions on and off and several seeds; control passes; the copy passes it and the 15 upstream tests.
devil's-advocate verifier	real, Low	Two `next()` calls or a bare `hasNext()` already corrupt the earlier stream; the "consume before advancing" case is rejected.
adjudication, separate re-runs, audit and final repro check	confirmed, Low	Re-runs on main fail with assertions on and off and pass with the copy; one minimal deterministic test; first affected release corrected from 6.4.0 to 6.5.0.
this doc's fix check	reproduced; fix A validated	Gradle without the fix fails (on, off); with it the repro and 4 closest suites pass, 69 tests.

Diagram file

The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.

PNG 424 KB

Sources and provenance

Finding record, Lucene and upstream sources, repro files and diagram notes1,409 words

Finding record

LFV-1117, snapshot of 2026-11-06

Registry title: GraphTokenStreamFiniteStrings.getFiniteStrings returns TokenStreams that all read the iterator's one reused IntsRef, so a stream read after the next hasNext() or next() call replays another path's tokens, or a mix that is no path of the graph (regression of LUCENE-7638, since 6.5.0)
Area: core / util.graph (GraphTokenStreamFiniteStrings.getFiniteStrings: per-path TokenStreams over FiniteStringsIterator's reused IntsRef)
Priority: Low, rank 877: The public token-graph helper GraphTokenStreamFiniteStrings silently replays the wrong tokens, even a mix that is no path of the graph, in every release since 6.5.0, but only for application code that calls getFiniteStrings() itself and holds a stream across the next hasNext() or next(). Lucene's own query builders read each stream at once and are not affected, so only direct callers can hit it.
Impact class: minor
Impact note: Only code that calls the public GraphTokenStreamFiniteStrings.getFiniteStrings() or getFiniteStrings(start, end) itself and keeps a returned TokenStream unread across the next hasNext() or next() call (for example collects the streams into a list before reading them) is hit: the held stream then silently replays a later path's tokens, or a mix of two paths that is no path of the graph, with -ea and -da [exec]; Lucene's own callers (QueryBuilder.analyzeGraphBoolean and analyzeGraphPhrase, IntervalBuilder.analyzeGraph) read each stream before advancing, so queries built by Lucene's query builders are not affected [read]; any legal token graph with two or more paths, ordinary scale, every release from 6.5.0 through 10.6.0 and main.
Summary: You build a GraphTokenStreamFiniteStrings over the tokens new, ny (a synonym spanning both positions) and york, whose paths are [new, york] and [ny], collect both TokenStreams from getFiniteStrings() into a list, and then read them. You expect each stream to replay its own path, as the original 6.4 API (which copied each path) did. You get [ny, york] and [ny], with no error: every stream reads the iterator's one reused IntsRef, which hasNext() overwrites with the next path, so the first stream mixes the second path's first token with its own leftover second token.
Introduced: 5386116e9a3b54db4674b21e39a41cc4d43553f8 (branch_6x, the copy that shipped first, in 6.5.0) and main-line commit e764d3e0590e998676a18f2b11364cecced4a8ad (first released in 7.0.0), both 'LUCENE-7638: Query parsers now analyze the token graph for articulation points (or cut vertices) ...' (issue 'Optimize graph query produced by QueryBuilder', migrated as apache/lucene#8689; a JIRA patch, no GitHub PR; author Jim Ferenczi, GitHub jimczi). It replaced the static getTokenStreams(TokenStream), which built every stream from IntsRef.deepCopyOf(ids) (LUCENE-7603, Matt Weber, GitHub mattweber: 0a5300af6cf on branch_6x, released in 6.4.0, and a81ebce8049 on the main line, first released in 7.0.0), with the lazy getFiniteStrings() iterator, whose next() wraps FiniteStringsIterator's reused IntsRef without that copy; unchanged since [read: git blame -w of GraphTokenStreamFiniteStrings.java:135-157; git log --all -S 'IntsRef.deepCopyOf(ids)' matches only the two LUCENE-7603 commits (added) and the two LUCENE-7638 commits (removed); exec: 6.5.0 fails, 6.5.0 with the copy restored in a shadow class passes] (2017-02-07 (author date 11:27:59 +0100 of both e764d3e0590 and 5386116e9a3; committed the same day))
First affected version: 6.5.0 [exec: the collect-then-read check fails on 6.5.0; on 6.4.2 the same graph through that release's only API, getTokenStreams(TokenStream), with all streams collected before any is read, passes; the class does not exist before 6.4.0], so this is a regression of LUCENE-7638
Affected versions: every release from 6.5.0 through 10.6.0 (released 2026-10-29, 4ae946e5a9b) and main 5adff78bb168 (12.0.0-SNAPSHOT). Executed, all failing with the same wrong output: the one-test JUnit on main (-ea and -da), 10.6.0, 10.5.2 and 9.12.3 (-ea), the finder's test on 10.6.0 (-ea and -da) and 9.12.3 (-ea), and a core-only main() form with the same graph and oracle on 10.0.0, 9.0.0, 8.11.4, 7.7.3, 7.0.0, 6.6.6 and 6.5.0 (-ea); 6.4.2 passes [exec]. By code identity, the 75 release tags from 6.5.0 to 10.6.0 in the history clone have the uncopied next() (the clone has no 8.9-8.11 tags; 8.11.4 was executed) [read]. Not new in 10.6 (10.5.2 fails). Not fixed upstream: the newest commit on GraphTokenStreamFiniteStrings.java is f394c9418e1 (author date 2024-05-27), already in 5adff78bb168, and the only open PR that touches the file (#16239) changes articulationPoints only [read through the GitHub API, 2026-11-02]. Executed on Linux aarch64 with JDK 25.0.3 only.
Status: documented (brief, checks and a per-finding doc exist)
Verification: Confirmed by AI-run checks: an independent repro, a cross-model review that agreed, an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
Found by: semi-formal: proof-obligation audit
Upstream and prior reports: none found (2026-11-02, on top of the finder's, the independent reproduction's, the intended-behaviour check's and the adjudication's GitHub searches; rechecked the same day): a scripted prior-report search over 16 GitHub issue and PR queries on apache/lucene, 3 commit queries, 2 downstream-repository queries, 20 mailing-list queries (dev@, java-user@, issues@, commits@), 4 JIRA-archive queries and 6 web queries (155 distinct hits), plus about 25 manual GitHub searches on apache/lucene, apache/lucene-solr, apache/solr, apache/lucenenet, Elasticsearch and OpenSearch, the changed files of the 31 apache/lucene PRs updated since 2026-10-31 (none touches GraphTokenStreamFiniteStrings, FiniteStringsIterator, QueryBuilder or IntervalBuilder), GitHub code search for the copying call, and the full LUCENE-7638 discussion (#8689): no report of the streams sharing a buffer or of a stream replaying another path. Same-day recheck: GitHub search on apache/lucene for GraphTokenStreamFiniteStrings issues updated since 2026-11-01 (0), PRs naming getFiniteStrings (0) or GraphTokenStreamFiniteStrings (only #16239, open, articulationPoints only, and #12249, merged, recursion depth), 'finite strings IntsRef reused' (0); newest commit on the file still f394c9418e1. Related, not reports: #9959 / LUCENE-8916 (same inner class FiniteStringsTokenStream, but about attribute classes; its fix lucene-solr#786 left the iterator unchanged), #8689 / LUCENE-7638 (the change that dropped the copy; its discussion never mentions it), #8654 / LUCENE-7603 (added the class, with the copy), #7425 / LUCENE-6365 (FiniteStringsIterator and its documented IntsRef reuse), and a 2021 java-user@ thread on a different assertion in this class.
Lucene commit tested: main 5adff78bb168 (2026-11-02) through gradle on 2026-11-03 in a scratch worktree, seed DEADBEEF, assertions on and off, without and with fix A (the repro, 4 closest suites, checkGoogleJavaFormat). The hunt ran the same or an equivalent JUnit test on 9.12.3, 10.5.2 and 10.6.0 (fail), and a core-only main() form with the same graph and oracle on 6.5.0, 6.6.6, 7.0.0, 7.7.3, 8.11.4, 9.0.0 and 10.0.0 (fail), on 6.5.0 with the copy restored (pass) and, through the 6.4 API, on 6.4.2 (pass). A probe with Lucene's SynonymGraphFilter ran on main with assertions on and off. Only Linux aarch64 with OpenJDK 25.0.3 was run.

Lucene and upstream sources

Finding record: lucene/core/src/java/org/apache/lucene/util/graph/GraphTokenStreamFiniteStrings.java:42-47 (at 5adff78bb168) (class javadoc; public final, no @lucene.internal or @lucene.experimental), :55-80 (FiniteStringsTokenStream keeps the IntsRef object, :63, fixes end once, :65, and reads ids.ints[offset] on every incrementToken, :72), :126-132 (getFiniteStrings javadoc 'Get all finite strings from the automaton.', no lifetime rule), :139-147 (hasNext() pre-fetches current = it.next()), :150-157 (next() wraps current without a copy at :154: fix site)
lucene/core/src/java/org/apache/lucene/util/automaton/FiniteStringsIterator.java:96-101 (at 5adff78bb168) (next(): 'The return value is just valid until the next call of this method!'), :132 and :144 (returns string.get(), the builder's one IntsRef)
lucene/core/src/java/org/apache/lucene/util/QueryBuilder.java:520-538 (at 5adff78bb168) (analyzeGraphBoolean builds each side-path query inside the lazy Iterator<Query>.next()), :575-581 (analyzeGraphPhrase reads each stream before the next hasNext())
lucene/queries/src/java/org/apache/lucene/queries/intervals/IntervalBuilder.java:216-234 (at 5adff78bb168) (analyzeGraph reads each stream before advancing)
https://github.com/apache/lucene/issues/8689 (LUCENE-7638), https://github.com/apache/lucene/issues/8654 (LUCENE-7603), https://github.com/apache/lucene/issues/9959 (LUCENE-8916), https://github.com/apache/lucene/pull/16239 (open, articulationPoints only), read 2026-11-02
The finding in 30 seconds: lucene/core/src/java/org/apache/lucene/util/graph/GraphTokenStreamFiniteStrings.java:55-80 (at 5adff78bb168) (FiniteStringsTokenStream: :63 keeps the IntsRef, :65 end fixed once, :72 reads ids.ints[offset]), :126-158 (getFiniteStrings; :139-147 hasNext pre-fetch; :154 next without a copy)
lucene/core/src/java/org/apache/lucene/util/automaton/FiniteStringsIterator.java:96-101 (at 5adff78bb168) (next() javadoc), :102-105 (the empty string returns EMPTY), :132, :144 (returns string.get())
Who is affected: lucene/core/src/java/org/apache/lucene/util/QueryBuilder.java:520-538, (at 5adff78bb168) :575-581, :618-622
lucene/queries/src/java/org/apache/lucene/queries/intervals/IntervalBuilder.java:216-234 (at 5adff78bb168)
lucene/analysis/common/src/java/org/apache/lucene/analysis/synonym/SynonymGraphFilter.java:504-519 (at 5adff78bb168) ("We must do the original tokens last")
Why it looks unintended: lucene/core/src/java/org/apache/lucene/util/graph/GraphTokenStreamFiniteStrings.java:42-47, (at 5adff78bb168) :61, :126, :131
lucene/core/src/java/org/apache/lucene/util/graph/package-info.java; (at 5adff78bb168) lucene/core/src/java/module-info.java:49
lucene/core/src/java/org/apache/lucene/util/automaton/FiniteStringsIterator.java:97; (at 5adff78bb168) lucene/core/src/java/org/apache/lucene/util/BytesRefIterator.java:26 ("The returned BytesRef may be re-used across calls to next")
lucene/core/src/test/org/apache/lucene/util/automaton/TestFiniteStringsIterator.java:181-185; (at 5adff78bb168) lucene/core/src/test/org/apache/lucene/util/graph/TestGraphTokenStreamFiniteStrings.java
https://github.com/apache/lucene/issues/8689 (LUCENE-7638 discussion)
Suggested fix: lucene/core/src/java/org/apache/lucene/util/graph/GraphTokenStreamFiniteStrings.java:61, (at 5adff78bb168) :63-65, :154
Prior reports: https://github.com/apache/lucene/issues/9959, https://github.com/apache/lucene/issues/8689, https://github.com/apache/lucene/issues/8654, https://github.com/apache/lucene/pull/16239
Diagrams: lucene/core/src/java/org/apache/lucene/util/graph/GraphTokenStreamFiniteStrings.java:55-80, (at 5adff78bb168) :139-157
lucene/core/src/java/org/apache/lucene/util/automaton/FiniteStringsIterator.java:96-101 (at 5adff78bb168)

Other statements trace to the hunt's working files (models, logs, reviews and briefs), which are not published.

Repro files

TestGraphTokenStreamFiniteStringsHeldStreams.java (lucene/core, package org.apache.lucene.util.graph, 1 test): repro/LFV-1117/TestGraphTokenStreamFiniteStringsHeldStreams.java (40 lines)

About the diagrams

The diagram illustrates the repro's graph and the buffer state after each iterator call, as a probe on main prints it (GraphTokenStreamFiniteStrings.java:139-157, FiniteStringsIterator.java:96-101).

assets/LFV-1117/bug.png (424 KB)

Built 2026-11-06 from the hunt's record of this finding and its doc file. Lucene main under test in this hunt: ea57360912ed. Every listed finding was re-run on Lucene main e1faeba08bde on 2026-11-02.

The finding in 30 seconds

Background: token graphs and their paths

The finding, step by step

Who is affected

The mechanism (main 5adff78bb168, lucene/core/src/java/org/apache/lucene/)

Which call patterns break (all executed on main)

Minimal repro

Environment

Observed output

Why it looks unintended

Suggested fix

Copy the path in next() (fix A) (validated by the checks) (recommended)

Copy in the FiniteStringsTokenStream constructor (not run)

Document the lifetime instead (not run)

Downstream note

How it was found

Prior reports, history and checks

Prior reports

History

Independent checks

Diagram file

Sources and provenance

Finding record

Lucene and upstream sources

Repro files

About the diagrams

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/`)