{"record":{"id":"a059ed479844dffe","repo":"oracle/graal","slug":"tracefinder-too-many-possible-results","errorCode":null,"errorMessage":"TraceFinder: too many possible results","messagePattern":"TraceFinder: too many possible results","errorType":"exception","errorClass":"UnsupportedRegexException","httpStatus":null,"severity":"error","filePath":"regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/NFATraceFinderGenerator.java","lineNumber":240,"sourceCode":"                    RegexRootNode.checkThreadInterrupted();\n                    // The graph-path contains nodes that have not been converted to tree form\n                    // yet, and must be treated differently than the rest of the path.\n                    while (duplicatedStatesMap[curElement.getTransition().getTarget().getId()] == null) {\n                        RegexRootNode.checkThreadInterrupted();\n                        graphPath.add(curElement);\n                        curElement = new PathElement(curElement.getNextTransition());\n                    }\n                    /*\n                     * We hit a node that has been converted to tree form already, so from here all\n                     * nodes will have exactly one parent node (getNext().size() == 1). To create a\n                     * proper tree, we have to duplicate the graphPath for all duplicates of the\n                     * node we hit. Initially, we will hit one of newUnAnchoredFinalState and\n                     * newAnchoredFinalState here.\n                     */\n                    for (NFAState duplicate : duplicatedStatesMap[curElement.getTransition().getTarget().getId()]) {\n                        int resultID = resultList.size();\n                        if (resultID == TRegexOptions.TRegexTraceFinderMaxNumberOfResults) {\n                            throw new UnsupportedRegexException(\"TraceFinder: too many possible results\");\n                        }\n                        NFAState lastCopied = copy(entry.getTarget(), resultID);\n                        PreCalculatedResultFactory result = resultFactory();\n                        // create a copy of the graph path\n                        int iResult = 0;\n                        for (int i = 0; i < graphPath.size(); i++) {\n                            final NFAStateTransition pathTransition = graphPath.get(i).getTransition();\n                            NFAState copy = copy(pathTransition.getTarget(), resultID);\n                            createTransition(lastCopied, copy, pathTransition, result, iResult);\n                            iResult += getEncodedSize(pathTransition);\n                            lastCopied = copy;\n                        }\n                        // link the copied path to the existing tree\n                        createTransition(lastCopied, duplicate, curElement.getTransition(), result, iResult);\n                        // traverse the existing tree to the root to complete the pre-calculated\n                        // result.\n                        NFAStateTransition parentTransition = curElement.getTransition();\n                        NFAState treeNode = duplicate;","sourceCodeStart":222,"sourceCodeEnd":258,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/NFATraceFinderGenerator.java#L222-L258","documentation":"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.","triggerScenarios":"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.","commonSituations":"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.","solutions":["Deduplicate or factor overlapping alternation branches (common prefixes/suffixes) so fewer distinct paths reach the same final state.","Sort the alternation and drop branches that are prefixes of other branches when their captures are not needed.","Use matches() with a fully anchored wrapper instead of find() where possible to avoid TraceFinder generation.","Accept fallback to the backtracking engine (the exception is caught by TRegexCompilationRequest and retried)."],"exampleFix":"// before\nString pattern = \"a|aa|aaa|aaaa|aaaaa\"; // overlapping branches, many result paths with find()\n\n// after\nString pattern = \"a+\"; // single path if group boundaries are not needed, or match anchors and check length in code","handlingStrategy":"try-catch","validationCode":"// detect overlapping literal branches before compiling for find()\nString[] branches = extractTopLevelAlternatives(pattern); // your helper\nfor (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\");","typeGuard":"null","tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { if (e.getMessage().contains(\"TraceFinder\")) { /* dedupe branches, use matches() instead of find(), or use backtracking fallback */ } }","preventionTips":["Deduplicate prefix-overlapping alternation branches.","Prefer anchored matches() over find() for ambiguous patterns.","Use dedicated string search (Aho-Corasick) for large literal lists."],"tags":["regex","tregex","trace-finder","find","limit-exceeded"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}