oracle/graal · error · UnsupportedRegexException

Too much additional capture group tracking overhead

Error message

Too much additional capture group tracking overhead

What it means

Thrown by TRegexCompiler.compileEagerDFAExecutor when the eager (pre-compiled) DFA's capture-group tracking cost exceeds TRegexMaxEagerCGDFACost (default 3000). Capture groups force the DFA to carry per-group position tracking through every transition; if that machinery would dominate the compiled executor, compilation is aborted with UnsupportedRegexException instead of producing a bloated matcher.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/TRegexCompiler.java:97

        } catch (UnsupportedRegexException bailout) {
            logCompilationTime(source, timer, null);
            Loggers.LOG_BAILOUT_MESSAGES.fine(() -> bailout.getReason() + ": " + source);
            throw bailout;
        }
    }

    @TruffleBoundary
    private static RegexObject doCompile(RegexLanguage language, RegexSource source) throws RegexSyntaxException {
        TRegexCompilationRequest compReq = new TRegexCompilationRequest(language, source);
        RegexExecNode execNode = compReq.compile();
        return new RegexObject(language, source, execNode, compReq.getAst().getFlavorSpecificFlags(), compReq.getAst().getNumberOfCaptureGroups(), compReq.getNamedCaptureGroups());
    }

    @TruffleBoundary
    public static TRegexDFAExecutorNode compileEagerDFAExecutor(RegexLanguage language, RegexSource source) {
        TRegexDFAExecutorNode executor = new TRegexCompilationRequest(language, source).compileEagerDFAExecutor();
        if (executor.getCGTrackingCost() > TRegexOptions.TRegexMaxEagerCGDFACost) {
            throw new UnsupportedRegexException("Too much additional capture group tracking overhead");
        }
        return executor;
    }

    @TruffleBoundary
    public static LazyCaptureGroupRegexSearchNode compileLazyDFAExecutor(RegexLanguage language, RegexSource source, NFA nfa, RegexProfile rootNodeProfile, boolean allowSimpleCG) {
        assert nfa == null || nfa.getAst().getSource() == source;
        if (nfa == null) {
            return new TRegexCompilationRequest(language, source).compileLazyDFAExecutorFromSource(rootNodeProfile, allowSimpleCG);
        } else {
            return new TRegexCompilationRequest(language, nfa).compileLazyDFAExecutor(rootNodeProfile, allowSimpleCG);
        }
    }

    @TruffleBoundary
    public static TRegexBacktrackerSubExecutorNode compileBacktrackingExecutor(RegexLanguage language, NFA nfa) {
        return new TRegexCompilationRequest(language, nfa).compileBacktrackingExecutor();
    }

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Convert capture groups that are not inspected later into non-capturing groups '(?:...)' — often the single biggest cost reduction
2. Split the pattern into several simpler regexes and combine results in host code instead of one group-heavy pattern
3. Use the lazy DFA executor (compileLazyDFAExecutor) or the default compilation path, which compiles states on demand and does not pay eager CG cost
4. Raise TRegexMaxEagerCGDFACost in TRegexOptions if the cost is acceptable for your workload (rebuild-time decision)

Example fix

// before
String p = "(a+)(b+)(c+)(d+)(e+)(f+)(g+)(h+)"; // 8 tracked groups

// after
String p = "(?:a+)(?:b+)(?:c+)(?:d+)(?:e+)(?:f+)(?:g+)(h+)"; // track only what you use

int captureGroupCount(String pattern) {
    int n = 0, depth = 0;
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        if (c == '\\') { i++; continue; }
        if (c == '(' && (i + 1 >= pattern.length() || pattern.charAt(i + 1) != '?')) n++;
    }
    return n; // heuristic: eager CG DFA cost grows with group count and quantifier nesting
}

try {
    return TRegexCompiler.compileEagerDFAExecutor(language, source);
} catch (UnsupportedRegexException e) {
    // capture-tracking cost too high: use the lazy DFA / default compile path instead
    return TRegexCompiler.compile(language, source); // falls back internally
}

When it happens

Trigger: Calling compileEagerDFAExecutor (eager DFA compilation, e.g. for a RegexExecNode with upfront-compiled automaton) on a pattern with many capture groups, nested quantified groups, or group-heavy alternations such that executor.getCGTrackingCost() > 3000.

Common situations: Embeddings that pin compilation to the eager DFA strategy for predictable first-match latency; patterns auto-generated by tools that wrap every alternation branch in (...) instead of (?:...); large log-matching patterns with dozens of labeled groups.

Related errors

• too many capture group transitions
• dependency cycle
• 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/063d7fb9c42915e1. Report an issue: GitHub.