AutomatonToTokenStream throws ArrayIndexOutOfBoundsException for the empty automaton (Automata.makeEmpty())

AutomatonToTokenStream.toTokenStream(Automaton) (lucene-core, public, no @lucene.internal or @lucene.experimental tag) turns an acyclic automaton into a token graph; its only stated precondition is "This requires the automaton be a finite DAG" (AutomatonToTokenStream.java:44, :46). Lucene's normal value for the empty language has no states: Automata.makeEmpty() ("a new (deterministic) automaton with the empty language", Automata.java:55-60), an empty makeStringUnion, RegExp #, and empty results of Operations.intersection, minus or removeDeadStates. For such an automaton the method sizes int[] indegree to the number of states, 0 (:52, :54), and reads indegree[0] at :61 to check that the start state has no incoming edges, without checking that a state exists, so the JVM throws ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0 with assertions on and off. The same empty language written as one non-accepting state already gives a stream with 0 tokens, as does Automata.makeEmptyString(). The read dates from the class's introduction in #157 (LUCENE-9963, 8.10.0); every release since fails, and it is not fixed upstream. A 4-line guard that returns the empty-string stream for 0 states fixes it (validated); throwing a clear IllegalArgumentException is the alternative. Low impact: no Lucene production code calls the converter, and no downstream use was found.

• Automaton (org.apache.lucene.util.automaton, @lucene.experimental): states are integers, "State 0 is always the initial state" (Automaton.java:37-38); transitions carry character ranges; accept states end a match.
• Empty language: the automaton accepts no string at all. Lucene's usual form has 0 states: Automata.makeEmpty() is new Automaton() plus finishState() (Automata.java:55-60), and Operations.isEmpty calls 0 states the "Common case" of the empty language (Operations.java:799-803). One non-accepting state with no transitions has the same language.
• AutomatonToTokenStream.toTokenStream (org.apache.lucene.analysis, lucene-core, public): "Nodes that have the same distance from the start are grouped together to form the position nodes for the TokenStream"; "This requires the automaton be a finite DAG" (AutomatonToTokenStream.java:40-47). It was added as a helper for the FlattenGraphFilter tests.

1. Transition[][] transitions = automaton.getSortedTransitions(); (:52) has one row per state (Automaton.java:116-118): for 0 states, length 0.
2. int[] indegree = new int[transitions.length]; (:54): length 0. The loop that counts in-degrees (:56-60) runs 0 times.
3. if (indegree[0] != 0) (:61) checks that the start state has no incoming edges and would throw IllegalArgumentException("Start node has incoming edges, creating cycle"). With no state 0, the read itself throws ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0, before the check can run.
4. With 1 non-accepting state, the same empty language passes: indegree is [0], the check passes, the walk (:65-85) puts state 0 at position 0, there are no edges, and the stream has 0 tokens. makeEmptyString() (1 accepting state) takes the same path.

Automata.makeEmpty(): 0 states, indegree.length 0, exception. Nine public ways to a 0-state automaton all throw the same way: Automata.makeEmpty(), Automata.makeStringUnion of an empty list, RegExp # and a&b (with RegExp.ALL), Operations.intersection(makeString("a"), makeString("b")), Operations.minus of two equal languages, Automata.makeCharRange(5, 4), an empty Automaton.Builder, and Operations.removeDeadStates of one non-accepting state. Controls: the 1-dead-state form and makeEmptyString() give 0 tokens. These nine inputs and two controls ran on main (assertions on and off), 10.5.2 and 9.12.3 (assertions off), all with the same result. makeEmpty() also fails on 10.6.0 (the minimal test, assertions on), and makeEmpty() and the empty intersection fail on all 40 releases from 8.10.0 to 10.5.2 (assertions on), where the controls makeEmptyString() and makeString("abc") give 0 and 3 tokens.

• Who is hit. Code that calls AutomatonToTokenStream.toTokenStream with an automaton whose language is empty in its 0-state form, for example (illustrative, not found in any project) a helper that builds an automaton from a possibly empty list of strings with Automata.makeStringUnion, or that intersects two automata and converts the result.
• Who is not hit. No Lucene production code calls the converter: its only callers in the tree are the tests TestAutomatonToTokenStream (core) and TestFlattenGraphFilter (analysis-common). A GitHub code search found 0 files in Elasticsearch, OpenSearch and Solr, and 53 files overall, all copies of Lucene. No query, analyzer, parser or index path reaches it.
• What happens. One ArrayIndexOutOfBoundsException whose message ("Index 0 out of bounds for length 0") points into the converter, not at the input.
• What does not happen. No wrong tokens, no hang, no memory growth; the input automaton is not changed and nothing is written.
• Default vs opt-in, scale. Opt-in: only an application that uses this utility. No setting is involved, and data size plays no part: the trigger is exactly an automaton with 0 states. Deterministic, with assertions on and off.
• How likely. Rare. The class was added in #157 as test infrastructure for FlattenGraphFilter (the reviewer called it "helpful infrastructure for future testing" and "a nice utility API"), and no report of this failure was found in the five years since 8.10.0.

