CompiledAutomaton.floor never returns on some infinite languages and grows its output until the heap or the array-size limit runs out

CompiledAutomaton.floor(input, output) promises the largest accepted term that is <= the input, or null when there is no floor term. On an infinite language whose accepted terms below the input have no largest element, it never returns. The smallest example is a stock query: new PrefixQuery(new Term("f", "b")).getCompiled().floor(new BytesRef("c"), new BytesRefBuilder()). Every term starting with b is accepted and sorts below c, and each one is beaten by a longer one, so there is no floor term. floor hands the case to addTail, whose push-down loop follows the largest transition until it reaches a state with no outgoing transitions; here that is the accept state's 0x00-0xff self-loop, so it appends 0xff forever and the output grows until OutOfMemoryError (or, with a heap that can hold a ~2 GiB array, IllegalArgumentException from ArrayUtil.oversize). On these DFA-backed automata, whenever floor returns, its answer is correct. Lucene's only caller, FuzzyTermsEnum, passes finite Levenshtein automata, and no query parser or search path reaches the method, so only code that calls the experimental floor() itself is exposed. The loop dates from LUCENE-3030 (2011): all 16 releases run, from 4.0.0-ALPHA to 10.6.0, and main fail. A step counter that returns null once the walk has taken more steps than the automaton has states (so it is on a cycle) fixes it.

• floor (CompiledAutomaton.java:390-480) walks the input. When the walk fails, it pops back to a state with a transition below the current label and calls return addTail(state, output, idx, label); (:470).
• addTail (:277-339) appends the largest label below the lead label (:283-311), then pushes down to the branch's largest term: "Push down to last accept state" (:316-338). It returns only at a state with zero transitions (:319); otherwise it takes the last (max) transition (:329), grows the output (:330), appends transition.max (:334) and moves on (:335). Nothing bounds the walk, and the public finite field (:97-101) is never read.
• For PrefixQuery("b") (PrefixQuery.java:44-58; the self-loop is :53-54) and input "c": no transition for c in state 0, so addTail appends b, moves to state 1, and the loop takes state 1's only transition, the self-loop, appending 0xff forever.

