SimplePatternTokenizer and SimplePatternSplitTokenizer retry a failed match in the middle of an emoji, so 🔥hot is indexed as U+FFFD + hot and so🔥hot is cut in two

SimplePatternTokenizer and SimplePatternSplitTokenizer read their input one code point at a time, so an emoji is one step of the automaton even though it is two Java chars ("The runDFA operates in Unicode space, not UTF16", SimplePatternTokenizer.java:114). When a match attempt that started at such a character fails after reading further, the false-alarm branch pushes back all but one char of what it read (pushBack(tokenUpto - 1), :155; pushBack(sepUpto - 1), SimplePatternSplitTokenizer.java:166), so the next attempt starts at the emoji's low surrogate, which the reader returns as a code point of its own.

If another part of the pattern accepts that half, typically a negated class that excludes the emoji or a range that reaches into the surrogate block (such as [\u0080-\uFFFF]; the pattern need not name a supplementary character), the tokenizer emits a token that starts inside the pair (\uDD25hot [1,5) instead of hot [2,5)), or an extra token made of half the emoji; the split tokenizer ends a token after the first half (so\uD83D) and loses the word so🔥hot. The index stores the lone halves as U+FFFD, so exact-term searches for the affected words miss. The line is in the classes' first commit (6.5.0) and fails on every release run, up to 10.5.2 and main. The fix changes two lines per class: push back all but the first code point.

SimplePatternTokenizer.incrementToken() (SimplePatternTokenizer.java:104-162 at a9779ef3c193) on 🔥hot deal, whose UTF-16 units are 0:D83D 1:DD25 2:h 3:o 4:t 5:space 6:d 7:e 8:a 9:l:

1. Read one code point and start the automaton (:116, :121). nextCodePoint() (:242-253) sees the high surrogate and joins it with the next unit (:248-249), so ch = U+1F525 and two units are in the term buffer. step(0, U+1F525) is live (it begins 🔥[0-9]+) but not accepting.
2. Look ahead (:126-139). h is not a digit, so the automaton dies. Nothing was accepted and the input did not end: the false-alarm branch (:153-156).
3. The false alarm rewinds by chars. pushBack(tokenUpto - 1) (:155, tokenUpto = 3 units) pushes back U+DD25 and h; the next line, tokenUpto = 0 (:156), discards the high surrogate already read, so the next try starts at offset 1, inside the pair. The comment says "push back all but the first character we scanned", but the first thing scanned was a two-unit code point.
4. The retry starts inside the pair. The next nextCodePoint() reads U+DD25, which is not a high surrogate, so it is returned as the code point U+DD25 (:248-252). Lucene RegExp negated classes are any code point from 0 to 0x10FFFF minus the listed ones (RegExp.java:1302, Automata.java:105-106), so [^🔥 ] accepts it, and the token is \uDD25hot [1,5) (:141-150).
5. The other no-match branch does it right. When the first step already fails (state == -1, :158-160), the whole code point is dropped: with [^🔥 ]+ alone both units of 🔥 are skipped and the next try starts at h. So whether 🔥 is stepped over correctly depends on whether some alternative can start with it.

SimplePatternSplitTokenizer (SimplePatternSplitTokenizer.java:99-170) looks for separators the same way, and every code point that does not start one stays in the pending token (:213-220). On so🔥hot now the try at 🔥 starts 🔥!, dies at h, and pushBack(sepUpto - 1) (:163-167) leaves so\uD83D in the pending token (here the high surrogate is kept). The retry reads U+DD25, which [^a-z🔥]+ accepts as a one-unit separator, so so\uD83D [0,3) is emitted and hot [4,7) starts a new token.

All three are needed; naming a supplementary character is not. (a) An attempt that starts at a supplementary character goes live and then dies after reading further, before the end of the input: some alternative starts with the character, by naming it (🔥[0-9]+, 🔥[a-z]+, 🔥!, 🔥🔥) or through a class that contains it followed by more (.[0-9]+, [^a-z ][0-9]+, [^ ]+!). (b) Nothing was accepted in that attempt: a top-level . or [^ ]+ accepts the whole character, so the longest match is the token and no retry happens (😀ab|. on 😀x and 🔥[0-9]+|[^ ]+ are correct). (c) Another part of the pattern accepts a match that starts with the exposed low surrogate: a negated class that excludes the character ([^🔥 ]), any range that reaches into the surrogate block U+D800-U+DFFF (the common "non-ASCII" [\u0080-\uFFFF], or [\u3000-\uFFEF]), or a hand-built automaton that accepts surrogate code points. (\uXXXX here stands for the character itself, as a Java string literal gives it; Lucene RegExp rejects \u as an escape.)

