ConcatenateGraphFilter without a separator (and CompletionAnalyzer with preserveSep=false) silently drops a path around a position hole

The finding in 30 seconds

Without a separator, the filter turns the arcs between tokens into empty moves (hole arcs always are), which Automaton.addEpsilon implements by copying the next state's exits. Here that state is still being built and unsorted (w, t). The copy's first write sorts it in place, so the copy reads w twice and never t.

Background: concatenating a token graph

ConcatenateGraphFilter glues the tokens of every path through a token graph into one output token. The document suggester (CompletionAnalyzer, SuggestField) uses it to index suggestions. With preserveSep=false, or a null tokenSeparator, tokens are glued with nothing in between.
A multi-word synonym adds a token that spans several positions (thewho over "the who"). A stop filter that then removes "the" leaves a hole: a position where no token ends.
Internally the filter builds an automaton with a separator arc between tokens and a hole arc over the gap. The hole arc always becomes an empty (epsilon) move, and with no separator the separator arc does too; an empty move is done by copying the target state's outgoing arcs onto the source state.

Diagram of the bug: the tokens play, thewho (spanning two positions) and who for "play the who", and the no-separator copy step in which the state after play holds the exits w (via the hole) and t (thewho); the copy reads w, the write sorts the state to t, w, and the copy reads w again, so the output is [playwho] instead of [playthewho, playwho]. — The token graph for "play the who" and the copy step that loses `t`: the state after `play` holds `w` then `t`, the copy's first write sorts it, and the copy reads `w` twice. Select the still to open it at full size. Generated with AI, checked against the code.

The finding, step by step

Analyze "play the who" with the synonym "the who" => "thewho" and the stop word "the". You get 3 tokens: play, thewho (spanning 2 positions) and who, so the token graph has 2 paths.
Concatenate them without a separator: new ConcatenateGraphFilter(in, null, true, 100), or CompletionAnalyzer with preserveSep=false. You expect 2 tokens, one per path: playthewho and playwho.
You get 1 token, playwho, and no error. A suggestion indexed for "play the who" is found for "playw" but gets 0 hits for "playth". With assertions on (-ea) the filter throws an AssertionError instead.
Why: the end of play must receive a copy of the next state's 2 exits, stored as w (via the hole) then t (thewho). The copy reads w; writing it makes Automaton finish that state, which sorts it to t, w. The second read sees w again, so t is never copied.
With a separator ('-', '|' and the default U+001F were run on this input), or when the hole branch's letter sorts first, both paths survive. Releases from 5.3.0 (CompletionAnalyzer) and 7.4.0 (ConcatenateGraphFilter) through 10.6.0 have it.

Who is affected

Only the opt-in no-separator mode: ConcatenateGraphFilter with a null separator (factory tokenSeparator="") and CompletionAnalyzer or the document suggester with preserveSep=false. It also needs a hole under a multi-position token, from a multi-word synonym containing a stop word, and an unlucky letter order. One value suffices; production is silent, test suites see an AssertionError.

Mechanism, terms and numbers685 words

ConcatenateGraphFilter promises one output token "for every path through the token stream (which is a graph)", and its tokenSeparator may be null to concatenate without separators; CompletionAnalyzer with preserveSep=false uses exactly that mode. For the token graph play | thewho (2 positions) | who, which a multi-word synonym ("the who" => "thewho") followed by a stop filter for "the" produces from "play the who", the filter emits only playwho: playthewho is lost silently with assertions off, and with -ea the same input throws an AssertionError in Automaton.getNextTransition. Through the document suggester, a SuggestField "play the who" gets 0 hits for the prefix "playth".

The cause is Automaton.addEpsilon(source, dest): it reads dest's transition count once and walks dest's transitions with a cursor while calling addTransition(source, ..). When dest is the state still being built, that first addTransition finishes dest, which sorts and merges its transitions in place, so the cursor reads one transition twice and never reads another. ConcatenateGraphFilter.replaceSep fills its automaton in reverse topological order and turns every separator and hole arc into addEpsilon, so dest is often that open state. It needs the opt-in no-separator mode, a hole under a multi-position token, and a hole-branch letter that sorts after the spanning token's letter. The root cause dates from 4.10.0 (LUCENE-5752); it is visible on stock jars from 5.3.0 (CompletionAnalyzer) and 7.4.0 (ConcatenateGraphFilter) through 10.6.0 and main. A five-line fix in addEpsilon (finish an open dest before copying) passes the repro and the automaton, filter and document-suggester suites.

The mechanism (main `5adff78bb168`)

ConcatenateGraphFilter.toAutomaton builds the token automaton with TokenStreamToAutomaton, then calls replaceSep and determinizes (ConcatenateGraphFilter.java:244-250). Between tokens there is a POS_SEP arc; over a position where no token ends, TokenStreamToAutomaton.addHoles adds a HOLE arc (TokenStreamToAutomaton.java:271-299).
replaceSep fills a plain Automaton, not an Automaton.Builder, in reverse topological order (ConcatenateGraphFilter.java:285-301). With a null separator each POS_SEP arc becomes addEpsilon(state, t.dest) (:311); every HOLE arc becomes addEpsilon too (:323). Because of the visit order, t.dest is often the state just filled, which is still the automaton's open state.
Fix site. Automaton.addEpsilon reads count = initTransition(dest, t) once (Automaton.java:191) and then loops getNextTransition(t) and addTransition(source, ..) (:192-195).
addTransition to a new source first finishes the open state (Automaton.java:162-165): finishCurrentState sorts its transitions, merges adjacent ones in place and sorts again (:239-311).
So when dest is open and unsorted, the first addTransition(source, ..) rewrites dest's block under the cursor, and the remaining reads see the rewritten block. With -ea, the sortedness assert in getNextTransition fires (:493; transitionSorted returns false for two equal transitions, :531-532).

