RegexCompletionQuery: "." and negated classes match past the end of a suggestion, so "foo." returns "foo"

RegexCompletionQuery "takes a regular expression as the prefix of the query term": a suggestion should match when some prefix of it matches the regex. The document suggester stores every suggestion in its FST as the analyzed form, then a reserved end byte 0x00, then dedup bytes, and the query intersects the regex automaton with these stored inputs unchanged. In Lucene's RegExp, . covers U+0000 to U+10FFFF and a negated class is "any character" minus the class, so both can consume the end byte. Over foo (weight 5), food (1) and fox (2), foo. and foo[^x] return [foo, food] instead of [food], foo. with n = 1 returns [foo], and foo.. returns [food] instead of []; with five entries foo in one segment, foo.. returns [foo, foo]. The same happens inside ContextQuery. Nothing throws; filters, deletions and contexts still apply. Every release from 5.3.0 to 10.5.2 and main is affected. An 8-line fix in RegexCompletionQuery.createWeight (intersect the automaton with "any code point except U+0000, repeated") passes the new test and the whole lucene/suggest module.

• Document suggester. A SuggestField (or ContextSuggestField) indexed with a completion postings format. Each segment keeps an FST whose inputs are the suggestions' analyzed forms; a completion query intersects an automaton with those inputs and then collects the best-weighted suggestions below each match.
• End byte and dedup bytes. Every stored input is the analyzed form, then END_BYTE 0x00, then one dedup byte per entry (0, 1, 2, ...), which keeps several entries with the same text apart. After 3 entries of one form a second dedup byte is opened. SuggestField rejects 0x00 in values, so the end byte is never text.
• RegexCompletionQuery. "A CompletionQuery which takes a regular expression as the prefix of the query term" (RegexCompletionQuery.java:31-43, @lucene.experimental), default flags RegExp.ALL.

1. createWeight builds Operations.determinize(new RegExp(text, flags).toAutomaton(), determinizeWorkLimit) and hands it to CompletionWeight unchanged (RegexCompletionQuery.java:92-97).
2. . is Automata.makeAnyChar() = [U+0000, U+10FFFF] (RegExp.java:695-696, Automata.java:104-107); a negated class is any character minus the class (RegExp.java:1299-1302). Both contain U+0000.
3. NRTSuggesterBuilder.startTerm appends END_BYTE 0x00 to every analyzed form and finishTerm the dedup bytes (NRTSuggesterBuilder.java:43, :66-69, :81-97, :124-134). So foo is stored as f o o 00 00, food as f o o d 00 00.
4. NRTSuggester.lookup intersects the automaton with the stored inputs through FSTUtil.intersectPrefixPaths (NRTSuggester.java:131-132), which follows every arc the automaton accepts, 0x00 included, and reports the first accepting node as a matching prefix (FSTUtil.java:71-123).
5. For foo., the . takes foo's 00; the completion search from that node still finds foo (NRTSuggester.java:230-253), so foo is returned next to food.
6. Two extra characters (foo..) end on a node with nothing left after it when a form has one dedup byte; the search does not emit such an empty completion (allowEmptyString false, NRTSuggester.java:245-248, Util.java:284). With 4 or more entries of one form in a segment, the second dedup byte leaves one byte to complete, and copies of the short suggestion come back.

Every row ran on main with assertions on and off; the first eight also on 10.5.2. PrefixCompletionQuery foo gives [foo, food]. Contexts still restrict the results (executed). By code reading, filters and deleted documents are still honoured: every completed path goes through CompletionScorer.accept (NRTSuggester.java:207, CompletionScorer.java:82-92).

The test lists duplicates (suggest(query, num, false)). With duplicate suppression on, five copies give [foo] for foo.. (still not []), and foo. over foo, food and fox still gives [foo, food]; with the fix [] and [food].

Expected results are stated over the analyzed form, which is what the FST stores. Here it equals the visible text. With other analysis (token separators, position increments, stop words, graph expansion; CompletionAnalyzer.java:69-99) the analyzed form, not the visible length, decides what should match.

