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

fallow_graph/graph/
mod.rs
