Operations.topoSortStates misses self-loop cycles and returns an order instead of throwing

Operations.topoSortStates(Automaton) documents that it "will throw an IllegalArgumentException if a cycle is detected". Its iterative depth-first search marks a state as on-stack only when that state pushes a child (it marks the parent, not the pushed child; the two coincide only when a loop 0 -> 0 pushes state 0 again), and pushes state 0 without any mark. A reachable non-initial state whose only remaining edge is a loop to itself therefore scans that loop while unmarked, sees "visited, not on stack", and is emitted. For the 2-state automaton 0 -a-> 1 (accept), 1 -b-> 1 (the language ab*) the method returns [0, 1]; determinized RegExp("ab*") and RegExp("a+") return [0, 1, 2]. Cycles of two or more states and a loop on state 0 are still caught. The gap dates from #12286 (9.7.0), which added the check on purpose, and is in every release up to 10.6.0 and main. Lucene's own callers (ConcatenateGraphFilter, AnalyzingSuggester) pass acyclic token graphs, so only direct callers that rely on the exception are affected. The fix is the textbook marking: mark a state when it is pushed.

  private static int topoSortStates(Automaton a, int[] states) {
    BitSet onStack = new BitSet(a.getNumStates());
    BitSet visited = new BitSet(a.getNumStates());
    var stack = new ArrayDeque<Integer>();
    stack.push(0); // Assuming that the initial state is 0.
    int upto = 0;
    Transition t = new Transition();

    while (!stack.isEmpty()) {
      int state = stack.peek(); // Just peek, don't remove the state yet

      int count = a.initTransition(state, t);
      boolean pushed = false;
      for (int i = 0; i < count; i++) {
        a.getNextTransition(t);
        if (!visited.get(t.dest)) {
          visited.set(t.dest);
          stack.push(t.dest); // Push the next unvisited state onto the stack
          onStack.set(state);
          pushed = true;
          break; // Exit the loop, we'll continue from here in the next iteration
        } else if (onStack.get(t.dest)) {
          // If the state is on the current recursion stack, we have detected a cycle
          throw new IllegalArgumentException("Input automaton has a cycle.");
        }
      }

      // If we haven't pushed any new state onto the stack, we're done with this state
      if (!pushed) {
        onStack.clear(state); // remove the node from the current recursion stack
        stack.pop();
        states[upto] = state;
        upto++;
      }
    }
    return upto;
  }

The lines that matter (notes, not source comments):

• :1400 pushes state 0 without setting its visited or onStack bit.
• :1414 sets the bit of state, the parent on top of the stack, not of the pushed t.dest.
• :1417-1419 is the only cycle check: a visited successor whose onStack bit is set.
• :1424-1429 clear, pop and emit a state that pushed nothing in this pass; every peek rescans its edges from the first one (:1407).

The public method reverses the emitted [1, 0] (Operations.java:1378-1383) and returns [0, 1].

