WordDelimiterGraphFilter catenation covers a part it skipped when the first part starts with an ALPHANUM character or an emoji

With CATENATE_WORDS or CATENATE_NUMBERS, WordDelimiterGraphFilter adds a token that glues neighbouring parts of one kind together and places it over exactly those parts. When a catenation run starts with a part whose first character is typed ALPHA|DIGIT, that breaks. Every supplementary character (an emoji, a CJK Extension B letter) gets that type, and so does any character mapped to ALPHANUM in the type table, such as # to keep hashtags whole. Such a run never ends at a part of the other kind: the part is neither added nor allowed to close the run. So #hot-sale-50 gives #hotsale with position length 3, covering 50, which it does not contain, while xhot-sale-50 gives xhotsale over 2 positions. QueryBuilder turns that path into a single-term alternative, so the phrase #hot-sale-50 also matches #hot-sale-49 and #hot-sale: 3 of 5 test documents instead of 1. With CATENATE_NUMBERS, #x-ab-12 indexes the extra term #x12. It has been there since the filter was added in 6.5.0 (LUCENE-7619, 2017); the run logic comes from the 2010 WordDelimiterFilter rewrite, and the deprecated filter emits the same wrong catenations (#x12, and #hotsale from #hot-12-sale). Ending a run at a part it will not absorb (one condition, in both filters) fixes it; the whole analysis module passes with that change.

