ConcatenateGraphFilter mishandles a custom tokenSeparator: doubled inside tokens, cut to one byte when non-ASCII

ConcatenateGraphFilter joins all tokens of a field into one term "with a separator". Since LUCENE-9018 (8.4.0) the separator is configurable, through the Character tokenSeparator constructor or the concatenateGraph factory, which accepts any one-char string. The code still treats a custom separator like the internal one-byte label U+001F it was written for: it passes the separator to an escaper (ConcatenateGraphFilter.java:235) that doubles every token byte equal to it (:265-280) and that asserts the separator fits in a signed byte and casts it to one (:259-262), and it emits the separator as one transition label (:309) that the byte path cuts to its low byte. So with - the single token e-mail becomes e--mail; with U+2013 new and york become new, U+0013, york when assertions are off and an AssertionError when they are on; U+00B7 gives a lone b7 byte, invalid UTF-8. The same input analyzes alike at index and query time, so an analyzed query for it still matches; the wrong term shows wherever it is compared with a string built outside the analyzer, and some different inputs collide (e-mail and e, a removed stop word, mail). Only chains with a custom separator are affected; the default separator and the suggest module's completion fields are not. The fix escapes only the internal label and writes a custom separator as given, as its UTF-8 bytes when non-ASCII (+41/-5 lines), validated with the analysis-common and suggest test suites.

• Join: the filter reads all tokens of a field and emits one term per path through the token graph, the tokens "joined with a separator" (one term for a plain token stream; more with synonyms).
• SEP_LABEL: the default separator, the control character U+001F, one byte in UTF-8. Because a token can itself contain that byte, the filter escapes it inside tokens by doubling it (a\u001fb gives a 1f 1f b, on every version since 7.4.0).
• Byte automaton: the filter builds an automaton whose transition labels are the UTF-8 bytes of the tokens, with a separator label between tokens, and reads the joined terms from it. Each label must fit in one byte (Util.toBytesRef: "you must ensure the int values fit into a byte").