• Why longer cycles are caught. Every state below the top of the stack has pushed a child, so it is marked; a cycle of two or more states ends in an edge to such an ancestor.
• When a self-loop is missed. A state with a self-loop that also pushes an unvisited child is marked by that push, and its loop is caught when it rescans its edges after the child is done. The miss needs a non-initial state whose other successors are all visited already, or that has none. Transitions are scanned in (min, max, dest) order (Automaton.java:297-298), so the shape and the labels decide.
• Why a loop on state 0 is caught. State 0 is never marked visited, so an edge back to it (also 0 -> 0) pushes 0 a second time, and the second copy finds a marked state (the study verifier's argument; the exhaustive check agrees).
• What still holds. visited keeps any state but 0 from being pushed twice, so the method ends, and its stack holds at most the number of states plus one (state 0 can be pushed twice). Memory stays O(numStates), as the javadoc's RAM sentence says (Operations.java:1359-1360).

Re-run on main for this doc: of 121,584 cyclic cases (every graph with up to 4 states, in two scan orders), 2,906 are sorted instead of rejected; of 97,648 cyclic random graphs with 2 to 40 states, 13,713. Every miss has only self-loop cycles; 0 false alarms and 0 invalid orders on acyclic graphs. Regexp shapes: ab* and a+ (determinized, 3 states) return [0, 1, 2]; a* (loop on state 0), (ab)*c (cycle 0 -> 1 -> 0) and the cycle 1 -> 2 -> 1 throw.

The method sorts only the states reachable from state 0 (Operations.java:1348), so "cycle" here means a cycle reachable from state 0; neither the check nor the fixes look at unreachable states.

• Who. Code that calls Operations.topoSortStates (public; the class is @lucene.experimental) and relies on the documented exception to reject cyclic automata, for example before walking or enumerating the automaton's strings. It accepts ab* or a+ and gets an order back; what happens next depends on that code. Core has had no public Operations.isFinite since #11813 (2022); it now lives in the test framework (AutomatonTestUtil.isFinite).
• Not default, no in-tree path for conforming token streams. The only main-source callers, ConcatenateGraphFilter.replaceSep and AnalyzingSuggester.replaceSep, get TokenStreamToAutomaton output. Its edges run forward from a position to pos + positionLength, and both stock attribute implementations (PackedTokenAttributeImpl, the default, and PositionLengthAttributeImpl) reject positionLength < 1, so for token streams that follow that contract it is acyclic. TokenStreamToAutomaton does not re-check the value; a custom attribute implementation that skips the check was not examined.
• Effect. A missing exception. The returned array orders the states as if the self-loops were removed. No hang, no out-of-memory, no crash, no wrong search result inside Lucene. FiniteStringsIterator has its own cycle check.
• Scale. One call on a 2-state automaton; no index.

• API. Automaton.createState, setAccept, addTransition, finishState, Operations.topoSortStates and LuceneTestCase.expectThrows; the package is for locality only, no package-private member is used. Nothing random is used.
• Smallest input. Two states, the smallest automaton with a self-loop on a non-initial state; a self-loop on state 0 alone is caught.
• Releases. The same file fails unchanged on every release 9.7.0 to 10.6.0.
• Regression test. This same method, for example added to TestOperations.

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

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on
TestTopoSortSelfLoop > testSelfLoopIsACycle FAILED
    junit.framework.AssertionFailedError: Expected exception IllegalArgumentException but no exception was thrown
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:3FBC0C235F1821E]:0)
        at app//org.apache.lucene.tests.util.LuceneTestCaseParent.expectThrows(LuceneTestCaseParent.java:1432)
        at app//org.apache.lucene.tests.util.LuceneTestCaseParent.expectThrows(LuceneTestCaseParent.java:1418)
        at app//org.apache.lucene.util.automaton.TestTopoSortSelfLoop.testSelfLoopIsACycle(TestTopoSortSelfLoop.java:32)
...
1 test completed, 1 failed
# assertions off (-Ptests.asserts=false): the same AssertionFailedError
# with fix A or B, assertions on and off: ":lucene:core:test (SUCCESS): 1 test", BUILD SUCCESSFUL

• Contract. Operations.java:1348-1350: "This method assumes that the automaton does not contain cycles, and will throw an IllegalArgumentException if a cycle is detected." :1359-1360: "as this method detects cycles, it will never attempt to use infinite RAM." :1394: "@throws IllegalArgumentException if the input automaton has a cycle."
• History. Before #12286 the javadoc said "Behavior is undefined if this automaton has cycles". In the PR description the author asked "Perhaps we should check if the automaton contains cycles, and throw an IllegalArgumentException if it does?"; mikemccand answered "That would be nice, though it really is illegal usage of the API -- can you detect that w/o much added cost in the iterative solution?"; the author added "a BitSet to track whether the current state is already on the stack"; rmuir wrote "the cycle detection is a really nice bonus. thanks for the unit test for that."; and mikemccand's "Since we detect cycles we will never have an 'attempt to use infinite RAM'" became the javadoc of #12292.
• Test. TestOperations.testCycledAutomaton (TestOperations.java:80-85) expects the exception. Its random automaton's only back edge goes to the initial state (:295-297), which the code catches, so it cannot see this gap.

Strongest case for "not a bug": the same sentence begins "This method assumes that the automaton does not contain cycles", and its promise is worded "will throw ... if a cycle is detected", which can be read as best-effort detection; mikemccand called cyclic input "illegal usage of the API", so cyclic input breaks a precondition, the exception is best effort, and Operations is @lucene.experimental. A cross-model reviewer (OpenAI GPT-5.6, refute lens) built this argument and rated it moderate.

