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, VisibilityTag};
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                resolved_imports: vec![ResolvedImport {
259                    info: ImportInfo {
260                        source: "./utils".to_string(),
261                        imported_name: ImportedName::Named("foo".to_string()),
262                        local_name: "foo".to_string(),
263                        is_type_only: false,
264                        from_style: 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                ..Default::default()
271            },
272            ResolvedModule {
273                file_id: FileId(1),
274                path: PathBuf::from("/project/src/utils.ts"),
275                exports: vec![
276                    fallow_types::extract::ExportInfo {
277                        name: ExportName::Named("foo".to_string()),
278                        local_name: Some("foo".to_string()),
279                        is_type_only: false,
280                        visibility: VisibilityTag::None,
281                        span: oxc_span::Span::new(0, 20),
282                        members: vec![],
283                        is_side_effect_used: false,
284                        super_class: None,
285                    },
286                    fallow_types::extract::ExportInfo {
287                        name: ExportName::Named("bar".to_string()),
288                        local_name: Some("bar".to_string()),
289                        is_type_only: false,
290                        visibility: VisibilityTag::None,
291                        span: oxc_span::Span::new(25, 45),
292                        members: vec![],
293                        is_side_effect_used: false,
294                        super_class: None,
295                    },
296                ],
297                ..Default::default()
298            },
299        ];
300
301        ModuleGraph::build(&resolved_modules, &entry_points, &files)
302    }
303
304    #[test]
305    fn graph_module_count() {
306        let graph = build_simple_graph();
307        assert_eq!(graph.module_count(), 2);
308    }
309
310    #[test]
311    fn graph_edge_count() {
312        let graph = build_simple_graph();
313        assert_eq!(graph.edge_count(), 1);
314    }
315
316    #[test]
317    fn graph_entry_point_is_reachable() {
318        let graph = build_simple_graph();
319        assert!(graph.modules[0].is_entry_point());
320        assert!(graph.modules[0].is_reachable());
321    }
322
323    #[test]
324    fn graph_imported_module_is_reachable() {
325        let graph = build_simple_graph();
326        assert!(!graph.modules[1].is_entry_point());
327        assert!(graph.modules[1].is_reachable());
328    }
329
330    #[test]
331    #[expect(
332        clippy::too_many_lines,
333        reason = "this test fixture exercises four reachability roles end-to-end; splitting it \
334                  would obscure the cross-role assertions"
335    )]
336    fn graph_distinguishes_runtime_test_and_support_reachability() {
337        let files = vec![
338            DiscoveredFile {
339                id: FileId(0),
340                path: PathBuf::from("/project/src/main.ts"),
341                size_bytes: 100,
342            },
343            DiscoveredFile {
344                id: FileId(1),
345                path: PathBuf::from("/project/src/runtime-only.ts"),
346                size_bytes: 50,
347            },
348            DiscoveredFile {
349                id: FileId(2),
350                path: PathBuf::from("/project/tests/app.test.ts"),
351                size_bytes: 50,
352            },
353            DiscoveredFile {
354                id: FileId(3),
355                path: PathBuf::from("/project/tests/setup.ts"),
356                size_bytes: 50,
357            },
358            DiscoveredFile {
359                id: FileId(4),
360                path: PathBuf::from("/project/src/covered.ts"),
361                size_bytes: 50,
362            },
363        ];
364
365        let all_entry_points = vec![
366            EntryPoint {
367                path: PathBuf::from("/project/src/main.ts"),
368                source: EntryPointSource::PackageJsonMain,
369            },
370            EntryPoint {
371                path: PathBuf::from("/project/tests/app.test.ts"),
372                source: EntryPointSource::TestFile,
373            },
374            EntryPoint {
375                path: PathBuf::from("/project/tests/setup.ts"),
376                source: EntryPointSource::Plugin {
377                    name: "vitest".to_string(),
378                },
379            },
380        ];
381        let runtime_entry_points = vec![EntryPoint {
382            path: PathBuf::from("/project/src/main.ts"),
383            source: EntryPointSource::PackageJsonMain,
384        }];
385        let test_entry_points = vec![EntryPoint {
386            path: PathBuf::from("/project/tests/app.test.ts"),
387            source: EntryPointSource::TestFile,
388        }];
389
390        let resolved_modules = vec![
391            ResolvedModule {
392                file_id: FileId(0),
393                path: PathBuf::from("/project/src/main.ts"),
394                resolved_imports: vec![ResolvedImport {
395                    info: ImportInfo {
396                        source: "./runtime-only".to_string(),
397                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
398                        local_name: "runtimeOnly".to_string(),
399                        is_type_only: false,
400                        from_style: false,
401                        span: oxc_span::Span::new(0, 10),
402                        source_span: oxc_span::Span::default(),
403                    },
404                    target: ResolveResult::InternalModule(FileId(1)),
405                }],
406                ..Default::default()
407            },
408            ResolvedModule {
409                file_id: FileId(1),
410                path: PathBuf::from("/project/src/runtime-only.ts"),
411                exports: vec![fallow_types::extract::ExportInfo {
412                    name: ExportName::Named("runtimeOnly".to_string()),
413                    local_name: Some("runtimeOnly".to_string()),
414                    is_type_only: false,
415                    visibility: VisibilityTag::None,
416                    span: oxc_span::Span::new(0, 20),
417                    members: vec![],
418                    is_side_effect_used: false,
419                    super_class: None,
420                }],
421                ..Default::default()
422            },
423            ResolvedModule {
424                file_id: FileId(2),
425                path: PathBuf::from("/project/tests/app.test.ts"),
426                resolved_imports: vec![ResolvedImport {
427                    info: ImportInfo {
428                        source: "../src/covered".to_string(),
429                        imported_name: ImportedName::Named("covered".to_string()),
430                        local_name: "covered".to_string(),
431                        is_type_only: false,
432                        from_style: false,
433                        span: oxc_span::Span::new(0, 10),
434                        source_span: oxc_span::Span::default(),
435                    },
436                    target: ResolveResult::InternalModule(FileId(4)),
437                }],
438                ..Default::default()
439            },
440            ResolvedModule {
441                file_id: FileId(3),
442                path: PathBuf::from("/project/tests/setup.ts"),
443                resolved_imports: vec![ResolvedImport {
444                    info: ImportInfo {
445                        source: "../src/runtime-only".to_string(),
446                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
447                        local_name: "runtimeOnly".to_string(),
448                        is_type_only: false,
449                        from_style: false,
450                        span: oxc_span::Span::new(0, 10),
451                        source_span: oxc_span::Span::default(),
452                    },
453                    target: ResolveResult::InternalModule(FileId(1)),
454                }],
455                ..Default::default()
456            },
457            ResolvedModule {
458                file_id: FileId(4),
459                path: PathBuf::from("/project/src/covered.ts"),
460                exports: vec![fallow_types::extract::ExportInfo {
461                    name: ExportName::Named("covered".to_string()),
462                    local_name: Some("covered".to_string()),
463                    is_type_only: false,
464                    visibility: VisibilityTag::None,
465                    span: oxc_span::Span::new(0, 20),
466                    members: vec![],
467                    is_side_effect_used: false,
468                    super_class: None,
469                }],
470                ..Default::default()
471            },
472        ];
473
474        let graph = ModuleGraph::build_with_reachability_roots(
475            &resolved_modules,
476            &all_entry_points,
477            &runtime_entry_points,
478            &test_entry_points,
479            &files,
480        );
481
482        assert!(graph.modules[1].is_reachable());
483        assert!(graph.modules[1].is_runtime_reachable());
484        assert!(
485            !graph.modules[1].is_test_reachable(),
486            "support roots should not make runtime-only modules test reachable"
487        );
488
489        assert!(graph.modules[4].is_reachable());
490        assert!(graph.modules[4].is_test_reachable());
491        assert!(
492            !graph.modules[4].is_runtime_reachable(),
493            "test-only reachability should stay separate from runtime roots"
494        );
495    }
496
497    #[test]
498    fn graph_export_has_reference() {
499        let graph = build_simple_graph();
500        let utils = &graph.modules[1];
501        let foo_export = utils
502            .exports
503            .iter()
504            .find(|e| e.name.to_string() == "foo")
505            .unwrap();
506        assert!(
507            !foo_export.references.is_empty(),
508            "foo should have references"
509        );
510    }
511
512    #[test]
513    fn graph_unused_export_no_reference() {
514        let graph = build_simple_graph();
515        let utils = &graph.modules[1];
516        let bar_export = utils
517            .exports
518            .iter()
519            .find(|e| e.name.to_string() == "bar")
520            .unwrap();
521        assert!(
522            bar_export.references.is_empty(),
523            "bar should have no references"
524        );
525    }
526
527    #[test]
528    fn graph_no_namespace_import() {
529        let graph = build_simple_graph();
530        assert!(!graph.has_namespace_import(FileId(0)));
531        assert!(!graph.has_namespace_import(FileId(1)));
532    }
533
534    #[test]
535    fn graph_has_namespace_import() {
536        let files = vec![
537            DiscoveredFile {
538                id: FileId(0),
539                path: PathBuf::from("/project/entry.ts"),
540                size_bytes: 100,
541            },
542            DiscoveredFile {
543                id: FileId(1),
544                path: PathBuf::from("/project/utils.ts"),
545                size_bytes: 50,
546            },
547        ];
548
549        let entry_points = vec![EntryPoint {
550            path: PathBuf::from("/project/entry.ts"),
551            source: EntryPointSource::PackageJsonMain,
552        }];
553
554        let resolved_modules = vec![
555            ResolvedModule {
556                file_id: FileId(0),
557                path: PathBuf::from("/project/entry.ts"),
558                resolved_imports: vec![ResolvedImport {
559                    info: ImportInfo {
560                        source: "./utils".to_string(),
561                        imported_name: ImportedName::Namespace,
562                        local_name: "utils".to_string(),
563                        is_type_only: false,
564                        from_style: false,
565                        span: oxc_span::Span::new(0, 10),
566                        source_span: oxc_span::Span::default(),
567                    },
568                    target: ResolveResult::InternalModule(FileId(1)),
569                }],
570                ..Default::default()
571            },
572            ResolvedModule {
573                file_id: FileId(1),
574                path: PathBuf::from("/project/utils.ts"),
575                exports: vec![fallow_types::extract::ExportInfo {
576                    name: ExportName::Named("foo".to_string()),
577                    local_name: Some("foo".to_string()),
578                    is_type_only: false,
579                    visibility: VisibilityTag::None,
580                    span: oxc_span::Span::new(0, 20),
581                    members: vec![],
582                    is_side_effect_used: false,
583                    super_class: None,
584                }],
585                ..Default::default()
586            },
587        ];
588
589        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
590        assert!(
591            graph.has_namespace_import(FileId(1)),
592            "utils should have namespace import"
593        );
594    }
595
596    #[test]
597    fn graph_has_namespace_import_out_of_bounds() {
598        let graph = build_simple_graph();
599        assert!(!graph.has_namespace_import(FileId(999)));
600    }
601
602    #[test]
603    fn graph_unreachable_module() {
604        // Three files: entry imports utils, orphan is not imported
605        let files = vec![
606            DiscoveredFile {
607                id: FileId(0),
608                path: PathBuf::from("/project/entry.ts"),
609                size_bytes: 100,
610            },
611            DiscoveredFile {
612                id: FileId(1),
613                path: PathBuf::from("/project/utils.ts"),
614                size_bytes: 50,
615            },
616            DiscoveredFile {
617                id: FileId(2),
618                path: PathBuf::from("/project/orphan.ts"),
619                size_bytes: 30,
620            },
621        ];
622
623        let entry_points = vec![EntryPoint {
624            path: PathBuf::from("/project/entry.ts"),
625            source: EntryPointSource::PackageJsonMain,
626        }];
627
628        let resolved_modules = vec![
629            ResolvedModule {
630                file_id: FileId(0),
631                path: PathBuf::from("/project/entry.ts"),
632                resolved_imports: vec![ResolvedImport {
633                    info: ImportInfo {
634                        source: "./utils".to_string(),
635                        imported_name: ImportedName::Named("foo".to_string()),
636                        local_name: "foo".to_string(),
637                        is_type_only: false,
638                        from_style: false,
639                        span: oxc_span::Span::new(0, 10),
640                        source_span: oxc_span::Span::default(),
641                    },
642                    target: ResolveResult::InternalModule(FileId(1)),
643                }],
644                ..Default::default()
645            },
646            ResolvedModule {
647                file_id: FileId(1),
648                path: PathBuf::from("/project/utils.ts"),
649                exports: vec![fallow_types::extract::ExportInfo {
650                    name: ExportName::Named("foo".to_string()),
651                    local_name: Some("foo".to_string()),
652                    is_type_only: false,
653                    visibility: VisibilityTag::None,
654                    span: oxc_span::Span::new(0, 20),
655                    members: vec![],
656                    is_side_effect_used: false,
657                    super_class: None,
658                }],
659                ..Default::default()
660            },
661            ResolvedModule {
662                file_id: FileId(2),
663                path: PathBuf::from("/project/orphan.ts"),
664                exports: vec![fallow_types::extract::ExportInfo {
665                    name: ExportName::Named("orphan".to_string()),
666                    local_name: Some("orphan".to_string()),
667                    is_type_only: false,
668                    visibility: VisibilityTag::None,
669                    span: oxc_span::Span::new(0, 20),
670                    members: vec![],
671                    is_side_effect_used: false,
672                    super_class: None,
673                }],
674                ..Default::default()
675            },
676        ];
677
678        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
679
680        assert!(graph.modules[0].is_reachable(), "entry should be reachable");
681        assert!(graph.modules[1].is_reachable(), "utils should be reachable");
682        assert!(
683            !graph.modules[2].is_reachable(),
684            "orphan should NOT be reachable"
685        );
686    }
687
688    #[test]
689    fn graph_package_usage_tracked() {
690        let files = vec![DiscoveredFile {
691            id: FileId(0),
692            path: PathBuf::from("/project/entry.ts"),
693            size_bytes: 100,
694        }];
695
696        let entry_points = vec![EntryPoint {
697            path: PathBuf::from("/project/entry.ts"),
698            source: EntryPointSource::PackageJsonMain,
699        }];
700
701        let resolved_modules = vec![ResolvedModule {
702            file_id: FileId(0),
703            path: PathBuf::from("/project/entry.ts"),
704            exports: vec![],
705            re_exports: vec![],
706            resolved_imports: vec![
707                ResolvedImport {
708                    info: ImportInfo {
709                        source: "react".to_string(),
710                        imported_name: ImportedName::Default,
711                        local_name: "React".to_string(),
712                        is_type_only: false,
713                        from_style: false,
714                        span: oxc_span::Span::new(0, 10),
715                        source_span: oxc_span::Span::default(),
716                    },
717                    target: ResolveResult::NpmPackage("react".to_string()),
718                },
719                ResolvedImport {
720                    info: ImportInfo {
721                        source: "lodash".to_string(),
722                        imported_name: ImportedName::Named("merge".to_string()),
723                        local_name: "merge".to_string(),
724                        is_type_only: false,
725                        from_style: false,
726                        span: oxc_span::Span::new(15, 30),
727                        source_span: oxc_span::Span::default(),
728                    },
729                    target: ResolveResult::NpmPackage("lodash".to_string()),
730                },
731            ],
732            ..Default::default()
733        }];
734
735        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
736        assert!(graph.package_usage.contains_key("react"));
737        assert!(graph.package_usage.contains_key("lodash"));
738        assert!(!graph.package_usage.contains_key("express"));
739    }
740
741    #[test]
742    fn graph_empty() {
743        let graph = ModuleGraph::build(&[], &[], &[]);
744        assert_eq!(graph.module_count(), 0);
745        assert_eq!(graph.edge_count(), 0);
746    }
747
748    #[test]
749    fn graph_cjs_exports_tracked() {
750        let files = vec![DiscoveredFile {
751            id: FileId(0),
752            path: PathBuf::from("/project/entry.ts"),
753            size_bytes: 100,
754        }];
755
756        let entry_points = vec![EntryPoint {
757            path: PathBuf::from("/project/entry.ts"),
758            source: EntryPointSource::PackageJsonMain,
759        }];
760
761        let resolved_modules = vec![ResolvedModule {
762            file_id: FileId(0),
763            path: PathBuf::from("/project/entry.ts"),
764            has_cjs_exports: true,
765            ..Default::default()
766        }];
767
768        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
769        assert!(graph.modules[0].has_cjs_exports());
770    }
771
772    #[test]
773    fn graph_edges_for_returns_targets() {
774        let graph = build_simple_graph();
775        let targets = graph.edges_for(FileId(0));
776        assert_eq!(targets, vec![FileId(1)]);
777    }
778
779    #[test]
780    fn graph_edges_for_no_imports() {
781        let graph = build_simple_graph();
782        // utils.ts has no outgoing imports
783        let targets = graph.edges_for(FileId(1));
784        assert!(targets.is_empty());
785    }
786
787    #[test]
788    fn graph_edges_for_out_of_bounds() {
789        let graph = build_simple_graph();
790        let targets = graph.edges_for(FileId(999));
791        assert!(targets.is_empty());
792    }
793
794    #[test]
795    fn graph_find_import_span_start_found() {
796        let graph = build_simple_graph();
797        let span_start = graph.find_import_span_start(FileId(0), FileId(1));
798        assert!(span_start.is_some());
799        assert_eq!(span_start.unwrap(), 0);
800    }
801
802    #[test]
803    fn graph_find_import_span_start_wrong_target() {
804        let graph = build_simple_graph();
805        // No edge from entry.ts to itself
806        let span_start = graph.find_import_span_start(FileId(0), FileId(0));
807        assert!(span_start.is_none());
808    }
809
810    #[test]
811    fn graph_find_import_span_start_source_out_of_bounds() {
812        let graph = build_simple_graph();
813        let span_start = graph.find_import_span_start(FileId(999), FileId(1));
814        assert!(span_start.is_none());
815    }
816
817    #[test]
818    fn graph_find_import_span_start_no_edges() {
819        let graph = build_simple_graph();
820        // utils.ts has no outgoing edges
821        let span_start = graph.find_import_span_start(FileId(1), FileId(0));
822        assert!(span_start.is_none());
823    }
824
825    #[test]
826    fn graph_reverse_deps_populated() {
827        let graph = build_simple_graph();
828        // utils.ts (FileId(1)) should be imported by entry.ts (FileId(0))
829        assert!(graph.reverse_deps[1].contains(&FileId(0)));
830        // entry.ts (FileId(0)) should not be imported by anyone
831        assert!(graph.reverse_deps[0].is_empty());
832    }
833
834    #[test]
835    fn graph_type_only_package_usage_tracked() {
836        let files = vec![DiscoveredFile {
837            id: FileId(0),
838            path: PathBuf::from("/project/entry.ts"),
839            size_bytes: 100,
840        }];
841        let entry_points = vec![EntryPoint {
842            path: PathBuf::from("/project/entry.ts"),
843            source: EntryPointSource::PackageJsonMain,
844        }];
845        let resolved_modules = vec![ResolvedModule {
846            file_id: FileId(0),
847            path: PathBuf::from("/project/entry.ts"),
848            resolved_imports: vec![
849                ResolvedImport {
850                    info: ImportInfo {
851                        source: "react".to_string(),
852                        imported_name: ImportedName::Named("FC".to_string()),
853                        local_name: "FC".to_string(),
854                        is_type_only: true,
855                        from_style: false,
856                        span: oxc_span::Span::new(0, 10),
857                        source_span: oxc_span::Span::default(),
858                    },
859                    target: ResolveResult::NpmPackage("react".to_string()),
860                },
861                ResolvedImport {
862                    info: ImportInfo {
863                        source: "react".to_string(),
864                        imported_name: ImportedName::Named("useState".to_string()),
865                        local_name: "useState".to_string(),
866                        is_type_only: false,
867                        from_style: false,
868                        span: oxc_span::Span::new(15, 30),
869                        source_span: oxc_span::Span::default(),
870                    },
871                    target: ResolveResult::NpmPackage("react".to_string()),
872                },
873            ],
874            ..Default::default()
875        }];
876
877        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
878        assert!(graph.package_usage.contains_key("react"));
879        assert!(graph.type_only_package_usage.contains_key("react"));
880    }
881
882    #[test]
883    fn graph_default_import_reference() {
884        let files = vec![
885            DiscoveredFile {
886                id: FileId(0),
887                path: PathBuf::from("/project/entry.ts"),
888                size_bytes: 100,
889            },
890            DiscoveredFile {
891                id: FileId(1),
892                path: PathBuf::from("/project/utils.ts"),
893                size_bytes: 50,
894            },
895        ];
896        let entry_points = vec![EntryPoint {
897            path: PathBuf::from("/project/entry.ts"),
898            source: EntryPointSource::PackageJsonMain,
899        }];
900        let resolved_modules = vec![
901            ResolvedModule {
902                file_id: FileId(0),
903                path: PathBuf::from("/project/entry.ts"),
904                resolved_imports: vec![ResolvedImport {
905                    info: ImportInfo {
906                        source: "./utils".to_string(),
907                        imported_name: ImportedName::Default,
908                        local_name: "Utils".to_string(),
909                        is_type_only: false,
910                        from_style: false,
911                        span: oxc_span::Span::new(0, 10),
912                        source_span: oxc_span::Span::default(),
913                    },
914                    target: ResolveResult::InternalModule(FileId(1)),
915                }],
916                ..Default::default()
917            },
918            ResolvedModule {
919                file_id: FileId(1),
920                path: PathBuf::from("/project/utils.ts"),
921                exports: vec![fallow_types::extract::ExportInfo {
922                    name: ExportName::Default,
923                    local_name: None,
924                    is_type_only: false,
925                    visibility: VisibilityTag::None,
926                    span: oxc_span::Span::new(0, 20),
927                    members: vec![],
928                    is_side_effect_used: false,
929                    super_class: None,
930                }],
931                ..Default::default()
932            },
933        ];
934
935        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
936        let utils = &graph.modules[1];
937        let default_export = utils
938            .exports
939            .iter()
940            .find(|e| matches!(e.name, ExportName::Default))
941            .unwrap();
942        assert!(!default_export.references.is_empty());
943        assert_eq!(
944            default_export.references[0].kind,
945            ReferenceKind::DefaultImport
946        );
947    }
948
949    #[test]
950    fn graph_side_effect_import_no_export_reference() {
951        let files = vec![
952            DiscoveredFile {
953                id: FileId(0),
954                path: PathBuf::from("/project/entry.ts"),
955                size_bytes: 100,
956            },
957            DiscoveredFile {
958                id: FileId(1),
959                path: PathBuf::from("/project/styles.ts"),
960                size_bytes: 50,
961            },
962        ];
963        let entry_points = vec![EntryPoint {
964            path: PathBuf::from("/project/entry.ts"),
965            source: EntryPointSource::PackageJsonMain,
966        }];
967        let resolved_modules = vec![
968            ResolvedModule {
969                file_id: FileId(0),
970                path: PathBuf::from("/project/entry.ts"),
971                resolved_imports: vec![ResolvedImport {
972                    info: ImportInfo {
973                        source: "./styles".to_string(),
974                        imported_name: ImportedName::SideEffect,
975                        local_name: String::new(),
976                        is_type_only: false,
977                        from_style: false,
978                        span: oxc_span::Span::new(0, 10),
979                        source_span: oxc_span::Span::default(),
980                    },
981                    target: ResolveResult::InternalModule(FileId(1)),
982                }],
983                ..Default::default()
984            },
985            ResolvedModule {
986                file_id: FileId(1),
987                path: PathBuf::from("/project/styles.ts"),
988                exports: vec![fallow_types::extract::ExportInfo {
989                    name: ExportName::Named("primaryColor".to_string()),
990                    local_name: Some("primaryColor".to_string()),
991                    is_type_only: false,
992                    visibility: VisibilityTag::None,
993                    span: oxc_span::Span::new(0, 20),
994                    members: vec![],
995                    is_side_effect_used: false,
996                    super_class: None,
997                }],
998                ..Default::default()
999            },
1000        ];
1001
1002        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1003        // Side-effect import should create an edge but not reference specific exports
1004        assert_eq!(graph.edge_count(), 1);
1005        let styles = &graph.modules[1];
1006        let export = &styles.exports[0];
1007        // Side-effect import doesn't match any named export
1008        assert!(
1009            export.references.is_empty(),
1010            "side-effect import should not reference named exports"
1011        );
1012    }
1013
1014    #[test]
1015    fn graph_multiple_entry_points() {
1016        let files = vec![
1017            DiscoveredFile {
1018                id: FileId(0),
1019                path: PathBuf::from("/project/main.ts"),
1020                size_bytes: 100,
1021            },
1022            DiscoveredFile {
1023                id: FileId(1),
1024                path: PathBuf::from("/project/worker.ts"),
1025                size_bytes: 100,
1026            },
1027            DiscoveredFile {
1028                id: FileId(2),
1029                path: PathBuf::from("/project/shared.ts"),
1030                size_bytes: 50,
1031            },
1032        ];
1033        let entry_points = vec![
1034            EntryPoint {
1035                path: PathBuf::from("/project/main.ts"),
1036                source: EntryPointSource::PackageJsonMain,
1037            },
1038            EntryPoint {
1039                path: PathBuf::from("/project/worker.ts"),
1040                source: EntryPointSource::PackageJsonMain,
1041            },
1042        ];
1043        let resolved_modules = vec![
1044            ResolvedModule {
1045                file_id: FileId(0),
1046                path: PathBuf::from("/project/main.ts"),
1047                resolved_imports: vec![ResolvedImport {
1048                    info: ImportInfo {
1049                        source: "./shared".to_string(),
1050                        imported_name: ImportedName::Named("helper".to_string()),
1051                        local_name: "helper".to_string(),
1052                        is_type_only: false,
1053                        from_style: false,
1054                        span: oxc_span::Span::new(0, 10),
1055                        source_span: oxc_span::Span::default(),
1056                    },
1057                    target: ResolveResult::InternalModule(FileId(2)),
1058                }],
1059                ..Default::default()
1060            },
1061            ResolvedModule {
1062                file_id: FileId(1),
1063                path: PathBuf::from("/project/worker.ts"),
1064                ..Default::default()
1065            },
1066            ResolvedModule {
1067                file_id: FileId(2),
1068                path: PathBuf::from("/project/shared.ts"),
1069                exports: vec![fallow_types::extract::ExportInfo {
1070                    name: ExportName::Named("helper".to_string()),
1071                    local_name: Some("helper".to_string()),
1072                    is_type_only: false,
1073                    visibility: VisibilityTag::None,
1074                    span: oxc_span::Span::new(0, 20),
1075                    members: vec![],
1076                    is_side_effect_used: false,
1077                    super_class: None,
1078                }],
1079                ..Default::default()
1080            },
1081        ];
1082
1083        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1084        assert!(graph.modules[0].is_entry_point());
1085        assert!(graph.modules[1].is_entry_point());
1086        assert!(!graph.modules[2].is_entry_point());
1087        // All should be reachable — shared is reached from main
1088        assert!(graph.modules[0].is_reachable());
1089        assert!(graph.modules[1].is_reachable());
1090        assert!(graph.modules[2].is_reachable());
1091    }
1092}
fallow_graph/graph/mod.rs

fallow_graph/graph/
mod.rs
