RunAutomaton throws ArrayIndexOutOfBoundsException on a 0-state automaton

new CharacterRunAutomaton(new Automaton.Builder().finish()) throws ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0 instead of returning a run automaton that accepts nothing. The input is a valid deterministic automaton with 0 states, the empty language. RunAutomaton gives a 0-state input one synthetic, non-accepting start state (size = Math.max(1, a.getNumStates())), but then loops over that synthetic state and asks the source automaton for state 0's transitions; Automaton.next reads states[0] of the source. Automaton.Builder.finish() sizes states[] exactly (numStates * 2 = 0 entries), so the read fails. Automata.makeEmpty(), also 0 states, works only because new Automaton() pre-allocates 4 slots. The same crash comes from ByteRunAutomaton, new Automaton(0, 0), Operations.repeat(emptyLanguage, 2, 2) and string patterns built on a bounded repeat {n} or {n,m} (n >= 1) of an empty-language operand, so new SimplePatternTokenizer("(a&b){2}") throws too (the same operand under {n,}, *, + or plain concatenation does not crash). Queries are protected by CompiledAutomaton's 0-state guard. Every release since 5.0.0 is affected: LUCENE-5959 made finish() allocate exact-size arrays.

// RunAutomaton.java:67-83 (constructor)
points = a.getStartPoints();                    // always holds MIN_CODE_POINT: points.length >= 1
size = Math.max(1, a.getNumStates());           // :68  1 for a 0-state automaton
accept = new FixedBitSet(size);
transitions = new int[size * points.length];
Arrays.fill(transitions, -1);                   // the synthetic state already rejects everything
Transition transition = new Transition();
for (int n = 0; n < size; n++) {                // :73  n = 0, but the source has no state 0
  if (a.isAccept(n)) { accept.set(n); }         // :74  java.util.BitSet.get(0) is false: no crash
  transition.source = n;
  transition.transitionUpto = -1;
  for (int c = 0; c < points.length; c++) {
    int dest = a.next(transition, points[c]);   // :80  -> Automaton.java:676 -> :694 states[2 * 0]

• Automaton.java:690-694: the private next reads states[stateIndex] with stateIndex = 2 * state, so state 0 reads states[0].
• Automaton() is this(2, 2) (Automaton.java:79-82, "creates an automaton with no states"): states has length 4, so the read returns leftover zeros, "0 transitions". That is why Automata.makeEmpty() (Automata.java:55-60) works.
• Automaton(int numStates, int numTransitions) allocates states = new int[numStates * 2] (Automaton.java:91-92), and Automaton.Builder.finish() builds its result with exactly new Automaton(numStates, numTransitions) (Automaton.java:889-894, "Create automaton with the correct size."). A Builder with no states yields states.length == 0.
• Regexp route: every bounded repeat {n} or {n,m} goes through Operations.repeat(a, min, max) (RegExp.java:672-674, Operations.java:291-323). For min == 1 it copies the operand into new Automaton() (:299-301), for min >= 2 it concatenates min copies (:302-308); either way it copies the result into a Builder and returns removeDeadStates(builder.finish()) (:311-312, :322), which hands a 0-state input back unchanged (:1010-1011). So for an empty-language operand such as (a&b), # or [^\D\d] and min >= 1 the result has 0 states, exact-size arrays, and reports itself deterministic: (a&b){1}, (a&b){1,3}, (a&b){2}, #{2,10} crash, while (a&b){2,}, (a&b)*, (a&b)+, (a&b)(a&b), x(a&b){1} and (a&b){0,2} do not. Kleene star and intersection return a 0-state input unchanged (:202-204, :396-401), so ((a&b){2})* and (a&b){2}&(a&b){2} crash too, while ((a&b){2})+ and (a&b){2}|(a&b){2} do not (probes on 645d4fe14a20).
• Tokenizer route: SimplePatternTokenizer(String) ("See RegExp for the accepted syntax") builds new RegExp(regexp).toAutomaton(), checks only determinism and calls new CharacterRunAutomaton(dfa) (SimplePatternTokenizer.java:75-101); the same in SimplePatternSplitTokenizer.java:64-91. SimplePatternTokenizerFactory parses the pattern in its constructor, which succeeds, and the crash appears when create() is called (SimplePatternTokenizerFactory.java:73-75, 87-88).
• Why queries are safe: CompiledAutomaton replaces a 0-state automaton with a fresh 1-state automaton before it builds a run automaton (CompiledAutomaton.java:154-157). AutomatonQuery builds one (AutomatonQuery.java:99), and RegexpQuery, WildcardQuery, PrefixQuery and TermRangeQuery extend it; FuzzyQuery uses CompiledAutomaton too (FuzzyAutomatonBuilder.java:63, :73). A search of every non-test source file for run-automaton constructions finds three other query-side places, none of which builds one from an exact-size 0-state automaton: TermInSetQuery (only for 2 or more terms, TermInSetQuery.java:185-195), the unified highlighter (Automata.makeString, or makeStringUnion, which returns makeEmpty() for no terms, Automata.java:642-643) and the sandbox TermAutomatonQuery (rewrites an empty automaton to MatchNoDocsQuery, TermAutomatonQuery.java:491-493).

For new Automaton.Builder().finish(): getNumStates() = 0, states.length = 0, getStartPoints() = [0], so RunAutomaton sets size = 1 and reads states[0] once: Index 0 out of bounds for length 0. For Automata.makeEmpty(): 0 states but states.length = 4, so the read returns 0 transitions and run("") and run("a") are false. A survey of 15 ways to build a 0-state automaton crashes in exactly the cases with states.length = 0.

• Who. (a) Code that constructs a CharacterRunAutomaton or ByteRunAutomaton directly from an empty-language automaton built through Automaton.Builder, new Automaton(0, 0) or Operations.repeat(empty, min >= 1, max); (b) SimplePatternTokenizer, SimplePatternSplitTokenizer and their factories with a pattern built on a bounded repeat {n} or {n,m} (n >= 1) of an empty-language operand, such as (a&b){2}, (a&b){1}, #{2,10}, ([^\D\d]){2} or ((a&b){2})*; the same operand under {n,}, *, + or plain concatenation does not crash. Such patterns are valid RegExp syntax; they can never match.
• Not default. It needs code that builds a run automaton itself, or a SimplePattern* tokenizer or factory configured with such a pattern. Queries build theirs through CompiledAutomaton or never from an exact-size 0-state automaton (source inventory); RegexpQuery on the same patterns returns 0 hits with no exception.
• Effect. An unchecked ArrayIndexOutOfBoundsException from a constructor instead of a reject-everything matcher. Through a factory the factory constructor succeeds and create() throws. No wrong results, no corruption, no hang.
• Scale. One call, no index.

• Smallest input. The Builder with no states is the smallest automaton there is; one call, one thread, no randomness. Same result with assertions on and off and with two seeds (DEADBEEF, C0FFEE).
• API. Public only (Automaton.Builder, CharacterRunAutomaton); the package org.apache.lucene.util.automaton is for locality, no package-private API is used.
• Releases. The same test fails on 10.5.2 and 10.6.0; a main() form of it fails on every release from 5.0.0 to 10.6.0 (all 108) and passes on 4.10.0 to 4.10.4.
• As the regression test: this same method. Upstream it can live in TestAutomaton or a small new class; the try/catch may go, the AIOOBE then shows as the test error (not run in that form).

cp $REPRO/TestRunAutomatonZeroStates.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/automaton/
cd $LUCENE
./gradlew :lucene:core:test --tests org.apache.lucene.util.automaton.TestRunAutomatonZeroStates -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same exception)

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on
TestRunAutomatonZeroStates > testRunAutomatonFromBuilderWithNoStates FAILED
    java.lang.AssertionError: new CharacterRunAutomaton(0-state automaton) threw java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:5E2D81154F1689AE]:0)
        at org.apache.lucene.util.automaton.TestRunAutomatonZeroStates.testRunAutomatonFromBuilderWithNoStates(TestRunAutomatonZeroStates.java:30)

        Caused by:
        java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
            at org.apache.lucene.util.automaton.Automaton.next(Automaton.java:694)
            at org.apache.lucene.util.automaton.Automaton.next(Automaton.java:676)
            at org.apache.lucene.util.automaton.RunAutomaton.<init>(RunAutomaton.java:80)
            at org.apache.lucene.util.automaton.CharacterRunAutomaton.<init>(CharacterRunAutomaton.java:27)
            at org.apache.lucene.util.automaton.TestRunAutomatonZeroStates.testRunAutomatonFromBuilderWithNoStates(TestRunAutomatonZeroStates.java:27)