// ConcatenateGraphFilter.java at a9779ef3c193, toAutomaton()
if (tokenSeparator != null) {
  tsta = new EscapingTokenStreamToAutomaton(tokenSeparator);   // :235  any custom separator goes to the escaper
...
/** Just escapes the {@link #SEP_LABEL} byte with an extra. */  // :253
public EscapingTokenStreamToAutomaton(int sepLabel) {
  assert sepLabel <= Byte.MAX_VALUE;                            // :260  fails for any separator above U+007F
  this.sepLabel = (byte) sepLabel;                              // :261  U+2013 -> 0x13
}
// :265-280 changeToken(): every token byte equal to sepLabel is written twice
// :309 replaceSep(): the token boundary becomes ONE label, tokenSeparator (0x2013 on a byte automaton)
// Util.java:793 toBytesRef(): scratch.setByteAt(i, (byte) value)  -> 0x13

1. Doubling. LUCENE-9018 replaced EscapingTokenStreamToAutomaton(SEP_LABEL) with EscapingTokenStreamToAutomaton(tokenSeparator). So with - the escaper doubles every - inside a token: e-mail becomes e--mail even when it is the only token and nothing is joined.
2. Truncation. The escaper's assert is the only upfront check of the separator, and the first assertion reached (Util.java:792 asserts later that each label is in -128..255). With assertions on it fails for every stream once the separator is above U+007F. With assertions off, the separator label is cut to its low byte when the term bytes are written: U+2013 (UTF-8 e2 80 93) becomes 13, a different, valid character; U+00B7 (c2 b7) becomes a lone b7, which is not valid UTF-8. Two separators with the same low byte give the same terms (from the code; not executed). The escaper also compares every token byte with that low byte, so equal in-token bytes are doubled even in a single token: with U+00B7, the token a·b (61 c2 b7 62) becomes 61 c2 b7 b7 62, and U+00F7 (c3 b7) becomes c3 b7 b7.
3. A third symptom with assertions off (executed with U+00F7 only): the filter also decodes the term bytes into its CharTermAttribute. When the cut byte is a UTF-8 lead byte (0xC0-0xFF) near the end of the term, the decoder reads up to 3 bytes past the term, left over from an earlier, longer term on the same thread (only the low 6 bits of each reach the decoded char); when the term exactly fills the buffer, incrementToken throws ArrayIndexOutOfBoundsException and that one document is rejected. The indexed bytes never contain the leftovers, and the index passed the CheckIndex that the test framework runs when the probe's directory closes.
4. A token pushed over the term limit (assertions off): the doubling turns a 20,000-byte token of - into 40,000 bytes, and IndexWriter rejects that document as an immense term ("bytes can be at most 32766 in length; got 40000"); the writer stays open.

With assertions on, the four non-ASCII rows throw AssertionError at ConcatenateGraphFilter.java:260. With the unicode-aware automaton (toAutomaton(true), public) the code point U+2013 comes out right between tokens with assertions off, but the escaper still runs on the token bytes first, so with the U+00B7 separator the token a·b gives U+0061 U+00B7 U+00B7 U+0062; the same assertion fails with assertions on.

• Who is hit. Code or configuration that picks a custom separator. Example choices (-, _, a space) hit tokens that already contain them: e-mail with a whitespace tokenizer, a keyword-like token or a multi-word synonym with a space. An adaptation of two upstream tests (the synonym three words synonym of testSeparatorWithSynonyms, kept as one mapping on the input mykeyword another, with the space separator of testSeparator) gives three words synonym another. A non-ASCII separator makes every joined term wrong and doubles in-token bytes equal to its low byte; with assertions off a single token without such a byte is unchanged, and with assertions on every document fails.
• Downstream default. OpenSearch exposes the filter as concatenate_graph with token_separator defaulting to a space and accepting any single character, so there the doubling needs no opt-in beyond using the filter.
• What goes wrong. The same input doubles alike at index and query time, so analyzed searches look fine apart from the collisions below (TermQuery("e--mail") finds the document). The term is wrong wherever it meets a string built outside the analyzer: an application-built TermQuery or terms filter on the joined key (TermQuery("e-mail") finds nothing), stored or exported joined values, term facets, terms enumeration and display. A non-ASCII separator puts a control character (U+2013 to U+0013) or invalid UTF-8 (U+00B7 to b7) into the index.
• Collisions. The doubled form is ambiguous: the single token e-mail and the tokens e, a removed stop word, mail give the same term e--mail with the default preservePositionIncrements=true; a plain join keeps them apart (e-mail vs e--mail). So with one analyzer on both sides an analyzed query can match an extra document: with a whitespace tokenizer, a stop filter for the and ConcatenateGraphFilter('-', true, 100), the query e the mail finds the document e-mail (both e--mail, 1 hit). Neither encoding is injective: the doubling keeps e-mail apart from e, mail but merges it with e, hole, mail; a plain join does the reverse.
• Silent in production. With assertions off nothing throws, apart from two per-document rejections: the narrow char-view exception, and a token that the doubling pushes over the 32,766-byte term limit. With assertions on (test runs) a non-ASCII separator fails every stream, and inside IndexWriter the first document closes the writer.
• How likely. It needs an opt-in separator plus matching characters, and the wrong term shows only outside analyzed matching; the recorded searches (2026-10-26) found no report since 8.4.0 (2019). No scale is needed: one document, one or two tokens.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError
       org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter$EscapingTokenStreamToAutomaton.<init>(ConcatenateGraphFilter.java:260)
       org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter.toAutomaton(ConcatenateGraphFilter.java:235)
       org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter.toAutomaton(ConcatenateGraphFilter.java:222)
       org.apache.lucene.analysis.miscellaneous.ConcatenateGraphFilter.incrementToken(ConcatenateGraphFilter.java:164)
       org.apache.lucene.analysis.miscellaneous.TestConcatenateGraphNonAsciiSeparator.testEnDashSeparator(TestConcatenateGraphNonAsciiSeparator.java:35)

• The contract. Class javadoc: "Concatenates/Joins every incoming token with a separator into one output token for every path through the token stream" (ConcatenateGraphFilter.java:40-41). Constructor: "@param tokenSeparator Separator to use for concatenation. Can be null, in this case tokens will be concatenated without any separators." (:101-102); the type is Character. Factory: "tokenSeparator: Separator to use for concatenation" (ConcatenateGraphFilterFactory.java:28-30), and getCharacter accepts any one-char string (:81-94); a supplementary character is rejected. Nothing documents escaping or an ASCII-only rule.
• The escaper was written for the internal label. Its javadoc: "Just escapes the {@link #SEP_LABEL} byte with an extra." (:253); the comment at :237-238 ties escaping to the "stolen" internal byte. It came from the suggester (LUCENE-8332: f9f5e837450 on the main line, first released in 8.0.0, and its branch_7x cherry-pick 9b61121ffb6 in 7.4.0), when only U+001F was ever passed; LUCENE-9018 (e466d622c81) changed EscapingTokenStreamToAutomaton(SEP_LABEL) to EscapingTokenStreamToAutomaton(tokenSeparator) and the remap label from sepLabel to tokenSeparator.
• The tests assert plain joins. testSeparator (' ', "not \u001F"), testSeparatorWithStopWords (B-C-F-H), testSeparatorWithStopWordsAndPreservePositionIncrements (-B-C---F--H), testSeparatorWithSynonyms (three words synonym-another-keyword) and the factory's testSeparator. None puts the separator inside a token or uses a non-ASCII separator; all pass with the fix.
• The discussion. #10061 (LUCENE-9018, 9 comments) covers the parameter name, preserveSep and back-compat; nothing on escaping or non-ASCII separators. In LUCENE-8332's review a reviewer wrote that SEP_LABEL "should only be used internally"; LUCENE-5030 chose U+001F so that it "survives to UTF8 as a single byte to keep replaceSep [relatively] simple": the one-byte assumption a non-ASCII separator breaks.
• Sibling filters append their separator verbatim: ShingleFilter.java:280, FixedShingleFilter.java:138-162, FingerprintFilter.java:172.
• Util.toBytesRef says "you must ensure the int values fit into a byte" (Util.java:786); the separator label at :309 does not.

"The doubling is intended escaping." LUCENE-9018 did route the custom separator through the escaper on purpose; the filter's stated use is "fast analyzed exact-match lookup" (CHANGES, LUCENE-8332), where a doubled form is self-consistent at index and query time; and the class is @lucene.experimental. The verifiers rated this moderate, for the doubling only.

Why it is weak, but not settled: nothing documents or tests the doubling, and there is no unescape. That the doubled form cannot be decoded (e-mail collides with e, hole, mail, and ["e-", "mail"] with ["e", "-mail"], both e---mail) does not prove intent either way: the default escape is not injective with holes either (the single token a\u001fb and the tokens a, hole, b both give 61 1f 1f 62). The stronger point is what the escape protects. It exists for the in-band label U+001F; with a custom separator that label is no longer escaped and turns into the separator (a\u001fb c gives a-b-c), while a character that never needed escaping is doubled. That is what a mechanical substitution looks like, not a designed escape. With the default separator a single token holding U+001F also changes, by design; with - the single token e-mail changes to protect nothing.

"Non-ASCII separators are unsupported." No such rule exists: the API takes a Character and the factory any one-char string. The only upfront guard is a private assert from 2018 written for U+001F, and an assert is not argument validation: with assertions off the filter writes a different character or invalid UTF-8.

Verdicts. The finder, the independent reproduction, the intended-behaviour check, the adjudication and the intended-lens GPT review called the bug real; the refute-lens GPT review said not real only because it could not run Java. Every review rejected an intent defence for the non-ASCII half. For the ASCII doubling, the GPT lenses, the intended-behaviour check, the adjudication and the cross-model fact check of this doc rated the intent case moderate. Suggested framing upstream: the non-ASCII half is a clear defect; the doubling is undocumented behaviour that needs a maintainer decision (fix it, or document it).

Option A was validated through gradle; B and C are alternatives a maintainer may prefer; D is a workaround for users today.

In toAutomaton, use EscapingTokenStreamToAutomaton(SEP_LABEL) only when the separator is the default SEP_LABEL; any other separator gets the plain TokenStreamToAutomaton. In replaceSep, emit the separator as one label when it is ASCII or the automaton is unicode-aware, and otherwise as the chain of its UTF-8 bytes through added states (their transitions are added after the copy loop, because Automaton takes each state's transitions in one run). The regression test: the doc's test, added to TestConcatenateGraphFilter.

-    if (tokenSeparator != null) {
-      tsta = new EscapingTokenStreamToAutomaton(tokenSeparator);
+    if (tokenSeparator != null && tokenSeparator == SEP_LABEL) {
+      // Only the internal SEP_LABEL byte needs escaping; a custom separator is written as given
+      tsta = new EscapingTokenStreamToAutomaton(SEP_LABEL);
 ...
-            result.addTransition(state, t.dest, tokenSeparator);
+            int from = state;
+            for (int k = 0; k < sepLabels.length; k++) {
+              int to = k == sepLabels.length - 1 ? t.dest : result.createState();
+              if (k == 0) {
+                result.addTransition(from, to, sepLabels[k]);
+              } else {
+                pending.add(new int[] {from, to, sepLabels[k]});
+              }
+              from = to;
+            }
 ...
+  private static int[] separatorLabels(Character tokenSeparator, boolean unicodeAware) {
+    if (tokenSeparator == null) {
+      return null;
+    }
+    if (unicodeAware || tokenSeparator < 0x80) {
+      return new int[] {tokenSeparator};
+    }
+    BytesRef utf8 = new BytesRef(String.valueOf(tokenSeparator));
+    int[] labels = new int[utf8.length];
+    for (int i = 0; i < utf8.length; i++) {
+      labels[i] = utf8.bytes[utf8.offset + i] & 0xFF;
+    }
+    return labels;
+  }

Trade-offs

• Only chains with a custom separator change: their terms lose the doubling, and non-ASCII separators become valid UTF-8. An index must be reindexed for exact lookups to match again only where its stored terms change: a custom separator that occurs inside tokens, or a non-ASCII separator. An ASCII separator that never occurs inside a token gives the same terms as before (the new-york control). The CHANGES entry should say so. The default separator (still escaped) and null behave as before, although the patch touches their path too (replaceSep builds a one-element label array and an empty list). No upstream test fails.
• A plain join is not injective: after the fix the single token e-mail and the tokens e, mail both give e-mail, as with ShingleFilter or FingerprintFilter. The default separator is not an unambiguous key either: the single token a\u001fb and the tokens a, hole, b both give 61 1f 1f 62, stock and with the fix.
• An unpaired surrogate as separator is written as U+FFFD (ef bf bd), because UnicodeUtil replaces it; new BytesRef(CharSequence) documents that its input must have no unpaired surrogates, so this relies on the implementation, and a maintainer may prefer to reject surrogates in the constructor and factory.
• Neighbouring in-band label cases, unchanged by the fix and out of scope here: with a custom separator an in-token U+001F turns into the separator (a\u001fb c gives a-b-c); with null an in-token U+001F is dropped (a\u001fb gives ab); with any separator an in-token U+001E is read as a hole and dropped (a\u001eb gives ab).
• Cost: one small array and one list per replaceSep call, and extra states only for multi-byte separators. Not benchmarked.

What the checks validated

• Scratch worktree at a9779ef3c193, gradle 9.8.1, JDK 25.0.3, seed DEADBEEF: with the fix and the three repro classes added, :lucene:analysis:common:test and :lucene:suggest:test (both whole modules) with assertions on and off: analysis-common 342 classes, 1,929 tests, 1 failure, 18 skipped; suggest 31 classes, 236 tests, 0 failures, 7 skipped.
• The 1,929 are the module's 1,909 upstream tests, none failing (18 of them skipped; among the rest TestConcatenateGraphFilter 12 of 12 and TestConcatenateGraphFilterFactory 6 of 6), plus the doc's test (5 of 5), the finder's (6 of 6) and the reproducer's (8 of 9). The one failure is the reproducer's diagnostic, which pins today's collision (expected:<[[65 2d 2d 6d 61 69 6c]]> but was:<[[65 2d 6d 61 69 6c]]>): the fix removes it, as intended.
• Static checks: :lucene:analysis:common:check -x test with the fix and the doc's test passes (checkGoogleJavaFormat, ecjLint, forbiddenApis); the final files are format-clean (format.log shows that tidy ran; no before/after copy was kept).
• With the standalone runner (fix shadowed on main ea57360912ed): the doc's test passes 5 of 5 with assertions on and off, and the char-view probe no longer sees the over-read (the U+00F7 term is the valid UTF-8 61 62 c3 b7, no exception). Earlier, the finder's sketch of the same idea, combined with two sibling fixes of its hunt unit, passed 136 upstream tests of the filter, its factory, TestGraphTokenizers and the suggest module.

The same toAutomaton change as A, plus an IllegalArgumentException in the constructor (and so in the factory) for a separator above U+007F.

Trade-offs

• Smaller: no automaton change.
• Narrows the documented contract (a Character; any single character in the factory), and configurations that use a non-ASCII separator today fail when the analyzer is built.
• Not run.

A javadoc sentence ("occurrences of the separator inside a token are doubled") plus A's UTF-8 labels.

Trade-offs

• The escaper doubles single bytes, so doubling a multi-byte separator inside tokens would need new code.
• Weak: the in-band U+001F stays unescaped while a harmless character is doubled, and a single token still changes.
• Not run.

Use the default separator (escaped correctly) or an ASCII separator that cannot occur inside a token, and no non-ASCII separator.

Trade-offs

• A visible separator may be what the application needed; the default U+001F is a control character.

Method: bounded-exhaustive translation validation (the study's "semi-formal" tier), hunt unit "completion suggester indexing", main ea57360912ed, 2026-10-26. No model checker, SMT solver or prover was involved.

• A harness ran the stock main jar on every token graph of up to 3 positions (holes, 1-2 stacked tokens per position, an optional trailing hole) over the alphabet a, b, ab, the empty token, a\u001fb, a-b, U+1F600 and U+00E9, with the separators U+001F, null, -, space and U+00B7, and compared the emitted terms with a reference that joins the tokens with the configured separator and escapes nothing: 1,041,120 join checks, 889,575 mismatches with assertions off.
• The mismatches were bucketed. Two buckets are this bug: a custom separator doubled inside a token (100,896) and the non-ASCII separator U+00B7 (191,589 invalid-UTF-8 results with assertions off; 208,224 AssertionErrors with them on). The others are the default separator's intended escape (100,896, which the no-escape reference does not model), a separate empty-token finding (245,958), an in-token U+001F dropped with null (97,176), and "OTHER" buckets (153,060) whose examples are an in-token U+001F turned into the custom separator, alone or mixed with the empty token (out of scope); a separate maxGraphExpansions check had 41,780 mismatches of its own. A clean run without the empty token, U+001F or - inside tokens and with ASCII separators only gave 0 join mismatches in 178,416 checks.
• An AI finder reduced it to the public-API JUnit test and wrote a fix sketch; independent AI tools reproduced, argued and judged it (see the checks).