oracle/graal · warning · UnsupportedRegexException

dependency cycle

Error message

dependency cycle

What it means

Thrown by DFAGenerator during capture-group transition-op scheduling. For each transition it must emit the position-updating operations in an order where no operation overwrites a value another operation still needs (a topological sort of the ops list); when scheduleOpsFindCandidate returns -1 for every remaining op, the operations are mutually dependent and cannot be scheduled, so compilation aborts with UnsupportedRegexException('dependency cycle').

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java:464

        /**
         * Re-order the {@link TransitionOp}s in {@link #ops} such that no operation modifies the
         * {@link TransitionOp#getSource(long) source} of any subsequent operation. If no such order
         * exists, temporary copies of counter-sets may be inserted.
         */
        private void scheduleOps() {
            if (ops.length() <= 1) {
                return;
            }
            for (int last = ops.length() - 1; last > 0; last--) {
                int toSchedule = scheduleOpsFindCandidate(last);
                if (toSchedule == -1) {
                    // TODO
                    // System.out.println("dependency cycle:");
                    // for (int i = 0; i <= last; i++) {
                    // System.out.println(TransitionOp.toString(ops.get(i)));
                    // }
                    // resolveDependencyCycle(last + 1);
                    throw new UnsupportedRegexException("dependency cycle");
                }
                long tmp = ops.get(last);
                ops.set(last, ops.get(toSchedule));
                ops.set(toSchedule, tmp);
            }
        }

        /**
         * Returns the index of the first operation between index {@code 0} and {@code last}
         * (inclusive) whose {@link TransitionOp#getSource(long) source} is unmodified by all other
         * operations in the specified range. If no such operation exists, returns {@code -1}.
         */
        private int scheduleOpsFindCandidate(int last) {
            outer: for (int i = 0; i <= last; i++) {
                int source = TransitionOp.getSource(ops.get(i));
                for (int j = 0; j <= last; j++) {
                    if (i != j && TransitionOp.getTarget(ops.get(j)) == source) {
                        continue outer;

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Reduce the number of nested capturing groups (non-capturing '(?:...)' where positions are not needed)
2. Restructure so that not all groups wrap the same quantified region; move groups inward onto the smallest needed subexpressions
3. Retry with the pattern split into multiple simpler regexes applied in sequence
4. If seen only as a log message with correct matching behavior, no action is needed — the backtracking fallback already handled it

Example fix

// before
String p = "((a)(b(c)?))+((d)?(e))+"; // heavily nested captures in one region

// after
String p = "(?:a(?:bc?)?)+"; // non-capturing, capture only the parts you read

// Default behavior already falls back to backtracking; only catch when forcing DFA/linear mode:
try {
    return compile(pattern, forcedOptions);
} catch (UnsupportedRegexException e) {
    log.debug("DFA op scheduling failed for pattern; falling back");
    return compile(pattern, defaultOptions);
}

When it happens

Trigger: Compiling (in DFA mode) a pattern whose capture-group updates within a single transition form a cyclic data dependency — typically patterns with many nested capture groups under interleaved quantifiers, e.g. ((a)(b)?)* with additional overlapping group writes. It is an internal limit of the op scheduler, not a syntax error.

Common situations: Rare; appears on machine-generated or heavily nested group patterns. Under default options the exception is caught in TRegexCompilationRequest and the engine falls back to backtracking, so users usually only see it (or its log line 'NFA generator bailout') when force-linear execution or eager DFA compilation is enabled or when reading fine-level matching-strategy logs.

Related errors

• Too much additional capture group tracking overhead
• too many capture group transitions
• too many branches in capture group tracking DFA
• too many partial transitions
• too many parallel NFA states in one DFA state for bounded qu

AI-assisted analysis of oracle/graal@a66e9ccd1d (2026-08-14). Data as JSON: /api/errors/8d4db48b20c549be. Report an issue: GitHub.