oracle/graal · error · UnsupportedRegexException

ASTSuccessor explosion

Error message

ASTSuccessor explosion

What it means

Thrown by ASTSuccessor.addAllIntersecting when the result list of merging look-aheads with the current transition reaches TRegexMaxNumberOfASTSuccessorsInOneASTStep (Short.MAX_VALUE = 32767) before the next element is added. It is the same exponential-successor guard as in ASTStep.addSuccessor, but applied during look-around merging, where each look-ahead multiplies the number of merged transitions.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/ASTSuccessor.java:182

                    for (int i = 0; i < lookAroundState.getTransitionSet().size(); i++) {
                        ASTTransition t = lookAroundState.getTransitionSet().getTransition(i);
                        if (mergedStateSet.add(t.getTarget())) {
                            mergedTransitions.add(t);
                            mergedConstraints.addAll(t.getConstraints());
                            mergedOperations.addAll(t.getOperations());
                        }
                    }
                    if (!mergedConstraints.isEmpty()) {
                        int firstQid = TransitionConstraint.getQuantifierID(mergedConstraints.get(0));
                        for (long constraint : mergedConstraints) {
                            if (TransitionConstraint.getQuantifierID(constraint) != firstQid) {
                                throw new UnsupportedRegexException("Regex with overlapping bounded quantifier (after look-ahead merging)");
                            }
                        }
                    }
                    if (result.size() >= TRegexOptions.TRegexMaxNumberOfASTSuccessorsInOneASTStep) {
                        throw new UnsupportedRegexException("ASTSuccessor explosion");
                    }
                    result.add(new TransitionBuilder<>(mergedTransitions.toArray(new ASTTransition[mergedTransitions.length()]), mergedStateSet, intersection, mergedConstraints.toArray(),
                                    mergedOperations.toArray()));
                }
            }
        }
    }

    @TruffleBoundary
    @Override
    public JsonValue toJson() {
        return Json.obj(Json.prop("lookAheads", lookAheads.stream().map(x -> Json.val(x.getRoot().getId())).collect(Collectors.toList())),
                        Json.prop("lookBehinds", lookBehinds.stream().map(x -> Json.val(x.getRoot().getId())).collect(Collectors.toList())),
                        Json.prop("mergedStates", mergedStates));
    }
}

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Reduce the number of stacked look-aheads; combine their conditions into fewer assertions or plain alternatives.
2. Narrow the alternatives inside the look-aheads (character classes instead of long alternations).
3. Replace look-ahead stacks with separate sequential matches validated in code.
4. Allow fallback to the backtracking engine rather than forcing the linear engine.

Example fix

// before
String pattern = "(?=.*a)(?=.*b)(?=.*c)(?=.*d)...(?=.*z)^.*$"; // many look-aheads merged

// after
boolean ok = input.chars().anyMatch(...); // simple contains() checks per letter in code
Pattern p = Pattern.compile("^.*$");

int lookAheads = pattern.split("\\(\\?=", -1).length - 1; if (lookAheads > 10) throw new IllegalArgumentException("too many stacked look-aheads; risk of successor explosion");

null

try { compile(pattern); } catch (UnsupportedRegexException e) { /* reduce look-ahead count or fall back to backtracking engine */ }

When it happens

Trigger: Compiling a regex that combines multiple look-aheads with branching transitions so that the cartesian product of merged states exceeds 32767, e.g. several (?=...)(?=...) assertions stacked over a wide alternation.

Common situations: Password-strength / format-validation patterns stacking many look-aheads; generated patterns that prepend dozens of independent look-ahead checks; look-aheads over character-class alternations with many branches.

Related errors

• ASTSuccessor explosion
• DFA transition size explosion
• too many quantifiers
• Regex with overlapping bounded quantifier (after look-ahead
• TraceFinder: too many possible results

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