ricecoder_orchestration/analyzers/
dependency_analyzer.rs

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

ricecoder_orchestration/analyzers/
dependency_analyzer.rs
