{"record":{"id":"8d4db48b20c549be","repo":"oracle/graal","slug":"dependency-cycle","errorCode":null,"errorMessage":"dependency cycle","messagePattern":"dependency cycle","errorType":"exception","errorClass":"UnsupportedRegexException","httpStatus":null,"severity":"warning","filePath":"regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java","lineNumber":464,"sourceCode":"        /**\n         * Re-order the {@link TransitionOp}s in {@link #ops} such that no operation modifies the\n         * {@link TransitionOp#getSource(long) source} of any subsequent operation. If no such order\n         * exists, temporary copies of counter-sets may be inserted.\n         */\n        private void scheduleOps() {\n            if (ops.length() <= 1) {\n                return;\n            }\n            for (int last = ops.length() - 1; last > 0; last--) {\n                int toSchedule = scheduleOpsFindCandidate(last);\n                if (toSchedule == -1) {\n                    // TODO\n                    // System.out.println(\"dependency cycle:\");\n                    // for (int i = 0; i <= last; i++) {\n                    // System.out.println(TransitionOp.toString(ops.get(i)));\n                    // }\n                    // resolveDependencyCycle(last + 1);\n                    throw new UnsupportedRegexException(\"dependency cycle\");\n                }\n                long tmp = ops.get(last);\n                ops.set(last, ops.get(toSchedule));\n                ops.set(toSchedule, tmp);\n            }\n        }\n\n        /**\n         * Returns the index of the first operation between index {@code 0} and {@code last}\n         * (inclusive) whose {@link TransitionOp#getSource(long) source} is unmodified by all other\n         * operations in the specified range. If no such operation exists, returns {@code -1}.\n         */\n        private int scheduleOpsFindCandidate(int last) {\n            outer: for (int i = 0; i <= last; i++) {\n                int source = TransitionOp.getSource(ops.get(i));\n                for (int j = 0; j <= last; j++) {\n                    if (i != j && TransitionOp.getTarget(ops.get(j)) == source) {\n                        continue outer;","sourceCodeStart":446,"sourceCodeEnd":482,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java#L446-L482","documentation":"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').","triggerScenarios":"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.","commonSituations":"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.","solutions":["Reduce the number of nested capturing groups (non-capturing '(?:...)' where positions are not needed)","Restructure so that not all groups wrap the same quantified region; move groups inward onto the smallest needed subexpressions","Retry with the pattern split into multiple simpler regexes applied in sequence","If seen only as a log message with correct matching behavior, no action is needed — the backtracking fallback already handled it"],"exampleFix":"// before\nString p = \"((a)(b(c)?))+((d)?(e))+\"; // heavily nested captures in one region\n\n// after\nString p = \"(?:a(?:bc?)?)+\"; // non-capturing, capture only the parts you read","handlingStrategy":"fallback","validationCode":null,"typeGuard":null,"tryCatchPattern":"// Default behavior already falls back to backtracking; only catch when forcing DFA/linear mode:\ntry {\n    return compile(pattern, forcedOptions);\n} catch (UnsupportedRegexException e) {\n    log.debug(\"DFA op scheduling failed for pattern; falling back\");\n    return compile(pattern, defaultOptions);\n}","preventionTips":["Treat 'dependency cycle' log lines as a hint to reduce nested capture groups, not as a hard failure","Keep group writes non-overlapping: each capture group wraps the smallest needed subexpression"],"tags":["regex","tregex","dfa","capture-groups","internal-limit"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}