CompiledAutomaton.floor throws NullPointerException for empty, match-all and single-term automata, and for non-deterministic ones

CompiledAutomaton.floor(input, output) promises the largest term the automaton accepts that is <= input, or null. The documented one-argument constructor passes simplify=true, which stores an empty or single-string language, and a match-all one its approximate totality test recognizes, as type NONE, SINGLE or ALL with no state machine (runAutomaton and automaton are null); since 10.0.0 an automaton that is non-deterministic, and still so in UTF-8, stays type NORMAL but runs on an NFARunAutomaton, again with runAutomaton null. floor walks runAutomaton and automaton without checking the type, so for all four forms it throws NullPointerException instead of answering: new CompiledAutomaton(Automata.makeString("m")).floor("x") throws where "m" is expected, with assertions on and off. NONE, ALL and SINGLE have failed since the method was created (LUCENE-3030, first released in 4.0.0); the NFA form is a 9.x-to-10.0 regression (#225), where 9.12.3 returns the right floor. Only application code that calls the experimental floor itself is hit: Lucene's own caller (FuzzyTermsEnum) uses plain DFAs. A fix that answers the three special forms directly and runs NORMAL through the DFA-or-NFA accessors was validated; for an NFA with a dead state it still returns a wrong floor, so it needs the no-dead-states rule the class already states for DFAs.

1. The default constructor simplifies. public CompiledAutomaton(Automaton automaton): "Create this, passing simplify=true, so that we try to simplify the automaton" (:106-109).
2. Three special forms keep no state machine. With simplify and a DFA (:160), an empty language becomes NONE (:166-177), a total one ALL when the totality test recognizes it (:181-199; the code comment calls it "only approximate, because automaton may not be minimal") and a single string SINGLE (:203-221). Each branch sets runAutomaton = null and this.automaton = null and returns.
3. NFAs keep no DFA either (10.0.0 and later). Other input becomes NORMAL (:224). If it and its UTF-8 form are both non-deterministic (:253), with or without simplify, the constructor sets automaton and runAutomaton to null and builds an NFARunAutomaton (:253-257). The class javadoc allows this: the automaton "could either be deterministic or non-deterministic", and an NFA "will be executed using NFARunAutomaton" (:36-40).
4. floor never checks. floor (:390) calls runAutomaton.isAccept(state) for an empty input (:398), runAutomaton.step(state, label) for each byte (:411), then automaton.getNumTransitions (:433) and addTail, which walks automaton too (:277-339). There is no switch (type) and no null check.
5. The siblings do check. getTermsEnum (:348-362) and visit (:365-382) switch on the type, and NORMAL consumers such as AutomatonTermsEnum use getByteRunnable() / getTransitionAccessor() (:486-493, :516-523; AutomatonTermsEnum.java:85-86). Where Lucene requires NORMAL it rejects the other forms with IllegalArgumentException: Terms.intersect, which also documents it (Terms.java:58, :79-81), and the AutomatonTermsEnum constructor (AutomatonTermsEnum.java:81-83; its javadoc does not mention it).
6. Why Lucene itself never hits it. The only non-test caller, FuzzyTermsEnum.getAutomatonEnum (FuzzyTermsEnum.java:185), gets its automata from FuzzyAutomatonBuilder as new CompiledAutomaton(levBuilder.toAutomaton(i, prefix), true, false) (FuzzyAutomatonBuilder.java:63, :73): simplify=false Levenshtein DFAs, always NORMAL with a runAutomaton. Upstream's floor test builds its automata the same way (TestCompiledAutomaton.java:38-60).

For an empty input the NPE comes from isAccept at :398 instead. The NFA-backed form also comes from the constructors with simplify=false, since that branch does not depend on simplify. The ALL row's "x" is exact for valid UTF-8 input (see the fixes).

• Who is hit. Code that calls CompiledAutomaton.floor directly. The failing instances come from ordinary inputs: the documented one-argument constructor on a single-string, empty or any-string automaton, a non-deterministic automaton on 10.x that stays non-deterministic in UTF-8 (for example new RegExp("(a|ab)c").toAutomaton(), since RegExp stopped determinizing in 10.0.0), and AutomatonQuery.getCompiled() of RegexpQuery("m") (SINGLE) and WildcardQuery("*") (ALL), executed on 10.0.0, 10.5.2, 10.6.0 and main.
• Every call. Once code calls floor on such an instance, it fails deterministically, with assertions on and off. One term is enough; index size does not matter.
• Default vs opt-in. The trigger is the default constructor with ordinary inputs, but calling floor is an expert, opt-in act: the class is @lucene.experimental.
• Not hit. Lucene's own query paths: the only in-tree caller, the fuzzy query's terms enum, passes simplify=false Levenshtein DFAs. A code search of the default branches of Elasticsearch, OpenSearch and Solr found no call of floor on a CompiledAutomaton (not exhaustive).
• What goes wrong. A NullPointerException that does not name the real restriction, instead of the documented result. No wrong result, no hang, no lasting state.
• Regression for NFAs. On 9.12.3 the constructor and RegExp determinize, so floor("b") of (a|ab)c returns "ac"; from 10.0.0 it throws. In the 10.x releases the default RegexpQuery still holds a DFA; on main (#15939, unreleased) it keeps the NFA, so RegexpQuery("(a|ab)c").getCompiled() fails there too.

The class sits in org.apache.lucene.util.automaton, next to TestCompiledAutomaton, and uses nothing package-private. The catch only turns the NPE into a failure message that states expected vs actual; the cause is kept. Deterministic: 20 of 20 derived seeds fail the same way. It needs org.apache.lucene.tests.util, so it compiles on 9.1.0 and later.

SINGLE was chosen for the repro because it needs no assumption about RegExp determinization and fails in every release since 4.0.0. The same NPE for NONE (Automata.makeEmpty()), ALL (Automata.makeAnyString()) and, since 10.0.0, NFA-backed NORMAL (new RegExp("(a|ab)c").toAutomaton(), floor("b") expected "ac") is in the table under "The finding in 30 seconds".

Regression test: this same test, as written. With the recommended fix it passes, and the core format, ECJ and forbidden-apis checks pass with it in place. If upstream chooses to reject these forms instead, the same test becomes an expectThrows of that exception.

cp $REPRO/TestCompiledAutomatonFloorSingle.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/automaton/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.automaton.TestCompiledAutomatonFloorSingle -Ptests.seed=DEADBEEF
# assertions off fails the same way: add -Ptests.asserts=false (the recorded runs added --offline --no-daemon)

# gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, assertions on
TestCompiledAutomatonFloorSingle > testFloorOfSingleTermAutomaton FAILED
    java.lang.AssertionError: floor("x") of {"m"}: expected "m", got java.lang.NullPointerException: Cannot invoke "org.apache.lucene.util.automaton.ByteRunAutomaton.step(int, int)" because "this.runAutomaton" is null
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:63B807B3C458016A]:0)
        at org.apache.lucene.util.automaton.TestCompiledAutomatonFloorSingle.testFloorOfSingleTermAutomaton(TestCompiledAutomatonFloorSingle.java:31)

        Caused by:
        java.lang.NullPointerException: Cannot invoke "org.apache.lucene.util.automaton.ByteRunAutomaton.step(int, int)" because "this.runAutomaton" is null
            at org.apache.lucene.util.automaton.CompiledAutomaton.floor(CompiledAutomaton.java:411)
            at org.apache.lucene.util.automaton.TestCompiledAutomatonFloorSingle.testFloorOfSingleTermAutomaton(TestCompiledAutomatonFloorSingle.java:29)

