{"record":{"id":"6a66ce56c9011be5","repo":"oracle/graal","slug":"backtracking-stack-limit-exceeded","errorCode":null,"errorMessage":"backtracking stack limit exceeded","messagePattern":"backtracking stack limit exceeded","errorType":"exception","errorClass":"UnsupportedRegexException","httpStatus":null,"severity":"error","filePath":"regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nodes/nfa/TRegexBacktrackingNFAExecutorLocals.java","lineNumber":376,"sourceCode":"    }\n\n    private void ensureSize(int minSize) {\n        if (CompilerDirectives.injectBranchProbability(CompilerDirectives.SLOWPATH_PROBABILITY, minSize > TRegexOptions.TRegexMaxBacktrackingStackSize)) {\n            CompilerDirectives.transferToInterpreterAndInvalidate();\n            throwBacktrackingStackLimitExceeded();\n        }\n        if (stack().length < minSize) {\n            int newLength = stack().length << 1;\n            while (newLength < minSize) {\n                newLength <<= 1;\n            }\n            stack.stack = Arrays.copyOf(stack(), newLength);\n        }\n    }\n\n    @TruffleBoundary\n    private static void throwBacktrackingStackLimitExceeded() {\n        throw new UnsupportedRegexException(\"backtracking stack limit exceeded\");\n    }\n\n    public void pushResult(int[] groupBoundaries, int groupBoundaryRecord, int index) {\n        EncodedGroupBoundaries.applyExploded(groupBoundaries, groupBoundaryRecord, result, 0, result.length - 1, index, trackLastGroup, dontOverwriteLastGroup);\n        pushResult();\n    }\n\n    /**\n     * Marks that a result was pushed at the current stack frame.\n     */\n    public void pushResult() {\n        lastResultSp = sp;\n        lastResultIndex = getIndex();\n    }\n\n    /**\n     * Copies the current capture group boundaries to the result array.\n     */","sourceCodeStart":358,"sourceCodeEnd":394,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nodes/nfa/TRegexBacktrackingNFAExecutorLocals.java#L358-L394","documentation":"Thrown via TRegexBacktrackingNFAExecutorLocals.throwBacktrackingStackLimitExceeded when the backtracking engine's stack cannot be grown enough for the required frame count. The engine doubles the stack array up to an internal limit; a regex whose exploration requires more simultaneous stack frames than that limit (e.g. deep nesting of groups/quantifiers over long inputs) is rejected at runtime, not at compile time.","triggerScenarios":"Executing a match on the backtracking executor where the pattern nests many groups/alternations and the input is long enough that the number of pushed exploration frames exceeds the stack-size limit during ensureStackSpace.","commonSituations":"Catastrophic-backtracking-shaped patterns ((a+)+b style) on long inputs; deeply nested groups from generated patterns; a regex that only blows the stack on specific input lengths, making it look like an intermittent failure.","solutions":["Rewrite the pattern to remove ambiguous nesting: use possessive/atomic equivalents supported by the flavor, character classes, or unrolled loops.","Bound the repeated groups explicitly so the exploration depth is finite and small.","Pre-validate input length before matching very long strings against nested quantifiers.","Anchor the pattern or use find() with tighter regions to reduce exploration."],"exampleFix":"// before\nString pattern = \"(a+)+b\"; // explosive on long 'aaaa...' inputs\n\n// after\nString pattern = \"a+b\"; // or \"(?>a+)b\" / possessive form where the flavor supports it","handlingStrategy":"validation","validationCode":"// guard input length before matching nested-quantifier patterns\nif (pattern.contains(\"+)+\") || pattern.matches(\".*\\\\(\\\\.[*++].*\\\\).*\")) { if (input.length() > 1000) throw new IllegalArgumentException(\"input too long for this pattern shape\"); }","typeGuard":"null","tryCatchPattern":"try { matcher.find(); } catch (UnsupportedRegexException e) { if (e.getMessage().contains(\"backtracking stack\")) { /* reject pattern/input combination; do not retry the same input */ } }","preventionTips":["Avoid ambiguous nested quantifiers like (a+)+.","Bound exploration with explicit {m,n} limits.","Cap input length before matching untrusted patterns.","Treat this as a pattern-shape defect, not a transient failure — never retry unchanged."],"tags":["regex","tregex","backtracking","runtime","stack-overflow"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}