ricecoder_orchestration/analyzers/
dependency_graph.rs

1//! Dependency graph construction and maintenance
2
3use crate::error::{OrchestrationError, Result};
4use crate::models::{Project, ProjectDependency};
5use std::collections::{HashMap, HashSet, VecDeque};
6
7/// Represents a directed graph of project dependencies
8#[derive(Debug, Clone)]
9pub struct DependencyGraph {
10    /// Adjacency list representation of the graph
11    adjacency_list: HashMap<String, Vec<String>>,
12
13    /// Reverse adjacency list (for upstream queries)
14    reverse_adjacency_list: HashMap<String, Vec<String>>,
15
16    /// All projects in the graph
17    projects: HashMap<String, Project>,
18
19    /// All dependencies in the graph
20    dependencies: HashMap<(String, String), ProjectDependency>,
21
22    /// Whether cycles are allowed
23    allow_cycles: bool,
24}
25
26impl DependencyGraph {
27    /// Creates a new dependency graph
28    pub fn new(allow_cycles: bool) -> Self {
29        Self {
30            adjacency_list: HashMap::new(),
31            reverse_adjacency_list: HashMap::new(),
32            projects: HashMap::new(),
33            dependencies: HashMap::new(),
34            allow_cycles,
35        }
36    }
37
38    /// Adds a project to the graph
39    pub fn add_project(&mut self, project: Project) -> Result<()> {
40        let name = project.name.clone();
41        self.projects.insert(name.clone(), project);
42        self.adjacency_list.entry(name.clone()).or_default();
43        self.reverse_adjacency_list.entry(name).or_default();
44        Ok(())
45    }
46
47    /// Adds a dependency to the graph
48    pub fn add_dependency(&mut self, dependency: ProjectDependency) -> Result<()> {
49        // Validate that both projects exist
50        if !self.projects.contains_key(&dependency.from) {
51            return Err(OrchestrationError::ProjectNotFound(dependency.from.clone()));
52        }
53        if !self.projects.contains_key(&dependency.to) {
54            return Err(OrchestrationError::ProjectNotFound(dependency.to.clone()));
55        }
56
57        // Check for cycles if not allowed
58        if !self.allow_cycles && self.would_create_cycle(&dependency.from, &dependency.to) {
59            return Err(OrchestrationError::CircularDependency(format!(
60                "Adding dependency from {} to {} would create a cycle",
61                dependency.from, dependency.to
62            )));
63        }
64
65        // Add to adjacency lists
66        self.adjacency_list
67            .entry(dependency.from.clone())
68            .or_default()
69            .push(dependency.to.clone());
70
71        self.reverse_adjacency_list
72            .entry(dependency.to.clone())
73            .or_default()
74            .push(dependency.from.clone());
75
76        // Store the dependency
77        self.dependencies
78            .insert((dependency.from.clone(), dependency.to.clone()), dependency);
79
80        Ok(())
81    }
82
83    /// Removes a dependency from the graph
84    pub fn remove_dependency(&mut self, from: &str, to: &str) -> Result<()> {
85        // Remove from adjacency list
86        if let Some(deps) = self.adjacency_list.get_mut(from) {
87            deps.retain(|d| d != to);
88        }
89
90        // Remove from reverse adjacency list
91        if let Some(deps) = self.reverse_adjacency_list.get_mut(to) {
92            deps.retain(|d| d != from);
93        }
94
95        // Remove from dependencies
96        self.dependencies.remove(&(from.to_string(), to.to_string()));
97
98        Ok(())
99    }
100
101    /// Checks if adding a dependency would create a cycle
102    fn would_create_cycle(&self, from: &str, to: &str) -> bool {
103        // If 'to' can reach 'from', then adding from->to would create a cycle
104        self.can_reach(to, from)
105    }
106
107    /// Checks if one project can reach another through the dependency graph
108    pub fn can_reach(&self, from: &str, to: &str) -> bool {
109        if from == to {
110            return true;
111        }
112
113        let mut visited = HashSet::new();
114        let mut queue = VecDeque::new();
115        queue.push_back(from.to_string());
116
117        while let Some(current) = queue.pop_front() {
118            if visited.contains(&current) {
119                continue;
120            }
121            visited.insert(current.clone());
122
123            if let Some(neighbors) = self.adjacency_list.get(&current) {
124                for neighbor in neighbors {
125                    if neighbor == to {
126                        return true;
127                    }
128                    if !visited.contains(neighbor) {
129                        queue.push_back(neighbor.clone());
130                    }
131                }
132            }
133        }
134
135        false
136    }
137
138    /// Gets all direct dependencies of a project
139    pub fn get_dependencies(&self, project: &str) -> Vec<String> {
140        self.adjacency_list
141            .get(project)
142            .cloned()
143            .unwrap_or_default()
144    }
145
146    /// Gets all projects that depend on a given project
147    pub fn get_dependents(&self, project: &str) -> Vec<String> {
148        self.reverse_adjacency_list
149            .get(project)
150            .cloned()
151            .unwrap_or_default()
152    }
153
154    /// Gets all transitive dependencies of a project
155    pub fn get_transitive_dependencies(&self, project: &str) -> Vec<String> {
156        let mut transitive = Vec::new();
157        let mut visited = HashSet::new();
158        let mut queue = VecDeque::new();
159
160        if let Some(direct_deps) = self.adjacency_list.get(project) {
161            for dep in direct_deps {
162                queue.push_back(dep.clone());
163            }
164        }
165
166        while let Some(current) = queue.pop_front() {
167            if visited.contains(&current) {
168                continue;
169            }
170            visited.insert(current.clone());
171            transitive.push(current.clone());
172
173            if let Some(deps) = self.adjacency_list.get(&current) {
174                for dep in deps {
175                    if !visited.contains(dep) {
176                        queue.push_back(dep.clone());
177                    }
178                }
179            }
180        }
181
182        transitive
183    }
184
185    /// Validates the graph consistency
186    pub fn validate(&self) -> Result<()> {
187        // Check that all dependencies reference existing projects
188        for (from, to) in self.dependencies.keys() {
189            if !self.projects.contains_key(from) {
190                return Err(OrchestrationError::DependencyValidationFailed(format!(
191                    "Project '{}' not found",
192                    from
193                )));
194            }
195            if !self.projects.contains_key(to) {
196                return Err(OrchestrationError::DependencyValidationFailed(format!(
197                    "Project '{}' not found",
198                    to
199                )));
200            }
201        }
202
203        // Check for cycles if not allowed
204        if !self.allow_cycles {
205            self.detect_cycles()?;
206        }
207
208        Ok(())
209    }
210
211    /// Detects cycles in the graph
212    pub fn detect_cycles(&self) -> Result<()> {
213        let mut visited = HashSet::new();
214        let mut rec_stack = HashSet::new();
215
216        for project_name in self.projects.keys() {
217            if !visited.contains(project_name) {
218                self.dfs_cycle_detection(project_name, &mut visited, &mut rec_stack)?;
219            }
220        }
221
222        Ok(())
223    }
224
225    /// DFS helper for cycle detection
226    fn dfs_cycle_detection(
227        &self,
228        node: &str,
229        visited: &mut HashSet<String>,
230        rec_stack: &mut HashSet<String>,
231    ) -> Result<()> {
232        visited.insert(node.to_string());
233        rec_stack.insert(node.to_string());
234
235        if let Some(neighbors) = self.adjacency_list.get(node) {
236            for neighbor in neighbors {
237                if !visited.contains(neighbor) {
238                    self.dfs_cycle_detection(neighbor, visited, rec_stack)?;
239                } else if rec_stack.contains(neighbor) {
240                    return Err(OrchestrationError::CircularDependency(format!(
241                        "Cycle detected: {} -> {}",
242                        node, neighbor
243                    )));
244                }
245            }
246        }
247
248        rec_stack.remove(node);
249        Ok(())
250    }
251
252    /// Gets the topological order of projects
253    pub fn topological_sort(&self) -> Result<Vec<String>> {
254        let mut in_degree: HashMap<String, usize> = HashMap::new();
255
256        // Initialize in-degrees
257        for project_name in self.projects.keys() {
258            in_degree.insert(project_name.clone(), 0);
259        }
260
261        // Calculate in-degrees
262        for neighbors in self.adjacency_list.values() {
263            for neighbor in neighbors {
264                *in_degree.entry(neighbor.clone()).or_insert(0) += 1;
265            }
266        }
267
268        // Kahn's algorithm
269        let mut queue: VecDeque<String> = in_degree
270            .iter()
271            .filter(|(_, &degree)| degree == 0)
272            .map(|(name, _)| name.clone())
273            .collect();
274
275        let mut sorted = Vec::new();
276
277        while let Some(node) = queue.pop_front() {
278            sorted.push(node.clone());
279
280            if let Some(neighbors) = self.adjacency_list.get(&node) {
281                for neighbor in neighbors {
282                    let degree = in_degree.entry(neighbor.clone()).or_insert(0);
283                    *degree -= 1;
284                    if *degree == 0 {
285                        queue.push_back(neighbor.clone());
286                    }
287                }
288            }
289        }
290
291        if sorted.len() != self.projects.len() {
292            return Err(OrchestrationError::CircularDependency(
293                "Topological sort failed: circular dependencies detected".to_string(),
294            ));
295        }
296
297        Ok(sorted)
298    }
299
300    /// Gets all projects in the graph
301    pub fn get_projects(&self) -> Vec<Project> {
302        self.projects.values().cloned().collect()
303    }
304
305    /// Gets all dependencies in the graph
306    pub fn get_all_dependencies(&self) -> Vec<ProjectDependency> {
307        self.dependencies.values().cloned().collect()
308    }
309
310    /// Gets the number of projects
311    pub fn project_count(&self) -> usize {
312        self.projects.len()
313    }
314
315    /// Gets the number of dependencies
316    pub fn dependency_count(&self) -> usize {
317        self.dependencies.len()
318    }
319
320    /// Checks if a project exists in the graph
321    pub fn has_project(&self, name: &str) -> bool {
322        self.projects.contains_key(name)
323    }
324
325    /// Checks if a dependency exists in the graph
326    pub fn has_dependency(&self, from: &str, to: &str) -> bool {
327        self.dependencies.contains_key(&(from.to_string(), to.to_string()))
328    }
329
330    /// Gets the adjacency list representation
331    pub fn get_adjacency_list(&self) -> HashMap<String, Vec<String>> {
332        self.adjacency_list.clone()
333    }
334
335    /// Gets the reverse adjacency list representation
336    pub fn get_reverse_adjacency_list(&self) -> HashMap<String, Vec<String>> {
337        self.reverse_adjacency_list.clone()
338    }
339
340    /// Clears the graph
341    pub fn clear(&mut self) {
342        self.adjacency_list.clear();
343        self.reverse_adjacency_list.clear();
344        self.projects.clear();
345        self.dependencies.clear();
346    }
347}
348
349impl Default for DependencyGraph {
350    fn default() -> Self {
351        Self::new(false)
352    }
353}
354
355#[cfg(test)]
356mod tests {
357    use super::*;
358    use crate::models::{ProjectStatus, DependencyType};
359    use std::path::PathBuf;
360
361    fn create_test_project(name: &str) -> Project {
362        Project {
363            path: PathBuf::from(format!("/path/to/{}", name)),
364            name: name.to_string(),
365            project_type: "rust".to_string(),
366            version: "0.1.0".to_string(),
367            status: ProjectStatus::Healthy,
368        }
369    }
370
371    #[test]
372    fn test_create_graph() {
373        let graph = DependencyGraph::new(false);
374        assert_eq!(graph.project_count(), 0);
375        assert_eq!(graph.dependency_count(), 0);
376    }
377
378    #[test]
379    fn test_add_project() {
380        let mut graph = DependencyGraph::new(false);
381        let project = create_test_project("project-a");
382
383        graph.add_project(project).unwrap();
384
385        assert_eq!(graph.project_count(), 1);
386        assert!(graph.has_project("project-a"));
387    }
388
389    #[test]
390    fn test_add_dependency() {
391        let mut graph = DependencyGraph::new(false);
392        graph.add_project(create_test_project("project-a")).unwrap();
393        graph.add_project(create_test_project("project-b")).unwrap();
394
395        let dep = ProjectDependency {
396            from: "project-a".to_string(),
397            to: "project-b".to_string(),
398            dependency_type: DependencyType::Direct,
399            version_constraint: "^0.1.0".to_string(),
400        };
401
402        graph.add_dependency(dep).unwrap();
403
404        assert_eq!(graph.dependency_count(), 1);
405        assert!(graph.has_dependency("project-a", "project-b"));
406    }
407
408    #[test]
409    fn test_add_dependency_missing_project() {
410        let mut graph = DependencyGraph::new(false);
411        graph.add_project(create_test_project("project-a")).unwrap();
412
413        let dep = ProjectDependency {
414            from: "project-a".to_string(),
415            to: "project-b".to_string(),
416            dependency_type: DependencyType::Direct,
417            version_constraint: "^0.1.0".to_string(),
418        };
419
420        let result = graph.add_dependency(dep);
421        assert!(result.is_err());
422    }
423
424    #[test]
425    fn test_cycle_detection_prevented() {
426        let mut graph = DependencyGraph::new(false);
427        graph.add_project(create_test_project("project-a")).unwrap();
428        graph.add_project(create_test_project("project-b")).unwrap();
429
430        // Add A -> B
431        graph
432            .add_dependency(ProjectDependency {
433                from: "project-a".to_string(),
434                to: "project-b".to_string(),
435                dependency_type: DependencyType::Direct,
436                version_constraint: "^0.1.0".to_string(),
437            })
438            .unwrap();
439
440        // Try to add B -> A (would create cycle)
441        let result = graph.add_dependency(ProjectDependency {
442            from: "project-b".to_string(),
443            to: "project-a".to_string(),
444            dependency_type: DependencyType::Direct,
445            version_constraint: "^0.1.0".to_string(),
446        });
447
448        assert!(result.is_err());
449    }
450
451    #[test]
452    fn test_cycle_allowed() {
453        let mut graph = DependencyGraph::new(true);
454        graph.add_project(create_test_project("project-a")).unwrap();
455        graph.add_project(create_test_project("project-b")).unwrap();
456
457        // Add A -> B
458        graph
459            .add_dependency(ProjectDependency {
460                from: "project-a".to_string(),
461                to: "project-b".to_string(),
462                dependency_type: DependencyType::Direct,
463                version_constraint: "^0.1.0".to_string(),
464            })
465            .unwrap();
466
467        // Add B -> A (cycle allowed)
468        let result = graph.add_dependency(ProjectDependency {
469            from: "project-b".to_string(),
470            to: "project-a".to_string(),
471            dependency_type: DependencyType::Direct,
472            version_constraint: "^0.1.0".to_string(),
473        });
474
475        assert!(result.is_ok());
476    }
477
478    #[test]
479    fn test_get_dependencies() {
480        let mut graph = DependencyGraph::new(false);
481        graph.add_project(create_test_project("project-a")).unwrap();
482        graph.add_project(create_test_project("project-b")).unwrap();
483        graph.add_project(create_test_project("project-c")).unwrap();
484
485        graph
486            .add_dependency(ProjectDependency {
487                from: "project-a".to_string(),
488                to: "project-b".to_string(),
489                dependency_type: DependencyType::Direct,
490                version_constraint: "^0.1.0".to_string(),
491            })
492            .unwrap();
493
494        graph
495            .add_dependency(ProjectDependency {
496                from: "project-a".to_string(),
497                to: "project-c".to_string(),
498                dependency_type: DependencyType::Direct,
499                version_constraint: "^0.1.0".to_string(),
500            })
501            .unwrap();
502
503        let deps = graph.get_dependencies("project-a");
504        assert_eq!(deps.len(), 2);
505        assert!(deps.contains(&"project-b".to_string()));
506        assert!(deps.contains(&"project-c".to_string()));
507    }
508
509    #[test]
510    fn test_get_dependents() {
511        let mut graph = DependencyGraph::new(false);
512        graph.add_project(create_test_project("project-a")).unwrap();
513        graph.add_project(create_test_project("project-b")).unwrap();
514        graph.add_project(create_test_project("project-c")).unwrap();
515
516        graph
517            .add_dependency(ProjectDependency {
518                from: "project-a".to_string(),
519                to: "project-c".to_string(),
520                dependency_type: DependencyType::Direct,
521                version_constraint: "^0.1.0".to_string(),
522            })
523            .unwrap();
524
525        graph
526            .add_dependency(ProjectDependency {
527                from: "project-b".to_string(),
528                to: "project-c".to_string(),
529                dependency_type: DependencyType::Direct,
530                version_constraint: "^0.1.0".to_string(),
531            })
532            .unwrap();
533
534        let dependents = graph.get_dependents("project-c");
535        assert_eq!(dependents.len(), 2);
536        assert!(dependents.contains(&"project-a".to_string()));
537        assert!(dependents.contains(&"project-b".to_string()));
538    }
539
540    #[test]
541    fn test_can_reach() {
542        let mut graph = DependencyGraph::new(false);
543        graph.add_project(create_test_project("project-a")).unwrap();
544        graph.add_project(create_test_project("project-b")).unwrap();
545        graph.add_project(create_test_project("project-c")).unwrap();
546
547        graph
548            .add_dependency(ProjectDependency {
549                from: "project-a".to_string(),
550                to: "project-b".to_string(),
551                dependency_type: DependencyType::Direct,
552                version_constraint: "^0.1.0".to_string(),
553            })
554            .unwrap();
555
556        graph
557            .add_dependency(ProjectDependency {
558                from: "project-b".to_string(),
559                to: "project-c".to_string(),
560                dependency_type: DependencyType::Direct,
561                version_constraint: "^0.1.0".to_string(),
562            })
563            .unwrap();
564
565        assert!(graph.can_reach("project-a", "project-b"));
566        assert!(graph.can_reach("project-a", "project-c"));
567        assert!(graph.can_reach("project-b", "project-c"));
568        assert!(!graph.can_reach("project-c", "project-a"));
569    }
570
571    #[test]
572    fn test_topological_sort() {
573        let mut graph = DependencyGraph::new(false);
574        graph.add_project(create_test_project("project-a")).unwrap();
575        graph.add_project(create_test_project("project-b")).unwrap();
576        graph.add_project(create_test_project("project-c")).unwrap();
577
578        graph
579            .add_dependency(ProjectDependency {
580                from: "project-a".to_string(),
581                to: "project-b".to_string(),
582                dependency_type: DependencyType::Direct,
583                version_constraint: "^0.1.0".to_string(),
584            })
585            .unwrap();
586
587        graph
588            .add_dependency(ProjectDependency {
589                from: "project-b".to_string(),
590                to: "project-c".to_string(),
591                dependency_type: DependencyType::Direct,
592                version_constraint: "^0.1.0".to_string(),
593            })
594            .unwrap();
595
596        let sorted = graph.topological_sort().unwrap();
597        assert_eq!(sorted.len(), 3);
598
599        let a_idx = sorted.iter().position(|x| x == "project-a").unwrap();
600        let b_idx = sorted.iter().position(|x| x == "project-b").unwrap();
601        let c_idx = sorted.iter().position(|x| x == "project-c").unwrap();
602
603        assert!(a_idx < b_idx);
604        assert!(b_idx < c_idx);
605    }
606
607    #[test]
608    fn test_remove_dependency() {
609        let mut graph = DependencyGraph::new(false);
610        graph.add_project(create_test_project("project-a")).unwrap();
611        graph.add_project(create_test_project("project-b")).unwrap();
612
613        graph
614            .add_dependency(ProjectDependency {
615                from: "project-a".to_string(),
616                to: "project-b".to_string(),
617                dependency_type: DependencyType::Direct,
618                version_constraint: "^0.1.0".to_string(),
619            })
620            .unwrap();
621
622        assert_eq!(graph.dependency_count(), 1);
623
624        graph.remove_dependency("project-a", "project-b").unwrap();
625
626        assert_eq!(graph.dependency_count(), 0);
627        assert!(!graph.has_dependency("project-a", "project-b"));
628    }
629
630    #[test]
631    fn test_validate_success() {
632        let mut graph = DependencyGraph::new(false);
633        graph.add_project(create_test_project("project-a")).unwrap();
634        graph.add_project(create_test_project("project-b")).unwrap();
635
636        graph
637            .add_dependency(ProjectDependency {
638                from: "project-a".to_string(),
639                to: "project-b".to_string(),
640                dependency_type: DependencyType::Direct,
641                version_constraint: "^0.1.0".to_string(),
642            })
643            .unwrap();
644
645        let result = graph.validate();
646        assert!(result.is_ok());
647    }
648
649    #[test]
650    fn test_get_transitive_dependencies() {
651        let mut graph = DependencyGraph::new(false);
652        graph.add_project(create_test_project("project-a")).unwrap();
653        graph.add_project(create_test_project("project-b")).unwrap();
654        graph.add_project(create_test_project("project-c")).unwrap();
655
656        graph
657            .add_dependency(ProjectDependency {
658                from: "project-a".to_string(),
659                to: "project-b".to_string(),
660                dependency_type: DependencyType::Direct,
661                version_constraint: "^0.1.0".to_string(),
662            })
663            .unwrap();
664
665        graph
666            .add_dependency(ProjectDependency {
667                from: "project-b".to_string(),
668                to: "project-c".to_string(),
669                dependency_type: DependencyType::Direct,
670                version_constraint: "^0.1.0".to_string(),
671            })
672            .unwrap();
673
674        let transitive = graph.get_transitive_dependencies("project-a");
675        assert_eq!(transitive.len(), 2);
676        assert!(transitive.contains(&"project-b".to_string()));
677        assert!(transitive.contains(&"project-c".to_string()));
678    }
679}
ricecoder_orchestration/analyzers/dependency_graph.rs

ricecoder_orchestration/analyzers/
dependency_graph.rs
