FuzzyQuery on the empty term matches only the empty term

FuzzyQuery promises to match every term within maxEdits edits of its term, and since 6.3.0 (LUCENE-7439) that includes short terms. For the empty term that means "" plus every indexed term of 1 to maxEdits characters (Unicode code points). Lucene returns only "": in a six-term index ""~1 gets 1 hit instead of 4 and ""~2 1 instead of 5, with no error, while "a"~1 correctly gets 5. The cause is the top-N pruning loop in FuzzyTermsEnum.bottomChanged: for a term of length 0 the best boost an edited term can reach, 1 - maxEdits/termLength, is -Infinity, the same value the empty queue reports, so the loop lowers maxEdits to 0 before any term is collected. Every release from 6.3.0 to 10.5.2 and main is affected.

• Edit distance: the number of single-character insertions, deletions, substitutions (and, by default, transpositions) that turn one term into another. From "" a term can only be built by insertions, so its distance is its length in code points.
• Boost: FuzzyTermsEnum scores a match as 1 - edits / min(length of the query term, length of the indexed term) (FuzzyTermsEnum.java:250-258); an exact match gets 1. Negative boosts are clamped to 0 when the query is built (TopTermsRewrite.java:166-170).
• Top-N pruning: the default rewrite keeps only the best maxExpansions terms (50). FuzzyTermsEnum.bottomChanged lowers maxEdits (and switches to a smaller automaton) once even the best boost possible at that distance cannot beat the worst term in the full queue.

1. FuzzyQuery.getTermsEnum sends only maxEdits == 0 to SingleTermsEnum (FuzzyQuery.java:203-209); ""~1 and ""~2 get a FuzzyTermsEnum.
2. FuzzyAutomatonBuilder sets termLength to the code-point count of the term: 0 (FuzzyAutomatonBuilder.java:50-51). Its automata are correct: automata[n] accepts exactly the terms of at most n code points, and getAutomata()/visit() report that set.
3. The constructor sets maxEdits = automata.length - 1, reads the shared queue state, and calls bottomChanged(null) (FuzzyTermsEnum.java:153-159). Nothing has been collected yet, so the state is the sentinel bottom = Float.NEGATIVE_INFINITY, bottomTerm = null (MaxNonCompetitiveBoostAttributeImpl.java:30-31).
4. In bottomChanged (FuzzyTermsEnum.java:199-210), termAfter is true because bottomTerm == null. The loop computes maxBoost = 1 - maxEdits/termLength = 1 - 2/0 = -Infinity. bottom < maxBoost is -Inf < -Inf, false, and the tie clause bottom == maxBoost && termAfter == false is off. So maxEdits drops 2 -> 1 -> 0.
5. getAutomatonEnum(0, null) intersects the terms with automata[0], the exact-match automaton (FuzzyTermsEnum.java:212-219). Only "" is enumerated.

For any term of length 1 or more, maxBoost is finite (for "a"~2: -1, then 0), so the -Infinity sentinel breaks the loop at once. Only the empty term ties with it.

Edit distance is symmetric, but matching is not: "a"~1 matches "", while ""~1 does not match "a".

