thread_flow/incremental/
graph.rs

1// SPDX-FileCopyrightText: 2025 Knitli Inc. <knitli@knit.li>
2// SPDX-License-Identifier: AGPL-3.0-or-later
3
4//! Dependency graph construction and traversal algorithms.
5//!
6//! This module implements the dependency graph that tracks relationships
7//! between files in the analyzed codebase. It provides:
8//!
9//! - **BFS traversal** for finding all files affected by a change
10//! - **Topological sort** for ordering reanalysis to respect dependencies
11//! - **Cycle detection** during topological sort
12//! - **Bidirectional queries** for both dependencies and dependents
13//!
14//! ## Design Pattern
15//!
16//! Adapted from ReCoco's scope traversal (analyzer.rs:656-668) and
17//! `is_op_scope_descendant` ancestor chain traversal.
18
19use super::types::{AnalysisDefFingerprint, DependencyEdge, DependencyStrength};
20use metrics::gauge;
21use std::collections::VecDeque;
22use std::fmt;
23use std::path::{Path, PathBuf};
24use thread_utilities::{RapidMap, RapidSet};
25
26/// Errors that can occur during dependency graph operations.
27#[derive(Debug)]
28pub enum GraphError {
29    /// A cyclic dependency was detected during topological sort.
30    CyclicDependency(PathBuf),
31}
32
33impl fmt::Display for GraphError {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        match self {
36            GraphError::CyclicDependency(path) => write!(
37                f,
38                "Cyclic dependency detected involving file: {}\n\
39                 Hint: Use `thread deps --cycles` to visualize the cycle",
40                path.display()
41            ),
42        }
43    }
44}
45
46impl std::error::Error for GraphError {}
47
48/// A dependency graph tracking relationships between source files.
49///
50/// The graph is directed: edges point from dependent files to their
51/// dependencies. For example, if `main.rs` imports `utils.rs`, there is
52/// an edge from `main.rs` to `utils.rs`.
53///
54/// The graph maintains both forward (dependencies) and reverse (dependents)
55/// adjacency lists for efficient bidirectional traversal.
56///
57/// # Examples
58///
59/// ```rust
60/// use thread_flow::incremental::graph::DependencyGraph;
61/// use thread_flow::incremental::types::{DependencyEdge, DependencyType};
62/// use std::path::PathBuf;
63/// use thread_utilities::RapidSet;
64///
65/// let mut graph = DependencyGraph::new();
66///
67/// // main.rs depends on utils.rs
68/// graph.add_edge(DependencyEdge::new(
69///     PathBuf::from("main.rs"),
70///     PathBuf::from("utils.rs"),
71///     DependencyType::Import,
72/// ));
73///
74/// // Find what main.rs depends on
75/// let deps = graph.get_dependencies(&PathBuf::from("main.rs"));
76/// assert_eq!(deps.len(), 1);
77/// assert_eq!(deps[0].to, PathBuf::from("utils.rs"));
78///
79/// // Find what depends on utils.rs
80/// let dependents = graph.get_dependents(&PathBuf::from("utils.rs"));
81/// assert_eq!(dependents.len(), 1);
82/// assert_eq!(dependents[0].from, PathBuf::from("main.rs"));
83/// ```
84#[derive(Debug, Clone)]
85pub struct DependencyGraph {
86    /// Fingerprint state for each tracked file.
87    pub nodes: RapidMap<PathBuf, AnalysisDefFingerprint>,
88
89    /// All dependency edges in the graph.
90    pub edges: Vec<DependencyEdge>,
91
92    /// Forward adjacency: file -> files it depends on.
93    forward_adj: RapidMap<PathBuf, Vec<usize>>,
94
95    /// Reverse adjacency: file -> files that depend on it.
96    reverse_adj: RapidMap<PathBuf, Vec<usize>>,
97}
98
99impl DependencyGraph {
100    /// Creates a new empty dependency graph.
101    ///
102    /// # Examples
103    ///
104    /// ```rust
105    /// use thread_flow::incremental::graph::DependencyGraph;
106    ///
107    /// let graph = DependencyGraph::new();
108    /// assert_eq!(graph.node_count(), 0);
109    /// assert_eq!(graph.edge_count(), 0);
110    /// ```
111    pub fn new() -> Self {
112        Self {
113            nodes: thread_utilities::get_map(),
114            edges: Vec::new(),
115            forward_adj: thread_utilities::get_map(),
116            reverse_adj: thread_utilities::get_map(),
117        }
118    }
119
120    /// Ensures a file node exists in the graph without adding any edges.
121    ///
122    /// This is useful when a file has been processed but no dependency edges
123    /// were extracted (e.g., a file with no imports, or a Go file where all
124    /// imports resolve to external packages without a configured module path).
125    ///
126    /// # Arguments
127    ///
128    /// * `file` - Path of the file to add as a node.
129    ///
130    /// # Examples
131    ///
132    /// ```rust
133    /// use thread_flow::incremental::graph::DependencyGraph;
134    /// use std::path::Path;
135    ///
136    /// let mut graph = DependencyGraph::new();
137    /// graph.add_node(Path::new("main.go"));
138    /// assert!(graph.contains_node(Path::new("main.go")));
139    /// assert_eq!(graph.node_count(), 1);
140    /// assert_eq!(graph.edge_count(), 0);
141    /// ```
142    pub fn add_node(&mut self, file: &Path) {
143        self.ensure_node(file);
144    }
145
146    /// Adds a dependency edge to the graph.
147    ///
148    /// Both the source (`from`) and target (`to`) nodes are automatically
149    /// registered if they do not already exist. Adjacency lists are updated
150    /// for both forward and reverse lookups.
151    ///
152    /// # Arguments
153    ///
154    /// * `edge` - The dependency edge to add.
155    ///
156    /// # Examples
157    ///
158    /// ```rust
159    /// use thread_flow::incremental::graph::DependencyGraph;
160    /// use thread_flow::incremental::types::{DependencyEdge, DependencyType};
161    /// use std::path::PathBuf;
162    ///
163    /// let mut graph = DependencyGraph::new();
164    /// graph.add_edge(DependencyEdge::new(
165    ///     PathBuf::from("a.rs"),
166    ///     PathBuf::from("b.rs"),
167    ///     DependencyType::Import,
168    /// ));
169    /// assert_eq!(graph.edge_count(), 1);
170    /// assert_eq!(graph.node_count(), 2);
171    /// ```
172    pub fn add_edge(&mut self, edge: DependencyEdge) {
173        let idx = self.edges.len();
174
175        // Ensure nodes exist
176        self.ensure_node(&edge.from);
177        self.ensure_node(&edge.to);
178
179        // Update adjacency lists
180        self.forward_adj
181            .entry(edge.from.clone())
182            .or_default()
183            .push(idx);
184        self.reverse_adj
185            .entry(edge.to.clone())
186            .or_default()
187            .push(idx);
188
189        self.edges.push(edge);
190
191        // Update metrics
192        gauge!("graph_nodes").set(self.nodes.len() as f64);
193        gauge!("graph_edges").set(self.edges.len() as f64);
194    }
195
196    /// Returns all direct dependencies of a file (files it depends on).
197    ///
198    /// # Arguments
199    ///
200    /// * `file` - The file to query dependencies for.
201    ///
202    /// # Returns
203    ///
204    /// A vector of references to dependency edges where `from` is the given file.
205    pub fn get_dependencies(&self, file: &Path) -> Vec<&DependencyEdge> {
206        self.forward_adj
207            .get(file)
208            .map(|indices| indices.iter().map(|&i| &self.edges[i]).collect())
209            .unwrap_or_default()
210    }
211
212    /// Returns all direct dependents of a file (files that depend on it).
213    ///
214    /// # Arguments
215    ///
216    /// * `file` - The file to query dependents for.
217    ///
218    /// # Returns
219    ///
220    /// A vector of references to dependency edges where `to` is the given file.
221    pub fn get_dependents(&self, file: &Path) -> Vec<&DependencyEdge> {
222        self.reverse_adj
223            .get(file)
224            .map(|indices| indices.iter().map(|&i| &self.edges[i]).collect())
225            .unwrap_or_default()
226    }
227
228    /// Finds all files affected by changes to the given set of files.
229    ///
230    /// Uses BFS traversal following reverse dependency edges (dependents)
231    /// to discover the full set of files that need reanalysis. Only
232    /// [`DependencyStrength::Strong`] edges trigger cascading invalidation.
233    ///
234    /// **Algorithm complexity**: O(V + E) where V = files, E = dependency edges.
235    ///
236    /// # Arguments
237    ///
238    /// * `changed_files` - Set of files that have been modified.
239    ///
240    /// # Returns
241    ///
242    /// Set of all affected files, including the changed files themselves.
243    ///
244    /// # Examples
245    ///
246    /// ```rust
247    /// use thread_flow::incremental::graph::DependencyGraph;
248    /// use thread_flow::incremental::types::{DependencyEdge, DependencyType};
249    /// use std::path::PathBuf;
250    /// use thread_utilities::RapidSet;
251    ///
252    /// let mut graph = DependencyGraph::new();
253    ///
254    /// // A -> B -> C (A depends on B, B depends on C)
255    /// graph.add_edge(DependencyEdge::new(
256    ///     PathBuf::from("A"), PathBuf::from("B"), DependencyType::Import,
257    /// ));
258    /// graph.add_edge(DependencyEdge::new(
259    ///     PathBuf::from("B"), PathBuf::from("C"), DependencyType::Import,
260    /// ));
261    ///
262    /// // Change C -> affects B and A
263    /// let changed = RapidSet::from([PathBuf::from("C")]);
264    /// let affected = graph.find_affected_files(&changed);
265    /// assert!(affected.contains(&PathBuf::from("A")));
266    /// assert!(affected.contains(&PathBuf::from("B")));
267    /// assert!(affected.contains(&PathBuf::from("C")));
268    /// ```
269    pub fn find_affected_files(&self, changed_files: &RapidSet<PathBuf>) -> RapidSet<PathBuf> {
270        let mut affected = thread_utilities::get_set();
271        let mut visited = thread_utilities::get_set();
272        let mut queue: VecDeque<PathBuf> = changed_files.iter().cloned().collect();
273
274        while let Some(file) = queue.pop_front() {
275            if !visited.insert(file.clone()) {
276                continue;
277            }
278
279            affected.insert(file.clone());
280
281            // Follow reverse edges (files that depend on this file)
282            for edge in self.get_dependents(&file) {
283                if edge.effective_strength() == DependencyStrength::Strong {
284                    queue.push_back(edge.from.clone());
285                }
286            }
287        }
288
289        affected
290    }
291
292    /// Performs topological sort on the given subset of files.
293    ///
294    /// Returns files in dependency order: dependencies appear before
295    /// their dependents. This ordering ensures correct incremental
296    /// reanalysis.
297    ///
298    /// Detects cyclic dependencies and returns [`GraphError::CyclicDependency`]
299    /// if a cycle is found.
300    ///
301    /// **Algorithm complexity**: O(V + E) using DFS.
302    ///
303    /// # Arguments
304    ///
305    /// * `files` - The subset of files to sort.
306    ///
307    /// # Errors
308    ///
309    /// Returns [`GraphError::CyclicDependency`] if a cycle is detected.
310    ///
311    /// # Examples
312    ///
313    /// ```rust
314    /// use thread_flow::incremental::graph::DependencyGraph;
315    /// use thread_flow::incremental::types::{DependencyEdge, DependencyType};
316    /// use std::path::PathBuf;
317    /// use thread_utilities::RapidSet;
318    ///
319    /// let mut graph = DependencyGraph::new();
320    /// // A depends on B, B depends on C
321    /// graph.add_edge(DependencyEdge::new(
322    ///     PathBuf::from("A"), PathBuf::from("B"), DependencyType::Import,
323    /// ));
324    /// graph.add_edge(DependencyEdge::new(
325    ///     PathBuf::from("B"), PathBuf::from("C"), DependencyType::Import,
326    /// ));
327    ///
328    /// let files = RapidSet::from([
329    ///     PathBuf::from("A"), PathBuf::from("B"), PathBuf::from("C"),
330    /// ]);
331    /// let sorted = graph.topological_sort(&files).unwrap();
332    /// // C should come before B, B before A
333    /// let pos_a = sorted.iter().position(|p| p == &PathBuf::from("A")).unwrap();
334    /// let pos_b = sorted.iter().position(|p| p == &PathBuf::from("B")).unwrap();
335    /// let pos_c = sorted.iter().position(|p| p == &PathBuf::from("C")).unwrap();
336    /// assert!(pos_c < pos_b);
337    /// assert!(pos_b < pos_a);
338    /// ```
339    pub fn topological_sort(&self, files: &RapidSet<PathBuf>) -> Result<Vec<PathBuf>, GraphError> {
340        let mut sorted = Vec::new();
341        let mut visited = thread_utilities::get_set();
342        let mut temp_mark = thread_utilities::get_set();
343
344        for file in files {
345            if !visited.contains(file) {
346                self.visit_node(file, files, &mut visited, &mut temp_mark, &mut sorted)?;
347            }
348        }
349
350        // DFS post-order naturally produces dependency-first ordering:
351        // dependencies are pushed before their dependents.
352        Ok(sorted)
353    }
354
355    /// Returns the number of nodes (files) in the graph.
356    pub fn node_count(&self) -> usize {
357        self.nodes.len()
358    }
359
360    /// Returns the number of edges in the graph.
361    pub fn edge_count(&self) -> usize {
362        self.edges.len()
363    }
364
365    /// Checks whether the graph contains a node for the given file.
366    pub fn contains_node(&self, file: &Path) -> bool {
367        self.nodes.contains_key(file)
368    }
369
370    /// Validates graph integrity.
371    ///
372    /// Checks for dangling edges (edges referencing nodes not in the graph)
373    /// and other structural issues.
374    ///
375    /// # Returns
376    ///
377    /// `Ok(())` if the graph is structurally valid, or a [`GraphError`] otherwise.
378    pub fn validate(&self) -> Result<(), GraphError> {
379        for edge in &self.edges {
380            if !self.nodes.contains_key(&edge.from) {
381                return Err(GraphError::CyclicDependency(edge.from.clone()));
382            }
383            if !self.nodes.contains_key(&edge.to) {
384                return Err(GraphError::CyclicDependency(edge.to.clone()));
385            }
386        }
387        Ok(())
388    }
389
390    /// Removes all edges and nodes from the graph.
391    pub fn clear(&mut self) {
392        self.nodes.clear();
393        self.edges.clear();
394        self.forward_adj.clear();
395        self.reverse_adj.clear();
396    }
397
398    // ── Private helpers ──────────────────────────────────────────────────
399
400    /// Ensures a node exists in the graph for the given file path.
401    /// Creates a default fingerprint entry if the node does not exist.
402    fn ensure_node(&mut self, file: &Path) {
403        self.nodes
404            .entry(file.to_path_buf())
405            .or_insert_with(|| AnalysisDefFingerprint::new(b""));
406    }
407
408    /// DFS visit for topological sort with cycle detection.
409    fn visit_node(
410        &self,
411        file: &Path,
412        subset: &RapidSet<PathBuf>,
413        visited: &mut RapidSet<PathBuf>,
414        temp_mark: &mut RapidSet<PathBuf>,
415        sorted: &mut Vec<PathBuf>,
416    ) -> Result<(), GraphError> {
417        let file_buf = file.to_path_buf();
418
419        if temp_mark.contains(&file_buf) {
420            return Err(GraphError::CyclicDependency(file_buf));
421        }
422
423        if visited.contains(&file_buf) {
424            return Ok(());
425        }
426
427        temp_mark.insert(file_buf.clone());
428
429        // Visit dependencies (forward edges) that are in our subset
430        for edge in self.get_dependencies(file) {
431            if subset.contains(&edge.to) {
432                self.visit_node(&edge.to, subset, visited, temp_mark, sorted)?;
433            }
434        }
435
436        temp_mark.remove(&file_buf);
437        visited.insert(file_buf.clone());
438        sorted.push(file_buf);
439
440        Ok(())
441    }
442}
443
444impl Default for DependencyGraph {
445    fn default() -> Self {
446        Self::new()
447    }
448}
449
450// ─── Tests (TDD: Written BEFORE implementation) ──────────────────────────────
451
452#[cfg(test)]
453mod tests {
454    use super::*;
455    use crate::incremental::types::DependencyType;
456
457    // ── Construction Tests ───────────────────────────────────────────────
458
459    #[test]
460    fn test_graph_new_is_empty() {
461        let graph = DependencyGraph::new();
462        assert_eq!(graph.node_count(), 0);
463        assert_eq!(graph.edge_count(), 0);
464    }
465
466    #[test]
467    fn test_graph_default_is_empty() {
468        let graph = DependencyGraph::default();
469        assert_eq!(graph.node_count(), 0);
470        assert_eq!(graph.edge_count(), 0);
471    }
472
473    #[test]
474    fn test_graph_add_edge_creates_nodes() {
475        let mut graph = DependencyGraph::new();
476        graph.add_edge(DependencyEdge::new(
477            PathBuf::from("a.rs"),
478            PathBuf::from("b.rs"),
479            DependencyType::Import,
480        ));
481
482        assert_eq!(graph.node_count(), 2);
483        assert_eq!(graph.edge_count(), 1);
484        assert!(graph.contains_node(Path::new("a.rs")));
485        assert!(graph.contains_node(Path::new("b.rs")));
486    }
487
488    #[test]
489    fn test_graph_add_multiple_edges() {
490        let mut graph = DependencyGraph::new();
491        graph.add_edge(DependencyEdge::new(
492            PathBuf::from("a.rs"),
493            PathBuf::from("b.rs"),
494            DependencyType::Import,
495        ));
496        graph.add_edge(DependencyEdge::new(
497            PathBuf::from("a.rs"),
498            PathBuf::from("c.rs"),
499            DependencyType::Import,
500        ));
501        graph.add_edge(DependencyEdge::new(
502            PathBuf::from("b.rs"),
503            PathBuf::from("c.rs"),
504            DependencyType::Import,
505        ));
506
507        assert_eq!(graph.node_count(), 3);
508        assert_eq!(graph.edge_count(), 3);
509    }
510
511    #[test]
512    fn test_graph_add_edge_no_duplicate_nodes() {
513        let mut graph = DependencyGraph::new();
514        graph.add_edge(DependencyEdge::new(
515            PathBuf::from("a.rs"),
516            PathBuf::from("b.rs"),
517            DependencyType::Import,
518        ));
519        graph.add_edge(DependencyEdge::new(
520            PathBuf::from("a.rs"),
521            PathBuf::from("c.rs"),
522            DependencyType::Import,
523        ));
524
525        // "a.rs" appears in two edges but should only be one node
526        assert_eq!(graph.node_count(), 3);
527    }
528
529    // ── get_dependencies Tests ───────────────────────────────────────────
530
531    #[test]
532    fn test_get_dependencies_empty_graph() {
533        let graph = DependencyGraph::new();
534        let deps = graph.get_dependencies(Path::new("nonexistent.rs"));
535        assert!(deps.is_empty());
536    }
537
538    #[test]
539    fn test_get_dependencies_returns_forward_edges() {
540        let mut graph = DependencyGraph::new();
541        graph.add_edge(DependencyEdge::new(
542            PathBuf::from("main.rs"),
543            PathBuf::from("utils.rs"),
544            DependencyType::Import,
545        ));
546        graph.add_edge(DependencyEdge::new(
547            PathBuf::from("main.rs"),
548            PathBuf::from("config.rs"),
549            DependencyType::Import,
550        ));
551
552        let deps = graph.get_dependencies(Path::new("main.rs"));
553        assert_eq!(deps.len(), 2);
554
555        let dep_targets: RapidSet<_> = deps.iter().map(|e| &e.to).collect();
556        assert!(dep_targets.contains(&PathBuf::from("utils.rs")));
557        assert!(dep_targets.contains(&PathBuf::from("config.rs")));
558    }
559
560    #[test]
561    fn test_get_dependencies_leaf_node_has_none() {
562        let mut graph = DependencyGraph::new();
563        graph.add_edge(DependencyEdge::new(
564            PathBuf::from("main.rs"),
565            PathBuf::from("utils.rs"),
566            DependencyType::Import,
567        ));
568
569        // utils.rs is a leaf - no outgoing edges
570        let deps = graph.get_dependencies(Path::new("utils.rs"));
571        assert!(deps.is_empty());
572    }
573
574    // ── get_dependents Tests ─────────────────────────────────────────────
575
576    #[test]
577    fn test_get_dependents_empty_graph() {
578        let graph = DependencyGraph::new();
579        let deps = graph.get_dependents(Path::new("nonexistent.rs"));
580        assert!(deps.is_empty());
581    }
582
583    #[test]
584    fn test_get_dependents_returns_reverse_edges() {
585        let mut graph = DependencyGraph::new();
586        graph.add_edge(DependencyEdge::new(
587            PathBuf::from("main.rs"),
588            PathBuf::from("utils.rs"),
589            DependencyType::Import,
590        ));
591        graph.add_edge(DependencyEdge::new(
592            PathBuf::from("lib.rs"),
593            PathBuf::from("utils.rs"),
594            DependencyType::Import,
595        ));
596
597        let dependents = graph.get_dependents(Path::new("utils.rs"));
598        assert_eq!(dependents.len(), 2);
599
600        let dependent_sources: RapidSet<_> = dependents.iter().map(|e| &e.from).collect();
601        assert!(dependent_sources.contains(&PathBuf::from("main.rs")));
602        assert!(dependent_sources.contains(&PathBuf::from("lib.rs")));
603    }
604
605    #[test]
606    fn test_get_dependents_root_node_has_none() {
607        let mut graph = DependencyGraph::new();
608        graph.add_edge(DependencyEdge::new(
609            PathBuf::from("main.rs"),
610            PathBuf::from("utils.rs"),
611            DependencyType::Import,
612        ));
613
614        // main.rs is a root - nothing depends on it
615        let dependents = graph.get_dependents(Path::new("main.rs"));
616        assert!(dependents.is_empty());
617    }
618
619    // ── find_affected_files Tests ────────────────────────────────────────
620
621    #[test]
622    fn test_find_affected_files_single_change() {
623        let mut graph = DependencyGraph::new();
624
625        // main.rs -> utils.rs
626        graph.add_edge(DependencyEdge::new(
627            PathBuf::from("main.rs"),
628            PathBuf::from("utils.rs"),
629            DependencyType::Import,
630        ));
631
632        let changed: thread_utilities::RapidSet<PathBuf> =
633            [PathBuf::from("utils.rs")].into_iter().collect();
634        let affected = graph.find_affected_files(&changed);
635
636        assert!(affected.contains(&PathBuf::from("utils.rs")));
637        assert!(affected.contains(&PathBuf::from("main.rs")));
638        assert_eq!(affected.len(), 2);
639    }
640
641    #[test]
642    fn test_find_affected_files_transitive() {
643        let mut graph = DependencyGraph::new();
644
645        // A -> B -> C (A depends on B, B depends on C)
646        graph.add_edge(DependencyEdge::new(
647            PathBuf::from("A"),
648            PathBuf::from("B"),
649            DependencyType::Import,
650        ));
651        graph.add_edge(DependencyEdge::new(
652            PathBuf::from("B"),
653            PathBuf::from("C"),
654            DependencyType::Import,
655        ));
656
657        let changed: thread_utilities::RapidSet<PathBuf> =
658            [PathBuf::from("C")].into_iter().collect();
659        let affected = graph.find_affected_files(&changed);
660
661        assert_eq!(affected.len(), 3);
662        assert!(affected.contains(&PathBuf::from("A")));
663        assert!(affected.contains(&PathBuf::from("B")));
664        assert!(affected.contains(&PathBuf::from("C")));
665    }
666
667    #[test]
668    fn test_find_affected_files_diamond_dependency() {
669        let mut graph = DependencyGraph::new();
670
671        // Diamond: A -> B, A -> C, B -> D, C -> D
672        graph.add_edge(DependencyEdge::new(
673            PathBuf::from("A"),
674            PathBuf::from("B"),
675            DependencyType::Import,
676        ));
677        graph.add_edge(DependencyEdge::new(
678            PathBuf::from("A"),
679            PathBuf::from("C"),
680            DependencyType::Import,
681        ));
682        graph.add_edge(DependencyEdge::new(
683            PathBuf::from("B"),
684            PathBuf::from("D"),
685            DependencyType::Import,
686        ));
687        graph.add_edge(DependencyEdge::new(
688            PathBuf::from("C"),
689            PathBuf::from("D"),
690            DependencyType::Import,
691        ));
692
693        let changed: thread_utilities::RapidSet<PathBuf> =
694            [PathBuf::from("D")].into_iter().collect();
695        let affected = graph.find_affected_files(&changed);
696
697        assert_eq!(affected.len(), 4);
698        assert!(affected.contains(&PathBuf::from("A")));
699        assert!(affected.contains(&PathBuf::from("B")));
700        assert!(affected.contains(&PathBuf::from("C")));
701        assert!(affected.contains(&PathBuf::from("D")));
702    }
703
704    #[test]
705    fn test_find_affected_files_isolated_node() {
706        let mut graph = DependencyGraph::new();
707
708        // A -> B, C is isolated
709        graph.add_edge(DependencyEdge::new(
710            PathBuf::from("A"),
711            PathBuf::from("B"),
712            DependencyType::Import,
713        ));
714        // Add C as an isolated node
715        graph.add_edge(DependencyEdge::new(
716            PathBuf::from("C"),
717            PathBuf::from("D"),
718            DependencyType::Import,
719        ));
720
721        let changed: thread_utilities::RapidSet<PathBuf> =
722            [PathBuf::from("B")].into_iter().collect();
723        let affected = graph.find_affected_files(&changed);
724
725        assert!(affected.contains(&PathBuf::from("A")));
726        assert!(affected.contains(&PathBuf::from("B")));
727        assert!(!affected.contains(&PathBuf::from("C")));
728        assert!(!affected.contains(&PathBuf::from("D")));
729    }
730
731    #[test]
732    fn test_find_affected_files_weak_dependency_not_followed() {
733        let mut graph = DependencyGraph::new();
734
735        // A -> B (strong import), C -> B (weak export)
736        graph.add_edge(DependencyEdge::new(
737            PathBuf::from("A"),
738            PathBuf::from("B"),
739            DependencyType::Import, // Strong
740        ));
741        graph.add_edge(DependencyEdge::new(
742            PathBuf::from("C"),
743            PathBuf::from("B"),
744            DependencyType::Export, // Weak
745        ));
746
747        let changed: thread_utilities::RapidSet<PathBuf> =
748            [PathBuf::from("B")].into_iter().collect();
749        let affected = graph.find_affected_files(&changed);
750
751        assert!(affected.contains(&PathBuf::from("A")));
752        assert!(affected.contains(&PathBuf::from("B")));
753        // C has a weak (Export) dependency on B, should NOT be affected
754        assert!(
755            !affected.contains(&PathBuf::from("C")),
756            "Weak dependencies should not propagate invalidation"
757        );
758    }
759
760    #[test]
761    fn test_find_affected_files_empty_changed_set() {
762        let mut graph = DependencyGraph::new();
763        graph.add_edge(DependencyEdge::new(
764            PathBuf::from("A"),
765            PathBuf::from("B"),
766            DependencyType::Import,
767        ));
768
769        let changed = thread_utilities::get_set();
770        let affected = graph.find_affected_files(&changed);
771        assert!(affected.is_empty());
772    }
773
774    #[test]
775    fn test_find_affected_files_unknown_file() {
776        let graph = DependencyGraph::new();
777        let changed: thread_utilities::RapidSet<PathBuf> =
778            [PathBuf::from("nonexistent.rs")].into_iter().collect();
779        let affected = graph.find_affected_files(&changed);
780
781        // The changed file itself is always included
782        assert_eq!(affected.len(), 1);
783        assert!(affected.contains(&PathBuf::from("nonexistent.rs")));
784    }
785
786    #[test]
787    fn test_find_affected_files_multiple_changes() {
788        let mut graph = DependencyGraph::new();
789
790        // A -> C, B -> C (both A and B depend on C independently)
791        graph.add_edge(DependencyEdge::new(
792            PathBuf::from("A"),
793            PathBuf::from("C"),
794            DependencyType::Import,
795        ));
796        graph.add_edge(DependencyEdge::new(
797            PathBuf::from("B"),
798            PathBuf::from("D"),
799            DependencyType::Import,
800        ));
801
802        let changed: thread_utilities::RapidSet<PathBuf> = [PathBuf::from("C"), PathBuf::from("D")]
803            .into_iter()
804            .collect();
805        let affected = graph.find_affected_files(&changed);
806
807        assert_eq!(affected.len(), 4);
808    }
809
810    // ── topological_sort Tests ───────────────────────────────────────────
811
812    #[test]
813    fn test_topological_sort_linear_chain() {
814        let mut graph = DependencyGraph::new();
815
816        // A -> B -> C
817        graph.add_edge(DependencyEdge::new(
818            PathBuf::from("A"),
819            PathBuf::from("B"),
820            DependencyType::Import,
821        ));
822        graph.add_edge(DependencyEdge::new(
823            PathBuf::from("B"),
824            PathBuf::from("C"),
825            DependencyType::Import,
826        ));
827
828        let files: thread_utilities::RapidSet<PathBuf> =
829            [PathBuf::from("A"), PathBuf::from("B"), PathBuf::from("C")]
830                .into_iter()
831                .collect();
832
833        let sorted = graph.topological_sort(&files).unwrap();
834        assert_eq!(sorted.len(), 3);
835
836        let pos_a = sorted.iter().position(|p| p == Path::new("A")).unwrap();
837        let pos_b = sorted.iter().position(|p| p == Path::new("B")).unwrap();
838        let pos_c = sorted.iter().position(|p| p == Path::new("C")).unwrap();
839
840        assert!(pos_c < pos_b, "C must come before B");
841        assert!(pos_b < pos_a, "B must come before A");
842    }
843
844    #[test]
845    fn test_topological_sort_diamond() {
846        let mut graph = DependencyGraph::new();
847
848        // Diamond: A -> B, A -> C, B -> D, C -> D
849        graph.add_edge(DependencyEdge::new(
850            PathBuf::from("A"),
851            PathBuf::from("B"),
852            DependencyType::Import,
853        ));
854        graph.add_edge(DependencyEdge::new(
855            PathBuf::from("A"),
856            PathBuf::from("C"),
857            DependencyType::Import,
858        ));
859        graph.add_edge(DependencyEdge::new(
860            PathBuf::from("B"),
861            PathBuf::from("D"),
862            DependencyType::Import,
863        ));
864        graph.add_edge(DependencyEdge::new(
865            PathBuf::from("C"),
866            PathBuf::from("D"),
867            DependencyType::Import,
868        ));
869
870        let files: thread_utilities::RapidSet<PathBuf> = [
871            PathBuf::from("A"),
872            PathBuf::from("B"),
873            PathBuf::from("C"),
874            PathBuf::from("D"),
875        ]
876        .into_iter()
877        .collect();
878
879        let sorted = graph.topological_sort(&files).unwrap();
880        assert_eq!(sorted.len(), 4);
881
882        let pos_a = sorted.iter().position(|p| p == Path::new("A")).unwrap();
883        let pos_b = sorted.iter().position(|p| p == Path::new("B")).unwrap();
884        let pos_c = sorted.iter().position(|p| p == Path::new("C")).unwrap();
885        let pos_d = sorted.iter().position(|p| p == Path::new("D")).unwrap();
886
887        // D must come before B and C; B and C must come before A
888        assert!(pos_d < pos_b);
889        assert!(pos_d < pos_c);
890        assert!(pos_b < pos_a);
891        assert!(pos_c < pos_a);
892    }
893
894    #[test]
895    fn test_topological_sort_disconnected() {
896        let mut graph = DependencyGraph::new();
897
898        // Two separate chains: A -> B, C -> D
899        graph.add_edge(DependencyEdge::new(
900            PathBuf::from("A"),
901            PathBuf::from("B"),
902            DependencyType::Import,
903        ));
904        graph.add_edge(DependencyEdge::new(
905            PathBuf::from("C"),
906            PathBuf::from("D"),
907            DependencyType::Import,
908        ));
909
910        let files: thread_utilities::RapidSet<PathBuf> = [
911            PathBuf::from("A"),
912            PathBuf::from("B"),
913            PathBuf::from("C"),
914            PathBuf::from("D"),
915        ]
916        .into_iter()
917        .collect();
918
919        let sorted = graph.topological_sort(&files).unwrap();
920        assert_eq!(sorted.len(), 4);
921
922        // Verify local ordering within each chain
923        let pos_a = sorted.iter().position(|p| p == Path::new("A")).unwrap();
924        let pos_b = sorted.iter().position(|p| p == Path::new("B")).unwrap();
925        let pos_c = sorted.iter().position(|p| p == Path::new("C")).unwrap();
926        let pos_d = sorted.iter().position(|p| p == Path::new("D")).unwrap();
927
928        assert!(pos_b < pos_a);
929        assert!(pos_d < pos_c);
930    }
931
932    #[test]
933    fn test_topological_sort_single_node() {
934        let graph = DependencyGraph::new();
935        let files: thread_utilities::RapidSet<PathBuf> =
936            [PathBuf::from("only.rs")].into_iter().collect();
937
938        let sorted = graph.topological_sort(&files).unwrap();
939        assert_eq!(sorted, vec![PathBuf::from("only.rs")]);
940    }
941
942    #[test]
943    fn test_topological_sort_empty_set() {
944        let graph = DependencyGraph::new();
945        let files = thread_utilities::get_set();
946
947        let sorted = graph.topological_sort(&files).unwrap();
948        assert!(sorted.is_empty());
949    }
950
951    #[test]
952    fn test_topological_sort_subset_of_graph() {
953        let mut graph = DependencyGraph::new();
954
955        // Full graph: A -> B -> C -> D
956        graph.add_edge(DependencyEdge::new(
957            PathBuf::from("A"),
958            PathBuf::from("B"),
959            DependencyType::Import,
960        ));
961        graph.add_edge(DependencyEdge::new(
962            PathBuf::from("B"),
963            PathBuf::from("C"),
964            DependencyType::Import,
965        ));
966        graph.add_edge(DependencyEdge::new(
967            PathBuf::from("C"),
968            PathBuf::from("D"),
969            DependencyType::Import,
970        ));
971
972        // Sort only A and B
973        let files: thread_utilities::RapidSet<PathBuf> = [PathBuf::from("A"), PathBuf::from("B")]
974            .into_iter()
975            .collect();
976
977        let sorted = graph.topological_sort(&files).unwrap();
978        assert_eq!(sorted.len(), 2);
979
980        let pos_a = sorted.iter().position(|p| p == Path::new("A")).unwrap();
981        let pos_b = sorted.iter().position(|p| p == Path::new("B")).unwrap();
982        assert!(pos_b < pos_a);
983    }
984
985    // ── Cycle Detection Tests ────────────────────────────────────────────
986
987    #[test]
988    fn test_topological_sort_detects_simple_cycle() {
989        let mut graph = DependencyGraph::new();
990
991        // Cycle: A -> B -> A
992        graph.add_edge(DependencyEdge::new(
993            PathBuf::from("A"),
994            PathBuf::from("B"),
995            DependencyType::Import,
996        ));
997        graph.add_edge(DependencyEdge::new(
998            PathBuf::from("B"),
999            PathBuf::from("A"),
1000            DependencyType::Import,
1001        ));
1002
1003        let files: thread_utilities::RapidSet<PathBuf> = [PathBuf::from("A"), PathBuf::from("B")]
1004            .into_iter()
1005            .collect();
1006        let result = graph.topological_sort(&files);
1007
1008        assert!(result.is_err());
1009        let err = result.unwrap_err();
1010        match err {
1011            GraphError::CyclicDependency(path) => {
1012                assert!(
1013                    path == Path::new("A") || path == Path::new("B"),
1014                    "Cycle should involve A or B, got: {}",
1015                    path.display()
1016                );
1017            }
1018        }
1019    }
1020
1021    #[test]
1022    fn test_topological_sort_detects_longer_cycle() {
1023        let mut graph = DependencyGraph::new();
1024
1025        // Cycle: A -> B -> C -> A
1026        graph.add_edge(DependencyEdge::new(
1027            PathBuf::from("A"),
1028            PathBuf::from("B"),
1029            DependencyType::Import,
1030        ));
1031        graph.add_edge(DependencyEdge::new(
1032            PathBuf::from("B"),
1033            PathBuf::from("C"),
1034            DependencyType::Import,
1035        ));
1036        graph.add_edge(DependencyEdge::new(
1037            PathBuf::from("C"),
1038            PathBuf::from("A"),
1039            DependencyType::Import,
1040        ));
1041
1042        let files: thread_utilities::RapidSet<PathBuf> =
1043            [PathBuf::from("A"), PathBuf::from("B"), PathBuf::from("C")]
1044                .into_iter()
1045                .collect();
1046        let result = graph.topological_sort(&files);
1047        assert!(result.is_err());
1048    }
1049
1050    #[test]
1051    fn test_topological_sort_self_loop() {
1052        let mut graph = DependencyGraph::new();
1053
1054        // Self-loop: A -> A
1055        graph.add_edge(DependencyEdge::new(
1056            PathBuf::from("A"),
1057            PathBuf::from("A"),
1058            DependencyType::Import,
1059        ));
1060
1061        let files: thread_utilities::RapidSet<PathBuf> = [PathBuf::from("A")].into_iter().collect();
1062        let result = graph.topological_sort(&files);
1063        assert!(result.is_err());
1064    }
1065
1066    // ── Validation Tests ─────────────────────────────────────────────────
1067
1068    #[test]
1069    fn test_validate_valid_graph() {
1070        let mut graph = DependencyGraph::new();
1071        graph.add_edge(DependencyEdge::new(
1072            PathBuf::from("a.rs"),
1073            PathBuf::from("b.rs"),
1074            DependencyType::Import,
1075        ));
1076
1077        assert!(graph.validate().is_ok());
1078    }
1079
1080    #[test]
1081    fn test_validate_empty_graph() {
1082        let graph = DependencyGraph::new();
1083        assert!(graph.validate().is_ok());
1084    }
1085
1086    // ── Clear Tests ──────────────────────────────────────────────────────
1087
1088    #[test]
1089    fn test_graph_clear() {
1090        let mut graph = DependencyGraph::new();
1091        graph.add_edge(DependencyEdge::new(
1092            PathBuf::from("a.rs"),
1093            PathBuf::from("b.rs"),
1094            DependencyType::Import,
1095        ));
1096
1097        assert_eq!(graph.node_count(), 2);
1098        assert_eq!(graph.edge_count(), 1);
1099
1100        graph.clear();
1101
1102        assert_eq!(graph.node_count(), 0);
1103        assert_eq!(graph.edge_count(), 0);
1104    }
1105
1106    // ── GraphError Display Tests ─────────────────────────────────────────
1107
1108    #[test]
1109    fn test_graph_error_display() {
1110        let err = GraphError::CyclicDependency(PathBuf::from("src/module.rs"));
1111        let display = format!("{}", err);
1112        assert!(display.contains("src/module.rs"));
1113        assert!(display.contains("Cyclic dependency"));
1114    }
1115
1116    #[test]
1117    fn test_graph_error_is_std_error() {
1118        let err = GraphError::CyclicDependency(PathBuf::from("a.rs"));
1119        // Verify it implements std::error::Error
1120        let _: &dyn std::error::Error = &err;
1121    }
1122}
thread_flow/incremental/graph.rs

thread_flow/incremental/
graph.rs
