Module call_graph 

Call graph analysis for detecting mutual recursion

This module builds a call graph from a Seq program and detects strongly connected components (SCCs) to identify mutual recursion cycles.

Usage

let call_graph = CallGraph::build(&program);
let cycles = call_graph.recursive_cycles();

Primary Use Cases

1. Type checker divergence detection: The type checker uses the call graph to identify mutually recursive tail calls, enabling correct type inference for patterns like even/odd that would otherwise require branch unification.

2. Future optimizations: The call graph infrastructure can support dead code detection, inlining decisions, and diagnostic tools.

Implementation Details

• Algorithm: Tarjan’s SCC algorithm, O(V + E) time complexity
• Builtins: Calls to builtins/external words are excluded from the graph (they don’t affect recursion detection since they always return)
• Quotations: Calls within quotations are included in the analysis
• Match arms: Calls within match arms are included in the analysis

Note on Tail Call Optimization

The existing codegen already emits musttail for all tail calls to user-defined words (see codegen/statements.rs). This means mutual TCO works automatically without needing explicit call graph checks in codegen. The call graph is primarily used for type checking, not for enabling TCO.

Structs

CallGraph

A call graph representing which words call which other words.

TailCallInfo

Information about tail calls for mutual TCO optimization.