amalgam_parser/
dependency_graph.rs

1//! Dependency graph for managing type dependencies
2
3use crate::imports::TypeReference;
4use std::collections::{HashMap, HashSet, VecDeque};
5
6/// Represents a node in the dependency graph
7#[derive(Debug, Clone, PartialEq, Eq, Hash)]
8pub struct TypeNode {
9    pub group: String,
10    pub version: String,
11    pub kind: String,
12}
13
14impl From<TypeReference> for TypeNode {
15    fn from(type_ref: TypeReference) -> Self {
16        Self {
17            group: type_ref.group,
18            version: type_ref.version,
19            kind: type_ref.kind,
20        }
21    }
22}
23
24impl TypeNode {
25    pub fn new(group: String, version: String, kind: String) -> Self {
26        Self {
27            group,
28            version,
29            kind,
30        }
31    }
32
33    pub fn full_name(&self) -> String {
34        format!("{}/{}/{}", self.group, self.version, self.kind)
35    }
36}
37
38/// Dependency graph for tracking type dependencies
39pub struct DependencyGraph {
40    /// Adjacency list: node -> set of nodes it depends on
41    dependencies: HashMap<TypeNode, HashSet<TypeNode>>,
42    /// Reverse dependencies: node -> set of nodes that depend on it
43    dependents: HashMap<TypeNode, HashSet<TypeNode>>,
44}
45
46impl Default for DependencyGraph {
47    fn default() -> Self {
48        Self::new()
49    }
50}
51
52impl DependencyGraph {
53    pub fn new() -> Self {
54        Self {
55            dependencies: HashMap::new(),
56            dependents: HashMap::new(),
57        }
58    }
59
60    /// Add a node to the graph
61    pub fn add_node(&mut self, node: TypeNode) {
62        self.dependencies.entry(node.clone()).or_default();
63        self.dependents.entry(node).or_default();
64    }
65
66    /// Add a dependency edge: `from` depends on `to`
67    pub fn add_dependency(&mut self, from: TypeNode, to: TypeNode) {
68        self.dependencies
69            .entry(from.clone())
70            .or_default()
71            .insert(to.clone());
72        self.dependents.entry(to).or_default().insert(from);
73    }
74
75    /// Get all direct dependencies of a node
76    pub fn dependencies_of(&self, node: &TypeNode) -> Option<&HashSet<TypeNode>> {
77        self.dependencies.get(node)
78    }
79
80    /// Get all nodes that depend on the given node
81    pub fn dependents_of(&self, node: &TypeNode) -> Option<&HashSet<TypeNode>> {
82        self.dependents.get(node)
83    }
84
85    /// Perform topological sort on the graph
86    /// Returns nodes in dependency order (dependencies come before dependents)
87    pub fn topological_sort(&self) -> Result<Vec<TypeNode>, CycleError> {
88        let mut result = Vec::new();
89        let mut in_degree: HashMap<TypeNode, usize> = HashMap::new();
90        let mut queue = VecDeque::new();
91
92        // Calculate in-degrees
93        for node in self.dependencies.keys() {
94            in_degree.insert(node.clone(), 0);
95        }
96
97        for deps in self.dependencies.values() {
98            for dep in deps {
99                *in_degree.entry(dep.clone()).or_insert(0) += 1;
100            }
101        }
102
103        // Find nodes with no incoming edges
104        for (node, &degree) in &in_degree {
105            if degree == 0 {
106                queue.push_back(node.clone());
107            }
108        }
109
110        // Process nodes
111        while let Some(node) = queue.pop_front() {
112            result.push(node.clone());
113
114            if let Some(deps) = self.dependencies.get(&node) {
115                for dep in deps {
116                    if let Some(degree) = in_degree.get_mut(dep) {
117                        *degree = degree.saturating_sub(1);
118                        if *degree == 0 {
119                            queue.push_back(dep.clone());
120                        }
121                    }
122                }
123            }
124        }
125
126        // Check for cycles
127        if result.len() != self.dependencies.len() {
128            return Err(CycleError::new(self.find_cycle()));
129        }
130
131        // Reverse to get dependency order
132        result.reverse();
133        Ok(result)
134    }
135
136    /// Find a cycle in the graph (if any)
137    fn find_cycle(&self) -> Vec<TypeNode> {
138        let mut visited = HashSet::new();
139        let mut rec_stack = HashSet::new();
140        let mut path = Vec::new();
141
142        for node in self.dependencies.keys() {
143            if !visited.contains(node) {
144                if let Some(cycle) =
145                    self.find_cycle_dfs(node, &mut visited, &mut rec_stack, &mut path)
146                {
147                    return cycle;
148                }
149            }
150        }
151
152        Vec::new()
153    }
154
155    fn find_cycle_dfs(
156        &self,
157        node: &TypeNode,
158        visited: &mut HashSet<TypeNode>,
159        rec_stack: &mut HashSet<TypeNode>,
160        path: &mut Vec<TypeNode>,
161    ) -> Option<Vec<TypeNode>> {
162        visited.insert(node.clone());
163        rec_stack.insert(node.clone());
164        path.push(node.clone());
165
166        if let Some(deps) = self.dependencies.get(node) {
167            for dep in deps {
168                if !visited.contains(dep) {
169                    if let Some(cycle) = self.find_cycle_dfs(dep, visited, rec_stack, path) {
170                        return Some(cycle);
171                    }
172                } else if rec_stack.contains(dep) {
173                    // Found a cycle
174                    let cycle_start = path.iter().position(|n| n == dep).unwrap();
175                    return Some(path[cycle_start..].to_vec());
176                }
177            }
178        }
179
180        rec_stack.remove(node);
181        path.pop();
182        None
183    }
184
185    /// Get all transitive dependencies of a node
186    pub fn transitive_dependencies(&self, node: &TypeNode) -> HashSet<TypeNode> {
187        let mut result = HashSet::new();
188        let mut to_visit = VecDeque::new();
189        to_visit.push_back(node.clone());
190
191        while let Some(current) = to_visit.pop_front() {
192            if let Some(deps) = self.dependencies.get(&current) {
193                for dep in deps {
194                    if result.insert(dep.clone()) {
195                        to_visit.push_back(dep.clone());
196                    }
197                }
198            }
199        }
200
201        result
202    }
203
204    /// Check if there's a path from `from` to `to`
205    pub fn has_path(&self, from: &TypeNode, to: &TypeNode) -> bool {
206        let transitive = self.transitive_dependencies(from);
207        transitive.contains(to)
208    }
209}
210
211/// Error type for cycle detection
212#[derive(Debug)]
213pub struct CycleError {
214    pub cycle: Vec<TypeNode>,
215}
216
217impl CycleError {
218    pub fn new(cycle: Vec<TypeNode>) -> Self {
219        Self { cycle }
220    }
221}
222
223impl std::fmt::Display for CycleError {
224    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
225        write!(f, "Dependency cycle detected: ")?;
226        for (i, node) in self.cycle.iter().enumerate() {
227            if i > 0 {
228                write!(f, " -> ")?;
229            }
230            write!(f, "{}", node.full_name())?;
231        }
232        Ok(())
233    }
234}
235
236impl std::error::Error for CycleError {}
237
238#[cfg(test)]
239mod tests {
240    use super::*;
241
242    #[test]
243    fn test_topological_sort() {
244        let mut graph = DependencyGraph::new();
245
246        let a = TypeNode::new("test".to_string(), "v1".to_string(), "A".to_string());
247        let b = TypeNode::new("test".to_string(), "v1".to_string(), "B".to_string());
248        let c = TypeNode::new("test".to_string(), "v1".to_string(), "C".to_string());
249
250        graph.add_node(a.clone());
251        graph.add_node(b.clone());
252        graph.add_node(c.clone());
253
254        // A depends on B, B depends on C
255        graph.add_dependency(a.clone(), b.clone());
256        graph.add_dependency(b.clone(), c.clone());
257
258        let sorted = graph.topological_sort().unwrap();
259
260        // C should come first (no dependencies), then B, then A
261        assert_eq!(sorted[0], c);
262        assert_eq!(sorted[1], b);
263        assert_eq!(sorted[2], a);
264    }
265
266    #[test]
267    fn test_cycle_detection() {
268        let mut graph = DependencyGraph::new();
269
270        let a = TypeNode::new("test".to_string(), "v1".to_string(), "A".to_string());
271        let b = TypeNode::new("test".to_string(), "v1".to_string(), "B".to_string());
272        let c = TypeNode::new("test".to_string(), "v1".to_string(), "C".to_string());
273
274        graph.add_node(a.clone());
275        graph.add_node(b.clone());
276        graph.add_node(c.clone());
277
278        // Create a cycle: A -> B -> C -> A
279        graph.add_dependency(a.clone(), b.clone());
280        graph.add_dependency(b.clone(), c.clone());
281        graph.add_dependency(c.clone(), a.clone());
282
283        let result = graph.topological_sort();
284        assert!(result.is_err());
285
286        if let Err(e) = result {
287            assert!(!e.cycle.is_empty());
288        }
289    }
290}
amalgam_parser/dependency_graph.rs

amalgam_parser/
dependency_graph.rs
