oracle/graal · error · UnsupportedRegexException

Cannot compile regex with empty state to DFA/NFA

Error message

Cannot compile regex with empty state to DFA/NFA

What it means

Thrown by NFATraversalRegexASTVisitor while walking a mandatory quantifier loop that can match the empty string: when the flavor does not require empty-loop checks (emptyChecksOnMandatoryLoopIterations() is false), the group is mandatory and not unrolled, and capture groups are visible / back-references exist / a caret (or dollar, in reverse matching) was crossed, a DFA cannot represent the state and compilation bails out.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/parser/ast/visitors/NFATraversalRegexASTVisitor.java:602

            if (curTerm.isGroupWithGuards() && insideEmptyGuardGroup.get(curTerm.asGroup().getGroupsWithGuardsIndex()) &&
                            !getFlavor().emptyChecksMonitorCaptureGroups()) {
                Group curGroup = curTerm.asGroup();
                Quantifier quantifier = curGroup.getQuantifier();
                // If we are:
                // - in ECMAScript or Python flavor
                // - in the mandatory split part of a quantifier
                // - that has not been unrolled
                // - and capture groups are visible to the caller, or the expression contains
                // back-references, or we crossed a caret
                if (!getFlavor().emptyChecksOnMandatoryLoopIterations() &&
                                curGroup.isMandatoryQuantifier() &&
                                !curGroup.isExpandedQuantifier() &&
                                (!ast.getOptions().isBooleanMatch() || ast.getProperties().hasBackReferences() || caretsOnPath() || isReverse() && dollarsOnPath())) {
                    // the existence of a mandatory copy of the quantifier loop implies a minimum
                    // greater than zero
                    assert quantifier.getMin() > 0;
                    if (isBuildingDFA()) {
                        throw new UnsupportedRegexException("Cannot compile regex with empty state to DFA/NFA");
                    }
                    popGroupExit();
                    cur = curTerm;
                    // Set the current group node as the path's target to indicate we want to
                    // generate an EMPTY_STATE for it. The empty state allows the backtracking
                    // engine to loop without consuming characters.
                    curPath.add(PathElement.create(cur));
                    return true;
                }
                if (isBuildingDFA() && curGroup.isMandatoryQuantifier() && !lookAroundsOnPath.isEmpty()) {
                    for (int i = curPath.length() - 1; i >= 0; i--) {
                        long element = curPath.get(i);
                        RegexASTNode node = pathGetNode(element);
                        if (PathElement.isGroupEnter(element) && node == curGroup) {
                            break;
                        }
                        if (node.isLookAheadAssertion()) {
                            throw new UnsupportedRegexException("empty path with look-ahead assertion in expression with bounded quantifier");

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Make the loop body unable to match empty: change ((a)?){3} to (a){0,3} or ((a)+)? forms.
2. Remove the count from the group or drop the unnecessary capture group (use (?:...)).
3. Let the engine fall back to the backtracking NFA, which creates an EMPTY_STATE and loops without consuming characters.
4. If you control the flavor options, enable empty-checks-on-mandatory-loop-iterations semantics instead of rewriting the pattern.

Example fix

// before
String pattern = "((?:a)?){5}b"; // mandatory loop whose body can match empty

// after
String pattern = "a{0,5}b"; // loop body cannot match empty

// reject mandatory loops whose body is wholly optional: ((x)?){n} shape
if (Pattern.compile("\\(\\([^)]*\\)\\?\\)\\{\\d+\\}").matcher(pattern).find()) throw new IllegalArgumentException("mandatory loop can match empty; unsupported in linear engine");

null

try { compileLinear(pattern); } catch (UnsupportedRegexException e) { compileBacktracking(pattern); } // backtracking engine handles empty loops via EMPTY_STATE

When it happens

Trigger: Compiling in DFA-building mode a pattern like ((a)?){3} or (a*){2} — a mandatory bounded loop whose body can match empty — under flavors that skip empty-iteration checks when captures/back-references/anchors are involved.

Common situations: Validation patterns wrapping optional content in counted groups, e.g. (\w?){n}; patterns with back-references inside counted loops; porting between flavors (e.g. from Perl/PCRE to Java/OracleDB) with different empty-iteration semantics.

Related errors

• empty path with look-ahead assertion in expression with boun
• Too much additional capture group tracking overhead
• too many capture group transitions
• too many parallel NFA states in one DFA state for bounded qu
• dependency cycle

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