Why it fails: the helper's @throws has no such condition ("if the input automaton has a cycle"), #12286 replaced "undefined" with that promise and tested it, and #12292's javadoc relies on it; no comment, test or PR remark treats self-loops as acceptable. @lucene.experimental is about API stability, not correctness. The reviewer reproduced the miss with its own RegExp("ab+") input and judged it real with high confidence. The dispute is about how serious the gap is, not whether it happens; the precondition reading is why the impact stays low: no correct in-tree caller hits it.

For an acyclic input both code fixes return exactly the same array as today: the changed lines only decide when to throw, and marking state 0 visited only matters when an edge leads back to state 0, which is itself a cycle.

In the private helper: after stack.push(0) add visited.set(0) and onStack.set(0); when pushing an unvisited child, call onStack.set(t.dest) and drop onStack.set(state). A state is then marked from its push to its pop, so its own loop, like any back edge, finds it marked.

     stack.push(0); // Assuming that the initial state is 0.
+    visited.set(0);
+    onStack.set(0);
...
         if (!visited.get(t.dest)) {
           visited.set(t.dest);
+          onStack.set(t.dest);
           stack.push(t.dest); // Push the next unvisited state onto the stack
-          onStack.set(state);
           pushed = true;

Trade-offs

• +3/-1 lines, no extra work per transition; matches the standard DFS cycle check.
• A back edge to state 0 is now reported at once instead of after pushing state 0 a second time.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF: the minimal test fails before the change and passes after it, with assertions on and off (the mode is set on the command line).
• org.apache.lucene.util.automaton.* (16 classes, incl. TestOperations 23/23), TestConcatenateGraphFilter and its factory test, TestAnalyzingSuggester, TestFuzzySuggester and org.apache.lucene.search.suggest.document.*: 352 tests, 2 skipped, 0 failures.
• The study's characterization suite against the patched class: 0 misses, 0 false alarms, 0 invalid orders on 132,132 cases (every graph with up to 4 states, in two scan orders) and 200,000 random graphs (stock main: 2,906 and 13,713 misses). The suite's JVM still reports "Tests run: 9, Failures: 2" on the patched class, because two of its tests assert that the stock method misses cases; the counters are the result.
• The study's TLA+ model checked the same fix on all graphs with 3 states (every scan order) and 4 states (sorted order).
• Not run: the whole :lucene:core:test or check.

Change the check to else if (t.dest == state || onStack.get(t.dest)).

-        } else if (onStack.get(t.dest)) {
+        } else if (t.dest == state || onStack.get(t.dest)) {
           throw new IllegalArgumentException("Input automaton has a cycle.");

Trade-offs

• One condition, at the check itself.
• Keeps the unusual marking (the parent is marked; an edge back to state 0 still pushes 0 twice before the cycle is seen), so it is correct only through the argument that every longer cycle ends at an ancestor that already pushed.

What the checks validated

• Gradle, seed DEADBEEF: org.apache.lucene.util.automaton.*, 239 tests, 2 skipped, 0 failures (incl. the minimal test and TestOperations); the minimal test alone passes with assertions on and off (in a separate re-run).
• The study's characterization suite against the patched class: 0 misses, 0 false alarms, 0 invalid orders on the same graphs (its JVM again reports 2 failures, for the same reason as under A).

Say that self-loops may go undetected.

Trade-offs

• No code change, but it takes back a promise #12286 made on purpose and leaves callers without a reliable check. Not run.

• Method. The study's automaton experiment compared Lucene's real topoSortStates with an exact reference over every automaton with 3 states on the letters a and b (2,097,152 automata): 14,616 were sorted instead of rejected.
• Model. A TLA+ model of the iterative search, with the graph and every successor order chosen freely, and the invariants "no missed cycle", "no false cycle" and "the output is a reverse topological order of exactly the reachable states". TLC found a counterexample trace of 5 TLC states (the initial state and 4 search steps) for 0 -> 1, 1 -> 1 in 2 s; with the fix, no error on all graphs with 3 states in every order and with 4 states in sorted order.
• Verifier. An independent verifier wrote its own 9 tests (the minimal case, ab*, a+, a self-loop with a visited sibling, 3 controls, and an exhaustive and a random characterization against Kahn's algorithm, a different sorting method): 4 contract failures, 5 passes, every miss self-loop-only.