oracle/graal · error · UnsupportedRegexException

TraceFinder: too many possible results

Error message

TraceFinder: too many possible results

What it means

Thrown by NFATraceFinderGenerator while unrolling a match graph into pre-calculated result trees: when a graph path hits a state that was already duplicated, the path must be copied for every duplicate, and each copy becomes one possible result (resultID). If resultList.size() reaches TRegexTraceFinderMaxNumberOfResults (254), the TraceFinder (the sub-regex instrumentation used for find()/lookingAt pre-calculation) gives up.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/NFATraceFinderGenerator.java:240

                    RegexRootNode.checkThreadInterrupted();
                    // The graph-path contains nodes that have not been converted to tree form
                    // yet, and must be treated differently than the rest of the path.
                    while (duplicatedStatesMap[curElement.getTransition().getTarget().getId()] == null) {
                        RegexRootNode.checkThreadInterrupted();
                        graphPath.add(curElement);
                        curElement = new PathElement(curElement.getNextTransition());
                    }
                    /*
                     * We hit a node that has been converted to tree form already, so from here all
                     * nodes will have exactly one parent node (getNext().size() == 1). To create a
                     * proper tree, we have to duplicate the graphPath for all duplicates of the
                     * node we hit. Initially, we will hit one of newUnAnchoredFinalState and
                     * newAnchoredFinalState here.
                     */
                    for (NFAState duplicate : duplicatedStatesMap[curElement.getTransition().getTarget().getId()]) {
                        int resultID = resultList.size();
                        if (resultID == TRegexOptions.TRegexTraceFinderMaxNumberOfResults) {
                            throw new UnsupportedRegexException("TraceFinder: too many possible results");
                        }
                        NFAState lastCopied = copy(entry.getTarget(), resultID);
                        PreCalculatedResultFactory result = resultFactory();
                        // create a copy of the graph path
                        int iResult = 0;
                        for (int i = 0; i < graphPath.size(); i++) {
                            final NFAStateTransition pathTransition = graphPath.get(i).getTransition();
                            NFAState copy = copy(pathTransition.getTarget(), resultID);
                            createTransition(lastCopied, copy, pathTransition, result, iResult);
                            iResult += getEncodedSize(pathTransition);
                            lastCopied = copy;
                        }
                        // link the copied path to the existing tree
                        createTransition(lastCopied, duplicate, curElement.getTransition(), result, iResult);
                        // traverse the existing tree to the root to complete the pre-calculated
                        // result.
                        NFAStateTransition parentTransition = curElement.getTransition();
                        NFAState treeNode = duplicate;

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Deduplicate or factor overlapping alternation branches (common prefixes/suffixes) so fewer distinct paths reach the same final state.
2. Sort the alternation and drop branches that are prefixes of other branches when their captures are not needed.
3. Use matches() with a fully anchored wrapper instead of find() where possible to avoid TraceFinder generation.
4. Accept fallback to the backtracking engine (the exception is caught by TRegexCompilationRequest and retried).

Example fix

// before
String pattern = "a|aa|aaa|aaaa|aaaaa"; // overlapping branches, many result paths with find()

// after
String pattern = "a+"; // single path if group boundaries are not needed, or match anchors and check length in code

// detect overlapping literal branches before compiling for find()
String[] branches = extractTopLevelAlternatives(pattern); // your helper
for (int i = 0; i < branches.length; i++) for (int j = 0; j < branches.length; j++) if (i != j && branches[j].startsWith(branches[i])) throw new IllegalArgumentException("overlapping alternation branches; TraceFinder result limit risk");

null

try { compile(pattern); } catch (UnsupportedRegexException e) { if (e.getMessage().contains("TraceFinder")) { /* dedupe branches, use matches() instead of find(), or use backtracking fallback */ } }

When it happens

Trigger: Compiling a regex whose match graph can end in a state reachable via more than 254 distinct duplicated paths — typically heavily ambiguous patterns with many alternations converging on the same final states, e.g. (a|aa|aaa|...)+ style overlaps.

Common situations: Ambiguous alternation lists (e.g. token lists from a dictionary) sharing prefixes and suffixes; fuzzy/tokenizing patterns used with find(); very wide alternations of literals that all terminate in a common tail.

Related errors

• DFA transition size explosion
• ASTSuccessor explosion
• too many quantifiers
• ASTSuccessor explosion
• too many transitions

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