fallow_graph/graph/
mod.rs

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

fallow_graph/graph/
mod.rs