Executed on main without naming any supplementary character (the doc's fact and diagram checks): .[0-9]+|[\u0080-\uFFFF]+|[a-z]+ on 🔥hot deal gives an extra \uDD25 [1,2) before hot, deal; [^ ]+!|[\u3000-\uFFEF]+ on 🔥中 b gives \uDD25中 [1,3) where PatternTokenizer gives 中 [2,3); the split tokenizer with [\u0080-\uFFFF]+|.! cuts so🔥hot now into so\uD83D, hot now. With the fix the diagram check's cases are correct.

If any of the three fails, the tokens are correct: a retry at the low surrogate that accepts nothing ends at the next code point, as a code-point retry would (:153-160). Executed correct: [^🔥 ]+ alone, 🔥[0-9]+|[^ ]+ and .[0-9]+|[a-z]+. The hunt's 39-pattern pool had no explicit range reaching into the surrogate block (its negated classes contain the block), so its counts say nothing about the range shapes: its 13,741 lone-surrogate mismatches per tokenizer were recorded (one example per class and pattern) only for the 2 pool patterns that meet all three conditions, while 3 more patterns that name the emoji were correct. When the try reaches the end of the input instead, another branch runs (:151-152): that is the sibling bug LFV-525.

• Who is exposed. Users of either tokenizer, directly or through the factories (SPI names simplePattern and simplePatternSplit, for example in CustomAnalyzer or a Solr schema), or through downstream tokenizers built on them, whose pattern has the shape above. A typical intent: keep an emoji-plus-something token such as 🔥5, and otherwise strip the emoji from words.
• Opt-in. Both classes and factories are @lucene.experimental, and no Lucene analyzer uses them by default.
• What it takes. With such a pattern, ordinary text triggers it every time the character is not followed by the rest of a live alternative and the try does not reach the end of the input: the emoji right before a word (🔥hot) or a space (🔥 x), or inside a word for the split tokenizer (so🔥hot). 🔥5, where the alternative matches, is tokenized correctly.
• Effect. Silent wrong tokens with offsets inside a surrogate pair, at any index size, with assertions on or off: an extra junk term (U+FFFD), the next word indexed under a U+FFFD-prefixed term (a search for the word misses the document), or a word cut into two terms (a search for the whole word misses, one for its tail matches). IndexWriter replaces lone surrogates with U+FFFD as documented, CheckIndex stays clean, and highlight snippets can contain unpaired surrogates of the document's own text. In the runs only the tokens of the value being tokenized changed. No hang was seen: in the hunt's cost probe (up to 2.4M chars, one aarch64 host) the per-char cost of stock and fixed code did not grow with input size.
• How likely. Rare, by judgement: it needs all three pattern conditions (the wider shapes found by the doc's checks were not counted), and no report since 6.5.0 (2017) was found in the public sources searched. Real deployments were not surveyed.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 2 test(s) run, 2 failed
    => org.junit.ComparisonFailure: term 0 expected:<[x]> but was:<[?]>
       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:710)
       org.apache.lucene.analysis.pattern.TestSimplePatternSurrogateRetry.testTokenizer(TestSimplePatternSurrogateRetry.java:39)
  JUnit Vintage:TestSimplePatternSurrogateRetry:testSplitTokenizer
    MethodSource [className = 'org.apache.lucene.analysis.pattern.TestSimplePatternSurrogateRetry', methodName = 'testSplitTokenizer', methodParameterTypes = '']
    => org.junit.ComparisonFailure: term 0 expected:<?[?b]> but was:<?[]>
       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)

