bock_build/
dep_graph.rs

1//! Module dependency graph construction.
2//!
3//! Builds a directed graph of module dependencies by inspecting import declarations
4//! in parsed AST modules. Each node is a module path, and edges represent "depends on"
5//! relationships extracted from `use` declarations.
6
7use std::collections::{HashMap, HashSet};
8
9use bock_ast::{ImportDecl, Module, ModulePath};
10
11/// A module identifier derived from its path segments (e.g., `"Std.Io.File"`).
12pub type ModuleId = String;
13
14/// Directed dependency graph where edges go from a module to its dependencies.
15#[derive(Debug, Clone, Default)]
16pub struct DepGraph {
17    /// Map from module ID to the set of module IDs it depends on.
18    edges: HashMap<ModuleId, HashSet<ModuleId>>,
19    /// Reverse edges: module ID → set of modules that depend on it.
20    reverse_edges: HashMap<ModuleId, HashSet<ModuleId>>,
21}
22
23impl DepGraph {
24    /// Creates a new empty dependency graph.
25    #[must_use]
26    pub fn new() -> Self {
27        Self::default()
28    }
29
30    /// Builds a dependency graph from a collection of parsed modules.
31    ///
32    /// Each module's import declarations are inspected to determine dependencies.
33    /// Modules without a declared path are assigned a synthetic ID based on their
34    /// index in the input slice.
35    #[must_use]
36    pub fn from_modules(modules: &[Module]) -> Self {
37        let mut graph = Self::new();
38        for (i, module) in modules.iter().enumerate() {
39            let module_id = module_id_from_module(module, i);
40            let deps = extract_dependencies(&module.imports);
41            graph.add_module_with_deps(module_id, deps);
42        }
43        graph
44    }
45
46    /// Adds a module and its dependencies to the graph.
47    pub fn add_module_with_deps(&mut self, module_id: ModuleId, deps: HashSet<ModuleId>) {
48        for dep in &deps {
49            self.reverse_edges
50                .entry(dep.clone())
51                .or_default()
52                .insert(module_id.clone());
53        }
54        self.edges.insert(module_id, deps);
55    }
56
57    /// Adds a single module with no dependencies.
58    pub fn add_module(&mut self, module_id: ModuleId) {
59        self.edges.entry(module_id).or_default();
60    }
61
62    /// Returns the direct dependencies of a module.
63    #[must_use]
64    pub fn dependencies(&self, module_id: &str) -> Option<&HashSet<ModuleId>> {
65        self.edges.get(module_id)
66    }
67
68    /// Returns the modules that directly depend on the given module (reverse deps).
69    #[must_use]
70    pub fn dependents(&self, module_id: &str) -> Option<&HashSet<ModuleId>> {
71        self.reverse_edges.get(module_id)
72    }
73
74    /// Returns all module IDs in the graph.
75    #[must_use]
76    pub fn modules(&self) -> Vec<&ModuleId> {
77        self.edges.keys().collect()
78    }
79
80    /// Returns the number of modules in the graph.
81    #[must_use]
82    pub fn module_count(&self) -> usize {
83        self.edges.len()
84    }
85
86    /// Returns true if the graph contains cycles.
87    #[must_use]
88    pub fn has_cycle(&self) -> bool {
89        let mut visited = HashSet::new();
90        let mut in_stack = HashSet::new();
91
92        for module_id in self.edges.keys() {
93            if self.dfs_cycle_check(module_id, &mut visited, &mut in_stack) {
94                return true;
95            }
96        }
97        false
98    }
99
100    /// Returns a topological ordering of modules (dependencies before dependents).
101    ///
102    /// Returns `None` if the graph contains a cycle.
103    #[must_use]
104    pub fn topological_order(&self) -> Option<Vec<ModuleId>> {
105        let mut visited = HashSet::new();
106        let mut in_stack = HashSet::new();
107        let mut order = Vec::new();
108
109        for module_id in self.edges.keys() {
110            if !self.topo_dfs(module_id, &mut visited, &mut in_stack, &mut order) {
111                return None;
112            }
113        }
114
115        // Post-order DFS with edges pointing dependent→dependency
116        // naturally produces dependencies before dependents.
117        Some(order)
118    }
119
120    fn dfs_cycle_check(
121        &self,
122        node: &str,
123        visited: &mut HashSet<String>,
124        in_stack: &mut HashSet<String>,
125    ) -> bool {
126        if in_stack.contains(node) {
127            return true;
128        }
129        if visited.contains(node) {
130            return false;
131        }
132
133        visited.insert(node.to_string());
134        in_stack.insert(node.to_string());
135
136        if let Some(deps) = self.edges.get(node) {
137            for dep in deps {
138                if self.dfs_cycle_check(dep, visited, in_stack) {
139                    return true;
140                }
141            }
142        }
143
144        in_stack.remove(node);
145        false
146    }
147
148    fn topo_dfs(
149        &self,
150        node: &str,
151        visited: &mut HashSet<String>,
152        in_stack: &mut HashSet<String>,
153        order: &mut Vec<String>,
154    ) -> bool {
155        if in_stack.contains(node) {
156            return false; // cycle
157        }
158        if visited.contains(node) {
159            return true;
160        }
161
162        visited.insert(node.to_string());
163        in_stack.insert(node.to_string());
164
165        if let Some(deps) = self.edges.get(node) {
166            for dep in deps {
167                if !self.topo_dfs(dep, visited, in_stack, order) {
168                    return false;
169                }
170            }
171        }
172
173        in_stack.remove(node);
174        order.push(node.to_string());
175        true
176    }
177}
178
179/// Extracts a module ID string from a parsed module.
180///
181/// Uses the module's declared path if available, otherwise generates a synthetic
182/// ID like `"<anonymous_0>"`.
183#[must_use]
184pub fn module_id_from_module(module: &Module, index: usize) -> ModuleId {
185    module
186        .path
187        .as_ref()
188        .map(module_path_to_id)
189        .unwrap_or_else(|| format!("<anonymous_{index}>"))
190}
191
192/// Converts a `ModulePath` to a dot-separated string ID.
193#[must_use]
194pub fn module_path_to_id(path: &ModulePath) -> ModuleId {
195    path.segments
196        .iter()
197        .map(|ident| ident.name.as_str())
198        .collect::<Vec<_>>()
199        .join(".")
200}
201
202/// Extracts dependency module IDs from a list of import declarations.
203#[must_use]
204pub fn extract_dependencies(imports: &[ImportDecl]) -> HashSet<ModuleId> {
205    imports
206        .iter()
207        .map(|import| module_path_to_id(&import.path))
208        .collect()
209}
210
211#[cfg(test)]
212mod tests {
213    use super::*;
214
215    #[test]
216    fn empty_graph() {
217        let graph = DepGraph::new();
218        assert_eq!(graph.module_count(), 0);
219        assert!(!graph.has_cycle());
220        assert_eq!(graph.topological_order(), Some(vec![]));
221    }
222
223    #[test]
224    fn single_module_no_deps() {
225        let mut graph = DepGraph::new();
226        graph.add_module("Main".to_string());
227        assert_eq!(graph.module_count(), 1);
228        assert!(graph.dependencies("Main").unwrap().is_empty());
229        assert!(!graph.has_cycle());
230    }
231
232    #[test]
233    fn linear_dependency_chain() {
234        let mut graph = DepGraph::new();
235        graph.add_module_with_deps("App".to_string(), HashSet::from(["Lib".to_string()]));
236        graph.add_module_with_deps("Lib".to_string(), HashSet::from(["Core".to_string()]));
237        graph.add_module("Core".to_string());
238
239        assert_eq!(graph.module_count(), 3);
240        assert!(!graph.has_cycle());
241
242        let order = graph.topological_order().unwrap();
243        let core_pos = order.iter().position(|m| m == "Core").unwrap();
244        let lib_pos = order.iter().position(|m| m == "Lib").unwrap();
245        let app_pos = order.iter().position(|m| m == "App").unwrap();
246        assert!(core_pos < lib_pos);
247        assert!(lib_pos < app_pos);
248    }
249
250    #[test]
251    fn cycle_detection() {
252        let mut graph = DepGraph::new();
253        graph.add_module_with_deps("A".to_string(), HashSet::from(["B".to_string()]));
254        graph.add_module_with_deps("B".to_string(), HashSet::from(["A".to_string()]));
255
256        assert!(graph.has_cycle());
257        assert!(graph.topological_order().is_none());
258    }
259
260    #[test]
261    fn reverse_dependencies() {
262        let mut graph = DepGraph::new();
263        graph.add_module_with_deps("App".to_string(), HashSet::from(["Lib".to_string()]));
264        graph.add_module_with_deps("Tests".to_string(), HashSet::from(["Lib".to_string()]));
265        graph.add_module("Lib".to_string());
266
267        let dependents = graph.dependents("Lib").unwrap();
268        assert!(dependents.contains("App"));
269        assert!(dependents.contains("Tests"));
270        assert_eq!(dependents.len(), 2);
271    }
272
273    #[test]
274    fn diamond_dependency() {
275        let mut graph = DepGraph::new();
276        graph.add_module_with_deps(
277            "App".to_string(),
278            HashSet::from(["Left".to_string(), "Right".to_string()]),
279        );
280        graph.add_module_with_deps("Left".to_string(), HashSet::from(["Base".to_string()]));
281        graph.add_module_with_deps("Right".to_string(), HashSet::from(["Base".to_string()]));
282        graph.add_module("Base".to_string());
283
284        assert!(!graph.has_cycle());
285        let order = graph.topological_order().unwrap();
286        let base_pos = order.iter().position(|m| m == "Base").unwrap();
287        let app_pos = order.iter().position(|m| m == "App").unwrap();
288        assert!(base_pos < app_pos);
289    }
290}
bock_build/dep_graph.rs

bock_build/
dep_graph.rs