TestAutomatonToTokenStreamZeroStates calls AutomatonToTokenStream.toTokenStream(Automata.makeEmpty()). As the adjudication asked, it accepts either outcome a fix may choose: an empty stream (checked with assertTokenStreamContents) or an IllegalArgumentException. An ArrayIndexOutOfBoundsException is rethrown as an AssertionError that states expected and actual, with the original as its cause. Automata.makeEmpty() is the smallest input (0 states, 0 transitions). Public API only (it sits in org.apache.lucene.analysis next to AutomatonToTokenStream, by Lucene convention); no randomness of its own, so the seed does not matter (seeds DEADBEEF and 5EED1234 gave the same failure). It compiles on 9.1 and later (it needs org.apache.lucene.tests.analysis.BaseTokenStreamTestCase).

As the regression test: this same test, for example as a new method in TestAutomatonToTokenStream. Name the unused catch parameter _ instead of acceptable (Lucene's convention): ./gradlew :lucene:core:check runs an ecj lint that rejects an unused named exception parameter. With that one-word change the test still fails on stock main with assertions on and off, passes with fix A, and ./gradlew :lucene:core:check -x test passes with it as a new test file. If the maintainer picks option B, the test can become expectThrows(IllegalArgumentException.class, () -> AutomatonToTokenStream.toTokenStream(Automata.makeEmpty())). Once a fix is chosen, the committed test should assert that one behaviour rather than accept both.

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

TestAutomatonToTokenStreamZeroStates > testMakeEmpty FAILED
    java.lang.AssertionError: expected an empty TokenStream or IllegalArgumentException, got java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:3799068DECC9FD1A]:0)
        at org.apache.lucene.analysis.TestAutomatonToTokenStreamZeroStates.testMakeEmpty(TestAutomatonToTokenStreamZeroStates.java:32)

        Caused by:
        java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
            at org.apache.lucene.analysis.AutomatonToTokenStream.toTokenStream(AutomatonToTokenStream.java:61)
            at org.apache.lucene.analysis.TestAutomatonToTokenStreamZeroStates.testMakeEmpty(TestAutomatonToTokenStreamZeroStates.java:28)

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions off (the test with its catch parameter named _, same lines); the same with assertions on.
# 10.6.0: the same at AutomatonToTokenStream.java:60; 9.12.3: at :65.

• Contract. AutomatonToTokenStream.java:44: "This requires the automaton be a finite DAG." :46: "@param automaton automaton to convert. Must be a finite DAG to avoid infinite loops!" Nothing says the automaton must have a state. The class has no @lucene.internal or @lucene.experimental tag (the automaton classes it takes, Automaton, Automata and Operations, are @lucene.experimental).
• A standard input. Automata.makeEmpty(): "Returns a new (deterministic) automaton with the empty language." (Automata.java:55), with 0 states. Operations.isEmpty treats 0 states as the common empty case (Operations.java:799-803).
• Representation, not language, decides the outcome. The same empty language as 1 dead state gives a stream with 0 tokens (executed); as 0 states it crashes.
• Its own validation throws IllegalArgumentException. Its two explicit checks reject a start state with incoming edges (:61-63) and leftover cycles (:87-91) with IllegalArgumentException, and the upstream tests assert exactly that (TestAutomatonToTokenStream.java:105-120 and :122-136, expectThrows(IllegalArgumentException.class, ...)).
• Precedent. Lucene's own topological sort of automata (org.apache.lucene.util.automaton, today Operations.topoSortStates) got an explicit 0-state guard in LUCENE-6365 (ae4723e0b50, 2015, "fix buggy Operations.topoSort; add test"), today Operations.java:1366-1368.
• No sign of intent. The introducing PR #157 and LUCENE-9963 never mention empty or 0-state automata; no upstream test passes one; no CHANGES or MIGRATE entry.

The strongest case for "not a bug" (the intended-behaviour checker's and the cross-model reviewers'): the javadoc builds positions from "distance from the start" (:42) and Automaton says "State 0 is always the initial state" (Automaton.java:37-38), so an automaton with no states has no start and could be read as outside the method's domain; and the class is a test-oriented helper.

