aver/call_graph/
codegen.rs

1use std::collections::{HashMap, HashSet};
2
3use crate::ast::FnDef;
4
5use super::collect_codegen_deps_body;
6use super::scc::{tarjan_sccs, topo_components};
7
8/// Deterministic function emission order for codegen backends.
9///
10/// Returns SCC components in callee-before-caller topological order.
11/// Each inner vector is one SCC (single function or mutual-recursive group).
12/// Function references passed as call arguments (e.g. `List.fold(xs, init, f)`)
13/// are treated as dependencies for ordering.
14pub fn ordered_fn_components<'a>(fns: &[&'a FnDef]) -> Vec<Vec<&'a FnDef>> {
15    if fns.is_empty() {
16        return vec![];
17    }
18
19    let fn_map: HashMap<String, &FnDef> = fns.iter().map(|fd| (fd.name.clone(), *fd)).collect();
20    let names: Vec<String> = fn_map.keys().cloned().collect();
21    let name_set: HashSet<String> = names.iter().cloned().collect();
22
23    let mut graph: HashMap<String, Vec<String>> = HashMap::new();
24    for fd in fns {
25        let mut deps = HashSet::new();
26        collect_codegen_deps_body(&fd.body, &name_set, &mut deps);
27        let mut sorted = deps.into_iter().collect::<Vec<_>>();
28        sorted.sort();
29        graph.insert(fd.name.clone(), sorted);
30    }
31
32    let sccs = tarjan_sccs(&names, &graph);
33    let mut comp_of: HashMap<String, usize> = HashMap::new();
34    for (idx, comp) in sccs.iter().enumerate() {
35        for name in comp {
36            comp_of.insert(name.clone(), idx);
37        }
38    }
39
40    let mut comp_graph: HashMap<usize, HashSet<usize>> = HashMap::new();
41    for (caller, deps) in &graph {
42        let from = comp_of[caller];
43        for callee in deps {
44            let to = comp_of[callee];
45            if from != to {
46                comp_graph.entry(from).or_default().insert(to);
47            }
48        }
49    }
50
51    let comp_order = topo_components(&sccs, &comp_graph);
52    comp_order
53        .into_iter()
54        .map(|idx| {
55            let mut group: Vec<&FnDef> = sccs[idx]
56                .iter()
57                .filter_map(|name| fn_map.get(name).copied())
58                .collect();
59            group.sort_by(|a, b| a.name.cmp(&b.name));
60            group
61        })
62        .collect()
63}
aver/call_graph/codegen.rs

aver/call_graph/
codegen.rs
