oracle/graal · error · UnsupportedRegexException

backtracking stack limit exceeded

Error message

backtracking stack limit exceeded

What it means

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.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nodes/nfa/TRegexBacktrackingNFAExecutorLocals.java:376

    }

    private void ensureSize(int minSize) {
        if (CompilerDirectives.injectBranchProbability(CompilerDirectives.SLOWPATH_PROBABILITY, minSize > TRegexOptions.TRegexMaxBacktrackingStackSize)) {
            CompilerDirectives.transferToInterpreterAndInvalidate();
            throwBacktrackingStackLimitExceeded();
        }
        if (stack().length < minSize) {
            int newLength = stack().length << 1;
            while (newLength < minSize) {
                newLength <<= 1;
            }
            stack.stack = Arrays.copyOf(stack(), newLength);
        }
    }

    @TruffleBoundary
    private static void throwBacktrackingStackLimitExceeded() {
        throw new UnsupportedRegexException("backtracking stack limit exceeded");
    }

    public void pushResult(int[] groupBoundaries, int groupBoundaryRecord, int index) {
        EncodedGroupBoundaries.applyExploded(groupBoundaries, groupBoundaryRecord, result, 0, result.length - 1, index, trackLastGroup, dontOverwriteLastGroup);
        pushResult();
    }

    /**
     * Marks that a result was pushed at the current stack frame.
     */
    public void pushResult() {
        lastResultSp = sp;
        lastResultIndex = getIndex();
    }

    /**
     * Copies the current capture group boundaries to the result array.
     */

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Rewrite the pattern to remove ambiguous nesting: use possessive/atomic equivalents supported by the flavor, character classes, or unrolled loops.
2. Bound the repeated groups explicitly so the exploration depth is finite and small.
3. Pre-validate input length before matching very long strings against nested quantifiers.
4. Anchor the pattern or use find() with tighter regions to reduce exploration.

Example fix

// before
String pattern = "(a+)+b"; // explosive on long 'aaaa...' inputs

// after
String pattern = "a+b"; // or "(?>a+)b" / possessive form where the flavor supports it

// guard input length before matching nested-quantifier patterns
if (pattern.contains("+)+") || pattern.matches(".*\\(\\.[*++].*\\).*")) { if (input.length() > 1000) throw new IllegalArgumentException("input too long for this pattern shape"); }

null

try { matcher.find(); } catch (UnsupportedRegexException e) { if (e.getMessage().contains("backtracking stack")) { /* reject pattern/input combination; do not retry the same input */ } }

When it happens

Trigger: 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.

Common situations: 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.

Related errors

• Independent non-capturing groups are not supported
• regex cannot be executed in linear time
• Too much additional capture group tracking overhead
• too many capture group 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/6a66ce56c9011be5. Report an issue: GitHub.