Skip to main content

source_mesh_core/graph/
model.rs

1use std::collections::BTreeMap;
2use std::collections::BTreeSet;
3use std::path::Component;
4use std::path::Path;
5use std::path::PathBuf;
6
7use anyhow::Context as _;
8use anyhow::Result;
9use anyhow::ensure;
10use derive_new::new;
11use getset::CopyGetters;
12use getset::Getters;
13
14#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Getters)]
15#[getset(get = "pub")]
16pub struct FileNode {
17    path: PathBuf,
18}
19
20impl FileNode {
21    pub fn new(path: PathBuf) -> Result<Self> {
22        ensure!(
23            path.components().all(|component| matches!(component, Component::Normal(_)))
24                && path.file_name().is_some(),
25            "File graph requires nonempty relative source paths with normal path components"
26        );
27        Ok(Self { path })
28    }
29}
30
31#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Getters, new)]
32#[getset(get = "pub")]
33pub struct FolderNode {
34    label: String,
35}
36
37#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
38pub enum DependencyKind {
39    Production,
40    Test,
41}
42
43#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, CopyGetters, Getters, new)]
44pub struct Edge<Node> {
45    #[getset(get = "pub")]
46    source: Node,
47    #[getset(get = "pub")]
48    target: Node,
49    #[getset(get_copy = "pub")]
50    kind: DependencyKind,
51}
52
53pub type FileEdge = Edge<FileNode>;
54pub type FolderEdge = Edge<FolderNode>;
55
56/** Counts distinct directed file pairs of the same dependency kind.
57
58```compile_fail
59use std::collections::BTreeMap;
60use std::collections::BTreeSet;
61use source_mesh_core::model::DependencyKind;
62use source_mesh_core::model::FolderEdge;
63use source_mesh_core::model::FolderGraph;
64use source_mesh_core::model::FolderNode;
65
66let folder = FolderNode::new("src".into());
67let edge = FolderEdge::new(folder.clone(), folder.clone(), DependencyKind::Production);
68let depth = 2_usize;
69let graph = FolderGraph::new(BTreeSet::from([folder]), BTreeMap::from([(edge, depth)]));
70```
71*/
72#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, CopyGetters, new)]
73#[getset(get_copy = "pub")]
74pub struct DependencyCount {
75    value: usize,
76}
77
78impl DependencyCount {
79    fn increment(&mut self) -> Result<()> {
80        self.value = self.value.checked_add(1).context("Dependency count overflow")?;
81        Ok(())
82    }
83}
84
85#[derive(Default, PartialEq, Getters)]
86#[getset(get = "pub")]
87pub struct FolderGraph {
88    nodes: BTreeSet<FolderNode>,
89    edges: BTreeMap<FolderEdge, DependencyCount>,
90}
91
92impl FolderGraph {
93    pub fn new(nodes: BTreeSet<FolderNode>, edges: BTreeMap<FolderEdge, DependencyCount>) -> Result<Self> {
94        ensure!(
95            edges.keys().all(|edge| nodes.contains(edge.source()) && nodes.contains(edge.target())),
96            "Folder graph has an unknown dependency endpoint"
97        );
98        Ok(Self { nodes, edges })
99    }
100}
101
102/**
103
104```compile_fail
105use std::collections::BTreeSet;
106use std::path::PathBuf;
107use source_mesh_core::model::FileGraph;
108
109let files = BTreeSet::from([PathBuf::from("lib.rs")]);
110let graph = FileGraph::new(files, BTreeSet::new());
111```
112*/
113#[derive(PartialEq, Getters)]
114#[getset(get = "pub")]
115pub struct FileGraph {
116    files: BTreeSet<FileNode>,
117    edges: BTreeSet<FileEdge>,
118}
119
120impl FileGraph {
121    pub fn new(files: BTreeSet<FileNode>, edges: BTreeSet<FileEdge>) -> Result<Self> {
122        ensure!(
123            edges.iter().all(|edge| files.contains(edge.source()) && files.contains(edge.target())),
124            "File graph has an unknown dependency endpoint"
125        );
126        Ok(Self { files, edges })
127    }
128
129    #[must_use]
130    pub fn without_test_dependencies(mut self) -> Self {
131        self.edges.retain(|edge| edge.kind() == DependencyKind::Production);
132        self
133    }
134
135    pub fn within_root(mut self, root: &Path) -> Result<Self> {
136        let root = relative_directory_root(root)?;
137        self.files.retain(|file| file.path().parent().is_some_and(|parent| parent.starts_with(&root)));
138        self.edges.retain(|edge| self.files.contains(edge.source()) && self.files.contains(edge.target()));
139        Ok(self)
140    }
141
142    pub fn folders(
143        &self,
144        root: &Path,
145        depth: Option<usize>,
146        include_self: bool,
147    ) -> Result<FolderGraph> {
148        let root = relative_directory_root(root)?;
149        let mut folder_graph = FolderGraph::default();
150        let mut file_folders = BTreeMap::new();
151        for file in &self.files {
152            let parent = file.path().parent().context("Indexed source file has no parent")?;
153            let Ok(relative) = parent.strip_prefix(&root) else {
154                continue;
155            };
156            let parts = relative
157                .components()
158                .take(depth.unwrap_or(usize::MAX))
159                .map(|part| {
160                    part.as_os_str()
161                        .to_str()
162                        .context("Folder path is not UTF-8")
163                })
164                .collect::<Result<Vec<_>>>()?;
165            let label = if parts.is_empty() {
166                ".".into()
167            } else {
168                parts.join("/")
169            };
170            let folder = FolderNode::new(label);
171            folder_graph.nodes.insert(folder.clone());
172            file_folders.insert(file, folder);
173        }
174        for edge in &self.edges {
175            let (source, target) = (edge.source(), edge.target());
176            if source == target {
177                continue;
178            }
179            if let (Some(source_folder), Some(target_folder)) = (file_folders.get(source), file_folders.get(target))
180                && (include_self || source_folder != target_folder)
181            {
182                folder_graph.edges.entry(FolderEdge::new(source_folder.clone(), target_folder.clone(), edge.kind()))
183                    .or_default().increment()?;
184            }
185        }
186        Ok(folder_graph)
187    }
188}
189
190fn relative_directory_root(root: &Path) -> Result<PathBuf> {
191    ensure!(root.components()
192        .all(|component| matches!(component, Component::Normal(_) | Component::CurDir)),
193        "--root must be a relative directory inside the indexed project (no '..')");
194    Ok(root.components().filter(|component| !matches!(component, Component::CurDir)).collect())
195}
196
197#[cfg(test)]
198#[expect(
199    clippy::panic_in_result_fn,
200    reason = "Tests use assertions for expectations while returning Result for fallible setup."
201)]
202mod tests {
203    use std::collections::BTreeMap;
204    use std::collections::BTreeSet;
205    use std::path::Path;
206    use std::path::PathBuf;
207
208    use anyhow::Result;
209    use pretty_assertions::assert_eq;
210    use rstest::rstest;
211
212    use super::DependencyCount;
213    use super::DependencyKind;
214    use super::FileEdge;
215    use super::FileGraph;
216    use super::FileNode;
217    use super::FolderEdge;
218    use super::FolderGraph;
219    use super::FolderNode;
220
221    #[rstest]
222    #[case(0, 1)]
223    #[case(7, 8)]
224    #[case(usize::MAX - 1, usize::MAX)]
225    fn test_dependency_count_increment(#[case] initial: usize, #[case] expected: usize) -> Result<()> {
226        let mut system_under_test = DependencyCount::new(initial);
227
228        system_under_test.increment()?;
229
230        assert_eq!(expected, system_under_test.value(), "Dependency count did not increase by one");
231        Ok(())
232    }
233
234    #[test]
235    fn test_dependency_count_overflow() -> Result<()> {
236        let mut system_under_test = DependencyCount::new(usize::MAX);
237
238        let result = system_under_test.increment();
239
240        assert!(result.is_err(), "Dependency count overflow was accepted");
241        assert_eq!(usize::MAX, system_under_test.value(), "Overflow changed the dependency count");
242        Ok(())
243    }
244
245    fn file_graph_fixture() -> Result<(BTreeSet<FileNode>, BTreeSet<FileEdge>)> {
246        let source_directory = Path::new("src");
247        let service_module = FileNode::new(source_directory.join("api").join("service.rs"))?;
248        let http_module = FileNode::new(source_directory.join("api").join("http.rs"))?;
249        let routes_module = FileNode::new(source_directory.join("api").join("v1").join("routes.rs"))?;
250        let request_module = FileNode::new(source_directory.join("domain").join("request.rs"))?;
251        let rules_module = FileNode::new(source_directory.join("domain").join("rules.rs"))?;
252        let database_module = FileNode::new(source_directory.join("storage").join("db.rs"))?;
253        let calls_module = FileNode::new(source_directory.join("body_only").join("calls.rs"))?;
254        let files = BTreeSet::from([
255            FileNode::new(source_directory.join("lib.rs"))?,
256            FileNode::new(source_directory.join("api").join("mod.rs"))?,
257            service_module.clone(),
258            http_module.clone(),
259            FileNode::new(source_directory.join("api").join("v1").join("mod.rs"))?,
260            routes_module.clone(),
261            FileNode::new(source_directory.join("domain").join("mod.rs"))?,
262            request_module.clone(),
263            rules_module.clone(),
264            database_module.clone(),
265            FileNode::new(source_directory.join("body_only").join("mod.rs"))?,
266            calls_module.clone(),
267            FileNode::new(source_directory.join("isolated").join("mod.rs"))?,
268            FileNode::new(source_directory.join("isolated").join("sample.rs"))?,
269        ]);
270        let dependencies = BTreeSet::from([
271            FileEdge::new(service_module.clone(), http_module.clone(), DependencyKind::Production),
272            FileEdge::new(service_module, routes_module.clone(), DependencyKind::Production),
273            FileEdge::new(http_module.clone(), request_module.clone(), DependencyKind::Production),
274            FileEdge::new(http_module, database_module.clone(), DependencyKind::Production),
275            FileEdge::new(routes_module.clone(), request_module.clone(), DependencyKind::Production),
276            FileEdge::new(routes_module, database_module.clone(), DependencyKind::Production),
277            FileEdge::new(request_module, rules_module.clone(), DependencyKind::Production),
278            FileEdge::new(rules_module, database_module.clone(), DependencyKind::Production),
279            FileEdge::new(calls_module, database_module, DependencyKind::Production),
280        ]);
281        Ok((files, dependencies))
282    }
283
284    #[must_use]
285    fn folder_edges(values: &[(&str, &str, usize)], kind: DependencyKind) -> BTreeMap<FolderEdge, DependencyCount> {
286        values
287            .iter()
288            .map(|&(source, destination, weight)| (
289                FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(destination.into()), kind),
290                DependencyCount::new(weight),
291            ))
292            .collect()
293    }
294
295    #[must_use]
296    fn folder_nodes(values: &[&str]) -> BTreeSet<FolderNode> {
297        values.iter().map(|&label| FolderNode::new(label.into())).collect()
298    }
299
300    fn mixed_dependency_fixture() -> Result<(BTreeSet<FileNode>, BTreeSet<FileEdge>)> {
301        let source_directory = Path::new("src");
302        let http_module = FileNode::new(source_directory.join("api").join("http.rs"))?;
303        let routes_module = FileNode::new(source_directory.join("api").join("v1").join("routes.rs"))?;
304        let request_module = FileNode::new(source_directory.join("domain").join("request.rs"))?;
305        let checks_module = FileNode::new(source_directory.join("tests").join("checks.rs"))?;
306        let files = BTreeSet::from([
307            http_module.clone(), routes_module.clone(), request_module.clone(), checks_module.clone(),
308            FileNode::new(source_directory.join("isolated").join("sample.rs"))?,
309        ]);
310        let dependencies = BTreeSet::from([
311            FileEdge::new(http_module.clone(), request_module.clone(), DependencyKind::Production),
312            FileEdge::new(routes_module.clone(), request_module.clone(), DependencyKind::Production),
313            FileEdge::new(http_module.clone(), request_module.clone(), DependencyKind::Test),
314            FileEdge::new(http_module.clone(), request_module.clone(), DependencyKind::Test),
315            FileEdge::new(routes_module, request_module.clone(), DependencyKind::Test),
316            FileEdge::new(request_module.clone(), http_module, DependencyKind::Test),
317            FileEdge::new(checks_module, request_module, DependencyKind::Test),
318        ]);
319        Ok((files, dependencies))
320    }
321
322    #[test]
323    fn test_physical_directories_and_isolated_files() -> Result<()> {
324        let (files, dependencies) = file_graph_fixture()?;
325        let system_under_test = FileGraph::new(files, dependencies)?;
326        let expected_nodes = folder_nodes(&[
327            ".", "api", "api/v1", "body_only", "domain", "isolated", "storage",
328        ]);
329        let expected_edges = folder_edges(&[
330            ("api", "api/v1", 1),
331            ("api", "domain", 1),
332            ("api", "storage", 1),
333            ("api/v1", "domain", 1),
334            ("api/v1", "storage", 1),
335            ("body_only", "storage", 1),
336            ("domain", "storage", 1),
337        ], DependencyKind::Production);
338
339        let graph = system_under_test.folders(Path::new("src"), None, false)?;
340
341        assert_eq!(&expected_nodes, graph.nodes(), "Physical directory nodes differ");
342        assert_eq!(&expected_edges, graph.edges(), "Physical directory dependencies differ");
343        assert!(!graph.nodes().contains(&FolderNode::new("persistence".into())), "A semantic module name was substituted for the physical folder");
344        Ok(())
345    }
346
347    #[rstest]
348    #[case(None)]
349    #[case(Some(2))]
350    #[case(Some(10))]
351    fn test_depth_beyond_existing_folders(#[case] depth: Option<usize>) -> Result<()> {
352        let (files, dependencies) = file_graph_fixture()?;
353        let system_under_test = FileGraph::new(files, dependencies)?;
354        let complete_graph = system_under_test.folders(Path::new("src"), None, false)?;
355
356        let graph = system_under_test.folders(Path::new("src"), depth, false)?;
357
358        assert_eq!(complete_graph.nodes(), graph.nodes(), "Depth {depth:?} changed nodes in a graph shallower than the requested limit");
359        assert_eq!(complete_graph.edges(), graph.edges(), "Depth {depth:?} changed dependencies in a graph shallower than the requested limit");
360        Ok(())
361    }
362
363    #[rstest]
364    #[case(0, &["."], &[])]
365    #[case(1, &[".", "api", "body_only", "domain", "isolated", "storage"], &[
366        ("api", "domain", 2), ("api", "storage", 2),
367        ("body_only", "storage", 1), ("domain", "storage", 1),
368    ])]
369    fn test_depth_grouping_and_distinct_file_pair_weights(
370        #[case] depth: usize,
371        #[case] expected_nodes: &[&str],
372        #[case] expected_edges: &[(&str, &str, usize)],
373    ) -> Result<()> {
374        let (files, dependencies) = file_graph_fixture()?;
375        let system_under_test = FileGraph::new(files, dependencies)?;
376
377        let graph = system_under_test.folders(Path::new("src"), Some(depth), false)?;
378
379        assert_eq!(&folder_nodes(expected_nodes), graph.nodes(), "Depth {depth} grouped nodes incorrectly");
380        assert_eq!(&folder_edges(expected_edges, DependencyKind::Production), graph.edges(), "Depth {depth} grouped dependencies incorrectly");
381        Ok(())
382    }
383
384    #[rstest]
385    #[case(None, &[
386        ("api", "api", 1), ("api", "api/v1", 1),
387        ("api", "domain", 1), ("api", "storage", 1),
388        ("api/v1", "domain", 1), ("api/v1", "storage", 1),
389        ("body_only", "storage", 1), ("domain", "domain", 1),
390        ("domain", "storage", 1),
391    ])]
392    #[case(Some(0), &[(".", ".", 9)])]
393    #[case(Some(1), &[
394        ("api", "api", 2), ("api", "domain", 2),
395        ("api", "storage", 2), ("body_only", "storage", 1),
396        ("domain", "domain", 1), ("domain", "storage", 1),
397    ])]
398    fn test_self_edges_between_distinct_files(
399        #[case] depth: Option<usize>,
400        #[case] expected_edges: &[(&str, &str, usize)],
401    ) -> Result<()> {
402        let (files, mut dependencies) = file_graph_fixture()?;
403        let request_module = FileNode::new(Path::new("src").join("domain").join("request.rs"))?;
404        dependencies.insert(FileEdge::new(request_module.clone(), request_module, DependencyKind::Production));
405        let system_under_test = FileGraph::new(files, dependencies)?;
406
407        let graph = system_under_test.folders(Path::new("src"), depth, true)?;
408
409        assert_eq!(&folder_edges(expected_edges, DependencyKind::Production), graph.edges(), "Self-edge handling at depth {depth:?} differs");
410        Ok(())
411    }
412
413    #[test]
414    fn test_scope_boundaries_use_path_components() -> Result<()> {
415        let (mut files, mut dependencies) = file_graph_fixture()?;
416        let outside_module = FileNode::new(Path::new("src2").join("outside.rs"))?;
417        files.insert(outside_module.clone());
418        dependencies.insert(FileEdge::new(
419            outside_module, FileNode::new(Path::new("src").join("api").join("service.rs"))?, DependencyKind::Production,
420        ));
421        let system_under_test = FileGraph::new(files, dependencies)?;
422
423        let api_graph = system_under_test.folders(&Path::new("src").join("api"), None, false)?;
424        let source_graph = system_under_test.folders(Path::new("src"), None, false)?;
425
426        assert_eq!(&folder_nodes(&[".", "v1"]), api_graph.nodes(), "API scope contains unexpected folders");
427        assert_eq!(&folder_edges(&[(".", "v1", 1)], DependencyKind::Production), api_graph.edges(), "API scope contains unexpected dependencies");
428        assert!(!source_graph.nodes().contains(&FolderNode::new("src2".into())), "Scope included a directory with a shared prefix outside the source tree");
429        assert_eq!(7, source_graph.edges().len(), "Scope changed the seven dependencies internal to the source tree");
430        Ok(())
431    }
432
433    #[rstest]
434    #[case(1, &["src"], &[])]
435    #[case(2, &["src", "src/api", "src/body_only", "src/domain", "src/isolated", "src/storage"], &[
436        ("src/api", "src/domain", 2), ("src/api", "src/storage", 2),
437        ("src/body_only", "src/storage", 1), ("src/domain", "src/storage", 1),
438    ])]
439    fn test_default_depth_origin(
440        #[case] depth: usize,
441        #[case] expected_nodes: &[&str],
442        #[case] expected_edges: &[(&str, &str, usize)],
443    ) -> Result<()> {
444        let (files, dependencies) = file_graph_fixture()?;
445        let system_under_test = FileGraph::new(files, dependencies)?;
446
447        let graph = system_under_test.folders(Path::new(""), Some(depth), false)?;
448
449        assert_eq!(&folder_nodes(expected_nodes), graph.nodes(), "Default root produced incorrect nodes at depth {depth}");
450        assert_eq!(&folder_edges(expected_edges, DependencyKind::Production), graph.edges(), "Default root produced incorrect dependencies at depth {depth}");
451        Ok(())
452    }
453
454    #[test]
455    fn test_isolated_folder_scope() -> Result<()> {
456        let (files, dependencies) = file_graph_fixture()?;
457        let system_under_test = FileGraph::new(files, dependencies)?;
458
459        let graph = system_under_test.folders(&Path::new("src").join("isolated"), None, true)?;
460
461        assert_eq!(&folder_nodes(&["."]), graph.nodes(), "Isolated scope contains unexpected folders");
462        assert!(graph.edges().is_empty(), "An isolated folder acquired dependencies");
463        Ok(())
464    }
465
466    #[rstest]
467    #[case(None, &[("api", "domain", 1), ("api/v1", "domain", 1)], &[
468        ("api", "domain", 1), ("api/v1", "domain", 1), ("domain", "api", 1), ("tests", "domain", 1),
469    ])]
470    #[case(Some(1), &[("api", "domain", 2)], &[
471        ("api", "domain", 2), ("domain", "api", 1), ("tests", "domain", 1),
472    ])]
473    #[case(Some(0), &[(".", ".", 2)], &[(".", ".", 4)])]
474    fn test_dependency_kinds_deduplication_and_depth_aggregation(
475        #[case] depth: Option<usize>,
476        #[case] expected_production: &[(&str, &str, usize)],
477        #[case] expected_tests: &[(&str, &str, usize)],
478    ) -> Result<()> {
479        let (files, dependencies) = mixed_dependency_fixture()?;
480        let system_under_test = FileGraph::new(files, dependencies)?;
481        let mut expected_edges = folder_edges(expected_production, DependencyKind::Production);
482        expected_edges.extend(folder_edges(expected_tests, DependencyKind::Test));
483
484        let graph = system_under_test.folders(Path::new("src"), depth, true)?;
485
486        assert_eq!(6, system_under_test.edges().len(), "Duplicate occurrences were retained or distinct dependency kinds were merged");
487        assert_eq!(&expected_edges, graph.edges(), "Depth {depth:?} changed dependency kinds or distinct file-pair counts");
488        Ok(())
489    }
490
491    #[test]
492    fn test_dependency_kind_filtering() -> Result<()> {
493        let (files, dependencies) = mixed_dependency_fixture()?;
494        let expected_files = files.clone();
495        let system_under_test = FileGraph::new(files, dependencies)?;
496        let expected_edges = folder_edges(&[("api", "domain", 1), ("api/v1", "domain", 1)], DependencyKind::Production);
497
498        let graph = system_under_test.without_test_dependencies();
499        let folders = graph.folders(Path::new("src"), None, false)?;
500
501        assert_eq!(&expected_files, graph.files(), "Excluding test dependencies removed source files");
502        assert_eq!(2, graph.edges().len(), "Excluding test dependencies lost production edges or retained test edges");
503        assert_eq!(&expected_edges, folders.edges(), "Excluding test dependencies changed production dependencies or counts");
504        assert_eq!(&folder_nodes(&["api", "api/v1", "domain", "isolated", "tests"]), folders.nodes(),
505            "Excluding test dependencies removed isolated or test-only source folders");
506        Ok(())
507    }
508
509    #[rstest]
510    #[case("")]
511    #[case(".")]
512    #[case("..")]
513    #[case("../outside.rs")]
514    #[case("./source.rs")]
515    #[case("/absolute.rs")]
516    fn test_file_node_source_path_preconditions(#[case] source_path: &str) {
517        let path = PathBuf::from(source_path);
518
519        let system_under_test = FileNode::new(path);
520
521        assert!(system_under_test.is_err(), "Invalid file source path was accepted: {source_path}");
522    }
523
524    #[rstest]
525    #[case("..")]
526    #[case("../src")]
527    #[case("/src")]
528    fn test_folder_scope_preconditions(#[case] root: &str) -> Result<()> {
529        let (files, dependencies) = file_graph_fixture()?;
530        let system_under_test = FileGraph::new(files, dependencies)?;
531
532        let graph = system_under_test.folders(Path::new(root), None, false);
533
534        assert!(graph.is_err(), "Invalid folder scope was accepted: {root}");
535        Ok(())
536    }
537
538    #[rstest]
539    #[case("known.rs", "missing.rs")]
540    #[case("missing.rs", "known.rs")]
541    fn test_file_graph_endpoint_membership(#[case] source: &str, #[case] destination: &str) -> Result<()> {
542        let files = BTreeSet::from([FileNode::new(PathBuf::from("known.rs"))?]);
543        let dependencies = BTreeSet::from([FileEdge::new(
544            FileNode::new(PathBuf::from(source))?, FileNode::new(PathBuf::from(destination))?,
545            DependencyKind::Production,
546        )]);
547
548        let system_under_test = FileGraph::new(files, dependencies);
549
550        assert!(system_under_test.is_err(), "File graph accepted an unknown dependency endpoint");
551        Ok(())
552    }
553
554    #[rstest]
555    #[case("known", "missing")]
556    #[case("missing", "known")]
557    fn test_folder_graph_endpoint_membership(#[case] source: &str, #[case] destination: &str) {
558        let nodes = folder_nodes(&["known"]);
559        let dependencies = folder_edges(&[(source, destination, 1)], DependencyKind::Production);
560
561        let system_under_test = FolderGraph::new(nodes, dependencies);
562
563        assert!(system_under_test.is_err(), "Folder graph accepted an unknown dependency endpoint");
564    }
565}