oracle/graal · error · UnsupportedRegexException

ASTSuccessor explosion

Error message

ASTSuccessor explosion

What it means

Thrown by ASTStep.addSuccessor when the number of ASTSuccessors in a single ASTStep exceeds TRegexMaxNumberOfASTSuccessorsInOneASTStep (Short.MAX_VALUE = 32767). Each ASTSuccessor represents one possible path to the next matching character; patterns like (a?|b?|c?|...)+ make this count grow exponentially with the number of repetitions. The bail-out happens during successor collection, before NFA transitions are built, to avoid running out of memory.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/ASTStep.java:89

    }

    public TBitSet getMatchedConditionGroups() {
        return matchedConditionGroups;
    }

    public void addSuccessor(ASTSuccessor successor) {
        successors.add(successor);
        // When compiling a regular expression, almost all ASTSuccessors will yield at least 1 NFA
        // transition (the only case when an ASTSuccessor yields no NFA transitions is when the NFA
        // transition would collide with a position assertion such as $ or ^, as in /(?=a$)ab/, see
        // NFAGenerator#createNFATransitions). Furthermore, there exist regular expressions such as
        // (a?|b?|c?|d?|e?|f?|g?)(a?|b?|c?|d?|e?|f?|g?)... The number of ASTSuccessors in a single
        // ASTStep rises exponentially with the number of repetitions of this pattern (there is a
        // different ASTSuccessor for every possible path to a next matching character). If we want
        // to avoid running out of memory in such situations, we have to bailout during the
        // collection of ASTSuccessors in ASTStep, before they are transformed into NFA transitions.
        if (successors.size() > TRegexOptions.TRegexMaxNumberOfASTSuccessorsInOneASTStep) {
            throw new UnsupportedRegexException("ASTSuccessor explosion");
        }
    }

    @TruffleBoundary
    @Override
    public JsonValue toJson() {
        return Json.obj(Json.prop("root", root.getId()),
                        Json.prop("successors", successors),
                        Json.prop("matchedConditionGroups", Json.array(matchedConditionGroups.stream().toArray())));
    }
}

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Rewrite the pattern to avoid optional-alternation blocks that all continue into the same successor term; e.g. replace (a?|b?|c?){8} style constructs with character classes or a bounded loop over a class.
2. Use a single character class [abc]? instead of alternations of single optional characters.
3. Split the expression into multiple regexes matched separately and combined in application code.
4. Accept the backtracking-engine fallback (the exception is caught in TRegexCompiler/TRegexCompilationRequest and retried as NFA) instead of forcing the linear-time engine.

Example fix

// before
String pattern = "(a?|b?|c?|d?|e?|f?|g?)(a?|b?|c?|d?|e?|f?|g?)(a?|b?|c?|d?|e?|f?|g?)..."; // repeated many times

// after
String pattern = "[a-g]?[a-g]?[a-g]?..."; // or "[a-g]{0,n}" — one successor per step

// reject patterns concatenating many optional-alternation blocks before compiling
int optionalAltBlocks = pattern.split("\\?\\|", -1).length - 1; // heuristic
if (optionalAltBlocks > 20) throw new IllegalArgumentException("pattern risks ASTSuccessor explosion");

null

try { compile(pattern); } catch (UnsupportedRegexException e) { /* log and fall back to backtracking engine or reject input pattern */ }

When it happens

Trigger: Compiling a regex whose single AST step (one input position) can be reached via exponentially many paths, e.g. (a?|b?|c?|d?|e?|f?|g?){n} repeated enough times, or deeply nested optional alternations that all converge on the same next term.

Common situations: Dynamically constructed regexes that concatenate many optional-alternation blocks; data-driven pattern generation that unrolls quantifiers into long optional chains; denial-of-service-like patterns accidentally fed to the compiler.

Related errors

• ASTSuccessor explosion
• DFA transition size explosion
• too many quantifiers
• TraceFinder: too many possible results
• too many transitions

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