FiniteStringsIterator returns the empty string twice

FiniteStringsIterator lists the strings that an acyclic automaton accepts. When the start state accepts and also has an outgoing transition, as for a?, (ab)? or a string union that includes "" with other strings, the iterator returns "" twice: first, and again as the very last result. For new RegExp("a?").toAutomaton(), which reports isDeterministic() == true, it returns "", "a", "", and LimitedFiniteStringsIterator(a, -1).size() is 3. The only case the class javadoc names for duplicates is an automaton that is "not determinized". Two code paths produce "": a special case for an accepting state 0, and the pop branch, which returns the current string whenever it pops an accepting state; popping the start state leaves the empty string. It has been there since the class was added (LUCENE-6365, 2015): every release from 5.3.0 to 10.5.2 and main. The API is @lucene.experimental and no in-tree caller is known to build such an automaton.

• Accepted strings: the finite set of strings an automaton without cycles accepts. a? accepts "" (zero a) and "a".
• Start state: state 0 ("State 0 is always the initial state", Automaton.java:37-38); the three-argument constructor takes a startState. The empty string is accepted exactly when the start state accepts.
• FiniteStringsIterator (public, @lucene.experimental): "Iterates all accepted strings"; the only case it names for duplicates is "If the automaton is not determinized" (FiniteStringsIterator.java:26, 33). LimitedFiniteStringsIterator stops after limit strings and counts them in size().

1. Path 1, the special case. The constructor sets emitEmptyString = a.isAccept(0) (:86), and the first next() returns EMPTY (:102-106, comment "Special case the empty string, as usual").
2. The start state is also on the path stack. If it has an outgoing transition, the constructor pushes it as the bottom node and sets the string length to 1 (:88-93).
3. Strings come out in post-order. A transition into an accepting state with no transitions returns the string (:130-132). When a node runs out of transitions it is popped: depth--; string.setLength(depth); and if (a.isAccept(state)) return string.get(); (:134-145). That is how a string ending at an inner accepting state comes out, such as "x" in {"x", "xy"}, so the branch is needed.
4. Path 2, popping the start node. It is popped last: depth becomes 0, the string is empty and the start state accepts, so "" is returned again, always as the final result before null.

The two-state automaton of {"", "a"} (state 0 accepts, 0 -a-> 1, state 1 accepts; a? behaves the same):

When (one-argument constructor, which starts at state 0). State 0 accepts and has at least one transition. Without a transition it is never pushed (makeEmptyString() gives "" once); if it does not accept, neither path fires. The language need not hold a second string: an accepting state 0 whose only transition leads to a non-accepting dead end accepts only "", and it too returns "" twice (such an automaton is not minimal, so this case is weaker). The three-argument constructor checks state 0 for the special case but startState for the push and the pop: there a duplicate needs both to accept, and if only state 0 accepts it returns a "" that is on no path from startState (a side finding, see the fixes).

All of them report isDeterministic() == true. With a limit: for {"", "a"} limits 1 and 2 are right and 3, 4, 5 and -1 return the duplicate; for {"", "a", "ab", "b"} limits 1 to 4 are right and 5 or -1 return 5 strings. LimitedFiniteStringsIterator counts every non-null result (LimitedFiniteStringsIterator.java:56-69), so size() counts the duplicate; that is a consequence, not a second defect.

• Who is hit. Direct callers of the public, @lucene.experimental iterators on a finite automaton whose start state accepts and has a transition: an optional pattern (a?, (ab)?), a makeStringUnion word list that includes "" with other words, or a hand-built automaton of that shape.
• What they see. One extra "", always last, and a count one too high. With the one-argument constructor, drained to the end, the set of distinct strings is right; only the multiplicity and the count are wrong. Code that uses the strings as a Set or as an OR of alternatives is unaffected; code that counts them, keeps a list, weights them, builds one clause per string or relies on size() gets one too many. (The separate three-argument side finding can add a "" that is not accepted from startState; that one changes the set.) No exception, with assertions on or off.
• In-tree callers (read, not executed): GraphTokenStreamFiniteStrings (used by QueryBuilder for graph token streams), ConcatenateGraphFilter, FuzzyCompletionQuery, FuzzySuggester and AnalyzingSuggester. The study verifier argued that they build their automata from token streams whose start state accepts only when it has no transitions, so none reaches the bug. Their tests pass with and without the fix.
• Downstream. A 2020 pull request to one downstream search engine uses the iterator for regex support in a wildcard field type; whether that code is still in use, and whether it can see an automaton of this shape, was not checked.
• Default vs opt-in. No flag is needed, but only direct users of this experimental API are exposed.
• Scale. None: a two-state automaton is enough.
• Long-standing. Every release since 5.3.0 (2015).
• Workaround. Collect the strings into a Set, or skip a second "" (the duplicate always comes after the first one, as the last result; a lone "", as from makeEmptyString(), is not a duplicate); do not rely on LimitedFiniteStringsIterator.size() for such automata.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: strings: [, a, ] expected:<2> but was:<3>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.util.automaton.TestFiniteStringsIteratorEmptyString.testEmptyStringReturnedOnce(TestFiniteStringsIteratorEmptyString.java:42)

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