The trace for the repro (executed, same loop as `replaceSep`)

State 1 is the end of play (SEP->5). State 5 has HOLE->13 and 't'->7; the hole branch continues 13: SEP->12, 12: 'w'->14. The visit order ends ... 13 ... 5, 1, ....

Visiting 5, the new automaton first copies 'w'->14 (through the hole) and then adds 't'->7: block [w, t], unsorted, still open.
Visiting 1, addEpsilon(1, 5) reads 'w'->14 and writes it to state 1. That write finishes state 5, which becomes [t, w]. The second read is 'w'->14 again.
State 1 ends with only 'w'->14: the play + thewho path is gone, and the output is [playwho].

Core-only form: Automaton a = new Automaton(); a.createState(); a.createState(); a.createState(); a.addTransition(1, 2, 'b'); a.addTransition(1, 0, 'a'); a.addEpsilon(0, 1); a.finishState(); leaves state 0 with only b->2 (-da, expected:<2> but was:<1>) or asserts (-ea).

Why the letter order matters

The hole arc sorts before any letter, so the hole branch's exit is copied into state 5 first and the spanning token's letter is added after it. If the hole branch's letter sorts first (a before w), the block is already sorted, finishing does not move anything, and both paths survive: [playaaa, playwhoa] for play | whoa (2 positions) | aaa.

Exposure and likelihood257 words

Who is hit. ConcatenateGraphFilter with a null tokenSeparator (ConcatenateGraphFilter.java:101-102), its factory with tokenSeparator="" (ConcatenateGraphFilterFactory.java:28-30, :85-86), and CompletionAnalyzer with preserveSep=false, whose stream wraps new ConcatenateGraphFilter(input, preserveSep, ..) (CompletionTokenStream.java:54-61; preserveSep=false maps to a null separator, ConcatenateGraphFilter.java:140). At index time a suggestion entry loses a path. By reading, PrefixCompletionQuery and FuzzyCompletionQuery analyze the prefix through the same stream, so a query-side path can be lost too (not run).
Default vs opt-in. Not default: DEFAULT_TOKEN_SEPARATOR = SEP_LABEL and DEFAULT_PRESERVE_SEP = true (ConcatenateGraphFilter.java:62-63). For this graph a separator keeps both paths ('-', U+001F and '|' were run); hole arcs still become addEpsilon with a separator, so that is shown for this input only. AnalyzingSuggester and FuzzySuggester are not affected: they build on Automaton.Builder since 5.0.0.
What it takes. A position hole under a multi-position token (for example a multi-word synonym that contains a stop word, followed by a stop filter), and a hole-branch first letter that sorts after the spanning token's first letter. preservePositionIncrements does not matter: false loses the path the same way.
Scale and visibility. One value with three tokens; no scale needed. With assertions off a suggestion quietly does not appear; with -ea (test suites) indexing throws an AssertionError. After a fix, completion entries already indexed need reindexing to gain the lost path.
Likelihood: rare. All three conditions must meet, the effect is easy to overlook, and no public report was found (searched 2026-11-02), although the suggester symptom is on stock jars from 5.3.0 (2015).

Minimal repro

One BaseTokenStreamTestCase test on the public API: three canned tokens, play (1, 1), thewho (1, 2) and who (1, 1), into new ConcatenateGraphFilter(in, null, true, 100), expecting playthewho and playwho. Single thread, deterministic; run it with assertions off for the silent form.

TestConcatenateGraphFilterHoleWithoutSeparator.java (lucene/analysis/common, public API)39 lines

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.analysis.miscellaneous;

import org.apache.lucene.tests.analysis.BaseTokenStreamTestCase;
import org.apache.lucene.tests.analysis.CannedTokenStream;
import org.apache.lucene.tests.analysis.Token;

public class TestConcatenateGraphFilterHoleWithoutSeparator extends BaseTokenStreamTestCase {

  public void testHoleUnderLongTokenWithoutSeparator() throws Exception {
    // expected: "playthewho" and "playwho"; actual: only "playwho" (AssertionError with -ea)
    CannedTokenStream in =
        new CannedTokenStream(
            new Token("play", 1, 0, 4, 1),
            new Token("thewho", 1, 5, 12, 2),
            new Token("who", 1, 9, 12, 1));
    assertTokenStreamContents(
        new ConcatenateGraphFilter(in, null, true, 100),
        new String[] {"playthewho", "playwho"},
        null,
        null,
        new int[] {1, 0});
  }
}

Command

cp $REPRO/TestConcatenateGraphFilterHoleWithoutSeparator.java $LUCENE/lucene/analysis/common/src/test/org/apache/lucene/analysis/miscellaneous/
cd $LUCENE && ./gradlew :lucene:analysis:common:test --tests TestConcatenateGraphFilterHoleWithoutSeparator -Ptests.seed=DEADBEEF -Ptests.asserts=false
# -Ptests.asserts=true gives the AssertionError form

Expected: two tokens: playthewho, then playwho.
Observed: assertions off: one token, playwho (term 0 expected:<play[the]who> but was:<play[]who>); assertions on: AssertionError at Automaton.getNextTransition(Automaton.java:493).

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

More files, environment, full output196 words

