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

fallow_graph/graph/
mod.rs
