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

fallow_graph/graph/
mod.rs
