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/// Importer details for one file that directly imports a target module.
103#[derive(Debug, Clone, PartialEq, Eq)]
104pub struct DirectImporterSummary {
105    /// Source file that imports the requested target.
106    pub source: FileId,
107    /// Symbols imported from the target by this source file.
108    pub symbols: Vec<ImportedSymbolSummary>,
109}
110
111/// Symbol details for a direct import edge.
112#[derive(Debug, Clone, PartialEq, Eq)]
113pub struct ImportedSymbolSummary {
114    /// Imported binding name, using `default`, `*`, and `side-effect` for
115    /// non-named imports.
116    pub imported: String,
117    /// Local binding name in the importing file.
118    pub local: String,
119    /// Whether this symbol came from a type-only import.
120    pub type_only: bool,
121}
122
123#[cfg(target_pointer_width = "64")]
124const _: () = assert!(std::mem::size_of::<Edge>() == 32);
125#[cfg(target_pointer_width = "64")]
126const _: () = assert!(std::mem::size_of::<ImportedSymbol>() == 64);
127
128impl ModuleGraph {
129    fn resolve_entry_point_ids(
130        entry_points: &[EntryPoint],
131        path_to_id: &FxHashMap<&Path, FileId>,
132    ) -> FxHashSet<FileId> {
133        entry_points
134            .iter()
135            .filter_map(|ep| {
136                path_to_id.get(ep.path.as_path()).copied().or_else(|| {
137                    dunce::canonicalize(&ep.path)
138                        .ok()
139                        .and_then(|path| path_to_id.get(path.as_path()).copied())
140                })
141            })
142            .collect()
143    }
144
145    /// Build the module graph from resolved modules and entry points.
146    pub fn build(
147        resolved_modules: &[ResolvedModule],
148        entry_points: &[EntryPoint],
149        files: &[DiscoveredFile],
150    ) -> Self {
151        Self::build_with_reachability_roots(
152            resolved_modules,
153            entry_points,
154            entry_points,
155            &[],
156            files,
157        )
158    }
159
160    /// Build the module graph with explicit runtime and test reachability roots.
161    pub fn build_with_reachability_roots(
162        resolved_modules: &[ResolvedModule],
163        entry_points: &[EntryPoint],
164        runtime_entry_points: &[EntryPoint],
165        test_entry_points: &[EntryPoint],
166        files: &[DiscoveredFile],
167    ) -> Self {
168        let _span = tracing::info_span!("build_graph").entered();
169
170        let module_count = files.len();
171
172        let max_file_id = files
173            .iter()
174            .map(|f| f.id.0 as usize)
175            .max()
176            .map_or(0, |m| m + 1);
177        let total_capacity = max_file_id.max(module_count);
178
179        let path_to_id: FxHashMap<&Path, FileId> =
180            files.iter().map(|f| (f.path.as_path(), f.id)).collect();
181
182        let module_by_id: FxHashMap<FileId, &ResolvedModule> =
183            resolved_modules.iter().map(|m| (m.file_id, m)).collect();
184
185        let mut entry_point_ids = Self::resolve_entry_point_ids(entry_points, &path_to_id);
186        let runtime_entry_point_ids =
187            Self::resolve_entry_point_ids(runtime_entry_points, &path_to_id);
188        let test_entry_point_ids = Self::resolve_entry_point_ids(test_entry_points, &path_to_id);
189
190        for file in files {
191            if is_declaration_file_path(&file.path) {
192                entry_point_ids.insert(file.id);
193            }
194        }
195
196        let mut graph = Self::populate_edges(&build::PopulateEdgesInput {
197            files,
198            module_by_id: &module_by_id,
199            entry_point_ids: &entry_point_ids,
200            runtime_entry_point_ids: &runtime_entry_point_ids,
201            test_entry_point_ids: &test_entry_point_ids,
202            module_count,
203            total_capacity,
204        });
205
206        graph.populate_references(&module_by_id, &entry_point_ids);
207
208        namespace_aliases::propagate_cross_package_aliases(&mut graph, &module_by_id);
209
210        namespace_re_exports::propagate_namespace_re_exports(&mut graph, &module_by_id);
211
212        graph.mark_reachable(
213            &entry_point_ids,
214            &runtime_entry_point_ids,
215            &test_entry_point_ids,
216            total_capacity,
217        );
218
219        graph.re_export_cycles = graph.resolve_re_export_chains();
220
221        graph
222    }
223
224    /// Total number of modules.
225    #[must_use]
226    pub const fn module_count(&self) -> usize {
227        self.modules.len()
228    }
229
230    /// Total number of edges.
231    #[must_use]
232    pub const fn edge_count(&self) -> usize {
233        self.edges.len()
234    }
235
236    /// Check if any importer uses `import * as ns` for this module.
237    /// Uses precomputed bitset — O(1) lookup.
238    #[must_use]
239    pub fn has_namespace_import(&self, file_id: FileId) -> bool {
240        let idx = file_id.0 as usize;
241        if idx >= self.namespace_imported.len() {
242            return false;
243        }
244        self.namespace_imported.contains(idx)
245    }
246
247    /// Get the target `FileId`s of all outgoing edges for a module.
248    #[must_use]
249    pub fn edges_for(&self, file_id: FileId) -> Vec<FileId> {
250        let idx = file_id.0 as usize;
251        if idx >= self.modules.len() {
252            return Vec::new();
253        }
254        let range = &self.modules[idx].edge_range;
255        self.edges[range.clone()].iter().map(|e| e.target).collect()
256    }
257
258    /// Summarize files that directly import `target`.
259    ///
260    /// Uses existing reverse dependency and edge indexes. Returns an empty
261    /// list when the target is out of range or has no importers.
262    #[must_use]
263    pub fn direct_importer_summaries(&self, target: FileId) -> Vec<DirectImporterSummary> {
264        let Some(importers) = self.reverse_deps.get(target.0 as usize) else {
265            return Vec::new();
266        };
267
268        let mut summaries = Vec::new();
269        for &source in importers {
270            let idx = source.0 as usize;
271            let Some(source_node) = self.modules.get(idx) else {
272                continue;
273            };
274            let mut symbols = Vec::new();
275            for edge in &self.edges[source_node.edge_range.clone()] {
276                if edge.target != target {
277                    continue;
278                }
279                symbols.extend(edge.symbols.iter().map(|symbol| ImportedSymbolSummary {
280                    imported: imported_name_label(&symbol.imported_name),
281                    local: symbol.local_name.clone(),
282                    type_only: symbol.is_type_only,
283                }));
284            }
285            symbols.sort_by(|a, b| {
286                a.imported
287                    .cmp(&b.imported)
288                    .then_with(|| a.local.cmp(&b.local))
289                    .then_with(|| a.type_only.cmp(&b.type_only))
290            });
291            symbols.dedup();
292            summaries.push(DirectImporterSummary { source, symbols });
293        }
294        summaries.sort_by_key(|summary| summary.source.0);
295        summaries
296    }
297
298    /// Find the byte offset of the import statement from `source` to `target`.
299    ///
300    /// Mixed type/value imports to the same target are stored as one edge. Prefer
301    /// the first value-carrying import so runtime-cycle diagnostics and line
302    /// suppressions anchor on the import that actually participates in the cycle.
303    /// Returns `None` if no edge exists or the edge has no symbols.
304    #[must_use]
305    pub fn find_import_span_start(&self, source: FileId, target: FileId) -> Option<u32> {
306        let idx = source.0 as usize;
307        if idx >= self.modules.len() {
308            return None;
309        }
310        let range = &self.modules[idx].edge_range;
311        for edge in &self.edges[range.clone()] {
312            if edge.target == target {
313                return edge
314                    .symbols
315                    .iter()
316                    .find(|s| !s.is_type_only)
317                    .or_else(|| edge.symbols.first())
318                    .map(|s| s.import_span.start);
319            }
320        }
321        None
322    }
323
324    /// Iterate outgoing edges with the data the boundary detector needs in a
325    /// single pass: target file id, whether every symbol on the edge is
326    /// type-only (matches the predicate used by cycle detection), and the
327    /// span start of the first value-carrying symbol (or the first symbol
328    /// when every symbol is type-only).
329    ///
330    /// When `featureB` has both `import type { Foo } from './x'` and
331    /// `import { bar } from './x'`, fallow groups them into ONE edge with the
332    /// type-only symbol first and the value symbol second. Consumers need the
333    /// value span so findings anchor on the runtime import line; otherwise a
334    /// `// fallow-ignore-next-line` above the type-only line would silently
335    /// suppress the real violation.
336    ///
337    /// Returns an empty iterator for out-of-range file ids.
338    pub fn outgoing_edge_summaries(
339        &self,
340        file_id: FileId,
341    ) -> impl Iterator<Item = (FileId, bool, Option<u32>)> + '_ {
342        let idx = file_id.0 as usize;
343        let range = if idx < self.modules.len() {
344            self.modules[idx].edge_range.clone()
345        } else {
346            0..0
347        };
348        self.edges[range].iter().map(|edge| {
349            let all_type_only =
350                !edge.symbols.is_empty() && edge.symbols.iter().all(|s| s.is_type_only);
351            let span = edge
352                .symbols
353                .iter()
354                .find(|s| !s.is_type_only)
355                .or_else(|| edge.symbols.first())
356                .map(|s| s.import_span.start);
357            (edge.target, all_type_only, span)
358        })
359    }
360}
361
362fn imported_name_label(name: &ImportedName) -> String {
363    match name {
364        ImportedName::Named(name) => name.clone(),
365        ImportedName::Default => "default".to_string(),
366        ImportedName::Namespace => "*".to_string(),
367        ImportedName::SideEffect => "side-effect".to_string(),
368    }
369}
370
371#[cfg(test)]
372mod tests {
373    use super::*;
374    use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
375    use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource, FileId};
376    use fallow_types::extract::{ExportName, ImportInfo, ImportedName, VisibilityTag};
377    use std::path::PathBuf;
378
379    fn build_simple_graph() -> ModuleGraph {
380        let files = vec![
381            DiscoveredFile {
382                id: FileId(0),
383                path: PathBuf::from("/project/src/entry.ts"),
384                size_bytes: 100,
385            },
386            DiscoveredFile {
387                id: FileId(1),
388                path: PathBuf::from("/project/src/utils.ts"),
389                size_bytes: 50,
390            },
391        ];
392
393        let entry_points = vec![EntryPoint {
394            path: PathBuf::from("/project/src/entry.ts"),
395            source: EntryPointSource::PackageJsonMain,
396        }];
397
398        let resolved_modules = vec![
399            ResolvedModule {
400                file_id: FileId(0),
401                path: PathBuf::from("/project/src/entry.ts"),
402                resolved_imports: vec![ResolvedImport {
403                    info: ImportInfo {
404                        source: "./utils".to_string(),
405                        imported_name: ImportedName::Named("foo".to_string()),
406                        local_name: "foo".to_string(),
407                        is_type_only: false,
408                        from_style: false,
409                        span: oxc_span::Span::new(0, 10),
410                        source_span: oxc_span::Span::default(),
411                    },
412                    target: ResolveResult::InternalModule(FileId(1)),
413                }],
414                ..Default::default()
415            },
416            ResolvedModule {
417                file_id: FileId(1),
418                path: PathBuf::from("/project/src/utils.ts"),
419                exports: vec![
420                    fallow_types::extract::ExportInfo {
421                        name: ExportName::Named("foo".to_string()),
422                        local_name: Some("foo".to_string()),
423                        is_type_only: false,
424                        visibility: VisibilityTag::None,
425                        span: oxc_span::Span::new(0, 20),
426                        members: vec![],
427                        is_side_effect_used: false,
428                        super_class: None,
429                    },
430                    fallow_types::extract::ExportInfo {
431                        name: ExportName::Named("bar".to_string()),
432                        local_name: Some("bar".to_string()),
433                        is_type_only: false,
434                        visibility: VisibilityTag::None,
435                        span: oxc_span::Span::new(25, 45),
436                        members: vec![],
437                        is_side_effect_used: false,
438                        super_class: None,
439                    },
440                ],
441                ..Default::default()
442            },
443        ];
444
445        ModuleGraph::build(&resolved_modules, &entry_points, &files)
446    }
447
448    #[test]
449    fn graph_module_count() {
450        let graph = build_simple_graph();
451        assert_eq!(graph.module_count(), 2);
452    }
453
454    #[test]
455    fn graph_edge_count() {
456        let graph = build_simple_graph();
457        assert_eq!(graph.edge_count(), 1);
458    }
459
460    #[test]
461    fn graph_entry_point_is_reachable() {
462        let graph = build_simple_graph();
463        assert!(graph.modules[0].is_entry_point());
464        assert!(graph.modules[0].is_reachable());
465    }
466
467    #[test]
468    fn graph_imported_module_is_reachable() {
469        let graph = build_simple_graph();
470        assert!(!graph.modules[1].is_entry_point());
471        assert!(graph.modules[1].is_reachable());
472    }
473
474    #[test]
475    #[expect(
476        clippy::too_many_lines,
477        reason = "this test fixture exercises four reachability roles end-to-end; splitting it \
478                  would obscure the cross-role assertions"
479    )]
480    fn graph_distinguishes_runtime_test_and_support_reachability() {
481        let files = vec![
482            DiscoveredFile {
483                id: FileId(0),
484                path: PathBuf::from("/project/src/main.ts"),
485                size_bytes: 100,
486            },
487            DiscoveredFile {
488                id: FileId(1),
489                path: PathBuf::from("/project/src/runtime-only.ts"),
490                size_bytes: 50,
491            },
492            DiscoveredFile {
493                id: FileId(2),
494                path: PathBuf::from("/project/tests/app.test.ts"),
495                size_bytes: 50,
496            },
497            DiscoveredFile {
498                id: FileId(3),
499                path: PathBuf::from("/project/tests/setup.ts"),
500                size_bytes: 50,
501            },
502            DiscoveredFile {
503                id: FileId(4),
504                path: PathBuf::from("/project/src/covered.ts"),
505                size_bytes: 50,
506            },
507        ];
508
509        let all_entry_points = vec![
510            EntryPoint {
511                path: PathBuf::from("/project/src/main.ts"),
512                source: EntryPointSource::PackageJsonMain,
513            },
514            EntryPoint {
515                path: PathBuf::from("/project/tests/app.test.ts"),
516                source: EntryPointSource::TestFile,
517            },
518            EntryPoint {
519                path: PathBuf::from("/project/tests/setup.ts"),
520                source: EntryPointSource::Plugin {
521                    name: "vitest".to_string(),
522                },
523            },
524        ];
525        let runtime_entry_points = vec![EntryPoint {
526            path: PathBuf::from("/project/src/main.ts"),
527            source: EntryPointSource::PackageJsonMain,
528        }];
529        let test_entry_points = vec![EntryPoint {
530            path: PathBuf::from("/project/tests/app.test.ts"),
531            source: EntryPointSource::TestFile,
532        }];
533
534        let resolved_modules = vec![
535            ResolvedModule {
536                file_id: FileId(0),
537                path: PathBuf::from("/project/src/main.ts"),
538                resolved_imports: vec![ResolvedImport {
539                    info: ImportInfo {
540                        source: "./runtime-only".to_string(),
541                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
542                        local_name: "runtimeOnly".to_string(),
543                        is_type_only: false,
544                        from_style: false,
545                        span: oxc_span::Span::new(0, 10),
546                        source_span: oxc_span::Span::default(),
547                    },
548                    target: ResolveResult::InternalModule(FileId(1)),
549                }],
550                ..Default::default()
551            },
552            ResolvedModule {
553                file_id: FileId(1),
554                path: PathBuf::from("/project/src/runtime-only.ts"),
555                exports: vec![fallow_types::extract::ExportInfo {
556                    name: ExportName::Named("runtimeOnly".to_string()),
557                    local_name: Some("runtimeOnly".to_string()),
558                    is_type_only: false,
559                    visibility: VisibilityTag::None,
560                    span: oxc_span::Span::new(0, 20),
561                    members: vec![],
562                    is_side_effect_used: false,
563                    super_class: None,
564                }],
565                ..Default::default()
566            },
567            ResolvedModule {
568                file_id: FileId(2),
569                path: PathBuf::from("/project/tests/app.test.ts"),
570                resolved_imports: vec![ResolvedImport {
571                    info: ImportInfo {
572                        source: "../src/covered".to_string(),
573                        imported_name: ImportedName::Named("covered".to_string()),
574                        local_name: "covered".to_string(),
575                        is_type_only: false,
576                        from_style: false,
577                        span: oxc_span::Span::new(0, 10),
578                        source_span: oxc_span::Span::default(),
579                    },
580                    target: ResolveResult::InternalModule(FileId(4)),
581                }],
582                ..Default::default()
583            },
584            ResolvedModule {
585                file_id: FileId(3),
586                path: PathBuf::from("/project/tests/setup.ts"),
587                resolved_imports: vec![ResolvedImport {
588                    info: ImportInfo {
589                        source: "../src/runtime-only".to_string(),
590                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
591                        local_name: "runtimeOnly".to_string(),
592                        is_type_only: false,
593                        from_style: false,
594                        span: oxc_span::Span::new(0, 10),
595                        source_span: oxc_span::Span::default(),
596                    },
597                    target: ResolveResult::InternalModule(FileId(1)),
598                }],
599                ..Default::default()
600            },
601            ResolvedModule {
602                file_id: FileId(4),
603                path: PathBuf::from("/project/src/covered.ts"),
604                exports: vec![fallow_types::extract::ExportInfo {
605                    name: ExportName::Named("covered".to_string()),
606                    local_name: Some("covered".to_string()),
607                    is_type_only: false,
608                    visibility: VisibilityTag::None,
609                    span: oxc_span::Span::new(0, 20),
610                    members: vec![],
611                    is_side_effect_used: false,
612                    super_class: None,
613                }],
614                ..Default::default()
615            },
616        ];
617
618        let graph = ModuleGraph::build_with_reachability_roots(
619            &resolved_modules,
620            &all_entry_points,
621            &runtime_entry_points,
622            &test_entry_points,
623            &files,
624        );
625
626        assert!(graph.modules[1].is_reachable());
627        assert!(graph.modules[1].is_runtime_reachable());
628        assert!(
629            !graph.modules[1].is_test_reachable(),
630            "support roots should not make runtime-only modules test reachable"
631        );
632
633        assert!(graph.modules[4].is_reachable());
634        assert!(graph.modules[4].is_test_reachable());
635        assert!(
636            !graph.modules[4].is_runtime_reachable(),
637            "test-only reachability should stay separate from runtime roots"
638        );
639    }
640
641    #[test]
642    fn graph_export_has_reference() {
643        let graph = build_simple_graph();
644        let utils = &graph.modules[1];
645        let foo_export = utils
646            .exports
647            .iter()
648            .find(|e| e.name.to_string() == "foo")
649            .unwrap();
650        assert!(
651            !foo_export.references.is_empty(),
652            "foo should have references"
653        );
654    }
655
656    #[test]
657    fn graph_unused_export_no_reference() {
658        let graph = build_simple_graph();
659        let utils = &graph.modules[1];
660        let bar_export = utils
661            .exports
662            .iter()
663            .find(|e| e.name.to_string() == "bar")
664            .unwrap();
665        assert!(
666            bar_export.references.is_empty(),
667            "bar should have no references"
668        );
669    }
670
671    #[test]
672    fn graph_no_namespace_import() {
673        let graph = build_simple_graph();
674        assert!(!graph.has_namespace_import(FileId(0)));
675        assert!(!graph.has_namespace_import(FileId(1)));
676    }
677
678    #[test]
679    fn graph_has_namespace_import() {
680        let files = vec![
681            DiscoveredFile {
682                id: FileId(0),
683                path: PathBuf::from("/project/entry.ts"),
684                size_bytes: 100,
685            },
686            DiscoveredFile {
687                id: FileId(1),
688                path: PathBuf::from("/project/utils.ts"),
689                size_bytes: 50,
690            },
691        ];
692
693        let entry_points = vec![EntryPoint {
694            path: PathBuf::from("/project/entry.ts"),
695            source: EntryPointSource::PackageJsonMain,
696        }];
697
698        let resolved_modules = vec![
699            ResolvedModule {
700                file_id: FileId(0),
701                path: PathBuf::from("/project/entry.ts"),
702                resolved_imports: vec![ResolvedImport {
703                    info: ImportInfo {
704                        source: "./utils".to_string(),
705                        imported_name: ImportedName::Namespace,
706                        local_name: "utils".to_string(),
707                        is_type_only: false,
708                        from_style: false,
709                        span: oxc_span::Span::new(0, 10),
710                        source_span: oxc_span::Span::default(),
711                    },
712                    target: ResolveResult::InternalModule(FileId(1)),
713                }],
714                ..Default::default()
715            },
716            ResolvedModule {
717                file_id: FileId(1),
718                path: PathBuf::from("/project/utils.ts"),
719                exports: vec![fallow_types::extract::ExportInfo {
720                    name: ExportName::Named("foo".to_string()),
721                    local_name: Some("foo".to_string()),
722                    is_type_only: false,
723                    visibility: VisibilityTag::None,
724                    span: oxc_span::Span::new(0, 20),
725                    members: vec![],
726                    is_side_effect_used: false,
727                    super_class: None,
728                }],
729                ..Default::default()
730            },
731        ];
732
733        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
734        assert!(
735            graph.has_namespace_import(FileId(1)),
736            "utils should have namespace import"
737        );
738    }
739
740    #[test]
741    fn graph_has_namespace_import_out_of_bounds() {
742        let graph = build_simple_graph();
743        assert!(!graph.has_namespace_import(FileId(999)));
744    }
745
746    #[test]
747    fn graph_unreachable_module() {
748        let files = vec![
749            DiscoveredFile {
750                id: FileId(0),
751                path: PathBuf::from("/project/entry.ts"),
752                size_bytes: 100,
753            },
754            DiscoveredFile {
755                id: FileId(1),
756                path: PathBuf::from("/project/utils.ts"),
757                size_bytes: 50,
758            },
759            DiscoveredFile {
760                id: FileId(2),
761                path: PathBuf::from("/project/orphan.ts"),
762                size_bytes: 30,
763            },
764        ];
765
766        let entry_points = vec![EntryPoint {
767            path: PathBuf::from("/project/entry.ts"),
768            source: EntryPointSource::PackageJsonMain,
769        }];
770
771        let resolved_modules = vec![
772            ResolvedModule {
773                file_id: FileId(0),
774                path: PathBuf::from("/project/entry.ts"),
775                resolved_imports: vec![ResolvedImport {
776                    info: ImportInfo {
777                        source: "./utils".to_string(),
778                        imported_name: ImportedName::Named("foo".to_string()),
779                        local_name: "foo".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::InternalModule(FileId(1)),
786                }],
787                ..Default::default()
788            },
789            ResolvedModule {
790                file_id: FileId(1),
791                path: PathBuf::from("/project/utils.ts"),
792                exports: vec![fallow_types::extract::ExportInfo {
793                    name: ExportName::Named("foo".to_string()),
794                    local_name: Some("foo".to_string()),
795                    is_type_only: false,
796                    visibility: VisibilityTag::None,
797                    span: oxc_span::Span::new(0, 20),
798                    members: vec![],
799                    is_side_effect_used: false,
800                    super_class: None,
801                }],
802                ..Default::default()
803            },
804            ResolvedModule {
805                file_id: FileId(2),
806                path: PathBuf::from("/project/orphan.ts"),
807                exports: vec![fallow_types::extract::ExportInfo {
808                    name: ExportName::Named("orphan".to_string()),
809                    local_name: Some("orphan".to_string()),
810                    is_type_only: false,
811                    visibility: VisibilityTag::None,
812                    span: oxc_span::Span::new(0, 20),
813                    members: vec![],
814                    is_side_effect_used: false,
815                    super_class: None,
816                }],
817                ..Default::default()
818            },
819        ];
820
821        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
822
823        assert!(graph.modules[0].is_reachable(), "entry should be reachable");
824        assert!(graph.modules[1].is_reachable(), "utils should be reachable");
825        assert!(
826            !graph.modules[2].is_reachable(),
827            "orphan should NOT be reachable"
828        );
829    }
830
831    #[test]
832    fn graph_package_usage_tracked() {
833        let files = vec![DiscoveredFile {
834            id: FileId(0),
835            path: PathBuf::from("/project/entry.ts"),
836            size_bytes: 100,
837        }];
838
839        let entry_points = vec![EntryPoint {
840            path: PathBuf::from("/project/entry.ts"),
841            source: EntryPointSource::PackageJsonMain,
842        }];
843
844        let resolved_modules = vec![ResolvedModule {
845            file_id: FileId(0),
846            path: PathBuf::from("/project/entry.ts"),
847            exports: vec![],
848            re_exports: vec![],
849            resolved_imports: vec![
850                ResolvedImport {
851                    info: ImportInfo {
852                        source: "react".to_string(),
853                        imported_name: ImportedName::Default,
854                        local_name: "React".to_string(),
855                        is_type_only: false,
856                        from_style: false,
857                        span: oxc_span::Span::new(0, 10),
858                        source_span: oxc_span::Span::default(),
859                    },
860                    target: ResolveResult::NpmPackage("react".to_string()),
861                },
862                ResolvedImport {
863                    info: ImportInfo {
864                        source: "lodash".to_string(),
865                        imported_name: ImportedName::Named("merge".to_string()),
866                        local_name: "merge".to_string(),
867                        is_type_only: false,
868                        from_style: false,
869                        span: oxc_span::Span::new(15, 30),
870                        source_span: oxc_span::Span::default(),
871                    },
872                    target: ResolveResult::NpmPackage("lodash".to_string()),
873                },
874            ],
875            ..Default::default()
876        }];
877
878        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
879        assert!(graph.package_usage.contains_key("react"));
880        assert!(graph.package_usage.contains_key("lodash"));
881        assert!(!graph.package_usage.contains_key("express"));
882    }
883
884    #[test]
885    fn graph_empty() {
886        let graph = ModuleGraph::build(&[], &[], &[]);
887        assert_eq!(graph.module_count(), 0);
888        assert_eq!(graph.edge_count(), 0);
889    }
890
891    #[test]
892    fn graph_cjs_exports_tracked() {
893        let files = vec![DiscoveredFile {
894            id: FileId(0),
895            path: PathBuf::from("/project/entry.ts"),
896            size_bytes: 100,
897        }];
898
899        let entry_points = vec![EntryPoint {
900            path: PathBuf::from("/project/entry.ts"),
901            source: EntryPointSource::PackageJsonMain,
902        }];
903
904        let resolved_modules = vec![ResolvedModule {
905            file_id: FileId(0),
906            path: PathBuf::from("/project/entry.ts"),
907            has_cjs_exports: true,
908            has_angular_component_template_url: false,
909            ..Default::default()
910        }];
911
912        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
913        assert!(graph.modules[0].has_cjs_exports());
914    }
915
916    #[test]
917    fn graph_edges_for_returns_targets() {
918        let graph = build_simple_graph();
919        let targets = graph.edges_for(FileId(0));
920        assert_eq!(targets, vec![FileId(1)]);
921    }
922
923    #[test]
924    fn graph_edges_for_no_imports() {
925        let graph = build_simple_graph();
926        let targets = graph.edges_for(FileId(1));
927        assert!(targets.is_empty());
928    }
929
930    #[test]
931    fn graph_edges_for_out_of_bounds() {
932        let graph = build_simple_graph();
933        let targets = graph.edges_for(FileId(999));
934        assert!(targets.is_empty());
935    }
936
937    #[test]
938    fn graph_direct_importer_summaries_include_symbols() {
939        let graph = build_simple_graph();
940        let summaries = graph.direct_importer_summaries(FileId(1));
941
942        assert_eq!(
943            summaries,
944            vec![DirectImporterSummary {
945                source: FileId(0),
946                symbols: vec![ImportedSymbolSummary {
947                    imported: "foo".to_string(),
948                    local: "foo".to_string(),
949                    type_only: false,
950                }],
951            }]
952        );
953    }
954
955    #[test]
956    fn graph_find_import_span_start_found() {
957        let graph = build_simple_graph();
958        let span_start = graph.find_import_span_start(FileId(0), FileId(1));
959        assert!(span_start.is_some());
960        assert_eq!(span_start.unwrap(), 0);
961    }
962
963    #[test]
964    fn graph_find_import_span_start_prefers_value_import_on_mixed_edge() {
965        let files = vec![
966            DiscoveredFile {
967                id: FileId(0),
968                path: PathBuf::from("/project/entry.ts"),
969                size_bytes: 100,
970            },
971            DiscoveredFile {
972                id: FileId(1),
973                path: PathBuf::from("/project/utils.ts"),
974                size_bytes: 50,
975            },
976        ];
977        let entry_points = vec![EntryPoint {
978            path: PathBuf::from("/project/entry.ts"),
979            source: EntryPointSource::PackageJsonMain,
980        }];
981        let resolved_modules = vec![
982            ResolvedModule {
983                file_id: FileId(0),
984                path: PathBuf::from("/project/entry.ts"),
985                resolved_imports: vec![
986                    ResolvedImport {
987                        info: ImportInfo {
988                            source: "./utils".to_string(),
989                            imported_name: ImportedName::Named("Foo".to_string()),
990                            local_name: "Foo".to_string(),
991                            is_type_only: true,
992                            from_style: false,
993                            span: oxc_span::Span::new(10, 20),
994                            source_span: oxc_span::Span::default(),
995                        },
996                        target: ResolveResult::InternalModule(FileId(1)),
997                    },
998                    ResolvedImport {
999                        info: ImportInfo {
1000                            source: "./utils".to_string(),
1001                            imported_name: ImportedName::Named("foo".to_string()),
1002                            local_name: "foo".to_string(),
1003                            is_type_only: false,
1004                            from_style: false,
1005                            span: oxc_span::Span::new(50, 60),
1006                            source_span: oxc_span::Span::default(),
1007                        },
1008                        target: ResolveResult::InternalModule(FileId(1)),
1009                    },
1010                ],
1011                ..Default::default()
1012            },
1013            ResolvedModule {
1014                file_id: FileId(1),
1015                path: PathBuf::from("/project/utils.ts"),
1016                ..Default::default()
1017            },
1018        ];
1019
1020        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1021        assert_eq!(graph.find_import_span_start(FileId(0), FileId(1)), Some(50));
1022    }
1023
1024    #[test]
1025    fn graph_find_import_span_start_wrong_target() {
1026        let graph = build_simple_graph();
1027        let span_start = graph.find_import_span_start(FileId(0), FileId(0));
1028        assert!(span_start.is_none());
1029    }
1030
1031    #[test]
1032    fn graph_find_import_span_start_source_out_of_bounds() {
1033        let graph = build_simple_graph();
1034        let span_start = graph.find_import_span_start(FileId(999), FileId(1));
1035        assert!(span_start.is_none());
1036    }
1037
1038    #[test]
1039    fn graph_find_import_span_start_no_edges() {
1040        let graph = build_simple_graph();
1041        let span_start = graph.find_import_span_start(FileId(1), FileId(0));
1042        assert!(span_start.is_none());
1043    }
1044
1045    #[test]
1046    fn graph_reverse_deps_populated() {
1047        let graph = build_simple_graph();
1048        assert!(graph.reverse_deps[1].contains(&FileId(0)));
1049        assert!(graph.reverse_deps[0].is_empty());
1050    }
1051
1052    #[test]
1053    fn graph_type_only_package_usage_tracked() {
1054        let files = vec![DiscoveredFile {
1055            id: FileId(0),
1056            path: PathBuf::from("/project/entry.ts"),
1057            size_bytes: 100,
1058        }];
1059        let entry_points = vec![EntryPoint {
1060            path: PathBuf::from("/project/entry.ts"),
1061            source: EntryPointSource::PackageJsonMain,
1062        }];
1063        let resolved_modules = vec![ResolvedModule {
1064            file_id: FileId(0),
1065            path: PathBuf::from("/project/entry.ts"),
1066            resolved_imports: vec![
1067                ResolvedImport {
1068                    info: ImportInfo {
1069                        source: "react".to_string(),
1070                        imported_name: ImportedName::Named("FC".to_string()),
1071                        local_name: "FC".to_string(),
1072                        is_type_only: true,
1073                        from_style: false,
1074                        span: oxc_span::Span::new(0, 10),
1075                        source_span: oxc_span::Span::default(),
1076                    },
1077                    target: ResolveResult::NpmPackage("react".to_string()),
1078                },
1079                ResolvedImport {
1080                    info: ImportInfo {
1081                        source: "react".to_string(),
1082                        imported_name: ImportedName::Named("useState".to_string()),
1083                        local_name: "useState".to_string(),
1084                        is_type_only: false,
1085                        from_style: false,
1086                        span: oxc_span::Span::new(15, 30),
1087                        source_span: oxc_span::Span::default(),
1088                    },
1089                    target: ResolveResult::NpmPackage("react".to_string()),
1090                },
1091            ],
1092            ..Default::default()
1093        }];
1094
1095        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1096        assert!(graph.package_usage.contains_key("react"));
1097        assert!(graph.type_only_package_usage.contains_key("react"));
1098    }
1099
1100    #[test]
1101    fn graph_default_import_reference() {
1102        let files = vec![
1103            DiscoveredFile {
1104                id: FileId(0),
1105                path: PathBuf::from("/project/entry.ts"),
1106                size_bytes: 100,
1107            },
1108            DiscoveredFile {
1109                id: FileId(1),
1110                path: PathBuf::from("/project/utils.ts"),
1111                size_bytes: 50,
1112            },
1113        ];
1114        let entry_points = vec![EntryPoint {
1115            path: PathBuf::from("/project/entry.ts"),
1116            source: EntryPointSource::PackageJsonMain,
1117        }];
1118        let resolved_modules = vec![
1119            ResolvedModule {
1120                file_id: FileId(0),
1121                path: PathBuf::from("/project/entry.ts"),
1122                resolved_imports: vec![ResolvedImport {
1123                    info: ImportInfo {
1124                        source: "./utils".to_string(),
1125                        imported_name: ImportedName::Default,
1126                        local_name: "Utils".to_string(),
1127                        is_type_only: false,
1128                        from_style: false,
1129                        span: oxc_span::Span::new(0, 10),
1130                        source_span: oxc_span::Span::default(),
1131                    },
1132                    target: ResolveResult::InternalModule(FileId(1)),
1133                }],
1134                ..Default::default()
1135            },
1136            ResolvedModule {
1137                file_id: FileId(1),
1138                path: PathBuf::from("/project/utils.ts"),
1139                exports: vec![fallow_types::extract::ExportInfo {
1140                    name: ExportName::Default,
1141                    local_name: None,
1142                    is_type_only: false,
1143                    visibility: VisibilityTag::None,
1144                    span: oxc_span::Span::new(0, 20),
1145                    members: vec![],
1146                    is_side_effect_used: false,
1147                    super_class: None,
1148                }],
1149                ..Default::default()
1150            },
1151        ];
1152
1153        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1154        let utils = &graph.modules[1];
1155        let default_export = utils
1156            .exports
1157            .iter()
1158            .find(|e| matches!(e.name, ExportName::Default))
1159            .unwrap();
1160        assert!(!default_export.references.is_empty());
1161        assert_eq!(
1162            default_export.references[0].kind,
1163            ReferenceKind::DefaultImport
1164        );
1165    }
1166
1167    #[test]
1168    fn graph_side_effect_import_no_export_reference() {
1169        let files = vec![
1170            DiscoveredFile {
1171                id: FileId(0),
1172                path: PathBuf::from("/project/entry.ts"),
1173                size_bytes: 100,
1174            },
1175            DiscoveredFile {
1176                id: FileId(1),
1177                path: PathBuf::from("/project/styles.ts"),
1178                size_bytes: 50,
1179            },
1180        ];
1181        let entry_points = vec![EntryPoint {
1182            path: PathBuf::from("/project/entry.ts"),
1183            source: EntryPointSource::PackageJsonMain,
1184        }];
1185        let resolved_modules = vec![
1186            ResolvedModule {
1187                file_id: FileId(0),
1188                path: PathBuf::from("/project/entry.ts"),
1189                resolved_imports: vec![ResolvedImport {
1190                    info: ImportInfo {
1191                        source: "./styles".to_string(),
1192                        imported_name: ImportedName::SideEffect,
1193                        local_name: String::new(),
1194                        is_type_only: false,
1195                        from_style: false,
1196                        span: oxc_span::Span::new(0, 10),
1197                        source_span: oxc_span::Span::default(),
1198                    },
1199                    target: ResolveResult::InternalModule(FileId(1)),
1200                }],
1201                ..Default::default()
1202            },
1203            ResolvedModule {
1204                file_id: FileId(1),
1205                path: PathBuf::from("/project/styles.ts"),
1206                exports: vec![fallow_types::extract::ExportInfo {
1207                    name: ExportName::Named("primaryColor".to_string()),
1208                    local_name: Some("primaryColor".to_string()),
1209                    is_type_only: false,
1210                    visibility: VisibilityTag::None,
1211                    span: oxc_span::Span::new(0, 20),
1212                    members: vec![],
1213                    is_side_effect_used: false,
1214                    super_class: None,
1215                }],
1216                ..Default::default()
1217            },
1218        ];
1219
1220        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1221        assert_eq!(graph.edge_count(), 1);
1222        let styles = &graph.modules[1];
1223        let export = &styles.exports[0];
1224        assert!(
1225            export.references.is_empty(),
1226            "side-effect import should not reference named exports"
1227        );
1228    }
1229
1230    #[test]
1231    fn graph_multiple_entry_points() {
1232        let files = vec![
1233            DiscoveredFile {
1234                id: FileId(0),
1235                path: PathBuf::from("/project/main.ts"),
1236                size_bytes: 100,
1237            },
1238            DiscoveredFile {
1239                id: FileId(1),
1240                path: PathBuf::from("/project/worker.ts"),
1241                size_bytes: 100,
1242            },
1243            DiscoveredFile {
1244                id: FileId(2),
1245                path: PathBuf::from("/project/shared.ts"),
1246                size_bytes: 50,
1247            },
1248        ];
1249        let entry_points = vec![
1250            EntryPoint {
1251                path: PathBuf::from("/project/main.ts"),
1252                source: EntryPointSource::PackageJsonMain,
1253            },
1254            EntryPoint {
1255                path: PathBuf::from("/project/worker.ts"),
1256                source: EntryPointSource::PackageJsonMain,
1257            },
1258        ];
1259        let resolved_modules = vec![
1260            ResolvedModule {
1261                file_id: FileId(0),
1262                path: PathBuf::from("/project/main.ts"),
1263                resolved_imports: vec![ResolvedImport {
1264                    info: ImportInfo {
1265                        source: "./shared".to_string(),
1266                        imported_name: ImportedName::Named("helper".to_string()),
1267                        local_name: "helper".to_string(),
1268                        is_type_only: false,
1269                        from_style: false,
1270                        span: oxc_span::Span::new(0, 10),
1271                        source_span: oxc_span::Span::default(),
1272                    },
1273                    target: ResolveResult::InternalModule(FileId(2)),
1274                }],
1275                ..Default::default()
1276            },
1277            ResolvedModule {
1278                file_id: FileId(1),
1279                path: PathBuf::from("/project/worker.ts"),
1280                ..Default::default()
1281            },
1282            ResolvedModule {
1283                file_id: FileId(2),
1284                path: PathBuf::from("/project/shared.ts"),
1285                exports: vec![fallow_types::extract::ExportInfo {
1286                    name: ExportName::Named("helper".to_string()),
1287                    local_name: Some("helper".to_string()),
1288                    is_type_only: false,
1289                    visibility: VisibilityTag::None,
1290                    span: oxc_span::Span::new(0, 20),
1291                    members: vec![],
1292                    is_side_effect_used: false,
1293                    super_class: None,
1294                }],
1295                ..Default::default()
1296            },
1297        ];
1298
1299        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
1300        assert!(graph.modules[0].is_entry_point());
1301        assert!(graph.modules[1].is_entry_point());
1302        assert!(!graph.modules[2].is_entry_point());
1303        assert!(graph.modules[0].is_reachable());
1304        assert!(graph.modules[1].is_reachable());
1305        assert!(graph.modules[2].is_reachable());
1306    }
1307}
fallow_graph/graph/mod.rs

fallow_graph/graph/
mod.rs