• The code works in code points. SimplePatternTokenizer.java:114 and SimplePatternSplitTokenizer.java:111: "The runDFA operates in Unicode space, not UTF16 (java's char)". nextCodePoint() joins surrogate pairs, and the first-step-fails branch (:158-160) skips the whole code point. On well-formed text a lone surrogate exists only because the false alarm rewinds into a code point that was read whole.
• Contract (no javadoc sentence mentions surrogates, defines where a retry starts or promises code-point-aligned boundaries: that this is not intended is inferred from the code and the comparisons, not from a documented contract). Class javadoc (SimplePatternTokenizer.java:34-35): "The matching is greedy: the longest match at a given start point will be the next token." Factory javadoc (SimplePatternTokenizerFactory.java:41-43): "the longest token matching at a given point is created." The split tokenizer is "just like SimplePatternTokenizer except that the pattern should make valid token separator characters, like String.split" (SimplePatternSplitTokenizer.java:33-34).
• An unused alternative changes the tokens. Within 🔥hot deal, [^🔥 ]+ and 🔥[0-9]+|[^🔥 ]+ match the same substrings, yet the first gives hot, deal and the second \uDD25hot, deal. The same holds for [^a-z🔥]+ vs [^a-z🔥]+|🔥! on so🔥hot now. No start-point rule allows that.
• The documented comparisons keep the pair. PatternTokenizer (group 0) gives hot, deal and x; in split mode (group -1) and with String.split, so🔥hot now gives so🔥hot, now.
• Supplementary input is in scope. Upstream testOneToken and testNoTokens feed TestUtil.randomUnicodeString through both tokenizers (with .*, which never fails a try); no dedicated test uses a failing alternative that starts with a supplementary character. TestRandomChains can build these tokenizers from random regexps that may contain surrogate pairs, but it checks consistency and offsets, not surrogate integrity.
• Precedent. lucene/CHANGES.txt lists as bug fixes "LUCENE-8325: Fixed the smartcn tokenizer to not split UTF-16 surrogate pairs" and "GITHUB#15899, GITHUB#15900: Improve TruncateTokenFilter to truncate on codepoints not chars and no longer produce half surrogates".
• History. The false-alarm line is in the first commit (93fa72f77bd, LUCENE-7465) next to the Unicode-space comment; the issue (#8517) never discusses surrogates or where a retry starts.

The strongest case for "intended": the pattern itself accepts lone surrogate code points ([^🔥 ] does), so the tokenizer only does what the automaton allows; both classes are @lucene.experimental; buffers and offsets count chars; and the comment says "push back all but the first character".

Why it fails: on well-formed text the automaton would never see a lone surrogate if the tokenizer kept the code points it read whole; java.util.regex gives [^🔥 ] the same meaning yet keeps the pair intact on these inputs; the same loop skips whole code points on its other no-match path; and the unused-alternative example shows the output is not a function of the pattern's language. @lucene.experimental marks API instability, not permission for malformed terms. Cross-model reviews (reading only) rated the works-as-designed case weak.

The recommended change was built at a9779ef3c193 and validated with gradle in a scratch worktree (the repro, TestSimplePattern*, the pattern package, the whole analysis-common module, assertions on and off, the module's static checks and TestRandomChains), and against the stock jars with the patched classes shadowed (this doc's repro, the finder's and a verifier's). It is code-identical to the hunt's fix, which the bounded-exhaustive check showed removes exactly this mismatch class. A verifier's independent fix is the unit-count variant below, also run. Ship it together with the sibling LFV-525 fix in the same function.

surrogate-retry-fix.diff, +9/-5 over both classes: after the first step, record how many UTF-16 units the attempt's first code point has, and on a false alarm push back all but that many. The retry then starts at the next code point, as the first-step-fails branch already does.

diff --git a/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternSplitTokenizer.java b/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternSplitTokenizer.java
index 1914875560d..13704d4ce64 100644
--- a/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternSplitTokenizer.java
+++ b/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternSplitTokenizer.java
@@ -119,6 +119,8 @@ public final class SimplePatternSplitTokenizer extends Tokenizer {
         }
       }
       int state = runDFA.step(0, ch);
+      // UTF-16 length of the code point this attempt starts at
+      final int firstLen = Character.charCount(ch);
 
       if (state != -1) {
         // a token separator just possibly started; keep scanning to see if the token is accepted:
@@ -161,9 +163,9 @@ public final class SimplePatternSplitTokenizer extends Tokenizer {
             return false;
           }
         } else {
-          // false alarm: there was no token separator here; push back all but the first character
-          // we scanned
-          pushBack(sepUpto - 1);
+          // false alarm: there was no token separator here; push back all but the first code
+          // point we scanned
+          pushBack(sepUpto - firstLen);
         }
       }
     }
diff --git a/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternTokenizer.java b/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternTokenizer.java
index 61812a21ece..b67b219a8b4 100644
--- a/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternTokenizer.java
+++ b/lucene/analysis/common/src/java/org/apache/lucene/analysis/pattern/SimplePatternTokenizer.java
@@ -119,6 +119,8 @@ public final class SimplePatternTokenizer extends Tokenizer {
       }
 
       int state = runDFA.step(0, ch);