• FiniteStringsIterator javadoc: "Iterates all accepted strings." (FiniteStringsIterator.java:26) and "If the automaton is not determinized then it's possible this iterator will return duplicates." (:33). That sentence names a sufficient condition, not an "only if"; but every failing automaton reports isDeterministic() == true and is minimal, so the one case it names does not apply.
• Automata.makeStringUnion: "Returns a new (deterministic and minimal) automaton" (Automata.java:634); TestRegExpParsing.testOptional asserts that a? is a minimal DFA (TestRegExpParsing.java:521).
• LimitedFiniteStringsIterator.size(): "Number of iterated finite strings" (LimitedFiniteStringsIterator.java:71).
• Lucene's test helper: // Check that no string is emitted twice. followed by the assertion (TestFiniteStringsIterator.java:196-200).
• The code has one explicit empty-string path, labelled "Special case the empty string, as usual" (:102); the second "" comes from the general pop branch reaching the start node. The comment labels the special case; on its own it does not say that this is the only source.

Why the tests miss it. testRandomFiniteStrings1 uses strings of length 1 to 200 (TestFiniteStringsIterator.java:46); its oracle AutomatonTestUtil.getFiniteStringsRecursive adds a string only when a transition enters an accepting state, so it never holds "" (AutomatonTestUtil.java:539-540); TestOperations.getFiniteStrings collects into a HashSet (TestOperations.java:247-254). No test has an explicit empty-string case. Two random tests can build an automaton that accepts "" (TestLimitedFiniteStringsIterator.testRandomFiniteStrings, TestStringsToAutomaton.testRandom), but they check only that the run completes or that each string is expected, not how often it comes back.

History.

