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::Path;
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<&Path, FileId>,
82    ) -> FxHashSet<FileId> {
83        entry_points
84            .iter()
85            .filter_map(|ep| {
86                path_to_id.get(ep.path.as_path()).copied().or_else(|| {
87                    dunce::canonicalize(&ep.path)
88                        .ok()
89                        .and_then(|path| path_to_id.get(path.as_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 (borrows paths from files slice to avoid cloning)
132        let path_to_id: FxHashMap<&Path, FileId> =
133            files.iter().map(|f| (f.path.as_path(), 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    #[expect(
341        clippy::too_many_lines,
342        reason = "integration test with extensive fixture setup"
343    )]
344    fn graph_distinguishes_runtime_test_and_support_reachability() {
345        let files = vec![
346            DiscoveredFile {
347                id: FileId(0),
348                path: PathBuf::from("/project/src/main.ts"),
349                size_bytes: 100,
350            },
351            DiscoveredFile {
352                id: FileId(1),
353                path: PathBuf::from("/project/src/runtime-only.ts"),
354                size_bytes: 50,
355            },
356            DiscoveredFile {
357                id: FileId(2),
358                path: PathBuf::from("/project/tests/app.test.ts"),
359                size_bytes: 50,
360            },
361            DiscoveredFile {
362                id: FileId(3),
363                path: PathBuf::from("/project/tests/setup.ts"),
364                size_bytes: 50,
365            },
366            DiscoveredFile {
367                id: FileId(4),
368                path: PathBuf::from("/project/src/covered.ts"),
369                size_bytes: 50,
370            },
371        ];
372
373        let all_entry_points = vec![
374            EntryPoint {
375                path: PathBuf::from("/project/src/main.ts"),
376                source: EntryPointSource::PackageJsonMain,
377            },
378            EntryPoint {
379                path: PathBuf::from("/project/tests/app.test.ts"),
380                source: EntryPointSource::TestFile,
381            },
382            EntryPoint {
383                path: PathBuf::from("/project/tests/setup.ts"),
384                source: EntryPointSource::Plugin {
385                    name: "vitest".to_string(),
386                },
387            },
388        ];
389        let runtime_entry_points = vec![EntryPoint {
390            path: PathBuf::from("/project/src/main.ts"),
391            source: EntryPointSource::PackageJsonMain,
392        }];
393        let test_entry_points = vec![EntryPoint {
394            path: PathBuf::from("/project/tests/app.test.ts"),
395            source: EntryPointSource::TestFile,
396        }];
397
398        let resolved_modules = vec![
399            ResolvedModule {
400                file_id: FileId(0),
401                path: PathBuf::from("/project/src/main.ts"),
402                exports: vec![],
403                re_exports: vec![],
404                resolved_imports: vec![ResolvedImport {
405                    info: ImportInfo {
406                        source: "./runtime-only".to_string(),
407                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
408                        local_name: "runtimeOnly".to_string(),
409                        is_type_only: false,
410                        span: oxc_span::Span::new(0, 10),
411                        source_span: oxc_span::Span::default(),
412                    },
413                    target: ResolveResult::InternalModule(FileId(1)),
414                }],
415                resolved_dynamic_imports: vec![],
416                resolved_dynamic_patterns: vec![],
417                member_accesses: vec![],
418                whole_object_uses: vec![],
419                has_cjs_exports: false,
420                unused_import_bindings: FxHashSet::default(),
421            },
422            ResolvedModule {
423                file_id: FileId(1),
424                path: PathBuf::from("/project/src/runtime-only.ts"),
425                exports: vec![fallow_types::extract::ExportInfo {
426                    name: ExportName::Named("runtimeOnly".to_string()),
427                    local_name: Some("runtimeOnly".to_string()),
428                    is_type_only: false,
429                    is_public: false,
430                    span: oxc_span::Span::new(0, 20),
431                    members: vec![],
432                }],
433                re_exports: vec![],
434                resolved_imports: vec![],
435                resolved_dynamic_imports: vec![],
436                resolved_dynamic_patterns: vec![],
437                member_accesses: vec![],
438                whole_object_uses: vec![],
439                has_cjs_exports: false,
440                unused_import_bindings: FxHashSet::default(),
441            },
442            ResolvedModule {
443                file_id: FileId(2),
444                path: PathBuf::from("/project/tests/app.test.ts"),
445                exports: vec![],
446                re_exports: vec![],
447                resolved_imports: vec![ResolvedImport {
448                    info: ImportInfo {
449                        source: "../src/covered".to_string(),
450                        imported_name: ImportedName::Named("covered".to_string()),
451                        local_name: "covered".to_string(),
452                        is_type_only: false,
453                        span: oxc_span::Span::new(0, 10),
454                        source_span: oxc_span::Span::default(),
455                    },
456                    target: ResolveResult::InternalModule(FileId(4)),
457                }],
458                resolved_dynamic_imports: vec![],
459                resolved_dynamic_patterns: vec![],
460                member_accesses: vec![],
461                whole_object_uses: vec![],
462                has_cjs_exports: false,
463                unused_import_bindings: FxHashSet::default(),
464            },
465            ResolvedModule {
466                file_id: FileId(3),
467                path: PathBuf::from("/project/tests/setup.ts"),
468                exports: vec![],
469                re_exports: vec![],
470                resolved_imports: vec![ResolvedImport {
471                    info: ImportInfo {
472                        source: "../src/runtime-only".to_string(),
473                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
474                        local_name: "runtimeOnly".to_string(),
475                        is_type_only: false,
476                        span: oxc_span::Span::new(0, 10),
477                        source_span: oxc_span::Span::default(),
478                    },
479                    target: ResolveResult::InternalModule(FileId(1)),
480                }],
481                resolved_dynamic_imports: vec![],
482                resolved_dynamic_patterns: vec![],
483                member_accesses: vec![],
484                whole_object_uses: vec![],
485                has_cjs_exports: false,
486                unused_import_bindings: FxHashSet::default(),
487            },
488            ResolvedModule {
489                file_id: FileId(4),
490                path: PathBuf::from("/project/src/covered.ts"),
491                exports: vec![fallow_types::extract::ExportInfo {
492                    name: ExportName::Named("covered".to_string()),
493                    local_name: Some("covered".to_string()),
494                    is_type_only: false,
495                    is_public: false,
496                    span: oxc_span::Span::new(0, 20),
497                    members: vec![],
498                }],
499                re_exports: vec![],
500                resolved_imports: vec![],
501                resolved_dynamic_imports: vec![],
502                resolved_dynamic_patterns: vec![],
503                member_accesses: vec![],
504                whole_object_uses: vec![],
505                has_cjs_exports: false,
506                unused_import_bindings: FxHashSet::default(),
507            },
508        ];
509
510        let graph = ModuleGraph::build_with_reachability_roots(
511            &resolved_modules,
512            &all_entry_points,
513            &runtime_entry_points,
514            &test_entry_points,
515            &files,
516        );
517
518        assert!(graph.modules[1].is_reachable());
519        assert!(graph.modules[1].is_runtime_reachable());
520        assert!(
521            !graph.modules[1].is_test_reachable(),
522            "support roots should not make runtime-only modules test reachable"
523        );
524
525        assert!(graph.modules[4].is_reachable());
526        assert!(graph.modules[4].is_test_reachable());
527        assert!(
528            !graph.modules[4].is_runtime_reachable(),
529            "test-only reachability should stay separate from runtime roots"
530        );
531    }
532
533    #[test]
534    fn graph_export_has_reference() {
535        let graph = build_simple_graph();
536        let utils = &graph.modules[1];
537        let foo_export = utils
538            .exports
539            .iter()
540            .find(|e| e.name.to_string() == "foo")
541            .unwrap();
542        assert!(
543            !foo_export.references.is_empty(),
544            "foo should have references"
545        );
546    }
547
548    #[test]
549    fn graph_unused_export_no_reference() {
550        let graph = build_simple_graph();
551        let utils = &graph.modules[1];
552        let bar_export = utils
553            .exports
554            .iter()
555            .find(|e| e.name.to_string() == "bar")
556            .unwrap();
557        assert!(
558            bar_export.references.is_empty(),
559            "bar should have no references"
560        );
561    }
562
563    #[test]
564    fn graph_no_namespace_import() {
565        let graph = build_simple_graph();
566        assert!(!graph.has_namespace_import(FileId(0)));
567        assert!(!graph.has_namespace_import(FileId(1)));
568    }
569
570    #[test]
571    fn graph_has_namespace_import() {
572        let files = vec![
573            DiscoveredFile {
574                id: FileId(0),
575                path: PathBuf::from("/project/entry.ts"),
576                size_bytes: 100,
577            },
578            DiscoveredFile {
579                id: FileId(1),
580                path: PathBuf::from("/project/utils.ts"),
581                size_bytes: 50,
582            },
583        ];
584
585        let entry_points = vec![EntryPoint {
586            path: PathBuf::from("/project/entry.ts"),
587            source: EntryPointSource::PackageJsonMain,
588        }];
589
590        let resolved_modules = vec![
591            ResolvedModule {
592                file_id: FileId(0),
593                path: PathBuf::from("/project/entry.ts"),
594                exports: vec![],
595                re_exports: vec![],
596                resolved_imports: vec![ResolvedImport {
597                    info: ImportInfo {
598                        source: "./utils".to_string(),
599                        imported_name: ImportedName::Namespace,
600                        local_name: "utils".to_string(),
601                        is_type_only: false,
602                        span: oxc_span::Span::new(0, 10),
603                        source_span: oxc_span::Span::default(),
604                    },
605                    target: ResolveResult::InternalModule(FileId(1)),
606                }],
607                resolved_dynamic_imports: vec![],
608                resolved_dynamic_patterns: vec![],
609                member_accesses: vec![],
610                whole_object_uses: vec![],
611                has_cjs_exports: false,
612                unused_import_bindings: FxHashSet::default(),
613            },
614            ResolvedModule {
615                file_id: FileId(1),
616                path: PathBuf::from("/project/utils.ts"),
617                exports: vec![fallow_types::extract::ExportInfo {
618                    name: ExportName::Named("foo".to_string()),
619                    local_name: Some("foo".to_string()),
620                    is_type_only: false,
621                    is_public: false,
622                    span: oxc_span::Span::new(0, 20),
623                    members: vec![],
624                }],
625                re_exports: vec![],
626                resolved_imports: vec![],
627                resolved_dynamic_imports: vec![],
628                resolved_dynamic_patterns: vec![],
629                member_accesses: vec![],
630                whole_object_uses: vec![],
631                has_cjs_exports: false,
632                unused_import_bindings: FxHashSet::default(),
633            },
634        ];
635
636        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
637        assert!(
638            graph.has_namespace_import(FileId(1)),
639            "utils should have namespace import"
640        );
641    }
642
643    #[test]
644    fn graph_has_namespace_import_out_of_bounds() {
645        let graph = build_simple_graph();
646        assert!(!graph.has_namespace_import(FileId(999)));
647    }
648
649    #[test]
650    fn graph_unreachable_module() {
651        // Three files: entry imports utils, orphan is not imported
652        let files = vec![
653            DiscoveredFile {
654                id: FileId(0),
655                path: PathBuf::from("/project/entry.ts"),
656                size_bytes: 100,
657            },
658            DiscoveredFile {
659                id: FileId(1),
660                path: PathBuf::from("/project/utils.ts"),
661                size_bytes: 50,
662            },
663            DiscoveredFile {
664                id: FileId(2),
665                path: PathBuf::from("/project/orphan.ts"),
666                size_bytes: 30,
667            },
668        ];
669
670        let entry_points = vec![EntryPoint {
671            path: PathBuf::from("/project/entry.ts"),
672            source: EntryPointSource::PackageJsonMain,
673        }];
674
675        let resolved_modules = vec![
676            ResolvedModule {
677                file_id: FileId(0),
678                path: PathBuf::from("/project/entry.ts"),
679                exports: vec![],
680                re_exports: vec![],
681                resolved_imports: vec![ResolvedImport {
682                    info: ImportInfo {
683                        source: "./utils".to_string(),
684                        imported_name: ImportedName::Named("foo".to_string()),
685                        local_name: "foo".to_string(),
686                        is_type_only: false,
687                        span: oxc_span::Span::new(0, 10),
688                        source_span: oxc_span::Span::default(),
689                    },
690                    target: ResolveResult::InternalModule(FileId(1)),
691                }],
692                resolved_dynamic_imports: vec![],
693                resolved_dynamic_patterns: vec![],
694                member_accesses: vec![],
695                whole_object_uses: vec![],
696                has_cjs_exports: false,
697                unused_import_bindings: FxHashSet::default(),
698            },
699            ResolvedModule {
700                file_id: FileId(1),
701                path: PathBuf::from("/project/utils.ts"),
702                exports: vec![fallow_types::extract::ExportInfo {
703                    name: ExportName::Named("foo".to_string()),
704                    local_name: Some("foo".to_string()),
705                    is_type_only: false,
706                    is_public: false,
707                    span: oxc_span::Span::new(0, 20),
708                    members: vec![],
709                }],
710                re_exports: vec![],
711                resolved_imports: vec![],
712                resolved_dynamic_imports: vec![],
713                resolved_dynamic_patterns: vec![],
714                member_accesses: vec![],
715                whole_object_uses: vec![],
716                has_cjs_exports: false,
717                unused_import_bindings: FxHashSet::default(),
718            },
719            ResolvedModule {
720                file_id: FileId(2),
721                path: PathBuf::from("/project/orphan.ts"),
722                exports: vec![fallow_types::extract::ExportInfo {
723                    name: ExportName::Named("orphan".to_string()),
724                    local_name: Some("orphan".to_string()),
725                    is_type_only: false,
726                    is_public: false,
727                    span: oxc_span::Span::new(0, 20),
728                    members: vec![],
729                }],
730                re_exports: vec![],
731                resolved_imports: vec![],
732                resolved_dynamic_imports: vec![],
733                resolved_dynamic_patterns: vec![],
734                member_accesses: vec![],
735                whole_object_uses: vec![],
736                has_cjs_exports: false,
737                unused_import_bindings: FxHashSet::default(),
738            },
739        ];
740
741        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
742
743        assert!(graph.modules[0].is_reachable(), "entry should be reachable");
744        assert!(graph.modules[1].is_reachable(), "utils should be reachable");
745        assert!(
746            !graph.modules[2].is_reachable(),
747            "orphan should NOT be reachable"
748        );
749    }
750
751    #[test]
752    fn graph_package_usage_tracked() {
753        let files = vec![DiscoveredFile {
754            id: FileId(0),
755            path: PathBuf::from("/project/entry.ts"),
756            size_bytes: 100,
757        }];
758
759        let entry_points = vec![EntryPoint {
760            path: PathBuf::from("/project/entry.ts"),
761            source: EntryPointSource::PackageJsonMain,
762        }];
763
764        let resolved_modules = vec![ResolvedModule {
765            file_id: FileId(0),
766            path: PathBuf::from("/project/entry.ts"),
767            exports: vec![],
768            re_exports: vec![],
769            resolved_imports: vec![
770                ResolvedImport {
771                    info: ImportInfo {
772                        source: "react".to_string(),
773                        imported_name: ImportedName::Default,
774                        local_name: "React".to_string(),
775                        is_type_only: false,
776                        span: oxc_span::Span::new(0, 10),
777                        source_span: oxc_span::Span::default(),
778                    },
779                    target: ResolveResult::NpmPackage("react".to_string()),
780                },
781                ResolvedImport {
782                    info: ImportInfo {
783                        source: "lodash".to_string(),
784                        imported_name: ImportedName::Named("merge".to_string()),
785                        local_name: "merge".to_string(),
786                        is_type_only: false,
787                        span: oxc_span::Span::new(15, 30),
788                        source_span: oxc_span::Span::default(),
789                    },
790                    target: ResolveResult::NpmPackage("lodash".to_string()),
791                },
792            ],
793            resolved_dynamic_imports: vec![],
794            resolved_dynamic_patterns: vec![],
795            member_accesses: vec![],
796            whole_object_uses: vec![],
797            has_cjs_exports: false,
798            unused_import_bindings: FxHashSet::default(),
799        }];
800
801        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
802        assert!(graph.package_usage.contains_key("react"));
803        assert!(graph.package_usage.contains_key("lodash"));
804        assert!(!graph.package_usage.contains_key("express"));
805    }
806
807    #[test]
808    fn graph_empty() {
809        let graph = ModuleGraph::build(&[], &[], &[]);
810        assert_eq!(graph.module_count(), 0);
811        assert_eq!(graph.edge_count(), 0);
812    }
813
814    #[test]
815    fn graph_cjs_exports_tracked() {
816        let files = vec![DiscoveredFile {
817            id: FileId(0),
818            path: PathBuf::from("/project/entry.ts"),
819            size_bytes: 100,
820        }];
821
822        let entry_points = vec![EntryPoint {
823            path: PathBuf::from("/project/entry.ts"),
824            source: EntryPointSource::PackageJsonMain,
825        }];
826
827        let resolved_modules = vec![ResolvedModule {
828            file_id: FileId(0),
829            path: PathBuf::from("/project/entry.ts"),
830            exports: vec![],
831            re_exports: vec![],
832            resolved_imports: vec![],
833            resolved_dynamic_imports: vec![],
834            resolved_dynamic_patterns: vec![],
835            member_accesses: vec![],
836            whole_object_uses: vec![],
837            has_cjs_exports: true,
838            unused_import_bindings: FxHashSet::default(),
839        }];
840
841        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
842        assert!(graph.modules[0].has_cjs_exports());
843    }
844
845    #[test]
846    fn graph_edges_for_returns_targets() {
847        let graph = build_simple_graph();
848        let targets = graph.edges_for(FileId(0));
849        assert_eq!(targets, vec![FileId(1)]);
850    }
851
852    #[test]
853    fn graph_edges_for_no_imports() {
854        let graph = build_simple_graph();
855        // utils.ts has no outgoing imports
856        let targets = graph.edges_for(FileId(1));
857        assert!(targets.is_empty());
858    }
859
860    #[test]
861    fn graph_edges_for_out_of_bounds() {
862        let graph = build_simple_graph();
863        let targets = graph.edges_for(FileId(999));
864        assert!(targets.is_empty());
865    }
866
867    #[test]
868    fn graph_find_import_span_start_found() {
869        let graph = build_simple_graph();
870        let span_start = graph.find_import_span_start(FileId(0), FileId(1));
871        assert!(span_start.is_some());
872        assert_eq!(span_start.unwrap(), 0);
873    }
874
875    #[test]
876    fn graph_find_import_span_start_wrong_target() {
877        let graph = build_simple_graph();
878        // No edge from entry.ts to itself
879        let span_start = graph.find_import_span_start(FileId(0), FileId(0));
880        assert!(span_start.is_none());
881    }
882
883    #[test]
884    fn graph_find_import_span_start_source_out_of_bounds() {
885        let graph = build_simple_graph();
886        let span_start = graph.find_import_span_start(FileId(999), FileId(1));
887        assert!(span_start.is_none());
888    }
889
890    #[test]
891    fn graph_find_import_span_start_no_edges() {
892        let graph = build_simple_graph();
893        // utils.ts has no outgoing edges
894        let span_start = graph.find_import_span_start(FileId(1), FileId(0));
895        assert!(span_start.is_none());
896    }
897
898    #[test]
899    fn graph_reverse_deps_populated() {
900        let graph = build_simple_graph();
901        // utils.ts (FileId(1)) should be imported by entry.ts (FileId(0))
902        assert!(graph.reverse_deps[1].contains(&FileId(0)));
903        // entry.ts (FileId(0)) should not be imported by anyone
904        assert!(graph.reverse_deps[0].is_empty());
905    }
906
907    #[test]
908    fn graph_type_only_package_usage_tracked() {
909        let files = vec![DiscoveredFile {
910            id: FileId(0),
911            path: PathBuf::from("/project/entry.ts"),
912            size_bytes: 100,
913        }];
914        let entry_points = vec![EntryPoint {
915            path: PathBuf::from("/project/entry.ts"),
916            source: EntryPointSource::PackageJsonMain,
917        }];
918        let resolved_modules = vec![ResolvedModule {
919            file_id: FileId(0),
920            path: PathBuf::from("/project/entry.ts"),
921            exports: vec![],
922            re_exports: vec![],
923            resolved_imports: vec![
924                ResolvedImport {
925                    info: ImportInfo {
926                        source: "react".to_string(),
927                        imported_name: ImportedName::Named("FC".to_string()),
928                        local_name: "FC".to_string(),
929                        is_type_only: true,
930                        span: oxc_span::Span::new(0, 10),
931                        source_span: oxc_span::Span::default(),
932                    },
933                    target: ResolveResult::NpmPackage("react".to_string()),
934                },
935                ResolvedImport {
936                    info: ImportInfo {
937                        source: "react".to_string(),
938                        imported_name: ImportedName::Named("useState".to_string()),
939                        local_name: "useState".to_string(),
940                        is_type_only: false,
941                        span: oxc_span::Span::new(15, 30),
942                        source_span: oxc_span::Span::default(),
943                    },
944                    target: ResolveResult::NpmPackage("react".to_string()),
945                },
946            ],
947            resolved_dynamic_imports: vec![],
948            resolved_dynamic_patterns: vec![],
949            member_accesses: vec![],
950            whole_object_uses: vec![],
951            has_cjs_exports: false,
952            unused_import_bindings: FxHashSet::default(),
953        }];
954
955        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
956        assert!(graph.package_usage.contains_key("react"));
957        assert!(graph.type_only_package_usage.contains_key("react"));
958    }
959
960    #[test]
961    fn graph_default_import_reference() {
962        let files = vec![
963            DiscoveredFile {
964                id: FileId(0),
965                path: PathBuf::from("/project/entry.ts"),
966                size_bytes: 100,
967            },
968            DiscoveredFile {
969                id: FileId(1),
970                path: PathBuf::from("/project/utils.ts"),
971                size_bytes: 50,
972            },
973        ];
974        let entry_points = vec![EntryPoint {
975            path: PathBuf::from("/project/entry.ts"),
976            source: EntryPointSource::PackageJsonMain,
977        }];
978        let resolved_modules = vec![
979            ResolvedModule {
980                file_id: FileId(0),
981                path: PathBuf::from("/project/entry.ts"),
982                exports: vec![],
983                re_exports: vec![],
984                resolved_imports: vec![ResolvedImport {
985                    info: ImportInfo {
986                        source: "./utils".to_string(),
987                        imported_name: ImportedName::Default,
988                        local_name: "Utils".to_string(),
989                        is_type_only: false,
990                        span: oxc_span::Span::new(0, 10),
991                        source_span: oxc_span::Span::default(),
992                    },
993                    target: ResolveResult::InternalModule(FileId(1)),
994                }],
995                resolved_dynamic_imports: vec![],
996                resolved_dynamic_patterns: vec![],
997                member_accesses: vec![],
998                whole_object_uses: vec![],
999                has_cjs_exports: false,
1000                unused_import_bindings: FxHashSet::default(),
1001            },
1002            ResolvedModule {
1003                file_id: FileId(1),
1004                path: PathBuf::from("/project/utils.ts"),
1005                exports: vec![fallow_types::extract::ExportInfo {
1006                    name: ExportName::Default,
1007                    local_name: None,
1008                    is_type_only: false,
1009                    is_public: false,
1010                    span: oxc_span::Span::new(0, 20),
1011                    members: vec![],
1012                }],
1013                re_exports: vec![],
1014                resolved_imports: vec![],
1015                resolved_dynamic_imports: vec![],
1016                resolved_dynamic_patterns: vec![],
1017                member_accesses: vec![],
1018                whole_object_uses: vec![],
1019                has_cjs_exports: false,
1020                unused_import_bindings: FxHashSet::default(),
1021            },
1022        ];
1023
1024        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1025        let utils = &graph.modules[1];
1026        let default_export = utils
1027            .exports
1028            .iter()
1029            .find(|e| matches!(e.name, ExportName::Default))
1030            .unwrap();
1031        assert!(!default_export.references.is_empty());
1032        assert_eq!(
1033            default_export.references[0].kind,
1034            ReferenceKind::DefaultImport
1035        );
1036    }
1037
1038    #[test]
1039    fn graph_side_effect_import_no_export_reference() {
1040        let files = vec![
1041            DiscoveredFile {
1042                id: FileId(0),
1043                path: PathBuf::from("/project/entry.ts"),
1044                size_bytes: 100,
1045            },
1046            DiscoveredFile {
1047                id: FileId(1),
1048                path: PathBuf::from("/project/styles.ts"),
1049                size_bytes: 50,
1050            },
1051        ];
1052        let entry_points = vec![EntryPoint {
1053            path: PathBuf::from("/project/entry.ts"),
1054            source: EntryPointSource::PackageJsonMain,
1055        }];
1056        let resolved_modules = vec![
1057            ResolvedModule {
1058                file_id: FileId(0),
1059                path: PathBuf::from("/project/entry.ts"),
1060                exports: vec![],
1061                re_exports: vec![],
1062                resolved_imports: vec![ResolvedImport {
1063                    info: ImportInfo {
1064                        source: "./styles".to_string(),
1065                        imported_name: ImportedName::SideEffect,
1066                        local_name: String::new(),
1067                        is_type_only: false,
1068                        span: oxc_span::Span::new(0, 10),
1069                        source_span: oxc_span::Span::default(),
1070                    },
1071                    target: ResolveResult::InternalModule(FileId(1)),
1072                }],
1073                resolved_dynamic_imports: vec![],
1074                resolved_dynamic_patterns: vec![],
1075                member_accesses: vec![],
1076                whole_object_uses: vec![],
1077                has_cjs_exports: false,
1078                unused_import_bindings: FxHashSet::default(),
1079            },
1080            ResolvedModule {
1081                file_id: FileId(1),
1082                path: PathBuf::from("/project/styles.ts"),
1083                exports: vec![fallow_types::extract::ExportInfo {
1084                    name: ExportName::Named("primaryColor".to_string()),
1085                    local_name: Some("primaryColor".to_string()),
1086                    is_type_only: false,
1087                    is_public: false,
1088                    span: oxc_span::Span::new(0, 20),
1089                    members: vec![],
1090                }],
1091                re_exports: vec![],
1092                resolved_imports: vec![],
1093                resolved_dynamic_imports: vec![],
1094                resolved_dynamic_patterns: vec![],
1095                member_accesses: vec![],
1096                whole_object_uses: vec![],
1097                has_cjs_exports: false,
1098                unused_import_bindings: FxHashSet::default(),
1099            },
1100        ];
1101
1102        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1103        // Side-effect import should create an edge but not reference specific exports
1104        assert_eq!(graph.edge_count(), 1);
1105        let styles = &graph.modules[1];
1106        let export = &styles.exports[0];
1107        // Side-effect import doesn't match any named export
1108        assert!(
1109            export.references.is_empty(),
1110            "side-effect import should not reference named exports"
1111        );
1112    }
1113
1114    #[test]
1115    fn graph_multiple_entry_points() {
1116        let files = vec![
1117            DiscoveredFile {
1118                id: FileId(0),
1119                path: PathBuf::from("/project/main.ts"),
1120                size_bytes: 100,
1121            },
1122            DiscoveredFile {
1123                id: FileId(1),
1124                path: PathBuf::from("/project/worker.ts"),
1125                size_bytes: 100,
1126            },
1127            DiscoveredFile {
1128                id: FileId(2),
1129                path: PathBuf::from("/project/shared.ts"),
1130                size_bytes: 50,
1131            },
1132        ];
1133        let entry_points = vec![
1134            EntryPoint {
1135                path: PathBuf::from("/project/main.ts"),
1136                source: EntryPointSource::PackageJsonMain,
1137            },
1138            EntryPoint {
1139                path: PathBuf::from("/project/worker.ts"),
1140                source: EntryPointSource::PackageJsonMain,
1141            },
1142        ];
1143        let resolved_modules = vec![
1144            ResolvedModule {
1145                file_id: FileId(0),
1146                path: PathBuf::from("/project/main.ts"),
1147                exports: vec![],
1148                re_exports: vec![],
1149                resolved_imports: vec![ResolvedImport {
1150                    info: ImportInfo {
1151                        source: "./shared".to_string(),
1152                        imported_name: ImportedName::Named("helper".to_string()),
1153                        local_name: "helper".to_string(),
1154                        is_type_only: false,
1155                        span: oxc_span::Span::new(0, 10),
1156                        source_span: oxc_span::Span::default(),
1157                    },
1158                    target: ResolveResult::InternalModule(FileId(2)),
1159                }],
1160                resolved_dynamic_imports: vec![],
1161                resolved_dynamic_patterns: vec![],
1162                member_accesses: vec![],
1163                whole_object_uses: vec![],
1164                has_cjs_exports: false,
1165                unused_import_bindings: FxHashSet::default(),
1166            },
1167            ResolvedModule {
1168                file_id: FileId(1),
1169                path: PathBuf::from("/project/worker.ts"),
1170                exports: vec![],
1171                re_exports: vec![],
1172                resolved_imports: vec![],
1173                resolved_dynamic_imports: vec![],
1174                resolved_dynamic_patterns: vec![],
1175                member_accesses: vec![],
1176                whole_object_uses: vec![],
1177                has_cjs_exports: false,
1178                unused_import_bindings: FxHashSet::default(),
1179            },
1180            ResolvedModule {
1181                file_id: FileId(2),
1182                path: PathBuf::from("/project/shared.ts"),
1183                exports: vec![fallow_types::extract::ExportInfo {
1184                    name: ExportName::Named("helper".to_string()),
1185                    local_name: Some("helper".to_string()),
1186                    is_type_only: false,
1187                    is_public: false,
1188                    span: oxc_span::Span::new(0, 20),
1189                    members: vec![],
1190                }],
1191                re_exports: vec![],
1192                resolved_imports: vec![],
1193                resolved_dynamic_imports: vec![],
1194                resolved_dynamic_patterns: vec![],
1195                member_accesses: vec![],
1196                whole_object_uses: vec![],
1197                has_cjs_exports: false,
1198                unused_import_bindings: FxHashSet::default(),
1199            },
1200        ];
1201
1202        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1203        assert!(graph.modules[0].is_entry_point());
1204        assert!(graph.modules[1].is_entry_point());
1205        assert!(!graph.modules[2].is_entry_point());
1206        // All should be reachable — shared is reached from main
1207        assert!(graph.modules[0].is_reachable());
1208        assert!(graph.modules[1].is_reachable());
1209        assert!(graph.modules[2].is_reachable());
1210    }
1211}
fallow_graph/graph/mod.rs

fallow_graph/graph/
mod.rs
