Skip to main content

reflex/pulse/build/
modules.rs

1//! Modules: directories of source files, and the dependency graph between them.
2//!
3//! A module is a top-level directory (tier 1) or one of its immediate subdirectories
4//! with at least three source files (tier 2). Deeper files belong to their nearest
5//! module. Only [`FileRole::Source`] files count, so test corpora, fixtures and build
6//! scripts never become modules. Source files at the repository root form the root
7//! module `.`.
8
9use crate::pulse::extract::{Corpus, FileRole};
10use crate::pulse::model::ModuleId;
11use std::collections::{BTreeMap, BTreeSet};
12
13/// Minimum source files for a subdirectory to be its own module.
14pub const SUBMODULE_MIN_FILES: usize = 3;
15
16#[derive(Debug, Clone)]
17pub struct Module {
18    pub id: ModuleId,
19    pub tier: u8,
20    pub parent: Option<ModuleId>,
21    /// Indices into `Corpus::files`, sorted by path.
22    pub files: Vec<usize>,
23    pub lines: u64,
24    /// Language display name → file count.
25    pub languages: BTreeMap<String, usize>,
26}
27
28impl Module {
29    pub fn is_root(&self) -> bool {
30        self.id.as_str() == "."
31    }
32
33    /// Display name: the path, or `(root)`.
34    pub fn name(&self) -> &str {
35        if self.is_root() {
36            "(root)"
37        } else {
38            self.id.as_str()
39        }
40    }
41}
42
43/// Module-level view of the corpus.
44#[derive(Debug, Clone)]
45pub struct ModuleGraph {
46    /// Sorted by id.
47    pub modules: Vec<Module>,
48    /// File index → owning module index (source files only).
49    pub owner: BTreeMap<usize, usize>,
50    /// (from, to) module indices → number of file-level imports.
51    pub edges: BTreeMap<(usize, usize), usize>,
52}
53
54impl ModuleGraph {
55    pub fn build(corpus: &Corpus, max_depth: u8, min_files: usize) -> Self {
56        let source: Vec<(usize, &str)> = corpus
57            .with_role(FileRole::Source)
58            .map(|(i, f)| (i, f.path.as_str()))
59            .collect();
60
61        // Count source files per tier-2 candidate directory (`a/b` for `a/b/**`).
62        let mut sub_counts: BTreeMap<String, usize> = BTreeMap::new();
63        if max_depth >= 2 {
64            for (_, path) in &source {
65                let parts: Vec<&str> = path.split('/').collect();
66                if parts.len() >= 3 {
67                    *sub_counts
68                        .entry(format!("{}/{}", parts[0], parts[1]))
69                        .or_default() += 1;
70                }
71            }
72        }
73
74        let mut by_id: BTreeMap<String, Vec<usize>> = BTreeMap::new();
75        for (i, path) in &source {
76            let parts: Vec<&str> = path.split('/').collect();
77            let id = match parts.len() {
78                1 => ".".to_string(),
79                2 => parts[0].to_string(),
80                _ => {
81                    let sub = format!("{}/{}", parts[0], parts[1]);
82                    if sub_counts.get(&sub).copied().unwrap_or(0) >= SUBMODULE_MIN_FILES {
83                        sub
84                    } else {
85                        parts[0].to_string()
86                    }
87                }
88            };
89            by_id.entry(id).or_default().push(*i);
90        }
91        // Every tier-2 module needs its tier-1 parent, even with no direct files.
92        let parents: BTreeSet<String> = by_id
93            .keys()
94            .filter_map(|id| id.split_once('/').map(|(p, _)| p.to_string()))
95            .collect();
96        for p in parents {
97            by_id.entry(p).or_default();
98        }
99
100        let mut modules: Vec<Module> = by_id
101            .into_iter()
102            .map(|(id, mut files)| {
103                files.sort_unstable();
104                let mut languages = BTreeMap::new();
105                let mut lines = 0;
106                for &i in &files {
107                    let f = &corpus.files[i];
108                    lines += f.lines;
109                    *languages
110                        .entry(crate::pulse::extract::language_name(f.language))
111                        .or_insert(0) += 1;
112                }
113                let (tier, parent) = match id.split_once('/') {
114                    Some((p, _)) => (2, Some(ModuleId::new(p))),
115                    None => (1, None),
116                };
117                Module {
118                    id: ModuleId::new(id),
119                    tier,
120                    parent,
121                    files,
122                    lines,
123                    languages,
124                }
125            })
126            .collect();
127
128        // Drop small modules, but never a parent that still has children.
129        let total_files = |m: &Module, all: &[Module]| {
130            m.files.len()
131                + all
132                    .iter()
133                    .filter(|c| c.parent.as_ref() == Some(&m.id))
134                    .map(|c| c.files.len())
135                    .sum::<usize>()
136        };
137        let keep: Vec<bool> = modules
138            .iter()
139            .map(|m| total_files(m, &modules) >= min_files.max(1))
140            .collect();
141        let mut i = 0;
142        modules.retain(|_| {
143            i += 1;
144            keep[i - 1]
145        });
146
147        let mut owner = BTreeMap::new();
148        for (mi, m) in modules.iter().enumerate() {
149            for &f in &m.files {
150                owner.insert(f, mi);
151            }
152        }
153        let mut edges: BTreeMap<(usize, usize), usize> = BTreeMap::new();
154        for &(a, b) in &corpus.edges {
155            if let (Some(&ma), Some(&mb)) = (owner.get(&a), owner.get(&b))
156                && ma != mb
157            {
158                *edges.entry((ma, mb)).or_insert(0) += 1;
159            }
160        }
161        Self {
162            modules,
163            owner,
164            edges,
165        }
166    }
167
168    pub fn index_of(&self, id: &ModuleId) -> Option<usize> {
169        self.modules.binary_search_by(|m| m.id.cmp(id)).ok()
170    }
171
172    pub fn children(&self, mi: usize) -> Vec<usize> {
173        let id = &self.modules[mi].id;
174        (0..self.modules.len())
175            .filter(|&c| self.modules[c].parent.as_ref() == Some(id))
176            .collect()
177    }
178
179    /// Modules `mi` imports from, heaviest first: (module, import count).
180    pub fn dependencies(&self, mi: usize) -> Vec<(usize, usize)> {
181        let mut v: Vec<(usize, usize)> = self
182            .edges
183            .iter()
184            .filter(|((a, _), _)| *a == mi)
185            .map(|((_, b), n)| (*b, *n))
186            .collect();
187        v.sort_by(|x, y| y.1.cmp(&x.1).then(x.0.cmp(&y.0)));
188        v
189    }
190
191    /// Modules that import from `mi`, heaviest first.
192    pub fn dependents(&self, mi: usize) -> Vec<(usize, usize)> {
193        let mut v: Vec<(usize, usize)> = self
194            .edges
195            .iter()
196            .filter(|((_, b), _)| *b == mi)
197            .map(|((a, _), n)| (*a, *n))
198            .collect();
199        v.sort_by(|x, y| y.1.cmp(&x.1).then(x.0.cmp(&y.0)));
200        v
201    }
202
203    /// Strongly connected components with more than one module (dependency cycles),
204    /// each sorted, the list sorted. Tarjan's algorithm.
205    pub fn cycles(&self) -> Vec<Vec<usize>> {
206        let n = self.modules.len();
207        let mut adj = vec![Vec::new(); n];
208        for &(a, b) in self.edges.keys() {
209            adj[a].push(b);
210        }
211        struct State {
212            index: usize,
213            idx: Vec<Option<usize>>,
214            low: Vec<usize>,
215            on: Vec<bool>,
216            stack: Vec<usize>,
217            out: Vec<Vec<usize>>,
218        }
219        fn visit(v: usize, adj: &[Vec<usize>], s: &mut State) {
220            s.idx[v] = Some(s.index);
221            s.low[v] = s.index;
222            s.index += 1;
223            s.stack.push(v);
224            s.on[v] = true;
225            for &w in &adj[v] {
226                match s.idx[w] {
227                    None => {
228                        visit(w, adj, s);
229                        s.low[v] = s.low[v].min(s.low[w]);
230                    }
231                    Some(iw) if s.on[w] => s.low[v] = s.low[v].min(iw),
232                    _ => {}
233                }
234            }
235            if Some(s.low[v]) == s.idx[v] {
236                let mut comp = Vec::new();
237                while let Some(w) = s.stack.pop() {
238                    s.on[w] = false;
239                    comp.push(w);
240                    if w == v {
241                        break;
242                    }
243                }
244                if comp.len() > 1 {
245                    comp.sort_unstable();
246                    s.out.push(comp);
247                }
248            }
249        }
250        let mut s = State {
251            index: 0,
252            idx: vec![None; n],
253            low: vec![0; n],
254            on: vec![false; n],
255            stack: Vec::new(),
256            out: Vec::new(),
257        };
258        for v in 0..n {
259            if s.idx[v].is_none() {
260                visit(v, &adj, &mut s);
261            }
262        }
263        s.out.sort();
264        s.out
265    }
266
267    /// File-level fan-in within source files: (file index, dependents), highest first.
268    pub fn file_hotspots(&self, corpus: &Corpus, limit: usize) -> Vec<(usize, usize)> {
269        let mut fan_in: BTreeMap<usize, usize> = BTreeMap::new();
270        for &(a, b) in &corpus.edges {
271            if self.owner.contains_key(&a) && self.owner.contains_key(&b) {
272                *fan_in.entry(b).or_insert(0) += 1;
273            }
274        }
275        let mut v: Vec<(usize, usize)> = fan_in.into_iter().collect();
276        v.sort_by(|x, y| y.1.cmp(&x.1).then(x.0.cmp(&y.0)));
277        v.truncate(limit);
278        v
279    }
280}
281
282#[cfg(test)]
283mod tests {
284    use super::*;
285    use crate::models::Language;
286    use crate::pulse::extract::{FileInfo, roles};
287    use std::path::{Path, PathBuf};
288
289    fn corpus(paths: &[&str], edges: &[(usize, usize)]) -> Corpus {
290        let mut files: Vec<FileInfo> = paths
291            .iter()
292            .map(|p| FileInfo {
293                path: p.to_string(),
294                language: Language::from_path(Path::new(p)),
295                lines: 10,
296                role: roles::classify(p),
297                hash: String::new(),
298            })
299            .collect();
300        files.sort_by(|a, b| a.path.cmp(&b.path));
301        Corpus {
302            root: PathBuf::from("."),
303            files,
304            edges: edges.to_vec(),
305            imports: Vec::new(),
306            readme: None,
307        }
308    }
309
310    #[test]
311    fn modules_skip_non_source_and_split_tier_two() {
312        let c = corpus(
313            &[
314                "build.rs",
315                "src/lib.rs",
316                "src/main.rs",
317                "src/pulse/a.rs",
318                "src/pulse/b.rs",
319                "src/pulse/deep/c.rs",
320                "src/tiny/x.rs",
321                "tests/corpus/sample.rs",
322                "tests/it.rs",
323                "main.py",
324            ],
325            &[],
326        );
327        let g = ModuleGraph::build(&c, 2, 1);
328        let ids: Vec<&str> = g.modules.iter().map(|m| m.id.as_str()).collect();
329        assert_eq!(ids, vec![".", "src", "src/pulse"]);
330        let src = &g.modules[g.index_of(&"src".into()).unwrap()];
331        // src/tiny has 1 file (< 3), so it stays in `src`.
332        assert_eq!(src.files.len(), 3);
333        let pulse = &g.modules[g.index_of(&"src/pulse".into()).unwrap()];
334        assert_eq!(
335            pulse.files.len(),
336            3,
337            "deep files belong to the tier-2 module"
338        );
339        assert_eq!(pulse.parent.as_ref().unwrap().as_str(), "src");
340        assert_eq!(g.modules[0].name(), "(root)");
341    }
342
343    #[test]
344    fn depth_one_keeps_top_level_only() {
345        let c = corpus(&["src/a/1.rs", "src/a/2.rs", "src/a/3.rs"], &[]);
346        let g = ModuleGraph::build(&c, 1, 1);
347        let ids: Vec<&str> = g.modules.iter().map(|m| m.id.as_str()).collect();
348        assert_eq!(ids, vec!["src"]);
349    }
350
351    #[test]
352    fn edges_cycles_and_hotspots() {
353        // Files sorted: a/1.rs(0) a/2.rs(1) b/1.rs(2) b/2.rs(3) c/1.rs(4) c/2.rs(5)
354        let c = corpus(
355            &["a/1.rs", "a/2.rs", "b/1.rs", "b/2.rs", "c/1.rs", "c/2.rs"],
356            &[(0, 2), (1, 2), (2, 0), (4, 2)],
357        );
358        let g = ModuleGraph::build(&c, 2, 1);
359        let (a, b, cc) = (0, 1, 2);
360        assert_eq!(g.edges.get(&(a, b)), Some(&2));
361        assert_eq!(g.edges.get(&(b, a)), Some(&1));
362        assert_eq!(g.dependents(b), vec![(a, 2), (cc, 1)]);
363        assert_eq!(g.cycles(), vec![vec![a, b]]);
364        assert_eq!(g.file_hotspots(&c, 1), vec![(2, 3)]);
365    }
366}