Skip to main content

Module call_graph

seqc

Module call_graph 

Source
Expand description

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.