• Who is exposed. Users of the document suggester (SuggestField or ContextSuggestField with a completion postings format) who run RegexCompletionQuery: directly, wrapped in a ContextQuery, or through a downstream engine's completion-suggester regex option. A read-only code search found two downstream completion field mappers that pass the user's pattern to RegexCompletionQuery unchanged. The API is @lucene.experimental.
• What triggers it. A pattern that can match one more character, from a class that contains U+0000, right after a complete, shorter suggestion: a trailing ., .+ ("at least one more letter"), .{n}, or a negated class such as [^x]. Patterns that can match nothing there, such as foo.* or foo.?, give the same results with and without the fix.
• Effect. Extra, too-short suggestions, often ranked first: bar. with n = 1 over bar/10, bark/3, barn/2 gives [bar] instead of [bark]; ba... gives [bark, barn] although no suggestion has five characters. Two or more extra characters reach a result only when 4 or more entries share one analyzed form in one segment.
• Scale. Deterministic; no large index is needed (three documents reproduce it); one or several segments (the harness covered 1 to 3), assertions on or off, completion postings formats from Completion50 to Completion104, and ordinary analyzers (whitespace, keyword, StandardAnalyzer through CompletionAnalyzer).
• Not affected. PrefixCompletionQuery, which has no wildcard (the prefix foo gives [foo, food]); zero-width tails; releases before 5.3.0, which have no RegexCompletionQuery. Nothing is written to the index, so a fix needs no reindexing.
• Cost. No resource-exhaustion effect was observed, and none was benchmarked. Each wrong match adds a prefix path, and the lookup multiplies the number of results it searches for by the number of prefix paths (NRTSuggester.java:142-144, :292-301), so the extra work is bounded but not zero.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<[food]> but was:<[foo, food]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.suggest.document.TestRegexCompletionEndByte.testDotNeedsARealCharacter(TestRegexCompletionEndByte.java:55)

