FuzzyQuery on a term whose bytes are not valid UTF-8 fuzzes the hex string "[ff 61 62 63]" and misses the term itself

FuzzyQuery (with maxEdits 1 or 2) and the public FuzzyTermsEnum build their Levenshtein automaton from Term.text() (FuzzyTermsEnum.java:101 and :132 at 5adff78bb168). For a term whose bytes are not valid UTF-8, which new Term(field, BytesRef) accepts and StringField(String, BytesRef, Store) indexes, Term.text() does not return the term: it falls back to BytesRef.toString(), a human-readable hex rendering such as "[ff 61 62 63]" (13 characters for 4 bytes). The automaton accepts strings within maxEdits of that rendering and can never accept the raw bytes. With one document holding the bytes ff 61 62 63, new FuzzyQuery(new Term("id", bytes), 1) counts 0 hits while FuzzyQuery(term, 0) and TermQuery count 1; documents holding the text [ff 61 62 63] are matched instead. No exception, with assertions on and off. Every release since 4.0.0 has it.

1. Two paths. FuzzyQuery.getTermsEnum (search/FuzzyQuery.java:204-209) uses new SingleTermsEnum(terms.iterator(), term.bytes()) for maxEdits == 0 (:205-206), the bytes, which is correct; otherwise it creates a FuzzyTermsEnum (:208).
2. The pattern is the text. Both FuzzyTermsEnum constructors, the public one (search/FuzzyTermsEnum.java:101) and the one FuzzyQuery uses (:132), supply new FuzzyAutomatonBuilder(term.text(), maxEdits, prefixLength, transpositions), the fix site. FuzzyQuery.getAutomata() (FuzzyQuery.java:172), used by visit() (:197-201), does the same.
3. The text of a binary term is its display string. Term.text() is toString(bytes) (index/Term.java:100-102): a strict UTF-8 decode that, on failure, returns BytesRef.toString() (:108-122), documented as "human-readable form of the term text. If the term is not unicode, the raw bytes will be printed instead." (:104-107). BytesRef.toString() is [ + hex bytes separated by spaces + ] (util/BytesRef.java:143-157).
4. The raw term is unreachable. FuzzyAutomatonBuilder takes the code points of [ff 61 62 63] (search/FuzzyAutomatonBuilder.java:50) and builds a Unicode automaton compiled to UTF-8 bytes; it can never accept a 0xff byte. The independent reproducer's diagnostic on main: "automaton accepts raw bytes: false", "automaton accepts display string: true".

So the results of a FuzzyQuery search are not monotone in maxEdits: 0 finds the term, 1 and 2 do not. Only that search path special-cases 0: the public FuzzyTermsEnum with maxEdits 0, and getAutomata() / visit() of a FuzzyQuery with maxEdits 0, also work on the display string (executed; see "Suggested fixes", fix A, "Open decision"). Before 4.3.0, text() was a lenient decode, so the pattern was garbled instead (no hit; with assertions on, an AssertionError in UnicodeUtil).

• Who. Code that builds a fuzzy pattern from raw bytes that are not UTF-8: new FuzzyQuery(new Term(field, bytes), maxEdits) or new FuzzyTermsEnum(terms, term, ...) over a field of binary keyword values (raw ids, hashes, other byte keys). Term(String, String) always encodes well-formed UTF-8, so text patterns are never affected.
• One parser path. The classic QueryParser builds the fuzzy Term from Analyzer.normalize() bytes (QueryParserBase.java:729-730). With the stock CollationKeyAnalyzer, the key bytes of the text 東京都 start with 0x80; 東京都~1 returns no hit while the plain term query matches (the devil's-advocate verifier's probe). Niche.
• Effect. Silently missing results (the exact match is dropped) and, when the index holds such text, extra hits near the hex string. No exception, no log.
• Default vs opt-in. Under the default settings the repro uses, a non-UTF-8 pattern is enough to trigger it.
• Scale. Deterministic: every recorded run without the fix failed; one document is enough.

