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

fallow_graph/graph/
mod.rs
