Automaton.Builder.addEpsilon(s, s) never returns and exhausts the heap once state s has a transition

Automaton.Builder.addEpsilon(source, dest) documents: "Add a [virtual] epsilon transition between source and dest. Dest state must already have all transitions added because this method simply copies those same transitions over to source." (Automaton.java:805-808 at 5adff78bb168). It scans the builder's transition list and appends a copy of every transition that leaves dest (:809-815), but its loop bound upto < nextTransition (:810) is re-read on every pass while each append advances nextTransition (:795-803). With source == dest every appended copy again leaves dest, the scan reaches it and appends another, and the loop never ends: a one-state builder with the arc s -a-> s and a call addEpsilon(s, s) ends in OutOfMemoryError: Java heap space with a 512 MB heap, assertions on and off. Read as documented, an epsilon from a state to itself changes nothing, and the sibling Automaton.addEpsilon, whose javadoc is word for word the same, returns on the same call on the state being built because it reads its count once (:185-199). No Lucene caller passes source == dest; application code that builds its own automata with the experimental Builder does, for example a hand-written Kleene star when the start state accepts. The loop has been there since the method was added in 2014 (LUCENE-5963); releases 4.10.3 through 10.6.0 and main are affected (every inspected release tag from 4.10.3 on carries the loop line, and 12 releases were executed). Reading the bound once fixes it.

1. addEpsilon(source, dest) loops for (int upto = 0; upto < nextTransition; upto += 4) (Automaton.java:810, the fix site). For each record with transitions[upto] == dest (:811) it calls addTransition(source, dest', min, max) (:812-813), which grows the array if needed (ArrayUtil.grow, :796-797), writes the record and advances nextTransition by 4 (:799-802).
2. The bound is read again on every pass. With source == dest, each appended record starts at dest again, so the scan reaches it and appends another one.
3. With one record (0, 0, 'a', 'a'): at upto = 0 the record matches and a copy goes to index 4 (nextTransition 4 -> 8); at upto = 4 the copy matches and another goes to index 8 (8 -> 12); and so on. The scan stays one record behind the end forever. The first growth of the default 64-int array happens at the 16th copy (64 -> 76 ints); after 1,000,000 copies nextTransition is 4,000,004 and the array has grown 91 times.
4. ArrayUtil.grow keeps enlarging the array until OutOfMemoryError: Java heap space (ArrayUtil.java:319). By reading, only a heap that holds an int[] of ArrayUtil.MAX_ARRAY_LENGTH (about 8 GiB) and, during that last copy, the previous array too (about 15 GiB or more in total) would get as far as ArrayUtil.oversize's IllegalArgumentException (ArrayUtil.java:145-151); that was not run.

The arc does not have to be a self-loop: any arc that leaves s does it (an independent test with s0 -x-> s1 and addEpsilon(s0, s0) fails the same way). A state without arcs is fine: addEpsilon(s, s) then makes no copy and returns. With source != dest the copies start at source, never match dest, and the loop ends at the old end of the list.

• Who. Direct users of Automaton.Builder; the Automaton class is @lucene.experimental (Automaton.java:43). One natural way to get there: a Kleene star written as "copy a, then addEpsilon(f, start) for every accept state f". When a's start state also accepts, one of those calls is addEpsilon(start, start). A counting probe shows it: the star of "b" returns after 1 copy; the star of "b?", whose start state accepts, hits the 1,000,000-copy cap.
• Effect. The call never returns and allocates until the JVM throws OutOfMemoryError: Java heap space, which can also hit other threads of the same JVM. No wrong automaton is ever returned. No scale is needed: one state and one arc.
• Not affected. The only non-test callers of Builder.addEpsilon never pass source == dest: Operations.repeat(a, min, max) links earlier accept states to the start of a freshly copied a (Operations.java:313-319), and AnalyzingSuggester.replaceSep walks an acyclic token automaton in topological order (AnalyzingSuggester.java:271-302). ConcatenateGraphFilter and the other Operations and Automata sites use the non-Builder Automaton.addEpsilon. Lucene's own Kleene star, Operations.repeat(a), avoids the shape: it returns early when state 0 is the only accept state (Operations.java:207-209) and skips states merged into the start (if (stateMap[s] != 0), :255).
• Likelihood: rare. No matching public report was found in the recorded searches, but whoever makes the call hangs every time.

TestBuilderAddEpsilonToItself (one method, extends LuceneTestCase, package org.apache.lucene.util.automaton of the lucene/core tests). With the license header, addEpsilon is at line 29. The test needs no heap flag: gradle's test JVMs use tests.heapsize, 512 MB by default, so the call fails fast instead of hanging.

As the regression test, the same method fits in TestAutomaton.

cp $REPRO/TestBuilderAddEpsilonToItself.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/automaton/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.automaton.TestBuilderAddEpsilonToItself -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: the same failure

TestBuilderAddEpsilonToItself > testEpsilonFromStateToItself FAILED
    java.lang.OutOfMemoryError: Java heap space
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:453316C862A39282]:0)
        at org.apache.lucene.util.ArrayUtil.growExact(ArrayUtil.java:319)
        at org.apache.lucene.util.ArrayUtil.growInRange(ArrayUtil.java:345)
        at org.apache.lucene.util.ArrayUtil.grow(ArrayUtil.java:377)
        at org.apache.lucene.util.automaton.Automaton$Builder.addTransition(Automaton.java:797)
        at org.apache.lucene.util.automaton.Automaton$Builder.addEpsilon(Automaton.java:812)
        at org.apache.lucene.util.automaton.TestBuilderAddEpsilonToItself.testEpsilonFromStateToItself(TestBuilderAddEpsilonToItself.java:29)

