A zero-length token makes TokenStreamToAutomaton drop every path through it, so the document suggester, AnalyzingSuggester and FuzzySuggester silently lose the suggestion

TokenStreamToAutomaton turns a token graph into an automaton whose labels are each token's bytes, with a separator (POS_SEP) between tokens. For each token it creates the state where the token ends and adds one arc per byte, the last one into that state. A token whose term is empty has no bytes, so no arc is added, the end state is never reached, and every path through the token is lost. Stock analysis emits such tokens on purpose: ArabicAnalyzer, PersianAnalyzer and SoraniAnalyzer turn a standalone tatweel (U+0640) into "", and PatternReplaceFilter can blank a punctuation-only token. Everything built on the class then drops the value without an error (the other suggesters, such as the infix and FST lookups, do not use it): ConcatenateGraphFilter emits no token although it promises "one output token for every path", the document suggester (SuggestField, CompletionAnalyzer) indexes no entry, and AnalyzingSuggester and FuzzySuggester skip the input. With ArabicAnalyzer, the suggestions "foo bar" and "foo ـ bar" and the prefix "foo" give only [foo bar]; a lookup that contains a standalone tatweel returns nothing. A stacked empty token loses only its own path. The loop has had no zero-length case since the class was written in 2012: all 120 release tags from 4.1.0 to 10.5.2 in the history clone have it, the 21 releases executed fail, and so does main.

• Empty token: a token whose term has zero characters, "". Lucene allows them, and some stock filters produce them on purpose: the Arabic, Persian and Sorani normalizers delete the tatweel (U+0640), a typographic stretching mark, so a tatweel standing alone between spaces becomes ""; PatternReplaceFilter can blank a token such as -.
• TokenStreamToAutomaton: turns the tokens of one value into an automaton, a graph of states joined by arcs, one arc per byte of each token, with a separator arc (SEP) between tokens and a HOLE arc where a position is missing (a removed stop word). Each path from the start to an accept state spells one way to read the value.
• Its users: ConcatenateGraphFilter joins every path into one token; the document suggester (SuggestField, CompletionAnalyzer) indexes those joined tokens; AnalyzingSuggester and FuzzySuggester index the automaton's strings directly. The other suggesters (AnalyzingInfixSuggester, BlendedInfixSuggester, FreeTextSuggester, FSTCompletionLookup, WFSTCompletionLookup) do not use it.

1. For every token, the state where the token ends is created first (TokenStreamToAutomaton.java:178-181).
2. The token's arcs are added only inside for (int byteIDX = 0; byteIDX < termLen; byteIDX++) (:197-207); the last arc ends in that state.
3. For an empty token termLen is 0, the loop runs zero times, and nothing joins the state where the token starts to the state where it ends. Everything after it hangs off an unreachable state: for foo, "", bar the automaton accepts no string.
4. With no strings, ConcatenateGraphFilter emits no token, the completion field gets no entry, and the analyzing suggesters get no input. If the empty token is stacked on a non-empty one at the same position, only its own path is lost.

• Entry points. The document suggester (SuggestField, ContextSuggestField, CompletionAnalyzer, PrefixCompletionQuery and its siblings), AnalyzingSuggester, FuzzySuggester, and ConcatenateGraphFilter (or its concatenateGraph factory) in any analysis chain.
• What it takes. A value, or a lookup key, whose analysis contains a token with an empty term that the paths must cross (an empty token stacked next to a non-empty one loses only its own path). Stock prebuilt analyzers: ArabicAnalyzer, PersianAnalyzer and SoraniAnalyzer on a standalone tatweel. Custom chains: a filter that can blank a token with no LengthFilter after it, for example PatternReplaceFilter stripping punctuation under a whitespace tokenizer (its javadoc warns it "may produce Tokens whose text is the empty string"), or KeywordTokenizer + TrimFilter on blanks.
• Opt-in. The completion suggesters and ConcatenateGraphFilter are features an application chooses (the document suggester also needs a completion postings format), and TokenStreamToAutomaton, ConcatenateGraphFilter and the suggester classes are marked experimental (the analyzers and PatternReplaceFilter are not). Within such an application the trigger is ordinary text.
• Deterministic and silent. Every value whose only path runs through an empty token is lost on the first try, with assertions on or off; no exception, no log line. The automaton is built from the value's own tokens, so index size plays no part. In the security probe the document and its other fields were indexed, CheckIndex was clean and other entries were unaffected.
• Both sides. At index time the value never becomes a suggestion (the document is indexed, its completion entry is not); at lookup time a key with a standalone tatweel ("foo ـ") returns nothing.
• Not affected. AnalyzingInfixSuggester, BlendedInfixSuggester, FreeTextSuggester, FSTCompletionLookup and WFSTCompletionLookup do not use TokenStreamToAutomaton or ConcatenateGraphFilter.
• How often. A standalone tatweel is uncommon in titles and names (it normally sits inside words); a punctuation-stripping chain hits ordinary text such as "Spider Man - Homecoming" every time. Nobody has reported it since 4.1.0, so the registry rates it rare (a judgement, not a measurement).
• Downstream. Search servers build completion features on these classes; that path was not executed.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: output tokens for the one path foo, "", bar expected:<1> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.analysis.miscellaneous.TestConcatenateGraphFilterEmptyToken.testPathThroughEmptyTokenIsKept(TestConcatenateGraphFilterEmptyToken.java:36)