TestFuzzyQueryBinaryPattern (one method, extends LuceneTestCase, package org.apache.lucene.search of the lucene/core tests), with the Apache license header. The test adds no randomness of its own (LuceneTestCase still randomizes the test environment); every recorded run without the fix failed, each under its recorded seed, with assertions on and off. Its catch accepts any IllegalArgumentException; the constructor's other checks (FuzzyQuery.java:94-103: maxEdits range, prefixLength, maxExpansions) cannot fire for these arguments; a regression test for fix A could also assert the rejection itself (expectThrows and the message). A separate re-run used a variant of this test that first asserts the maxEdits = 0 hit; without the fix it fails at its maxEdits = 1 assertion.

cp $REPRO/TestFuzzyQueryBinaryPattern.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestFuzzyQueryBinaryPattern -Ptests.seed=DEADBEEF

# gradle, scratch worktree at 5adff78bb168, -Ptests.seed=DEADBEEF -Ptests.asserts=false
TestFuzzyQueryBinaryPattern > testFuzzyQueryMatchesIdenticalBinaryTerm FAILED
    java.lang.AssertionError: expected:<1> but was:<0>
        at org.apache.lucene.search.TestFuzzyQueryBinaryPattern.testFuzzyQueryMatchesIdenticalBinaryTerm(TestFuzzyQueryBinaryPattern.java:48)

# gradle, same, assertions on: the same failure

# with the rejection fix: PASS with assertions on and off

