The Kleene star of the empty language returns the empty language instead of {""}

X* means zero or more repetitions of X, and zero repetitions is the empty string, so X* accepts "" even when X accepts nothing. Lucene usually represents "accepts nothing" as an automaton with 0 states (Automata.makeEmpty(), #, an impossible intersection such as (a&b), an empty character class), and Operations.repeat(Automaton) returns such an input unchanged. So #*, (a&b)* and (#){0,} accept nothing, and because a concatenation with an empty part is empty, a(a&b)* matches nothing at all: RegexpQuery and both query parsers' /.../ syntax silently return 0 hits where 1 is expected. The same empty language built with 1 state gives the correct {""}. The 0-state shortcut came from the 2014 LUCENE-6054 crash fix; every release from 4.10.3 to 10.5.2 and main is affected, and 4.9.1 was correct.

• Language: the set of strings an automaton or regex accepts. The empty language { } accepts nothing; the empty-string language {""} accepts exactly one string, the empty one. They are different.
• Kleene star X*: zero or more repetitions of X. Zero repetitions always gives "", so for every X, X* contains "". In particular { }* = {""}.
• How X can be empty in Lucene's regex syntax (all enabled by default, RegExp.ALL): # ("the empty language" in the RegExp grammar), an impossible intersection such as (a&b) or ([a-c]&[x-z]), an empty character class such as [^\s\S]. In code: Automata.makeEmpty(), an intersection with no common string, Automata.makeStringUnion of an empty list.

1. Lucene usually represents the empty language as an automaton with 0 states: Automata.makeEmpty() (Automata.java:55-60, also used for #), Operations.intersection (it returns a 0-state operand as is and ends with removeDeadStates, which drops every state when nothing can reach an accept state; Operations.java:396-401, 436, 1007-1043), makeCharClass with no ranges, makeStringUnion of an empty list.
2. Operations.repeat(Automaton) starts with a shortcut (Operations.java:202-205 at ea57360912ed):

if (a.getNumStates() == 0) {
  // Repeating the empty automata will still only accept the empty automata.
  return a;
}

The general path below it starts with a new accepting initial state (:212-215), so it accepts "". A second shortcut (:207-210) returns an input whose only accept state is its initial state; such an input already accepts "", so that shortcut is correct too. Only the 0-state shortcut returns an automaton that rejects "".

1. {0,} takes the same path: repeat(a, 0) calls repeat(a) (:273-276), and RegExp maps * and {n,} to these two methods (RegExp.java:665-671). ? and {0,k} are correct, because optional adds a state when there is none (:177-180) and repeat(a, 0, max) starts from makeEmptyString() (:297-298).
2. concatenate returns the empty automaton as soon as one part has 0 states (:79-81). So the error spreads to the whole pattern: a(a&b)* = a followed by "nothing" = nothing.
3. RegexpQuery hands the automaton to CompiledAutomaton (AutomatonQuery.java:99), which replaces a 0-state automaton with a 1-state one that accepts nothing (CompiledAutomaton.java:154-157) and classifies it as AUTOMATON_TYPE.NONE (:166-168). The wrong language is kept, no term matches, and no error is raised.

RegexpQuery over the terms "" and a: (a&b)* and a(a&b)* count 0 hits each where 1 is expected; the controls a* = 2, (a&b)? = 1 and a(a&b)? = 1 are right. #+, (a&b)+ and (#){1,} correctly accept nothing.

Same language, different answer. An independent test compared repeat() with the textbook definition of L* on all 31 words over {a,b} of length 0 to 4, for 2,000 random automata with 0 to 4 states: all 384 of 384 0-state inputs were wrong, none of the 1,616 inputs with at least one state were, and 775 of those also had the empty language. A second seed gave 418 of 418 against 0 of 1,582.

• Who is hit. Any code that stars an empty operand with 0 states. That is how #, impossible intersections, empty character classes and Automata.makeEmpty() represent the empty language; an empty operand with 1 or more states is handled correctly:
  • new RegExp(String) (default RegExp.ALL, which enables # and &; RegExp.java:512-513) and RegexpQuery(Term) (RegexpQuery.java:54-55);
  • the classic and the flexible query parser, which both build RegexpQuery with RegExp.ALL (QueryParserBase.java:511-513, RegexpQueryNodeBuilder.java:45-50). Over the terms a and ab, /a(a&b)*/ counts 0 hits in both, where 1 is expected; /a(b)*/ = 2 and /a(a&b)?/ = 1 are right;
  • code that composes automata with the public Operations and Automata API, where an operand can come out empty on its own: an intersection with no common string, a string union of an empty word list, an empty character class, or a difference whose left language is contained in the right. Operations.repeat of each of these rejects "".
• Default, not opt-in. No flag or setting is involved.
• Silent, and wider than the empty string. No exception, with assertions on and off. Because a concatenation with an empty part is empty, a whole pattern such as prefix(<empty>)*suffix matches no term at all. As a standalone positive query it only under-matches (no crash, no index damage); under a negation (a MUST_NOT clause, Operations.complement, a deny filter) the miss turns into an over-match.
• How likely. Rare. #* or (a&b)* is unlikely in a hand-written query; generated patterns and composed automata are the more plausible path. No report from any downstream user is known.
• Scale. None needed: #* is three characters.
• Long-standing. Every release from 4.10.3 (2014) to 10.5.2, and main.
• Workaround. Write (X)? or (X){0,k} instead of (X)* when X may be empty; in code, check Operations.isEmpty(x) before calling repeat and use Automata.makeEmptyString().

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: repeat(makeEmpty()) accepts "" expected:<true> but was:<false>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.apache.lucene.util.automaton.TestKleeneStarOfEmptyLanguage.testStarOfEmptyLanguageAcceptsEmptyString(TestKleeneStarOfEmptyLanguage.java:26)

The contract, in its own words (at ea57360912ed):

• Operations.repeat(Automaton) (Operations.java:196-197): "Returns an automaton that accepts the Kleene star (zero or more concatenated repetitions) of the language of the given automaton."
• repeat(Automaton, int) (:268-269): "accepts min or more concatenated repetitions"; for min = 0 that includes zero repetitions.
• RegExp grammar: * "(zero or more occurrences)" (RegExp.java:121), {n,} "(n or more occurrences)" (:142), ? "(zero or one occurrence)" (:114), # "(the empty language)" (:230).
• The package doc promises "all standard (and a number of non-standard) regular expression operations" and points to dk.brics (package-info.java:33-34, 40-42). In #15182 a committer (rmuir) wrote that the syntax "should continue to match https://www.brics.dk/automaton/". Lucene 4.9.1's repeat, which came from dk.brics, returns {""} here.
• optional and repeat(a, 0, max) in the same class already return {""} for the empty language.
• No javadoc, CHANGES.txt or MIGRATE.md text says the star of the empty language is empty. CHANGES.txt lists the change only as "LUCENE-6054: Allow repeating the empty automaton", under bug fixes (lines 11525 and 11719).

History.

• LUCENE-6054 (GitHub #7116, reported by nik9000) is a crash report: "RegExp.toAutomaton fails on #*", body "This throws an assertion error: new RegExp("#*").toAutomaton(1000);". The fix (nik9000's patch, committed by mikemccand as 54156c042d4 on 2014-11-07, about 9 minutes after the issue was filed) added the return a branch. The comments are thanks, commit notices and a bulk close; nobody discussed what #* should accept. Its test (TestRegExp.testRepeatWithEmptyLanguage, TestRegExp.java:107-117) only checks that toString() is non-empty ("paranoia").
• Before the fix, in 4.10.0-4.10.2, a 0-state input went down the general path: with assertions on it threw AssertionError: state=0 nextState=0 (the reported crash); with assertions off it returned the correct {""}. So the crash fix silently changed production results. Reverting only that hunk inside 4.10.3 restores the 4.10.2 result on all five bug checks (they throw again with assertions on; with them off they return {""} and the whole output is identical to 4.10.2's). With assertions on, one control differs: 4.10.2 also throws on repeat(makeEmpty(), 0, 3) and the reverted 4.10.3 does not, because LUCENE-6046 rewrote the bounded repeat in 4.10.3.
• The tests that pin today's result came later, from optimisation work. TestOperations.testRepeatEmptyLanguage (TestOperations.java:304-309) asserts assertSame(input, Operations.repeat(input)) for makeEmpty(): jpountz added the assertion in #13714 (2024-09-05, "Make Operations#repeat create simpler automata"), and rmuir moved it into its own test in #14218 (2025-02-13, dead-state clean-up), adding AutomatonTestUtil.assertMinimalDFA(actual), which treats the 0-state result as the expected minimal DFA. testDuelRepeat's oracle naiveRepeat, labelled "the original implementation of Operations#repeat" (:487-491), copies the same return a, so it cannot catch this. The study read both PRs and their review comments: nobody discusses what the star of the empty language should be.

Tests. With the fix, the only test failures in all of :lucene:core:test and six modules that use RegExp are those two pinning tests; with them updated, everything passes (see the fix section).

An independent reviewer from another model family (OpenAI GPT-5.6), asked to refute the claim, made the strongest case for "intended" (verdict not real, high confidence): the 0-state branch has an explanatory comment; it was added on purpose, with a CHANGES entry; a dedicated assertSame test (with assertMinimalDFA on the result) and a copied oracle pin it; two later reviewed PRs (2024, 2025) kept and strengthened it; and these APIs are @lucene.experimental. It called the behaviour "conclusively intentional in the current implementation". The reviewer itself reproduced the bug, agreed on the root cause and that the inputs are valid, and conceded that the history "does not articulate why empty-language star should depart from the documented operation" and that #13714 and #14218 "were not semantic discussions".

Why it fails (the second adjudication, verdict real):

1. The artifacts show that the branch and its result were chosen and kept on purpose: the comment states the result, and assertSame, assertMinimalDFA and the copied oracle preserve it. None of them explains the result or reconciles it with the documented Kleene star; there is no "by design" or "won't fix" anywhere.
2. The branch comes from a crash fix committed minutes after the report, whose own test never checks what is accepted; the pinning tests come from an optimisation and a clean-up, and the oracle copies "the original implementation".
3. The code comment is not API documentation, gives no reason, and contradicts the javadoc six lines above it; all public docs say the opposite.
4. The result depends on the number of states, not on the language (384 of 384 against 0 of 1,616). A rule about languages cannot split results that way; if the split is deliberate, it is a rule about representations, and the javadoc defines repeat by the language alone.
5. @lucene.experimental allows API changes, not results that contradict the API's own javadoc.
6. Before 2014, production code returned the correct {""}; the change was announced only as "Allow repeating the empty automaton".

Verdict: not intended, a defect.

One option was validated with gradle in a scratch worktree at ea57360912ed; the other two are alternatives that were not run. The scratch worktree was removed after the runs.

One line in Operations.repeat(Automaton) plus the two pinning tests in TestOperations. testRepeatEmptyLanguage then asserts that the result is a minimal DFA with the same language as Automata.makeEmptyString(), and naiveRepeat gets the same one-line change. A regression test for TestRegExp (#*, (a&b)*, (#){0,} accept only ""; a(a&b)* accepts a) is in the repro section.

public static Automaton repeat(Automaton a) {
  if (a.getNumStates() == 0) {
    // Zero repetitions are always allowed: the Kleene star of the empty language is {""}.
    return Automata.makeEmptyString();
  }

Trade-offs

• Matches the javadoc, the RegExp grammar, optional, repeat(a, 0, max), the 1-state empty automaton and 4.9.1. makeEmptyString() is a 1-state minimal DFA. Cost: one new 1-state automaton per call on a 0-state input instead of returning the input, a small constant; not benchmarked.
• #+, (a&b)+ and (#){1,} stay empty, as they should.
• Query compilation changes with it: (a&b)* and a(a&b)* compile to AUTOMATON_TYPE.SINGLE (the term "" and the term a) instead of NONE (executed).
• Visible change: patterns with a starred empty sub-expression match more afterwards (the empty term, or the whole enclosing concatenation). Worth a CHANGES line.
• repeat() no longer returns the same instance for an empty input; in-tree only the assertSame test relied on that.

What the checks validated

• The repro: stock 7 tests, 6 failed; with the fix 7 of 7 pass. The TestRegExp regression test fails on stock (assertions off) and passes with the fix.
• 34 core classes (util.automaton.*, TestRegexp*, TestAutomatonQuery*, TestWildcard*, TestPrefix*, TestTermsEnum*, the DocValues and FieldCache rewrite methods, TestQueryBuilder, TestMatchesIterator, TestDisjunctionMaxQuery), seed DEADBEEF: stock 388 tests, 6 failures (all in the repro); code fix only: exactly 2 failures, testRepeatEmptyLanguage and testDuelRepeat; with the 2-test update: 0 failures.
• Assertions off, seed 1234ABCD (util.automaton.*, TestRegexp*, TestAutomatonQuery*): 267 tests, 0 failures.
• The whole :lucene:core:test (fix, both test changes and the repro): 748 classes, 8,873 tests, 0 failures, 322 skipped.
• queryparser 533, highlighter 722, monitor 181, queries 512, memory 51 and suggest 236 tests: 0 failures. Not run: analysis.tests and the other modules.
• :lucene:core:checkGoogleJavaFormat passes; the TestRegExp method was formatted with tidy.

Map * and {0,} of an empty operand to makeEmptyString() in RegExp.

Trade-offs

Fixes regex users but leaves the public Operations.repeat wrong, and dependent on the state count, for code that composes automata. Not recommended.

Amend the javadoc and the RegExp grammar.

Trade-offs

The text would have to say that the result depends on the number of states (0 states: empty; 1 dead state: {""}) and make an exception for * and {n,}. It would contradict optional, repeat(a, 0, max), dk.brics and 4.9.1.

Method: differential fuzzing (Jazzer 0.30.0), the study's non-formal baseline tier, 2026-10-22, main 7cecf79523.

• An AI tool ran the RegexDiffFuzzer target: one random regex syntax tree is rendered both as a Lucene RegExp and as a java.util.regex pattern and the two are compared, with self-consistency checks across Operations (run, complement, intersection, union, reverse, minimize). About 145 k executions in 5 runs produced this bug and three other automaton and regex findings.
• A separate AI verifier wrote its own 10-test JUnit (9 fail; the in-test controls pass), traced the history to LUCENE-6054, ran 4.9.1 (correct) and 4.10.4, 5.0.0, 10.1.0, 10.5.2 and main (wrong), and tested the fix against 210 Lucene tests.
• On 2026-10-26 the hunt re-ran it on ea57360912ed (-ea, -da, 10.5.2, 9.12.3), obtained a cross-model refute review and a second adjudication, built the release matrix with -ea and -da, and searched for prior reports. For this page the fix was validated with gradle.