# assertions off (-Ptests.asserts=false): the same message
# standalone runner, seed DEADBEEF: 1 of 1 failed, same message, on main (-ea and -da), 10.6.0, 10.5.2, 10.0.0, 9.12.3 (there at line 401)
# before 6.3.0 (4.0.0 to 6.2.1; release probes on 4.0.0-ALPHA to 5.5.5): the NPE names ByteRunAutomaton.getInitialState() instead; 6.6.6 and later name step(int, int)
# with the recommended fix: the test passes (assertions on and off)

• The contract is unconditional. "Finds largest term accepted by this Automaton, that's <= the provided input term. ... The returned result is either the provided output, or null if there is no floor term (ie, the provided input term is before the first term accepted by this Automaton)" (CompiledAutomaton.java:384-389). No type, no "NORMAL only".
• The default constructor produces the failing forms. It is documented as passing simplify=true (:106), so NONE, ALL and SINGLE are what a plain new CompiledAutomaton(a) gives for those languages.
• NFAs are accepted by the class. The class javadoc accepts non-deterministic automata (:36-40), and an NFA-backed instance has type NORMAL (:224).
• The NFA migration skipped floor. LUCENE-10010 / #225 (zhaih, 2021) added the NFA runner and moved AutomatonTermsEnum and the codecs' intersect enums to getByteRunnable() / getTransitionAccessor(); floor is not in its diff. visit() was missed too and moved only by #15961 (2026, main only), whose description says "some code paths (especially query visiting/highlighting and equality checks) still assumed a DFA-only representation". "floor" appears 0 times in the discussions of #225, #485, #11049 and #15961.
• Upstream fixed the same pattern as a bug. LUCENE-7576, CHANGES 6.4.0 "Bug Fixes": "Fix Terms.intersect in the default codec to detect when the incoming automaton is a special case and throw a clearer exception than NullPointerException" (lucene/CHANGES.txt:8691-8693). Michael McCandless wrote there: "This is unfortunately a confusing expert API; other terms dicts were checking that the provided compiled automaton is NORMAL and throwing a clearer exception if not, so I carried that same check over ... I also added a note to the javadocs for Terms.intersect." floor got neither the check nor the note.
• Nothing pins the current behaviour. No test, javadoc, CHANGES or MIGRATE entry says floor should throw for these forms.

