AutomatonTermsEnum throws ArrayIndexOutOfBoundsException for an NFA with a reachable dead state

Since 10.0.0 CompiledAutomaton runs non-deterministic automata (NFAs) directly, and its javadoc forbids dead states only for deterministic ones. It does not remove them from an NFA it runs that way. AutomatonTermsEnum, which the doc-values rewrite, SortedSetDocValues.intersect, MemoryIndex and every Terms without its own intersect use, builds the next candidate term from the smallest transitions and assumes every non-accepting state has one. When the walk reaches a dead end, a dead state with no transitions, NFARunAutomaton.getNextTransition reads past the end of its transition table: ArrayIndexOutOfBoundsException, with assertions on and off. The default codec with the default rewrite (block tree) returns the right answer. Only applications that build such an automaton themselves are affected; calling Operations.removeDeadStates for NFAs in the CompiledAutomaton constructor fixes it.

• CompiledAutomaton: the compiled form every AutomatonQuery (and RegexpQuery, WildcardQuery, ...) runs. For an NFA it keeps an NFARunAutomaton, which determinizes lazily: each DFA state is the set of NFA states the input could be in.
• AutomatonTermsEnum: the generic term enumerator for an automaton. From the current term it constructs the next term that could still match, by appending the smallest transition of each state, and seeks the terms dictionary there. Block tree has its own IntersectTermsEnum instead.

1. AutomatonQuery compiles the NFA with new CompiledAutomaton(automaton, false, true, isBinary) (AutomatonQuery.java:99). The NONE/ALL/SINGLE checks run only for DFAs ("simplify requires a DFA", CompiledAutomaton.java:159-160), so the NFA is NORMAL. Its UTF-8 form binary is non-deterministic too, so it is wrapped as is: new NFARunAutomaton(binary, 0x100) (:253-257; if either automaton were deterministic, the constructor would determinize binary instead, :258-261). Nothing removes dead states. The javadoc allows this: "For deterministic automaton, it must not have dead states ... For non-deterministic automaton, it will be executed using NFARunAutomaton" (:36-40).
2. DOC_VALUES_REWRITE gives the query an anonymous Terms over the doc values (DocValuesRewriteMethod.java:98-104); getTermsEnum calls terms.intersect(compiled, null) (CompiledAutomaton.java:348-357), and the default Terms.intersect builds an AutomatonTermsEnum (Terms.java:64-86). SortedSetDocValues.intersect builds one directly (SortedSetDocValues.java:109-119).
3. In NFARunAutomaton, the dead NFA state 1, a dead end, becomes the DFA state {1}. It has no outgoing transitions, so all 5 entries of its transition table (one per character class) are MISSING (NFARunAutomaton.java:399-403), and initTransition returns 0.
4. The first seek: the empty term does not match, so nextString (called at :223) takes the smallest transition out of the start state, "a", into {1} (AutomatonTermsEnum.java:283-291). For a state that is neither visited nor accepting it then takes the next smallest transition without checking the count (:294-302), trusting the comment "we work with a DFA with no transitions to dead states ... if it is not an accept state, then there MUST be at least one transition" (:297-299).
5. getNextTransition scans while (dState.transitions[++t.transitionUpto] == MISSING) (NFARunAutomaton.java:214) and reads index 5 of a 5-entry table. Its comment states the rule that was broken: "this shouldn't throw AIOOBE as long as this function is only called numTransitions times" (:215-216).

Which dead states trigger it: the walk stops at a state it has already visited, so the crash needs a dead end that the walk reaches. In the fact check's probe (doc-values rewrite, assertions on and off), the repro NFA throws; the same NFA with a self-loop on state 1 counts correctly (1, and 2 for the docs ax, axx, b, bc); {b, bc} with a dead end on "z", which sorts after every match, counts 1 for the doc "b" but throws for the docs "b" and "c"; an empty-language NFA ending in a dead end throws.

Block tree is fine for this repro because IntersectTermsEnum walks the terms that exist and takes a transition only when the state has one (IntersectTermsEnumFrame.java:123-137); here the dead end simply rejects.