With no dead states (the class's stated requirement for a DFA), the max-label walk either reaches a leaf, and the result is the branch's largest term, or enters a cycle. In a cycle every term of the branch is beaten by a longer one, and every other candidate is smaller, so no floor term exists at all. An executed check over 400 random regexps and 84 inputs each (33,600 calls) found 7,884 diverging calls, exactly the 7,884 calls for which a bounded oracle finds no floor, and 0 wrong answers. The same happens for WildcardQuery("b*") with c (its automaton is converted from UTF-32 to UTF-8, so it appends U+10FFFF's 4-byte UTF-8 form f4 8f bf bf again and again) and RegexpQuery("c*") with d (it appends c); both compile to DFA-backed instances. The bug needs that shape: since 10.0.0 a non-deterministic input is kept as an NFA (CompiledAutomaton.java:253-257), and there floor throws NullPointerException before it reaches addTail (LFV-891, a separate bug).

• Who is exposed. Application code that calls floor() on a DFA-backed NORMAL instance of an infinite language: the getCompiled() automaton (10.0.0 and later) of a PrefixQuery with a non-empty prefix, or of a WildcardQuery or RegexpQuery whose pattern compiles to a DFA (a non-deterministic pattern is NFA-backed and gets LFV-891's NullPointerException instead), or new CompiledAutomaton(...) of an infinite DFA without dead states (all versions), with an input whose lower set of accepted terms has no maximum.
• Not reached by Lucene. The only in-tree caller, FuzzyTermsEnum.java:185, passes Levenshtein automata built with finite=true (FuzzyAutomatonBuilder.java:63,73); no query, codec or Terms.intersect path calls floor. A read-only GitHub code search found no downstream caller on an infinite automaton.
• Effect. A few seconds of allocation, then OutOfMemoryError (3.2 s at a 512 MB heap, about 13 s at 2 GB), which can hit unrelated work in the same JVM; with a 6 GB heap a ~2 GiB buffer and then IllegalArgumentException after 26.5 s. No wrong answers on these automata, no index involved.
• Scale. A one-letter prefix and a one-byte input. The study's 23% divergence rate is for its synthetic sample (regexps over {a,b,c}, inputs over {a,b,c,d} of length 1-3), not a real-world rate.
• Likelihood plausible, priority low: an opt-in direct call to an @lucene.experimental class; no public report was found, although the code is 15 years old.

Copy the file into lucene/core/src/test/org/apache/lucene/util/automaton/ of a Lucene checkout and run the command. It needs 10.0.0 or later (AutomatonQuery.getCompiled()); older releases fail the same way through a hand-built automaton and the public CompiledAutomaton constructor.

Lucene's test JVMs run with -XX:+HeapDumpOnOutOfMemoryError, so a failing gradle run also writes a heap dump of about 200 MB (java_pid*.hprof) into lucene/core/build/tests-cwd/; delete it afterwards.

The same test with a standalone runner fails the same way, with the same frames addTail:330 <- floor:470: on main and 10.5.2 with assertions on and off (12.5-13.2 s at -Xmx2g; on main also 2.7 s at -Xmx256m, assertions off), on 10.6.0 with assertions on (18.8 s at -Xmx2g) and on 10.0.0 with assertions off (3.3 s at -Xmx256m). With -Xmx6g and assertions off it fails on main after 26.5 s with IllegalArgumentException: requested array size 2147483632 exceeds maximum array in java (2147483631) at ArrayUtil.oversize:146 <- ArrayUtil.grow:448 <- BytesRefBuilder.grow:60 <- addTail:330 <- floor:470.

Regression test: this same test, for the recommended null fix: with it the test passes in under 0.1 s. Because it only checks that the call returns, it can be tightened to assertNull(compiled.floor(new BytesRef("c"), new BytesRefBuilder())), which also checks the value. For the exception option the matching test is expectThrows(IllegalArgumentException.class, () -> compiled.floor(new BytesRef("c"), new BytesRefBuilder())).

cp $REPRO/TestCompiledAutomatonFloorPrefix.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/automaton/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.automaton.TestCompiledAutomatonFloorPrefix -Ptests.seed=DEADBEEF
# assertions off fails the same way: -Ptests.asserts=false; a failing run leaves a ~200 MB java_pid*.hprof in lucene/core/build/tests-cwd/

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on, 512 MB test heap (test 3.18 s)
java.lang.OutOfMemoryError: Java heap space
Dumping heap to java_pid18556.hprof ...
Heap dump file created [200496935 bytes in 0.308 secs]

TestCompiledAutomatonFloorPrefix > testFloorReturnsOnPrefixAutomaton FAILED
    java.lang.AssertionError: expected floor("c") on PrefixQuery("b") to return null or a term, but it kept appending bytes until java.lang.OutOfMemoryError: Java heap space
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:65344359139D9DA4]:0)
        at org.apache.lucene.util.automaton.TestCompiledAutomatonFloorPrefix.testFloorReturnsOnPrefixAutomaton(TestCompiledAutomatonFloorPrefix.java:32)

        Caused by:
        java.lang.OutOfMemoryError: Java heap space
            at org.apache.lucene.util.ArrayUtil.growExact(ArrayUtil.java:436)
            at org.apache.lucene.util.ArrayUtil.grow(ArrayUtil.java:448)
            at org.apache.lucene.util.BytesRefBuilder.grow(BytesRefBuilder.java:60)
            at org.apache.lucene.util.automaton.CompiledAutomaton.addTail(CompiledAutomaton.java:330)
            at org.apache.lucene.util.automaton.CompiledAutomaton.floor(CompiledAutomaton.java:470)
            at org.apache.lucene.util.automaton.TestCompiledAutomatonFloorPrefix.testFloorReturnsOnPrefixAutomaton(TestCompiledAutomatonFloorPrefix.java:30)

1 test completed, 1 failed
BUILD FAILED in 1m 7s

• Contract (CompiledAutomaton.java:384-389): "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)." No finite-language precondition and no exception; the parenthetical spells out only the before-the-first-term case and does not address a lower set with no maximum, so null is the natural reading, and a documented exception would also be defensible (the second fix option).
• Infinite automata are accepted. The class javadoc's only DFA requirement is "must not have dead states" (:36-43). Both constructors say "Set finite to true if the automaton is finite, otherwise set to false if infinite or you don't know" (:137-141, :146-150), and every AutomatonQuery compiles with finite=false (AutomatonQuery.java:99). On #11813 (merged 2022), rmuir wrote "PrefixQuery is always infinite" and "If you dont know that your automaton is finite, pass false to CompiledAutomaton, it is safe." floor ignores the flag.
• It works on infinite automata except in the no-maximum case: on the same PrefixQuery("b") automaton it returns b for "b" and bb for "bb", and null for "" and "a", where no accepted term is <= the input. The loop's own comment, "Push down to last accept state" (:316), assumes the walk ends at a leaf.
• Lucene's convention for finite-only code: FiniteStringsIterator documents that cycles may cause an IllegalArgumentException ("but this is not guaranteed!", FiniteStringsIterator.java:28-29) and throws "automaton has cycles" (:119-120); Operations.topoSortStates "detects cycles, it will never attempt to use infinite RAM" (Operations.java:1347-1360).
• Never tested on infinite languages: TestCompiledAutomaton builds its floor fixtures only with Automata.makeStringUnion and finite=true (TestCompiledAutomaton.java:44-45). No test, comment, CHANGES entry, issue or PR says infinite languages are unsupported.
• Project stance: SECURITY.md:46 says "Issues that fall outside the scope above are still valid bug reports and hardening suggestions." Its example, "a change that prevents an endless loop or replaces a low-level failure with a clean CorruptIndexException on a broken index is welcome, provided it does not negatively impact performance", is about broken indexes, and it adds that robustness improvements "must not slow down the hot paths"; the fix's cost is one compare per appended byte.

The strongest case for "intended" (the cross-model refute review and the tie-break): the javadoc's parenthetical defines null as "the input is before the first accepted term", so the author assumed a floor exists otherwise, which holds only for finite languages; the only caller and every test use finite automata; the class is @lucene.experimental; and the largest term does not mathematically exist, so there is no answer to give.

Why it fails: an unwritten assumption is not a contract, and the constructors invite infinite automata. "No largest term" is what "no floor term" means, and the javadoc's only answer for it is null; even under the narrowest reading, an unanswerable input calls for a documented restriction or a clean exception, as Lucene's own finite-only algorithms do, not unbounded allocation. @lucene.experimental is about API stability, not permission to hang. The reviewer agreed with the root cause and the legality of the inputs, rated the intended-behaviour argument weak, and gave not real only because it could not run code. Verdict: a defect.

One fix was built and validated through gradle in a scratch worktree of 645d4fe14a20. The other options are sketches, not built.

Add a step counter to the push-down loop of addTail (+9/-1 in CompiledAutomaton.java: 7 lines in the loop and 2 javadoc lines added, 1 javadoc line removed). It does not track visited states; it counts the walk's transitions and returns null once there are more than the automaton has states. A walk that long must have revisited a state, and because it always takes the last transition, a revisit means a cycle: the branch has no largest term and every other candidate is smaller, so there is no floor term. The floor javadoc's null case gains "or, for an infinite language, the accepted terms before it have no largest element".

// Push down to last accept state
int steps = 0;
while (true) {
  numTransitions = automaton.getNumTransitions(state);
  if (numTransitions == 0) {
    ...   // unchanged: return the term
  } else {
    if (++steps > automaton.getNumStates()) {
      // the max-label walk is on a cycle: no floor term
      return null;
    }
    ...   // unchanged: append transition.max and move on
  }
}

Trade-offs

• Changes only calls that never returned; every call that returns today returns the same answer. Before it returns null it writes about the input length + 1 + the number of states bytes (plus the builder's usual over-allocation).
• Cost: one increment and compare per appended byte. Lucene calls floor only when FuzzyTermsEnum drops to a smaller edit distance, and its finite automata never take the new branch.
• A caller cannot tell this null from "input before the first term"; option B keeps them apart. On the null path output has been grown and written to without its length being set; harmless for FuzzyTermsEnum, which passes a fresh builder and uses only the return value, but worth a line in the review.
• Relies on the documented no-dead-states requirement, which CompiledAutomaton does not enforce: on an automaton that breaks it, a walk into a dead cycle would return null where today it loops. Such automata already break floor in another way (a walk ending in a non-accepting leaf fails the assert at :321 with -ea and returns a non-accepted term with -da, read); the fix does not change that.
• Touches the same method as open PR #16361 (a binary search for the first scan of addTail), but the two diffs do not overlap and apply cleanly in either order.

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle, OpenJDK 25.0.3, seed DEADBEEF. Stock: the repro fails with the OutOfMemoryError above.
• With the fix: org.apache.lucene.util.automaton.* and TestFuzzyQuery, 17 classes, 252 tests, 0 failures, 2 skipped, with assertions on and off; the repro passes in 0.082 s, TestCompiledAutomaton 14/14, TestFuzzyQuery 13/13.
• checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest of :lucene:core pass with the fix and the repro in place.
• With the same logic, the no-floor cases PrefixQuery("b")/c, WildcardQuery("b*")/c and RegexpQuery("c*")/d return, and answers where a floor exists are unchanged (tie-break). The independent fact check called them on the fixed build directly: all three return null, and the five controls give the same answers as stock.

The same step counter, but throw new IllegalArgumentException(...) instead of return null, as FiniteStringsIterator and Operations.topoSortStates do for cycles.

Trade-offs

Keeps null for "before the first term" only, so callers can tell the cases apart; but it adds an exception, and a @throws, for a case the javadoc already maps to null. Judged an equally valid upstream choice by the tie-break. With it, the regression test must become expectThrows(IllegalArgumentException.class, ...).

Check the public finite flag at the start of floor.

Trade-offs

Too broad: it rejects calls that work today on infinite automata where a floor exists (for example PrefixQuery("b") with bb), and every AutomatonQuery compiles with finite=false, even for finite patterns.

Document the limitation and leave the loop.

Trade-offs

Anyone who misses the note still allocates until OutOfMemoryError.

Method: Jazzer fuzzing with an exact-set oracle (the study's non-formal baseline tier, 2026-10-22). The AutomatonMiscFuzzer harness checked several automaton utilities against exact set oracles, CompiledAutomaton.floor among them; the first seed of its replay driver did not return.

• A separate verifier read only the triggering sequence and wrote its own tests: a hand-built two-state byte DFA for b a* and RegExp("ba*") with input "bb" (out of memory at -Xmx256m in about 1.5 s; IllegalArgumentException at -Xmx6g after 22-25 s), with four controls that pass.
• Its characterization compared 33,600 floor calls (400 random regexps x 84 inputs) with a bounded-length oracle: 7,884 diverged, exactly the no-floor cases, and 0 answers were wrong; 15,000 calls on Levenshtein automata, the shape FuzzyQuery uses, never diverged.
• The hunt then cut the repro down to one stock-query test (PrefixQuery("b"), "c"), re-ran it on current main and releases, ran a cross-model review and a second adjudication, and validated a fix.