• ConcatenateGraphFilter javadoc (ConcatenateGraphFilter.java:40-41): "Concatenates/Joins every incoming token with a separator into one output token for every path through the token stream (which is a graph)."
• TokenStreamToAutomaton javadoc (:31-33): the labels are the token's bytes, and "Between tokens we insert POS_SEP and for holes we insert HOLE." Read literally, a, "", b gives a SEP SEP b, not an empty language; the javadoc does not mention empty tokens, so this is a reading, not an explicit rule.
• The authors' comment in replaceSep (AnalyzingSuggester.java:295-301, added with the trunk commit of the class, f2f91bae46c; the copy at ConcatenateGraphFilter.java:316-322 came later through CompletionTokenStream, LUCENE-6339, and LUCENE-8332): removing a hole leaves "two SEP tokens next to each other ... Note that it will also match an empty-string token". Our reading, an inference: it assumes the empty token's path is there.
• preservePositionIncrements javadoc (ConcatenateGraphFilter.java:103-105): "Whether to add an empty token for missing positions. The effect is a consecutive SEP_LABEL."
• Empty terms are legal: TestSoraniNormalizationFilter asserts checkOneTerm(a, "\u0640", "") (:85); PatternReplaceFilter's javadoc warns it may produce empty tokens; LUCENE-3529 and LUCENE-4880 made IndexWriter and MemoryIndex accept empty terms. Being legal to index does not by itself mean every experimental graph consumer promises to handle them; the case rests on the ConcatenateGraphFilter promise and on the absence of any exclusion.
• Upstream tests: one randomized test, TestFlattenGraphFilter (:702), asserts that this class's output for its graphs has no dead states (not a stated invariant, but dead states are not expected output); the empty-token automaton has them. TestGraphTokenizers and TestConcatenateGraphFilter cover holes and an empty stream, never a zero-length token, and no test pins today's behaviour.
• History: the loop never had a zero-length case (LUCENE-3842, 2012); the 66 JIRA comments of that issue discuss holes and separators only, and no won't-fix or by-design discussion was found.

Strongest case for "intended": the classes that build and consume the automaton are experimental; PatternReplaceFilter warns about empty tokens, so users should add LengthFilter(min=1); some components reject empty tokens; AnalyzingSuggester documents that "Lookups with the empty string return no results", SuggestField rejects an empty value, and an empty stream yields no output by design. And an empty term has no byte for an arc, so encoding it as a HOLE conflates a real token with a missing position; nobody has reported the behaviour.

Why it fails: experimental allows API changes, not silent loss of entries; no javadoc of these classes asks for non-empty tokens, and the authors' comment, on our reading, expects the empty token to survive; the prebuilt Arabic, Persian and Sorani analyzers have no option for an extra filter (wrapping them works, but nothing tells users to); the empty-input rules cover an empty value, stream or lookup, not a non-empty value with one empty token inside; and an upstream test treats dead states as a failure for its graphs. The encoding point is about how to keep the path, not whether to keep it. Every checker concluded "not intended". The exact joined form (a SEP SEP b or a SEP b) is a design choice for the maintainers; the path must not vanish.

