cha_core/graph/
module_graph.rs

1use std::collections::{HashMap, HashSet};
2
3/// A group of tightly-coupled files inferred from the import graph.
4#[derive(Debug, Clone)]
5pub struct Module {
6    pub name: String,
7    pub files: Vec<String>,
8}
9
10/// Infer modules from file-level import edges.
11///
12/// Algorithm:
13/// 1. Exclusive-dependency merge: if file B has fan-in=1 (only imported by A), merge B into A's module.
14///    Repeat until no new merges.
15/// 2. Directory fallback: remaining unmerged files are grouped by parent directory.
16pub fn infer_modules(file_imports: &[(String, String)], all_files: &[String]) -> Vec<Module> {
17    let mut fan_in: HashMap<&str, HashSet<&str>> = HashMap::new();
18    for (from, to) in file_imports {
19        fan_in.entry(to.as_str()).or_default().insert(from.as_str());
20    }
21
22    let mut parent: HashMap<String, String> =
23        all_files.iter().map(|f| (f.clone(), f.clone())).collect();
24
25    merge_exclusive_deps(file_imports, &fan_in, &mut parent);
26
27    let mut groups: HashMap<String, Vec<String>> = HashMap::new();
28    for file in all_files {
29        groups
30            .entry(find(&parent, file))
31            .or_default()
32            .push(file.clone());
33    }
34
35    let mut dir_groups: HashMap<String, Vec<String>> = HashMap::new();
36    for (_, members) in groups {
37        dir_groups
38            .entry(common_prefix(&members))
39            .or_default()
40            .extend(members);
41    }
42
43    dir_groups
44        .into_values()
45        .map(|files| Module {
46            name: common_prefix(&files),
47            files,
48        })
49        .collect()
50}
51
52fn merge_exclusive_deps(
53    file_imports: &[(String, String)],
54    fan_in: &HashMap<&str, HashSet<&str>>,
55    parent: &mut HashMap<String, String>,
56) {
57    loop {
58        let mut changed = false;
59        for (_, to) in file_imports {
60            let importers = match fan_in.get(to.as_str()) {
61                Some(s) if s.len() == 1 => s,
62                _ => continue,
63            };
64            let sole_importer = importers.iter().next().unwrap();
65            let root_a = find(parent, sole_importer);
66            let root_b = find(parent, to);
67            if root_a != root_b {
68                parent.insert(root_b, root_a.clone());
69                changed = true;
70            }
71        }
72        if !changed {
73            break;
74        }
75    }
76}
77
78fn find(parent: &HashMap<String, String>, x: &str) -> String {
79    let mut cur = x.to_string();
80    while let Some(p) = parent.get(&cur) {
81        if p == &cur {
82            break;
83        }
84        cur = p.clone();
85    }
86    cur
87}
88
89fn common_prefix(paths: &[String]) -> String {
90    if paths.len() <= 1 {
91        return paths
92            .first()
93            .and_then(|p| std::path::Path::new(p).parent())
94            .map(|p| p.to_string_lossy().to_string())
95            .unwrap_or_default();
96    }
97    let parts: Vec<Vec<&str>> = paths.iter().map(|p| p.split('/').collect()).collect();
98    let prefix: Vec<&str> = (0..)
99        .map_while(|i| {
100            let first = parts[0].get(i)?;
101            parts
102                .iter()
103                .all(|p| p.get(i) == Some(first))
104                .then_some(*first)
105        })
106        .collect();
107    if prefix.is_empty() {
108        "(root)".to_string()
109    } else {
110        prefix.join("/")
111    }
112}
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117
118    #[test]
119    fn exclusive_dep_merges() {
120        let files = vec!["src/a.rs".into(), "src/b.rs".into(), "src/c.rs".into()];
121        // b only imported by a → merge
122        // c imported by a and b → not merged
123        let imports = vec![
124            ("src/a.rs".into(), "src/b.rs".into()),
125            ("src/a.rs".into(), "src/c.rs".into()),
126            ("src/b.rs".into(), "src/c.rs".into()),
127        ];
128        let modules = infer_modules(&imports, &files);
129        // a and b should be in same module, c separate
130        let ab_mod = modules
131            .iter()
132            .find(|m| m.files.contains(&"src/a.rs".to_string()));
133        assert!(ab_mod.is_some());
134        assert!(ab_mod.unwrap().files.contains(&"src/b.rs".to_string()));
135    }
136
137    #[test]
138    fn directory_fallback() {
139        let files = vec![
140            "src/core/x.rs".into(),
141            "src/core/y.rs".into(),
142            "src/util/z.rs".into(),
143        ];
144        // No exclusive deps, so directory fallback
145        let imports = vec![];
146        let modules = infer_modules(&imports, &files);
147        // core/x and core/y should be in same module
148        let core_mod = modules
149            .iter()
150            .find(|m| m.files.contains(&"src/core/x.rs".to_string()));
151        assert!(core_mod.is_some());
152        assert!(
153            core_mod
154                .unwrap()
155                .files
156                .contains(&"src/core/y.rs".to_string())
157        );
158    }
159}
cha_core/graph/module_graph.rs

cha_core/graph/
module_graph.rs