NFA 0 -a-> 1, 0 -b-> 2, 0 -b-> 3, 3 -c-> 2, state 2 accepting (language {b, bc}); one document with SortedSetDocValuesField("f", "b"). Expected count 1; actual ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 at NFARunAutomaton.getNextTransition(NFARunAutomaton.java:214) from AutomatonTermsEnum.nextString(AutomatonTermsEnum.java:302). Controls: the same NFA over StringField("f", "b") with the default codec and default rewrite counts 1; DOC_VALUES_REWRITE over Operations.removeDeadStates(nfa) counts 1.

• Trigger. A non-deterministic automaton with a reachable dead end (a dead state with no transitions) that the term walk reaches, built by the application: Automaton / Automaton.Builder, an AutomatonProvider for RegExp <name> leaves, or Intervals.multiterm over a CompiledAutomaton. On main, since #15939 (11.0.0, unreleased), RegexpQuery no longer determinizes, so a provider-supplied NFA reaches NFARunAutomaton unchanged; the study's RegexpQuery + provider test fails the same way. That is most direct for a bare <name> leaf, whose automaton is returned as is; in composed expressions the cleaning operations usually remove dead states (code reading).
• Paths. Everything that enumerates through AutomatonTermsEnum: MultiTermQuery.DOC_VALUES_REWRITE (the repro), SortedSetDocValues.intersect / SortedDocValues.intersect, MemoryIndex, FilterLeafReader.FilterTerms wrappers without their own intersect, and postings formats without one. The default rewrite on a StringField with the SimpleText codec throws the same exception. The test framework's random codec can route even the default rewrite here: the cross-model reviewer's own default-rewrite control failed under it.
• Not affected. The default codec with the default rewrite (block tree) counts 1. Lucene's own builders, in the study's checks: no reachable dead state in any RegExp AST up to size 5 (1,127,357 ASTs) or in about 100k RegExp and 173k WildcardQuery NFAs from a random scan; LevenshteinAutomata (fuzzy) builds DFAs without dead states. concatenate, repeat, complement, intersection, union and reverse return removeDeadStates(...) of their result; optional ("This may create a dead state") and determinize do not, and the exhaustive RegExp check includes ?. Bounded evidence, not an API guarantee.
• Effect. An unchecked ArrayIndexOutOfBoundsException for that query, with assertions on and off. No wrong results, corruption or hang in the recorded runs; the probe's variants that do not throw (a self-loop on the dead state, a dead end the walk never reaches) return the right count. An empty-language NFA that ends in a dead end throws too.
• Scale. One document and one term are enough.

The test sits in org.apache.lucene.search, next to the upstream TestAutomatonQuery; unchanged, it is the suggested regression test (it fits as a new method of TestAutomatonQuery). The doc-values field keeps it independent of the randomized postings format: DOC_VALUES_REWRITE always enumerates through AutomatonTermsEnum. It fails on stock main and on the 10.0.0, 10.5.2 and 10.6.0 release jars, and passes with fix A or fix B.

Not shown by the test (same AutomatonTermsEnum code, executed elsewhere): SortedSetDocValues.intersect, MemoryIndex, a FilterTerms wrapper, RegexpQuery with an AutomatonProvider (the study's 10-test file) and the SimpleText codec with the default rewrite (a path probe).

cp TestAutomatonQueryNfaDeadState.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestAutomatonQueryNfaDeadState -Ptests.seed=DEADBEEF -Ptests.asserts=true
# assertions off: -Ptests.asserts=false instead (same result)

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=true (the same with =false)
TestAutomatonQueryNfaDeadState > testDocValuesRewriteOfNfaWithReachableDeadState FAILED
    java.lang.AssertionError: expected count 1, got java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:D6B9123FC978E9DF]:0)
        at org.apache.lucene.search.TestAutomatonQueryNfaDeadState.testDocValuesRewriteOfNfaWithReachableDeadState(TestAutomatonQueryNfaDeadState.java:56)

        Caused by:
        java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
            at org.apache.lucene.util.automaton.NFARunAutomaton.getNextTransition(NFARunAutomaton.java:214)
            at org.apache.lucene.index.AutomatonTermsEnum.nextString(AutomatonTermsEnum.java:302)
            at org.apache.lucene.index.AutomatonTermsEnum.nextString(AutomatonTermsEnum.java:223)
            at org.apache.lucene.index.AutomatonTermsEnum.nextSeekTerm(AutomatonTermsEnum.java:142)
            at org.apache.lucene.index.FilteredTermsEnum.next(FilteredTermsEnum.java:230)
            at org.apache.lucene.search.DocValuesRangeIterator.buildOrdinalSet(DocValuesRangeIterator.java:152)
            at org.apache.lucene.search.DocValuesRangeIterator.forOrdinalSet(DocValuesRangeIterator.java:194)
            at org.apache.lucene.search.DocValuesRewriteMethod$MultiTermQueryDocValuesWrapper$1$2.get(DocValuesRewriteMethod.java:174)
            ...