The strongest case for "intended" (a devil's-advocate verifier, the cross-model reviews, a tie-break): the runAutomaton and automaton fields are documented "only valid for NORMAL" (:69-80); the only in-tree caller and the only test use simplify=false DFAs; the class is @lucene.experimental; MIGRATE.md for 10.0 says "It is the responsibility of the caller to call Operations.determinize() for DFA execution" (lucene/MIGRATE.md:922-926); and floor takes a BytesRefBuilder, which is @lucene.internal.

Why it fails: the "only valid for NORMAL" notes are on fields, not on floor, and an NFA-backed instance is NORMAL. @lucene.experimental means the API may change between releases, not that a public method may throw an undocumented NPE on legal input; LUCENE-7576 treated exactly that as a bug in an equally expert API. The MIGRATE note covers the NFA form at most: the minimal repro (makeString("m")) is already a DFA and fails in every release since 4.0.0. BytesRefBuilder is also a required parameter of public non-internal core APIs, for example Term(String, BytesRefBuilder) (Term.java:63).

Two fixes were built and run through gradle in a scratch worktree of 645d4fe14a20; the recommended one gives the javadoc result for all four forms in every executed case except an NFA with a dead state (see its trade-offs). A third option, documenting and rejecting these forms as Terms.intersect does, was not built.

At the top of floor, answer the three special forms directly; for NORMAL, read the DFA-or-NFA accessors that AutomatonTermsEnum uses (since #225) and visit() uses (since #15961) instead of the runAutomaton and automaton fields, also inside addTail. The rest of the diff renames the field uses to the two locals. Condensed:

switch (type) {
  case NONE: return null;
  case ALL: output.copyBytes(input); return output.get();
  case SINGLE:
    if (term.compareTo(input) <= 0) { output.copyBytes(term); return output.get(); }
    return null;
  case NORMAL: break;
}
// NORMAL: a DFA or an NFA; the rest of floor and addTail use these instead of the fields
final ByteRunnable runnable = getByteRunnable();
final TransitionAccessor accessor = getTransitionAccessor();

Trade-offs

• ALL returns the input. Exact for a binary ALL and for valid UTF-8 input. For a unicode ALL and input its UTF-8 form does not accept (for example the byte ff), it returns the input anyway (executed: input [ff] gives [ff]). For such input no largest accepted term exists: any accepted term below it can be extended, for example by a NUL character, and still stays below it. So any answer is a convention a reviewer may want documented. CompiledAutomaton does not keep isBinary, so floor cannot tell the two ALLs apart.
• NFA path: correct only without dead states. It walks the lazily determinized states of NFARunAutomaton, as AutomatonTermsEnum does, and like the DFA path it assumes every state can still reach an accept state. The class javadoc requires that of DFAs only ("must not have dead states"). An independent reviewer from another model family (OpenAI GPT-5.6) gave a counterexample, which we then ran: the NFA for {"b"} with 0 -[a-b]-> 1 (not accepting, no outgoing transitions) and 0 -b-> 2 (accepting). With the fix, floor("ab") returns "a" (not in the language) with assertions off and throws AssertionError with them on, where null is right; a second NFA with a dead state, {"b", "bc"}, fails the same way. That matches what 9.12.3 returns for the same NFAs (its constructor determinizes and keeps the dead state) and what main returns today for the same language built as a DFA with a dead state and simplify=false. After Operations.removeDeadStates the second NFA is still NFA-backed and the fix gives the right floor for every input tried. So the fix should come with one of: extending the class javadoc's no-dead-states rule to NFAs (the caller then trims, as for DFAs today), or removing dead states in the constructor's NFA branch (not built). Lucene's own caller keeps the unchanged DFA path.
• Shared scratch field. Like the stock code, the fix uses the per-instance transition field in floor and addTail, although the class javadoc calls the class immutable. It changes nothing about concurrent floor calls on one instance.
• Cost. One switch per call; no hot path calls floor on these forms.
• Not covered. The separate non-termination of floor on some infinite languages (another bug in the same method) is unchanged.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, OpenJDK 25.0.3, seed DEADBEEF (2026-10-31). Stock: the repro fails. With the fix: it passes with assertions on and off.
• The repro, the finder's five-form probe (SINGLE "m", NONE null, ALL "x", NFA "ac", DFA reference) and the suites org.apache.lucene.util.automaton.*, TestFuzzy*, TestAutomatonQuery*, TestRegexp*, TestWildcard*, TestPrefix* and index.TestTermsEnum*: 32 suites, 321 tests, 3 skipped, 0 failures.
• A differential check (not the repro): 5 iterations of 500 random finite languages (unions of up to 4 short strings through the one-argument constructor, so NONE, SINGLE, NFA-backed and DFA NORMAL) with 20 random inputs each, against a brute-force floor over the sorted terms: 0 failures; on stock code it fails with the NPE. Its NFAs are unions of strings, which have no dead states, so it does not cover the dead-state case above.
• :lucene:core:test over org.apache.lucene.search.* and org.apache.lucene.util.automaton.*: 230 suites, 2,578 tests, 51 skipped, 0 failures.
• checkGoogleJavaFormat, ecjLintMain, ecjLintTest (with the repro test in place), forbiddenApisMain, forbiddenApisTest: pass.

The same switch for NONE, ALL and SINGLE, and throw new UnsupportedOperationException("floor requires a deterministic automaton") when NORMAL has no runAutomaton (+18 lines). This is the study's first sketch.

Trade-offs

Smaller, but the NFA form still gets no result, so the 9.x-to-10.0 regression stays and the restriction needs a javadoc note. ALL has the same convention as above.

What the checks validated

The repro passes with assertions on and off (standalone runner and gradle). Through gradle with util.automaton.* and TestFuzzy*, the only 2 failures are the five-form probe's NFA case and the differential check, both hitting the deliberate exception.

Add "only works for NORMAL deterministic automata" to the floor javadoc and throw IllegalArgumentException (or IllegalStateException) for the other forms.

Trade-offs

The smallest behaviour change and an existing precedent, but callers must then special-case three common forms themselves, and the regression test becomes an expectThrows.

Method: non-formal (code reading plus a probe, then public-API JUnit tests); no formal tool produced the signal.

• The hunt unit's plan listed public methods in core and queries that no registry row, upstream issue or earlier study had named, with the function their javadoc states. For CompiledAutomaton.floor, reading the constructor showed four forms with a null runAutomaton and floor showed no dispatch on the type.
• A probe confirmed it, and the finder reduced it to a JUnit with five tests on the public API: SINGLE, NONE, ALL, the NFA from RegExp("(a|ab)c"), and a reference that compiles the same NFA language as a determinized DFA (which returns "ac").
• An independent reproducer, a devil's-advocate verifier, cross-model reviews (OpenAI GPT-5.6, reading only) and an adjudication checked it; the repro was then minimized to the single SINGLE test, re-checked on main 645d4fe14a20, and a tie-break re-ran it with an independent probe outside the package.