Before 9.0 a second path gave the same result: FuzzyQuery.getTermsEnum also sent prefixLength >= term.text().length() (0 >= 0 for "") to SingleTermsEnum. LUCENE-9365 (#10405, 9.0.0) removed that shortcut, and since then the pruning loop alone cuts "" to exact match.

• Who is exposed. Code that passes an empty term text to FuzzyQuery or FuzzyTermsEnum with maxEdits 1 or 2, on a field that has terms of 1 to maxEdits code points: for example new FuzzyQuery(new Term(field, userInput)) with blank input, or new Term(field), whose javadoc describes its empty text as a "pattern for a query" (Term.java:78-85).
• Not checked: which applications, downstream engines or analyzers produce an empty fuzzy term. The classic query parser's term~ syntax needs at least one character and passes it through Analyzer.normalize (QueryParserBase.java:727-731); whether a normalizer can return an empty term was not checked. DirectSpellChecker skips words shorter than minQueryLength (default 4).
• Default, not opt-in. The plain-Java repro uses the default FuzzyQuery settings and the default codec (new IndexWriterConfig()). The JUnit repro fails the same way under the test framework's randomized codec and similarity, with the default rewrite, CONSTANT_SCORE_REWRITE and a direct FuzzyTermsEnum.
• Silent. No exception: the result is exactly the exact-match result.
• What is lost. The terms that should match are exactly the indexed terms of 1 to maxEdits code points, the only terms within maxEdits of "" (with maxEdits capped at 2, one- and two-code-point terms). A direct FuzzyTermsEnum and CONSTANT_SCORE_REWRITE lose all of them; the default rewrite keeps at most maxExpansions terms (50), so it loses the ones that cap would have kept.
• Lucene disagrees with itself. For the same term and distance, FuzzyQuery.getAutomata() (what visit() reports to a QueryVisitor) and Intervals.fuzzyTerm accept the full set.
• How common. Probably rare: it needs an empty term text, and no report was found since 6.3.0.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<2> but was:<1>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.search.TestFuzzyQueryEmptyTermText.testEmptyTermMatchesTermOneEditAway(TestFuzzyQueryEmptyTermText.java:42)

• Constructor javadoc (FuzzyQuery.java:70-72): "Create a new FuzzyQuery that will match terms with an edit distance of at most maxEdits to term." The constructor validates maxEdits and prefixLength (:95-101) but puts no condition on the term text.
• FuzzyTermsEnum constructor javadoc (FuzzyTermsEnum.java:79-82, the public 5-argument constructor declared at :94): "enumeration of all terms ... which share a prefix of length prefixLength with term and which have at most maxEdits edits."
• CHANGES, 6.3.0 (lucene/CHANGES.txt:8855-8856): "LUCENE-7439: FuzzyQuery now matches all terms within the specified edit distance, even if they are short terms". The issue's goal: "edit distance 2 does in fact match all terms with edit distance <= 2".
• Class javadoc (FuzzyQuery.java:34-37): terms "will be collected and scored according to their edit distance".
• Tests. TestFuzzyTermOnShortTerms.java:47-56 asserts that short terms match since LUCENE-7439. No test builds a fuzzy query on "": TestFuzzyQuery.testRandom draws query terms of 1 to 8 characters (TestFuzzyQuery.java:585-592) and calls random().nextInt(queryTerm.length()) (:620), which would throw for length 0.
• History. LUCENE-7439 changed the rule for every other term and did not touch the empty-term paths. The empty term returns only "" in every release from 5.0.0 to main; it became a contract violation in 6.3.0.

The strongest case for "intended": the FuzzyQuery class javadoc still says (FuzzyQuery.java:46-50, LUCENE-5206, 2013) "For a term to match, the edit distance between the terms must be less than the minimum length term (either the input term, or the candidate term)". For a length-0 input term that allows only exact matches, which is what happens. Fuzzy matching on nothing is also degenerate, the result has been the same since at least 5.0.0, and the boost formula 1 - edits/min(length) has no finite value for a length-0 term, so exact-only avoids inventing a ranking.

Why it fails: the NOTE predates LUCENE-7439, which removed its rule. TestFuzzyTermOnShortTerms.java:49-56 asserts both of its examples the other way round, and by its rule "a"~1 could not match "" either, yet it does. Main follows the NOTE only for the empty query term, and only through an arithmetic tie with the empty-queue sentinel. The matching set is well defined, the query's own automaton accepts it, and Intervals.fuzzyTerm matches it. If exact-only were intended, the constructor would say so or reject the input. The boost only ranks matches: Lucene already matches the empty indexed term ("a"~1) although its boost is 1 - 1/0 = -Infinity, clamped to 0 (FuzzyTermsEnum.java:250-257, TopTermsRewrite.java:170), and fix A keeps those boosts. The stability is a real compatibility cost for a fix (see Suggested fix), not evidence of intent. Verdict: not intended, a defect. The cross-model refute review rated the intended-behaviour argument "moderate" and the bug "real, high confidence".

Two fixes were built and validated with gradle in a scratch worktree at ea57360912ed; both change nothing for a non-empty query term, because Math.max(1, termLength) == termLength and termLength > 0 whenever termLength >= 1. They differ in how the empty term ranks its matches when there are more candidates than maxExpansions. Options C and D were not run. Both A and B change results that have been exact-only since 5.0.0: callers that use a fuzzy clause on blank input as a filter or a MUST_NOT clause would see more matches or fewer exclusions, so the CHANGES entry should say so. On 9.0.0 and later the FuzzyTermsEnum change alone is enough (executed on 9.0.0 with fix A; for fix B by reading); 6.3-8.x also need the prefixLength >= term.text().length() shortcut in FuzzyQuery.getTermsEnum changed (executed on 6.3.0 and 8.0.0).

In FuzzyTermsEnum, use Math.max(1, termLength) in the pruning bound of bottomChanged (line 205) and in the similarity of next() (line 254). For "" the best boosts become -1 (2 edits) and 0 (1 edit), which never tie with the -Infinity sentinel, so pruning works for "" exactly as for a one-character term.

// FuzzyTermsEnum.bottomChanged, line 205
float maxBoost = 1.0f - ((float) maxEdits / (float) Math.max(1, termLength));
// FuzzyTermsEnum.next, line 254
int minTermLength = Math.min(codePointCount, Math.max(1, termLength));

Trade-offs

• Non-exact matches of "" get finite boosts ordered by distance (1 edit: 0, 2 edits: -1). For a kept non-exact term the clause boost stays 0 after the clamp, as for a one-character term; the result set does change (the missing matches are added), and at the maxExpansions cap fixes A and B keep different terms.
• With more candidates than maxExpansions, the closest terms are kept: over "" aa ab b c with maxExpansions 3, it keeps "", b, c (0, 1, 1 edits).
• An empty indexed term matched by a non-empty query keeps its -Infinity boost, as today.
• The one-character scale is a choice: any positive length gives the same order, and after the clamp only the order matters.

What the checks validated

• The JUnit repro: 6 of 6 pass (stock: 4 of 6 fail); TestFuzzyQuery.testEmptyTerm passes; the top-terms probe passes 2 of 2.
• :lucene:core:test on org.apache.lucene.search.* and org.apache.lucene.util.automaton.*: 2,577 tests, 0 failures, 51 skipped (stock: the same 2,577 tests with exactly 6 failures, the new tests).
• :lucene:suggest (search.spell.*), :lucene:sandbox (*FuzzyLikeThis*), :lucene:queries (queries.intervals.*), :lucene:classification, :lucene:queryparser, :lucene:highlighter: 1,451 tests, 0 failures.
• :lucene:core:checkGoogleJavaFormat passes on the patch; TestFuzzy* with seed 1234ABCD and assertions off: 15 tests pass.
• Through the repro runner with the fix shadowed: the repro passes with -ea and -da; the plain-Java program prints 5, 4 and 5 hits.
• Not run: the rest of the test suite and any performance benchmark.

The one-line guard while (maxEdits > 0 && termLength > 0) in bottomChanged (line 204): the smallest change, and it fixes the matching.

while (maxEdits > 0 && termLength > 0) {

Trade-offs

• All non-exact matches of "" keep boost -Infinity, so the top-N queue breaks the tie by term order, not distance: over "" aa ab b c with maxExpansions 3 it keeps "", aa, ab (2 edits) and drops b, c (1 edit), against the class javadoc's "scored according to their edit distance".
• No pruning for "": it enumerates every term of at most maxEdits code points (bounded; not benchmarked).

What the checks validated

The JUnit repro 6 of 6 and TestFuzzyQuery.testEmptyTerm pass; the same suites as option B (without the probe): 2,575 core tests and 1,451 module tests, 0 failures; format check and seed 1234ABCD with assertions off pass. The top-terms probe fails 1 of 2 (the ranking above).

Throw IllegalArgumentException from FuzzyQuery and FuzzyTermsEnum for an empty term.

Trade-offs

Explicit, but a behaviour change for callers who get exact-match results today, and it contradicts edit-distance semantics that are well defined for "". Not run.

Keep the behaviour and say so in the javadoc.

Trade-offs

Contradicts the constructor javadoc and LUCENE-7439, and leaves getAutomata()/visit() and Intervals.fuzzyTerm inconsistent with the query.

Method: fuzzing with an independent oracle (the study's non-formal baseline tier). Jazzer generated query terms and term sets; the oracle was a brute-force optimal-string-alignment edit distance over code points, written independently of Lucene, compared with the terms FuzzyQuery matched.

• An AI verifier wrote its own 9-test JUnit (one document per term "", a, b, ab, abc, x): 6 failed on main for 5 seeds. It traced the cause to bottomChanged and confirmed it with the one-line guard, under which all 9 pass and Lucene's own TestFuzzyQuery, TestFuzzyTermOnShortTerms and TestMultiTermQueryRewrites still pass.
• The hunt wrote the minimal 6-test JUnit, re-ran it on main ea57360912ed, 10.5.2 and 9.12.3, and had it reviewed by an independent reviewer from another model family (OpenAI GPT-5.6), which wrote and ran its own test with the terms "", q, r, qr, qrs.
• An AI history checker ran a version probe on all 107 releases from 5.0.0 to 10.5.2 and pinned the introduction with single-change A/B runs.