fallow_graph/graph/
mod.rs

1//! Module dependency graph with re-export chain propagation and reachability analysis.
2//!
3//! The graph is built from resolved modules and entry points, then used to determine
4//! which files are reachable and which exports are referenced.
5
6mod build;
7mod cycles;
8mod namespace_aliases;
9mod namespace_re_exports;
10mod narrowing;
11mod re_exports;
12mod reachability;
13pub mod types;
14
15use std::path::Path;
16
17use fixedbitset::FixedBitSet;
18use rustc_hash::{FxHashMap, FxHashSet};
19
20use crate::resolve::ResolvedModule;
21use fallow_types::discover::{DiscoveredFile, EntryPoint, FileId};
22use fallow_types::extract::ImportedName;
23
24pub use re_exports::GraphReExportCycle;
25pub use types::{ExportSymbol, ModuleNode, ReExportEdge, ReferenceKind, SymbolReference};
26
27/// True when the path's final component looks like a TypeScript declaration
28/// file (`.d.ts`, `.d.mts`, `.d.cts`). Used to seed declaration files as
29/// overall entry points so ambient `typeof import()` references stay alive.
30///
31/// Keep in sync with `fallow_core::analyze::predicates::is_declaration_file`;
32/// the graph crate cannot depend on core, so the predicate is duplicated.
33fn is_declaration_file_path(path: &Path) -> bool {
34    path.file_name()
35        .and_then(|n| n.to_str())
36        .is_some_and(|name| {
37            name.ends_with(".d.ts") || name.ends_with(".d.mts") || name.ends_with(".d.cts")
38        })
39}
40
41/// The core module dependency graph.
42#[derive(Debug)]
43pub struct ModuleGraph {
44    /// All modules indexed by `FileId`.
45    ///
46    /// Invariant: `modules[file_id.0 as usize].file_id == file_id` for every
47    /// `FileId` in the graph. Holds because `discover/walk.rs` assigns FileIds
48    /// sequentially via `.enumerate()` after path-sorting, and
49    /// `build::populate_edges` pushes one `ModuleNode` per file in iteration
50    /// order. Detectors rely on this for O(1) FileId-to-module lookup
51    /// (`graph.modules.get(file_id.0 as usize)`) instead of building a
52    /// per-call `FxHashMap<FileId, &ModuleNode>`.
53    pub modules: Vec<ModuleNode>,
54    /// Flat edge storage for cache-friendly iteration.
55    edges: Vec<Edge>,
56    /// Maps npm package names to the set of `FileId`s that import them.
57    pub package_usage: FxHashMap<String, Vec<FileId>>,
58    /// Maps npm package names to the set of `FileId`s that import them with type-only imports.
59    /// A package appearing here but not in `package_usage` (or only in both) indicates
60    /// it's only used for types and could be a devDependency.
61    pub type_only_package_usage: FxHashMap<String, Vec<FileId>>,
62    /// All entry point `FileId`s.
63    pub entry_points: FxHashSet<FileId>,
64    /// Runtime/application entry point `FileId`s.
65    pub runtime_entry_points: FxHashSet<FileId>,
66    /// Test entry point `FileId`s.
67    pub test_entry_points: FxHashSet<FileId>,
68    /// Reverse index: for each `FileId`, which files import it.
69    pub reverse_deps: Vec<Vec<FileId>>,
70    /// Precomputed: which modules have namespace imports (import * as ns).
71    namespace_imported: FixedBitSet,
72    /// Re-export cycles and self-loops detected during Phase 4 chain
73    /// resolution. Each entry names the participating files (sorted
74    /// lexicographically) and a `is_self_loop` flag distinguishing
75    /// single-file self-re-exports from multi-node cycles. Populated by
76    /// `re_exports::find_re_export_cycles` and consumed by
77    /// `fallow_core::analyze::re_export_cycles::find_re_export_cycles` which
78    /// wraps each entry in a typed `ReExportCycleFinding`.
79    pub re_export_cycles: Vec<GraphReExportCycle>,
80}
81
82/// An edge in the module graph.
83#[derive(Debug)]
84pub(super) struct Edge {
85    pub(super) source: FileId,
86    pub(super) target: FileId,
87    pub(super) symbols: Vec<ImportedSymbol>,
88}
89
90/// A symbol imported across an edge.
91#[derive(Debug)]
92pub(super) struct ImportedSymbol {
93    pub(super) imported_name: ImportedName,
94    pub(super) local_name: String,
95    /// Byte span of the import statement in the source file.
96    pub(super) import_span: oxc_span::Span,
97    /// Whether this import is type-only (`import type { ... }`).
98    /// Used to skip type-only edges in circular dependency detection.
99    pub(super) is_type_only: bool,
100}
101
102#[cfg(target_pointer_width = "64")]
103const _: () = assert!(std::mem::size_of::<Edge>() == 32);
104#[cfg(target_pointer_width = "64")]
105const _: () = assert!(std::mem::size_of::<ImportedSymbol>() == 64);
106
107impl ModuleGraph {
108    fn resolve_entry_point_ids(
109        entry_points: &[EntryPoint],
110        path_to_id: &FxHashMap<&Path, FileId>,
111    ) -> FxHashSet<FileId> {
112        entry_points
113            .iter()
114            .filter_map(|ep| {
115                path_to_id.get(ep.path.as_path()).copied().or_else(|| {
116                    dunce::canonicalize(&ep.path)
117                        .ok()
118                        .and_then(|path| path_to_id.get(path.as_path()).copied())
119                })
120            })
121            .collect()
122    }
123
124    /// Build the module graph from resolved modules and entry points.
125    pub fn build(
126        resolved_modules: &[ResolvedModule],
127        entry_points: &[EntryPoint],
128        files: &[DiscoveredFile],
129    ) -> Self {
130        Self::build_with_reachability_roots(
131            resolved_modules,
132            entry_points,
133            entry_points,
134            &[],
135            files,
136        )
137    }
138
139    /// Build the module graph with explicit runtime and test reachability roots.
140    pub fn build_with_reachability_roots(
141        resolved_modules: &[ResolvedModule],
142        entry_points: &[EntryPoint],
143        runtime_entry_points: &[EntryPoint],
144        test_entry_points: &[EntryPoint],
145        files: &[DiscoveredFile],
146    ) -> Self {
147        let _span = tracing::info_span!("build_graph").entered();
148
149        let module_count = files.len();
150
151        let max_file_id = files
152            .iter()
153            .map(|f| f.id.0 as usize)
154            .max()
155            .map_or(0, |m| m + 1);
156        let total_capacity = max_file_id.max(module_count);
157
158        let path_to_id: FxHashMap<&Path, FileId> =
159            files.iter().map(|f| (f.path.as_path(), f.id)).collect();
160
161        let module_by_id: FxHashMap<FileId, &ResolvedModule> =
162            resolved_modules.iter().map(|m| (m.file_id, m)).collect();
163
164        let mut entry_point_ids = Self::resolve_entry_point_ids(entry_points, &path_to_id);
165        let runtime_entry_point_ids =
166            Self::resolve_entry_point_ids(runtime_entry_points, &path_to_id);
167        let test_entry_point_ids = Self::resolve_entry_point_ids(test_entry_points, &path_to_id);
168
169        for file in files {
170            if is_declaration_file_path(&file.path) {
171                entry_point_ids.insert(file.id);
172            }
173        }
174
175        let mut graph = Self::populate_edges(
176            files,
177            &module_by_id,
178            &entry_point_ids,
179            &runtime_entry_point_ids,
180            &test_entry_point_ids,
181            module_count,
182            total_capacity,
183        );
184
185        graph.populate_references(&module_by_id, &entry_point_ids);
186
187        namespace_aliases::propagate_cross_package_aliases(&mut graph, &module_by_id);
188
189        namespace_re_exports::propagate_namespace_re_exports(&mut graph, &module_by_id);
190
191        graph.mark_reachable(
192            &entry_point_ids,
193            &runtime_entry_point_ids,
194            &test_entry_point_ids,
195            total_capacity,
196        );
197
198        graph.re_export_cycles = graph.resolve_re_export_chains();
199
200        graph
201    }
202
203    /// Total number of modules.
204    #[must_use]
205    pub const fn module_count(&self) -> usize {
206        self.modules.len()
207    }
208
209    /// Total number of edges.
210    #[must_use]
211    pub const fn edge_count(&self) -> usize {
212        self.edges.len()
213    }
214
215    /// Check if any importer uses `import * as ns` for this module.
216    /// Uses precomputed bitset — O(1) lookup.
217    #[must_use]
218    pub fn has_namespace_import(&self, file_id: FileId) -> bool {
219        let idx = file_id.0 as usize;
220        if idx >= self.namespace_imported.len() {
221            return false;
222        }
223        self.namespace_imported.contains(idx)
224    }
225
226    /// Get the target `FileId`s of all outgoing edges for a module.
227    #[must_use]
228    pub fn edges_for(&self, file_id: FileId) -> Vec<FileId> {
229        let idx = file_id.0 as usize;
230        if idx >= self.modules.len() {
231            return Vec::new();
232        }
233        let range = &self.modules[idx].edge_range;
234        self.edges[range.clone()].iter().map(|e| e.target).collect()
235    }
236
237    /// Find the byte offset of the import statement from `source` to `target`.
238    ///
239    /// Mixed type/value imports to the same target are stored as one edge. Prefer
240    /// the first value-carrying import so runtime-cycle diagnostics and line
241    /// suppressions anchor on the import that actually participates in the cycle.
242    /// Returns `None` if no edge exists or the edge has no symbols.
243    #[must_use]
244    pub fn find_import_span_start(&self, source: FileId, target: FileId) -> Option<u32> {
245        let idx = source.0 as usize;
246        if idx >= self.modules.len() {
247            return None;
248        }
249        let range = &self.modules[idx].edge_range;
250        for edge in &self.edges[range.clone()] {
251            if edge.target == target {
252                return edge
253                    .symbols
254                    .iter()
255                    .find(|s| !s.is_type_only)
256                    .or_else(|| edge.symbols.first())
257                    .map(|s| s.import_span.start);
258            }
259        }
260        None
261    }
262
263    /// Iterate outgoing edges with the data the boundary detector needs in a
264    /// single pass: target file id, whether every symbol on the edge is
265    /// type-only (matches the predicate used by cycle detection), and the
266    /// span start of the first value-carrying symbol (or the first symbol
267    /// when every symbol is type-only).
268    ///
269    /// When `featureB` has both `import type { Foo } from './x'` and
270    /// `import { bar } from './x'`, fallow groups them into ONE edge with the
271    /// type-only symbol first and the value symbol second. Consumers need the
272    /// value span so findings anchor on the runtime import line; otherwise a
273    /// `// fallow-ignore-next-line` above the type-only line would silently
274    /// suppress the real violation.
275    ///
276    /// Returns an empty iterator for out-of-range file ids.
277    pub fn outgoing_edge_summaries(
278        &self,
279        file_id: FileId,
280    ) -> impl Iterator<Item = (FileId, bool, Option<u32>)> + '_ {
281        let idx = file_id.0 as usize;
282        let range = if idx < self.modules.len() {
283            self.modules[idx].edge_range.clone()
284        } else {
285            0..0
286        };
287        self.edges[range].iter().map(|edge| {
288            let all_type_only =
289                !edge.symbols.is_empty() && edge.symbols.iter().all(|s| s.is_type_only);
290            let span = edge
291                .symbols
292                .iter()
293                .find(|s| !s.is_type_only)
294                .or_else(|| edge.symbols.first())
295                .map(|s| s.import_span.start);
296            (edge.target, all_type_only, span)
297        })
298    }
299}
300
301#[cfg(test)]
302mod tests {
303    use super::*;
304    use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
305    use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource, FileId};
306    use fallow_types::extract::{ExportName, ImportInfo, ImportedName, VisibilityTag};
307    use std::path::PathBuf;
308
309    fn build_simple_graph() -> ModuleGraph {
310        let files = vec![
311            DiscoveredFile {
312                id: FileId(0),
313                path: PathBuf::from("/project/src/entry.ts"),
314                size_bytes: 100,
315            },
316            DiscoveredFile {
317                id: FileId(1),
318                path: PathBuf::from("/project/src/utils.ts"),
319                size_bytes: 50,
320            },
321        ];
322
323        let entry_points = vec![EntryPoint {
324            path: PathBuf::from("/project/src/entry.ts"),
325            source: EntryPointSource::PackageJsonMain,
326        }];
327
328        let resolved_modules = vec![
329            ResolvedModule {
330                file_id: FileId(0),
331                path: PathBuf::from("/project/src/entry.ts"),
332                resolved_imports: vec![ResolvedImport {
333                    info: ImportInfo {
334                        source: "./utils".to_string(),
335                        imported_name: ImportedName::Named("foo".to_string()),
336                        local_name: "foo".to_string(),
337                        is_type_only: false,
338                        from_style: false,
339                        span: oxc_span::Span::new(0, 10),
340                        source_span: oxc_span::Span::default(),
341                    },
342                    target: ResolveResult::InternalModule(FileId(1)),
343                }],
344                ..Default::default()
345            },
346            ResolvedModule {
347                file_id: FileId(1),
348                path: PathBuf::from("/project/src/utils.ts"),
349                exports: vec![
350                    fallow_types::extract::ExportInfo {
351                        name: ExportName::Named("foo".to_string()),
352                        local_name: Some("foo".to_string()),
353                        is_type_only: false,
354                        visibility: VisibilityTag::None,
355                        span: oxc_span::Span::new(0, 20),
356                        members: vec![],
357                        is_side_effect_used: false,
358                        super_class: None,
359                    },
360                    fallow_types::extract::ExportInfo {
361                        name: ExportName::Named("bar".to_string()),
362                        local_name: Some("bar".to_string()),
363                        is_type_only: false,
364                        visibility: VisibilityTag::None,
365                        span: oxc_span::Span::new(25, 45),
366                        members: vec![],
367                        is_side_effect_used: false,
368                        super_class: None,
369                    },
370                ],
371                ..Default::default()
372            },
373        ];
374
375        ModuleGraph::build(&resolved_modules, &entry_points, &files)
376    }
377
378    #[test]
379    fn graph_module_count() {
380        let graph = build_simple_graph();
381        assert_eq!(graph.module_count(), 2);
382    }
383
384    #[test]
385    fn graph_edge_count() {
386        let graph = build_simple_graph();
387        assert_eq!(graph.edge_count(), 1);
388    }
389
390    #[test]
391    fn graph_entry_point_is_reachable() {
392        let graph = build_simple_graph();
393        assert!(graph.modules[0].is_entry_point());
394        assert!(graph.modules[0].is_reachable());
395    }
396
397    #[test]
398    fn graph_imported_module_is_reachable() {
399        let graph = build_simple_graph();
400        assert!(!graph.modules[1].is_entry_point());
401        assert!(graph.modules[1].is_reachable());
402    }
403
404    #[test]
405    #[expect(
406        clippy::too_many_lines,
407        reason = "this test fixture exercises four reachability roles end-to-end; splitting it \
408                  would obscure the cross-role assertions"
409    )]
410    fn graph_distinguishes_runtime_test_and_support_reachability() {
411        let files = vec![
412            DiscoveredFile {
413                id: FileId(0),
414                path: PathBuf::from("/project/src/main.ts"),
415                size_bytes: 100,
416            },
417            DiscoveredFile {
418                id: FileId(1),
419                path: PathBuf::from("/project/src/runtime-only.ts"),
420                size_bytes: 50,
421            },
422            DiscoveredFile {
423                id: FileId(2),
424                path: PathBuf::from("/project/tests/app.test.ts"),
425                size_bytes: 50,
426            },
427            DiscoveredFile {
428                id: FileId(3),
429                path: PathBuf::from("/project/tests/setup.ts"),
430                size_bytes: 50,
431            },
432            DiscoveredFile {
433                id: FileId(4),
434                path: PathBuf::from("/project/src/covered.ts"),
435                size_bytes: 50,
436            },
437        ];
438
439        let all_entry_points = vec![
440            EntryPoint {
441                path: PathBuf::from("/project/src/main.ts"),
442                source: EntryPointSource::PackageJsonMain,
443            },
444            EntryPoint {
445                path: PathBuf::from("/project/tests/app.test.ts"),
446                source: EntryPointSource::TestFile,
447            },
448            EntryPoint {
449                path: PathBuf::from("/project/tests/setup.ts"),
450                source: EntryPointSource::Plugin {
451                    name: "vitest".to_string(),
452                },
453            },
454        ];
455        let runtime_entry_points = vec![EntryPoint {
456            path: PathBuf::from("/project/src/main.ts"),
457            source: EntryPointSource::PackageJsonMain,
458        }];
459        let test_entry_points = vec![EntryPoint {
460            path: PathBuf::from("/project/tests/app.test.ts"),
461            source: EntryPointSource::TestFile,
462        }];
463
464        let resolved_modules = vec![
465            ResolvedModule {
466                file_id: FileId(0),
467                path: PathBuf::from("/project/src/main.ts"),
468                resolved_imports: vec![ResolvedImport {
469                    info: ImportInfo {
470                        source: "./runtime-only".to_string(),
471                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
472                        local_name: "runtimeOnly".to_string(),
473                        is_type_only: false,
474                        from_style: false,
475                        span: oxc_span::Span::new(0, 10),
476                        source_span: oxc_span::Span::default(),
477                    },
478                    target: ResolveResult::InternalModule(FileId(1)),
479                }],
480                ..Default::default()
481            },
482            ResolvedModule {
483                file_id: FileId(1),
484                path: PathBuf::from("/project/src/runtime-only.ts"),
485                exports: vec![fallow_types::extract::ExportInfo {
486                    name: ExportName::Named("runtimeOnly".to_string()),
487                    local_name: Some("runtimeOnly".to_string()),
488                    is_type_only: false,
489                    visibility: VisibilityTag::None,
490                    span: oxc_span::Span::new(0, 20),
491                    members: vec![],
492                    is_side_effect_used: false,
493                    super_class: None,
494                }],
495                ..Default::default()
496            },
497            ResolvedModule {
498                file_id: FileId(2),
499                path: PathBuf::from("/project/tests/app.test.ts"),
500                resolved_imports: vec![ResolvedImport {
501                    info: ImportInfo {
502                        source: "../src/covered".to_string(),
503                        imported_name: ImportedName::Named("covered".to_string()),
504                        local_name: "covered".to_string(),
505                        is_type_only: false,
506                        from_style: false,
507                        span: oxc_span::Span::new(0, 10),
508                        source_span: oxc_span::Span::default(),
509                    },
510                    target: ResolveResult::InternalModule(FileId(4)),
511                }],
512                ..Default::default()
513            },
514            ResolvedModule {
515                file_id: FileId(3),
516                path: PathBuf::from("/project/tests/setup.ts"),
517                resolved_imports: vec![ResolvedImport {
518                    info: ImportInfo {
519                        source: "../src/runtime-only".to_string(),
520                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
521                        local_name: "runtimeOnly".to_string(),
522                        is_type_only: false,
523                        from_style: false,
524                        span: oxc_span::Span::new(0, 10),
525                        source_span: oxc_span::Span::default(),
526                    },
527                    target: ResolveResult::InternalModule(FileId(1)),
528                }],
529                ..Default::default()
530            },
531            ResolvedModule {
532                file_id: FileId(4),
533                path: PathBuf::from("/project/src/covered.ts"),
534                exports: vec![fallow_types::extract::ExportInfo {
535                    name: ExportName::Named("covered".to_string()),
536                    local_name: Some("covered".to_string()),
537                    is_type_only: false,
538                    visibility: VisibilityTag::None,
539                    span: oxc_span::Span::new(0, 20),
540                    members: vec![],
541                    is_side_effect_used: false,
542                    super_class: None,
543                }],
544                ..Default::default()
545            },
546        ];
547
548        let graph = ModuleGraph::build_with_reachability_roots(
549            &resolved_modules,
550            &all_entry_points,
551            &runtime_entry_points,
552            &test_entry_points,
553            &files,
554        );
555
556        assert!(graph.modules[1].is_reachable());
557        assert!(graph.modules[1].is_runtime_reachable());
558        assert!(
559            !graph.modules[1].is_test_reachable(),
560            "support roots should not make runtime-only modules test reachable"
561        );
562
563        assert!(graph.modules[4].is_reachable());
564        assert!(graph.modules[4].is_test_reachable());
565        assert!(
566            !graph.modules[4].is_runtime_reachable(),
567            "test-only reachability should stay separate from runtime roots"
568        );
569    }
570
571    #[test]
572    fn graph_export_has_reference() {
573        let graph = build_simple_graph();
574        let utils = &graph.modules[1];
575        let foo_export = utils
576            .exports
577            .iter()
578            .find(|e| e.name.to_string() == "foo")
579            .unwrap();
580        assert!(
581            !foo_export.references.is_empty(),
582            "foo should have references"
583        );
584    }
585
586    #[test]
587    fn graph_unused_export_no_reference() {
588        let graph = build_simple_graph();
589        let utils = &graph.modules[1];
590        let bar_export = utils
591            .exports
592            .iter()
593            .find(|e| e.name.to_string() == "bar")
594            .unwrap();
595        assert!(
596            bar_export.references.is_empty(),
597            "bar should have no references"
598        );
599    }
600
601    #[test]
602    fn graph_no_namespace_import() {
603        let graph = build_simple_graph();
604        assert!(!graph.has_namespace_import(FileId(0)));
605        assert!(!graph.has_namespace_import(FileId(1)));
606    }
607
608    #[test]
609    fn graph_has_namespace_import() {
610        let files = vec![
611            DiscoveredFile {
612                id: FileId(0),
613                path: PathBuf::from("/project/entry.ts"),
614                size_bytes: 100,
615            },
616            DiscoveredFile {
617                id: FileId(1),
618                path: PathBuf::from("/project/utils.ts"),
619                size_bytes: 50,
620            },
621        ];
622
623        let entry_points = vec![EntryPoint {
624            path: PathBuf::from("/project/entry.ts"),
625            source: EntryPointSource::PackageJsonMain,
626        }];
627
628        let resolved_modules = vec![
629            ResolvedModule {
630                file_id: FileId(0),
631                path: PathBuf::from("/project/entry.ts"),
632                resolved_imports: vec![ResolvedImport {
633                    info: ImportInfo {
634                        source: "./utils".to_string(),
635                        imported_name: ImportedName::Namespace,
636                        local_name: "utils".to_string(),
637                        is_type_only: false,
638                        from_style: false,
639                        span: oxc_span::Span::new(0, 10),
640                        source_span: oxc_span::Span::default(),
641                    },
642                    target: ResolveResult::InternalModule(FileId(1)),
643                }],
644                ..Default::default()
645            },
646            ResolvedModule {
647                file_id: FileId(1),
648                path: PathBuf::from("/project/utils.ts"),
649                exports: vec![fallow_types::extract::ExportInfo {
650                    name: ExportName::Named("foo".to_string()),
651                    local_name: Some("foo".to_string()),
652                    is_type_only: false,
653                    visibility: VisibilityTag::None,
654                    span: oxc_span::Span::new(0, 20),
655                    members: vec![],
656                    is_side_effect_used: false,
657                    super_class: None,
658                }],
659                ..Default::default()
660            },
661        ];
662
663        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
664        assert!(
665            graph.has_namespace_import(FileId(1)),
666            "utils should have namespace import"
667        );
668    }
669
670    #[test]
671    fn graph_has_namespace_import_out_of_bounds() {
672        let graph = build_simple_graph();
673        assert!(!graph.has_namespace_import(FileId(999)));
674    }
675
676    #[test]
677    fn graph_unreachable_module() {
678        let files = vec![
679            DiscoveredFile {
680                id: FileId(0),
681                path: PathBuf::from("/project/entry.ts"),
682                size_bytes: 100,
683            },
684            DiscoveredFile {
685                id: FileId(1),
686                path: PathBuf::from("/project/utils.ts"),
687                size_bytes: 50,
688            },
689            DiscoveredFile {
690                id: FileId(2),
691                path: PathBuf::from("/project/orphan.ts"),
692                size_bytes: 30,
693            },
694        ];
695
696        let entry_points = vec![EntryPoint {
697            path: PathBuf::from("/project/entry.ts"),
698            source: EntryPointSource::PackageJsonMain,
699        }];
700
701        let resolved_modules = vec![
702            ResolvedModule {
703                file_id: FileId(0),
704                path: PathBuf::from("/project/entry.ts"),
705                resolved_imports: vec![ResolvedImport {
706                    info: ImportInfo {
707                        source: "./utils".to_string(),
708                        imported_name: ImportedName::Named("foo".to_string()),
709                        local_name: "foo".to_string(),
710                        is_type_only: false,
711                        from_style: false,
712                        span: oxc_span::Span::new(0, 10),
713                        source_span: oxc_span::Span::default(),
714                    },
715                    target: ResolveResult::InternalModule(FileId(1)),
716                }],
717                ..Default::default()
718            },
719            ResolvedModule {
720                file_id: FileId(1),
721                path: PathBuf::from("/project/utils.ts"),
722                exports: vec![fallow_types::extract::ExportInfo {
723                    name: ExportName::Named("foo".to_string()),
724                    local_name: Some("foo".to_string()),
725                    is_type_only: false,
726                    visibility: VisibilityTag::None,
727                    span: oxc_span::Span::new(0, 20),
728                    members: vec![],
729                    is_side_effect_used: false,
730                    super_class: None,
731                }],
732                ..Default::default()
733            },
734            ResolvedModule {
735                file_id: FileId(2),
736                path: PathBuf::from("/project/orphan.ts"),
737                exports: vec![fallow_types::extract::ExportInfo {
738                    name: ExportName::Named("orphan".to_string()),
739                    local_name: Some("orphan".to_string()),
740                    is_type_only: false,
741                    visibility: VisibilityTag::None,
742                    span: oxc_span::Span::new(0, 20),
743                    members: vec![],
744                    is_side_effect_used: false,
745                    super_class: None,
746                }],
747                ..Default::default()
748            },
749        ];
750
751        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
752
753        assert!(graph.modules[0].is_reachable(), "entry should be reachable");
754        assert!(graph.modules[1].is_reachable(), "utils should be reachable");
755        assert!(
756            !graph.modules[2].is_reachable(),
757            "orphan should NOT be reachable"
758        );
759    }
760
761    #[test]
762    fn graph_package_usage_tracked() {
763        let files = vec![DiscoveredFile {
764            id: FileId(0),
765            path: PathBuf::from("/project/entry.ts"),
766            size_bytes: 100,
767        }];
768
769        let entry_points = vec![EntryPoint {
770            path: PathBuf::from("/project/entry.ts"),
771            source: EntryPointSource::PackageJsonMain,
772        }];
773
774        let resolved_modules = vec![ResolvedModule {
775            file_id: FileId(0),
776            path: PathBuf::from("/project/entry.ts"),
777            exports: vec![],
778            re_exports: vec![],
779            resolved_imports: vec![
780                ResolvedImport {
781                    info: ImportInfo {
782                        source: "react".to_string(),
783                        imported_name: ImportedName::Default,
784                        local_name: "React".to_string(),
785                        is_type_only: false,
786                        from_style: false,
787                        span: oxc_span::Span::new(0, 10),
788                        source_span: oxc_span::Span::default(),
789                    },
790                    target: ResolveResult::NpmPackage("react".to_string()),
791                },
792                ResolvedImport {
793                    info: ImportInfo {
794                        source: "lodash".to_string(),
795                        imported_name: ImportedName::Named("merge".to_string()),
796                        local_name: "merge".to_string(),
797                        is_type_only: false,
798                        from_style: false,
799                        span: oxc_span::Span::new(15, 30),
800                        source_span: oxc_span::Span::default(),
801                    },
802                    target: ResolveResult::NpmPackage("lodash".to_string()),
803                },
804            ],
805            ..Default::default()
806        }];
807
808        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
809        assert!(graph.package_usage.contains_key("react"));
810        assert!(graph.package_usage.contains_key("lodash"));
811        assert!(!graph.package_usage.contains_key("express"));
812    }
813
814    #[test]
815    fn graph_empty() {
816        let graph = ModuleGraph::build(&[], &[], &[]);
817        assert_eq!(graph.module_count(), 0);
818        assert_eq!(graph.edge_count(), 0);
819    }
820
821    #[test]
822    fn graph_cjs_exports_tracked() {
823        let files = vec![DiscoveredFile {
824            id: FileId(0),
825            path: PathBuf::from("/project/entry.ts"),
826            size_bytes: 100,
827        }];
828
829        let entry_points = vec![EntryPoint {
830            path: PathBuf::from("/project/entry.ts"),
831            source: EntryPointSource::PackageJsonMain,
832        }];
833
834        let resolved_modules = vec![ResolvedModule {
835            file_id: FileId(0),
836            path: PathBuf::from("/project/entry.ts"),
837            has_cjs_exports: true,
838            has_angular_component_template_url: false,
839            ..Default::default()
840        }];
841
842        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
843        assert!(graph.modules[0].has_cjs_exports());
844    }
845
846    #[test]
847    fn graph_edges_for_returns_targets() {
848        let graph = build_simple_graph();
849        let targets = graph.edges_for(FileId(0));
850        assert_eq!(targets, vec![FileId(1)]);
851    }
852
853    #[test]
854    fn graph_edges_for_no_imports() {
855        let graph = build_simple_graph();
856        let targets = graph.edges_for(FileId(1));
857        assert!(targets.is_empty());
858    }
859
860    #[test]
861    fn graph_edges_for_out_of_bounds() {
862        let graph = build_simple_graph();
863        let targets = graph.edges_for(FileId(999));
864        assert!(targets.is_empty());
865    }
866
867    #[test]
868    fn graph_find_import_span_start_found() {
869        let graph = build_simple_graph();
870        let span_start = graph.find_import_span_start(FileId(0), FileId(1));
871        assert!(span_start.is_some());
872        assert_eq!(span_start.unwrap(), 0);
873    }
874
875    #[test]
876    fn graph_find_import_span_start_prefers_value_import_on_mixed_edge() {
877        let files = vec![
878            DiscoveredFile {
879                id: FileId(0),
880                path: PathBuf::from("/project/entry.ts"),
881                size_bytes: 100,
882            },
883            DiscoveredFile {
884                id: FileId(1),
885                path: PathBuf::from("/project/utils.ts"),
886                size_bytes: 50,
887            },
888        ];
889        let entry_points = vec![EntryPoint {
890            path: PathBuf::from("/project/entry.ts"),
891            source: EntryPointSource::PackageJsonMain,
892        }];
893        let resolved_modules = vec![
894            ResolvedModule {
895                file_id: FileId(0),
896                path: PathBuf::from("/project/entry.ts"),
897                resolved_imports: vec![
898                    ResolvedImport {
899                        info: ImportInfo {
900                            source: "./utils".to_string(),
901                            imported_name: ImportedName::Named("Foo".to_string()),
902                            local_name: "Foo".to_string(),
903                            is_type_only: true,
904                            from_style: false,
905                            span: oxc_span::Span::new(10, 20),
906                            source_span: oxc_span::Span::default(),
907                        },
908                        target: ResolveResult::InternalModule(FileId(1)),
909                    },
910                    ResolvedImport {
911                        info: ImportInfo {
912                            source: "./utils".to_string(),
913                            imported_name: ImportedName::Named("foo".to_string()),
914                            local_name: "foo".to_string(),
915                            is_type_only: false,
916                            from_style: false,
917                            span: oxc_span::Span::new(50, 60),
918                            source_span: oxc_span::Span::default(),
919                        },
920                        target: ResolveResult::InternalModule(FileId(1)),
921                    },
922                ],
923                ..Default::default()
924            },
925            ResolvedModule {
926                file_id: FileId(1),
927                path: PathBuf::from("/project/utils.ts"),
928                ..Default::default()
929            },
930        ];
931
932        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
933        assert_eq!(graph.find_import_span_start(FileId(0), FileId(1)), Some(50));
934    }
935
936    #[test]
937    fn graph_find_import_span_start_wrong_target() {
938        let graph = build_simple_graph();
939        let span_start = graph.find_import_span_start(FileId(0), FileId(0));
940        assert!(span_start.is_none());
941    }
942
943    #[test]
944    fn graph_find_import_span_start_source_out_of_bounds() {
945        let graph = build_simple_graph();
946        let span_start = graph.find_import_span_start(FileId(999), FileId(1));
947        assert!(span_start.is_none());
948    }
949
950    #[test]
951    fn graph_find_import_span_start_no_edges() {
952        let graph = build_simple_graph();
953        let span_start = graph.find_import_span_start(FileId(1), FileId(0));
954        assert!(span_start.is_none());
955    }
956
957    #[test]
958    fn graph_reverse_deps_populated() {
959        let graph = build_simple_graph();
960        assert!(graph.reverse_deps[1].contains(&FileId(0)));
961        assert!(graph.reverse_deps[0].is_empty());
962    }
963
964    #[test]
965    fn graph_type_only_package_usage_tracked() {
966        let files = vec![DiscoveredFile {
967            id: FileId(0),
968            path: PathBuf::from("/project/entry.ts"),
969            size_bytes: 100,
970        }];
971        let entry_points = vec![EntryPoint {
972            path: PathBuf::from("/project/entry.ts"),
973            source: EntryPointSource::PackageJsonMain,
974        }];
975        let resolved_modules = vec![ResolvedModule {
976            file_id: FileId(0),
977            path: PathBuf::from("/project/entry.ts"),
978            resolved_imports: vec![
979                ResolvedImport {
980                    info: ImportInfo {
981                        source: "react".to_string(),
982                        imported_name: ImportedName::Named("FC".to_string()),
983                        local_name: "FC".to_string(),
984                        is_type_only: true,
985                        from_style: false,
986                        span: oxc_span::Span::new(0, 10),
987                        source_span: oxc_span::Span::default(),
988                    },
989                    target: ResolveResult::NpmPackage("react".to_string()),
990                },
991                ResolvedImport {
992                    info: ImportInfo {
993                        source: "react".to_string(),
994                        imported_name: ImportedName::Named("useState".to_string()),
995                        local_name: "useState".to_string(),
996                        is_type_only: false,
997                        from_style: false,
998                        span: oxc_span::Span::new(15, 30),
999                        source_span: oxc_span::Span::default(),
1000                    },
1001                    target: ResolveResult::NpmPackage("react".to_string()),
1002                },
1003            ],
1004            ..Default::default()
1005        }];
1006
1007        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1008        assert!(graph.package_usage.contains_key("react"));
1009        assert!(graph.type_only_package_usage.contains_key("react"));
1010    }
1011
1012    #[test]
1013    fn graph_default_import_reference() {
1014        let files = vec![
1015            DiscoveredFile {
1016                id: FileId(0),
1017                path: PathBuf::from("/project/entry.ts"),
1018                size_bytes: 100,
1019            },
1020            DiscoveredFile {
1021                id: FileId(1),
1022                path: PathBuf::from("/project/utils.ts"),
1023                size_bytes: 50,
1024            },
1025        ];
1026        let entry_points = vec![EntryPoint {
1027            path: PathBuf::from("/project/entry.ts"),
1028            source: EntryPointSource::PackageJsonMain,
1029        }];
1030        let resolved_modules = vec![
1031            ResolvedModule {
1032                file_id: FileId(0),
1033                path: PathBuf::from("/project/entry.ts"),
1034                resolved_imports: vec![ResolvedImport {
1035                    info: ImportInfo {
1036                        source: "./utils".to_string(),
1037                        imported_name: ImportedName::Default,
1038                        local_name: "Utils".to_string(),
1039                        is_type_only: false,
1040                        from_style: false,
1041                        span: oxc_span::Span::new(0, 10),
1042                        source_span: oxc_span::Span::default(),
1043                    },
1044                    target: ResolveResult::InternalModule(FileId(1)),
1045                }],
1046                ..Default::default()
1047            },
1048            ResolvedModule {
1049                file_id: FileId(1),
1050                path: PathBuf::from("/project/utils.ts"),
1051                exports: vec![fallow_types::extract::ExportInfo {
1052                    name: ExportName::Default,
1053                    local_name: None,
1054                    is_type_only: false,
1055                    visibility: VisibilityTag::None,
1056                    span: oxc_span::Span::new(0, 20),
1057                    members: vec![],
1058                    is_side_effect_used: false,
1059                    super_class: None,
1060                }],
1061                ..Default::default()
1062            },
1063        ];
1064
1065        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1066        let utils = &graph.modules[1];
1067        let default_export = utils
1068            .exports
1069            .iter()
1070            .find(|e| matches!(e.name, ExportName::Default))
1071            .unwrap();
1072        assert!(!default_export.references.is_empty());
1073        assert_eq!(
1074            default_export.references[0].kind,
1075            ReferenceKind::DefaultImport
1076        );
1077    }
1078
1079    #[test]
1080    fn graph_side_effect_import_no_export_reference() {
1081        let files = vec![
1082            DiscoveredFile {
1083                id: FileId(0),
1084                path: PathBuf::from("/project/entry.ts"),
1085                size_bytes: 100,
1086            },
1087            DiscoveredFile {
1088                id: FileId(1),
1089                path: PathBuf::from("/project/styles.ts"),
1090                size_bytes: 50,
1091            },
1092        ];
1093        let entry_points = vec![EntryPoint {
1094            path: PathBuf::from("/project/entry.ts"),
1095            source: EntryPointSource::PackageJsonMain,
1096        }];
1097        let resolved_modules = vec![
1098            ResolvedModule {
1099                file_id: FileId(0),
1100                path: PathBuf::from("/project/entry.ts"),
1101                resolved_imports: vec![ResolvedImport {
1102                    info: ImportInfo {
1103                        source: "./styles".to_string(),
1104                        imported_name: ImportedName::SideEffect,
1105                        local_name: String::new(),
1106                        is_type_only: false,
1107                        from_style: false,
1108                        span: oxc_span::Span::new(0, 10),
1109                        source_span: oxc_span::Span::default(),
1110                    },
1111                    target: ResolveResult::InternalModule(FileId(1)),
1112                }],
1113                ..Default::default()
1114            },
1115            ResolvedModule {
1116                file_id: FileId(1),
1117                path: PathBuf::from("/project/styles.ts"),
1118                exports: vec![fallow_types::extract::ExportInfo {
1119                    name: ExportName::Named("primaryColor".to_string()),
1120                    local_name: Some("primaryColor".to_string()),
1121                    is_type_only: false,
1122                    visibility: VisibilityTag::None,
1123                    span: oxc_span::Span::new(0, 20),
1124                    members: vec![],
1125                    is_side_effect_used: false,
1126                    super_class: None,
1127                }],
1128                ..Default::default()
1129            },
1130        ];
1131
1132        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1133        assert_eq!(graph.edge_count(), 1);
1134        let styles = &graph.modules[1];
1135        let export = &styles.exports[0];
1136        assert!(
1137            export.references.is_empty(),
1138            "side-effect import should not reference named exports"
1139        );
1140    }
1141
1142    #[test]
1143    fn graph_multiple_entry_points() {
1144        let files = vec![
1145            DiscoveredFile {
1146                id: FileId(0),
1147                path: PathBuf::from("/project/main.ts"),
1148                size_bytes: 100,
1149            },
1150            DiscoveredFile {
1151                id: FileId(1),
1152                path: PathBuf::from("/project/worker.ts"),
1153                size_bytes: 100,
1154            },
1155            DiscoveredFile {
1156                id: FileId(2),
1157                path: PathBuf::from("/project/shared.ts"),
1158                size_bytes: 50,
1159            },
1160        ];
1161        let entry_points = vec![
1162            EntryPoint {
1163                path: PathBuf::from("/project/main.ts"),
1164                source: EntryPointSource::PackageJsonMain,
1165            },
1166            EntryPoint {
1167                path: PathBuf::from("/project/worker.ts"),
1168                source: EntryPointSource::PackageJsonMain,
1169            },
1170        ];
1171        let resolved_modules = vec![
1172            ResolvedModule {
1173                file_id: FileId(0),
1174                path: PathBuf::from("/project/main.ts"),
1175                resolved_imports: vec![ResolvedImport {
1176                    info: ImportInfo {
1177                        source: "./shared".to_string(),
1178                        imported_name: ImportedName::Named("helper".to_string()),
1179                        local_name: "helper".to_string(),
1180                        is_type_only: false,
1181                        from_style: false,
1182                        span: oxc_span::Span::new(0, 10),
1183                        source_span: oxc_span::Span::default(),
1184                    },
1185                    target: ResolveResult::InternalModule(FileId(2)),
1186                }],
1187                ..Default::default()
1188            },
1189            ResolvedModule {
1190                file_id: FileId(1),
1191                path: PathBuf::from("/project/worker.ts"),
1192                ..Default::default()
1193            },
1194            ResolvedModule {
1195                file_id: FileId(2),
1196                path: PathBuf::from("/project/shared.ts"),
1197                exports: vec![fallow_types::extract::ExportInfo {
1198                    name: ExportName::Named("helper".to_string()),
1199                    local_name: Some("helper".to_string()),
1200                    is_type_only: false,
1201                    visibility: VisibilityTag::None,
1202                    span: oxc_span::Span::new(0, 20),
1203                    members: vec![],
1204                    is_side_effect_used: false,
1205                    super_class: None,
1206                }],
1207                ..Default::default()
1208            },
1209        ];
1210
1211        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1212        assert!(graph.modules[0].is_entry_point());
1213        assert!(graph.modules[1].is_entry_point());
1214        assert!(!graph.modules[2].is_entry_point());
1215        assert!(graph.modules[0].is_reachable());
1216        assert!(graph.modules[1].is_reachable());
1217        assert!(graph.modules[2].is_reachable());
1218    }
1219}
fallow_graph/graph/mod.rs

fallow_graph/graph/
mod.rs