Both arc-based options were run through gradle in a scratch worktree at ea57360912ed; the others are untested design alternatives. Every command is in the fix folder's commands.txt.

optionA2-hole-arc-unless-all-empty.diff, TokenStreamToAutomaton.java only, +20 lines (counting an IntArrayList import and two blank lines). Each empty token's start and end states are recorded; after the loop they get the one HOLE arc a hole gets, if the stream had any non-empty token. ConcatenateGraphFilter and AnalyzingSuggester (so also FuzzySuggester) turn HOLE into an epsilon, so a, "", b is joined as a SEP SEP b, the form the replaceSep comment and the preservePositionIncrements javadoc describe; direct callers of toAutomaton, such as the test framework's assertGraphStrings, see the raw HOLE label. A stream of only empty tokens keeps today's automaton (it accepts nothing), so a lookup key made only of empty tokens still matches nothing, like an empty key, and for SuggestField, AnalyzingSuggester and FuzzySuggester a value made only of tatweels still gets no entry. Automaton.Builder accepts transitions in any order.

    // (from, to) state pairs of zero-length tokens, connected at the end:
    final IntArrayList emptyTokens = new IntArrayList();
    boolean sawNonEmptyToken = false;
    while (in.incrementToken()) {
      ...
      if (termLen == 0) {
        emptyTokens.add(state);
        emptyTokens.add(endPosData.arriving);
      } else {
        sawNonEmptyToken = true;
      }
      ...
    }
    in.end();

    if (sawNonEmptyToken) {
      // A zero-length token has no bytes, but it still spans its position(s): connect it like a
      // hole so the paths through it are kept (consumers remove HOLE, leaving two adjacent
      // separators). A stream of only zero-length tokens accepts nothing, like an empty stream.
      for (int i = 0; i < emptyTokens.size(); i += 2) {
        builder.addTransition(emptyTokens.get(i), emptyTokens.get(i + 1), HOLE);
      }
    }

Trade-offs

• ContextSuggestField: the all-empty exception looks at the whole stream, and ContextSuggestField puts a non-empty context-prefix token in front of the value. So with this fix a ContextSuggestField value made only of tatweels gets an entry with an empty key (stock gets none), and a match-all ContextQuery returns it (executed by the fact check). The guard test checks only the lookup side. Any non-empty token, even one stacked alternative, turns the exception off.
• An empty token and a removed (hole) token become the same in the automaton when preservePositionIncrements is true; with false a hole collapses to a SEP b while this fix still gives a SEP SEP b. The exact form is the maintainers' choice.
• A prefix lookup "foo" returns "foo ـ bar", but the exact lookup "foo bar" does not match it, as with a stop-word hole.
• Edges: a stream whose only position holds a non-empty token and a stacked empty one also accepts the empty string (no stock analyzer was seen producing that); an empty token with positionLength > 1 gets one HOLE arc across its span (untested).
• Not reviewed by a committer.

What the checks validated

