SimplePatternTokenizer stops at an unclosed quote and drops every later token; SimplePatternSplitTokenizer merges them into one

SimplePatternTokenizer runs its DFA from each start point and keeps the longest accepted match; when nothing matches, it pushes back all but the first character and retries one character later (SimplePatternTokenizer.java:153-156). That retry runs only when the lookahead dies before the end of the input. When the lookahead stays alive to the end without ever accepting, as an unclosed quote does in '[^']*'|[a-z]+, the branch } else if (ch == -1) { return false; } (:151-152) ends tokenization, so don't stop me yields only don and say "hello world (with \"[^\"]*\"|[a-z]+) only say. SimplePatternSplitTokenizer has the same branch (SimplePatternSplitTokenizer.java:156-162) and emits everything from the current token start to the end as one token: separators \<[^\>]*\>|[ ]+ on x < y give x, < y. (Patterns are written as the Lucene RegExp strings that were run: in that syntax ", < and > are reserved and escaped; unescaped, those two patterns throw before tokenizing anything.) Tokenization raises no exception or warning, and end() still reports the full final offset. The branch dates from the first commit of both classes (LUCENE-7465, 6.5.0) and fails on every release run, up to 10.5.2 and main. A fix that retries at the end of the input too, with a small memo that kept many unclosed openers linear on the measured inputs, passes the module's tests.

SimplePatternTokenizer.incrementToken() (SimplePatternTokenizer.java:104-162 at a9779ef3c193):

1. It takes the next code point as a possible token start and steps the pattern's DFA (:116-121). If the DFA can start there (state != -1, :123), an inner loop reads ahead and records the longest accepted length (:126-132), until the DFA dies (:139) or the input ends (ch == -1, then break, :134-137).
2. If something was accepted, the longest match is the token (:141-150), also when the lookahead then ran into the end of the input: the scanned rest is pushed back. This accepting end-of-input path is correct on stock (its pushBack was fixed in 2017 by 2d03aa21a2b) and both fix options keep it.
3. If nothing was accepted and the DFA died, it is a "false alarm": pushBack(tokenUpto - 1) returns all but the first scanned character and the loop retries one character later (:153-156).
4. If nothing was accepted and the input ended, } else if (ch == -1) { return false; } (:151-152) ends tokenization. That assumes that no match before the end means no later token, which is false: a later start point inside the scanned run can still match a shorter string.