• Contract. "Create a new FuzzyQuery that will match terms with an edit distance of at most maxEdits to term" (FuzzyQuery.java:70-72). If a binary Term is within the pattern domain this API accepts, the identical bytes are a 0-edit match, and maxEdits = 0 does match them.
• No UTF-8 precondition in the checked docs. No javadoc or test says the pattern must be UTF-8, and no CHANGES entry says what happens otherwise. The closest entry, LUCENE-2265 (lucene/CHANGES.txt:15525-15528, 4.0.0-ALPHA), says "FuzzyQuery and WildcardQuery now operate on Unicode codepoints, not unicode code units"; it predates byte-based terms (its commit 5b74a4ec611 is from 2010-05-03, two months before LUCENE-2514) and states no rule for non-UTF-8 patterns. Term(String, BytesRef) (Term.java:52) and StringField(String, BytesRef, Store) (StringField.java:79) accept any bytes, and TestBinaryTerms indexes and searches binary terms.
• A display aid. The hex fallback came with LUCENE-4934 (#5998, 4.3.0) so that toString() works on binary terms; the same commit added TestBinaryTerms.testToString ("foo:[ff fe]"). Neither the commit nor its issue discusses fuzzy matching.
• Inconsistent paths. The maxEdits = 0 path uses term.bytes(), the others term.text().
• Tests. TestFuzzyQuery uses text patterns only.

The strongest case for "not a bug": fuzzy edit distance is defined over Unicode code points (LUCENE-2265, #3341, where Robert Muir wrote "fuzzy, regex, wildcard, all of our users are defined on unicode characters ... bytes is an implementation detail"; its CHANGES entry, lucene/CHANGES.txt:15525, says FuzzyQuery and WildcardQuery "now operate on Unicode codepoints"), so a binary pattern is outside the query's domain; WildcardQuery and RegexpQuery also read Term.text().

Why it fails: that justifies rejecting or documenting such patterns, not silently fuzzing a display string and dropping the 0-edit match, and nothing tells the caller. The verifiers rated the argument moderate and rejected it; it is also why the recommended fix rejects, and a maintainer may still prefer the documentation-only fix. The WildcardQuery and RegexpQuery siblings share the assumption (a WildcardQuery without wildcards behaves the same way in the devil's-advocate verifier's probe, executed; RegexpQuery was only read, not run), but are not claimed here.

Option A was built and checked through gradle on 5adff78bb168; B and C were not built. WildcardQuery (executed) and RegexpQuery (read only) share the Term.text() assumption; no option here changes them.

A package-private FuzzyQuery.checkUtf8Pattern(term, maxEdits) runs the same strict UTF-8 check Term.toString(BytesRef) uses and throws when it fails. The FuzzyQuery constructor calls it after its other argument checks; the public FuzzyTermsEnum constructor passes its term through it.

  /** The edit distance is defined over the pattern's code points (FuzzyAutomatonBuilder). */
  static Term checkUtf8Pattern(Term term, int maxEdits) {
    if (maxEdits > 0 && isUtf8(term.bytes()) == false) {
      throw new IllegalArgumentException(
          "fuzzy matching with maxEdits > 0 needs a term whose bytes are valid UTF-8; got " + term);
    }
    return term;
  }

Trade-offs

A behaviour change: code that builds such queries today gets an exception instead of silent wrong results. That includes the classic QueryParser over a CollationKeyAnalyzer field, where 東京都~1 would throw instead of returning nothing (not run), and the three main-source callers of the public FuzzyTermsEnum constructor: DirectSpellChecker (DirectSpellChecker.java:425, suggest), the sandbox FuzzyLikeThisQuery (FuzzyLikeThisQuery.java:217) and the classification module's NearestFuzzyQuery (NearestFuzzyQuery.java:153); the suites of the first two ran with the fix, the classification tests did not. The first sketch guarded only FuzzyQuery; the cross-model refute review found the public constructor unguarded, so both are guarded.

Open decision: the other maxEdits = 0 paths (left as they are by fix A). The guard fires only for maxEdits > 0, but maxEdits = 0 is special-cased only in FuzzyQuery.getTermsEnum. The public FuzzyTermsEnum constructor (FuzzyTermsEnum.java:94-102) and FuzzyQuery.getAutomata() (:172, used by visit(), :197-201) build the automaton from term.text() for maxEdits = 0 too. Executed on main and with fix A shadowed (same output): FuzzyQuery(term, 0) counts 1, but new FuzzyTermsEnum(terms, term, 0, 0, false) enumerates only the text term [ff 61 62 63] (bytes 5b 66 66 20 ...), and the automata from getAutomata() and visit() accept that text and reject the raw bytes. A complete fix needs a choice: reject non-UTF-8 terms in the public FuzzyTermsEnum constructor for every maxEdits (it always builds an automaton), and for getAutomata() / visit() either reject them in FuzzyQuery for every maxEdits or build the 0-edit automaton from the bytes. Not built or run.

What the checks validated

• Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on and off) and passes with it (on and off).
• With the fix: 203 tests run, 0 failures (202 pass, 1 is @Ignored by its suite): in core the repro, TestFuzzyQuery (13), TestFuzzyTermOnShortTerms (1), TestMultiTermQueryRewrites (4), TestWildcardQuery (14) and TestBinaryTerms (2); TestQueryParser (73), TestSimpleQueryParser (46) and TestQPHelper (38) in queryparser; TestDirectSpellChecker (6) in suggest; TestFuzzyLikeThisQuery (5) in sandbox. :lucene:core:checkGoogleJavaFormat passes on the fix.

A javadoc note on FuzzyQuery and FuzzyTermsEnum that the pattern must be UTF-8 text.

Trade-offs

Smallest change and no behaviour change, but callers who miss the note still get 0 hits silently. Given the Unicode-only design (#3341), a maintainer may well choose this.

Build a byte-alphabet Levenshtein automaton when the pattern is not UTF-8.

Trade-offs

Real fuzzy matches on binary terms, but distances would mean bytes for some patterns and code points for others; a larger design change that the Unicode-only design (#3341) argues against.

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

• The finder read FuzzyTermsEnum and FuzzyQuery against their obligation (terms within maxEdits of the pattern term) and the inputs Term accepts (any bytes). The automaton is built from term.text(), and Term.text() is the term only for valid UTF-8; for other bytes it is the hex display string.
• The finder then wrote a public-API JUnit test that fails on main with assertions on and off and on 10.6.0, 9.12.3 and 8.11.4.
• An independent reproducer, two executed cross-model reviews, a devil's-advocate verifier and an adjudication reproduced it with their own tests ("Prior reports, history and checks").