1 test completed, 1 failed

• Public contract. CompiledAutomaton (@lucene.experimental): "The Automaton could either be deterministic or non-deterministic, For deterministic automaton, it must not have dead states ... For non-deterministic automaton, it will be executed using NFARunAutomaton" (CompiledAutomaton.java:36-40). AutomatonQuery: the automaton "can be constructed with the org.apache.lucene.util.automaton API", and "terms that are accepted are considered a match" (AutomatonQuery.java:29-42, :59-65), with no restriction. MIGRATE.md 10.0: these classes "no longer determinize behind the scenes. It is the responsibility of the caller to call Operations.determinize() for DFA execution" (lucene/MIGRATE.md:922-926), so an undeterminized NFA is meant to run as an NFA.
• Path-dependent result. The same query counts 1 on block tree and throws on doc values, SimpleText or MemoryIndex. Nothing documents that.
• History. Before #225 the javadoc read "The Automaton must be deterministic, must not have dead states but is not necessarily minimal" and the constructor rejected NFAs. #225 (c972c6a7754e, LUCENE-10010) removed the check, scoped the dead-state rule to DFAs and wrapped NFAs as they are; the "MUST be at least one transition" loop stayed. In the LUCENE-10010 discussion rmuir wrote that the current algorithm "requires not just DFA, but also no dead states" (#11049).
• Maintainers clean dead states out of NFAs. #14218 added AutomatonTestUtil.assertCleanNFA; #14211/#14212 stopped reverse() from adding dead states.

Strongest case for "intended": AutomatonTermsEnum is @lucene.internal and its precondition is written in the code (private nextString javadoc, AutomatonTermsEnum.java:190-191, and the comment at :297-299). For DFAs the same input is a documented violation, Lucene's own producers did not create such an NFA in the study's checks, and the same input threw in every sampled release from 4.0.0 to 9.12.3. A maintainer could call it garbage in and only document the rule.

Why it fails: users do not call AutomatonTermsEnum directly; they call public AutomatonQuery, CompiledAutomaton or SortedSetDocValues.intersect, whose javadoc limits the rule to DFAs. In 4.x to 9.x the javadoc did forbid dead states; #225 dropped that rule for NFAs without adding cleanup. Block tree accepts the same input, and the fix costs one liveness pass that returns the input instance when nothing is dead. At the least, code and docs disagree; the cross-model reviewer reached the same verdict. Verdict: a defect, low severity.

Fix A and fix B were both run through gradle in a scratch worktree of 645d4fe14a20 (2026-11-01). A is recommended: it restores the guarantee AutomatonTermsEnum relies on for every consumer at once and makes the NFA path match the javadoc. B is cheaper on the normal path but fixes only the enumerator. C only documents the rule.

