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

fallow_graph/graph/
mod.rs