• LUCENE-6365 ("Optimized iteration of finite strings", #7425; committed on 2015-07-04) added the class. The API it replaced, Operations.getFiniteStrings, collected results in a HashSet, produced "" only through the same isAccept(0) special case, and returned nothing from its pop branch; 5.0.0 to 5.2.1 give {"", "a"}.
• The issue text changed the emission order on purpose: "Old: emit current node, if accept / recurse. New: recurse / emit current node, if accept." The new post-order step was not skipped for the start node, whose empty string the kept special case already returns.
• Duplicates came up once (2015-07-05/06), for a test that fed a non-determinized union containing the same string twice. The patch author noted that "The de-duplication has prior been implemented by the big set containing the result, which has been removed"; a committer (mikemccand) replied that "if you pass a non-minimal automaton to it, it's fair game for it to return dups ... so this is a test bug". The javadoc sentence at :33 was added right after (f0b550a092c).
• None of the 44 comments on #7425 mentions the empty string or the start state.

An independent reviewer from another model family (OpenAI GPT-5.6), asked to refute the claim, made the strongest case for "intended" and rated it "moderate": the API is @lucene.experimental; "Iterates all accepted strings" does not literally say "exactly once"; the iteration order is unspecified; and the LUCENE-6365 discussion says the result Set, and with it de-duplication, was removed on purpose, so callers could be expected to tolerate repeated values. LimitedFiniteStringsIterator.size() literally counts what was iterated, so 3 is "right".

Why it fails:

1. The javadoc sentence about duplicates was written in response to that very discussion, and the only case it names is an automaton that is not determinized; the committer's "fair game" remark was about a non-minimal automaton. The sentence is a sufficient condition, not an "only if", so it does not by itself forbid duplicates elsewhere; but these automata are deterministic and minimal, and nothing in the javadoc or the discussion covers that case.
2. The removed Set de-duplicated a string reached by two different paths of a non-deterministic automaton. Here there is one path, and the iterator returns it twice from its own bookkeeping.
3. Lucene's own test helper asserts that no string is emitted twice. The tests that use it never give it an automaton that accepts "", and the random tests that can build one do not check how often a string comes back.
4. @lucene.experimental permits API changes, not results that contradict the class's own javadoc.

The reviewer itself reproduced the bug with its own RegExp("x?") test, agreed on the root cause and that the inputs are in contract, and concluded real, high confidence.

One option was validated with gradle in a scratch worktree at ea57360912ed (removed after the runs); the study's one-line variant was validated and fails one case; the third option was not run.

Two lines in FiniteStringsIterator. With the one-argument constructor (the only one LimitedFiniteStringsIterator offers), "" stays the first result, as today, so a small limit keeps its current output; only the trailing duplicate disappears. Regression tests for TestFiniteStringsIterator and TestLimitedFiniteStringsIterator are in the repro section.

// constructor (was: this.emitEmptyString = a.isAccept(0);)
this.emitEmptyString = a.getNumStates() > startState && a.isAccept(startState);

// pop branch in next() (was: if (a.isAccept(state)) {)
// depth == 0: we popped the start node; "" was already returned by the special case
if (depth > 0 && a.isAccept(state)) {
  return string.get();
}

Trade-offs

• With the three-argument constructor the startState change alters three more cases (state 0 is not startState; executed on stock and with the fix): (1) startState accepts and has a transition, state 0 does not accept: stock returns the correct "" last (["a", ""]), the fix first (["", "a"]), and the one-line variant drops it (["a"]); (2) the same startState with no transition: stock returns nothing, the fix returns [""], the zero-length path from an accepting startState; (3) startState does not accept but state 0 does (a separate side finding): stock returns a "" that is on no path from startState, the fix does not. Only GraphTokenStreamFiniteStrings uses that constructor in-tree; its tests pass with the fix, and the study found no impact there.
• It does not define every three-argument case: endState is checked only when a transition reaches it (:117, :130), so with startState == endState neither stock nor the fix treats the zero-length path as ending at endState, and all regression tests use endState == -1 (read). The fix is validated for LFV-021 and the existing callers, not for every (startState, endState) combination.
• Cost: no asymptotic change. The fix adds one comparison per pop and a constant-time guard in the constructor (not benchmarked); today a consumer pays for one extra result and one extra next() call per drained iterator.

What the checks validated

• The JUnit repro and the regression tests (3 classes, 21 tests, seed DEADBEEF): stock 5 failures, with assertions on and off; with the fix 0.
• Assertions off, seed 1234ABCD: util.automaton.*, util.graph.*, TestQueryBuilder, TestUnicodeUtil: 294 tests, 0 failures.
• :lucene:suggest:test 236 tests, :lucene:queryparser:test 533, TestConcatenateGraphFilter* 18: 0 failures.
• The whole :lucene:core:test with the fix, the regression tests and the repro: 748 classes, 8,873 tests, 0 failures, 322 skipped.
• :lucene:core:checkGoogleJavaFormat passes (tests formatted with tidy).
• Through the repro runner earlier: 142 core tests (seeds DEADBEEF and 1234ABCD) and 52 caller tests (seed DEADBEEF) pass stock and patched.

The study's one-line variant: if (depth > 0 && a.isAccept(state)), keeping emitEmptyString = a.isAccept(0).

Trade-offs

Fixes the repro, but for new FiniteStringsIterator(a, 1, -1) on 0 -x-> 1 (accept) -a-> 2 (accept) it drops the "" that stock Lucene returns correctly, because the special case still looks at state 0. It also leaves the separate state-0 side finding unfixed.

What the checks validated

With gradle: 21 tests, 1 failure, testEmptyStringFromAcceptingStartStateOtherThanZero expected:<2> but was:<1>. Through the repro runner the two start-state checks fail 2 of 2 (the dropped "", expected:<[, a]> but was:<[a]>, and the side-finding "", expected:<[b]> but was:<[, b]>); stock fails only the second.

Keep the special case only for a start state with no transitions (it is then never pushed).

Trade-offs

Also returns "" once, but last instead of first. The javadoc allows any order, but it changes which strings LimitedFiniteStringsIterator keeps at its limit (for a? with limit 1: "a" instead of ""). Not recommended.

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

• An AI tool ran the AutomatonMiscFuzzer target, which compares several automaton utilities with exact set oracles: <n-m> decimal intervals, makeBinaryInterval, makeStringUnion, FiniteStringsIterator, CompiledAutomaton.floor, finite concatenate and repeat(min, max). About 4.4 M executions in 10 + 20 minutes produced this finding. The study's attribution record classes it as a blind find.
• A separate AI verifier wrote its own 6-test JUnit (4 fail, the controls pass), ran 7.4.0, 8.11.4, 10.1.0 and main, confirmed the root cause with a one-line patch, and read the LUCENE-6365 discussion.
• On 2026-10-26 the hunt re-ran it on ea57360912ed (-ea, -da, 10.5.2), obtained a cross-model refute review, built the release matrix and searched for prior reports. For this page the fix was validated with gradle.