kiss/rust_graph/
include_graph.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2use std::path::Path;
3
4use crate::rust_parsing::{ParsedRustFile, parse_rust_file};
5
6use super::extract_rust_imports;
7
8pub struct IncludeGraph {
9    pub direct: HashMap<std::path::PathBuf, Vec<std::path::PathBuf>>,
10}
11
12impl IncludeGraph {
13    #[must_use]
14    pub fn transitive_from(&self, root: &Path) -> Vec<std::path::PathBuf> {
15        const MAX: usize = 10_000;
16        let root = crate::rust_include::canonical_path(root);
17        let mut seen = HashSet::new();
18        let mut out = Vec::new();
19        let mut queue = VecDeque::new();
20        queue.push_back(root);
21        while let Some(cur) = queue.pop_front() {
22            if !seen.insert(cur.clone()) {
23                continue;
24            }
25            if let Some(children) = self.direct.get(&cur) {
26                for child in children {
27                    if seen.len() >= MAX {
28                        return out;
29                    }
30                    if child != &cur {
31                        out.push(child.clone());
32                        queue.push_back(child.clone());
33                    }
34                }
35            }
36        }
37        out
38    }
39}
40
41pub fn build_include_graph(parsed_files: &[&ParsedRustFile]) -> IncludeGraph {
42    let mut direct: HashMap<std::path::PathBuf, Vec<std::path::PathBuf>> = HashMap::new();
43    for parsed in parsed_files {
44        let parent = crate::rust_include::canonical_path(&parsed.path);
45        let imports = extract_rust_imports(&parsed.ast);
46        let mut children = Vec::new();
47        for lit in imports.include_literals {
48            let target = crate::rust_include::resolve_include_path(&parsed.path, &lit);
49            if target.is_file() {
50                children.push(crate::rust_include::canonical_path(&target));
51            }
52        }
53        if !children.is_empty() {
54            direct.insert(parent, children);
55        }
56    }
57    IncludeGraph { direct }
58}
59
60#[must_use]
61pub fn expand_rust_files(files: Vec<std::path::PathBuf>) -> Vec<std::path::PathBuf> {
62    const MAX: usize = 10_000;
63    let mut set: HashSet<std::path::PathBuf> = files
64        .into_iter()
65        .map(|p| crate::rust_include::canonical_path(&p))
66        .collect();
67    loop {
68        let snapshot: Vec<_> = set.iter().cloned().collect();
69        let mut changed = false;
70        for path in snapshot {
71            if set.len() >= MAX {
72                break;
73            }
74            let Ok(parsed) = parse_rust_file(&path) else {
75                continue;
76            };
77            for lit in extract_rust_imports(&parsed.ast).include_literals {
78                let inc = crate::rust_include::resolve_include_path(&path, &lit);
79                if inc.is_file() {
80                    let c = crate::rust_include::canonical_path(&inc);
81                    if set.insert(c) {
82                        changed = true;
83                    }
84                }
85            }
86        }
87        if !changed || set.len() >= MAX {
88            break;
89        }
90    }
91    let mut out: Vec<_> = set.into_iter().collect();
92    out.sort();
93    out
94}
95
96#[cfg(test)]
97mod include_graph_tests {
98    use super::*;
99    use std::collections::HashMap;
100    use std::path::PathBuf;
101
102    #[test]
103    fn include_graph_transitive_from_follows_direct_edges() {
104        let root = PathBuf::from("/tmp/root.rs");
105        let child = PathBuf::from("/tmp/child.rs");
106        let mut direct = HashMap::new();
107        direct.insert(root.clone(), vec![child.clone()]);
108        let graph = IncludeGraph { direct };
109        assert_eq!(graph.transitive_from(&root), vec![child]);
110    }
111}
kiss/rust_graph/include_graph.rs

kiss/rust_graph/
include_graph.rs