• Parts: the filter splits #hot-sale-50 into the word parts #hot, sale and the number part 50, at positions 0, 1, 2 (with GENERATE_WORD_PARTS | GENERATE_NUMBER_PARTS).
• Run and catenation: with CATENATE_WORDS, a run of neighbouring word parts is glued into one extra token (#hotsale) whose position length should cover exactly those parts; CATENATE_NUMBERS does the same for number parts.
• Type: each part is typed by its first character (WordDelimiterIterator.java:190-204): ALPHA (letters), DIGIT, or both. Characters below the type table's length come from the table (256 entries by default; a factory-built table can be longer); getType types the others, and it types every UTF-16 surrogate, so every supplementary character, ALPHA|DIGIT (:302-307, :342-343, "prevent splitting"). ALPHANUM (:36) is the same value, and the factory's types option accepts it (WordDelimiterGraphFilterFactory.java:195). A table passed to the constructor may hold any byte, so any entry with an alpha bit and the digit bit acts the same.

1. concatenate() sets a run's type from its first part only (WordDelimiterGraphFilter.java:576-584).
2. The run is flushed only when (concat.type & wordType) == 0 (:286-289); a part joins only if shouldConcatenate(wordType): CATENATE_WORDS and an alpha bit, or CATENATE_NUMBERS and the digit bit (:292-294, :555-558).
3. A run typed ALPHA|DIGIT overlaps every part, so it is never flushed. With one CATENATE flag, a part of the other kind (50) is not added, yet the run stays open; the part is still emitted and advances the position (:302-305).
4. At the next or the final flush (:309-312), write() places the run from its start to the current position (:618-621), so it also covers the skipped part. Later parts of the run's kind are appended across the gap (#hot-12-sale gives #hotsale).
5. QueryBuilder.analyzeGraphPhrase makes every graph path a SHOULD clause (QueryBuilder.java:566-583); the path through #hotsale[0,3) is one term, so the phrase gets an alternative that does not require 50.

"words" is GENERATE_WORD_PARTS | GENERATE_NUMBER_PARTS | CATENATE_WORDS, "numbers" the same with CATENATE_NUMBERS. With both CATENATE flags the glued token contains every part it covers, so that combination is not claimed as a graph error. The deprecated WordDelimiterFilter has the same flush line (WordDelimiterFilter.java:336-337) and emits #x12, the emoji-plus-12 term and, with CATENATE_WORDS, #hotsale from #hot-12-sale as well (it sets no position lengths).

• Who is exposed. Applications that run WordDelimiterGraphFilter with CATENATE_WORDS or CATENATE_NUMBERS: directly, through the wordDelimiterGraph SPI factory, or through a search server's word-delimiter-graph filter built on it. Both flags are off by default, so it is opt-in.
• What it takes. A token kept whole by the tokenizer (the javadoc recommends WhitespaceTokenizer) in which a catenation run starts with a part that begins with a supplementary character (emoji, CJK Extension B, mathematical alphanumerics) or with a character mapped to ALPHANUM (a hashtag # or a mention @ kept on its word), followed by a part of the other kind: #hot-sale-50, 🔥-ab-12, #hot-12-sale. At least two parts must join the run in total, before or after the skipped part (#hot-12-sale: #hot before 12, sale after it); a one-part run writes no catenation when parts are generated.
• Index time. Wrong extra terms: #x12 from #x-ab-12 (CATENATE_NUMBERS), #hotsale from #hot-12-sale (CATENATE_WORDS). Word and number parts themselves are not dropped: none in 1,499,520 exhaustive checks over every flag set with a CATENATE flag; where both GENERATE flags were set, the checks also compared their positions, and none moved.
• Query time, with catenation in the query analyzer: phrase queries gain an alternative that drops a part and over-match (3 of 5 documents instead of 1). Position length is not indexed, so the position-length-only case changes no indexed term. FlattenGraphFilter consumes it: on these examples it keeps every position, but it can change the glued token's end offset (next item).
• Offsets. With adjustInternalOffsets, the filter ends the glued token's offsets at the last part it appended, so they cover a skipped part only when a later part is appended across it: #hot-12-sale gives #hotsale offsets 0-12, over 12, while #hot-sale-50 gives 0-9. After FlattenGraphFilter at index time, #hot-sale-50 also gives 0-12, over 50. With fix A: 0-9 after flattening, and no #hotsale for #hot-12-sale.
• Scale and versions. Deterministic and independent of index size; no error. Every release from 6.5.0 to 10.5.2 and main: the root-cause lines are in all 74 tagged releases, and the probe fails on 19 releases, among them the 9 untagged ones from 8.8.2 to 8.11.4.
• How likely. Rare: it needs the opt-in flags and that token shape, and nobody has reported it since 2017.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: term 0 expected:<#x[]> but was:<#x[12]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.apache.lucene.tests.analysis.BaseTokenStreamTestCase.assertTokenStreamContents(BaseTokenStreamTestCase.java:262)
       org.apache.lucene.tests.analysis.BaseTokenStreamTestCase.assertTokenStreamContents(BaseTokenStreamTestCase.java:513)
       org.apache.lucene.tests.analysis.BaseTokenStreamTestCase.assertTokenStreamContents(BaseTokenStreamTestCase.java:598)
       org.apache.lucene.tests.analysis.BaseTokenStreamTestCase.assertTokenStreamContents(BaseTokenStreamTestCase.java:622)
       org.apache.lucene.tests.analysis.BaseTokenStreamTestCase.assertTokenStreamContents(BaseTokenStreamTestCase.java:689)
       org.apache.lucene.analysis.miscellaneous.TestWordDelimiterGraphFilterAlphanumCatenation.testCatenateNumbersJoinsOnlyAdjacentParts(TestWordDelimiterGraphFilterAlphanumCatenation.java:32)

• The javadoc. CATENATE_WORDS: "maximum runs of non-numeric subwords are catenated and produced at the same position of the last subword in the run". CATENATE_NUMBERS "works like CATENATE_WORDS, but for adjacent digit sequences". The class produces "a correct token graph so that e.g. PhraseQuery can work correctly when this filter is used in the search-time analyzer" (WordDelimiterGraphFilter.java:38-40, :67-76). #hotsale[0,3) ends at 50, not at the last part of its run; #x12 glues parts that are not adjacent; the phrase over-matches. Under any reading of ALPHA|DIGIT (word, number or both), a glued token must not cover a part it does not contain.
• The type is legitimate input. The surrogate typing exists to keep a surrogate pair from being split ("prevent splitting", SOLR-1078, 2009, whose tests set no CATENATE flag). Upstream testSplits covers supplementary input ("don't split supplementaries into unpaired surrogates", TestWordDelimiterGraphFilter.java:218-219). The factory documents the types option and parses ALPHANUM; SOLR-2059, which added the option in 2010, mapped \u200D => ALPHANUM in its test types file.
• Position length is what this filter is for. LUCENE-7619 added it "just like WordDelimiterFilter except it produces correct token graphs so that proximity queries at search time will produce correct results" (lucene/CHANGES.txt:8407-8410). Upstream fixed another graph defect of the filter as a bug (LUCENE-8395, a spurious hole with PRESERVE_ORIGINAL, listed under Bug Fixes in 7.5.0) and changed its token order twice as improvements (LUCENE-9006 and LUCENE-9458).
• Nothing pins the current output. No upstream test checks the output for such input. testRandomStrings and testRandomHugeStrings do feed random text, supplementary characters included, through random flags, but only check token-stream consistency and skip position length ("TODO: properly support positionLengthAttribute", TestWordDelimiterGraphFilter.java:703-756); the slowWDF reference of testRandomPaths types surrogates as delimiters, and its random text is ASCII only (:826-837, :1105-1139); no test of the module maps a character to ALPHANUM. With the fix, all 1,913 tests of the module pass.

The checkers built the strongest case for "intended": (a) the flush test is bitwise on purpose, an ALPHA|DIGIT part is meant to be compatible with both run kinds, and with both CATENATE flags the output is self-consistent (#xab12[0,3)); (b) the logic is inherited unchanged from WordDelimiterFilter (2010), and LUCENE-8730 made the two filters' output identical except for position length; (c) the ALPHANUM constant is commented "combinations: for testing, not for setting bits"; (d) a committer wrote in 2018 that the filter "is really only suitable for categorizing characters in the BMP, it just doesn't split surrogates"; (e) the javadoc suggests CATENATE options in the index analyzer, not the query analyzer.

Why it fails: (a) explains why such a part may join either kind of run, not why a run may skip a part and still cover it; nothing in the code, comments, tests or history covers that case, and the recommended fix leaves the both-flags output exactly as it is. (b) Parity explains the identical #x12 in the deprecated filter, but position length is precisely the attribute that is wrong; the fix changes both filters, so parity stays. (c) The class itself returns ALPHA|DIGIT for every surrogate, and the factory's public parser accepts ALPHANUM. (d) The type-table trigger is plain ASCII, and the 2018 thread was about BMP symbols deleted as delimiters, not catenation. (e) The javadoc calls index-only catenation "One way", promises a correct graph in the search-time analyzer, and the wrong extra terms are an index-time effect anyway. Every checker rejected the case; the cross-model reviews and the adjudication rated it moderate.

Option A was applied in a scratch worktree of main a9779ef3c193 and run through gradle with assertions on and off; option B is the finder's sketch, run through the repro harness only; option C was not run.

In WordDelimiterGraphFilter.bufferWordParts (WordDelimiterGraphFilter.java:287) and in WordDelimiterFilter.incrementToken (WordDelimiterFilter.java:337), also flush the pending run when shouldConcatenate(wordType) is false. The WDGF hunk is the one-line root-cause change the independent reproducer ran.

What it changes, by code. With only CATENATE_WORDS, a run starts only with a part that has an alpha bit; if its type is exactly ALPHA, "overlaps the run" and "will be absorbed" are the same test, so nothing changes; likewise for CATENATE_NUMBERS and DIGIT. With both flags, shouldConcatenate is true for every part, so the new clause never fires. Output therefore changes only when one CATENATE flag is set and the run's first part is typed ALPHA|DIGIT; the both-flags output (#xab12[0,3)) stays.

New output. #hot-sale-50 and 🔥hot-sale-50 give the glued token over 2 positions; #hot-12-sale gives no catenation (as xhot-12-sale); #x-ab-12 and 🔥-ab-12 with CATENATE_NUMBERS give none, in both filters; the phrase #hot-sale-50 builds body:"#hotsale 50" body:"#hot sale 50" and finds 1 of 5.

-        // do we already have queued up incompatible concatenations?
-        if (concat.isNotEmpty() && (concat.type & wordType) == 0) {
+        // do we already have queued up incompatible concatenations? A run also ends at a subword it
+        // will not absorb: a run that starts with an ALPHA|DIGIT subword overlaps both kinds
+        if (concat.isNotEmpty()
+            && ((concat.type & wordType) == 0 || shouldConcatenate(wordType) == false)) {
           flushConcatenation(concat);
         }

Trade-offs

• Indexed terms change only for the affected token shapes; an index built before the fix keeps the old terms until reindexed.
• The wrong CATENATE_NUMBERS terms disappear from the deprecated filter too, which keeps the LUCENE-8730 output parity; fixing only WordDelimiterGraphFilter would break it.
• Without both GENERATE flags, fix A also changes positions in some outputs, and with PRESERVE_ORIGINAL the original's position length: in 240 outputs with one GENERATE flag a later part moves one position, because fix A writes a part the stock run had absorbed as its own one-part catenation (U+1F600a1a1 with GENERATE_NUMBER_PARTS | CATENATE_WORDS | SPLIT_ON_NUMERICS); with CATENATE_WORDS | PRESERVE_ORIGINAL, U+1F600-1-a gets an original of position length 2 instead of 1, as a-1-a has. No oracle judges these configurations.
• The new test pins fix A's output; the part that holds under any reading is only that no catenation covers a part it does not contain or joins parts that are not adjacent. With option B or C its expected tokens change.

What the checks validated

• The 4 new tests pass; upstream TestWordDelimiterGraphFilter (28) and TestWordDelimiterFilter (16) pass; assertions on and off (stock: the 4 new tests fail).
• All of :lucene:analysis:common:test with assertions on: 340 classes, 1,913 tests, 18 skipped, 0 failures.
• :lucene:analysis:common:check -x test passes (google-java-format, ecjLint, forbiddenApis, licenses).
• Through the repro harness: the finder's repro passes 5 of 5 and the independent reproducer's suite 10 of 10.
• The hunt's exhaustive check (every string up to length 6 over a, A, 1, -, U+1F600, every value of the 9 flags below IGNORE_KEYWORDS (0 to 511), 9,999,360 checks; the span oracle judges configurations with both GENERATE flags): stock 40,128 offset and 44,968 span violations, fix A none. Over a, A, 1, -, ', s (28,664,832 checks, also compared with upstream's slowWDF reference): no mismatch on stock or with fix A, so ASCII behaviour does not change.
• Everything it changes (after the fact checks): the full output of every string up to length 5 over a, A, 1, -, U+1F600 for every flag value from 0 to 511, stock against fix A: 15,024 of 1,999,360 outputs change, all with the emoji and none with both CATENATE flags; no output loses a part. Where the emoji stands alone between hyphens, fix A's output equals the stock output of the ASCII analog (emoji replaced by a under CATENATE_WORDS, by 1 under CATENATE_NUMBERS) in all 47,616 comparable cases (stock: 4,512 differ).

In concatenate(), also concatenation.type &= iterator.type() (except for the catenate-all run), so a run started by an ALPHA|DIGIT part becomes a word run or a number run once a second part joins. Run through the repro harness: the finder's repro 5 of 5, upstream TestWordDelimiterGraphFilter 28 of 28, the exhaustive check with no mismatch, and the new test 4 of 4.

Trade-offs

Also changes the both-flags output, #x-ab-12 to #xab[0,2) instead of #xab12[0,3), a change of indexed terms for a configuration whose output is self-consistent today (a semantic choice for upstream); and the sketch leaves the deprecated filter emitting #x12.

Type a surrogate pair by Character.getType(codePoint) instead of ALPHA|DIGIT.

Trade-offs

Fixes only the supplementary trigger, not the ALPHANUM type-table trigger; changes splitting for every supplementary character (an emoji is OTHER_SYMBOL, which getType types as a delimiter in its default branch, so emoji would be dropped); and the iterator works on UTF-16 chars, so it is a larger change.

• Method (semi-formal): bounded-exhaustive translation validation of the stock main jar, in the hunt's unit on analysis graph filters. Every string up to length 6 over a, A, 1, - and U+1F600, as one token, with every combination of the 9 flags below IGNORE_KEYWORDS (flag values 0 to 511): 9,999,360 checks.
• Oracle, taken from the class javadoc and independent of the code: when both GENERATE flags are set, a token spanning positions [p, p+len), other than the preserved original, must equal the parts at those positions glued together. Further checks covered graph invariants, offsets with adjustInternalOffsets, and agreement with upstream's slowWDF reference.
• Signal. 44,968 span violations and 40,128 offset violations, all on texts with a supplementary character; the 28.7 million checks without one found none and matched the reference exactly.
• Root cause by reading the run-flush test and WordDelimiterIterator.getType, which also showed that a character mapped to ALPHANUM gives the same type. The finder then wrote the public-API JUnit and the fix sketch; independent checkers followed (see "Independent checks").