oracle/graal · error · UnsupportedRegexException

parse tree explosion

Error message

parse tree explosion

What it means

Thrown by ThresholdCounter during regex AST construction (RegexAST.java:121) when the number of parse-tree nodes exceeds the MaxParserTreeSize option (default TRegexOptions.TRegexParserTreeMaxSize). It is a hard size guard: TRegex refuses to build an AST for patterns so large that compilation cost or memory use would explode. The throw is an UnsupportedRegexException, the standard 'this pattern is too complex for TRegex' signal.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/parser/Counter.java:91

        count -= i;
        return ret;
    }

    public static class ThresholdCounter extends Counter {

        private final int max;
        private final String errorMsg;

        public ThresholdCounter(int max, String errorMsg) {
            this.max = max;
            this.errorMsg = errorMsg;
        }

        @Override
        public int inc(int i) {
            final int ret = super.inc(i);
            if (getCount() > max) {
                throw new UnsupportedRegexException(errorMsg);
            }
            return ret;
        }
    }

    public static class ThreadSafeCounter extends Counter {

        @Override
        public int inc() {
            int c = count;
            if (c < Integer.MAX_VALUE) {
                count = c + 1;
            }
            return count;
        }

        @Override
        public int inc(int i) {

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Simplify or split the pattern: replace long literal alternations with a trie-like grouping or match them in guest-language code instead of one regex.
2. Raise the limit at compile time via the RegexOptions string, e.g. append 'MaxParserTreeSize=10000' (option key RegexOptions.MAX_PARSER_TREE_SIZE_NAME); in Truffle settings it appears as regexDummyLang.MaxParserTreeSize.
3. Catch UnsupportedRegexException at the compilation call site and fall back to a simpler matcher (backtracking engine or literal search).

Example fix

// before
Object result = regexLanguage.parse(sourceWithHugePattern);

// after
try {
    Object result = regexLanguage.parse(source);
} catch (UnsupportedRegexException e) {
    // pattern exceeds parser limits; use fallback matcher
    throw new PatternSyntaxException("pattern too large: " + source.getFlags(), e);
}

// Pre-compile pattern at startup / cache site before hot use
try {
    Object compiled = compiler.compile(source, options);
} catch (UnsupportedRegexException e) {
    // decide: reject input, or lower MaxParserTreeSize pressure
}

catch (UnsupportedRegexException e) — it extends AbstractTruffleException; catch it at the regex-compilation boundary, log source name/pattern hash, and fall back to a guest-language backtracking matcher or reject the input pattern.

When it happens

Trigger: Parsing a pattern with a very large number of AST nodes: deeply nested groups, huge character classes, or machine-generated patterns (e.g. alternations of thousands of literals). The counter increments per node created in RegexAST, so any API that compiles a regex source (RegexCompiler via a Truffle regex language) triggers it once nodeCount > MaxParserTreeSize.

Common situations: Generated/programmatic regexes (keyword lists joined with |), JSON-schema-derived patterns, obfuscated or minified patterns embedded in scraped JS, or users lowering MaxParserTreeSize for tests (as RubyTests does with 'MaxParserTreeSize=10000') and then feeding it a normal pattern.

Related errors

• NFA explosion
• NFA transition explosion
• TraceFinder NFA explosion
• TraceFinder NFA transition explosion
• PureNFA explosion

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