sdivi_graph/
dependency_graph.rs

1//! [`DependencyGraph`] construction from raw edges or `FeatureRecord` slices.
2
3use std::collections::BTreeMap;
4use std::path::{Path, PathBuf};
5
6use petgraph::graph::NodeIndex;
7use petgraph::Graph;
8use thiserror::Error;
9use tracing::debug;
10
11/// Errors that can occur during graph construction.
12#[derive(Debug, Error)]
13pub enum GraphError {
14    /// No source files were provided to the builder.
15    #[error("no source records provided")]
16    Empty,
17}
18
19/// Directed dependency graph with one node per source file.
20///
21/// Nodes carry the file path (relative to the repository root).
22/// Edges are directed from the importing file to the imported file.
23///
24/// # Examples
25///
26/// ```rust
27/// use sdivi_graph::dependency_graph::{DependencyGraph, build_dependency_graph_from_edges};
28///
29/// let dg = build_dependency_graph_from_edges(
30///     &["src/lib.rs".to_string(), "src/models.rs".to_string()],
31///     &[(0, 1)],
32/// );
33/// assert_eq!(dg.node_count(), 2);
34/// assert_eq!(dg.edge_count(), 1);
35/// ```
36#[derive(Debug, Clone)]
37pub struct DependencyGraph {
38    pub(crate) graph: Graph<PathBuf, ()>,
39    pub(crate) path_to_node: BTreeMap<PathBuf, NodeIndex>,
40}
41
42impl DependencyGraph {
43    /// Number of nodes (source files) in the graph.
44    pub fn node_count(&self) -> usize {
45        self.graph.node_count()
46    }
47
48    /// Number of directed edges in the graph.
49    pub fn edge_count(&self) -> usize {
50        self.graph.edge_count()
51    }
52
53    /// Returns the file path for node index `idx`.
54    pub fn node_path(&self, idx: usize) -> Option<&Path> {
55        let ni = NodeIndex::new(idx);
56        self.graph.node_weight(ni).map(|p| p.as_path())
57    }
58
59    /// Returns the node index for `path`, or `None` if not present.
60    pub fn node_for_path(&self, path: &Path) -> Option<usize> {
61        self.path_to_node.get(path).map(|ni| ni.index())
62    }
63
64    /// Returns all directed edges as `(from_idx, to_idx)` pairs.
65    pub fn edges_as_pairs(&self) -> Vec<(usize, usize)> {
66        self.graph
67            .raw_edges()
68            .iter()
69            .map(|e| (e.source().index(), e.target().index()))
70            .collect()
71    }
72
73    /// Returns the neighbors of node `idx` (nodes that `idx` imports from).
74    pub fn neighbors(&self, idx: usize) -> Vec<usize> {
75        let ni = NodeIndex::new(idx);
76        self.graph.neighbors(ni).map(|n| n.index()).collect()
77    }
78}
79
80/// Builds a [`DependencyGraph`] from node paths and raw `(from, to)` edge pairs.
81///
82/// Each entry in `node_paths` becomes one node; edges reference nodes by
83/// 0-based index into `node_paths`.  Out-of-range edge indices and self-loops
84/// are silently dropped.  Duplicate edges are deduplicated.
85///
86/// This constructor is always available (no `pipeline-records` feature needed).
87///
88/// # Examples
89///
90/// ```rust
91/// use sdivi_graph::dependency_graph::build_dependency_graph_from_edges;
92///
93/// let dg = build_dependency_graph_from_edges(
94///     &["src/lib.rs".to_string(), "src/models.rs".to_string()],
95///     &[(0, 1)],
96/// );
97/// assert_eq!(dg.node_count(), 2);
98/// assert_eq!(dg.edge_count(), 1);
99/// ```
100pub fn build_dependency_graph_from_edges(
101    node_paths: &[String],
102    edges: &[(usize, usize)],
103) -> DependencyGraph {
104    let mut graph: Graph<PathBuf, ()> = Graph::new();
105    let mut path_to_node: BTreeMap<PathBuf, NodeIndex> = BTreeMap::new();
106
107    for path_str in node_paths {
108        let path = PathBuf::from(path_str);
109        let ni = graph.add_node(path.clone());
110        path_to_node.insert(path, ni);
111    }
112
113    let node_count = node_paths.len();
114    for &(from, to) in edges {
115        if from >= node_count || to >= node_count || from == to {
116            continue;
117        }
118        let from_ni = NodeIndex::new(from);
119        let to_ni = NodeIndex::new(to);
120        if !graph.contains_edge(from_ni, to_ni) {
121            graph.add_edge(from_ni, to_ni, ());
122        }
123    }
124
125    DependencyGraph {
126        graph,
127        path_to_node,
128    }
129}
130
131/// Builds a [`DependencyGraph`] from a slice of `FeatureRecord`s.
132///
133/// Each record becomes one node. Import strings are resolved against the set
134/// of known file paths; unresolvable imports are dropped at `DEBUG` level.
135///
136/// # Examples
137///
138/// ```rust
139/// use sdivi_graph::dependency_graph::build_dependency_graph;
140/// use sdivi_parsing::feature_record::FeatureRecord;
141/// use std::path::PathBuf;
142///
143/// let records: Vec<FeatureRecord> = vec![];
144/// let dg = build_dependency_graph(&records);
145/// assert_eq!(dg.node_count(), 0);
146/// ```
147#[cfg(feature = "pipeline-records")]
148pub fn build_dependency_graph(
149    records: &[sdivi_parsing::feature_record::FeatureRecord],
150) -> DependencyGraph {
151    let mut graph: Graph<PathBuf, ()> = Graph::new();
152    let mut path_to_node: BTreeMap<PathBuf, NodeIndex> = BTreeMap::new();
153
154    for record in records {
155        let ni = graph.add_node(record.path.clone());
156        path_to_node.insert(record.path.clone(), ni);
157    }
158
159    let stem_map = build_stem_map(&path_to_node);
160
161    for record in records {
162        let from_ni = path_to_node[&record.path];
163        for import in &record.imports {
164            match resolve_import(import, &record.path, &stem_map, &path_to_node) {
165                Some(to_ni) if to_ni != from_ni => {
166                    if !graph.contains_edge(from_ni, to_ni) {
167                        graph.add_edge(from_ni, to_ni, ());
168                    }
169                }
170                Some(_) => {}
171                None => {
172                    debug!(%import, path = ?record.path, "unresolved import dropped");
173                }
174            }
175        }
176    }
177
178    DependencyGraph {
179        graph,
180        path_to_node,
181    }
182}
183
184#[cfg(feature = "pipeline-records")]
185fn build_stem_map(path_to_node: &BTreeMap<PathBuf, NodeIndex>) -> BTreeMap<String, Vec<NodeIndex>> {
186    let mut map: BTreeMap<String, Vec<NodeIndex>> = BTreeMap::new();
187    for (path, &ni) in path_to_node {
188        if let Some(stem) = path.file_stem().and_then(|s| s.to_str()) {
189            map.entry(stem.to_ascii_lowercase()).or_default().push(ni);
190        }
191    }
192    map
193}
194
195#[cfg(feature = "pipeline-records")]
196fn resolve_import(
197    import: &str,
198    from_path: &Path,
199    stem_map: &BTreeMap<String, Vec<NodeIndex>>,
200    path_to_node: &BTreeMap<PathBuf, NodeIndex>,
201) -> Option<NodeIndex> {
202    if import.starts_with("./") || import.starts_with("../") {
203        return resolve_relative(import, from_path, path_to_node);
204    }
205
206    let local = import
207        .strip_prefix("crate::")
208        .or_else(|| import.strip_prefix("self::"))
209        .or_else(|| import.strip_prefix("super::"));
210
211    if let Some(local) = local {
212        let first = local.split("::").next()?;
213        return resolve_stem(first, stem_map);
214    }
215
216    None
217}
218
219#[cfg(feature = "pipeline-records")]
220fn resolve_relative(
221    import: &str,
222    from_path: &Path,
223    path_to_node: &BTreeMap<PathBuf, NodeIndex>,
224) -> Option<NodeIndex> {
225    let from_dir = from_path.parent()?;
226    let rel = import.trim_start_matches("./").trim_start_matches("../");
227    for ext in &["rs", "py", "ts", "tsx", "js", "go", "java"] {
228        let candidate = from_dir.join(format!("{rel}.{ext}"));
229        if let Some(&ni) = path_to_node.get(&candidate) {
230            return Some(ni);
231        }
232    }
233    for index in &["mod.rs", "index.ts", "index.js", "__init__.py"] {
234        let candidate = from_dir.join(rel).join(index);
235        if let Some(&ni) = path_to_node.get(&candidate) {
236            return Some(ni);
237        }
238    }
239    None
240}
241
242#[cfg(feature = "pipeline-records")]
243fn resolve_stem(stem: &str, stem_map: &BTreeMap<String, Vec<NodeIndex>>) -> Option<NodeIndex> {
244    let candidates = stem_map.get(&stem.to_ascii_lowercase())?;
245    if candidates.len() == 1 {
246        Some(candidates[0])
247    } else {
248        None
249    }
250}
sdivi_graph/dependency_graph.rs

sdivi_graph/
dependency_graph.rs
