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

fallow_graph/graph/
mod.rs
