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

fallow_graph/graph/
mod.rs