(gradle on main 5adff78bb168, seed DEADBEEF, assertions on, 1.15 s; with -Ptests.asserts=false the same error and stack, 1.17 s)

• Contract. Builder.addEpsilon: "Add a [virtual] epsilon transition between source and dest. Dest state must already have all transitions added because this method simply copies those same transitions over to source." (Automaton.java:805-808). The precondition holds for source == dest. Nothing in the javadoc, package docs, tests, CHANGES.txt, MIGRATE.md or the commit history excludes the case. Nor does anything promise that a self call is supported: the case rests on the natural reading of the documented copy, which is well defined and finite for source == dest.
• The class is meant for this kind of construction. The Builder javadoc: "Use this when you cannot create the Automaton directly because it's too restrictive to have to add all transitions leaving each state at once." (:761-765).
• The sibling handles it. Automaton.addEpsilon (:185-199) has the same javadoc but reads its count once (int count = initTransition(dest, t);, :191). A self call there returns on the state being built, or throws a clean IllegalStateException ("from state (0) already had transitions added") once the state is finished.
• History. The method came with LUCENE-5963 (#7025, 2014), written for one caller, AnalyzingSuggester.replaceSep, where source and dest always differ. The only later change is the 2020 reformat. The issue thread never discusses a self epsilon or the loop bound, and no upstream test calls Builder.addEpsilon at all (the test callers, TestOperations.java:608 and the test framework's AutomatonTestUtil.java:391, use Automaton.addEpsilon).

The strongest case for "intended". Automaton is @lucene.experimental; Builder.addEpsilon is a minimal helper added for one caller; an epsilon from a state to itself is pointless; a copy into itself is the classic aliasing case other APIs leave undefined (java.util.List.addAll leaves the behaviour undefined if the argument is modified during the call, which it notes happens when the argument is this list and it is nonempty); "Dest state must already have all transitions added" can be read as "no arcs are added to dest afterwards", which the self call itself breaks; and the failure is loud.

Why it fails. @lucene.experimental marks API instability, not permission to hang. Unlike List.addAll, this javadoc states no aliasing exclusion, and its documented effect (copy dest's arcs to source) is well defined and finite for source == dest. The precondition is about dest's arcs before the copy, and they are all there. The sibling with the same contract handles the call. And the call arises in ordinary NFA code, such as a Kleene star whose start state accepts, with one state and one arc. That is a fair argument for Low priority and for accepting a documentation-only fix (option C), not evidence that the hang is intended. The independent reproducer, the cross-model review lenses (OpenAI GPT-5.6, "intended argument weak"), the devil's-advocate verifier and the adjudication all rejected it.

Fix A was built and checked through gradle in a scratch worktree at 5adff78bb168; B and C were not run. A maintainer may prefer B (an exact early return, no duplicate arc) or C (a javadoc line); A matches the sibling method and is a small change (one local for the bound, and the loop condition). The fix applies to the 10.x source unchanged: the loop line is identical in all 101 release tags of the history clone from 4.10.3 on.

In Automaton.Builder.addEpsilon (Automaton.java:809-819), snapshot nextTransition before the loop and loop to the snapshot.

    public void addEpsilon(int source, int dest) {
      // read the bound once: with source == dest the copies appended below also leave dest
      final int end = nextTransition;
      for (int upto = 0; upto < end; upto += 4) {
        if (transitions[upto] == dest) {
          addTransition(
              source, transitions[upto + 1], transitions[upto + 2], transitions[upto + 3]);
        }
      }
      if (isAccept(dest)) {
        setAccept(source, true);
      }
    }

Trade-offs

A changed loop condition plus one local (and a comment). For source != dest the old loop already stopped at the same place, since records appended there never match dest. For source == dest it appends one duplicate of each arc of dest; finish() merges it, because finishCurrentState combines transitions with the same dest and overlapping labels (Automaton.java:247-295); with the fix the probe's finished state has 1 transition and accepts "aaa". So A is not a pure no-op inside the builder: until finish(), a self call on a state with k arcs holds k extra records, which finish() sorts and merges.

What the checks validated

• Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on, and -Ptests.asserts=false: OutOfMemoryError) and passes with it (0.27 s and 0.26 s).
• With the fix: core's whole org.apache.lucene.util.automaton test package, 16 classes incl. the repro (TestAutomaton 85, TestRegExpParsing 63, TestOperations 23, which covers repeat(a, min, max), ...): 239 tests, 0 failures, 2 skipped; suggest's org.apache.lucene.search.suggest.analyzing package (TestAnalyzingSuggester 23, TestFuzzySuggester 14, ..., which exercise replaceSep): 89 tests, 0 failures, 1 skipped. checkGoogleJavaFormat on core passes. The full core suite was not run; only OpenJDK 25.0.3 on Linux aarch64 was used.
• Earlier: the hunt's shadow-class runs of the same change pass the repro (assertions on and off), the other verifiers' own tests and 112 tests of TestAutomaton, TestOperations, TestMinimize and TestDeterminism; with the bound read once, the 4.10.3 source passes too.

Add if (source == dest) return; at the top of Builder.addEpsilon.

Trade-offs

Exact for the resulting automaton: an epsilon from a state to itself changes neither the arcs nor the accept bit, and no duplicate arc is added. It covers only the self case, which is the only case the re-read bound can break, and leaves the loop as it is. One observable difference: Builder is not final and addTransition is public (Automaton.java:766, :795), so a subclass that overrides addTransition sees no call for a self epsilon under B, while A keeps one call per original arc, as documented. Not run.

Add "source and dest must be different states" to the javadoc, optionally with an IllegalArgumentException.

Trade-offs

Cheapest, but keeps a hang (or turns it into an exception) for a call whose documented effect is well defined and which the sibling method handles. Not run.

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

• The finder checked Builder.addEpsilon against its javadoc for every pair of states that meets its one precondition. Termination needs the loop bound to be fixed, but addTransition advances it, and for source == dest every appended record matches again.
• The finder then wrote a public-API JUnit test, a probe that counts addTransition calls, and the bound-once fix that makes both pass.
• An independent reproducer, an executed cross-model review with a refute and an intended-behaviour lens, a devil's-advocate verifier and an adjudication reproduced it with their own tests ("Prior reports, history and checks").