• The doc's test plus 3 guard tests for lookups made only of empty tokens (AnalyzingSuggester, PrefixCompletionQuery, ContextQuery): 9 tests, 0 failures, with -Ptests.asserts=true and =false.
• TestGraphTokenizers with 3 new tests: 26 tests, 0 failures; core org.apache.lucene.analysis.*: 21 classes, 171 tests, 0 failures (assertions on, the core module's default for this seed).
• The whole suggest module: 32 classes, 245 tests (236 upstream + 9 new), 0 failures, with assertions off (2026-10-26, the seed's default) and on (the fact check's -Ptests.asserts=true re-run). The whole analysis-common module: 339 classes, 1,909 tests, 0 failures, likewise off and on (it includes the graph-string tests of TestSynonymGraphFilter and TestWordDelimiterGraphFilter, which use this class). TestRandomChains: 2 tests, 0 failures (assertions off).
• :lucene:core:check :lucene:suggest:check -x test (google-java-format, ecjLint, forbiddenApis) passes.
• Harness with the fix shadowed in: the finder's test 3 of 3 (including the joined token a SEP SEP b), an independent reproducer's 10 of 10, and the follow-up's security probe: in 620 lookups every stock result set is a subset of the fix's, 0 ContextQuery errors, a lone-tatweel lookup returns nothing, 81 of 84 inputs get an entry.

Inside the loop, if (termLen == 0) builder.addTransition(state, endPosData.arriving, HOLE);. It fixes every bug test, and no upstream test fails (suggest 245 tests, analysis-common 1,909, TestRandomChains).

      if (termLen == 0) {
        // A zero-length token still spans its position(s): connect it like a hole so that the paths
        // through it are kept (consumers remove HOLE, so it reads as an empty element between two SEPs).
        builder.addTransition(state, endPosData.arriving, HOLE);
      }

Trade-offs

A value or lookup made only of empty tokens becomes the empty string: a lookup for a lone tatweel returns every suggestion (AnalyzingSuggester 2 of 2 instead of 0, PrefixCompletionQuery 1 of 1), against the documented "Lookups with the empty string return no results". With assertions off a ContextQuery returns 2 of 2, including an entry made only of a tatweel; with assertions on that lookup fails with an AssertionError at ContextQuery.java:319.

What the checks validated

The 6 bug tests, the finder's 3 and the reproducer's 10 pass. The 3 guard tests fail through gradle with assertions off and through the harness with assertions on and off; testOnlyEmptyTokens fails (assertions on). The suggest, analysis-common and TestRandomChains suites ran with assertions off (the seed's default).

Treat a zero-length token like a removed token with preservePositionIncrements=false, so "foo ـ bar" matches the lookup "foo bar".

Trade-offs

More code (merge the token's start and end states, or an epsilon), and an empty token then behaves differently from a hole, against the preservePositionIncrements javadoc. Untested.

Wrap the stream in ConcatenateGraphFilter and the analyzing suggesters with a filter that drops empty tokens and carries their position increment, as LengthFilter does.

Trade-offs

For an empty token alone at its position it gives the recommended fix's result for those consumers; for a stacked one (position increment 0) the filter removes the alternative, while the recommended fix keeps it as a HOLE path. TokenStreamToAutomaton stays wrong for its other callers (for example the test framework's assertGraphStrings), and three places change instead of one. Untested.

Either toAutomaton throws on a zero-length term, so the loss becomes loud, or the empty token gets its own label instead of HOLE, so consumers can tell it from a missing position.

Trade-offs

Rejecting makes values that index silently today fail at index time; a new label needs every consumer of the automaton to handle it. Untested; listed because the cross-model fact check suggested presenting it.

In a CustomAnalyzer, add the length filter with min=1; around a prebuilt analyzer, an AnalyzerWrapper whose wrapComponents appends new LengthFilter(tokenStream, 1, Integer.MAX_VALUE). LengthFilter turns the removed token into a hole, so the value is joined as foo SEP SEP bar, the same form as the recommended fix for an empty token alone at its position (a stacked empty token is simply removed).

Trade-offs

Each application has to know about it; nothing in the suggester documentation says it is needed.

What the checks validated

On stock main, ArabicAnalyzer wrapped this way returns [foo ـ bar, foo bar] from both AnalyzingSuggester and SuggestField (2 tests, 0 failures).

Method: bounded-exhaustive translation validation (a hunt unit, completion suggester indexing, 2026-10-26, main ea57360912ed). No model checker, SMT solver or prover was involved.

• The finder (an AI tool) wrote an independent reference of the documented join semantics: one output token for every path, separators between tokens, holes for missing positions.
• Its checker (ConcatGraphTV.java) ran the real classes against it over every token graph of up to 3 positions, each a hole or 1-2 distinct stacked tokens from an 8-token alphabet that includes the empty token (every token with position length 1; graphs made only of holes skipped), with trailing holes on and off, 5 separators and both preservePositionIncrements settings: 1,041,120 checks. The run reported 889,575 mismatches in all, sorted into classes; the class "missing paths through an empty token" (245,958 checks) is this bug, and the other classes (separator escaping, non-ASCII separators, the expansion limit and an unclassified rest) are separate questions, not part of this report.
• A suggester-level checker (SuggestTV.java), with a token mapped to "", found 7,915 mismatching (query x configuration) checks out of 13,440, each missing one or more results and none returning an extra one; a survey of stock analyzers found that the Arabic, Persian and Sorani analyzers emit an empty token for a standalone tatweel.
• Then a public-API JUnit, a cross-model review, independent verifiers, an adjudication, a 66-run release sweep, a prior-report search and a security screen (see Independent checks).