Pattern '[^']*'|[a-z]+, text don't stop me (13 chars; executed trace on main): start 0 accepts d, do, don and dies at the apostrophe, so don is a token. Start 3, the apostrophe, can begin a quoted phrase; [^']* keeps the DFA alive over t stop me to the end of the text, never accepting because no closing quote comes. Step 4 returns false, and starts 4-12 (t, stop, me) are never tried.

SimplePatternSplitTokenizer (SimplePatternSplitTokenizer.java:99-170) scans for separators the same way. Its end-of-input branch (:156-162) emits everything from the current token start to the end as one token, instead of the false-alarm retry (:163-166), so the separators after an unclosed < are never found: \<[^\>]*\>|[ ]+ on x < y gives x, < y. (The branch's return false arm cannot be reached from a lookahead: the scanned characters are already appended to the pending token, :213-219.)

A pattern alternative that can stay alive without accepting up to the true end of the value, plus a later start point inside that run that could match: a quoted-string, bracket or tag alternative next to a word or separator alternative (\"[^\"]*\"|[a-z]+, '[^']*'|[a-z]+, \<[^\>]*\>|[ ]+, in Lucene RegExp syntax), or abc|b, ab*c|b. A pattern made only of a quote alternative loses nothing (no later match exists inside the run). Plain character-class patterns such as [^ ]+ or [ ]+ are unaffected, and so are whitespace classes like the factories' javadoc examples when the tab, CR and LF in them are real characters (executed in the fact check). As the javadoc prints them, with backslash escapes inside the class, [^ \t\r\n]+ and [ \t\r\n]+ are rejected by RegExp ("invalid character class") on main, 10.5.2 and 9.12.3: a separate documentation matter. Tokenization raises no exception or warning; end() still reports the full final offset (:164-169).

• Who is exposed. Users of either tokenizer: directly, through the factories (SPI names simplePattern and simplePatternSplit, for example in CustomAnalyzer or a Solr schema), or through downstream tokenizers built on them (Elasticsearch's and OpenSearch's simple_pattern and simple_pattern_split; read in their sources, not run there).
• Opt-in. Both classes and factories are @lucene.experimental, and no Lucene analyzer uses them by default. The bug needs no special setting beyond a pattern of the affected shape.
• What it takes. A pattern alternative that can stay open to the end of the value (a quoted string, bracket group or tag) next to one that can match later inside it. With such a pattern, one unclosed opener in ordinary text is enough: the apostrophe in don't, a < b, the emoticon <3. Plain character-class patterns are unaffected.
• Effect. Every token after the unclosed opener is missing from the index (tokenizer) or merged into one term (split tokenizer), at any index size, with assertions on or off. Tokenization raises no exception or warning; end() reports the full offset; the stored value keeps all the text; other values, fields and documents are unaffected.
• A sharper case. The split tokenizer's merged rest is one term; past 32,766 UTF-8 bytes IndexWriter rejects the whole document as containing an immense term (non-aborting): "Bob <3 wrote: " plus 40,000 chars of words was rejected on main, 10.5.2 and 9.12.3, and is indexed with either fix option.
• How likely. Rare, by judgement: the affected pattern shape seems uncommon among simple-pattern patterns, and no report of it since 6.5.0 (2017) was found in the public sources searched. How often it appears in real deployments was not surveyed.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: token 0 does not exist
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.assertTrue(Assert.java:42)
       org.apache.lucene.tests.analysis.BaseTokenStreamTestCase.assertTokenStreamContents(BaseTokenStreamTestCase.java:257)
       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.pattern.TestSimplePatternLookaheadAtEnd.testLookaheadReachesEnd(TestSimplePatternLookaheadAtEnd.java:29)

• 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 matching is greedy such that the longest token matching at a given point is created." The class comment states the algorithm (:44-45): "on failing to match a token, we skip one character forward and try again." The split tokenizer is "just like SimplePatternTokenizer except that the pattern should make valid token separator characters, like String.split" (SimplePatternSplitTokenizer.java:33-34).
• Two no-match branches of one loop disagree. The dead-state branch retries one character later (:153-156); the end-of-input branch gives up (:151-152). No code comment, javadoc, CHANGES or MIGRATE entry explains the difference.
• The documented comparisons give the full lists. PatternTokenizer (java.util.regex) with the same regex gives don, t, stop, me and say, hello, world; in split mode (group -1) and with String.split, x < y gives x, <, y.
• Prefix-dependent output. ab*c|b gives no token on abb but b, b on abbx: whether the tokens of a prefix exist depends on whether one more character, which belongs to no token, follows. That is strong evidence the behaviour is accidental rather than a chosen rule.
• Tests do not pin it. Two upstream tests reach the no-accept end-of-input branch (a verifier found them): testBigLookahead (the literal pattern of 100 as and a b, over 200 as; start points 0-99 die, start point 100 runs to the end) and testEndLookahead ((ab)+ on aba: the first lookahead accepts ab, then the trailing a takes the no-accept branch). Neither has a later start point that could match; both pass with the fixes, as does the whole analysis-common module.
• History. The branch is in the first commit (93fa72f77bd, LUCENE-7465) without a comment. The only later fix here, 2d03aa21a2b (2017-02-21, "fix corner case in SimplePattern/SplitTokenizer when lookahead hits end of input"), handled the accepting case and added testEndLookahead; it left this branch alone. The 31 comments of LUCENE-7465 (#8517) never discuss it.

The strongest case for "intended": the end-of-input branch is explicit, symmetric code from the first commit; the classes are @lucene.experimental; the javadoc only says the longest match at a start point is the token, not that every start point is tried; and the shortcut keeps an unclosed opener to one linear scan, while retrying makes each unclosed opener rescan to the end.

Why it fails: the class's own comment says it skips one character and tries again, and the dead-state path does exactly that; output that changes when one non-token character is appended is strong evidence against a chosen rule; PatternTokenizer and String.split give the full lists; @lucene.experimental marks API instability, not permission for wrong output. The cost point is real for the minimal fix (quadratic on many unclosed openers) but not on the measured inputs of the recommended one. The class TODO (:41-53) says the naive matcher "does have N^2 adversarial cases" because it skips one character and retries, and such cases exist on stock through dead states; it does not say whether rescanning at the end of the input was considered, so it supports the retry design, not a deliberate end-of-input shortcut. None of this proves the shortcut was not a deliberate optimization, but together it makes an accident much more likely. Every check that ran code judged it a defect; the reading-only refute review said "not real" only because it could not run code, and the cross-model fact check rated the intended-behaviour case moderate for the tokenizer and weak to moderate for the split tokenizer.

Two options were built at a9779ef3c193 and validated with gradle (the repro, the pattern package, the whole analysis-common module, assertions on and off) and against the stock jars with the patched classes shadowed. Both also change the retry step from one UTF-16 unit to one code point; without that, sending the end of input into the retry would spread a separate defect of the retry path (a supplementary first character is split) to the new path. Timings: single thread, assertions off, on a shared host; up to 64,000 chars 30 warm-up runs and the best of 20 (WarmCost), the 1,024,000-char scaling 10 warm-up runs and the best of 10 (WarmScale); heap from the thread's allocation counter and used heap after GC (MemProbe).

optionB-retry-at-end-linear.diff, +113/-14 over both classes. The minimal option's change, plus a LongHashSet of (offset, state) pairs (from org.apache.lucene.internal.hppc, a package analysis-common already uses; LongHashSet itself is new there):

• when a lookahead reaches the end of the input (or a recorded pair), the tokenizer replays its buffered code points through the DFA and records every 16th pair after its last accept. No accept is reachable from such a pair: the DFA is deterministic, the rest of the input is fixed, and the earlier lookahead walked it to the end. This needs a deterministic automaton; every instance that can be constructed has one, because the Automaton constructors reject a non-deterministic one (SimplePatternTokenizer.java:97-99, SimplePatternSplitTokenizer.java:87-89) and the factories determinize;
• every later lookahead checks the set at each step, only while it is non-empty, and stops at a recorded pair as if the input ended there; a lookahead that joins a recorded path after that path's last accept stops within 16 steps;
• reset() releases the set when it is not empty.

"Linear" is measured, not proven in general: from 64,000 to 1,024,000 chars of many unclosed openers the time grows 1.50-2.15x per doubling (split tag-or-space) and 1.85-2.12x with one 3.25x step (tag-or-word). The set is keyed by (offset, state), so several states can be recorded at one offset, and no general bound on its size is established. The class's other N^2 cases remain.

// in the lookahead loop of incrementToken(); the split tokenizer is analogous
if (noAcceptAhead.isEmpty() == false && noAcceptAhead.contains(pair(offset, state))) {
  noMoreAccepts = true; // an earlier lookahead went from here to the end without an accept
  break;
}
ch = nextCodePoint();
if (ch == -1) {
  noMoreAccepts = true;
  break;
}
// after the loop: replay the lookahead, record every 16th (offset, state) after its last accept
if (noMoreAccepts) {
  rememberNoAccept(termAtt.buffer(), 0, tokenUpto, offsetStart, lastAcceptLength);
}

Trade-offs

• About 100 more lines than the minimal option, and a small set that lives until the next value.
• Inputs without an unclosed opener at the end: within noise of stock (plain words 8.7-8.9 ns/char vs 8.3-8.6; closed tags 10.1-10.4 vs 11.0-11.3, one run 15.6).
• One unclosed opener, then 200,000 chars of words: 22.8-27.4 ns/char (minimal option 13.5-17.9; stock 5.5-5.6 but 0 tokens).
• Many unclosed openers: "< " repeated to 64,000 chars 5.0 ms (minimal option 9,444 ms in this run, 5.5-9.4 s across runs; stock 0.38 ms with 1 token); to 1,024,000 chars 87 ms, about 2x per doubling.
• Heap for one 1,000,000-char value with one unclosed opener: 2.1 MB allocated and held until the next reset() (stock and the minimal option: none beyond the term buffer). Recording every pair instead of every 16th held 17.8 MB.
• The class's existing dead-state N^2 cases are unchanged ([a-z]+\@[a-z]+ on one 64,000-char word: about 10-15 s on stock and on both options).

What the checks validated

• gradle: the repro 5 of 5; org.apache.lucene.analysis.pattern.* 87 tests; the whole analysis-common module 1,914 tests, 18 skipped, 0 failures; assertions on and off. check -x test (lint, forbidden APIs, formatting) passes; TestRandomChains passes with 3 seeds.
• The new upstream-suite methods pass; on stock all 4 fail.
• Shadowed on the stock jars: the hunt's bounded-exhaustive check (1,523,418 runs of the two tokenizers, part of 4,140,572 checks with PatternTokenizer controls) 0 mismatches; its long-input check (1,560 inputs through both tokenizers, 3,120 checks, chunked reads) 0; an opener-dense random differential 0 of 32,000 (stock 6,024); the finder's and a verifier's repros and the hunt's reach probe all pass.

optionA-retry-at-end.diff, +12/-14: delete the end-of-input branch in both classes so that the lookahead takes the false-alarm path, and push back all but the first code point. The same change as the hunt's combined fix, re-made at a9779ef3c193.

final int firstLen = Character.charCount(ch); // after runDFA.step(0, ch)
...
-        } else if (ch == -1) {
-          return false;
         } else {
-          pushBack(tokenUpto - 1);
+          // false alarm (also when the lookahead reached the end of the input)
+          if (tokenUpto > firstLen) {
+            pushBack(tokenUpto - firstLen);
+          }
           tokenUpto = 0;
         }

Trade-offs

• Smallest diff.
• Each unclosed opener whose run reaches the end rescans the rest of the value, so many unclosed openers become quadratic where stock is linear (and wrong): "< " repeated to 64,000 chars takes 5.5-9.4 s on a shared host (9.4 s best of 20 here, 5.53 s in the hunt, 5.56 s in the fact check), about 4x per doubling from 8,000 chars. Quote-or-word patterns on paired quotes stay linear (only the last unpaired quote scans to the end).
• Proposing it means stating that cost. The class TODO already says the naive matcher has N^2 adversarial cases (it does not discuss the end of the input).

What the checks validated

• gradle: the repro 5 of 5; the pattern package 87 tests; the whole module 1,914 tests, 0 failures, assertions on and off; the new upstream-suite methods pass.
• Shadowed: the bounded-exhaustive check and the opener-dense differential find 0 mismatches; the reach probe passes 10 of 10.

Compile something like .* | <pattern> so that one pass finds every match, as the TODO (:46-53) suggests.

Trade-offs

Would also remove the dead-state N^2 cases, but the TODO notes it needs sub-group capture that Lucene's regexps lack; a much larger change.

State in the javadoc that tokenization ends when a lookahead reaches the end of the input without a match.

Trade-offs

Keeps the prefix-dependent output and the split tokenizer's merged term; neither fix needs it.

Method: bounded-exhaustive translation validation (the hunt's semi-formal tier). The checker ran the real SimplePatternTokenizer and SimplePatternSplitTokenizer on every string of up to 6 code points over the alphabet {a, b, space, -, U+1F600}, for 39 RegExp patterns, and compared each output with a reference written from the class javadoc and its implementation comment: the longest non-empty match at each start point, otherwise skip one code point (membership checked with java.util.regex). Of 761,709 tokenizer runs, 3,916 lost trailing tokens, and 3,916 of 761,709 split runs merged tokens, all on the patterns with a live non-accepting run before a later match. A second mismatch class (lone surrogates) is a separate bug of the retry step. (The checker's total of 4,140,572 checks also covers PatternTokenizer in three modes on the same patterns and a 17-pattern PatternTokenizer pool.)

The finder then wrote a JUnit through the public factories (3 of 3 fail on main with assertions on and off, 10.5.2 and 9.12.3) and a fix, which removes the end-of-input class from the exhaustive check; with the code-point retry as well, the check finds 0 mismatches. Independent checks followed (below).