oracle/graal · error · UnsupportedRegexException

Regex with overlapping bounded quantifier (after look-ahead

Error message

Regex with overlapping bounded quantifier (after look-ahead merging)

What it means

Thrown by ASTSuccessor.addAllIntersecting during look-ahead merging: after merging a look-ahead's transitions into a successor state, the accumulated TransitionConstraints must all reference the same quantifier id (firstQid). If constraints on different quantifiers end up on one merged transition, the linear engine cannot evaluate them and rejects the regex.

Source

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

                    LongArrayBuffer mergedOperations = new LongArrayBuffer();
                    StateSet<RegexAST, Term> mergedStateSet = state.getTransitionSet().getTargetStateSet().copy();
                    mergedTransitions.addAll(state.getTransitionSet().getTransitions());
                    mergedConstraints.addAll(state.getConstraints());
                    mergedOperations.addAll(state.getOperations());

                    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())),

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Remove the bounded count from inside the look-ahead, e.g. replace (?=x{1,2}y) with (?=x{0,2}y) variants, or an unbounded/greedy form (?=x*y) when the exact count is not load-bearing.
2. Move the counted constraint out of the look-ahead into the main expression.
3. Let the pattern fall back to the backtracking engine, which handles overlapping counted quantifiers.
4. Verify the counted condition in application code after the match.

Example fix

// before
String pattern = "(a{1,3}b)*(?=x{1,2}y)";

// after
String pattern = "(a{1,3}b)*(?=x{0,2}y)"; // constraint on only one quantifier, or
String pattern = "(a{1,3}b)*"; // check the x{1,2}y condition in code after matching

// reject look-aheads containing bounded quantifiers when the main path also has one
Matcher m = Pattern.compile("\\(\\?=(.*?\\{\\d+,\\d+\\}.*)\\)").matcher(pattern);
if (m.find() && pattern.matches(".*\\{\\d+,\\d+\\}.*")) throw new IllegalArgumentException("overlapping bounded quantifier across look-ahead");

null

try { compile(pattern); } catch (UnsupportedRegexException e) { /* rewrite look-ahead without counted bounds, or use backtracking fallback */ }

When it happens

Trigger: A look-ahead that contains a bounded quantifier whose constraints overlap with a bounded quantifier active on the main path, e.g. patterns like (a{1,3}b)*(?=x{1,2}y) where the merged transition constrains both the outer and the look-ahead's quantifier.

Common situations: Password/validation regexes combining counted repetition with look-aheads; ported PCRE patterns using (?=(...){m,n}) constructs; generated patterns that wrap every alternative in a counted group and a look-ahead.

Related errors

• too many quantifiers
• empty path with look-ahead assertion in expression with boun
• DFA transition size explosion
• nested look-behind assertions
• ASTSuccessor explosion

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