+      // UTF-16 length of the code point this attempt starts at
+      final int firstLen = Character.charCount(ch);
 
       if (state != -1) {
         // a token just possibly started; keep scanning to see if the token is accepted:
@@ -151,8 +153,8 @@ public final class SimplePatternTokenizer extends Tokenizer {
         } else if (ch == -1) {
           return false;
         } else {
-          // false alarm: there was no token here; push back all but the first character we scanned
-          pushBack(tokenUpto - 1);
+          // false alarm: there was no token here; push back all but the first code point we scanned
+          pushBack(tokenUpto - firstLen);
           tokenUpto = 0;
         }
       } else {

Trade-offs

• None found: one local per method, no new state.
• Cost: in the hunt's cost probe (-da, one aarch64 host, 300k-2.4M chars where every emoji takes the retry) the per-char cost did not grow with input size; at 1.2M and 2.4M chars 6.2-13.9 ns/char with the fix vs 13.0-19.3 on stock.

What the checks validated

• gradle at a9779ef3c193: the repro 5 of 5; TestSimplePattern* 34 tests; org.apache.lucene.analysis.pattern.* 87 tests (2 skipped); the whole analysis-common module 1,914 tests, 18 skipped, 0 failures; each with assertions on and off. check -x test (lint, forbidden APIs, formatting) passes; TestRandomChains passes with 2 seeds.
• The new upstream-suite methods pass; on stock both fail.
• Shadowed on the stock jars: this doc's repro 5 of 5 (-ea, -da), the finder's 2 of 2, a verifier's 8 of 8. The hunt's bounded-exhaustive check (4,140,572 checks): this mismatch class goes from 13,741 runs per tokenizer to 0, the sibling's end-of-input class stays; with both fixes, 0 mismatches. The same fix applied to the 6.5.0 sources passes there.

The sibling bug LFV-525 (a lookahead that reaches the end of the input without a match ends tokenization) is in the same function; both of its fix options already contain this change, and this doc's repro passes 5 of 5 with its recommended patch shadowed.

Trade-offs

If the end-of-input fix landed without this one, this bug would fire more often (15,432 instead of 13,741 runs per tokenizer in the exhaustive check), because more attempts reach the false-alarm retry.

final int firstLen = tokenUpto; (sepUpto in the split tokenizer) right after the first nextCodePoint(), then the same pushBack(... - firstLen). This is the independent fix of verifier: its own 8-test JUnit passes 8 of 8 (-ea, -da) and the upstream suites 29 of 29 on main ea57360912ed, and this doc's repro passes 5 of 5 with it shadowed on main a9779ef3c193 (-ea, -da).

Trade-offs

The same as Character.charCount(ch) on well-formed text. On malformed text (an unpaired high surrogate, which nextCodePoint() joins with the next unit unchecked) it still counts exactly the units read; that is reasoned from the code, not tested.

For patterns built in Java code, add \uD800-\uDFFF to every negated class, so a retry at a lone half dies at its first step and is skipped whole: 🔥[0-9]+|[^🔥 \uD800-\uDFFF]+ and [^a-z🔥\uD800-\uDFFF]+|🔥! give the expected tokens on all five inputs of this doc on stock main.

Trade-offs

Needs lone surrogate characters in the pattern string, which text configuration formats may not carry (not tried there); every user must know about it.

State that a failed try at a supplementary character retries at its second char.

Trade-offs

Keeps malformed terms and the unused-alternative inconsistency, when the fix is two lines per class.

Method: bounded-exhaustive translation validation (the hunt's semi-formal tier). The checker ran the real SimplePatternTokenizer and SimplePatternSplitTokenizer on all 19,531 strings of up to 6 code points over {a, b, space, -, U+1F600}, for 39 RegExp patterns (4,140,572 checks, including PatternTokenizer controls), against a reference written from the class javadoc: the greedy longest match per start point, with membership decided by java.util.regex. The mismatch class "lone surrogate in token" (13,741 runs per tokenizer) came only from the 2 pool patterns that start an alternative with the emoji and exclude it from a negated class (😀a|[^😀a ]+, 😀😀|[^😀 ]\-). Reading the code then located pushBack(tokenUpto - 1) / pushBack(sepUpto - 1). The pool had no explicit range reaching into the surrogate block, so the check did not cover the range shapes of the trigger that the doc's checks found later.

The finder then wrote a JUnit through the public constructors (2 of 2 fail on main with assertions on and off, 10.5.2 and 9.12.3) and the one-line fix, which removes exactly this class from the check. Independent checks followed (below).