1 test completed, 1 failed
# gradle, assertions off (-Ptests.asserts=false): the same AssertionError and cause
# 10.5.2 release jars, assertions on and off: the same exception at the same line numbers
# with the recommended fix: BUILD SUCCESSFUL, 1 test, 0 failures (assertions on and off)

• Contract. RunAutomaton.java:55-60: "Constructs a new RunAutomaton from a deterministic Automaton. ... @throws IllegalArgumentException if the automaton is not deterministic". CharacterRunAutomaton.java:21-25 ("Construct from a DFA") and ByteRunAutomaton.java:22-35 document only the same exception.
• 0-state automata are first-class. Automaton.java:79 "creates an automaton with no states"; Automata.java:55 "Returns a new (deterministic) automaton with the empty language" (0 states); Operations special-cases getNumStates() == 0 in many places, e.g. Operations.java:202-205, "Repeating the empty automata will still only accept the empty automata".
• RunAutomaton means to support them. size = Math.max(1, a.getNumStates()) (RunAutomaton.java:68) exists only to give a 0-state input a start state; the class javadoc says "The initial state is always 0" (:38).
• Lucene relies on it. MockTokenFilter.EMPTY_STOPSET, "Empty set of stopwords", is new CharacterRunAutomaton(makeEmpty()) (test framework, MockTokenFilter.java:43-44); it works only because makeEmpty() carries spare capacity.
• Tests. TestRegExp.testRepeatWithEmptyLanguage (TestRegExp.java:107-117) builds #{2,10} and checks only toString(); nothing asserts a run automaton must refuse such input.
• History. The crash appeared with LUCENE-5959 (#7021), a 5.0.0 memory optimization that made finish() exact-size; it did not discuss 0-state automata. 4.10.4 passes the same check (its main() form).
• Precedent. LUCENE-6054 (#7116, "RegExp.toAutomaton fails on #*"), an earlier empty-language edge case, was fixed under Bug Fixes.

Strongest case for "not a bug": RunAutomaton and Automaton are @lucene.experimental low-level APIs, and callers should go through CompiledAutomaton, which already handles 0 states; direct construction from a 0-state automaton is unsupported. For the tokenizers, the class javadoc says "The provided regex should match valid token characters" (SimplePatternTokenizer.java:33-34), so a maintainer may see a never-matching pattern as invalid configuration and prefer a clear IllegalArgumentException.

Why it fails: @lucene.experimental is about API stability, not correctness; no javadoc states that precondition; the CompiledAutomaton guard shows the case is known but is not a contract on RunAutomaton; Lucene's own MockTokenFilter and the pattern tokenizers construct run automata directly; and SimplePatternTokenizer is a public, string-configured API that reaches the crash with valid RegExp syntax. That javadoc sentence contrasts token characters with separators; it does not say the pattern must be able to match, and an AIOOBE from inside RunAutomaton is not a validation error. A cross-model reviewer (OpenAI GPT-5.6) built the API argument, rated it weak and voted real with high confidence; a second cross-model fact check rated the intended-behaviour case moderate because of the javadoc sentence and still found fix A the most defensible default.

One validated option and two alternatives that were not run. A is the smallest change at the place that invents the extra state; B and C only move or narrow the guard.

Keep size = Math.max(1, a.getNumStates()) for the tables, but query the source only for states it has. The synthetic state 0 is already initialised as non-accepting with every transition -1 by new FixedBitSet(size) and Arrays.fill(transitions, -1).

// RunAutomaton.java:73
-    for (int n = 0; n < size; n++) {
+    // size is max(1, numStates); only query states that exist in the source automaton. A 0-state
+    // automaton keeps the synthetic state 0 as non-accepting with all transitions = -1.
+    final int numStates = a.getNumStates();
+    for (int n = 0; n < numStates; n++) {

Trade-offs

• For every automaton with at least one state numStates == size: same table, same cost; constructor only, no hot-path change.
• Fixes every caller at once: direct CharacterRunAutomaton / ByteRunAutomaton users, both pattern tokenizers and their factories.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, OpenJDK 25.0.3, seed DEADBEEF: the minimal test fails before the change and passes after it, with assertions on and off.
• :lucene:core:test over org.apache.lucene.util.automaton.* plus TestRegexp*, TestAutomatonQuery*, TestWildcard*, TestTermInSetQuery, TestFuzzyQuery, TestTermsEnum*: 28 classes, 322 tests, 4 skipped, 0 failures.
• :lucene:analysis:common:test over org.apache.lucene.analysis.pattern.* (incl. TestSimplePatternTokenizer, TestSimplePatternSplitTokenizer): 11 classes, 82 tests, 2 skipped, 0 failures.
• :lucene:core:checkGoogleJavaFormat: clean.
• Earlier and independently: the study's 14 tests and Lucene's 220 prebuilt core automaton tests pass with it; the cross-model reviewer's SimplePatternTokenizer("(a&b){2}") test and TestRegExp (9/9) pass with it.

Allocate at least 2 states[] slots even for 0 states in Automaton(int, int) (Automaton.java:92), the only place states[] is allocated (Builder.finish() uses it at :894; elsewhere it is only grown, :209, :359). Not run.

Trade-offs

It would cover every way of building a 0-state automaton, and with a 2-slot minimum only 0-state automata get more memory. But it hides the read of a state that does not exist instead of removing it (RunAutomaton would still read state 0 of a 0-state source and rely on spare zeros), and it changes a shared core constructor for a RunAutomaton problem. Not recommended.

Replace a 0-state automaton with a 1-state non-accepting one in SimplePatternTokenizer and SimplePatternSplitTokenizer before new CharacterRunAutomaton(dfa). Not run.

Trade-offs

Fixes the tokenizer path only; direct CharacterRunAutomaton / ByteRunAutomaton users keep the crash. Not recommended alone.

• The study's fuzzing unit ran RegexDiffFuzzer (Jazzer): random regex syntax trees rendered both as Lucene RegExp and as java.util.regex and compared, plus self-consistency across Operations.run, ByteRunAutomaton, CompiledAutomaton and the automaton operations. It reported the AIOOBE with ([^\D\d]){2} and Builder().finish() as triggers.
• An independent verifier wrote 14 tests from scratch (triggers, controls, a survey of 15 constructions, the tokenizer and factory paths, query and highlighter controls), probed release jars, and validated the loop-bound fix against Lucene's 220 core automaton tests.
• The hunt minimised it to one method, re-ran it on main and 10.5.2, bisected the introducing commit on both branches, swept every release, and had a cross-model review.