thread_flow/incremental/
invalidation.rs

1// SPDX-FileCopyrightText: 2025 Knitli Inc. <knitli@knit.li>
2// SPDX-License-Identifier: AGPL-3.0-or-later
3
4//! Invalidation detection and topological sorting for incremental updates.
5//!
6//! This module provides sophisticated invalidation detection that determines
7//! which files require reanalysis after changes. It uses:
8//!
9//! - **BFS/DFS traversal** from [`DependencyGraph`] to find affected files
10//! - **Topological sort** to order reanalysis respecting dependencies
11//! - **Tarjan's SCC algorithm** to detect and report circular dependencies
12//!
13//! ## Design Pattern
14//!
15//! Wraps [`DependencyGraph`] with higher-level API that packages results
16//! into [`InvalidationResult`] with comprehensive cycle detection.
17
18use super::graph::{DependencyGraph, GraphError};
19use metrics::histogram;
20use std::path::{Path, PathBuf};
21use std::time::Instant;
22use thread_utilities::{RapidMap, RapidSet};
23use tracing::{info, warn};
24
25/// Errors that can occur during invalidation detection.
26#[derive(Debug, thiserror::Error)]
27pub enum InvalidationError {
28    /// A circular dependency was detected during topological sort.
29    #[error("Circular dependency detected: {0:?}")]
30    CircularDependency(Vec<PathBuf>),
31
32    /// An error occurred in the underlying dependency graph.
33    #[error("Graph error: {0}")]
34    Graph(String),
35}
36
37/// Result of invalidation detection, including cycle information.
38///
39/// This structure packages all information needed to perform incremental
40/// reanalysis: which files are affected, what order to analyze them in,
41/// and whether any circular dependencies were detected.
42///
43/// # Examples
44///
45/// ```rust
46/// use thread_flow::incremental::invalidation::InvalidationDetector;
47/// use thread_flow::incremental::DependencyGraph;
48/// use thread_utilities::RapishSet;
49/// use std::path::PathBuf;
50///
51/// let graph = DependencyGraph::new();
52/// let detector = InvalidationDetector::new(graph);
53/// let result = detector.compute_invalidation_set(&[PathBuf::from("main.rs")]);
54///
55/// if result.circular_dependencies.is_empty() {
56///     // Safe to analyze in order
57///     for file in &result.analysis_order {
58///         // analyze(file);
59///     }
60/// } else {
61///     // Handle cycles
62///     eprintln!("Circular dependencies detected: {:?}", result.circular_dependencies);
63/// }
64/// ```
65#[derive(Debug, Clone)]
66pub struct InvalidationResult {
67    /// All files that require reanalysis (includes changed files).
68    pub invalidated_files: Vec<PathBuf>,
69
70    /// Files in topological order (dependencies before dependents).
71    /// May be empty or partial if cycles are detected.
72    pub analysis_order: Vec<PathBuf>,
73
74    /// Strongly connected components representing circular dependencies.
75    /// Each inner Vec contains files involved in a cycle.
76    /// Empty if no cycles exist.
77    pub circular_dependencies: Vec<Vec<PathBuf>>,
78}
79
80/// Detects invalidation scope and computes reanalysis order.
81///
82/// Wraps [`DependencyGraph`] to provide:
83/// - Propagation of invalidation through dependency edges
84/// - Topological sorting for correct reanalysis order
85/// - Comprehensive cycle detection using Tarjan's algorithm
86///
87/// # Examples
88///
89/// ```rust
90/// use thread_flow::incremental::invalidation::InvalidationDetector;
91/// use thread_flow::incremental::DependencyGraph;
92/// use thread_flow::incremental::types::{DependencyEdge, DependencyType};
93/// use std::path::PathBuf;
94///
95/// let mut graph = DependencyGraph::new();
96/// graph.add_edge(DependencyEdge::new(
97///     PathBuf::from("main.rs"),
98///     PathBuf::from("lib.rs"),
99///     DependencyType::Import,
100/// ));
101///
102/// let detector = InvalidationDetector::new(graph);
103/// let result = detector.compute_invalidation_set(&[PathBuf::from("lib.rs")]);
104///
105/// assert!(result.invalidated_files.contains(&PathBuf::from("main.rs")));
106/// ```
107#[derive(Debug, Clone)]
108pub struct InvalidationDetector {
109    graph: DependencyGraph,
110}
111
112impl InvalidationDetector {
113    /// Creates a new invalidation detector wrapping the given dependency graph.
114    ///
115    /// # Arguments
116    ///
117    /// * `graph` - The dependency graph to use for invalidation detection.
118    ///
119    /// # Examples
120    ///
121    /// ```rust
122    /// use thread_flow::incremental::invalidation::InvalidationDetector;
123    /// use thread_flow::incremental::DependencyGraph;
124    ///
125    /// let graph = DependencyGraph::new();
126    /// let detector = InvalidationDetector::new(graph);
127    /// ```
128    pub fn new(graph: DependencyGraph) -> Self {
129        Self { graph }
130    }
131
132    /// Computes the complete invalidation set for the given changed files.
133    ///
134    /// This is the primary high-level API for invalidation detection. It:
135    /// 1. Finds all files transitively affected by changes
136    /// 2. Attempts topological sort for reanalysis order
137    /// 3. Detects and reports any circular dependencies
138    ///
139    /// Always returns a result (never fails). If cycles are detected,
140    /// they are reported in `circular_dependencies` and `analysis_order`
141    /// may be empty or partial.
142    ///
143    /// # Arguments
144    ///
145    /// * `changed_files` - Files that have been modified or added.
146    ///
147    /// # Returns
148    ///
149    /// An [`InvalidationResult`] with:
150    /// - All affected files
151    /// - Topological order for reanalysis (if no cycles)
152    /// - Detected circular dependencies (if any)
153    ///
154    /// # Examples
155    ///
156    /// ```rust
157    /// use thread_flow::incremental::invalidation::InvalidationDetector;
158    /// use thread_flow::incremental::DependencyGraph;
159    /// use std::path::PathBuf;
160    ///
161    /// let graph = DependencyGraph::new();
162    /// let detector = InvalidationDetector::new(graph);
163    ///
164    /// let result = detector.compute_invalidation_set(&[
165    ///     PathBuf::from("src/utils.rs"),
166    /// ]);
167    ///
168    /// println!("Files to reanalyze: {}", result.invalidated_files.len());
169    /// ```
170    pub fn compute_invalidation_set(&self, changed_files: &[PathBuf]) -> InvalidationResult {
171        let start = Instant::now();
172        info!(
173            "computing invalidation set for {} changed files",
174            changed_files.len()
175        );
176
177        // Step 1: Find all files transitively affected by changes
178        let changed_set: RapidSet<PathBuf> = changed_files.iter().cloned().collect();
179        let affected = self.graph.find_affected_files(&changed_set);
180        let invalidated_files: Vec<PathBuf> = affected.iter().cloned().collect();
181
182        info!(
183            "found {} files affected by changes",
184            invalidated_files.len()
185        );
186
187        // Step 2: Attempt topological sort on affected files
188        let result = match self.topological_sort(&invalidated_files) {
189            Ok(analysis_order) => {
190                // Success - no cycles detected
191                info!("topological sort successful");
192                InvalidationResult {
193                    invalidated_files,
194                    analysis_order,
195                    circular_dependencies: vec![],
196                }
197            }
198            Err(_) => {
199                // Cycle detected - find all strongly connected components
200                warn!("circular dependencies detected");
201                let cycles = self.find_strongly_connected_components(&affected);
202
203                // Try to provide partial ordering for acyclic parts
204                // For now, return empty analysis_order when cycles exist
205                InvalidationResult {
206                    invalidated_files,
207                    analysis_order: vec![],
208                    circular_dependencies: cycles,
209                }
210            }
211        };
212
213        let duration_ms = start.elapsed().as_micros() as f64 / 1000.0;
214        histogram!("invalidation_time_ms").record(duration_ms);
215
216        info!(
217            invalidated_count = result.invalidated_files.len(),
218            cycles = result.circular_dependencies.len(),
219            duration_ms = %format!("{:.2}", duration_ms),
220            "invalidation complete"
221        );
222
223        result
224    }
225
226    /// Performs topological sort on the given subset of files.
227    ///
228    /// Returns files in dependency order: dependencies appear before
229    /// their dependents. This is a lower-level API that directly exposes
230    /// sort failures as errors.
231    ///
232    /// # Arguments
233    ///
234    /// * `files` - The subset of files to sort.
235    ///
236    /// # Errors
237    ///
238    /// Returns [`InvalidationError::CircularDependency`] if a cycle is detected.
239    ///
240    /// # Examples
241    ///
242    /// ```rust
243    /// use thread_flow::incremental::invalidation::InvalidationDetector;
244    /// use thread_flow::incremental::DependencyGraph;
245    /// use std::path::PathBuf;
246    ///
247    /// let graph = DependencyGraph::new();
248    /// let detector = InvalidationDetector::new(graph);
249    ///
250    /// let sorted = detector.topological_sort(&[
251    ///     PathBuf::from("a.rs"),
252    ///     PathBuf::from("b.rs"),
253    /// ]);
254    ///
255    /// match sorted {
256    ///     Ok(order) => println!("Analysis order: {:?}", order),
257    ///     Err(e) => eprintln!("Cycle detected: {}", e),
258    /// }
259    /// ```
260    pub fn topological_sort(&self, files: &[PathBuf]) -> Result<Vec<PathBuf>, InvalidationError> {
261        // Delegate to DependencyGraph's topological sort and map errors
262        let files_set: RapidSet<PathBuf> = files.iter().cloned().collect();
263
264        self.graph
265            .topological_sort(&files_set)
266            .map_err(|e| match e {
267                GraphError::CyclicDependency(path) => {
268                    InvalidationError::CircularDependency(vec![path])
269                }
270            })
271    }
272
273    /// Propagates invalidation from a single root file.
274    ///
275    /// Finds all files transitively affected by changes to the given root.
276    /// Uses BFS traversal following reverse dependency edges (dependents).
277    ///
278    /// # Arguments
279    ///
280    /// * `root` - The changed file to propagate from.
281    ///
282    /// # Returns
283    ///
284    /// All files affected by the change, including the root itself.
285    ///
286    /// # Examples
287    ///
288    /// ```rust
289    /// use thread_flow::incremental::invalidation::InvalidationDetector;
290    /// use thread_flow::incremental::DependencyGraph;
291    /// use std::path::PathBuf;
292    ///
293    /// let graph = DependencyGraph::new();
294    /// let detector = InvalidationDetector::new(graph);
295    ///
296    /// let affected = detector.propagate_invalidation(&PathBuf::from("core.rs"));
297    /// println!("Files affected: {}", affected.len());
298    /// ```
299    pub fn propagate_invalidation(&self, root: &Path) -> Vec<PathBuf> {
300        // Delegate to DependencyGraph's find_affected_files for single root
301        let root_set: RapidSet<PathBuf> = [root.to_path_buf()].into_iter().collect();
302        let affected: RapidSet<PathBuf> = self.graph.find_affected_files(&root_set);
303        affected.into_iter().collect()
304    }
305
306    // ── Private helpers ──────────────────────────────────────────────────
307
308    /// Finds strongly connected components using Tarjan's algorithm.
309    ///
310    /// Returns all non-trivial SCCs (size > 1), which represent cycles.
311    /// This is O(V + E) time complexity.
312    ///
313    /// # Arguments
314    ///
315    /// * `files` - The subset of files to analyze for cycles.
316    ///
317    /// # Returns
318    ///
319    /// Vector of strongly connected components, where each component
320    /// is a vector of file paths involved in a cycle.
321    fn find_strongly_connected_components(&self, files: &RapidSet<PathBuf>) -> Vec<Vec<PathBuf>> {
322        // Tarjan's SCC algorithm for finding all cycles
323        let mut state = TarjanState::new();
324        let mut sccs = Vec::new();
325
326        // Run DFS from each unvisited node
327        for file in files {
328            if !state.indices.contains_key(file) {
329                self.tarjan_dfs(file, &mut state, &mut sccs);
330            }
331        }
332
333        // Filter to non-trivial SCCs (cycles)
334        sccs.into_iter()
335            .filter(|scc| {
336                // Include if size > 1, or size == 1 with self-loop
337                scc.len() > 1 || (scc.len() == 1 && self.has_self_loop(&scc[0]))
338            })
339            .collect()
340    }
341
342    /// DFS helper for Tarjan's algorithm
343    fn tarjan_dfs(&self, v: &Path, state: &mut TarjanState, sccs: &mut Vec<Vec<PathBuf>>) {
344        // Initialize node
345        let index = state.index_counter;
346        state.indices.insert(v.to_path_buf(), index);
347        state.lowlinks.insert(v.to_path_buf(), index);
348        state.index_counter += 1;
349        state.stack.push(v.to_path_buf());
350        state.on_stack.insert(v.to_path_buf());
351
352        // Visit all successors (dependencies)
353        let dependencies = self.graph.get_dependencies(v);
354        for edge in dependencies {
355            let dep = &edge.to;
356            if !state.indices.contains_key(dep) {
357                // Successor not yet visited - recurse
358                self.tarjan_dfs(dep, state, sccs);
359
360                // Update lowlink
361                let w_lowlink = *state.lowlinks.get(dep).unwrap();
362                let v_lowlink = state.lowlinks.get_mut(&v.to_path_buf()).unwrap();
363                *v_lowlink = (*v_lowlink).min(w_lowlink);
364            } else if state.on_stack.contains(dep) {
365                // Successor is on stack (part of current SCC)
366                let w_index = *state.indices.get(dep).unwrap();
367                let v_lowlink = state.lowlinks.get_mut(&v.to_path_buf()).unwrap();
368                *v_lowlink = (*v_lowlink).min(w_index);
369            }
370        }
371
372        // If v is a root node, pop the stack to create an SCC
373        let v_index = *state.indices.get(&v.to_path_buf()).unwrap();
374        let v_lowlink = *state.lowlinks.get(&v.to_path_buf()).unwrap();
375
376        if v_lowlink == v_index {
377            let mut scc = Vec::new();
378            loop {
379                let w = state.stack.pop().unwrap();
380                state.on_stack.remove(&w);
381                scc.push(w.clone());
382                if w == v {
383                    break;
384                }
385            }
386            sccs.push(scc);
387        }
388    }
389
390    /// Check if a file has a self-referential edge
391    fn has_self_loop(&self, file: &Path) -> bool {
392        let deps = self.graph.get_dependencies(file);
393        deps.iter().any(|edge| edge.to == file)
394    }
395}
396
397/// State for Tarjan's SCC algorithm
398struct TarjanState {
399    index_counter: usize,
400    indices: RapidMap<PathBuf, usize>,
401    lowlinks: RapidMap<PathBuf, usize>,
402    stack: Vec<PathBuf>,
403    on_stack: RapidSet<PathBuf>,
404}
405
406impl TarjanState {
407    fn new() -> Self {
408        Self {
409            index_counter: 0,
410            indices: thread_utilities::get_map(),
411            lowlinks: thread_utilities::get_map(),
412            stack: Vec::new(),
413            on_stack: thread_utilities::get_set(),
414        }
415    }
416}
417
418// ─── Tests (TDD: Written BEFORE implementation) ──────────────────────────────
419
420#[cfg(test)]
421mod tests {
422    use super::*;
423    use crate::incremental::types::{DependencyEdge, DependencyType};
424
425    // ── Construction Tests ───────────────────────────────────────────────
426
427    #[test]
428    fn test_invalidation_detector_new() {
429        let graph = DependencyGraph::new();
430        let detector = InvalidationDetector::new(graph);
431
432        // Verify detector is properly constructed
433        assert_eq!(detector.graph.node_count(), 0);
434        assert_eq!(detector.graph.edge_count(), 0);
435    }
436
437    #[test]
438    fn test_invalidation_detector_with_populated_graph() {
439        let mut graph = DependencyGraph::new();
440        graph.add_edge(DependencyEdge::new(
441            PathBuf::from("A"),
442            PathBuf::from("B"),
443            DependencyType::Import,
444        ));
445
446        let detector = InvalidationDetector::new(graph);
447        assert_eq!(detector.graph.node_count(), 2);
448        assert_eq!(detector.graph.edge_count(), 1);
449    }
450
451    // ── propagate_invalidation Tests ─────────────────────────────────────
452
453    #[test]
454    fn test_propagate_single_file_no_dependents() {
455        let mut graph = DependencyGraph::new();
456        graph.add_node(&PathBuf::from("isolated.rs"));
457
458        let detector = InvalidationDetector::new(graph);
459        let affected = detector.propagate_invalidation(&PathBuf::from("isolated.rs"));
460
461        assert_eq!(affected.len(), 1);
462        assert_eq!(affected[0], PathBuf::from("isolated.rs"));
463    }
464
465    #[test]
466    fn test_propagate_linear_chain() {
467        let mut graph = DependencyGraph::new();
468        // A -> B -> C (A depends on B, B depends on C)
469        graph.add_edge(DependencyEdge::new(
470            PathBuf::from("A"),
471            PathBuf::from("B"),
472            DependencyType::Import,
473        ));
474        graph.add_edge(DependencyEdge::new(
475            PathBuf::from("B"),
476            PathBuf::from("C"),
477            DependencyType::Import,
478        ));
479
480        let detector = InvalidationDetector::new(graph);
481        let affected = detector.propagate_invalidation(&PathBuf::from("C"));
482
483        // C changed -> B affected -> A affected
484        assert_eq!(affected.len(), 3);
485        assert!(affected.contains(&PathBuf::from("A")));
486        assert!(affected.contains(&PathBuf::from("B")));
487        assert!(affected.contains(&PathBuf::from("C")));
488    }
489
490    #[test]
491    fn test_propagate_diamond_dependency() {
492        let mut graph = DependencyGraph::new();
493        // Diamond: A -> B, A -> C, B -> D, C -> D
494        graph.add_edge(DependencyEdge::new(
495            PathBuf::from("A"),
496            PathBuf::from("B"),
497            DependencyType::Import,
498        ));
499        graph.add_edge(DependencyEdge::new(
500            PathBuf::from("A"),
501            PathBuf::from("C"),
502            DependencyType::Import,
503        ));
504        graph.add_edge(DependencyEdge::new(
505            PathBuf::from("B"),
506            PathBuf::from("D"),
507            DependencyType::Import,
508        ));
509        graph.add_edge(DependencyEdge::new(
510            PathBuf::from("C"),
511            PathBuf::from("D"),
512            DependencyType::Import,
513        ));
514
515        let detector = InvalidationDetector::new(graph);
516        let affected = detector.propagate_invalidation(&PathBuf::from("D"));
517
518        // D changed -> B and C affected -> A affected
519        assert_eq!(affected.len(), 4);
520        assert!(affected.contains(&PathBuf::from("A")));
521        assert!(affected.contains(&PathBuf::from("B")));
522        assert!(affected.contains(&PathBuf::from("C")));
523        assert!(affected.contains(&PathBuf::from("D")));
524    }
525
526    #[test]
527    fn test_propagate_respects_strong_dependencies_only() {
528        let mut graph = DependencyGraph::new();
529        // A -> B (strong Import), C -> B (weak Export)
530        graph.add_edge(DependencyEdge::new(
531            PathBuf::from("A"),
532            PathBuf::from("B"),
533            DependencyType::Import, // Strong
534        ));
535        graph.add_edge(DependencyEdge::new(
536            PathBuf::from("C"),
537            PathBuf::from("B"),
538            DependencyType::Export, // Weak
539        ));
540
541        let detector = InvalidationDetector::new(graph);
542        let affected = detector.propagate_invalidation(&PathBuf::from("B"));
543
544        // B changed -> A affected (strong), C NOT affected (weak)
545        assert!(affected.contains(&PathBuf::from("A")));
546        assert!(affected.contains(&PathBuf::from("B")));
547        assert!(
548            !affected.contains(&PathBuf::from("C")),
549            "Weak dependencies should not propagate invalidation"
550        );
551    }
552
553    #[test]
554    fn test_propagate_stops_at_frontier() {
555        let mut graph = DependencyGraph::new();
556        // Two separate chains: A -> B, C -> D
557        graph.add_edge(DependencyEdge::new(
558            PathBuf::from("A"),
559            PathBuf::from("B"),
560            DependencyType::Import,
561        ));
562        graph.add_edge(DependencyEdge::new(
563            PathBuf::from("C"),
564            PathBuf::from("D"),
565            DependencyType::Import,
566        ));
567
568        let detector = InvalidationDetector::new(graph);
569        let affected = detector.propagate_invalidation(&PathBuf::from("B"));
570
571        // B changed -> A affected, but C and D are independent
572        assert_eq!(affected.len(), 2);
573        assert!(affected.contains(&PathBuf::from("A")));
574        assert!(affected.contains(&PathBuf::from("B")));
575        assert!(!affected.contains(&PathBuf::from("C")));
576        assert!(!affected.contains(&PathBuf::from("D")));
577    }
578
579    #[test]
580    fn test_propagate_unknown_file() {
581        let graph = DependencyGraph::new();
582        let detector = InvalidationDetector::new(graph);
583        let affected = detector.propagate_invalidation(&PathBuf::from("unknown.rs"));
584
585        // Unknown file should still be included in result
586        assert_eq!(affected.len(), 1);
587        assert_eq!(affected[0], PathBuf::from("unknown.rs"));
588    }
589
590    // ── topological_sort Tests ───────────────────────────────────────────
591
592    #[test]
593    fn test_topological_sort_linear_chain() {
594        let mut graph = DependencyGraph::new();
595        // A -> B -> C
596        graph.add_edge(DependencyEdge::new(
597            PathBuf::from("A"),
598            PathBuf::from("B"),
599            DependencyType::Import,
600        ));
601        graph.add_edge(DependencyEdge::new(
602            PathBuf::from("B"),
603            PathBuf::from("C"),
604            DependencyType::Import,
605        ));
606
607        let detector = InvalidationDetector::new(graph);
608        let sorted = detector
609            .topological_sort(&[PathBuf::from("A"), PathBuf::from("B"), PathBuf::from("C")])
610            .unwrap();
611
612        assert_eq!(sorted.len(), 3);
613
614        // C must come before B, B before A (dependencies first)
615        let pos_a = sorted
616            .iter()
617            .position(|p| p == &PathBuf::from("A"))
618            .unwrap();
619        let pos_b = sorted
620            .iter()
621            .position(|p| p == &PathBuf::from("B"))
622            .unwrap();
623        let pos_c = sorted
624            .iter()
625            .position(|p| p == &PathBuf::from("C"))
626            .unwrap();
627
628        assert!(pos_c < pos_b, "C must come before B");
629        assert!(pos_b < pos_a, "B must come before A");
630    }
631
632    #[test]
633    fn test_topological_sort_diamond() {
634        let mut graph = DependencyGraph::new();
635        // Diamond: A -> B, A -> C, B -> D, C -> D
636        graph.add_edge(DependencyEdge::new(
637            PathBuf::from("A"),
638            PathBuf::from("B"),
639            DependencyType::Import,
640        ));
641        graph.add_edge(DependencyEdge::new(
642            PathBuf::from("A"),
643            PathBuf::from("C"),
644            DependencyType::Import,
645        ));
646        graph.add_edge(DependencyEdge::new(
647            PathBuf::from("B"),
648            PathBuf::from("D"),
649            DependencyType::Import,
650        ));
651        graph.add_edge(DependencyEdge::new(
652            PathBuf::from("C"),
653            PathBuf::from("D"),
654            DependencyType::Import,
655        ));
656
657        let detector = InvalidationDetector::new(graph);
658        let sorted = detector
659            .topological_sort(&[
660                PathBuf::from("A"),
661                PathBuf::from("B"),
662                PathBuf::from("C"),
663                PathBuf::from("D"),
664            ])
665            .unwrap();
666
667        assert_eq!(sorted.len(), 4);
668
669        let pos_a = sorted
670            .iter()
671            .position(|p| p == &PathBuf::from("A"))
672            .unwrap();
673        let pos_b = sorted
674            .iter()
675            .position(|p| p == &PathBuf::from("B"))
676            .unwrap();
677        let pos_c = sorted
678            .iter()
679            .position(|p| p == &PathBuf::from("C"))
680            .unwrap();
681        let pos_d = sorted
682            .iter()
683            .position(|p| p == &PathBuf::from("D"))
684            .unwrap();
685
686        // D before B and C, B and C before A
687        assert!(pos_d < pos_b, "D must come before B");
688        assert!(pos_d < pos_c, "D must come before C");
689        assert!(pos_b < pos_a, "B must come before A");
690        assert!(pos_c < pos_a, "C must come before A");
691    }
692
693    #[test]
694    fn test_topological_sort_disconnected_components() {
695        let mut graph = DependencyGraph::new();
696        // Two separate chains: A -> B, C -> D
697        graph.add_edge(DependencyEdge::new(
698            PathBuf::from("A"),
699            PathBuf::from("B"),
700            DependencyType::Import,
701        ));
702        graph.add_edge(DependencyEdge::new(
703            PathBuf::from("C"),
704            PathBuf::from("D"),
705            DependencyType::Import,
706        ));
707
708        let detector = InvalidationDetector::new(graph);
709        let sorted = detector
710            .topological_sort(&[
711                PathBuf::from("A"),
712                PathBuf::from("B"),
713                PathBuf::from("C"),
714                PathBuf::from("D"),
715            ])
716            .unwrap();
717
718        assert_eq!(sorted.len(), 4);
719
720        // Verify local ordering within each component
721        let pos_a = sorted
722            .iter()
723            .position(|p| p == &PathBuf::from("A"))
724            .unwrap();
725        let pos_b = sorted
726            .iter()
727            .position(|p| p == &PathBuf::from("B"))
728            .unwrap();
729        let pos_c = sorted
730            .iter()
731            .position(|p| p == &PathBuf::from("C"))
732            .unwrap();
733        let pos_d = sorted
734            .iter()
735            .position(|p| p == &PathBuf::from("D"))
736            .unwrap();
737
738        assert!(pos_b < pos_a, "B must come before A");
739        assert!(pos_d < pos_c, "D must come before C");
740    }
741
742    #[test]
743    fn test_topological_sort_single_file() {
744        let graph = DependencyGraph::new();
745        let detector = InvalidationDetector::new(graph);
746        let sorted = detector
747            .topological_sort(&[PathBuf::from("only.rs")])
748            .unwrap();
749
750        assert_eq!(sorted, vec![PathBuf::from("only.rs")]);
751    }
752
753    #[test]
754    fn test_topological_sort_empty_set() {
755        let graph = DependencyGraph::new();
756        let detector = InvalidationDetector::new(graph);
757        let sorted = detector.topological_sort(&[]).unwrap();
758
759        assert!(sorted.is_empty());
760    }
761
762    #[test]
763    fn test_topological_sort_cycle_error() {
764        let mut graph = DependencyGraph::new();
765        // Cycle: A -> B -> A
766        graph.add_edge(DependencyEdge::new(
767            PathBuf::from("A"),
768            PathBuf::from("B"),
769            DependencyType::Import,
770        ));
771        graph.add_edge(DependencyEdge::new(
772            PathBuf::from("B"),
773            PathBuf::from("A"),
774            DependencyType::Import,
775        ));
776
777        let detector = InvalidationDetector::new(graph);
778        let result = detector.topological_sort(&[PathBuf::from("A"), PathBuf::from("B")]);
779
780        assert!(result.is_err());
781        match result.unwrap_err() {
782            InvalidationError::CircularDependency(cycle) => {
783                assert!(!cycle.is_empty(), "Cycle should contain file paths");
784            }
785            _ => panic!("Expected CircularDependency error"),
786        }
787    }
788
789    #[test]
790    fn test_topological_sort_self_loop() {
791        let mut graph = DependencyGraph::new();
792        // Self-loop: A -> A
793        graph.add_edge(DependencyEdge::new(
794            PathBuf::from("A"),
795            PathBuf::from("A"),
796            DependencyType::Import,
797        ));
798
799        let detector = InvalidationDetector::new(graph);
800        let result = detector.topological_sort(&[PathBuf::from("A")]);
801
802        assert!(result.is_err());
803        match result.unwrap_err() {
804            InvalidationError::CircularDependency(_) => {
805                // Expected
806            }
807            _ => panic!("Expected CircularDependency error"),
808        }
809    }
810
811    // ── compute_invalidation_set Tests ───────────────────────────────────
812
813    #[test]
814    fn test_compute_invalidation_single_change() {
815        let mut graph = DependencyGraph::new();
816        // A -> B
817        graph.add_edge(DependencyEdge::new(
818            PathBuf::from("A"),
819            PathBuf::from("B"),
820            DependencyType::Import,
821        ));
822
823        let detector = InvalidationDetector::new(graph);
824        let result = detector.compute_invalidation_set(&[PathBuf::from("B")]);
825
826        // B changed -> A affected
827        assert_eq!(result.invalidated_files.len(), 2);
828        assert!(result.invalidated_files.contains(&PathBuf::from("A")));
829        assert!(result.invalidated_files.contains(&PathBuf::from("B")));
830
831        // Should have valid analysis order
832        assert_eq!(result.analysis_order.len(), 2);
833        let pos_a = result
834            .analysis_order
835            .iter()
836            .position(|p| p == &PathBuf::from("A"))
837            .unwrap();
838        let pos_b = result
839            .analysis_order
840            .iter()
841            .position(|p| p == &PathBuf::from("B"))
842            .unwrap();
843        assert!(pos_b < pos_a, "B must come before A in analysis order");
844
845        // No cycles
846        assert!(result.circular_dependencies.is_empty());
847    }
848
849    #[test]
850    fn test_compute_invalidation_transitive() {
851        let mut graph = DependencyGraph::new();
852        // A -> B -> C
853        graph.add_edge(DependencyEdge::new(
854            PathBuf::from("A"),
855            PathBuf::from("B"),
856            DependencyType::Import,
857        ));
858        graph.add_edge(DependencyEdge::new(
859            PathBuf::from("B"),
860            PathBuf::from("C"),
861            DependencyType::Import,
862        ));
863
864        let detector = InvalidationDetector::new(graph);
865        let result = detector.compute_invalidation_set(&[PathBuf::from("C")]);
866
867        assert_eq!(result.invalidated_files.len(), 3);
868        assert!(result.invalidated_files.contains(&PathBuf::from("A")));
869        assert!(result.invalidated_files.contains(&PathBuf::from("B")));
870        assert!(result.invalidated_files.contains(&PathBuf::from("C")));
871
872        // Verify correct topological order: C, B, A
873        assert_eq!(result.analysis_order.len(), 3);
874        let pos_a = result
875            .analysis_order
876            .iter()
877            .position(|p| p == &PathBuf::from("A"))
878            .unwrap();
879        let pos_b = result
880            .analysis_order
881            .iter()
882            .position(|p| p == &PathBuf::from("B"))
883            .unwrap();
884        let pos_c = result
885            .analysis_order
886            .iter()
887            .position(|p| p == &PathBuf::from("C"))
888            .unwrap();
889        assert!(pos_c < pos_b);
890        assert!(pos_b < pos_a);
891
892        assert!(result.circular_dependencies.is_empty());
893    }
894
895    #[test]
896    fn test_compute_invalidation_multiple_changes() {
897        let mut graph = DependencyGraph::new();
898        // A -> C, B -> D (two independent chains)
899        graph.add_edge(DependencyEdge::new(
900            PathBuf::from("A"),
901            PathBuf::from("C"),
902            DependencyType::Import,
903        ));
904        graph.add_edge(DependencyEdge::new(
905            PathBuf::from("B"),
906            PathBuf::from("D"),
907            DependencyType::Import,
908        ));
909
910        let detector = InvalidationDetector::new(graph);
911        let result = detector.compute_invalidation_set(&[PathBuf::from("C"), PathBuf::from("D")]);
912
913        assert_eq!(result.invalidated_files.len(), 4);
914        assert!(result.invalidated_files.contains(&PathBuf::from("A")));
915        assert!(result.invalidated_files.contains(&PathBuf::from("B")));
916        assert!(result.invalidated_files.contains(&PathBuf::from("C")));
917        assert!(result.invalidated_files.contains(&PathBuf::from("D")));
918
919        assert!(result.circular_dependencies.is_empty());
920    }
921
922    #[test]
923    fn test_compute_invalidation_empty_changes() {
924        let graph = DependencyGraph::new();
925        let detector = InvalidationDetector::new(graph);
926        let result = detector.compute_invalidation_set(&[]);
927
928        assert!(result.invalidated_files.is_empty());
929        assert!(result.analysis_order.is_empty());
930        assert!(result.circular_dependencies.is_empty());
931    }
932
933    #[test]
934    fn test_compute_invalidation_unknown_files() {
935        let graph = DependencyGraph::new();
936        let detector = InvalidationDetector::new(graph);
937        let result = detector.compute_invalidation_set(&[PathBuf::from("unknown.rs")]);
938
939        // Unknown file should still be included
940        assert_eq!(result.invalidated_files.len(), 1);
941        assert!(
942            result
943                .invalidated_files
944                .contains(&PathBuf::from("unknown.rs"))
945        );
946    }
947
948    #[test]
949    fn test_compute_invalidation_with_cycle() {
950        let mut graph = DependencyGraph::new();
951        // Cycle: A -> B -> A, plus C -> A
952        graph.add_edge(DependencyEdge::new(
953            PathBuf::from("A"),
954            PathBuf::from("B"),
955            DependencyType::Import,
956        ));
957        graph.add_edge(DependencyEdge::new(
958            PathBuf::from("B"),
959            PathBuf::from("A"),
960            DependencyType::Import,
961        ));
962        graph.add_edge(DependencyEdge::new(
963            PathBuf::from("C"),
964            PathBuf::from("A"),
965            DependencyType::Import,
966        ));
967
968        let detector = InvalidationDetector::new(graph);
969        let result = detector.compute_invalidation_set(&[PathBuf::from("A")]);
970
971        // All files should be in invalidated set
972        assert_eq!(result.invalidated_files.len(), 3);
973
974        // Should detect the cycle between A and B
975        assert!(!result.circular_dependencies.is_empty());
976        assert!(
977            result.circular_dependencies.iter().any(|cycle| {
978                cycle.contains(&PathBuf::from("A")) && cycle.contains(&PathBuf::from("B"))
979            }),
980            "Should detect cycle involving A and B"
981        );
982    }
983
984    #[test]
985    fn test_compute_invalidation_multiple_cycles() {
986        let mut graph = DependencyGraph::new();
987        // Two separate cycles: A -> B -> A, C -> D -> C
988        graph.add_edge(DependencyEdge::new(
989            PathBuf::from("A"),
990            PathBuf::from("B"),
991            DependencyType::Import,
992        ));
993        graph.add_edge(DependencyEdge::new(
994            PathBuf::from("B"),
995            PathBuf::from("A"),
996            DependencyType::Import,
997        ));
998        graph.add_edge(DependencyEdge::new(
999            PathBuf::from("C"),
1000            PathBuf::from("D"),
1001            DependencyType::Import,
1002        ));
1003        graph.add_edge(DependencyEdge::new(
1004            PathBuf::from("D"),
1005            PathBuf::from("C"),
1006            DependencyType::Import,
1007        ));
1008
1009        let detector = InvalidationDetector::new(graph);
1010        let result = detector.compute_invalidation_set(&[PathBuf::from("A"), PathBuf::from("C")]);
1011
1012        // Should detect both cycles
1013        assert_eq!(result.circular_dependencies.len(), 2);
1014    }
1015
1016    #[test]
1017    fn test_compute_invalidation_partial_cycle() {
1018        let mut graph = DependencyGraph::new();
1019        // Mixed: A -> B -> C -> B (cycle B-C), D -> A (independent)
1020        graph.add_edge(DependencyEdge::new(
1021            PathBuf::from("A"),
1022            PathBuf::from("B"),
1023            DependencyType::Import,
1024        ));
1025        graph.add_edge(DependencyEdge::new(
1026            PathBuf::from("B"),
1027            PathBuf::from("C"),
1028            DependencyType::Import,
1029        ));
1030        graph.add_edge(DependencyEdge::new(
1031            PathBuf::from("C"),
1032            PathBuf::from("B"),
1033            DependencyType::Import,
1034        ));
1035        graph.add_edge(DependencyEdge::new(
1036            PathBuf::from("D"),
1037            PathBuf::from("A"),
1038            DependencyType::Import,
1039        ));
1040
1041        let detector = InvalidationDetector::new(graph);
1042        let result = detector.compute_invalidation_set(&[PathBuf::from("B")]);
1043
1044        // Should detect cycle between B and C
1045        assert!(!result.circular_dependencies.is_empty());
1046        let cycle = &result.circular_dependencies[0];
1047        assert!(cycle.contains(&PathBuf::from("B")));
1048        assert!(cycle.contains(&PathBuf::from("C")));
1049        // A and D should not be in the cycle
1050        assert!(!cycle.contains(&PathBuf::from("A")));
1051        assert!(!cycle.contains(&PathBuf::from("D")));
1052    }
1053
1054    // ── Tarjan's SCC Algorithm Tests ─────────────────────────────────────
1055
1056    #[test]
1057    fn test_find_scc_no_cycles() {
1058        let mut graph = DependencyGraph::new();
1059        // Linear: A -> B -> C
1060        graph.add_edge(DependencyEdge::new(
1061            PathBuf::from("A"),
1062            PathBuf::from("B"),
1063            DependencyType::Import,
1064        ));
1065        graph.add_edge(DependencyEdge::new(
1066            PathBuf::from("B"),
1067            PathBuf::from("C"),
1068            DependencyType::Import,
1069        ));
1070
1071        let detector = InvalidationDetector::new(graph);
1072        let files: RapidSet<PathBuf> = [PathBuf::from("A"), PathBuf::from("B"), PathBuf::from("C")]
1073            .into_iter()
1074            .collect();
1075        let sccs = detector.find_strongly_connected_components(&files);
1076
1077        // No non-trivial SCCs (all components have size 1)
1078        assert!(sccs.is_empty());
1079    }
1080
1081    #[test]
1082    fn test_find_scc_simple_cycle() {
1083        let mut graph = DependencyGraph::new();
1084        // Cycle: A -> B -> A
1085        graph.add_edge(DependencyEdge::new(
1086            PathBuf::from("A"),
1087            PathBuf::from("B"),
1088            DependencyType::Import,
1089        ));
1090        graph.add_edge(DependencyEdge::new(
1091            PathBuf::from("B"),
1092            PathBuf::from("A"),
1093            DependencyType::Import,
1094        ));
1095
1096        let detector = InvalidationDetector::new(graph);
1097        let files: RapidSet<PathBuf> = [PathBuf::from("A"), PathBuf::from("B")]
1098            .into_iter()
1099            .collect();
1100        let sccs = detector.find_strongly_connected_components(&files);
1101
1102        assert_eq!(sccs.len(), 1);
1103        assert_eq!(sccs[0].len(), 2);
1104        assert!(sccs[0].contains(&PathBuf::from("A")));
1105        assert!(sccs[0].contains(&PathBuf::from("B")));
1106    }
1107
1108    #[test]
1109    fn test_find_scc_self_loop() {
1110        let mut graph = DependencyGraph::new();
1111        // Self-loop: A -> A
1112        graph.add_edge(DependencyEdge::new(
1113            PathBuf::from("A"),
1114            PathBuf::from("A"),
1115            DependencyType::Import,
1116        ));
1117
1118        let detector = InvalidationDetector::new(graph);
1119        let files: RapidSet<PathBuf> = [PathBuf::from("A")].into_iter().collect();
1120        let sccs = detector.find_strongly_connected_components(&files);
1121
1122        // Self-loop creates a non-trivial SCC of size 1
1123        assert_eq!(sccs.len(), 1);
1124        assert_eq!(sccs[0].len(), 1);
1125        assert_eq!(sccs[0][0], PathBuf::from("A"));
1126    }
1127
1128    #[test]
1129    fn test_find_scc_multiple_cycles() {
1130        let mut graph = DependencyGraph::new();
1131        // Two cycles: A -> B -> A, C -> D -> C
1132        graph.add_edge(DependencyEdge::new(
1133            PathBuf::from("A"),
1134            PathBuf::from("B"),
1135            DependencyType::Import,
1136        ));
1137        graph.add_edge(DependencyEdge::new(
1138            PathBuf::from("B"),
1139            PathBuf::from("A"),
1140            DependencyType::Import,
1141        ));
1142        graph.add_edge(DependencyEdge::new(
1143            PathBuf::from("C"),
1144            PathBuf::from("D"),
1145            DependencyType::Import,
1146        ));
1147        graph.add_edge(DependencyEdge::new(
1148            PathBuf::from("D"),
1149            PathBuf::from("C"),
1150            DependencyType::Import,
1151        ));
1152
1153        let detector = InvalidationDetector::new(graph);
1154        let files: RapidSet<PathBuf> = [
1155            PathBuf::from("A"),
1156            PathBuf::from("B"),
1157            PathBuf::from("C"),
1158            PathBuf::from("D"),
1159        ]
1160        .into_iter()
1161        .collect();
1162        let sccs = detector.find_strongly_connected_components(&files);
1163
1164        assert_eq!(sccs.len(), 2);
1165    }
1166
1167    #[test]
1168    fn test_find_scc_nested_components() {
1169        let mut graph = DependencyGraph::new();
1170        // Complex: A -> B -> C -> B (B-C cycle), A -> D
1171        graph.add_edge(DependencyEdge::new(
1172            PathBuf::from("A"),
1173            PathBuf::from("B"),
1174            DependencyType::Import,
1175        ));
1176        graph.add_edge(DependencyEdge::new(
1177            PathBuf::from("B"),
1178            PathBuf::from("C"),
1179            DependencyType::Import,
1180        ));
1181        graph.add_edge(DependencyEdge::new(
1182            PathBuf::from("C"),
1183            PathBuf::from("B"),
1184            DependencyType::Import,
1185        ));
1186        graph.add_edge(DependencyEdge::new(
1187            PathBuf::from("A"),
1188            PathBuf::from("D"),
1189            DependencyType::Import,
1190        ));
1191
1192        let detector = InvalidationDetector::new(graph);
1193        let files: RapidSet<PathBuf> = [
1194            PathBuf::from("A"),
1195            PathBuf::from("B"),
1196            PathBuf::from("C"),
1197            PathBuf::from("D"),
1198        ]
1199        .into_iter()
1200        .collect();
1201        let sccs = detector.find_strongly_connected_components(&files);
1202
1203        // Should find one SCC containing B and C
1204        assert_eq!(sccs.len(), 1);
1205        assert_eq!(sccs[0].len(), 2);
1206        assert!(sccs[0].contains(&PathBuf::from("B")));
1207        assert!(sccs[0].contains(&PathBuf::from("C")));
1208    }
1209
1210    // ── Performance Tests ────────────────────────────────────────────────
1211
1212    #[test]
1213    fn test_large_graph_performance() {
1214        // Build a graph with 1000 nodes in a chain
1215        let mut graph = DependencyGraph::new();
1216        for i in 0..999 {
1217            graph.add_edge(DependencyEdge::new(
1218                PathBuf::from(format!("file_{}", i)),
1219                PathBuf::from(format!("file_{}", i + 1)),
1220                DependencyType::Import,
1221            ));
1222        }
1223
1224        let detector = InvalidationDetector::new(graph);
1225        let start = std::time::Instant::now();
1226        let result = detector.compute_invalidation_set(&[PathBuf::from("file_500")]);
1227        let duration = start.elapsed();
1228
1229        // Should complete quickly with O(V+E) complexity
1230        assert!(
1231            duration.as_millis() < 50,
1232            "Large graph processing took {}ms (expected < 50ms)",
1233            duration.as_millis()
1234        );
1235        assert!(result.invalidated_files.len() >= 500);
1236    }
1237
1238    #[test]
1239    fn test_wide_fanout_performance() {
1240        // One file with 100 dependents
1241        let mut graph = DependencyGraph::new();
1242        for i in 0..100 {
1243            graph.add_edge(DependencyEdge::new(
1244                PathBuf::from(format!("dependent_{}", i)),
1245                PathBuf::from("core.rs"),
1246                DependencyType::Import,
1247            ));
1248        }
1249
1250        let detector = InvalidationDetector::new(graph);
1251        let start = std::time::Instant::now();
1252        let result = detector.compute_invalidation_set(&[PathBuf::from("core.rs")]);
1253        let duration = start.elapsed();
1254
1255        assert!(duration.as_millis() < 10);
1256        assert_eq!(result.invalidated_files.len(), 101); // core + 100 dependents
1257    }
1258}
thread_flow/incremental/invalidation.rs

thread_flow/incremental/
invalidation.rs
