fallow_graph/graph/
fan_io.rs

1//! Fan-in / fan-out + focus graph facts: from a changed-file set, compute
2//! the per-file graph blast-radius signals (fan-IN = importers, fan-OUT = forward
3//! deps) and the two confidence-flag signals (dynamic dispatch, re-export
4//! indirection) that the weighted focus map (`audit_focus.rs`) consumes.
5//!
6//! This is the graph-crate half of the focus map: all `ModuleGraph` access
7//! lives here (mirroring `impact_closure` / `partition_order`), so the CLI focus
8//! extractor stays a pure function of these resolved facts. The fan-in/out is the
9//! roadmap stage-4 "fan-in / fan-out (graph): reverse-deps + forward-deps; high
10//! fan-in = high blast radius" signal; the confidence flags are the
11//! "dynamically-wired / re-export-heavy code is not silently de-prioritized"
12//! guard.
13//!
14//! Determinism (matching the partition + order engine): the engine is a pure function of
15//! `(graph, changed_file_ids)`. No timestamps, no randomness, no float scoring.
16//! No `FxHashMap` iteration order reaches output: every collection is sorted
17//! before serialization in the path-resolved view.
18
19use std::path::{Path, PathBuf};
20
21use fallow_types::discover::FileId;
22use rustc_hash::FxHashSet;
23
24use super::{ModuleGraph, ReferenceKind};
25
26/// Per-file graph facts for one changed file, used by the focus map.
27///
28/// `fan_in` / `fan_out` are the blast-radius signals; `dynamic_dispatch` and
29/// `re_export_indirection` are the confidence-flag signals (a file that MAY be
30/// reached through dynamic dispatch or re-export indirection carries the flag so
31/// its static-reachability signal is not trusted as complete). `FileId`-keyed;
32/// the caller path-resolves via [`ModuleGraph::focus_facts_with_paths`].
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct FocusFileFacts {
35    /// The changed file these facts describe.
36    pub file: FileId,
37    /// Count of DISTINCT files importing this file (fan-in / blast radius).
38    /// Excludes the changed file itself.
39    pub fan_in: u32,
40    /// Count of DISTINCT forward-dependency files this file imports (fan-out).
41    /// Excludes the changed file itself.
42    pub fan_out: u32,
43    /// Whether this file is wired through dynamic dispatch: it has any outgoing
44    /// dynamic-import edge OR is referenced by another file via a `DynamicImport`
45    /// reference (DI / decorators / plugin-loader / `React.lazy` patterns the
46    /// static graph cannot fully resolve). Drives the `low: dynamic dispatch
47    /// detected` confidence flag. Conservative (over-flags): a file that MAY be
48    /// dynamically wired carries the flag.
49    pub dynamic_dispatch: bool,
50    /// Whether this file's reachability runs through re-export indirection: it is
51    /// a re-export barrel (has its own `re_exports`), is a re-export SOURCE of a
52    /// barrel, or is referenced via a `ReExport` reference. Drives the `low:
53    /// re-export indirection` confidence flag.
54    pub re_export_indirection: bool,
55}
56
57/// The same per-file facts with the `FileId` resolved to a root-relative,
58/// forward-slashed path string, sorted for deterministic output.
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct FocusFileFactsPaths {
61    /// Root-relative, forward-slashed path of the changed file.
62    pub file: String,
63    /// Fan-in count (importers).
64    pub fan_in: u32,
65    /// Fan-out count (forward deps).
66    pub fan_out: u32,
67    /// Dynamic-dispatch confidence signal.
68    pub dynamic_dispatch: bool,
69    /// Re-export-indirection confidence signal.
70    pub re_export_indirection: bool,
71}
72
73impl ModuleGraph {
74    /// Compute the per-file focus graph facts (fan-in/out + the two
75    /// confidence-flag signals) for a changed-file seed set.
76    ///
77    /// Out-of-range or duplicate ids in `changed` are tolerated (dropped /
78    /// deduped). Each fact is keyed by the changed file's `FileId`; the caller
79    /// relativizes via [`ModuleGraph::focus_facts_with_paths`] for serialization.
80    #[must_use]
81    pub fn focus_file_facts(&self, changed: &[FileId]) -> Vec<FocusFileFacts> {
82        // Dedup + drop out-of-range ids into a stable working set.
83        let mut seen = FxHashSet::default();
84        let mut changed_ids: Vec<FileId> = Vec::with_capacity(changed.len());
85        for &id in changed {
86            if (id.0 as usize) < self.modules.len() && seen.insert(id) {
87                changed_ids.push(id);
88            }
89        }
90        changed_ids.sort_unstable_by_key(|f| f.0);
91
92        // A file is referenced via a DynamicImport / ReExport when ANY export on
93        // ANY module carries such a reference TO it. Build the per-target signal
94        // sets once (a single pass over every export's references), so the
95        // per-changed-file lookups are O(1).
96        let (dynamic_targets, re_export_ref_targets) = self.collect_reference_signal_targets();
97
98        changed_ids
99            .iter()
100            .map(|&id| {
101                let fan_in = self.fan_in_count(id);
102                let fan_out = self.fan_out_count(id);
103                let dynamic_dispatch =
104                    dynamic_targets.contains(&id) || self.has_dynamic_outgoing_edge(id);
105                let re_export_indirection = re_export_ref_targets.contains(&id)
106                    || self.is_re_export_participant(id, &re_export_ref_targets);
107                FocusFileFacts {
108                    file: id,
109                    fan_in,
110                    fan_out,
111                    dynamic_dispatch,
112                    re_export_indirection,
113                }
114            })
115            .collect()
116    }
117
118    /// Distinct count of files importing `file` (fan-in), excluding `file`.
119    fn fan_in_count(&self, file: FileId) -> u32 {
120        let Some(importers) = self.reverse_deps.get(file.0 as usize) else {
121            return 0;
122        };
123        let mut distinct: FxHashSet<FileId> = FxHashSet::default();
124        for &importer in importers {
125            if importer != file {
126                distinct.insert(importer);
127            }
128        }
129        u32::try_from(distinct.len()).unwrap_or(u32::MAX)
130    }
131
132    /// Distinct count of forward-dependency files `file` imports (fan-out),
133    /// excluding self-edges.
134    fn fan_out_count(&self, file: FileId) -> u32 {
135        let mut distinct: FxHashSet<FileId> = FxHashSet::default();
136        for target in self.edges_for(file) {
137            if target != file {
138                distinct.insert(target);
139            }
140        }
141        u32::try_from(distinct.len()).unwrap_or(u32::MAX)
142    }
143
144    /// Build the set of files referenced via a `DynamicImport` reference and the
145    /// set referenced via a `ReExport` reference, in one pass over every export's
146    /// reference list.
147    fn collect_reference_signal_targets(&self) -> (FxHashSet<FileId>, FxHashSet<FileId>) {
148        let mut dynamic: FxHashSet<FileId> = FxHashSet::default();
149        let mut re_export: FxHashSet<FileId> = FxHashSet::default();
150        for node in &self.modules {
151            for export in &node.exports {
152                for reference in &export.references {
153                    match reference.kind {
154                        ReferenceKind::DynamicImport => {
155                            dynamic.insert(node.file_id);
156                        }
157                        ReferenceKind::ReExport => {
158                            re_export.insert(node.file_id);
159                        }
160                        _ => {}
161                    }
162                }
163            }
164        }
165        (dynamic, re_export)
166    }
167
168    /// Whether `file` has any outgoing edge whose target is dynamically imported.
169    /// The `Edge` type does not carry a per-edge kind, so this is approximated by
170    /// the presence of a dynamic reference FROM `file` on a target's export
171    /// reference list. Conservative: it is fine to over-flag.
172    fn has_dynamic_outgoing_edge(&self, file: FileId) -> bool {
173        // A target export referenced by `file` via DynamicImport means `file`
174        // dynamically imports that target.
175        self.modules.iter().any(|node| {
176            node.exports.iter().any(|export| {
177                export.references.iter().any(|reference| {
178                    reference.kind == ReferenceKind::DynamicImport && reference.from_file == file
179                })
180            })
181        })
182    }
183
184    /// Whether `file` participates in re-export indirection: it is a re-export
185    /// barrel (declares its own `re_exports`), it is a re-export SOURCE of some
186    /// barrel, or it is referenced via a `ReExport` reference (the
187    /// `re_export_ref_targets` membership the caller passes in).
188    fn is_re_export_participant(
189        &self,
190        file: FileId,
191        re_export_ref_targets: &FxHashSet<FileId>,
192    ) -> bool {
193        if re_export_ref_targets.contains(&file) {
194            return true;
195        }
196        // Barrel: declares its own re-exports.
197        if let Some(node) = self.modules.get(file.0 as usize)
198            && !node.re_exports.is_empty()
199        {
200            return true;
201        }
202        // Re-export SOURCE: some barrel re-exports FROM this file.
203        self.modules
204            .iter()
205            .any(|node| node.re_exports.iter().any(|edge| edge.source_file == file))
206    }
207
208    /// Resolve a `FocusFileFacts` set's `FileId`s to root-relative, forward-
209    /// slashed paths, sorted for deterministic output. Files whose module is
210    /// missing are dropped.
211    #[must_use]
212    pub fn focus_facts_with_paths(
213        &self,
214        facts: &[FocusFileFacts],
215        root: &Path,
216    ) -> Vec<FocusFileFactsPaths> {
217        let mut resolved: Vec<FocusFileFactsPaths> = facts
218            .iter()
219            .filter_map(|f| {
220                let path = self.modules.get(f.file.0 as usize)?;
221                Some(FocusFileFactsPaths {
222                    file: relativize(&path.path, root),
223                    fan_in: f.fan_in,
224                    fan_out: f.fan_out,
225                    dynamic_dispatch: f.dynamic_dispatch,
226                    re_export_indirection: f.re_export_indirection,
227                })
228            })
229            .collect();
230        resolved.sort_by(|a, b| a.file.cmp(&b.file));
231        resolved
232    }
233}
234
235/// Strip `root` and forward-slash-normalize a module path (mirrors
236/// `impact_closure::relativize` / `partition_order::relativize`).
237fn relativize(path: &Path, root: &Path) -> String {
238    let rel: PathBuf = path.strip_prefix(root).unwrap_or(path).to_path_buf();
239    rel.to_string_lossy().replace('\\', "/")
240}
241
242#[cfg(test)]
243mod tests {
244    use super::*;
245    use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
246    use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource};
247    use fallow_types::extract::{ExportInfo, ExportName, ImportInfo, ImportedName, VisibilityTag};
248    use std::path::PathBuf;
249
250    fn file(id: u32, path: &str) -> DiscoveredFile {
251        DiscoveredFile {
252            id: FileId(id),
253            path: PathBuf::from(path),
254            size_bytes: 10,
255        }
256    }
257
258    fn named_import(source: &str, name: &str, target: FileId) -> ResolvedImport {
259        ResolvedImport {
260            info: ImportInfo {
261                source: source.to_string(),
262                imported_name: ImportedName::Named(name.to_string()),
263                local_name: name.to_string(),
264                is_type_only: false,
265                from_style: false,
266                span: oxc_span::Span::new(0, 10),
267                source_span: oxc_span::Span::default(),
268            },
269            target: ResolveResult::InternalModule(target),
270        }
271    }
272
273    fn named_export(name: &str) -> ExportInfo {
274        ExportInfo {
275            name: ExportName::Named(name.to_string()),
276            local_name: Some(name.to_string()),
277            is_type_only: false,
278            visibility: VisibilityTag::None,
279            expected_unused_reason: None,
280            span: oxc_span::Span::new(0, 20),
281            members: vec![],
282            is_side_effect_used: false,
283            super_class: None,
284        }
285    }
286
287    /// core (0) <- mid (1) <- app (2). app imports mid imports core.
288    fn build_chain_graph() -> ModuleGraph {
289        let files = vec![
290            file(0, "/p/src/core.ts"),
291            file(1, "/p/src/mid.ts"),
292            file(2, "/p/src/app.ts"),
293        ];
294        let entry_points = vec![EntryPoint {
295            path: PathBuf::from("/p/src/app.ts"),
296            source: EntryPointSource::PackageJsonMain,
297        }];
298        let resolved = vec![
299            ResolvedModule {
300                file_id: FileId(0),
301                path: PathBuf::from("/p/src/core.ts"),
302                exports: vec![named_export("compute")],
303                ..Default::default()
304            },
305            ResolvedModule {
306                file_id: FileId(1),
307                path: PathBuf::from("/p/src/mid.ts"),
308                resolved_imports: vec![named_import("./core", "compute", FileId(0))],
309                exports: vec![named_export("midFn")],
310                ..Default::default()
311            },
312            ResolvedModule {
313                file_id: FileId(2),
314                path: PathBuf::from("/p/src/app.ts"),
315                resolved_imports: vec![named_import("./mid", "midFn", FileId(1))],
316                ..Default::default()
317            },
318        ];
319        ModuleGraph::build(&resolved, &entry_points, &files)
320    }
321
322    #[test]
323    fn fan_in_counts_importers() {
324        let graph = build_chain_graph();
325        // core is imported by mid: fan_in = 1, fan_out = 0.
326        let facts = graph.focus_file_facts(&[FileId(0)]);
327        assert_eq!(facts.len(), 1);
328        assert_eq!(facts[0].fan_in, 1);
329        assert_eq!(facts[0].fan_out, 0);
330    }
331
332    #[test]
333    fn fan_out_counts_forward_deps() {
334        let graph = build_chain_graph();
335        // app imports mid: fan_out = 1, fan_in = 0 (nothing imports app).
336        let facts = graph.focus_file_facts(&[FileId(2)]);
337        assert_eq!(facts.len(), 1);
338        assert_eq!(facts[0].fan_out, 1);
339        assert_eq!(facts[0].fan_in, 0);
340    }
341
342    #[test]
343    fn focus_facts_are_byte_identical_across_runs() {
344        let graph = build_chain_graph();
345        let changed = [FileId(0), FileId(1), FileId(2)];
346        let first = graph.focus_file_facts(&changed);
347        let second = graph.focus_file_facts(&changed);
348        assert_eq!(first, second);
349        let p1 = graph.focus_facts_with_paths(&first, Path::new("/p"));
350        let p2 = graph.focus_facts_with_paths(&second, Path::new("/p"));
351        assert_eq!(format!("{p1:?}"), format!("{p2:?}"));
352    }
353
354    #[test]
355    fn re_export_barrel_flags_indirection() {
356        use crate::resolve::ResolvedReExport;
357        use fallow_types::extract::ReExportInfo;
358
359        let files = vec![
360            file(0, "/p/src/impl.ts"),
361            file(1, "/p/src/barrel.ts"),
362            file(2, "/p/src/consumer.ts"),
363        ];
364        let entry_points = vec![EntryPoint {
365            path: PathBuf::from("/p/src/consumer.ts"),
366            source: EntryPointSource::PackageJsonMain,
367        }];
368        let resolved = vec![
369            ResolvedModule {
370                file_id: FileId(0),
371                path: PathBuf::from("/p/src/impl.ts"),
372                exports: vec![named_export("widget")],
373                ..Default::default()
374            },
375            ResolvedModule {
376                file_id: FileId(1),
377                path: PathBuf::from("/p/src/barrel.ts"),
378                re_exports: vec![ResolvedReExport {
379                    info: ReExportInfo {
380                        source: "./impl".to_string(),
381                        imported_name: "widget".to_string(),
382                        exported_name: "widget".to_string(),
383                        is_type_only: false,
384                        span: oxc_span::Span::new(0, 10),
385                    },
386                    target: ResolveResult::InternalModule(FileId(0)),
387                }],
388                ..Default::default()
389            },
390            ResolvedModule {
391                file_id: FileId(2),
392                path: PathBuf::from("/p/src/consumer.ts"),
393                resolved_imports: vec![named_import("./barrel", "widget", FileId(1))],
394                ..Default::default()
395            },
396        ];
397        let graph = ModuleGraph::build(&resolved, &entry_points, &files);
398        // barrel.ts declares re-exports -> flagged. impl.ts is a re-export source
399        // -> flagged.
400        let barrel = graph.focus_file_facts(&[FileId(1)]);
401        assert!(barrel[0].re_export_indirection, "barrel flags indirection");
402        let impl_facts = graph.focus_file_facts(&[FileId(0)]);
403        assert!(
404            impl_facts[0].re_export_indirection,
405            "re-export source flags indirection"
406        );
407    }
408
409    #[test]
410    fn empty_changed_set_yields_no_facts() {
411        let graph = build_chain_graph();
412        assert!(graph.focus_file_facts(&[]).is_empty());
413    }
414
415    #[test]
416    fn out_of_range_ids_are_dropped() {
417        let graph = build_chain_graph();
418        let facts = graph.focus_file_facts(&[FileId(999)]);
419        assert!(facts.is_empty());
420    }
421}
fallow_graph/graph/fan_io.rs

fallow_graph/graph/
fan_io.rs
