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

fallow_graph/graph/
mod.rs