At the top of the 4-argument constructor, before the existing 0-state check (the study verifier's fix, re-applied to 645d4fe14a20).

   public CompiledAutomaton(
       Automaton automaton, boolean finite, boolean simplify, boolean isBinary) {
 
+    // AutomatonTermsEnum needs an automaton without dead states; an NFA is executed via lazy
+    // determinization, whose DFA states inherit any NFA dead state.
+    if (automaton.isDeterministic() == false) {
+      automaton = Operations.removeDeadStates(automaton);
+    }
+
     if (automaton.getNumStates() == 0) {

Trade-offs

• Covers every consumer at once: doc values, MemoryIndex, FilterTerms, SimpleText, Intervals. Before the 0-state check, an all-dead NFA (empty language) reuses that check; the study's empty-language NFA then returns 0.
• Cost: one liveness pass per compiled NFA (forward reachability, plus backward reachability over a reversed copy). The pass allocates these even when nothing is dead; only then does it return the input instance instead of a cleaned copy. Once per query construction, not per segment or term. On main, where #15939 and #15961 made RegexpQuery and WildcardQuery run NFAs directly, every non-deterministic regexp or wildcard automaton pays it although built-in NFAs are already clean.
• If removing dead states makes the automaton deterministic, the DFA path and its NONE/ALL/SINGLE simplification take over, which is correct.
• Scope: only non-deterministic input is cleaned; a DFA with dead states stays outside the documented DFA domain and can still fail. Cleaning before the UTF-8 conversion appears sufficient (UTF32ToUTF8.convert follows only reachable states; code reading, no dedicated test). AutomatonQuery keeps the caller's automaton for equals/toString, and its sharesAutomaton check counts a cleaned copy in RAM accounting.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20: the repro fails on stock main and passes with A, with -Ptests.asserts=true and =false.
• With A: 22 core test classes run 222 tests, 0 failures, 2 skipped (@Nightly): the repro, TestAutomatonQuery, TestAutomatonQueryUnicode, TestRegexpQuery, TestRegexpRandom, TestRegexpRandom2, TestWildcardQuery, TestWildcardRandom, TestPrefixQuery, TestPrefixRandom, TestFuzzyQuery, TestDocValuesRewriteMethod, TestMultiTermQueryRewrites, TestTermRangeQuery, TestCompiledAutomaton, TestNFARunAutomaton, TestOperations, TestAutomaton, TestRegExp, TestDeterminism, TestTermsEnum, TestTermsEnum2. The memory module runs 51 tests, 0 failures. :lucene:core:check -x test passes. The full core suite was not run.
• Earlier: the study's 10-test file passes 10/10; the cross-model reviewer's own test and TestCompiledAutomaton, TestAutomatonQuery and TestNFARunAutomaton pass with the fix shadowed.

In AutomatonTermsEnum.nextString(int, int) (:301), seek to the prefix that led into a dead state instead of taking a transition it does not have.

-          transitionAccessor.initTransition(state, transition);
+          if (transitionAccessor.initTransition(state, transition) == 0) {
+            // a dead state, which an NFA may have: seek to this prefix, the terms dictionary and
+            // backtracking take it from there
+            return true;
+          }
           transitionAccessor.getNextTransition(transition);

Trade-offs

One comparison on the normal path. By code reasoning the prefix is still a valid lower bound: the terms dictionary seeks to the next real term, which is checked as usual, and the next nextString backtracks past the dead branch. Narrower: it fixes only AutomatonTermsEnum, its "no dead states" comment and javadoc need rewording, and a dead branch costs an extra seek. The tested cases pass; repeated seeks or loops are not ruled out by those suites, so broader randomized testing would be prudent before preferring B.

What the checks validated

Gradle, same worktree: the repro passes with B, with assertions on and off; the same 22 core test classes run 222 tests, 0 failures, 2 skipped. The memory module and the static checks were not run with B.

Say in the CompiledAutomaton and AutomatonQuery javadoc that NFAs must not have dead states either (callers can use Operations.removeDeadStates), optionally with a check that throws IllegalArgumentException (Operations.hasDeadStatesFromInitial; hasDeadStates would also reject harmless unreachable states).

Trade-offs

Least behaviour change, but without the check the result still differs between block tree and the other paths; the check costs the same liveness pass as A. Not tested.

Method: semi-formal (bounded-exhaustive end-to-end translation validation). The prior study's automaton harness compares Lucene's automaton code with an exact reference semantics. One check indexes 161 terms and, for every automaton with at most 2 states and labels {a}, {b}, [a-b] (16,401 automata) and their determinizations, compares the terms that getTermsEnum, AutomatonTermsEnum and Terms.intersect return with the exact accepted set. 10 of the 16,401 failed in 4 s; over all scopes the failures (158 code-point and 66 binary cases) were all NFAs with a reachable dead state.

The study's verifier wrote its own 10-test file (block tree correct; doc-values rewrite, SortedSetDocValues.intersect, MemoryIndex, a FilterTerms wrapper and RegexpQuery + provider fail), a plain main() without assertions, a scan of built-in producers, and the fix. The hunt then reduced it to the one-test repro and re-verified it on main and releases.