Codegen time grows cubically with call-chain depth #267

Code generation time grows roughly with the cube of call-chain depth, so rue build becomes unusable on projects that are large but not unusual. Checking the same projects scales linearly.

Reproduction

The script below generates a project of N files with 20 small functions each (about 144 lines per file). File i imports and calls one function from file i - 1, and main calls into the last file, so main reaches a call chain N deep.

# usage: python3 gen.py <dir> <files> <functions per file>
import sys, os
root, nfiles, nfns = sys.argv[1], int(sys.argv[2]), int(sys.argv[3])
os.makedirs(root + "/src", exist_ok=True)
open(root + "/Rue.toml", "w").write('[compiler]\nentrypoint = "src"\n')
for i in range(nfiles):
    L = []
    if i > 0:
        L.append(f"import m{i-1}::{{f{i-1}_0, P{i-1}}};\n")
    L.append(f"export struct P{i} {{ a: Int, b: Int }}\n")
    for j in range(nfns):
        L.append(f"export fn f{i}_{j}(x: Int, y: Int) -> Int {{")
        L.append(f"    let p = P{i} {{ a: x, b: y }};")
        L.append(f"    let s = p.a * {j+1} + p.b;")
        if i > 0 and j == 0:
            L.append(f"    let q = P{i-1} {{ a: s, b: x }};")
            L.append(f"    let t = f{i-1}_0(q.a, q.b);")
        else:
            L.append(f"    let t = s - {j};")
        L.append(f"    if t > 100 {{ t / 2 }} else {{ t + x * y }}")
        L.append("}\n")
    open(f"{root}/src/m{i}.rue", "w").write("\n".join(L))
last = nfiles - 1
open(root + "/src/main.rue", "w").write(
    f"import m{last}::f{last}_0;\n\nfn main(x: Int) -> Int {{\n    f{last}_0(x, 3)\n}}\n")

CPU time per phase, measured by calling rue-compiler directly (release build, macOS aarch64):

Each doubling of depth multiplies codegen time by about 8. If every file imports from m0 instead (no chain, same size), codegen time stays near zero, and checking 58k lines takes 1.6s.

Cause

A CPU profile of codegen at depth 200 is dominated by DependencyGraph::dependencies (crates/rue-hir/src/dependency_graph.rs) and the hashing, set insertion and allocation it does:

• Each call walks the full transitive closure from the symbol, with a fresh visited set.
• Each stack entry clones self.dependencies[current] and the entered vector, and visited hashes (SymbolId, bool, Vec<bool>) tuples.
• Nothing is cached, and lowering calls it from several places in crates/rue-hir/src/lower.rs: once per function for its captures (function_groups, and again around line 578), once per referenced symbol to decide whether to inline it (the dependencies(symbol, false).contains(&symbol) check around line 1036), and inside the loop that splits symbols into groups (around line 906). That loop calls it for every remaining symbol on every pass.

Each call is O(N) for a chain N deep, and the number of calls grows with N (or N² in the grouping loop), which matches the roughly cubic growth.

Possible fix

Memoize the closure per (symbol, captures_only), or compute every symbol's closure once when the graph is built.

The part that needs care is entered. Whether a local counts as a capture depends on which enclosing scopes the path has entered, so the result depends on the starting symbol's owners as well as on the symbol being visited. One option: split the closure into a path-independent part, cached per symbol, and the filtering of the starting symbol's enclosing-scope locals, applied afterwards. The existing closure-capture tests in rue-hir and the end-to-end tests should pin down the behavior.

A regression test could build a chain a few hundred calls deep and assert that codegen finishes well within a time budget, or count calls to dependencies.

Related: #268 (the same chain shape overflows the stack at around 2000 calls).