The token graph is exactly what WhitespaceTokenizer + SynonymGraphFilter ("the who" => "thewho", keep original) + StopFilter ("the") produce for "play the who"; a canned stream keeps the test free of the synonym and stop machinery. Dropping the leading play token makes the test pass, so three tokens is the smallest input shown to fail. The test has no randomness; it failed under every seed it was run with. If the fix is accepted, this same test is the regression test; it passes checkGoogleJavaFormat.

Environment

lucene	`main 5adff78bb168 (12.0.0-SNAPSHOT); also fails on the 10.6.0, 10.5.2 and 9.12.3 release jars`
jdk	`OpenJDK 25.0.3 (build 25.0.3+9-LTS)`
os	`Linux, aarch64 (only this platform was run)`

Command (environment)

cp $REPRO/TestConcatenateGraphFilterHoleWithoutSeparator.java $LUCENE/lucene/analysis/common/src/test/org/apache/lucene/analysis/miscellaneous/
cd $LUCENE && ./gradlew :lucene:analysis:common:test --tests TestConcatenateGraphFilterHoleWithoutSeparator -Ptests.seed=DEADBEEF -Ptests.asserts=false
# -Ptests.asserts=true gives the AssertionError form

Observed output

-Ptests.asserts=false (main 5adff78bb168):
TestConcatenateGraphFilterHoleWithoutSeparator > testHoleUnderLongTokenWithoutSeparator FAILED
    org.junit.ComparisonFailure: term 0 expected:<play[the]who> but was:<play[]who>
:lucene:analysis:common:test (FAILURE): 1 test, 1  failure

-Ptests.asserts=true (main 5adff78bb168; module prefixes and test-framework frames trimmed):
TestConcatenateGraphFilterHoleWithoutSeparator > testHoleUnderLongTokenWithoutSeparator FAILED
    java.lang.AssertionError
        at org.apache.lucene.util.automaton.Automaton.getNextTransition(Automaton.java:493)
        at org.apache.lucene.util.automaton.Automaton.addEpsilon(Automaton.java:193)
        at org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter.replaceSep(ConcatenateGraphFilter.java:311)
        at org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter.toAutomaton(ConcatenateGraphFilter.java:248)
        at org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter.toAutomaton(ConcatenateGraphFilter.java:222)
        at org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter.incrementToken(ConcatenateGraphFilter.java:164)
:lucene:analysis:common:test (FAILURE): 1 test, 1  failure

with fix A applied: PASS, assertions on and off

Why it looks unintended

The class promises "one output token for every path through the token stream (which is a graph)" and documents a null separator.
addEpsilon only requires that dest "already have all transitions added", which holds here.
The same graph with separator '-' keeps both paths, and the same algorithm on Automaton.Builder gives [playthewho, playwho].

The full argument186 words