Why it fails: nothing documents that precondition, while the documented one (a finite DAG) holds; the method already handles the same language when it has one dead state; an input the method does not accept should get the method's own IllegalArgumentException, not an index error from its validation line; and "test-oriented" bears on severity, not on validity, since the class is public API in the lucene-core jar. Residual: a maintainer may prefer to reject 0 states with an IllegalArgumentException rather than return an empty stream. That is a choice of fix (option B), and the repro accepts it.

The choice is the maintainer's: this doc suggests A because the 0-state form then behaves like the 1-dead-state form of the same language; the cross-model fact check of the brief would make B the default, because it states the implicit start-state requirement and does not merge the empty language with the empty string. Both are validated; neither is shown to be better. Fix A was validated through gradle in a scratch worktree of 645d4fe14a20. Option B, the alternative the adjudication asked to offer, was validated with the fix shadowed into the stock jars only.

Before reading indegree, return the stream that the method already builds for makeEmptyString() and for the 1-dead-state form: one position layer with no edges.

--- a/lucene/core/src/java/org/apache/lucene/analysis/AutomatonToTokenStream.java
+++ b/lucene/core/src/java/org/apache/lucene/analysis/AutomatonToTokenStream.java
@@ -49,6 +49,10 @@
   public static TokenStream toTokenStream(Automaton automaton) {
     List<IntArrayList> positionNodes = new ArrayList<>();
 
+    if (automaton.getNumStates() == 0) {
+      // the empty language: no tokens (same stream as for the empty string)
+      return new TopoTokenStream(List.of(List.of()));
+    }
     Transition[][] transitions = automaton.getSortedTransitions();
 
     int[] indegree = new int[transitions.length];

Trade-offs

• The 0-state form of the empty language then behaves like its 1-dead-state form, which already returns this stream. No change for any automaton with at least one state.
• The stream is the one makeEmptyString() gives, so it cannot tell the empty language from the empty string; that is already true for the 1-dead-state form. In the other direction, TokenStreamToAutomaton turns this stream into an automaton that accepts nothing (executed on the stream of makeEmptyString(), which is this stream). A cross-model reviewer suggested the code comment not imply that the two languages are the same in general.
• Keep the one empty layer: with List.of() (no layer), end() would call setOffset(-1, -1), because it uses edgesByPos.size() - 1 (:165-170, code reading).

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, 2026-11-01: without the fix the repro fails with assertions on and off; with it, it passes with assertions on and off.
• Every core test class in org.apache.lucene.analysis with the fix (TestAutomatonToTokenStream, TestGraphTokenizers, the repro and 19 more): 22 classes, 169 tests, 0 failures.
• TestFlattenGraphFilter (analysis-common), the other in-tree user of the converter: 25 tests, 0 failures.
• ./gradlew :lucene:core:check -x test with the fix and the repro (catch parameter named _) as a new test file: passes (google-java-format, ecj lint of main and test code, forbidden APIs; error-prone skipped). The full Lucene test suite was not run.
• Earlier, with the fix shadowed into the stock jars: the finder's repro with the upstream TestAutomatonToTokenStream (9 tests), the independent reproducer's 6 tests and the minimal repro with assertions on and off pass.

Throw the method's own exception type with a message that names the cause, and document it in the javadoc.

+    if (automaton.getNumStates() == 0) {
+      throw new IllegalArgumentException("Automaton has no states (empty language)");
+    }

Trade-offs

• Explicit, and it does not equate the empty language with the empty string.
• The outcome still depends on the representation (1 dead state gives an empty stream, 0 states throws), so the javadoc should say that an automaton with no states is rejected, and callers must special-case empty languages before converting.

What the checks validated

• Shadowed into the stock 645d4fe14a20 jars (standalone, assertions on): the minimal repro and the upstream TestAutomatonToTokenStream pass, 7 tests, 0 failures. Not run through gradle.

• Method: bounded-exhaustive translation validation, the hunt's semi-formal tier, in the hunt unit on token-graph and automaton conversion. The unit compared the stock jar's token graphs with an independent model of the documented construction over all small automata with at least one state (for example all 33,554,432 topologically numbered 5-state automata over {a, b}). In every automaton in scope the jar threw nothing other than IllegalArgumentException.
• The hint: the model needs a start state, so its precondition excluded 0 states; writing that down showed that the code reads indegree[0] with no such check.
• Witness: a JUnit test on the stock main jar (makeEmpty(), an empty intersection, and a makeEmptyString() control) failed on both empty inputs while the control passed; a shadowed 4-line fix made it pass.
• Later: an independent reproducer, an intended-behaviour devil's advocate, cross-model reviews and an adjudication checked it (2026-10-28); the history was checked by execution over 40 releases; the test was reduced to one test method (2026-10-29) and re-verified on main 645d4fe14a20.