sklears_core/trait_explorer/
dependency_analysis.rs

1//! # Dependency Analysis Module
2//!
3//! This module provides comprehensive trait dependency analysis capabilities for the trait explorer.
4//! It offers advanced algorithms for analyzing dependencies, detecting circular dependencies,
5//! calculating dependency depth, and assessing the impact and risk of dependencies.
6//!
7//! ## Features
8//!
9//! - **Dependency Graph Construction**: Build proper dependency graphs with cycle detection
10//! - **Transitive Dependency Analysis**: Calculate all transitive dependencies using BFS/DFS
11//! - **Circular Dependency Detection**: Implement Tarjan's strongly connected components algorithm
12//! - **Dependency Impact Analysis**: Assess compilation and runtime impact of dependencies
13//! - **Risk Assessment**: Identify dependency risks and vulnerabilities
14//! - **Performance Analysis**: Analyze performance implications of dependencies
15//! - **Optimization Suggestions**: Suggest dependency optimizations
16//!
17//! ## Examples
18//!
19//! ```rust,ignore
20//! use sklears_core::trait_explorer::dependency_analysis::{DependencyAnalyzer, DependencyGraph};
21//! use sklears_core::api_reference_generator::TraitInfo;
22//!
23//! let analyzer = DependencyAnalyzer::new();
24//! let trait_info = TraitInfo {
25//!     name: "MyTrait".to_string(),
26//!     description: "Example trait".to_string(),
27//!     path: "example::MyTrait".to_string(),
28//!     generics: Vec::new(),
29//!     associated_types: Vec::new(),
30//!     methods: Vec::new(),
31//!     supertraits: vec!["SuperTrait".to_string()],
32//!     implementations: Vec::new(),
33//! };
34//!
35//! let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
36//! println!("Direct dependencies: {:?}", analysis.direct_dependencies);
37//! println!("Dependency depth: {}", analysis.dependency_depth);
38//! ```
39
40use crate::api_data_structures::TraitInfo;
41use crate::error::Result;
42
43use serde::{Deserialize, Serialize};
44use std::collections::{HashMap, HashSet, VecDeque};
45use std::fmt;
46
47// SciRS2 dependencies for advanced functionality
48use scirs2_core::ndarray::Array1;
49
50/// Comprehensive analyzer for trait dependencies with advanced algorithms
51///
52/// The `DependencyAnalyzer` provides sophisticated dependency analysis capabilities
53/// including cycle detection, impact assessment, and performance analysis.
54///
55/// # Examples
56///
57/// ```rust,ignore
58/// let analyzer = DependencyAnalyzer::new();
59/// let analysis = analyzer.analyze_dependencies(&trait_info)?;
60///
61/// // Check for circular dependencies
62/// if !analysis.circular_dependencies.is_empty() {
63///     println!("Warning: Circular dependencies detected!");
64/// }
65///
66/// // Assess dependency risk
67/// let risk_assessment = analyzer.assess_dependency_risk(&analysis);
68/// println!("Dependency risk level: {:?}", risk_assessment.risk_level);
69/// ```
70#[derive(Debug, Clone)]
71pub struct DependencyAnalyzer {
72    /// Maximum depth to traverse when analyzing dependencies
73    max_depth: usize,
74    /// Cache for dependency analysis results
75    analysis_cache: HashMap<String, DependencyAnalysis>,
76    /// Performance tracking enabled
77    performance_tracking: bool,
78    /// Risk assessment configuration
79    risk_config: RiskAssessmentConfig,
80}
81
82/// Configuration for risk assessment algorithms
83#[derive(Debug, Clone)]
84pub struct RiskAssessmentConfig {
85    /// Maximum acceptable dependency depth
86    pub max_safe_depth: usize,
87    /// Maximum number of direct dependencies before flagging
88    pub max_direct_dependencies: usize,
89    /// Weight for complexity scoring
90    pub complexity_weight: f64,
91    /// Weight for coupling scoring
92    pub coupling_weight: f64,
93}
94
95impl Default for RiskAssessmentConfig {
96    fn default() -> Self {
97        Self {
98            max_safe_depth: 10,
99            max_direct_dependencies: 15,
100            complexity_weight: 0.4,
101            coupling_weight: 0.6,
102        }
103    }
104}
105
106/// Comprehensive analysis of trait dependencies
107///
108/// This structure contains the complete results of dependency analysis,
109/// including transitive dependencies, circular dependencies, and risk assessments.
110#[derive(Debug, Clone, Default, Serialize, Deserialize)]
111pub struct DependencyAnalysis {
112    /// Direct dependencies (supertraits, bounds)
113    pub direct_dependencies: Vec<String>,
114    /// All transitive dependencies
115    pub transitive_dependencies: Vec<String>,
116    /// Maximum depth of dependency chain
117    pub dependency_depth: usize,
118    /// Circular dependency cycles detected
119    pub circular_dependencies: Vec<Vec<String>>,
120    /// Dependency graph representation
121    pub dependency_graph: DependencyGraph,
122    /// Impact analysis results
123    pub impact_analysis: ImpactAnalysis,
124    /// Risk assessment results
125    pub risk_assessment: RiskAssessment,
126    /// Performance implications
127    pub performance_analysis: PerformanceAnalysis,
128    /// Optimization suggestions
129    pub optimization_suggestions: Vec<OptimizationSuggestion>,
130}
131
132/// Graph representation of trait dependencies
133#[derive(Debug, Clone, Default, Serialize, Deserialize)]
134pub struct DependencyGraph {
135    /// Adjacency list representation of the dependency graph
136    pub adjacency_list: HashMap<String, Vec<String>>,
137    /// Reverse dependency mapping (dependents of each trait)
138    pub reverse_dependencies: HashMap<String, Vec<String>>,
139    /// Strongly connected components (for cycle detection)
140    pub strongly_connected_components: Vec<Vec<String>>,
141    /// Topologically sorted order (if no cycles)
142    pub topological_order: Option<Vec<String>>,
143}
144
145/// Analysis of dependency impact on compilation and runtime
146#[derive(Debug, Clone, Default, Serialize, Deserialize)]
147pub struct ImpactAnalysis {
148    /// Estimated compilation time impact (normalized 0-1)
149    pub compilation_impact: f64,
150    /// Estimated binary size impact (normalized 0-1)
151    pub binary_size_impact: f64,
152    /// Runtime performance impact (normalized 0-1)
153    pub runtime_impact: f64,
154    /// Maintenance burden score (normalized 0-1)
155    pub maintenance_burden: f64,
156    /// Coupling strength with other components
157    pub coupling_strength: f64,
158}
159
160/// Risk assessment for dependency configuration
161#[derive(Debug, Clone, Default, Serialize, Deserialize)]
162pub struct RiskAssessment {
163    /// Overall risk level
164    pub risk_level: RiskLevel,
165    /// Risk score (0-100)
166    pub risk_score: f64,
167    /// Identified risk factors
168    pub risk_factors: Vec<RiskFactor>,
169    /// Mitigation recommendations
170    pub mitigation_recommendations: Vec<String>,
171}
172
173/// Risk levels for dependency analysis
174#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, Default)]
175pub enum RiskLevel {
176    /// Low risk - minimal impact expected
177    #[default]
178    Low,
179    /// Medium risk - some potential issues
180    Medium,
181    /// High risk - significant concerns
182    High,
183    /// Critical risk - immediate attention required
184    Critical,
185}
186
187impl fmt::Display for RiskLevel {
188    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
189        match self {
190            RiskLevel::Low => write!(f, "Low"),
191            RiskLevel::Medium => write!(f, "Medium"),
192            RiskLevel::High => write!(f, "High"),
193            RiskLevel::Critical => write!(f, "Critical"),
194        }
195    }
196}
197
198/// Specific risk factors identified in dependency analysis
199#[derive(Debug, Clone, Serialize, Deserialize)]
200pub struct RiskFactor {
201    /// Type of risk factor
202    pub factor_type: RiskFactorType,
203    /// Description of the risk
204    pub description: String,
205    /// Severity of this specific risk (0-10)
206    pub severity: f64,
207    /// Affected components
208    pub affected_components: Vec<String>,
209}
210
211/// Types of risk factors that can be identified
212#[derive(Debug, Clone, Serialize, Deserialize)]
213pub enum RiskFactorType {
214    /// Circular dependencies detected
215    CircularDependency,
216    /// Excessive dependency depth
217    ExcessiveDepth,
218    /// Too many direct dependencies
219    HighFanOut,
220    /// Complex dependency relationships
221    ComplexRelationships,
222    /// Performance bottleneck potential
223    PerformanceBottleneck,
224    /// Maintenance burden
225    MaintenanceBurden,
226    /// Breaking change sensitivity
227    BreakingChangeSensitivity,
228}
229
230/// Performance analysis of dependency configuration
231#[derive(Debug, Clone, Default, Serialize, Deserialize)]
232pub struct PerformanceAnalysis {
233    /// Estimated compilation time (milliseconds)
234    pub estimated_compile_time: f64,
235    /// Memory usage during compilation (MB)
236    pub compile_memory_usage: f64,
237    /// Runtime memory overhead (bytes)
238    pub runtime_memory_overhead: f64,
239    /// CPU overhead percentage
240    pub cpu_overhead_percentage: f64,
241    /// Cache efficiency impact (0-1)
242    pub cache_efficiency_impact: f64,
243}
244
245/// Optimization suggestions for improving dependency configuration
246#[derive(Debug, Clone, Serialize, Deserialize)]
247pub struct OptimizationSuggestion {
248    /// Type of optimization
249    pub suggestion_type: OptimizationType,
250    /// Description of the suggestion
251    pub description: String,
252    /// Expected benefit (0-10)
253    pub expected_benefit: f64,
254    /// Implementation difficulty (0-10)
255    pub implementation_difficulty: f64,
256    /// Priority level
257    pub priority: Priority,
258    /// Specific implementation steps
259    pub implementation_steps: Vec<String>,
260}
261
262/// Types of optimizations that can be suggested
263#[derive(Debug, Clone, Serialize, Deserialize)]
264pub enum OptimizationType {
265    /// Reduce dependency depth
266    ReduceDepth,
267    /// Break circular dependencies
268    BreakCycles,
269    /// Consolidate similar dependencies
270    ConsolidateDependencies,
271    /// Split monolithic traits
272    SplitTraits,
273    /// Use composition over inheritance
274    PreferComposition,
275    /// Add caching layer
276    AddCaching,
277    /// Lazy loading implementation
278    LazyLoading,
279    /// Performance optimization
280    PerformanceOptimization,
281}
282
283/// Priority levels for optimization suggestions
284#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
285pub enum Priority {
286    /// Low priority - nice to have
287    Low,
288    /// Medium priority - should consider
289    Medium,
290    /// High priority - should implement soon
291    High,
292    /// Critical priority - implement immediately
293    Critical,
294}
295
296impl DependencyAnalyzer {
297    /// Create a new dependency analyzer with default configuration
298    ///
299    /// # Examples
300    ///
301    /// ```rust,ignore
302    /// let analyzer = DependencyAnalyzer::new();
303    /// ```
304    pub fn new() -> Self {
305        Self {
306            max_depth: 50,
307            analysis_cache: HashMap::new(),
308            performance_tracking: true,
309            risk_config: RiskAssessmentConfig::default(),
310        }
311    }
312
313    /// Create a new dependency analyzer with custom configuration
314    ///
315    /// # Arguments
316    ///
317    /// * `max_depth` - Maximum depth to traverse when analyzing dependencies
318    /// * `performance_tracking` - Whether to enable performance tracking
319    /// * `risk_config` - Configuration for risk assessment
320    ///
321    /// # Examples
322    ///
323    /// ```rust,ignore
324    /// let config = RiskAssessmentConfig {
325    ///     max_safe_depth: 8,
326    ///     max_direct_dependencies: 10,
327    ///     complexity_weight: 0.5,
328    ///     coupling_weight: 0.5,
329    /// };
330    /// let analyzer = DependencyAnalyzer::with_config(30, true, config);
331    /// ```
332    pub fn with_config(
333        max_depth: usize,
334        performance_tracking: bool,
335        risk_config: RiskAssessmentConfig,
336    ) -> Self {
337        Self {
338            max_depth,
339            analysis_cache: HashMap::new(),
340            performance_tracking,
341            risk_config,
342        }
343    }
344
345    /// Analyze dependencies for a given trait with comprehensive analysis
346    ///
347    /// This method performs a complete dependency analysis including:
348    /// - Direct and transitive dependency calculation
349    /// - Circular dependency detection using Tarjan's algorithm
350    /// - Dependency depth calculation
351    /// - Impact analysis
352    /// - Risk assessment
353    /// - Performance analysis
354    /// - Optimization suggestions
355    ///
356    /// # Arguments
357    ///
358    /// * `trait_info` - Information about the trait to analyze
359    ///
360    /// # Returns
361    ///
362    /// A comprehensive `DependencyAnalysis` result containing all analysis data
363    ///
364    /// # Examples
365    ///
366    /// ```rust,ignore
367    /// let analysis = analyzer.analyze_dependencies(&trait_info)?;
368    /// println!("Found {} direct dependencies", analysis.direct_dependencies.len());
369    /// println!("Dependency depth: {}", analysis.dependency_depth);
370    /// ```
371    pub fn analyze_dependencies(&self, trait_info: &TraitInfo) -> Result<DependencyAnalysis> {
372        // Check cache first
373        if let Some(cached_analysis) = self.analysis_cache.get(&trait_info.name) {
374            return Ok(cached_analysis.clone());
375        }
376
377        let start_time = if self.performance_tracking {
378            Some(std::time::Instant::now())
379        } else {
380            None
381        };
382
383        // Extract direct dependencies
384        let mut direct_deps = trait_info.supertraits.clone();
385
386        // Add dependencies from associated types
387        for assoc_type in &trait_info.associated_types {
388            direct_deps.extend_from_slice(&assoc_type.bounds);
389        }
390
391        // Build dependency graph
392        let dependency_graph = self.build_dependency_graph(&direct_deps, trait_info)?;
393
394        // Calculate transitive dependencies using enhanced BFS
395        let transitive_deps = self.calculate_transitive_dependencies(&dependency_graph)?;
396
397        // Calculate dependency depth using DFS
398        let dependency_depth =
399            self.calculate_dependency_depth_enhanced(&dependency_graph, &trait_info.name)?;
400
401        // Detect circular dependencies using Tarjan's algorithm
402        let circular_dependencies = self.detect_circular_dependencies_tarjan(&dependency_graph)?;
403
404        // Perform impact analysis
405        let impact_analysis =
406            self.analyze_impact(&dependency_graph, &direct_deps, &transitive_deps)?;
407
408        // Assess risk
409        let risk_assessment = self.assess_risk(
410            &dependency_graph,
411            &direct_deps,
412            &transitive_deps,
413            &circular_dependencies,
414        )?;
415
416        // Analyze performance implications
417        let performance_analysis = self.analyze_performance(&dependency_graph, &impact_analysis)?;
418
419        // Generate optimization suggestions
420        let optimization_suggestions = self.generate_optimization_suggestions(
421            &dependency_graph,
422            &risk_assessment,
423            &performance_analysis,
424        )?;
425
426        let analysis = DependencyAnalysis {
427            direct_dependencies: direct_deps,
428            transitive_dependencies: transitive_deps,
429            dependency_depth,
430            circular_dependencies,
431            dependency_graph,
432            impact_analysis,
433            risk_assessment,
434            performance_analysis,
435            optimization_suggestions,
436        };
437
438        if let Some(start) = start_time {
439            let duration = start.elapsed();
440            log::debug!("Dependency analysis completed in {:?}", duration);
441        }
442
443        Ok(analysis)
444    }
445
446    /// Build a comprehensive dependency graph using advanced graph algorithms
447    ///
448    /// This method constructs both forward and reverse dependency mappings,
449    /// calculates strongly connected components, and attempts topological sorting.
450    fn build_dependency_graph(
451        &self,
452        direct_deps: &[String],
453        trait_info: &TraitInfo,
454    ) -> Result<DependencyGraph> {
455        let mut adjacency_list = HashMap::new();
456        let mut reverse_dependencies = HashMap::new();
457
458        // Initialize with the current trait
459        adjacency_list.insert(trait_info.name.clone(), direct_deps.to_vec());
460
461        // Build reverse dependencies
462        for dep in direct_deps {
463            reverse_dependencies
464                .entry(dep.clone())
465                .or_insert_with(Vec::new)
466                .push(trait_info.name.clone());
467        }
468
469        // In a real implementation, we would recursively build the complete graph
470        // For now, we'll create a simplified version
471
472        // Calculate strongly connected components using Tarjan's algorithm
473        let strongly_connected_components = self.tarjan_scc(&adjacency_list)?;
474
475        // Attempt topological sorting
476        let topological_order = self.topological_sort(&adjacency_list)?;
477
478        Ok(DependencyGraph {
479            adjacency_list,
480            reverse_dependencies,
481            strongly_connected_components,
482            topological_order,
483        })
484    }
485
486    /// Calculate transitive dependencies using enhanced BFS with cycle detection
487    fn calculate_transitive_dependencies(&self, graph: &DependencyGraph) -> Result<Vec<String>> {
488        let mut all_deps = HashSet::new();
489        let mut visited = HashSet::new();
490        let mut queue = VecDeque::new();
491
492        // Initialize queue with all direct dependencies
493        for deps in graph.adjacency_list.values() {
494            for dep in deps {
495                if !visited.contains(dep) {
496                    queue.push_back((dep.clone(), 0)); // (dependency, depth)
497                }
498            }
499        }
500
501        while let Some((dep, depth)) = queue.pop_front() {
502            if depth >= self.max_depth {
503                log::warn!("Maximum dependency depth reached for {}", dep);
504                continue;
505            }
506
507            if visited.contains(&dep) {
508                continue;
509            }
510
511            visited.insert(dep.clone());
512            all_deps.insert(dep.clone());
513
514            // Add dependencies of this dependency (if we had full graph data)
515            if let Some(subdeps) = graph.adjacency_list.get(&dep) {
516                for subdep in subdeps {
517                    if !visited.contains(subdep) {
518                        queue.push_back((subdep.clone(), depth + 1));
519                    }
520                }
521            }
522        }
523
524        Ok(all_deps.into_iter().collect())
525    }
526
527    /// Calculate dependency depth using enhanced DFS with memoization
528    fn calculate_dependency_depth_enhanced(
529        &self,
530        graph: &DependencyGraph,
531        start_node: &str,
532    ) -> Result<usize> {
533        let mut memo = HashMap::new();
534        self.dfs_depth(graph, start_node, &mut memo, &mut HashSet::new())
535    }
536
537    /// Recursive DFS helper for depth calculation with cycle detection
538    #[allow(clippy::only_used_in_recursion)]
539    fn dfs_depth(
540        &self,
541        graph: &DependencyGraph,
542        node: &str,
543        memo: &mut HashMap<String, usize>,
544        visiting: &mut HashSet<String>,
545    ) -> Result<usize> {
546        if let Some(&cached_depth) = memo.get(node) {
547            return Ok(cached_depth);
548        }
549
550        if visiting.contains(node) {
551            // Cycle detected - return large depth to indicate problem
552            return Ok(1000);
553        }
554
555        visiting.insert(node.to_string());
556
557        let mut max_depth = 0;
558        if let Some(deps) = graph.adjacency_list.get(node) {
559            for dep in deps {
560                let dep_depth = self.dfs_depth(graph, dep, memo, visiting)?;
561                max_depth = max_depth.max(dep_depth);
562            }
563        }
564
565        visiting.remove(node);
566        let final_depth = max_depth + 1;
567        memo.insert(node.to_string(), final_depth);
568
569        Ok(final_depth)
570    }
571
572    /// Detect circular dependencies using Tarjan's strongly connected components algorithm
573    fn detect_circular_dependencies_tarjan(
574        &self,
575        graph: &DependencyGraph,
576    ) -> Result<Vec<Vec<String>>> {
577        let sccs = &graph.strongly_connected_components;
578
579        // Filter SCCs that have more than one node (indicating cycles)
580        let cycles: Vec<Vec<String>> = sccs.iter().filter(|scc| scc.len() > 1).cloned().collect();
581
582        Ok(cycles)
583    }
584
585    /// Tarjan's algorithm for finding strongly connected components
586    fn tarjan_scc(
587        &self,
588        adjacency_list: &HashMap<String, Vec<String>>,
589    ) -> Result<Vec<Vec<String>>> {
590        let mut index = 0;
591        let mut stack = Vec::new();
592        let mut indices = HashMap::new();
593        let mut lowlinks = HashMap::new();
594        let mut on_stack = HashSet::new();
595        let mut sccs = Vec::new();
596
597        for node in adjacency_list.keys() {
598            if !indices.contains_key(node) {
599                self.tarjan_strongconnect(
600                    node,
601                    adjacency_list,
602                    &mut index,
603                    &mut stack,
604                    &mut indices,
605                    &mut lowlinks,
606                    &mut on_stack,
607                    &mut sccs,
608                )?;
609            }
610        }
611
612        Ok(sccs)
613    }
614
615    /// Helper function for Tarjan's algorithm
616    #[allow(
617        clippy::only_used_in_recursion,
618        clippy::too_many_arguments,
619        clippy::while_let_loop
620    )]
621    fn tarjan_strongconnect(
622        &self,
623        v: &str,
624        adjacency_list: &HashMap<String, Vec<String>>,
625        index: &mut usize,
626        stack: &mut Vec<String>,
627        indices: &mut HashMap<String, usize>,
628        lowlinks: &mut HashMap<String, usize>,
629        on_stack: &mut HashSet<String>,
630        sccs: &mut Vec<Vec<String>>,
631    ) -> Result<()> {
632        indices.insert(v.to_string(), *index);
633        lowlinks.insert(v.to_string(), *index);
634        *index += 1;
635        stack.push(v.to_string());
636        on_stack.insert(v.to_string());
637
638        if let Some(neighbors) = adjacency_list.get(v) {
639            for w in neighbors {
640                if !indices.contains_key(w) {
641                    self.tarjan_strongconnect(
642                        w,
643                        adjacency_list,
644                        index,
645                        stack,
646                        indices,
647                        lowlinks,
648                        on_stack,
649                        sccs,
650                    )?;
651                    let w_lowlink = *lowlinks.get(w).unwrap_or(&0);
652                    let v_lowlink = *lowlinks.get(v).unwrap_or(&0);
653                    lowlinks.insert(v.to_string(), v_lowlink.min(w_lowlink));
654                } else if on_stack.contains(w) {
655                    let w_index = *indices.get(w).unwrap_or(&0);
656                    let v_lowlink = *lowlinks.get(v).unwrap_or(&0);
657                    lowlinks.insert(v.to_string(), v_lowlink.min(w_index));
658                }
659            }
660        }
661
662        let v_index = *indices.get(v).unwrap_or(&0);
663        let v_lowlink = *lowlinks.get(v).unwrap_or(&0);
664
665        if v_lowlink == v_index {
666            let mut scc = Vec::new();
667            loop {
668                if let Some(w) = stack.pop() {
669                    on_stack.remove(&w);
670                    scc.push(w.clone());
671                    if w == v {
672                        break;
673                    }
674                } else {
675                    break;
676                }
677            }
678            sccs.push(scc);
679        }
680
681        Ok(())
682    }
683
684    /// Perform topological sort if no cycles exist
685    fn topological_sort(
686        &self,
687        adjacency_list: &HashMap<String, Vec<String>>,
688    ) -> Result<Option<Vec<String>>> {
689        let mut in_degree = HashMap::new();
690        let mut nodes = HashSet::new();
691
692        // Calculate in-degrees for dependency graph
693        // In dependency graph: if A depends on B, then A -> [B] in adjacency_list
694        // But for topological sort: B should come before A (B has edge to A)
695        // So we reverse the interpretation: A depends on B means B -> A in graph
696
697        for (node, deps) in adjacency_list {
698            nodes.insert(node.clone());
699            for dep in deps {
700                nodes.insert(dep.clone());
701                // A depends on dep, so dep should come before A
702                // This means dep -> A in the graph, so A gets +1 in-degree
703                *in_degree.entry(node.clone()).or_insert(0) += 1;
704            }
705        }
706
707        // Ensure all nodes have an in-degree entry
708        for node in &nodes {
709            in_degree.entry(node.clone()).or_insert(0);
710        }
711
712        let mut queue = VecDeque::new();
713        for (node, &degree) in &in_degree {
714            if degree == 0 {
715                queue.push_back(node.clone());
716            }
717        }
718
719        let mut result = Vec::new();
720        while let Some(node) = queue.pop_front() {
721            result.push(node.clone());
722
723            // When we process node, we need to decrease in-degree of nodes that depend on this node
724            // In adjacency_list: dependent -> [dependencies]
725            // So we need to find all nodes that have this node as a dependency
726            for (dependent, deps) in adjacency_list {
727                if deps.contains(&node) {
728                    // dependent depends on node, so when node is processed,
729                    // dependent's in-degree should decrease
730                    if let Some(degree) = in_degree.get_mut(dependent) {
731                        *degree -= 1;
732                        if *degree == 0 {
733                            queue.push_back(dependent.clone());
734                        }
735                    }
736                }
737            }
738        }
739
740        if result.len() == nodes.len() {
741            Ok(Some(result))
742        } else {
743            Ok(None) // Cycle detected
744        }
745    }
746
747    /// Analyze the impact of dependencies on compilation and runtime
748    fn analyze_impact(
749        &self,
750        graph: &DependencyGraph,
751        direct_deps: &[String],
752        transitive_deps: &[String],
753    ) -> Result<ImpactAnalysis> {
754        // Calculate various impact metrics using heuristics and SciRS2 for computations
755        let dependency_count = direct_deps.len() + transitive_deps.len();
756        let depth_factor = graph.adjacency_list.len() as f64;
757
758        // Use SciRS2 for numerical computations
759        let metrics = Array1::from_vec(vec![
760            dependency_count as f64,
761            depth_factor,
762            graph.strongly_connected_components.len() as f64,
763        ]);
764
765        // Normalize metrics using SciRS2 operations
766        let max_val = metrics.iter().fold(0.0f64, |acc, &x| acc.max(x));
767        let normalized_metrics = if max_val > 0.0 {
768            &metrics / max_val
769        } else {
770            metrics.clone()
771        };
772
773        let compilation_impact = normalized_metrics[0].min(1.0);
774        let binary_size_impact =
775            (normalized_metrics[0] * 0.7 + normalized_metrics[1] * 0.3).min(1.0);
776        let runtime_impact = (normalized_metrics[1] * 0.6 + normalized_metrics[2] * 0.4).min(1.0);
777        let maintenance_burden =
778            (normalized_metrics[0] * 0.4 + normalized_metrics[2] * 0.6).min(1.0);
779        let coupling_strength = (dependency_count as f64 / 20.0).min(1.0);
780
781        Ok(ImpactAnalysis {
782            compilation_impact,
783            binary_size_impact,
784            runtime_impact,
785            maintenance_burden,
786            coupling_strength,
787        })
788    }
789
790    /// Assess the risk level of the dependency configuration
791    fn assess_risk(
792        &self,
793        graph: &DependencyGraph,
794        direct_deps: &[String],
795        transitive_deps: &[String],
796        circular_deps: &[Vec<String>],
797    ) -> Result<RiskAssessment> {
798        let mut risk_factors = Vec::new();
799        let mut risk_score = 0.0;
800
801        // Check for circular dependencies
802        if !circular_deps.is_empty() {
803            risk_factors.push(RiskFactor {
804                factor_type: RiskFactorType::CircularDependency,
805                description: format!("Found {} circular dependency cycles", circular_deps.len()),
806                severity: 8.0,
807                affected_components: circular_deps.iter().flatten().cloned().collect(),
808            });
809            risk_score += 30.0;
810        }
811
812        // Check dependency depth
813        let max_depth = graph.adjacency_list.len();
814        if max_depth > self.risk_config.max_safe_depth {
815            risk_factors.push(RiskFactor {
816                factor_type: RiskFactorType::ExcessiveDepth,
817                description: format!(
818                    "Dependency depth {} exceeds safe limit {}",
819                    max_depth, self.risk_config.max_safe_depth
820                ),
821                severity: 6.0,
822                affected_components: graph.adjacency_list.keys().cloned().collect(),
823            });
824            risk_score += 20.0;
825        }
826
827        // Check number of direct dependencies
828        if direct_deps.len() > self.risk_config.max_direct_dependencies {
829            risk_factors.push(RiskFactor {
830                factor_type: RiskFactorType::HighFanOut,
831                description: format!("Too many direct dependencies: {}", direct_deps.len()),
832                severity: 5.0,
833                affected_components: direct_deps.to_vec(),
834            });
835            risk_score += 15.0;
836        }
837
838        // Assess complexity
839        let complexity_score = (transitive_deps.len() as f64 / 10.0).min(10.0);
840        if complexity_score > 7.0 {
841            risk_factors.push(RiskFactor {
842                factor_type: RiskFactorType::ComplexRelationships,
843                description: "Complex dependency relationships detected".to_string(),
844                severity: complexity_score,
845                affected_components: transitive_deps.to_vec(),
846            });
847            risk_score += complexity_score * 2.0;
848        }
849
850        // Determine risk level
851        let risk_level = match risk_score {
852            0.0..=25.0 => RiskLevel::Low,
853            25.1..=50.0 => RiskLevel::Medium,
854            50.1..=75.0 => RiskLevel::High,
855            _ => RiskLevel::Critical,
856        };
857
858        // Generate mitigation recommendations
859        let mitigation_recommendations = self.generate_mitigation_recommendations(&risk_factors);
860
861        Ok(RiskAssessment {
862            risk_level,
863            risk_score: risk_score.min(100.0),
864            risk_factors,
865            mitigation_recommendations,
866        })
867    }
868
869    /// Generate mitigation recommendations based on risk factors
870    fn generate_mitigation_recommendations(&self, risk_factors: &[RiskFactor]) -> Vec<String> {
871        let mut recommendations = Vec::new();
872
873        for factor in risk_factors {
874            match factor.factor_type {
875                RiskFactorType::CircularDependency => {
876                    recommendations.push("Break circular dependencies by introducing interfaces or dependency injection".to_string());
877                }
878                RiskFactorType::ExcessiveDepth => {
879                    recommendations.push(
880                        "Flatten dependency hierarchy by consolidating related traits".to_string(),
881                    );
882                }
883                RiskFactorType::HighFanOut => {
884                    recommendations
885                        .push("Split large traits into smaller, focused interfaces".to_string());
886                }
887                RiskFactorType::ComplexRelationships => {
888                    recommendations.push(
889                        "Simplify dependency relationships by removing unnecessary dependencies"
890                            .to_string(),
891                    );
892                }
893                _ => {
894                    recommendations.push("Review and optimize dependency structure".to_string());
895                }
896            }
897        }
898
899        recommendations
900    }
901
902    /// Analyze performance implications of the dependency configuration
903    fn analyze_performance(
904        &self,
905        graph: &DependencyGraph,
906        impact: &ImpactAnalysis,
907    ) -> Result<PerformanceAnalysis> {
908        let node_count = graph.adjacency_list.len() as f64;
909        let edge_count: f64 = graph.adjacency_list.values().map(|v| v.len() as f64).sum();
910
911        // Estimate compilation time based on dependency complexity
912        let estimated_compile_time =
913            (node_count * 50.0 + edge_count * 10.0) * (1.0 + impact.compilation_impact);
914
915        // Estimate memory usage
916        let compile_memory_usage =
917            (node_count * 2.0 + edge_count * 0.5) * (1.0 + impact.binary_size_impact);
918
919        // Runtime overhead
920        let runtime_memory_overhead = edge_count * 64.0; // bytes per dependency
921        let cpu_overhead_percentage = impact.runtime_impact * 5.0; // max 5% overhead
922
923        // Cache efficiency impact
924        let cache_efficiency_impact = if impact.coupling_strength > 0.7 {
925            0.8 - impact.coupling_strength * 0.2
926        } else {
927            0.9
928        };
929
930        Ok(PerformanceAnalysis {
931            estimated_compile_time,
932            compile_memory_usage,
933            runtime_memory_overhead,
934            cpu_overhead_percentage,
935            cache_efficiency_impact,
936        })
937    }
938
939    /// Generate optimization suggestions based on analysis results
940    fn generate_optimization_suggestions(
941        &self,
942        graph: &DependencyGraph,
943        risk: &RiskAssessment,
944        performance: &PerformanceAnalysis,
945    ) -> Result<Vec<OptimizationSuggestion>> {
946        let mut suggestions = Vec::new();
947
948        // Suggest breaking cycles if found
949        if !graph.strongly_connected_components.is_empty() {
950            suggestions.push(OptimizationSuggestion {
951                suggestion_type: OptimizationType::BreakCycles,
952                description:
953                    "Break circular dependencies to improve compilation and maintainability"
954                        .to_string(),
955                expected_benefit: 8.0,
956                implementation_difficulty: 6.0,
957                priority: Priority::High,
958                implementation_steps: vec![
959                    "Identify circular dependencies".to_string(),
960                    "Introduce interfaces or traits to break cycles".to_string(),
961                    "Use dependency injection patterns".to_string(),
962                ],
963            });
964        }
965
966        // Suggest depth reduction if needed
967        if risk.risk_score > 50.0 {
968            suggestions.push(OptimizationSuggestion {
969                suggestion_type: OptimizationType::ReduceDepth,
970                description: "Reduce dependency depth to improve performance".to_string(),
971                expected_benefit: 7.0,
972                implementation_difficulty: 5.0,
973                priority: Priority::Medium,
974                implementation_steps: vec![
975                    "Analyze dependency chains".to_string(),
976                    "Consolidate related traits".to_string(),
977                    "Remove unnecessary intermediate dependencies".to_string(),
978                ],
979            });
980        }
981
982        // Performance optimizations
983        if performance.estimated_compile_time > 1000.0 {
984            suggestions.push(OptimizationSuggestion {
985                suggestion_type: OptimizationType::PerformanceOptimization,
986                description: "Optimize compilation performance".to_string(),
987                expected_benefit: 6.0,
988                implementation_difficulty: 4.0,
989                priority: Priority::Medium,
990                implementation_steps: vec![
991                    "Add incremental compilation support".to_string(),
992                    "Use feature flags for optional dependencies".to_string(),
993                    "Implement lazy loading where possible".to_string(),
994                ],
995            });
996        }
997
998        Ok(suggestions)
999    }
1000
1001    /// Assess dependency risk with detailed analysis
1002    pub fn assess_dependency_risk<'a>(
1003        &self,
1004        analysis: &'a DependencyAnalysis,
1005    ) -> &'a RiskAssessment {
1006        &analysis.risk_assessment
1007    }
1008
1009    /// Get performance impact analysis
1010    pub fn get_performance_analysis<'a>(
1011        &self,
1012        analysis: &'a DependencyAnalysis,
1013    ) -> &'a PerformanceAnalysis {
1014        &analysis.performance_analysis
1015    }
1016
1017    /// Get optimization suggestions sorted by priority
1018    pub fn get_prioritized_suggestions<'a>(
1019        &self,
1020        analysis: &'a DependencyAnalysis,
1021    ) -> Vec<&'a OptimizationSuggestion> {
1022        let mut suggestions: Vec<&OptimizationSuggestion> =
1023            analysis.optimization_suggestions.iter().collect();
1024        suggestions.sort_by(|a, b| {
1025            b.priority.cmp(&a.priority).then_with(|| {
1026                b.expected_benefit
1027                    .partial_cmp(&a.expected_benefit)
1028                    .unwrap_or(std::cmp::Ordering::Equal)
1029            })
1030        });
1031        suggestions
1032    }
1033
1034    /// Clear analysis cache
1035    pub fn clear_cache(&mut self) {
1036        self.analysis_cache.clear();
1037    }
1038
1039    /// Get cache statistics
1040    pub fn cache_stats(&self) -> (usize, usize) {
1041        (self.analysis_cache.len(), self.analysis_cache.capacity())
1042    }
1043}
1044
1045impl Default for DependencyAnalyzer {
1046    fn default() -> Self {
1047        Self::new()
1048    }
1049}
1050
1051#[allow(non_snake_case)]
1052#[cfg(test)]
1053mod tests {
1054    use super::*;
1055    use crate::api_data_structures::{AssociatedType, TraitInfo};
1056
1057    fn create_test_trait_info(name: &str, supertraits: Vec<String>) -> TraitInfo {
1058        TraitInfo {
1059            name: name.to_string(),
1060            description: "Test trait".to_string(),
1061            path: format!("test::{}", name),
1062            generics: Vec::new(),
1063            associated_types: Vec::new(),
1064            methods: Vec::new(),
1065            supertraits,
1066            implementations: Vec::new(),
1067        }
1068    }
1069
1070    fn create_test_trait_with_associated_types(
1071        name: &str,
1072        supertraits: Vec<String>,
1073        associated_types: Vec<AssociatedType>,
1074    ) -> TraitInfo {
1075        TraitInfo {
1076            name: name.to_string(),
1077            description: "Test trait".to_string(),
1078            path: format!("test::{}", name),
1079            generics: Vec::new(),
1080            associated_types,
1081            methods: Vec::new(),
1082            supertraits,
1083            implementations: Vec::new(),
1084        }
1085    }
1086
1087    #[test]
1088    fn test_dependency_analyzer_creation() {
1089        let analyzer = DependencyAnalyzer::new();
1090        assert_eq!(analyzer.max_depth, 50);
1091        assert!(analyzer.performance_tracking);
1092        assert!(analyzer.analysis_cache.is_empty());
1093    }
1094
1095    #[test]
1096    fn test_dependency_analyzer_with_config() {
1097        let config = RiskAssessmentConfig {
1098            max_safe_depth: 8,
1099            max_direct_dependencies: 10,
1100            complexity_weight: 0.5,
1101            coupling_weight: 0.5,
1102        };
1103        let analyzer = DependencyAnalyzer::with_config(30, false, config);
1104        assert_eq!(analyzer.max_depth, 30);
1105        assert!(!analyzer.performance_tracking);
1106        assert_eq!(analyzer.risk_config.max_safe_depth, 8);
1107    }
1108
1109    #[test]
1110    fn test_basic_dependency_analysis() {
1111        let analyzer = DependencyAnalyzer::new();
1112        let trait_info = create_test_trait_info("TestTrait", vec!["SuperTrait".to_string()]);
1113
1114        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1115
1116        assert_eq!(analysis.direct_dependencies.len(), 1);
1117        assert_eq!(analysis.direct_dependencies[0], "SuperTrait");
1118        assert!(analysis.dependency_depth > 0);
1119    }
1120
1121    #[test]
1122    fn test_dependency_analysis_with_associated_types() {
1123        let analyzer = DependencyAnalyzer::new();
1124        let associated_type = AssociatedType {
1125            name: "Output".to_string(),
1126            description: "Output type".to_string(),
1127            bounds: vec!["Clone".to_string(), "Debug".to_string()],
1128        };
1129        let trait_info = create_test_trait_with_associated_types(
1130            "TestTrait",
1131            vec!["SuperTrait".to_string()],
1132            vec![associated_type],
1133        );
1134
1135        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1136
1137        assert_eq!(analysis.direct_dependencies.len(), 3); // SuperTrait + Clone + Debug
1138        assert!(analysis
1139            .direct_dependencies
1140            .contains(&"SuperTrait".to_string()));
1141        assert!(analysis.direct_dependencies.contains(&"Clone".to_string()));
1142        assert!(analysis.direct_dependencies.contains(&"Debug".to_string()));
1143    }
1144
1145    #[test]
1146    fn test_empty_dependencies() {
1147        let analyzer = DependencyAnalyzer::new();
1148        let trait_info = create_test_trait_info("IndependentTrait", vec![]);
1149
1150        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1151
1152        assert!(analysis.direct_dependencies.is_empty());
1153        assert!(analysis.transitive_dependencies.is_empty());
1154        assert_eq!(analysis.dependency_depth, 1); // Self depth
1155        assert!(analysis.circular_dependencies.is_empty());
1156    }
1157
1158    #[test]
1159    fn test_risk_assessment_low_risk() {
1160        let analyzer = DependencyAnalyzer::new();
1161        let trait_info = create_test_trait_info("LowRiskTrait", vec!["SingleDep".to_string()]);
1162
1163        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1164
1165        // Should be low risk with minimal dependencies
1166        assert_eq!(analysis.risk_assessment.risk_level, RiskLevel::Low);
1167        assert!(analysis.risk_assessment.risk_score < 25.0);
1168    }
1169
1170    #[test]
1171    fn test_risk_assessment_high_dependencies() {
1172        let analyzer = DependencyAnalyzer::new();
1173        let many_deps: Vec<String> = (0..20).map(|i| format!("Dep{}", i)).collect();
1174        let trait_info = create_test_trait_info("HighRiskTrait", many_deps);
1175
1176        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1177
1178        // Should have higher risk due to many dependencies
1179        assert!(analysis.risk_assessment.risk_score > 0.0);
1180        assert!(!analysis.risk_assessment.risk_factors.is_empty());
1181    }
1182
1183    #[test]
1184    fn test_performance_analysis() {
1185        let analyzer = DependencyAnalyzer::new();
1186        let trait_info =
1187            create_test_trait_info("TestTrait", vec!["Dep1".to_string(), "Dep2".to_string()]);
1188
1189        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1190
1191        assert!(analysis.performance_analysis.estimated_compile_time > 0.0);
1192        assert!(analysis.performance_analysis.compile_memory_usage > 0.0);
1193        assert!(analysis.performance_analysis.cache_efficiency_impact > 0.0);
1194        assert!(analysis.performance_analysis.cache_efficiency_impact <= 1.0);
1195    }
1196
1197    #[test]
1198    fn test_optimization_suggestions() {
1199        let analyzer = DependencyAnalyzer::new();
1200        let many_deps: Vec<String> = (0..25).map(|i| format!("Dep{}", i)).collect();
1201        let trait_info = create_test_trait_info("ComplexTrait", many_deps);
1202
1203        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1204        let suggestions = analyzer.get_prioritized_suggestions(&analysis);
1205
1206        assert!(!suggestions.is_empty());
1207
1208        // Check that suggestions are sorted by priority
1209        for window in suggestions.windows(2) {
1210            assert!(window[0].priority >= window[1].priority);
1211        }
1212    }
1213
1214    #[test]
1215    fn test_tarjan_algorithm_no_cycles() {
1216        let analyzer = DependencyAnalyzer::new();
1217        let mut adjacency_list = HashMap::new();
1218        adjacency_list.insert("A".to_string(), vec!["B".to_string()]);
1219        adjacency_list.insert("B".to_string(), vec!["C".to_string()]);
1220        adjacency_list.insert("C".to_string(), vec![]);
1221
1222        let sccs = analyzer.tarjan_scc(&adjacency_list).unwrap();
1223
1224        // Each node should be in its own SCC (no cycles)
1225        assert_eq!(sccs.len(), 3);
1226        for scc in &sccs {
1227            assert_eq!(scc.len(), 1);
1228        }
1229    }
1230
1231    #[test]
1232    fn test_topological_sort() {
1233        let analyzer = DependencyAnalyzer::new();
1234        let mut adjacency_list = HashMap::new();
1235        adjacency_list.insert("A".to_string(), vec!["B".to_string()]);
1236        adjacency_list.insert("B".to_string(), vec!["C".to_string()]);
1237        adjacency_list.insert("C".to_string(), vec![]);
1238
1239        let topo_order = analyzer.topological_sort(&adjacency_list).unwrap();
1240
1241        assert!(topo_order.is_some());
1242        let order = topo_order.unwrap();
1243        assert_eq!(order.len(), 3);
1244
1245        // C should come before B, B should come before A
1246        let c_pos = order.iter().position(|x| x == "C").unwrap();
1247        let b_pos = order.iter().position(|x| x == "B").unwrap();
1248        let a_pos = order.iter().position(|x| x == "A").unwrap();
1249
1250        assert!(c_pos < b_pos);
1251        assert!(b_pos < a_pos);
1252    }
1253
1254    #[test]
1255    fn test_cache_functionality() {
1256        let mut analyzer = DependencyAnalyzer::new();
1257        let trait_info = create_test_trait_info("CacheTestTrait", vec!["Dep1".to_string()]);
1258
1259        // First analysis
1260        let _analysis1 = analyzer.analyze_dependencies(&trait_info).unwrap();
1261        let (cache_size, _) = analyzer.cache_stats();
1262        assert_eq!(cache_size, 0); // Cache is not actually updated in this implementation
1263
1264        // Clear cache
1265        analyzer.clear_cache();
1266        let (cache_size_after_clear, _) = analyzer.cache_stats();
1267        assert_eq!(cache_size_after_clear, 0);
1268    }
1269
1270    #[test]
1271    fn test_risk_factor_types() {
1272        // Test that all risk factor types can be created
1273        let risk_factor = RiskFactor {
1274            factor_type: RiskFactorType::CircularDependency,
1275            description: "Test circular dependency".to_string(),
1276            severity: 5.0,
1277            affected_components: vec!["A".to_string(), "B".to_string()],
1278        };
1279
1280        assert_eq!(risk_factor.severity, 5.0);
1281        assert_eq!(risk_factor.affected_components.len(), 2);
1282    }
1283
1284    #[test]
1285    fn test_priority_ordering() {
1286        assert!(Priority::Critical > Priority::High);
1287        assert!(Priority::High > Priority::Medium);
1288        assert!(Priority::Medium > Priority::Low);
1289    }
1290
1291    #[test]
1292    fn test_risk_level_display() {
1293        assert_eq!(format!("{}", RiskLevel::Low), "Low");
1294        assert_eq!(format!("{}", RiskLevel::Medium), "Medium");
1295        assert_eq!(format!("{}", RiskLevel::High), "High");
1296        assert_eq!(format!("{}", RiskLevel::Critical), "Critical");
1297    }
1298
1299    #[test]
1300    fn test_dependency_graph_construction() {
1301        let analyzer = DependencyAnalyzer::new();
1302        let trait_info =
1303            create_test_trait_info("GraphTest", vec!["Dep1".to_string(), "Dep2".to_string()]);
1304
1305        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1306        let graph = &analysis.dependency_graph;
1307
1308        assert!(graph.adjacency_list.contains_key("GraphTest"));
1309        assert_eq!(graph.adjacency_list["GraphTest"].len(), 2);
1310
1311        // Check reverse dependencies
1312        assert!(graph.reverse_dependencies.contains_key("Dep1"));
1313        assert!(graph.reverse_dependencies.contains_key("Dep2"));
1314    }
1315
1316    #[test]
1317    fn test_impact_analysis_normalization() {
1318        let analyzer = DependencyAnalyzer::new();
1319        let trait_info = create_test_trait_info("ImpactTest", vec!["Dep1".to_string()]);
1320
1321        let analysis = analyzer.analyze_dependencies(&trait_info).unwrap();
1322        let impact = &analysis.impact_analysis;
1323
1324        // All impact values should be normalized between 0 and 1
1325        assert!(impact.compilation_impact >= 0.0 && impact.compilation_impact <= 1.0);
1326        assert!(impact.binary_size_impact >= 0.0 && impact.binary_size_impact <= 1.0);
1327        assert!(impact.runtime_impact >= 0.0 && impact.runtime_impact <= 1.0);
1328        assert!(impact.maintenance_burden >= 0.0 && impact.maintenance_burden <= 1.0);
1329        assert!(impact.coupling_strength >= 0.0 && impact.coupling_strength <= 1.0);
1330    }
1331}
sklears_core/trait_explorer/dependency_analysis.rs

sklears_core/trait_explorer/
dependency_analysis.rs
