---
id: solc-0001
repo: ethereum/solidity
file: libyul/optimiser/CallGraphGenerator.cpp
line: 49
status: unpatched
severity: HIGH
complexity: O(F × D²) — F functions, D max call depth
pattern: std::find on std::vector<FunctionHandle> currentPath in DFS cycle detector
---

## Description

`CallGraphCycleFinder::visit()` maintains `currentPath` as a `std::vector<FunctionHandle>`
representing the current DFS stack. On every node visited, it calls:

```cpp
auto it = find(currentPath.begin(), currentPath.end(), _function);  // O(|path|)
```

This is an O(|path|) linear scan to check whether `_function` is already on the current
DFS path (i.e., whether we've found a cycle back to it). For a call graph with F functions
and maximum call depth D, the total cost is O(F × D²).

The developer left a comment at line 36: `// TODO: This algorithm is non-optimal.`

## Context

`CallGraph::recursiveFunctions()` is called during Yul optimizer passes to identify which
functions are recursive (so they can be handled differently during inlining and optimization).
It is invoked on every contract compiled through the Yul IR pipeline, which includes all
contracts compiled with `--via-ir` or `--optimize` on modern solc.

## Fix

Maintain a parallel `std::set<FunctionHandle>` (or `std::unordered_set` if hash is available)
alongside `currentPath`:

```cpp
struct CallGraphCycleFinder {
    CallGraph const& callGraph;
    std::set<FunctionHandle> containedInCycle{};
    std::set<FunctionHandle> visited{};
    std::vector<FunctionHandle> currentPath{};
    std::set<FunctionHandle> currentPathSet{};  // CWE-407 fix

    void visit(FunctionHandle const& _function) {
        if (visited.count(_function))
            return;
        if (currentPathSet.count(_function))  // O(log n) instead of O(|path|)
        {
            // Cycle confirmed — find position for range insert (rare, O(|path|) ok)
            auto it = find(currentPath.begin(), currentPath.end(), _function);
            containedInCycle.insert(it, currentPath.end());
        }
        else {
            currentPathSet.insert(_function);
            currentPath.emplace_back(_function);
            if (callGraph.functionCalls.count(_function))
                for (auto const& child: callGraph.functionCalls.at(_function))
                    visit(child);
            currentPath.pop_back();
            currentPathSet.erase(_function);
            visited.insert(_function);
        }
    }
};
```

The fallback `find` inside the cycle-detected branch runs only when a cycle is actually
found — rare in practice. The hot path (no cycle) is now O(log D) per node instead of O(D).

## Complexity after fix

O(F × D × log D) instead of O(F × D²).

## Work items

- [ ] patch
- [ ] unit test (operation count: comparisons before and after at F=100, D=50)
- [ ] integration test (contracts with recursive Yul functions)
- [ ] benchmark