Contracts. "Concatenates/Joins every incoming token with a separator into one output token for every path through the token stream (which is a graph)" (ConcatenateGraphFilter.java:40-41). tokenSeparator: "Can be null, in this case tokens will be concatenated without any separators" (:101-102). addEpsilon: "Dest state must already have all transitions added because this method simply copies those same transitions over to source" (Automaton.java:185-188). State 5 has all its transitions when it is copied.
Differentials. With separator '-': [play--who, play-thewho]; with null: [playwho]; the same replaceSep algorithm on Automaton.Builder: [playthewho, playwho]. Dropping separators should not drop a path.
Tests. TestConcatenateGraphFilter.testWithNoPreserveSep covers no-separator input without holes (:45-52); testWithStopword covers holes only with a separator (:108-131). Upstream tests treat a hole under a multi-position token as legal input (TestGraphTokenizers.testSynOverHole, TestFlattenGraphFilter.testHoleUnderSyn).
History. LUCENE-5963 (#7025, 5.0.0) moved only AnalyzingSuggester.replaceSep to Automaton.Builder, for allocation reasons. Nobody discussed lossy no-separator output there, in LUCENE-6339 (#7400), or in LUCENE-9018 (#10061, which made the separator configurable, null meaning none; the epsilon branch dates from LUCENE-6339 / LUCENE-8332).

The devil's-advocate check140 words

The strongest "intended" case: the Automaton class javadoc says each state "must have all of its transitions added at once" and that a state is finished once you start adding transitions to another state (Automaton.java:36-41). One could read addEpsilon as requiring a finished dest, which would make replaceSep's call a misuse.

Why it fails: addEpsilon's own precondition is "all transitions added", which holds. Under the strict reading the misusing caller is Lucene's own ConcatenateGraphFilter, so the user-visible loss stands and only the fix site is in question. A "lossy by design" reading fails too: nothing documents it, and whether a path survives depends on the letters (swapping them keeps both paths). The intended-behaviour check and the adjudication rejected the intended-behaviour argument, and an independent reviewer from another model family (OpenAI GPT-5.6) rated it weak.

Suggested fix

Recommended A. Finish an open dest at the top of addEpsilon

In Automaton.addEpsilon, finish dest first when it is the state still being built (if (curState == dest && source != dest) finishState();, five lines). The repro then passes with assertions on and off, and so do the automaton (238 tests), ConcatenateGraphFilter (19) and document-suggester (58) suites.

  public void addEpsilon(int source, int dest) {
+    if (curState == dest && source != dest) {
+      // dest is still open: finish it now, so that adding to source cannot rewrite (sort and
+      // reduce) dest's transitions while they are being copied
+      finishState();
+    }
     Transition t = new Transition();
     int count = initTransition(dest, t);

All options and trade-offs3 options · 412 words

Three options; A was validated in a scratch worktree of 5adff78bb168 with gradle.

A. Finish an open dest at the top of addEpsilon (validated by the checks) (recommended)

Before copying, finish dest if it is the open state, so that adding to source cannot sort or merge dest's transitions mid-copy.

  public void addEpsilon(int source, int dest) {
+    if (curState == dest && source != dest) {
+      // dest is still open: finish it now, so that adding to source cannot rewrite (sort and
+      // reduce) dest's transitions while they are being copied
+      finishState();
+    }
     Transition t = new Transition();
     int count = initTransition(dest, t);

Trade-offs

Five lines in core; handles the open-dest case inside addEpsilon, so current callers need no change; no change when dest is already finished. It only moves the finishing of dest earlier: the old code also finished dest on the first addTransition(source, ..), so a later addTransition(dest, ..) threw "already had transitions added" before and still does.

What the checks validated

Stock: the repro fails with assertions on and off.
With A: the repro, TestConcatenateGraphFilter and TestConcatenateGraphFilterFactory pass (19 tests, assertions on); the repro passes with assertions off; :lucene:core:test --tests 'org.apache.lucene.util.automaton.*' --tests TestTokenStreamToAutomaton passes (15 classes, 238 tests, 2 skipped; the second filter matches no class at 5adff78bb168); :lucene:suggest:test --tests 'org.apache.lucene.search.suggest.document.*' passes (6 classes, 58 tests); checkGoogleJavaFormat passes on core and analysis-common.
An earlier run with the fix over the stock jars passed TestAutomaton, TestOperations and TestConcatenateGraphFilter, 120 of 120.

B. Snapshot dest's transitions before adding any

Read dest's (dest, min, max) triples with getTransition(dest, i, t) into a local int[], then add them to source. An independent reviewer wrote this fix; their filter test and the core-only test pass with it, with assertions on and off.

Trade-offs

One int[3 * count] allocation per call; dest is still finished by the first addTransition(source, ..), as today.

C. Build replaceSep on Automaton.Builder

Caller-side: fill replaceSep's result with Automaton.Builder, as AnalyzingSuggester does since LUCENE-5963. The same algorithm on Builder gives [playthewho, playwho] (a probe; not run through the module suites).

Trade-offs

Fixes the filter but leaves the addEpsilon hazard for any other caller that passes an open state (by reading, the plain-Automaton callers in Operations and Automata pass finished states). Both classes are @lucene.experimental and the Automaton javadoc asks for a state's transitions at once, so a maintainer may prefer this site.

Downstream note

Applications that offer completion fields with token separators turned off can silently miss suggestions for synonym-expanded values; configuring a separator avoids it.

How it was found

A proof-obligation audit of Automaton.addEpsilon's contract: the obligation that addEpsilon(source, dest) copies every transition of dest to source was checked against addTransition, which sorts and merges the open state in place. The gap was then witnessed by a one-test public-API JUnit on stock main.

The method in full133 words

Method: semi-formal, a proof-obligation audit witnessed by an executable repro. The audit stated the obligation of Automaton.addEpsilon(source, dest) (every transition of dest ends up on source) and checked it against the code it calls: addTransition finishes the open state, and finishCurrentState sorts and merges that state's block in place. The obligation fails when dest is the open state. Of the callers, ConcatenateGraphFilter.replaceSep can pass the open state (the core callers in Operations and Automata pass finished states, by reading), and a one-test JUnit on the stock main jars witnessed the lost path with assertions off and the AssertionError with assertions on.

It was then checked by a reproducer, a cross-model reviewer told to refute it, an intended-behaviour devil's advocate, an adjudication, a credibility audit and a final repro check (see "Independent checks").

Prior reports, history and checks

Prior reports

No prior report found (searched 2026-11-02): GitHub issues, PRs and commits, the JIRA archive, five mailing lists including CI mails, two downstream search servers and the web, plus the changed files of all 409 open PRs. Nearest items (#10061, #7025, #9391, #9185) are different.

Searches5 searches

Nothing public describes addEpsilon copying from a still-open state, the getNextTransition assertion reached from addEpsilon, or ConcatenateGraphFilter / CompletionAnalyzer without a separator dropping a path around a hole. Caveat: keyword search; GitHub search does not index PR review comments, so those were read only on the related items.

What was searched, when, and what turned up
Where	When	How	Found
GitHub issues and PRs (apache/lucene), commits	2026-11-02	16 issue/PR queries and 3 commit queries by a scripted search, about 30 manual searches (addEpsilon, replaceSep, preserveSep, CompletionAnalyzer, ConcatenateGraphFilter, getNextTransition, CompletionTokenStream; every item read), a re-check	no report of this defect
Open PRs	2026-11-02	the changed files of all 409 open apache/lucene PRs	only #14360 touches Automaton.java (adds toMermaid(), leaves addEpsilon alone); none touches ConcatenateGraphFilter, CompletionAnalyzer, CompletionTokenStream or TokenStreamToAutomaton
Mailing lists and CI mails	2026-11-02	20 queries over dev@, java-user@, issues@ and commits@; builds@ for failure mails naming addEpsilon, getNextTransition or ConcatenateGraphFilter	no report; 0 CI failure mails
JIRA archive, downstream repositories, web	2026-11-02	4 JIRA-archive queries, 2 downstream-repository queries plus manual searches of apache/lucene-solr, apache/solr and two downstream search servers, 6 web queries	no report
Related items (read)	2026-11-02	the nearest hits	#10061 / LUCENE-9018 (made the separator configurable, null = none), #7025 / LUCENE-5963 (moved AnalyzingSuggester to Automaton.Builder for allocation), #6814 / LUCENE-5752, #7400 / LUCENE-6339, #9379 / LUCENE-8332, #9391 / LUCENE-8344 (a trailing-hole bug in TokenStreamToAutomaton), #9185 / LUCENE-8137 (open, a query-side synonym-plus-stop loss): none is this bug

History

Root cause from LUCENE-5752 (2014, first released in 4.10.0); visible on stock jars from 5.3.0 (CompletionAnalyzer, preserveSep=false) and 7.4.0 (ConcatenateGraphFilter, when the class arrived) through 10.6.0 and main; not fixed upstream (as of 2026-11-02).

Versions tested8 rows

Introduced by LUCENE-5752 (#6814, "Explore light weight Automaton replacement"; JIRA era, no pull request; Michael McCandless): branch commit 7339f52d921 (2014-06-11) added addEpsilon, whose body is unchanged since apart from the 2020 reformat; it landed as ec2eaaafad8 (trunk, "switch to simpler Automaton implementation", 2014-06-19) and 46132142cc2 (branch_4x, "switch to simpler, immutable Automaton implementation", 2014-06-20), first released in 4.10.0.

LUCENE-5963 (#7025, 5.0.0) moved AnalyzingSuggester.replaceSep to Automaton.Builder for allocation reasons, which removed the defect there as a side effect.
LUCENE-6339 (40e94c39ad3, 5.1.0) brought the plain-Automaton replaceSep back in the new document suggester; LUCENE-8332 (9b61121ffb6, 7.4.0) moved it into ConcatenateGraphFilter.
LUCENE-5879 (7b94751e141, 5.2.0) added the sortedness assert that fires with -ea; before that the defect is silent with -ea too.
An older, separate TokenStreamToAutomaton hole bug (fixed in 6.4.0 by 2336152fb4a) masks this one for this input in 5.1.0-5.2.x and adds a wrong extra string in 5.3.0-6.3.x; runs that apply one fix at a time separate the two bugs.
Not fixed upstream (as of 2026-11-02): the newest commits on Automaton.java (86593e51b28, 2026-04-19) and ConcatenateGraphFilter.java (36ddc378eac, 2025-05-30) are unrelated.

76 runs from 4.9.1 to main over the core API, AnalyzingSuggester, CompletionAnalyzer and ConcatenateGraphFilter; releases between the executed ones were not run (same code by reading).

Versions and branches executed, with results
Version or commit	Verdict	Result
main `5adff78bb168`	affected	`[playwho]` with assertions off; `AssertionError` at `Automaton.java:493` with assertions on
10.6.0, 10.5.2, 9.12.3	affected	the repro fails with assertions on and off (release jars)
7.4.0, 8.11.4	affected	`ConcatenateGraphFilter` (`preserveSep=false`, no separator): `[playwho]`; `AssertionError` with `-ea`
6.4.0 to 10.6.0 and main (`CompletionAnalyzer`)	affected	`preserveSep=false`: `[playwho]` (run on 6.4.0, 6.6.6, 7.3.1, 7.7.3, 8.11.4, 9.0.0, 9.12.3, 10.0.0, 10.6.0 and main)
5.3.0 to 6.3.x (`CompletionAnalyzer`)	plus older bug	`[playwho, who]` (5.3.0, 5.4.1, 5.5.5, 6.3.0 run): `playthewho` lost, plus an extra wrong string from the older hole bug fixed in 6.4.0
5.1.0 to 5.2.x (`CompletionAnalyzer`)	masked	path present on stock 5.1.0 and 5.2.1 (the older hole bug changes the graph); 5.1.0 with only that bug's fix applied gives `[playwho]`
4.10.0 to 5.0.0 (core API)	latent	the core-only test copies 1 of 2 transitions (4.10.0, 4.10.4, 5.0.0); `AnalyzingSuggester` keeps both paths on stock jars, and the document suggester does not exist yet
4.9.1	not affected	the int-state `Automaton` API does not exist yet

Independent checks

A reproducer, a cross-model reviewer told to refute it (OpenAI GPT-5.6), an intended-behaviour devil's advocate, an adjudication, a credibility audit and a final repro check all confirmed it; the adjudication corrected the first claim (position increments do not matter, the letter order does). Fix A was re-validated for this doc with gradle.

Checks and verdicts287 words

Each check ran its own tests or probes on main 5adff78bb168 unless stated.

Each independent check and its verdict
Check	Verdict	What it found
reproducer	real	Its own set-oracle test fails on main, 10.6.0, 10.5.2 and 9.12.3 with `-ea` and `-da` (`expected:<[playthewho, playwho]> but was:<[playwho]>`); its core-only test copies 1 of 2 transitions; its own snapshot fix passes; probes show the real synonym + stop chain gives this graph and that the letter order decides.
cross-model refute review	real, high confidence; intended argument weak	An independent reviewer from another model family (OpenAI GPT-5.6) wrote its own tests (`red`, `bluegreen` over two positions, `green`: `redgreen` instead of `redbluegreen`); separator `'\|'` passes; fix A passes its tests and the 12 upstream `TestConcatenateGraphFilter` tests. Re-run on `5adff78bb168`: fail.
intended-behaviour check	not intended	Built the "dest must be finished" and "lossy by design" cases and rejected both; the same `replaceSep` on `Automaton.Builder` keeps both paths.
adjudication	confirmed, high confidence	Re-ran the repro on stock main (`-ea` assert, `-da` lost path) and with fix A (pass); corrected the claim: `preservePositionIncrements=true` is not needed, the trigger depends on the letter order, and 9.12.3 also fails with `-da`.
credibility audit	confirmed	Re-ran the repro and an end-to-end `CompletionAnalyzer` probe of its own: `preserveSep=true` keeps both paths, `preserveSep=false` emits only `[playwho]`.
final repro check	confirmed	One test, three tokens (the smallest input shown to fail); a silent missing token in a documented mode, not an assertion-only symptom.
fix validation (this doc)	fix A passes	Scratch worktree of `5adff78bb168` with gradle: stock fails, fix A passes the repro and the automaton, filter and document-suggester suites, and the format check.

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 489 KB

Sources and provenance

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

Finding record

LFV-1118, snapshot of 2026-11-06

Registry title: ConcatenateGraphFilter without a token separator (and so CompletionAnalyzer with preserveSep=false) silently drops a concatenated path around a position hole, because Automaton.addEpsilon copies from a dest state that its own first addTransition sorts and reduces in place (AssertionError with -ea)
Area: analysis-common / ConcatenateGraphFilter no-separator mode, and core / util.automaton (Automaton.addEpsilon); reached from suggest (CompletionAnalyzer preserveSep=false, document suggester)
Priority: Low, rank 271: In the opt-in no-separator mode of ConcatenateGraphFilter (CompletionAnalyzer with preserveSep=false), a value whose token graph has a position hole under a multi-word token silently loses one concatenated path, and so a suggestion, in every release since 5.3.0. It needs that mode, a stop word inside a multi-word synonym and an unlucky label order, so it is a rare trigger in an opt-in suggester mode and belongs in Low.
Impact class: silent wrong results
Impact note: Only analysis chains that use the opt-in no-separator mode are hit (ConcatenateGraphFilter with a null tokenSeparator, its factory with tokenSeparator="", or CompletionAnalyzer and so the document suggester with preserveSep=false; a non-null separator, including the default, and AnalyzingSuggester/FuzzySuggester are not affected), and then only for values whose token graph has a position hole under a multi-position token (what a multi-word synonym that contains a stop word, followed by a stop filter, produces: 'play the who' with 'the who' => 'thewho' and stop word 'the') and whose hole-branch label sorts after the spanning token's label: with -da one concatenation, and with it one suggestion entry, is silently missing, and with -ea the same value throws AssertionError [exec]; preservePositionIncrements does not matter, no scale is needed, and it is in every release from 5.3.0 (CompletionAnalyzer) and 7.4.0 (ConcatenateGraphFilter) through 10.6.0 and main.
Summary: You concatenate the token graph play | thewho (spanning two positions) | who, which a multi-word synonym ('the who' => 'thewho') followed by a stop filter produces for 'play the who', with ConcatenateGraphFilter and no separator (a null tokenSeparator, or CompletionAnalyzer with preserveSep=false), and expect one token per path, 'playthewho' and 'playwho', as the class javadoc promises. With assertions disabled you get only 'playwho', so a suggestion reached through the synonym (prefix 'playth') is silently missing; with -ea the filter throws an AssertionError in Automaton.getNextTransition. The cause is Automaton.addEpsilon: it copies the transitions of a state that is still being built, and its own first addTransition to the other state sorts and shrinks that state in place mid-copy, so some transitions are copied twice and others never.
Introduced: 46132142cc2 (branch_4x, first released in 4.10.0) and trunk merge ec2eaaafad8, 'LUCENE-5752: switch to simpler, immutable Automaton implementation' (migrated as apache/lucene#6814; a JIRA-era change, no pull request; author Michael McCandless). The code was written on the lucene5752 branch: 7339f52d921 added addEpsilon, whose body is unchanged since apart from the 2020 reformat, and c98b9a8d525 ('cutover suggesters') rebuilt AnalyzingSuggester.replaceSep as a plain Automaton filled in reverse topological order, with addEpsilon for SEP and HOLE arcs [read: git log, git blame and git log -L in the history clone; exec: the core-API test fails on 4.10.0 and does not compile on 4.9.1]. The calling pattern was carried into the document suggester by LUCENE-6339 (40e94c39ad3, first released in 5.1.0; trunk b7adb6ac770) and into ConcatenateGraphFilter by LUCENE-8332 (9b61121ffb6, 7.4.0; master f9f5e837450); LUCENE-5963 (1c2918f66d7, 5.0.0, #7025) moved only AnalyzingSuggester's copy to Automaton.Builder, for allocation reasons, which removed the defect there as a side effect [read] (2014-06-11 (author date of 7339f52d921 and c98b9a8d525 on the lucene5752 branch); landed 2014-06-19 on trunk (ec2eaaafad8) and 2014-06-20 on branch_4x (46132142cc2))
First affected version: 4.10.0 for the defective Automaton.addEpsilon [exec: the core-API test copies 1 of 2 transitions on 4.10.0 with -ea and -da; 4.9.1 has no int-state Automaton API]. By public analysis path on stock jars: CompletionAnalyzer(preserveSep=false) loses the path from 5.3.0 [exec; 5.1.0-5.2.x have the calling code, but for this input an older, separately fixed TokenStreamToAutomaton hole bug masks it: with only that bug's 6.4.0 fix shadowed, 5.1.0 loses the path], and ConcatenateGraphFilter without a separator from 7.4.0, its first release [exec; 7.3.1 lacks the class]
Affected versions: Root-cause code in every release from 4.10.0 through 10.6.0 (released 2026-10-29, 4ae946e5a9b) and main 5adff78bb168 (12.0.0-SNAPSHOT) [exec, core-API test: 4.10.0, 4.10.4, 5.0.0, 6.6.6, 8.11.4, 9.12.3, 10.6.0, main]. With the repro's token graph on stock jars: ConcatenateGraphFilter without a separator 7.4.0 through 10.6.0 and main [exec: the finder's JUnit on main, 10.6.0 (-ea and -da) and 9.12.3 (-ea, and -da in the history run); the independent reproduction's JUnit on main, 10.6.0, 10.5.2 and 9.12.3 (-ea and -da); a main() form on 7.4.0 and 8.11.4 (-ea and -da)]; CompletionAnalyzer(preserveSep=false) 5.3.0 through 10.6.0 and main [exec -da: 5.3.0, 5.4.1, 5.5.5, 6.3.0, 6.4.0, 6.6.6, 7.3.1, 7.7.3, 8.11.4, 9.0.0, 9.12.3, 10.0.0, 10.6.0, main], where 5.3.0-6.3.x also emit an extra wrong string from the older TokenStreamToAutomaton hole bug (fixed in 6.4.0 by 2336152fb4a) and, with -ea, fail on that bug's assertion first. Latent (code present, masked for this input on stock jars): 4.10.x AnalyzingSuggester/FuzzySuggester without PRESERVE_SEP and the 5.1.0-5.2.x document suggester [exec with only the 6.4.0 TokenStreamToAutomaton fix shadowed]. With -ea the failure is an AssertionError from 5.2.0 on (the sortedness assert came with LUCENE-5879, 7b94751e141); before that it is silent under -ea too. Releases between the executed ones were not run; their addEpsilon, finishCurrentState and replaceSep code is the same by reading. Not new in 10.6 (10.5.2 fails). Not fixed upstream: the newest commits are 86593e51b28 on Automaton.java (author date 2026-04-19, unrelated) and 36ddc378eac on ConcatenateGraphFilter.java (author date 2025-05-30, typo fixes); the only open PR touching Automaton.java (#14360) adds toMermaid() and leaves addEpsilon alone [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 (243 distinct hits, the only highly relevant one #10061, read), a builds@ search for CI failure mails naming addEpsilon, getNextTransition or ConcatenateGraphFilter (0 hits), about 30 manual GitHub searches on apache/lucene, apache/lucene-solr, apache/solr, Elasticsearch and OpenSearch (every item for ConcatenateGraphFilter, CompletionTokenStream, preserveSep, CompletionAnalyzer, addEpsilon and replaceSep read), the changed files of all 409 open apache/lucene PRs, and commit history by path with author dates. Same-day recheck: GitHub search on apache/lucene for addEpsilon (3, unchanged), ConcatenateGraphFilter (6), preserveSep (6), getNextTransition (5), replaceSep (4); issues and PRs updated since 2026-10-31 matching automaton, suggest, epsilon, synonym or CompletionAnalyzer (none relevant); the 18 open PRs updated since 2026-10-31 (none touches Automaton.java, ConcatenateGraphFilter.java, CompletionTokenStream.java, CompletionAnalyzer.java or TokenStreamToAutomaton.java); newest commits on the two fix-site files unchanged. Related, not reports: #10061 / LUCENE-9018 (added the Character tokenSeparator and the current addEpsilon branch for SEP; nobody discusses lost paths or an assertion), #7025 / LUCENE-5963 (moved only AnalyzingSuggester.replaceSep to Automaton.Builder, for allocation reasons), #6814 / LUCENE-5752 (introduced addEpsilon), #7400 / LUCENE-6339 and #9379 / LUCENE-8332 (carried the plain-Automaton replaceSep into the document suggester and ConcatenateGraphFilter), #9391 / LUCENE-8344 (same settings, a trailing-hole TokenStreamToAutomaton bug), #9185 / LUCENE-8137 (open; a query-side synonym-plus-stop path loss in GraphTokenStreamFiniteStrings), #9297 and #5137 (open; debates about the graph a stop filter leaves), #9408 (open; TestRandomChains).
Lucene commit tested: main 5adff78bb168 (12.0.0-SNAPSHOT) through gradle and a standalone runner, assertions on and off; release jars 10.6.0, 10.5.2 and 9.12.3 (the JUnit), 7.4.0 and 8.11.4 (a main() form), and 4.9.1 to 10.0.0 for the history runs; fix A in a scratch worktree of 5adff78bb168 (OpenJDK 25.0.3, Linux aarch64). The cross-model review ran on main ea57360912ed, whose Automaton.java, ConcatenateGraphFilter.java, TokenStreamToAutomaton.java and Operations.java are byte-identical to 5adff78bb168's, and its tests were re-run on 5adff78bb168.

Lucene and upstream sources

Finding record: lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java:33-43 (at 5adff78bb168) (class javadoc: each state must have all of its transitions added at once; a state is finished, sorted and reduced once transitions go to another state or finishState() is called; @lucene.experimental), :154-183 (addTransition: when curState != source it calls finishCurrentState() on the open state, :162-165), :185-199 (addEpsilon javadoc 'Dest state must already have all transitions added because this method simply copies those same transitions over to source'; count = initTransition(dest, t) read once at :191, cursor reads while addTransition(source, ..) runs, :192-195: fix site), :239-311 (finishCurrentState sorts and reduces the block in place), :488-498 (getNextTransition asserts at :490 and :493)
lucene/analysis/common/src/java/org/apache/lucene/analysis/miscellaneous/ConcatenateGraphFilter.java:39-46 (at 5adff78bb168) (class javadoc: 'one output token for every path through the token stream (which is a graph)'; @lucene.experimental), :62-63 (DEFAULT_TOKEN_SEPARATOR = SEP_LABEL, DEFAULT_PRESERVE_SEP = true), :101-102 (tokenSeparator 'Can be null, in this case tokens will be concatenated without any separators'), :128-143 (preserveSep=false maps to a null separator), :285-333 (replaceSep: a plain Automaton filled in reverse topological order; POS_SEP becomes addEpsilon(state, t.dest) when tokenSeparator is null, :311; HOLE always becomes addEpsilon, :323)
lucene/analysis/common/src/java/org/apache/lucene/analysis/miscellaneous/ConcatenateGraphFilterFactory.java:28-30 (at 5adff78bb168) and :81-94 (an empty tokenSeparator means no separator); lucene/suggest/src/java/org/apache/lucene/search/suggest/document/CompletionTokenStream.java:46-61 (CompletionAnalyzer's stream wraps new ConcatenateGraphFilter(input, preserveSep, ..)); lucene/core/src/java/org/apache/lucene/analysis/TokenStreamToAutomaton.java:271-299 (addHoles: the HOLE arc under a token that spans a position where nothing ends)
https://github.com/apache/lucene/issues/10061, https://github.com/apache/lucene/issues/7025, https://github.com/apache/lucene/issues/6814, https://github.com/apache/lucene/issues/7400, https://github.com/apache/lucene/issues/9379, https://github.com/apache/lucene/issues/9391, https://github.com/apache/lucene/issues/9185, https://github.com/apache/lucene/pull/14360 (read 2026-11-02)
The finding in 30 seconds: lucene/analysis/common/src/java/org/apache/lucene/analysis/miscellaneous/ConcatenateGraphFilter.java:244-250 (at 5adff78bb168) (toAutomaton), :285-333 (replaceSep; :311 POS_SEP to addEpsilon with a null separator, :323 HOLE to addEpsilon)
lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java:154-183 (at 5adff78bb168) (addTransition; :162-165 finishCurrentState on the open state), :185-199 (addEpsilon; :191 count read once, :192-195 cursor loop), :239-311 (finishCurrentState), :488-498 and :500-533 (getNextTransition, transitionSorted)
lucene/core/src/java/org/apache/lucene/analysis/TokenStreamToAutomaton.java:271-299 (at 5adff78bb168) (addHoles)
Who is affected: lucene/analysis/common/src/java/org/apache/lucene/analysis/miscellaneous/ConcatenateGraphFilter.java:62-63, (at 5adff78bb168) :101-102, :140
lucene/analysis/common/src/java/org/apache/lucene/analysis/miscellaneous/ConcatenateGraphFilterFactory.java:28-30, (at 5adff78bb168) :81-94
lucene/suggest/src/java/org/apache/lucene/search/suggest/document/CompletionTokenStream.java:54-61; (at 5adff78bb168) CompletionAnalyzer.java:69-88
Why it looks unintended: lucene/analysis/common/src/java/org/apache/lucene/analysis/miscellaneous/ConcatenateGraphFilter.java:39-46, (at 5adff78bb168) :101-102
lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java:33-43 (at 5adff78bb168) (class javadoc), :185-188 (addEpsilon javadoc)
lucene/analysis/common/src/test/org/apache/lucene/analysis/miscellaneous/TestConcatenateGraphFilter.java:45-52, (at 5adff78bb168) :108-131; lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java:533; lucene/analysis/common/src/test/org/apache/lucene/analysis/core/TestFlattenGraphFilter.java:241
https://github.com/apache/lucene/issues/7025, https://github.com/apache/lucene/issues/7400, https://github.com/apache/lucene/issues/10061 (read 2026-11-02)
Suggested fix: lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java:154-183, (at 5adff78bb168) :185-199, :326-331 (finishState)
lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java:36-43; (at 5adff78bb168) lucene/analysis/common/src/java/org/apache/lucene/analysis/miscellaneous/ConcatenateGraphFilter.java:46 (@lucene.experimental); Operations.java:189, :495, :1299 and Automata.java:541 (the plain-Automaton addEpsilon callers)
Prior reports: https://github.com/apache/lucene/issues/10061, https://github.com/apache/lucene/issues/7025, https://github.com/apache/lucene/issues/6814, https://github.com/apache/lucene/issues/7400, https://github.com/apache/lucene/issues/9379, https://github.com/apache/lucene/issues/9391, https://github.com/apache/lucene/issues/9185, https://github.com/apache/lucene/pull/14360 (read 2026-11-02)
History: https://github.com/apache/lucene/issues/6814, https://github.com/apache/lucene/issues/7025, https://github.com/apache/lucene/issues/9379 (read 2026-11-02)

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

Repro files

TestConcatenateGraphFilterHoleWithoutSeparator.java (lucene/analysis/common, public API): repro/LFV-1118/TestConcatenateGraphFilterHoleWithoutSeparator.java (39 lines)

About the diagrams

A summary still (PNG), drawn from probes on main 5adff78bb168 with assertions on and off.

assets/LFV-1118/bug.png (489 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: concatenating a token graph

The finding, step by step

Who is affected

The mechanism (main 5adff78bb168)

The trace for the repro (executed, same loop as replaceSep)

Why the letter order matters

Minimal repro

Environment

Observed output

Why it looks unintended

Suggested fix

A. Finish an open dest at the top of addEpsilon (validated by the checks) (recommended)

B. Snapshot dest's transitions before adding any

C. Build replaceSep on Automaton.Builder

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`)

The trace for the repro (executed, same loop as `replaceSep`)