java-topology/tools/tickets/defects/solc-0001.md

id	repo	file	line	status	severity	complexity	pattern
solc-0001	ethereum/solidity	libyul/optimiser/CallGraphGenerator.cpp	49	unpatched	HIGH	O(F × D²) — F functions, D max call depth	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:

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:

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