• Contract. Class javadoc (RegexCompletionQuery.java:31-43): "A CompletionQuery which takes a regular expression as the prefix of the query term", with the example su[g|b] for "a prefix of 'sug' and 'sub'". CompletionQuery matches "documents containing terms with a specified prefix" (CompletionQuery.java:32). The introducing issue LUCENE-6459 (#7518): "Return documents with values that match the prefix of a regular expression".
• The end byte is internal. SuggestField refuses 0x00 in values as "a reserved character" (SuggestField.java:86-96, :140-149).
• Same concern elsewhere. A TODO in FuzzyCompletionQuery (:177-181): "We probably don't want to allow the trailing dedup bytes to be edited". On #9335, @jimczi: "Completion queries should always match a prefix from the suggestions".
• Consistency. PrefixCompletionQuery returns [foo, food] for foo; LUCENE-8287 already aligned the empty regex with PrefixCompletionQuery (RegexCompletionQuery.java:90-91).
• Tests. TestRegexCompletionQuery uses only [a|w|s]s?ugg, the empty regex, [a|s][d|u|s][u|d|g] and [a|s][d|u|s][u|g], none of which can run past a suggestion; the 236 upstream lucene/suggest tests run with 0 failures with the fix.
• History. The unchanged automaton came with the class (LUCENE-6459, 2015); the FST layout with the end byte is older (LUCENE-6339, 5.1.0), when only a prefix lookup on the analyzed key existed. No later commit, issue comment or test that was found discusses or changes it.

Strongest case (built by the devil's advocate and by the lenses of the reviewer from another model family; all rated it weak): the API is @lucene.experimental; the regex already runs over raw FST byte labels rather than characters (#9526: non-ASCII patterns do not match); the expert CompletionWeight javadoc speaks of "every partial path in the index that matched the query automaton" (CompletionWeight.java:66); and a literal U+0000 in the pattern works today as an end anchor ("foo\u0000" returns only foo).

Why it fails: the natural reading of every public description (the class javadoc, the LUCENE-6459 text, the committer quote) is a prefix of the analyzed suggestion; none of them exposes the end or dedup bytes as matchable content (the javadoc literally says "prefix of the query term"), and the end byte is a marker no value may contain. The trigger is ordinary regex syntax with the default flags. @lucene.experimental allows API changes, not wrong results. The CompletionWeight sentence describes how a match is reported, not which inputs should match. The U+0000 anchor appears in no doc, test or downstream code that was found, and #9526 is a different problem (missing matches) whose natural fix, a UTF32ToUTF8 conversion, keeps U+0000 in ..

One fix was built and validated with gradle; the alternatives were not run.

The dedup bytes always follow END_BYTE, so an automaton that cannot read 0x00 reaches neither. Suggestion values cannot contain 0x00, so with ordinary analyzers no real match is lost. It also makes U+0000 unmatchable anywhere in the analyzed form: SuggestField checks the raw value, not the analyzer's output, so an analyzed form with U+0000 from custom analysis can no longer be matched through that byte (untested). The determinize work limit still applies.

        getTerm().text().isEmpty()
            ? Automata.makeEmpty()
            : Operations.determinize(
-                new RegExp(getTerm().text(), flags).toAutomaton(), determinizeWorkLimit);
+                // each suggestion is stored as its analyzed form, the reserved END_BYTE (0x00)
+                // and dedup bytes: the regex must match the analyzed form, never those bytes
+                Operations.intersection(
+                    new RegExp(getTerm().text(), flags).toAutomaton(),
+                    Operations.repeat(
+                        Automata.makeCharRange(
+                            NRTSuggesterBuilder.END_BYTE + 1, Character.MAX_CODE_POINT))),
+                determinizeWorkLimit);

Trade-offs

• Removes an undocumented trick: a literal U+0000 in the pattern acted as an end anchor ("foo\u0000" returned [foo], now []). No doc, test or downstream code using it was found; one sentence in the PR is enough.
• Analyzer output: an analyzed form that contains U+0000 (custom analysis only) can no longer be matched through that byte (SuggestField.java:86-98 checks the value, :103-105 wraps the analyzer's stream unchecked). Untested.
• Coverage: only RegexCompletionQuery is fixed; a custom CompletionQuery that builds its own "any character" automaton would still reach the internal bytes.
• Cost: one intersection per query with an automaton of one live state (a [U+0001, U+10FFFF] self-loop), before the determinize that already runs; not benchmarked.
• Index and backport: query-side only, no reindexing. 10.5.2 has the identical createWeight expression; 9.12.3 builds it with toAutomaton(determinizeWorkLimit), so a 9.x backport needs a slightly different patch. Only main was built and tested with gradle.

What the checks validated

• Gradle, scratch worktree at a9779ef3c193, JDK 25: the new test fails 5 of 8 on stock and passes 8 of 8 with the fix; the seven closest suites (the new test, TestRegexCompletionQuery, TestContextQuery, TestPrefixCompletionQuery, TestFuzzyCompletionQuery, TestSuggestField, TestContextSuggestField) pass 66 of 66; the whole lucene/suggest module, 32 suites and 244 tests (7 skipped), passes with assertions on and off; :lucene:suggest:check -x test passes (google-java-format, ecjLint, forbiddenApis).
• Standalone runner with the fix: the new test 8/8 (assertions on and off), the independent reproducer's 8/8, the devil's advocate's 7/7, the finder's 4/4, and the ContextQuery and keep-behaviour probes 4/4 (foo bar is still returned for foo.).
• With the finder's identical change, the bounded-exhaustive harness loses the whole end-byte mismatch class, while the separate #9335 class stays. (That run also had another unit's unrelated fuzzy-query fix shadowed in; the end-byte class is regex-only, so the attribution holds.)

Make "a query automaton never consumes END_BYTE" a property of the suggester: intersect in the CompletionWeight constructor, or stop NRTSuggester.lookup's prefix walk at 0x00. Also covers custom CompletionQuery subclasses and FuzzyCompletionQuery, whose TODO raises the same concern.

Trade-offs

FSTUtil is shared with AnalyzingSuggester; the walk needs a deterministic automaton, and the product of two deterministic automata stays deterministic, so a central intersection needs a new determinize only when its input is not already deterministic; it cannot treat every 0x00 label as END_BYTE, because context values are checked only for U+001D (ContextSuggestField.java:166-178, ContextQuery.java:128-139) and custom analysis may emit U+0000, so it must find the real end of the analyzed form (for example after the context prefix); it touches every completion query, so it needs the fuzzy and context suites and a benchmark. A design choice for the committers.

Say in the javadoc that . and negated classes can match past the end of a suggestion.

Trade-offs

No code change; every affected pattern stays wrong, including those that downstream regex options pass through.

Use a class that excludes U+0000, a literal NUL character in the Java string: foo[^\u0000] for foo., and foo[^x\u0000] for foo[^x]. Applications can rewrite user patterns this way, or subclass RegexCompletionQuery with the fix above.

Trade-offs

Every place that builds a pattern must do it; a pattern written by a user still needs rewriting.

What the checks validated

On stock main with assertions off: foo[^\u0000] and foo[^x\u0000] give [food] (also with n = 1), foo[^\u0000][^\u0000] gives [] (also over five copies of foo), and fo[^\u0000] still gives [foo, fox, food].

Method: bounded-exhaustive translation validation (semi-formal tier). Leg A of the harness compared the stock main jar with an independent reference evaluated with java.util.regex, over every suggestion of length 1 to 3 over {a, b, c} as its own document, 1 to 3 segments and index sort, SuggestField and ContextSuggestField, 40 RegexCompletionQuery patterns with RegExp.ALL and RegExp.NONE, and num 1, 3 and 200: 2,085,120 checks per run over all completion query kinds, with assertions on and off.

• Class REGEX-END-BYTE (16 plain and 88 ContextQuery checks) was explained in every case by "the pattern may also consume the 0x00 end byte" and disappeared with the fix shadowed in.
• The separately classified, known #9335 class (184 ContextQuery checks) stayed with the fix.
• The finding was reduced to a public-API JUnit on the stock main jars, then checked by a reviewer from another model family (OpenAI GPT-5.6) in lenses, an independent reproducer, a devil's advocate, an adjudication and an audit.