logicaffeine_compile/analysis/
callgraph.rs

1use std::collections::{HashMap, HashSet};
2
3use logicaffeine_base::{Interner, Symbol};
4use logicaffeine_language::ast::{Expr, Stmt};
5use logicaffeine_language::ast::stmt::ClosureBody;
6
7/// Whole-program call graph for the LOGOS compilation pipeline.
8///
9/// Captures all direct and closure-embedded call edges between user-defined
10/// functions. Used by `ReadonlyParams` for transitive mutation detection and
11/// by liveness analysis for inter-procedural precision.
12pub struct CallGraph {
13    /// Direct call edges: fn_sym → set of directly called function symbols.
14    pub edges: HashMap<Symbol, HashSet<Symbol>>,
15    /// Set of native (extern) function symbols.
16    pub native_fns: HashSet<Symbol>,
17    /// Strongly connected components (Kosaraju's algorithm).
18    pub sccs: Vec<Vec<Symbol>>,
19}
20
21impl CallGraph {
22    /// Build the call graph from a program's top-level statements.
23    ///
24    /// Walks all `FunctionDef` bodies, collecting `Stmt::Call` and
25    /// `Expr::Call` targets, including calls inside closure bodies.
26    pub fn build(stmts: &[Stmt<'_>], _interner: &Interner) -> Self {
27        let mut edges: HashMap<Symbol, HashSet<Symbol>> = HashMap::new();
28        let mut native_fns: HashSet<Symbol> = HashSet::new();
29
30        for stmt in stmts {
31            if let Stmt::FunctionDef { name, body, is_native, .. } = stmt {
32                edges.entry(*name).or_default();
33                if *is_native {
34                    native_fns.insert(*name);
35                } else {
36                    let callees = edges.entry(*name).or_default();
37                    collect_calls_from_stmts(body, callees);
38                }
39            }
40        }
41
42        let sccs = compute_sccs(&edges);
43
44        Self { edges, native_fns, sccs }
45    }
46
47    /// Returns all functions reachable from `fn_sym` via the call graph.
48    ///
49    /// Does not include `fn_sym` itself unless it is part of a cycle.
50    pub fn reachable_from(&self, fn_sym: Symbol) -> HashSet<Symbol> {
51        let mut visited = HashSet::new();
52        let mut stack = Vec::new();
53
54        if let Some(callees) = self.edges.get(&fn_sym) {
55            for &c in callees {
56                if c != fn_sym {
57                    stack.push(c);
58                }
59            }
60        }
61
62        while let Some(f) = stack.pop() {
63            if visited.insert(f) {
64                if let Some(callees) = self.edges.get(&f) {
65                    for &c in callees {
66                        if !visited.contains(&c) {
67                            stack.push(c);
68                        }
69                    }
70                }
71            }
72        }
73
74        visited
75    }
76
77    /// Returns `true` if `fn_sym` participates in a recursive cycle
78    /// (direct self-call or mutual recursion via SCC membership).
79    pub fn is_recursive(&self, fn_sym: Symbol) -> bool {
80        // Direct self-edge
81        if self.edges.get(&fn_sym).map(|s| s.contains(&fn_sym)).unwrap_or(false) {
82            return true;
83        }
84        // Mutual recursion: fn_sym is in an SCC with more than one member
85        for scc in &self.sccs {
86            if scc.len() > 1 && scc.contains(&fn_sym) {
87                return true;
88            }
89        }
90        false
91    }
92}
93
94// =============================================================================
95// Call collection from AST
96// =============================================================================
97
98/// The set of functions a block of statements calls *synchronously* (`Stmt::Call`
99/// / `Expr::Call` / closures), NOT including spawned (`LaunchTask`) targets — a
100/// spawn is a distinct concurrent thread, not a same-thread call. Used by the
101/// determinacy classifier to attribute a thread's reachable print sites.
102pub(crate) fn calls_in_stmts(stmts: &[Stmt<'_>]) -> HashSet<Symbol> {
103    let mut calls = HashSet::new();
104    collect_calls_from_stmts(stmts, &mut calls);
105    calls
106}
107
108fn collect_calls_from_stmts(stmts: &[Stmt<'_>], calls: &mut HashSet<Symbol>) {
109    for stmt in stmts {
110        collect_calls_from_stmt(stmt, calls);
111    }
112}
113
114fn collect_calls_from_stmt(stmt: &Stmt<'_>, calls: &mut HashSet<Symbol>) {
115    match stmt {
116        Stmt::Call { function, args } => {
117            calls.insert(*function);
118            for arg in args {
119                collect_calls_from_expr(arg, calls);
120            }
121        }
122        Stmt::Let { value, .. } => collect_calls_from_expr(value, calls),
123        Stmt::Set { value, .. } => collect_calls_from_expr(value, calls),
124        Stmt::Return { value: Some(v) } => collect_calls_from_expr(v, calls),
125        Stmt::If { cond, then_block, else_block } => {
126            collect_calls_from_expr(cond, calls);
127            collect_calls_from_stmts(then_block, calls);
128            if let Some(else_b) = else_block {
129                collect_calls_from_stmts(else_b, calls);
130            }
131        }
132        Stmt::While { cond, body, .. } => {
133            collect_calls_from_expr(cond, calls);
134            collect_calls_from_stmts(body, calls);
135        }
136        Stmt::Repeat { iterable, body, .. } => {
137            collect_calls_from_expr(iterable, calls);
138            collect_calls_from_stmts(body, calls);
139        }
140        Stmt::Push { value, collection } => {
141            collect_calls_from_expr(value, calls);
142            collect_calls_from_expr(collection, calls);
143        }
144        Stmt::Pop { collection, .. } => collect_calls_from_expr(collection, calls),
145        Stmt::Add { value, collection } => {
146            collect_calls_from_expr(value, calls);
147            collect_calls_from_expr(collection, calls);
148        }
149        Stmt::Remove { value, collection } => {
150            collect_calls_from_expr(value, calls);
151            collect_calls_from_expr(collection, calls);
152        }
153        Stmt::SetIndex { collection, index, value } => {
154            collect_calls_from_expr(collection, calls);
155            collect_calls_from_expr(index, calls);
156            collect_calls_from_expr(value, calls);
157        }
158        Stmt::SetField { object, value, .. } => {
159            collect_calls_from_expr(object, calls);
160            collect_calls_from_expr(value, calls);
161        }
162        Stmt::Inspect { target, arms, .. } => {
163            collect_calls_from_expr(target, calls);
164            for arm in arms {
165                collect_calls_from_stmts(arm.body, calls);
166            }
167        }
168        Stmt::Concurrent { tasks } | Stmt::Parallel { tasks } => {
169            collect_calls_from_stmts(tasks, calls);
170        }
171        Stmt::Zone { body, .. } => collect_calls_from_stmts(body, calls),
172        _ => {}
173    }
174}
175
176fn collect_calls_from_expr(expr: &Expr<'_>, calls: &mut HashSet<Symbol>) {
177    match expr {
178        Expr::Call { function, args } => {
179            calls.insert(*function);
180            for arg in args {
181                collect_calls_from_expr(arg, calls);
182            }
183        }
184        Expr::Closure { body, .. } => match body {
185            ClosureBody::Expression(e) => collect_calls_from_expr(e, calls),
186            ClosureBody::Block(stmts) => collect_calls_from_stmts(stmts, calls),
187        },
188        Expr::BinaryOp { left, right, .. } => {
189            collect_calls_from_expr(left, calls);
190            collect_calls_from_expr(right, calls);
191        }
192        Expr::Index { collection, index } => {
193            collect_calls_from_expr(collection, calls);
194            collect_calls_from_expr(index, calls);
195        }
196        Expr::Slice { collection, start, end } => {
197            collect_calls_from_expr(collection, calls);
198            collect_calls_from_expr(start, calls);
199            collect_calls_from_expr(end, calls);
200        }
201        Expr::Length { collection } => collect_calls_from_expr(collection, calls),
202        Expr::Contains { collection, value } => {
203            collect_calls_from_expr(collection, calls);
204            collect_calls_from_expr(value, calls);
205        }
206        Expr::Union { left, right } | Expr::Intersection { left, right } => {
207            collect_calls_from_expr(left, calls);
208            collect_calls_from_expr(right, calls);
209        }
210        Expr::FieldAccess { object, .. } => collect_calls_from_expr(object, calls),
211        Expr::List(items) | Expr::Tuple(items) => {
212            for item in items {
213                collect_calls_from_expr(item, calls);
214            }
215        }
216        Expr::Range { start, end } => {
217            collect_calls_from_expr(start, calls);
218            collect_calls_from_expr(end, calls);
219        }
220        Expr::Copy { expr } | Expr::Give { value: expr } => {
221            collect_calls_from_expr(expr, calls);
222        }
223        Expr::OptionSome { value } => collect_calls_from_expr(value, calls),
224        Expr::WithCapacity { value, capacity } => {
225            collect_calls_from_expr(value, calls);
226            collect_calls_from_expr(capacity, calls);
227        }
228        Expr::CallExpr { callee, args } => {
229            collect_calls_from_expr(callee, calls);
230            for arg in args {
231                collect_calls_from_expr(arg, calls);
232            }
233        }
234        _ => {}
235    }
236}
237
238// =============================================================================
239// Kosaraju's SCC algorithm
240// =============================================================================
241
242fn compute_sccs(edges: &HashMap<Symbol, HashSet<Symbol>>) -> Vec<Vec<Symbol>> {
243    let nodes: Vec<Symbol> = edges.keys().copied().collect();
244
245    // Step 1: DFS on forward graph to compute finish order
246    let mut visited: HashSet<Symbol> = HashSet::new();
247    let mut finish_order: Vec<Symbol> = Vec::new();
248
249    for &v in &nodes {
250        if !visited.contains(&v) {
251            dfs_finish(v, edges, &mut visited, &mut finish_order);
252        }
253    }
254
255    // Step 2: Build reversed graph
256    let mut rev_edges: HashMap<Symbol, HashSet<Symbol>> = HashMap::new();
257    for (&src, callees) in edges {
258        for &dst in callees {
259            rev_edges.entry(dst).or_default().insert(src);
260        }
261    }
262
263    // Step 3: DFS on reversed graph in reverse finish order to collect SCCs
264    let mut visited2: HashSet<Symbol> = HashSet::new();
265    let mut sccs: Vec<Vec<Symbol>> = Vec::new();
266
267    for &v in finish_order.iter().rev() {
268        if !visited2.contains(&v) {
269            let mut scc = Vec::new();
270            dfs_collect(v, &rev_edges, &mut visited2, &mut scc);
271            sccs.push(scc);
272        }
273    }
274
275    sccs
276}
277
278fn dfs_finish(
279    v: Symbol,
280    edges: &HashMap<Symbol, HashSet<Symbol>>,
281    visited: &mut HashSet<Symbol>,
282    finish_order: &mut Vec<Symbol>,
283) {
284    if !visited.insert(v) {
285        return;
286    }
287    if let Some(callees) = edges.get(&v) {
288        for &callee in callees {
289            dfs_finish(callee, edges, visited, finish_order);
290        }
291    }
292    finish_order.push(v);
293}
294
295fn dfs_collect(
296    v: Symbol,
297    edges: &HashMap<Symbol, HashSet<Symbol>>,
298    visited: &mut HashSet<Symbol>,
299    scc: &mut Vec<Symbol>,
300) {
301    if !visited.insert(v) {
302        return;
303    }
304    scc.push(v);
305    if let Some(callees) = edges.get(&v) {
306        for &callee in callees {
307            dfs_collect(callee, edges, visited, scc);
308        }
309    }
310}
logicaffeine_compile/analysis/callgraph.rs

logicaffeine_compile/analysis/
callgraph.rs
