Skip to main content

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 ambiguity;
7mod build;
8mod cycle_edge_span;
9mod cycles;
10mod effective_exports;
11mod effective_re_exports;
12mod entry_load;
13mod fan_io;
14mod impact_closure;
15mod namespace_aliases;
16mod namespace_indexes;
17mod namespace_re_exports;
18mod narrowing;
19pub mod package_entry;
20mod partition_order;
21mod public_exports;
22mod re_exports;
23mod reachability;
24mod shortest_import_path;
25mod support_reach;
26mod test_reach;
27pub mod types;
28
29use std::path::Path;
30
31use fixedbitset::FixedBitSet;
32use rustc_hash::{FxHashMap, FxHashSet};
33
34use crate::resolve::{ResolvedModule, ResolvedReplacedModuleTarget};
35use fallow_types::discover::{DiscoveredFile, EntryPoint, FileId};
36use fallow_types::extract::{ImportLoadKind, ImportedName, ModuleLoadMechanism};
37use types::{ReferencePathInterner, ReferencePathNode, ReferenceRouteNodeId, ReferenceRoutes};
38
39/// Strip `root` and forward-slash-normalize a module path so report keys match
40/// across platforms. Every report surface that emits a root-relative path key
41/// goes through this, so the four surfaces cannot drift apart.
42pub(super) fn relativize(path: &Path, root: &Path) -> String {
43    path.strip_prefix(root)
44        .unwrap_or(path)
45        .to_string_lossy()
46        .replace('\\', "/")
47}
48
49pub use ambiguity::{AmbiguityParticipants, AmbiguousStarExport};
50pub use cycles::{CycleOptions, CycleSearch, MAX_CYCLE_LENGTH, MAX_CYCLES_PER_SCC};
51pub use effective_exports::{EffectiveExportBinding, EffectiveExportResolution, ExportNamespace};
52pub use effective_re_exports::EffectiveReExportRoute;
53pub use entry_load::{DominatingImport, EntryLoadClosure};
54pub use fan_io::{FocusFileFacts, FocusFileFactsPaths};
55pub use impact_closure::{
56    CoordinationGap, CoordinationGapPaths, ImpactClosure, ImpactClosurePaths,
57};
58pub use partition_order::{PartitionOrder, PartitionOrderPaths, ReviewUnit, ReviewUnitPaths};
59pub use public_exports::PublicExportOrigin;
60pub use re_exports::GraphReExportCycle;
61pub use shortest_import_path::ImportPathHop;
62pub use test_reach::{ExportTestReach, ExportTestReachResult, TestMaskingState};
63pub use types::{
64    ExportSymbol, ModuleNode, ReExportEdge, ReachabilityRoots, ReferenceKind, ReferencePathId,
65    SymbolReference,
66};
67
68/// Direct declaration selected by one unique effective export binding.
69#[derive(Debug, Clone, Copy)]
70pub struct EffectiveExportOrigin<'graph> {
71    file_id: FileId,
72    export: &'graph ExportSymbol,
73}
74
75/// One namespace-specific export exposed by a module and its effective binding.
76#[derive(Debug, Clone, Copy)]
77pub struct EffectiveExportSurface<'graph> {
78    binding: EffectiveExportBinding,
79    namespace: ExportNamespace,
80    export: Option<&'graph ExportSymbol>,
81    origin: Option<EffectiveExportOrigin<'graph>>,
82    local_export: bool,
83}
84
85impl<'graph> EffectiveExportSurface<'graph> {
86    /// Canonical binding exposed by the requested module/name/namespace.
87    #[must_use]
88    pub const fn binding(self) -> EffectiveExportBinding {
89        self.binding
90    }
91
92    /// Namespace selected for this surface.
93    #[must_use]
94    pub const fn namespace(self) -> ExportNamespace {
95        self.namespace
96    }
97
98    /// Reference-bearing graph export selected for this surface.
99    ///
100    /// Direct declarations use their origin export. Named re-exports use their
101    /// single barrel surface while references remain namespace-specific;
102    /// namespace objects and implicit SFC defaults have no declaration export.
103    #[must_use]
104    pub const fn export(self) -> Option<&'graph ExportSymbol> {
105        self.export
106    }
107
108    /// Direct declaration that owns this binding, when one exists.
109    #[must_use]
110    pub const fn origin(self) -> Option<EffectiveExportOrigin<'graph>> {
111        self.origin
112    }
113}
114
115impl<'graph> EffectiveExportOrigin<'graph> {
116    /// Module that owns the selected declaration.
117    #[must_use]
118    pub const fn file_id(self) -> FileId {
119        self.file_id
120    }
121
122    /// Selected declaration in its owning module.
123    #[must_use]
124    pub const fn export(self) -> &'graph ExportSymbol {
125        self.export
126    }
127}
128
129/// True when the path's final component looks like a TypeScript declaration
130/// file (`.d.ts`, `.d.mts`, `.d.cts`). Used to seed declaration files as
131/// overall entry points so ambient `typeof import()` references stay alive;
132/// see [`ModuleGraph::build_with_declaration_seeding`] for the exception.
133///
134/// The analysis layer reuses this predicate. Keep it in sync with the
135/// discovery walk's declaration-file predicate, which exempts declaration
136/// files from the file-size skip.
137#[must_use]
138pub fn is_declaration_file_path(path: &Path) -> bool {
139    path.file_name()
140        .and_then(|n| n.to_str())
141        .is_some_and(|name| {
142            name.ends_with(".d.ts") || name.ends_with(".d.mts") || name.ends_with(".d.cts")
143        })
144}
145
146/// The core module dependency graph.
147///
148/// Derives `serde` so the whole graph can be persisted to `.fallow/graph-cache.bin`
149/// (see `crate::cache`) and skipped on a re-run whose inputs are byte-identical.
150/// `namespace_imported` is a derived `FixedBitSet` reconstructed from the edge
151/// set on cache load (`reconstruct_namespace_imported`), so it is
152/// `#[serde(skip, default)]` rather than persisted.
153#[derive(Debug, serde::Serialize, serde::Deserialize)]
154pub struct ModuleGraph {
155    /// All modules indexed by `FileId`.
156    ///
157    /// Invariant: `modules[file_id.0 as usize].file_id == file_id` for every
158    /// `FileId` in the graph. Holds because `discover/walk.rs` assigns FileIds
159    /// sequentially via `.enumerate()` after path-sorting, and
160    /// `build::populate_edges` pushes one `ModuleNode` per file in iteration
161    /// order. Detectors rely on this for O(1) FileId-to-module lookup
162    /// (`graph.modules.get(file_id.0 as usize)`) instead of building a
163    /// per-call `FxHashMap<FileId, &ModuleNode>`.
164    pub modules: Vec<ModuleNode>,
165    /// Flat edge storage for cache-friendly iteration.
166    edges: Vec<Edge>,
167    /// Maps npm package names to the `FileId`s that import them, with one
168    /// entry per import. A file with two imports of a package appears twice.
169    pub package_usage: FxHashMap<String, Vec<FileId>>,
170    /// Maps npm package names to the `FileId`s that import them with type-only
171    /// imports, with one entry per type-only import.
172    /// A package appearing here but not in `package_usage` (or only in both) indicates
173    /// it's only used for types and could be a devDependency.
174    pub type_only_package_usage: FxHashMap<String, Vec<FileId>>,
175    /// Maps npm package names to the `FileId`s that read a file of the
176    /// package through a webpack asset loader (`raw-loader!pkg/file.txt`).
177    /// The bundle holds the text, the bytes or a URL of the file, so the
178    /// package is used at build time and the import is not a runtime import.
179    /// Every entry is also in `package_usage`.
180    pub asset_package_usage: FxHashMap<String, Vec<FileId>>,
181    /// Package specifiers that each module imports statically with a runtime
182    /// value (no `import()`, no type-only import). Read by the startup weight
183    /// report to list the packages on the startup path of an entry.
184    pub eager_package_imports: FxHashMap<FileId, Vec<EagerPackageImport>>,
185    /// All entry point `FileId`s.
186    pub entry_points: FxHashSet<FileId>,
187    /// Runtime/application entry point `FileId`s.
188    pub runtime_entry_points: FxHashSet<FileId>,
189    /// Test entry point `FileId`s.
190    pub test_entry_points: FxHashSet<FileId>,
191    /// Support entry point `FileId`s, such as files that package.json scripts run.
192    support_entry_points: FxHashSet<FileId>,
193    /// Compact correlation index for distinct test-root replacement profiles.
194    ///
195    /// Empty when no test root declares a project-internal replacement. That
196    /// preserves the ordinary single-BFS test reachability path.
197    test_reachability_index: TestReachabilityIndex,
198    /// Flat interned linked paths used by exact export references.
199    reference_paths: Vec<ReferencePathNode>,
200    /// Compact transition graphs used by namespace-derived references.
201    reference_routes: ReferenceRoutes,
202    /// Reverse index: for each `FileId`, which files import it.
203    pub reverse_deps: Vec<Vec<FileId>>,
204    /// Precomputed: which modules have namespace imports (import * as ns).
205    ///
206    /// Derived entirely from the edge set (a module is namespace-imported iff
207    /// some edge to it carries an `ImportedName::Namespace` symbol), so it is
208    /// not persisted: on cache load it is rebuilt by
209    /// [`ModuleGraph::reconstruct_namespace_imported`], which replicates the
210    /// exact insertion logic from `build.rs`.
211    #[serde(skip, default)]
212    namespace_imported: FixedBitSet,
213    /// Re-export cycles and self-loops detected during Phase 4 chain
214    /// resolution. Each entry names the participating files (sorted
215    /// lexicographically) and a `is_self_loop` flag distinguishing
216    /// single-file self-re-exports from multi-node cycles. Populated by
217    /// `re_exports::find_re_export_cycles` and consumed by the analysis
218    /// backend, which wraps each entry in a typed `ReExportCycleFinding`.
219    pub re_export_cycles: Vec<GraphReExportCycle>,
220    /// Canonical direct and transitive export binding resolution.
221    effective_exports: effective_exports::EffectiveExportIndex,
222}
223
224/// An edge in the module graph.
225///
226/// Public consumers inspect relationships through summary methods such as
227/// [`ModuleGraph::direct_importer_summaries`] and
228/// [`ModuleGraph::outgoing_edge_summaries`]. Keeping the raw storage private
229/// preserves graph invariants and the `Edge == 32` size assertion below.
230#[derive(Debug, serde::Serialize, serde::Deserialize)]
231pub struct Edge {
232    /// Source module of this import edge.
233    source: FileId,
234    /// Target module imported by `source`.
235    target: FileId,
236    /// Symbols imported across this edge.
237    symbols: Vec<ImportedSymbol>,
238}
239
240impl Edge {
241    /// Whether the target can run as code through this edge (see
242    /// [`ImportLoadKind::runs_target_code`]). An edge whose every symbol is an
243    /// asset reference keeps the target in use, but reachability does not
244    /// continue into the imports of the target.
245    #[must_use]
246    fn runs_target_code(&self) -> bool {
247        self.symbols.is_empty()
248            || self
249                .symbols
250                .iter()
251                .any(|symbol| symbol.load_kind.runs_target_code())
252    }
253
254    /// Whether a test that loads the target through this edge runs target
255    /// code. The build erases a type-only import before the test runs, so an
256    /// edge whose every symbol is type-only gives no test reach. Dead-code
257    /// reachability keeps [`Self::runs_target_code`].
258    #[must_use]
259    fn runs_target_code_in_tests(&self) -> bool {
260        self.symbols.is_empty()
261            || self
262                .symbols
263                .iter()
264                .any(|symbol| !symbol.is_type_only && symbol.load_kind.runs_target_code())
265    }
266}
267
268/// One package specifier that a module imports statically with a runtime value.
269#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
270pub struct EagerPackageImport {
271    /// The package name, for example `lodash` or `@scope/pkg`.
272    pub package: String,
273    /// The specifier as written, for example `lodash/debounce`.
274    pub specifier: String,
275}
276
277/// A symbol imported across an edge.
278#[derive(Debug, serde::Serialize, serde::Deserialize)]
279pub struct ImportedSymbol {
280    /// The name as imported from the target (`Named`, `Default`, `Namespace`,
281    /// `SideEffect`).
282    pub imported_name: ImportedName,
283    /// Local binding name in the importing file.
284    pub local_name: String,
285    /// Byte span of the import statement in the source file.
286    #[serde(with = "crate::cache::span_serde")]
287    pub import_span: oxc_span::Span,
288    /// Whether this import is type-only (`import type { ... }`).
289    /// Used to skip type-only edges in circular dependency detection.
290    pub is_type_only: bool,
291    /// Whether the ambient star this symbol stands for is spelled
292    /// `export type *` (issue #2375), which forwards type meanings only.
293    pub(crate) is_type_only_star: bool,
294    /// Runtime module mechanism that created this symbol edge.
295    mechanism: ModuleLoadMechanism,
296    /// When the target loads relative to the importer, and whether it runs
297    /// at all. Fits in the padding after the flags, so the 64-byte size
298    /// assertion holds.
299    load_kind: ImportLoadKind,
300}
301
302impl ImportedSymbol {
303    /// When the target of this symbol edge loads, relative to the importer.
304    #[must_use]
305    pub const fn load_kind(&self) -> ImportLoadKind {
306        self.load_kind
307    }
308
309    /// Whether this symbol loads its target before the importer runs and
310    /// carries a runtime value, so the target is on the startup path.
311    #[must_use]
312    pub const fn is_eager_value(&self) -> bool {
313        self.load_kind.is_eager_value(self.is_type_only)
314    }
315
316    /// Whether this symbol runs its target (see
317    /// [`ImportLoadKind::loads_target`]). A path reference and an asset
318    /// reference keep the target in use without running it.
319    #[must_use]
320    pub const fn loads_target(&self) -> bool {
321        self.load_kind.loads_target()
322    }
323
324    /// Whether this symbol is the whole-module shape of `export *` or
325    /// `export * as ns` inside a `declare module '...'` body (issue #2357):
326    /// type-only, bound to no local name, and naming the module namespace or
327    /// its `default` member (recorded for the `export * as ns` form).
328    ///
329    /// The ambient body is erased at runtime, so package usage stays
330    /// type-only, but the star forwards every export of the target, so the
331    /// graph credits its star surface instead of narrowing to imported names.
332    /// Every other type-only symbol, bound (`import type { x }`) or not (an
333    /// ambient named re-export, an `import()` type reference), credits the
334    /// names it actually imports.
335    #[must_use]
336    fn is_ambient_star(&self) -> bool {
337        self.is_type_only
338            && self.local_name.is_empty()
339            && matches!(
340                self.imported_name,
341                ImportedName::Namespace | ImportedName::Default
342            )
343    }
344
345    /// Whether this ambient star forwards both meanings of every name it
346    /// carries.
347    ///
348    /// `export *` inside the body re-exports the target's value and type
349    /// declarations alike, so it credits both namespaces. `export type *`
350    /// erases every value meaning (issue #2375), so it credits type space
351    /// only, exactly like the ambient named re-exports of issue #2349.
352    #[must_use]
353    fn is_value_bearing_ambient_star(&self) -> bool {
354        self.is_ambient_star() && !self.is_type_only_star
355    }
356}
357
358/// Flat bitset index mapping files to the test profiles that reach them.
359///
360/// Each file owns `words_per_file` contiguous reachable-profile words. Masks are
361/// target-sparse: only explicit replacement targets own a row, while every row
362/// retains dense profile words for constant-time word lookup. Retained storage
363/// is `O((files + replaced_targets) * ceil(profiles / 64))`; correlation queries
364/// intersect machine words instead of scanning profile file lists.
365#[derive(Debug, Default, serde::Serialize, serde::Deserialize)]
366struct TestReachabilityIndex {
367    profile_count: usize,
368    words_per_file: usize,
369    reachable_profiles: Vec<u64>,
370    masked_profiles: Vec<MaskedTestProfiles>,
371    /// The test roots of each profile, by profile index. The per-root query
372    /// reads it to find the replacement mask of one root.
373    profile_roots: Vec<Vec<FileId>>,
374    /// True when test roots declare replacement masks, but the distinct mask
375    /// count passed the profile safety cap. Reachability then ignores the
376    /// masks, so a mocked module counts as reached.
377    masking_capped: bool,
378}
379
380/// Sparse profile-mask row for one replaced target.
381#[derive(Debug, serde::Serialize, serde::Deserialize)]
382struct MaskedTestProfiles {
383    target: FileId,
384    profiles: Vec<u64>,
385}
386
387impl TestReachabilityIndex {
388    fn new(file_capacity: usize, profile_count: usize) -> Self {
389        let words_per_file = profile_count.div_ceil(u64::BITS as usize);
390        let storage_len = file_capacity.saturating_mul(words_per_file);
391        Self {
392            profile_count,
393            words_per_file,
394            reachable_profiles: vec![0; storage_len],
395            masked_profiles: Vec::new(),
396            profile_roots: Vec::new(),
397            masking_capped: false,
398        }
399    }
400
401    /// The replaced targets of each test root that has a replacement, sorted
402    /// by target id.
403    fn root_masks(&self) -> FxHashMap<FileId, Vec<FileId>> {
404        let mut masks: FxHashMap<FileId, Vec<FileId>> = FxHashMap::default();
405        for row in &self.masked_profiles {
406            for (profile, roots) in self.profile_roots.iter().enumerate() {
407                let masked = row
408                    .profiles
409                    .get(profile / u64::BITS as usize)
410                    .is_some_and(|word| word & (1_u64 << (profile % u64::BITS as usize)) != 0);
411                if !masked {
412                    continue;
413                }
414                for &root in roots {
415                    masks.entry(root).or_default().push(row.target);
416                }
417            }
418        }
419        masks
420    }
421
422    fn set_sparse_masks(&mut self, masks: FxHashMap<FileId, Vec<u64>>) {
423        let mut rows: Vec<_> = masks
424            .into_iter()
425            .map(|(target, profiles)| MaskedTestProfiles { target, profiles })
426            .collect();
427        rows.sort_unstable_by_key(|row| row.target.0);
428        self.masked_profiles = rows;
429    }
430
431    fn profiles_for<'a>(&self, storage: &'a [u64], file_id: FileId) -> Option<&'a [u64]> {
432        let start = (file_id.0 as usize).checked_mul(self.words_per_file)?;
433        let end = start.checked_add(self.words_per_file)?;
434        storage.get(start..end)
435    }
436
437    fn masked_profiles_for(&self, file_id: FileId) -> Option<&[u64]> {
438        self.masked_profiles
439            .binary_search_by_key(&file_id.0, |row| row.target.0)
440            .ok()
441            .map(|index| self.masked_profiles[index].profiles.as_slice())
442    }
443
444    fn covers_reference_path(
445        &self,
446        source: FileId,
447        path: types::ReferencePathId,
448        paths: &[ReferencePathNode],
449        routes: &ReferenceRoutes,
450    ) -> bool {
451        let Some(source_profiles) = self.profiles_for(&self.reachable_profiles, source) else {
452            return false;
453        };
454
455        for (word_index, &source_word) in source_profiles.iter().enumerate() {
456            let mut active_profiles = source_word;
457            if active_profiles == 0 {
458                continue;
459            }
460
461            let mut next = Some(path);
462            while let Some(path_id) = next {
463                let Some(path_node) = paths.get(path_id.index()) else {
464                    return false;
465                };
466                next = path_node.parent();
467                active_profiles = match *path_node {
468                    ReferencePathNode::Hop {
469                        target, mechanism, ..
470                    } => self.active_hop_profiles(target, mechanism, word_index, active_profiles),
471                    ReferencePathNode::Route {
472                        graph,
473                        start,
474                        terminal,
475                        start_mechanism,
476                        ..
477                    } => self.active_route_profiles(
478                        routes,
479                        graph,
480                        start,
481                        terminal,
482                        start_mechanism,
483                        word_index,
484                        active_profiles,
485                    ),
486                };
487                if active_profiles == 0 {
488                    break;
489                }
490            }
491
492            if active_profiles != 0 {
493                return true;
494            }
495        }
496
497        false
498    }
499
500    fn active_hop_profiles(
501        &self,
502        target: FileId,
503        mechanism: ModuleLoadMechanism,
504        word_index: usize,
505        mut active_profiles: u64,
506    ) -> u64 {
507        let Some(target_word) = self
508            .profiles_for(&self.reachable_profiles, target)
509            .and_then(|profiles| profiles.get(word_index))
510        else {
511            return 0;
512        };
513        active_profiles &= target_word;
514        if matches!(mechanism, ModuleLoadMechanism::EsModule)
515            && let Some(masked_profiles) = self.masked_profiles_for(target)
516        {
517            let Some(masked_word) = masked_profiles.get(word_index) else {
518                return 0;
519            };
520            active_profiles &= !masked_word;
521        }
522        active_profiles
523    }
524
525    /// Evaluate one compact namespace transition graph with a monotone
526    /// profile-bit worklist. Each `(route node, profile bit)` is processed at
527    /// most once, including cyclic graphs.
528    #[expect(
529        clippy::too_many_arguments,
530        reason = "the route identity and profile word form one evaluation contract"
531    )]
532    fn active_route_profiles(
533        &self,
534        routes: &ReferenceRoutes,
535        graph_id: types::ReferenceRouteGraphId,
536        start: ReferenceRouteNodeId,
537        terminal: ReferenceRouteNodeId,
538        start_mechanism: Option<ModuleLoadMechanism>,
539        word_index: usize,
540        candidate_profiles: u64,
541    ) -> u64 {
542        let Some(graph) = routes.graphs.get(graph_id.0 as usize) else {
543            return 0;
544        };
545        let node_count = graph.nodes.end.saturating_sub(graph.nodes.start) as usize;
546        let start_index = start.0 as usize;
547        let terminal_index = terminal.0 as usize;
548        if start_index >= node_count || terminal_index >= node_count {
549            return 0;
550        }
551
552        let mut attempted = vec![0_u64; node_count];
553        let mut pending = vec![0_u64; node_count];
554        let mut queued = vec![false; node_count];
555        let mut queue = std::collections::VecDeque::from([start_index]);
556        pending[start_index] = candidate_profiles;
557        queued[start_index] = true;
558        let mut successful_profiles = 0_u64;
559
560        while let Some(local_index) = queue.pop_front() {
561            queued[local_index] = false;
562            let incoming = pending[local_index] & !attempted[local_index];
563            pending[local_index] = 0;
564            attempted[local_index] |= incoming;
565            if incoming == 0 {
566                continue;
567            }
568
569            let Some(node) = routes.nodes.get(graph.nodes.start as usize + local_index) else {
570                return 0;
571            };
572            let active = if local_index == start_index {
573                start_mechanism.map_or(incoming, |mechanism| {
574                    self.active_hop_profiles(node.target, mechanism, word_index, incoming)
575                })
576            } else {
577                self.active_hop_profiles(node.target, node.mechanism, word_index, incoming)
578            };
579            if active == 0 {
580                continue;
581            }
582            if local_index == terminal_index {
583                successful_profiles |= active;
584                continue;
585            }
586
587            let Some(successors) = routes
588                .edges
589                .get(node.successors.start as usize..node.successors.end as usize)
590            else {
591                return 0;
592            };
593            for successor in successors {
594                let successor_index = successor.0 as usize;
595                if successor_index >= node_count {
596                    return 0;
597                }
598                let new_profiles = active & !attempted[successor_index] & !pending[successor_index];
599                if new_profiles == 0 {
600                    continue;
601                }
602                pending[successor_index] |= new_profiles;
603                if !queued[successor_index] {
604                    queued[successor_index] = true;
605                    queue.push_back(successor_index);
606                }
607            }
608        }
609
610        successful_profiles
611    }
612
613    #[cfg(test)]
614    fn profile_contains(&self, storage: &[u64], file_id: FileId, profile: usize) -> bool {
615        self.profiles_for(storage, file_id)
616            .and_then(|words| words.get(profile / u64::BITS as usize))
617            .is_some_and(|word| word & (1_u64 << (profile % u64::BITS as usize)) != 0)
618    }
619
620    #[cfg(test)]
621    fn profile_reaches(&self, file_id: FileId, profile: usize) -> bool {
622        self.profile_contains(&self.reachable_profiles, file_id, profile)
623    }
624
625    #[cfg(test)]
626    fn profile_masks(&self, file_id: FileId, profile: usize) -> bool {
627        self.masked_profiles_for(file_id)
628            .and_then(|words| words.get(profile / u64::BITS as usize))
629            .is_some_and(|word| word & (1_u64 << (profile % u64::BITS as usize)) != 0)
630    }
631}
632
633/// One outgoing edge that runs its target, from
634/// [`ModuleGraph::outgoing_edge_summaries`].
635#[derive(Debug, Clone, Copy)]
636pub struct OutgoingEdgeSummary<'a> {
637    /// The imported module.
638    pub target: FileId,
639    /// Whether every symbol that loads the target is type-only, so the build
640    /// erases the import.
641    pub all_type_only: bool,
642    /// Byte offset of the first value symbol that loads the target, or of
643    /// the first loading symbol when all of them are type-only.
644    pub span_start: Option<u32>,
645    /// Every symbol of the edge, also the symbols that do not load the
646    /// target. Filter with [`ImportedSymbol::loads_target`].
647    pub symbols: &'a [ImportedSymbol],
648}
649
650/// Importer details for one file that directly imports a target module.
651#[derive(Debug, Clone, PartialEq, Eq)]
652pub struct DirectImporterSummary {
653    /// Source file that imports the requested target.
654    pub source: FileId,
655    /// Symbols imported from the target by this source file.
656    pub symbols: Vec<ImportedSymbolSummary>,
657}
658
659/// Symbol details for a direct import edge.
660#[derive(Debug, Clone, PartialEq, Eq)]
661pub struct ImportedSymbolSummary {
662    /// Imported binding name, using `default`, `*`, and `side-effect` for
663    /// non-named imports.
664    pub imported: String,
665    /// Local binding name in the importing file.
666    pub local: String,
667    /// Whether this symbol came from a type-only import.
668    pub type_only: bool,
669}
670
671#[cfg(target_pointer_width = "64")]
672const _: () = assert!(std::mem::size_of::<Edge>() == 32);
673#[cfg(target_pointer_width = "64")]
674const _: () = assert!(std::mem::size_of::<ImportedSymbol>() == 64);
675
676#[cold]
677#[inline(never)]
678fn propagate_namespace_references(
679    graph: &mut ModuleGraph,
680    module_by_id: &FxHashMap<FileId, &ResolvedModule>,
681    features: build::NamespaceFeatures,
682    exposed_namespace_targets: &re_exports::ExposedNamespaceTargets,
683    reference_paths: &mut ReferencePathInterner,
684) {
685    let indexes = namespace_indexes::NamespacePropagationIndexes::new(graph, module_by_id);
686    if features.has_aliases {
687        namespace_aliases::propagate_cross_package_aliases(
688            graph,
689            module_by_id,
690            &indexes,
691            reference_paths,
692        );
693    }
694    if features.has_re_exports {
695        namespace_re_exports::propagate_namespace_re_exports(
696            graph,
697            &indexes,
698            exposed_namespace_targets,
699            reference_paths,
700        );
701    }
702}
703
704impl ModuleGraph {
705    fn resolve_entry_point_ids(
706        entry_points: &[EntryPoint],
707        path_to_id: &FxHashMap<&Path, FileId>,
708    ) -> FxHashSet<FileId> {
709        entry_points
710            .iter()
711            .filter_map(|ep| {
712                path_to_id.get(ep.path.as_path()).copied().or_else(|| {
713                    dunce::canonicalize(&ep.path)
714                        .ok()
715                        .and_then(|path| path_to_id.get(path.as_path()).copied())
716                })
717            })
718            .collect()
719    }
720
721    /// Build the module graph from resolved modules and entry points.
722    pub fn build(
723        resolved_modules: &[ResolvedModule],
724        entry_points: &[EntryPoint],
725        files: &[DiscoveredFile],
726    ) -> Self {
727        Self::build_with_reachability_roots(
728            resolved_modules,
729            entry_points,
730            entry_points,
731            &[],
732            files,
733        )
734    }
735
736    /// Build the module graph with explicit runtime and test reachability roots.
737    fn build_with_reachability_roots(
738        resolved_modules: &[ResolvedModule],
739        entry_points: &[EntryPoint],
740        runtime_entry_points: &[EntryPoint],
741        test_entry_points: &[EntryPoint],
742        files: &[DiscoveredFile],
743    ) -> Self {
744        Self::build_with_reachability_roots_and_replacements(
745            resolved_modules,
746            &[],
747            entry_points,
748            runtime_entry_points,
749            test_entry_points,
750            files,
751        )
752    }
753
754    /// Build the module graph with root-specific test-time module replacements.
755    pub fn build_with_reachability_roots_and_replacements(
756        resolved_modules: &[ResolvedModule],
757        replaced_module_targets: &[ResolvedReplacedModuleTarget],
758        entry_points: &[EntryPoint],
759        runtime_entry_points: &[EntryPoint],
760        test_entry_points: &[EntryPoint],
761        files: &[DiscoveredFile],
762    ) -> Self {
763        Self::build_with_declaration_seeding(
764            resolved_modules,
765            replaced_module_targets,
766            &ReachabilityRoots {
767                all: entry_points,
768                runtime: runtime_entry_points,
769                test: test_entry_points,
770                consumer_checked: &FxHashSet::default(),
771            },
772            files,
773            &FxHashSet::default(),
774        )
775    }
776
777    /// Build the module graph like
778    /// [`Self::build_with_reachability_roots_and_replacements`], except that
779    /// the declaration files in `unseeded_declaration_files` are not seeded as
780    /// entry points.
781    ///
782    /// Every other declaration file is seeded so ambient declarations and
783    /// their `typeof import()` references stay alive. The caller names the
784    /// orphan module declaration files: a module declaration file that nothing
785    /// points to adds nothing to the global scope, so it must be reachable
786    /// through an import to stay used.
787    pub fn build_with_declaration_seeding(
788        resolved_modules: &[ResolvedModule],
789        replaced_module_targets: &[ResolvedReplacedModuleTarget],
790        roots: &ReachabilityRoots<'_>,
791        files: &[DiscoveredFile],
792        unseeded_declaration_files: &FxHashSet<FileId>,
793    ) -> Self {
794        let ReachabilityRoots {
795            all: entry_points,
796            runtime: runtime_entry_points,
797            test: test_entry_points,
798            consumer_checked,
799        } = *roots;
800        let _span = tracing::info_span!("build_graph").entered();
801
802        let module_count = files.len();
803
804        let max_file_id = files
805            .iter()
806            .map(|f| f.id.0 as usize)
807            .max()
808            .map_or(0, |m| m + 1);
809        let total_capacity = max_file_id.max(module_count);
810
811        let path_to_id: FxHashMap<&Path, FileId> =
812            files.iter().map(|f| (f.path.as_path(), f.id)).collect();
813
814        let module_by_id: FxHashMap<FileId, &ResolvedModule> =
815            resolved_modules.iter().map(|m| (m.file_id, m)).collect();
816
817        let mut entry_point_ids = Self::resolve_entry_point_ids(entry_points, &path_to_id);
818        let runtime_entry_point_ids =
819            Self::resolve_entry_point_ids(runtime_entry_points, &path_to_id);
820        let test_entry_point_ids = Self::resolve_entry_point_ids(test_entry_points, &path_to_id);
821
822        for file in files {
823            if is_declaration_file_path(&file.path)
824                && !unseeded_declaration_files.contains(&file.id)
825            {
826                entry_point_ids.insert(file.id);
827            }
828        }
829
830        let (mut graph, namespace_features) = Self::populate_edges(&build::PopulateEdgesInput {
831            files,
832            module_by_id: &module_by_id,
833            entry_point_ids: &entry_point_ids,
834            runtime_entry_point_ids: &runtime_entry_point_ids,
835            test_entry_point_ids: &test_entry_point_ids,
836            module_count,
837            total_capacity,
838        });
839        graph.effective_exports = effective_exports::EffectiveExportIndex::build(resolved_modules);
840
841        let test_reachability_plan = reachability::TestReachabilityPlan::new(
842            &test_entry_point_ids,
843            replaced_module_targets,
844            total_capacity,
845        );
846
847        let mut reference_paths =
848            ReferencePathInterner::new(test_reachability_plan.requires_reference_provenance());
849        let whole_module_targets =
850            graph.populate_references(&module_by_id, &entry_point_ids, &mut reference_paths);
851        // Entry-point reachability depends on edges alone, so it is available
852        // here and is reused verbatim by `mark_reachable` below. The exposed
853        // namespace closure needs it to stay off modules the report already
854        // calls unused files.
855        let entry_reachable = graph.collect_reachable(&entry_point_ids, total_capacity);
856        let exposed_namespace_targets = graph.collect_exposed_namespace_targets(
857            &whole_module_targets,
858            &entry_reachable,
859            &module_by_id,
860        );
861
862        if namespace_features.has_aliases || namespace_features.has_re_exports {
863            propagate_namespace_references(
864                &mut graph,
865                &module_by_id,
866                namespace_features,
867                &exposed_namespace_targets,
868                &mut reference_paths,
869            );
870        }
871
872        graph.mark_reachable(
873            &entry_reachable,
874            &entry_point_ids,
875            &runtime_entry_point_ids,
876            test_reachability_plan,
877            total_capacity,
878        );
879
880        graph.re_export_cycles = graph.resolve_re_export_chains(
881            &module_by_id,
882            &exposed_namespace_targets,
883            consumer_checked,
884            &mut reference_paths,
885        );
886        let finalized_paths = reference_paths.finalize(&mut graph.modules);
887        graph.reference_paths = finalized_paths.paths;
888        graph.reference_routes = finalized_paths.routes;
889
890        graph
891    }
892
893    /// Total number of modules.
894    #[must_use]
895    pub const fn module_count(&self) -> usize {
896        self.modules.len()
897    }
898
899    /// Total number of edges.
900    #[must_use]
901    pub const fn edge_count(&self) -> usize {
902        self.edges.len()
903    }
904
905    /// Return whether any test-root traversal reaches `file_id`.
906    #[must_use]
907    pub fn is_test_reachable(&self, file_id: FileId) -> bool {
908        self.modules
909            .get(file_id.0 as usize)
910            .is_some_and(ModuleNode::is_test_reachable)
911    }
912
913    /// Return whether one test-root traversal covers the export reference at
914    /// `reference_index` on `export`.
915    ///
916    /// Coverage requires one profile that reaches the referencing file and
917    /// every target hop. ESM hops also require that profile not to replace the
918    /// hop target; CommonJS hops remain active because Vitest replacement mocks
919    /// do not intercept `require()`.
920    ///
921    /// Only a value reference can give coverage. A type reference never runs
922    /// the export, so it never gives coverage. This includes `import type` and
923    /// a plain import that the test uses only in type positions.
924    #[must_use]
925    fn is_test_reference_covered(&self, export: &ExportSymbol, reference_index: usize) -> bool {
926        let Some(reference) = export.references.get(reference_index) else {
927            return false;
928        };
929        if reference.namespace != ExportNamespace::Value {
930            return false;
931        }
932        if self.test_reachability_index.profile_count == 0 {
933            return self.is_test_reachable(reference.from_file);
934        }
935
936        let Some(path) = export.reference_path(reference_index) else {
937            return false;
938        };
939
940        self.test_reachability_index.covers_reference_path(
941            reference.from_file,
942            path,
943            &self.reference_paths,
944            &self.reference_routes,
945        )
946    }
947
948    /// Return whether any reference on `export` is covered by a test-root
949    /// traversal.
950    #[must_use]
951    pub fn is_any_test_reference_covered(&self, export: &ExportSymbol) -> bool {
952        (0..export.references.len())
953            .any(|reference_index| self.is_test_reference_covered(export, reference_index))
954    }
955
956    #[cfg(test)]
957    fn reference_path_hops(
958        &self,
959        export: &ExportSymbol,
960        reference_index: usize,
961    ) -> Vec<(FileId, ModuleLoadMechanism)> {
962        let mut hops = Vec::new();
963        let mut next = export.reference_path(reference_index);
964        while let Some(path_id) = next {
965            let Some(node) = self.reference_paths.get(path_id.index()) else {
966                return Vec::new();
967            };
968            next = node.parent();
969            match *node {
970                ReferencePathNode::Hop {
971                    target, mechanism, ..
972                } => hops.push((target, mechanism)),
973                ReferencePathNode::Route {
974                    graph,
975                    start,
976                    terminal,
977                    start_mechanism,
978                    ..
979                } => hops.extend(self.reference_routes.canonical_hops(
980                    graph,
981                    start,
982                    terminal,
983                    start_mechanism,
984                )),
985            }
986        }
987        hops
988    }
989
990    /// Rebuild the `namespace_imported` bitset from the edge set.
991    ///
992    /// `namespace_imported` is `#[serde(skip)]`, so a graph loaded from the
993    /// persisted cache (`crate::cache`) arrives with an empty default bitset.
994    /// This restores it by replicating the EXACT insertion rule from
995    /// `build.rs`: a target `FileId` is namespace-imported iff some edge to it
996    /// carries an `ImportedName::Namespace` symbol. Both build-time insertion
997    /// sites (static / dynamic `import * as ns` in `collect_import_edge`, and
998    /// glob dynamic-import patterns in `collect_edges_for_module`) push a
999    /// `Namespace` symbol onto the target's edge, so iterating the persisted
1000    /// edges and checking for a `Namespace` symbol reproduces the original
1001    /// bitset bit-for-bit. The capacity matches `build.rs`'s
1002    /// `max_file_id.max(module_count)`, which equals `modules.len()` under the
1003    /// dense path-sorted FileId invariant.
1004    pub(crate) fn reconstruct_namespace_imported(&mut self) {
1005        let capacity = self
1006            .edges
1007            .iter()
1008            .map(|edge| edge.target.0 as usize + 1)
1009            .max()
1010            .unwrap_or(0)
1011            .max(self.modules.len());
1012        let mut bitset = FixedBitSet::with_capacity(capacity);
1013        for edge in &self.edges {
1014            if edge
1015                .symbols
1016                .iter()
1017                .any(|sym| matches!(sym.imported_name, ImportedName::Namespace))
1018            {
1019                let idx = edge.target.0 as usize;
1020                if idx < capacity {
1021                    bitset.insert(idx);
1022                }
1023            }
1024        }
1025        self.namespace_imported = bitset;
1026    }
1027
1028    /// Resolve the effective declaration exported under `name` in one namespace.
1029    ///
1030    /// This is the canonical graph contract for direct exports and every named
1031    /// or star re-export path. Missing and ambiguous bindings are explicit so
1032    /// consumers cannot accidentally credit an arbitrary source declaration.
1033    #[must_use]
1034    pub fn resolve_export(
1035        &self,
1036        file_id: FileId,
1037        name: &str,
1038        namespace: ExportNamespace,
1039    ) -> EffectiveExportResolution {
1040        self.effective_exports.resolve(file_id, name, namespace)
1041    }
1042
1043    /// Whether two effective bindings denote the same declaration surface.
1044    ///
1045    /// TypeScript declaration merges occupy separate export slots while
1046    /// representing one symbol. Consumers that compare type and value lanes
1047    /// use this instead of raw binding equality so either half can carry the
1048    /// reference credit for the merged declaration.
1049    #[must_use]
1050    pub fn effective_bindings_share_declaration_group(
1051        &self,
1052        left: EffectiveExportBinding,
1053        right: EffectiveExportBinding,
1054    ) -> bool {
1055        if left == right || left.origin_file() != right.origin_file() {
1056            return left == right;
1057        }
1058        let Some(right_slot) = right.origin_slot() else {
1059            return false;
1060        };
1061        self.effective_exports
1062            .declaration_group_slots(left)
1063            .contains(&right_slot)
1064    }
1065
1066    /// Resolve one exported name to its unique direct declaration.
1067    ///
1068    /// Missing and ambiguous bindings return `None`. Namespace-object exports
1069    /// are bindings in their own right rather than direct declarations, so
1070    /// they also have no declaration origin.
1071    #[must_use]
1072    pub fn resolve_export_origin(
1073        &self,
1074        file_id: FileId,
1075        name: &str,
1076        namespace: ExportNamespace,
1077    ) -> Option<EffectiveExportOrigin<'_>> {
1078        let EffectiveExportResolution::Unique(binding) =
1079            self.resolve_export(file_id, name, namespace)
1080        else {
1081            return None;
1082        };
1083        self.export_binding_origin(binding)
1084    }
1085
1086    /// Resolve one module surface to its canonical binding and reference-bearing
1087    /// graph export. Value and type namespaces are selected independently.
1088    #[must_use]
1089    pub fn effective_export_surface(
1090        &self,
1091        file_id: FileId,
1092        name: &str,
1093        namespace: ExportNamespace,
1094    ) -> Option<EffectiveExportSurface<'_>> {
1095        let EffectiveExportResolution::Unique(binding) =
1096            self.resolve_export(file_id, name, namespace)
1097        else {
1098            return None;
1099        };
1100        let module = self.modules.get(file_id.0 as usize)?;
1101        let exact_surface = module.exports.iter().find(|export| {
1102            export.name.matches_str(name)
1103                && match namespace {
1104                    ExportNamespace::Type => export.is_type_only,
1105                    ExportNamespace::Value => !export.is_type_only,
1106                }
1107        });
1108        let surface_export = exact_surface.or_else(|| {
1109            module
1110                .exports
1111                .iter()
1112                .find(|export| export.name.matches_str(name))
1113        });
1114        let origin = self.export_binding_origin(binding);
1115        let export = surface_export.or_else(|| origin.map(|o| o.export));
1116        Some(EffectiveExportSurface {
1117            binding,
1118            namespace,
1119            export,
1120            origin,
1121            local_export: surface_export.is_some(),
1122        })
1123    }
1124
1125    /// Local re-export specifier that owns one effective module surface.
1126    ///
1127    /// Direct declarations and star-only forwarded surfaces return `None`.
1128    /// Named and namespace re-exports return the namespace-compatible edge
1129    /// whose source resolves to the same canonical binding.
1130    #[must_use]
1131    pub fn effective_export_surface_re_export(
1132        &self,
1133        file_id: FileId,
1134        name: &str,
1135        namespace: ExportNamespace,
1136    ) -> Option<&ReExportEdge> {
1137        let EffectiveExportResolution::Unique(binding) =
1138            self.resolve_export(file_id, name, namespace)
1139        else {
1140            return None;
1141        };
1142        self.modules
1143            .get(file_id.0 as usize)?
1144            .re_exports
1145            .iter()
1146            .find(|re_export| {
1147                re_export.exported_name == name
1148                    && (namespace == ExportNamespace::Type || !re_export.is_type_only)
1149                    && if re_export.imported_name == "*" {
1150                        binding.namespace_source() == Some(re_export.source_file)
1151                    } else {
1152                        self.resolve_export(
1153                            re_export.source_file,
1154                            &re_export.imported_name,
1155                            namespace,
1156                        ) == EffectiveExportResolution::Unique(binding)
1157                    }
1158            })
1159    }
1160
1161    /// References that reach one exact module export surface.
1162    ///
1163    /// Star-only surfaces share their declaration with other barrels, so their
1164    /// origin references are filtered by recorded provenance instead of being
1165    /// borrowed wholesale from the declaration.
1166    #[must_use]
1167    pub fn effective_export_surface_references(
1168        &self,
1169        file_id: FileId,
1170        name: &str,
1171        namespace: ExportNamespace,
1172    ) -> Vec<&SymbolReference> {
1173        let Some(surface) = self.effective_export_surface(file_id, name, namespace) else {
1174            return Vec::new();
1175        };
1176        let Some(export) = surface.export() else {
1177            return Vec::new();
1178        };
1179        if surface.local_export
1180            || surface
1181                .origin()
1182                .is_none_or(|origin| origin.file_id() == file_id)
1183        {
1184            return export.references_in(namespace).collect();
1185        }
1186        let mut exposed: FxHashMap<FileId, FxHashSet<String>> = FxHashMap::default();
1187        exposed.entry(file_id).or_default().insert(name.to_string());
1188        for route in self.effective_re_export_routes(file_id, name, namespace) {
1189            exposed
1190                .entry(route.barrel_file())
1191                .or_default()
1192                .insert(route.exported_name().to_string());
1193        }
1194        export
1195            .references
1196            .iter()
1197            .filter(|reference| {
1198                reference.namespace == namespace
1199                    && self.reference_reaches_surface(reference, &exposed, namespace)
1200            })
1201            .collect()
1202    }
1203
1204    fn reference_reaches_surface(
1205        &self,
1206        reference: &SymbolReference,
1207        exposed: &FxHashMap<FileId, FxHashSet<String>>,
1208        namespace: ExportNamespace,
1209    ) -> bool {
1210        if reference.kind == ReferenceKind::ReExport && exposed.contains_key(&reference.from_file) {
1211            return true;
1212        }
1213        self.outgoing_symbol_edges(reference.from_file)
1214            .any(|(target, symbols)| {
1215                let Some(names) = exposed.get(&target) else {
1216                    return false;
1217                };
1218                symbols.iter().any(|symbol| {
1219                    symbol.import_span == reference.import_span
1220                        && (namespace == ExportNamespace::Type
1221                            || !symbol.is_type_only
1222                            || symbol.is_value_bearing_ambient_star())
1223                        && match &symbol.imported_name {
1224                            ImportedName::Named(imported) => names.contains(imported.as_str()),
1225                            ImportedName::Default => names.contains("default"),
1226                            ImportedName::Namespace => true,
1227                            ImportedName::SideEffect => false,
1228                        }
1229                })
1230            })
1231    }
1232
1233    /// Resolve a unique binding to its direct declaration, when it has one.
1234    #[must_use]
1235    pub fn export_binding_origin(
1236        &self,
1237        binding: EffectiveExportBinding,
1238    ) -> Option<EffectiveExportOrigin<'_>> {
1239        let origin_file = binding.origin_file();
1240        let export = self
1241            .modules
1242            .get(origin_file.0 as usize)?
1243            .exports
1244            .get(binding.origin_slot()?)?;
1245        Some(EffectiveExportOrigin {
1246            file_id: origin_file,
1247            export,
1248        })
1249    }
1250
1251    /// Unique bindings exposed by a module in one namespace.
1252    ///
1253    /// Multiple names that resolve to the same declaration are deduplicated;
1254    /// missing and ambiguous exports are excluded.
1255    #[must_use]
1256    pub fn unique_export_bindings(
1257        &self,
1258        file_id: FileId,
1259        namespace: ExportNamespace,
1260    ) -> FxHashSet<EffectiveExportBinding> {
1261        self.effective_exports.unique_bindings(file_id, namespace)
1262    }
1263
1264    /// Whether `importer` connects to `source` as an origin of `name`.
1265    ///
1266    /// Any direct import connects the two modules for duplicate-export
1267    /// grouping, even when it imports a different symbol. A re-export-only edge
1268    /// connects them only when it contributes this binding, including each
1269    /// contributor to an ambiguous star export and excluding star bindings
1270    /// shadowed by an explicit export.
1271    #[must_use]
1272    pub fn importer_connects_export_origin(
1273        &self,
1274        importer: FileId,
1275        source: FileId,
1276        name: &str,
1277        namespace: ExportNamespace,
1278    ) -> bool {
1279        let Some(importer_module) = self.modules.get(importer.0 as usize) else {
1280            return false;
1281        };
1282        let re_export_count = importer_module
1283            .re_exports
1284            .iter()
1285            .filter(|re_export| re_export.source_file == source)
1286            .count();
1287        if self.edges[importer_module.edge_range.clone()]
1288            .iter()
1289            .any(|edge| edge.target == source && edge.symbols.len() > re_export_count)
1290        {
1291            return true;
1292        }
1293
1294        importer_module.re_exports.iter().any(|re_export| {
1295            if re_export.source_file != source
1296                || (namespace == ExportNamespace::Value && re_export.is_type_only)
1297            {
1298                return false;
1299            }
1300            let exported_name = if re_export.imported_name == "*" {
1301                if re_export.exported_name != "*" || name == "default" {
1302                    return false;
1303                }
1304                name
1305            } else {
1306                if re_export.imported_name != name {
1307                    return false;
1308                }
1309                &re_export.exported_name
1310            };
1311            self.effective_exports.contributes_through(
1312                importer,
1313                exported_name,
1314                source,
1315                name,
1316                namespace,
1317            )
1318        })
1319    }
1320
1321    /// Check if any importer uses `import * as ns` for this module.
1322    /// Uses precomputed bitset, O(1) lookup.
1323    #[must_use]
1324    pub fn has_namespace_import(&self, file_id: FileId) -> bool {
1325        // `FixedBitSet::contains` is false for an index past the end.
1326        self.namespace_imported.contains(file_id.0 as usize)
1327    }
1328
1329    /// Get the target `FileId`s of all outgoing edges for a module.
1330    #[must_use]
1331    pub fn edges_for(&self, file_id: FileId) -> Vec<FileId> {
1332        let idx = file_id.0 as usize;
1333        if idx >= self.modules.len() {
1334            return Vec::new();
1335        }
1336        let range = &self.modules[idx].edge_range;
1337        self.edges[range.clone()].iter().map(|e| e.target).collect()
1338    }
1339
1340    /// Iterate the outgoing edges of `file_id` with full per-symbol data.
1341    ///
1342    /// `fallow trace` needs the raw `ImportedSymbol` set on each edge in
1343    /// both directions, which the flattened summary structs cannot express.
1344    /// Returns an empty iterator for out-of-range file ids.
1345    pub fn outgoing_symbol_edges(
1346        &self,
1347        file_id: FileId,
1348    ) -> impl Iterator<Item = (FileId, &[ImportedSymbol])> + '_ {
1349        let idx = file_id.0 as usize;
1350        let range = if idx < self.modules.len() {
1351            self.modules[idx].edge_range.clone()
1352        } else {
1353            0..0
1354        };
1355        self.edges[range]
1356            .iter()
1357            .map(|edge| (edge.target, edge.symbols.as_slice()))
1358    }
1359
1360    /// The importer `FileId`s that directly import `target` (reverse-dep view).
1361    ///
1362    /// Returns an empty slice when `target` is out of range.
1363    #[must_use]
1364    pub fn importers_of(&self, target: FileId) -> &[FileId] {
1365        self.reverse_deps
1366            .get(target.0 as usize)
1367            .map_or(&[], Vec::as_slice)
1368    }
1369
1370    /// Summarize files that directly import `target`.
1371    ///
1372    /// Uses existing reverse dependency and edge indexes. Returns an empty
1373    /// list when the target is out of range or has no importers.
1374    #[must_use]
1375    pub fn direct_importer_summaries(&self, target: FileId) -> Vec<DirectImporterSummary> {
1376        let Some(importers) = self.reverse_deps.get(target.0 as usize) else {
1377            return Vec::new();
1378        };
1379
1380        let mut summaries = Vec::new();
1381        for &source in importers {
1382            let idx = source.0 as usize;
1383            let Some(source_node) = self.modules.get(idx) else {
1384                continue;
1385            };
1386            let mut symbols = Vec::new();
1387            for edge in &self.edges[source_node.edge_range.clone()] {
1388                if edge.target != target {
1389                    continue;
1390                }
1391                symbols.extend(edge.symbols.iter().map(|symbol| ImportedSymbolSummary {
1392                    imported: imported_name_label(&symbol.imported_name),
1393                    local: symbol.local_name.clone(),
1394                    type_only: symbol.is_type_only,
1395                }));
1396            }
1397            symbols.sort_by(|a, b| {
1398                a.imported
1399                    .cmp(&b.imported)
1400                    .then_with(|| a.local.cmp(&b.local))
1401                    .then_with(|| a.type_only.cmp(&b.type_only))
1402            });
1403            symbols.dedup();
1404            summaries.push(DirectImporterSummary { source, symbols });
1405        }
1406        summaries.sort_by_key(|summary| summary.source.0);
1407        summaries
1408    }
1409
1410    /// Iterate the outgoing edges of `file_id` that run their target, with
1411    /// the data the boundary detector and the security scans need in a single
1412    /// pass.
1413    ///
1414    /// Only symbols that load the target count (see
1415    /// [`ImportedSymbol::loads_target`]). A `require.resolve('./x')` path
1416    /// reference and an asset loader request (`raw-loader!./x.js`) keep the
1417    /// target in use but do not run it, so they cannot cross an architecture
1418    /// boundary or carry code into a bundle. An edge without such a symbol is
1419    /// skipped.
1420    ///
1421    /// When `featureB` has both `import type { Foo } from './x'` and
1422    /// `import { bar } from './x'`, fallow groups them into ONE edge with the
1423    /// type-only symbol first and the value symbol second. The summary
1424    /// anchors on the value symbol, so findings anchor on the runtime import
1425    /// line; otherwise a `// fallow-ignore-next-line` above the type-only line
1426    /// would silently suppress the real violation.
1427    ///
1428    /// Returns an empty iterator for out-of-range file ids.
1429    pub fn outgoing_edge_summaries(
1430        &self,
1431        file_id: FileId,
1432    ) -> impl Iterator<Item = OutgoingEdgeSummary<'_>> + '_ {
1433        self.outgoing_symbol_edges(file_id)
1434            .filter_map(|(target, symbols)| {
1435                let mut loading = symbols.iter().filter(|s| s.loads_target()).peekable();
1436                let first = loading.peek().copied()?;
1437                let value = loading.find(|s| !s.is_type_only);
1438                Some(OutgoingEdgeSummary {
1439                    target,
1440                    all_type_only: value.is_none(),
1441                    span_start: Some(value.unwrap_or(first).import_span.start),
1442                    symbols,
1443                })
1444            })
1445    }
1446
1447    /// Iterate outgoing edges with the symbols of each edge.
1448    ///
1449    /// One edge holds every import from `file_id` to one target, so
1450    /// `import type { Y } from './y'` and `import { y } from './y'` share an
1451    /// edge. Use this method when a consumer must suppress or report each
1452    /// import statement on its own line; [`Self::outgoing_edge_summaries`]
1453    /// gives only one span per edge. A re-export or a dynamic import pattern
1454    /// has an empty `import_span`.
1455    ///
1456    /// Returns an empty iterator for out-of-range file ids.
1457    pub fn outgoing_edge_symbols(
1458        &self,
1459        file_id: FileId,
1460    ) -> impl Iterator<Item = (FileId, &[ImportedSymbol])> + '_ {
1461        let idx = file_id.0 as usize;
1462        let range = if idx < self.modules.len() {
1463            self.modules[idx].edge_range.clone()
1464        } else {
1465            0..0
1466        };
1467        self.edges[range]
1468            .iter()
1469            .map(|edge| (edge.target, edge.symbols.as_slice()))
1470    }
1471
1472    /// Like [`Self::outgoing_edge_summaries`] (only edges that run their
1473    /// target, and only their loading symbols) but additionally reports, as a
1474    /// fourth boolean, whether EVERY non-type-only symbol on the edge has an
1475    /// `import_span` start in `excluded_span_starts` (`all_client_only`). The
1476    /// security `client-server-leak` BFS passes the `next/dynamic ssr:false`
1477    /// dynamic-import span starts so it can skip an edge reached ONLY through the
1478    /// client-only escape hatch. An edge with no non-type-only symbols, or with at
1479    /// least one non-type-only symbol whose span is not excluded, reports `false`
1480    /// (so a target also reached via a real static import stays in the cone).
1481    ///
1482    /// Unlike [`Self::outgoing_edge_summaries`], a named symbol also counts as
1483    /// type-only when the name resolves on the target to a type declaration and
1484    /// to no value declaration (`import { Props } from "./x"` where `x` has
1485    /// `export interface Props`). The build erases such an import, so it cannot
1486    /// leak into a client bundle. Default, namespace, and side-effect imports,
1487    /// and names that do not resolve to a type, stay live.
1488    ///
1489    /// Returns an empty iterator for out-of-range file ids.
1490    pub fn outgoing_edge_summaries_with_exclusions<'a>(
1491        &'a self,
1492        file_id: FileId,
1493        excluded_span_starts: &'a FxHashSet<u32>,
1494    ) -> impl Iterator<Item = (FileId, bool, Option<u32>, bool)> + 'a {
1495        let idx = file_id.0 as usize;
1496        let range = if idx < self.modules.len() {
1497            self.modules[idx].edge_range.clone()
1498        } else {
1499            0..0
1500        };
1501        self.edges[range].iter().filter_map(move |edge| {
1502            let loading = || edge.symbols.iter().filter(|s| s.loads_target());
1503            let first = loading().next()?;
1504            let erased = |s: &&ImportedSymbol| {
1505                s.is_type_only || self.names_only_type_exports(edge.target, &s.imported_name)
1506            };
1507            let all_type_only = loading().all(|s| erased(&s));
1508            let span = loading()
1509                .find(|s| !erased(s))
1510                .unwrap_or(first)
1511                .import_span
1512                .start;
1513            // `all_client_only`: there is at least one non-type-only symbol and
1514            // every such symbol's import span is in the excluded set. A
1515            // non-excluded value symbol keeps the edge live.
1516            let mut value_symbols = loading().filter(|s| !erased(s)).peekable();
1517            let all_client_only = value_symbols.peek().is_some()
1518                && value_symbols.all(|s| excluded_span_starts.contains(&s.import_span.start));
1519            Some((edge.target, all_type_only, Some(span), all_client_only))
1520        })
1521    }
1522}
1523
1524impl ModuleGraph {
1525    /// Return `true` when `name` is a named import that resolves on `target`
1526    /// to a type declaration and to no value declaration. Default, namespace,
1527    /// and side-effect imports return `false`, and so does a name that the
1528    /// graph cannot resolve in the type namespace.
1529    fn names_only_type_exports(&self, target: FileId, name: &ImportedName) -> bool {
1530        let ImportedName::Named(name) = name else {
1531            return false;
1532        };
1533        matches!(
1534            self.resolve_export(target, name, ExportNamespace::Value),
1535            EffectiveExportResolution::Missing
1536        ) && matches!(
1537            self.resolve_export(target, name, ExportNamespace::Type),
1538            EffectiveExportResolution::Unique(_)
1539        )
1540    }
1541}
1542
1543fn imported_name_label(name: &ImportedName) -> String {
1544    match name {
1545        ImportedName::Named(name) => name.clone(),
1546        ImportedName::Default => "default".to_string(),
1547        ImportedName::Namespace => "*".to_string(),
1548        ImportedName::SideEffect => "side-effect".to_string(),
1549    }
1550}
1551
1552#[cfg(test)]
1553mod tests {
1554    use super::*;
1555    use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
1556    use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource, FileId};
1557    use fallow_types::extract::{ExportName, ImportInfo, ImportedName, VisibilityTag};
1558    use std::path::PathBuf;
1559
1560    fn build_simple_graph() -> ModuleGraph {
1561        let files = vec![
1562            DiscoveredFile {
1563                id: FileId(0),
1564                path: PathBuf::from("/project/src/entry.ts"),
1565                size_bytes: 100,
1566            },
1567            DiscoveredFile {
1568                id: FileId(1),
1569                path: PathBuf::from("/project/src/utils.ts"),
1570                size_bytes: 50,
1571            },
1572        ];
1573
1574        let entry_points = vec![EntryPoint {
1575            path: PathBuf::from("/project/src/entry.ts"),
1576            source: EntryPointSource::PackageJsonMain,
1577        }];
1578
1579        let resolved_modules = vec![
1580            ResolvedModule {
1581                file_id: FileId(0),
1582                path: PathBuf::from("/project/src/entry.ts"),
1583                resolved_imports: vec![ResolvedImport {
1584                    info: ImportInfo {
1585                        source: "./utils".to_string(),
1586                        imported_name: ImportedName::Named("foo".to_string()),
1587                        local_name: "foo".to_string(),
1588                        is_type_only: false,
1589                        is_type_only_star: false,
1590                        from_style: false,
1591                        span: oxc_span::Span::new(0, 10),
1592                        source_span: oxc_span::Span::default(),
1593                    },
1594                    target: ResolveResult::InternalModule(FileId(1)),
1595                }],
1596                ..Default::default()
1597            },
1598            ResolvedModule {
1599                file_id: FileId(1),
1600                path: PathBuf::from("/project/src/utils.ts"),
1601                exports: vec![
1602                    fallow_types::extract::ExportInfo {
1603                        name: ExportName::Named("foo".to_string()),
1604                        local_name: Some("foo".to_string()),
1605                        is_type_only: false,
1606                        visibility: VisibilityTag::None,
1607                        expected_unused_reason: None,
1608                        span: oxc_span::Span::new(0, 20),
1609                        members: vec![],
1610                        is_side_effect_used: false,
1611                        super_class: None,
1612                        deprecated: false,
1613                        deprecated_reason: None,
1614                    },
1615                    fallow_types::extract::ExportInfo {
1616                        name: ExportName::Named("bar".to_string()),
1617                        local_name: Some("bar".to_string()),
1618                        is_type_only: false,
1619                        visibility: VisibilityTag::None,
1620                        expected_unused_reason: None,
1621                        span: oxc_span::Span::new(25, 45),
1622                        members: vec![],
1623                        is_side_effect_used: false,
1624                        super_class: None,
1625                        deprecated: false,
1626                        deprecated_reason: None,
1627                    },
1628                ]
1629                .into(),
1630                ..Default::default()
1631            },
1632        ];
1633
1634        ModuleGraph::build(&resolved_modules, &entry_points, &files)
1635    }
1636
1637    fn declaration_seeding_graph(unseeded: &FxHashSet<FileId>) -> ModuleGraph {
1638        let paths = [
1639            "/project/types/ambient.d.ts",
1640            "/project/types/orphan.d.ts",
1641            "/project/types/helper.ts",
1642        ];
1643        let files: Vec<DiscoveredFile> = paths
1644            .iter()
1645            .zip(0u32..)
1646            .map(|(path, id)| DiscoveredFile {
1647                id: FileId(id),
1648                path: PathBuf::from(path),
1649                size_bytes: 10,
1650            })
1651            .collect();
1652        let resolved_modules = vec![
1653            ResolvedModule {
1654                file_id: FileId(0),
1655                path: files[0].path.clone(),
1656                ..Default::default()
1657            },
1658            ResolvedModule {
1659                file_id: FileId(1),
1660                path: files[1].path.clone(),
1661                resolved_imports: vec![ResolvedImport {
1662                    info: ImportInfo {
1663                        source: "./helper".to_string(),
1664                        imported_name: ImportedName::Named("Helper".to_string()),
1665                        local_name: "Helper".to_string(),
1666                        is_type_only: true,
1667                        is_type_only_star: false,
1668                        from_style: false,
1669                        span: oxc_span::Span::new(0, 10),
1670                        source_span: oxc_span::Span::default(),
1671                    },
1672                    target: ResolveResult::InternalModule(FileId(2)),
1673                }],
1674                ..Default::default()
1675            },
1676            ResolvedModule {
1677                file_id: FileId(2),
1678                path: files[2].path.clone(),
1679                ..Default::default()
1680            },
1681        ];
1682        ModuleGraph::build_with_declaration_seeding(
1683            &resolved_modules,
1684            &[],
1685            &ReachabilityRoots {
1686                all: &[],
1687                runtime: &[],
1688                test: &[],
1689                consumer_checked: &FxHashSet::default(),
1690            },
1691            &files,
1692            unseeded,
1693        )
1694    }
1695
1696    #[test]
1697    fn every_declaration_file_is_seeded_by_default() {
1698        let graph = declaration_seeding_graph(&FxHashSet::default());
1699        assert!(graph.modules[0].is_entry_point());
1700        assert!(graph.modules[1].is_entry_point());
1701        assert!(graph.modules[2].is_reachable());
1702    }
1703
1704    #[test]
1705    fn unseeded_declaration_file_no_longer_keeps_its_imports_reachable() {
1706        let unseeded: FxHashSet<FileId> = std::iter::once(FileId(1)).collect();
1707        let graph = declaration_seeding_graph(&unseeded);
1708        assert!(graph.modules[0].is_entry_point());
1709        assert!(!graph.modules[1].is_entry_point());
1710        assert!(!graph.modules[1].is_reachable());
1711        assert!(!graph.modules[2].is_reachable());
1712    }
1713
1714    #[test]
1715    fn graph_module_count() {
1716        let graph = build_simple_graph();
1717        assert_eq!(graph.module_count(), 2);
1718    }
1719
1720    #[test]
1721    fn graph_edge_count() {
1722        let graph = build_simple_graph();
1723        assert_eq!(graph.edge_count(), 1);
1724    }
1725
1726    #[test]
1727    fn graph_entry_point_is_reachable() {
1728        let graph = build_simple_graph();
1729        assert!(graph.modules[0].is_entry_point());
1730        assert!(graph.modules[0].is_reachable());
1731    }
1732
1733    #[test]
1734    fn graph_imported_module_is_reachable() {
1735        let graph = build_simple_graph();
1736        assert!(!graph.modules[1].is_entry_point());
1737        assert!(graph.modules[1].is_reachable());
1738    }
1739
1740    #[test]
1741    #[expect(
1742        clippy::too_many_lines,
1743        reason = "this test fixture exercises four reachability roles end-to-end; splitting it \
1744                  would obscure the cross-role assertions"
1745    )]
1746    fn graph_distinguishes_runtime_test_and_support_reachability() {
1747        let files = vec![
1748            DiscoveredFile {
1749                id: FileId(0),
1750                path: PathBuf::from("/project/src/main.ts"),
1751                size_bytes: 100,
1752            },
1753            DiscoveredFile {
1754                id: FileId(1),
1755                path: PathBuf::from("/project/src/runtime-only.ts"),
1756                size_bytes: 50,
1757            },
1758            DiscoveredFile {
1759                id: FileId(2),
1760                path: PathBuf::from("/project/tests/app.test.ts"),
1761                size_bytes: 50,
1762            },
1763            DiscoveredFile {
1764                id: FileId(3),
1765                path: PathBuf::from("/project/tests/setup.ts"),
1766                size_bytes: 50,
1767            },
1768            DiscoveredFile {
1769                id: FileId(4),
1770                path: PathBuf::from("/project/src/covered.ts"),
1771                size_bytes: 50,
1772            },
1773        ];
1774
1775        let all_entry_points = vec![
1776            EntryPoint {
1777                path: PathBuf::from("/project/src/main.ts"),
1778                source: EntryPointSource::PackageJsonMain,
1779            },
1780            EntryPoint {
1781                path: PathBuf::from("/project/tests/app.test.ts"),
1782                source: EntryPointSource::TestFile,
1783            },
1784            EntryPoint {
1785                path: PathBuf::from("/project/tests/setup.ts"),
1786                source: EntryPointSource::Plugin {
1787                    name: "vitest".to_string(),
1788                },
1789            },
1790        ];
1791        let runtime_entry_points = vec![EntryPoint {
1792            path: PathBuf::from("/project/src/main.ts"),
1793            source: EntryPointSource::PackageJsonMain,
1794        }];
1795        let test_entry_points = vec![EntryPoint {
1796            path: PathBuf::from("/project/tests/app.test.ts"),
1797            source: EntryPointSource::TestFile,
1798        }];
1799
1800        let resolved_modules = vec![
1801            ResolvedModule {
1802                file_id: FileId(0),
1803                path: PathBuf::from("/project/src/main.ts"),
1804                resolved_imports: vec![ResolvedImport {
1805                    info: ImportInfo {
1806                        source: "./runtime-only".to_string(),
1807                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
1808                        local_name: "runtimeOnly".to_string(),
1809                        is_type_only: false,
1810                        is_type_only_star: false,
1811                        from_style: false,
1812                        span: oxc_span::Span::new(0, 10),
1813                        source_span: oxc_span::Span::default(),
1814                    },
1815                    target: ResolveResult::InternalModule(FileId(1)),
1816                }],
1817                ..Default::default()
1818            },
1819            ResolvedModule {
1820                file_id: FileId(1),
1821                path: PathBuf::from("/project/src/runtime-only.ts"),
1822                exports: vec![fallow_types::extract::ExportInfo {
1823                    name: ExportName::Named("runtimeOnly".to_string()),
1824                    local_name: Some("runtimeOnly".to_string()),
1825                    is_type_only: false,
1826                    visibility: VisibilityTag::None,
1827                    expected_unused_reason: None,
1828                    span: oxc_span::Span::new(0, 20),
1829                    members: vec![],
1830                    is_side_effect_used: false,
1831                    super_class: None,
1832                    deprecated: false,
1833                    deprecated_reason: None,
1834                }]
1835                .into(),
1836                ..Default::default()
1837            },
1838            ResolvedModule {
1839                file_id: FileId(2),
1840                path: PathBuf::from("/project/tests/app.test.ts"),
1841                resolved_imports: vec![ResolvedImport {
1842                    info: ImportInfo {
1843                        source: "../src/covered".to_string(),
1844                        imported_name: ImportedName::Named("covered".to_string()),
1845                        local_name: "covered".to_string(),
1846                        is_type_only: false,
1847                        is_type_only_star: false,
1848                        from_style: false,
1849                        span: oxc_span::Span::new(0, 10),
1850                        source_span: oxc_span::Span::default(),
1851                    },
1852                    target: ResolveResult::InternalModule(FileId(4)),
1853                }],
1854                ..Default::default()
1855            },
1856            ResolvedModule {
1857                file_id: FileId(3),
1858                path: PathBuf::from("/project/tests/setup.ts"),
1859                resolved_imports: vec![ResolvedImport {
1860                    info: ImportInfo {
1861                        source: "../src/runtime-only".to_string(),
1862                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
1863                        local_name: "runtimeOnly".to_string(),
1864                        is_type_only: false,
1865                        is_type_only_star: false,
1866                        from_style: false,
1867                        span: oxc_span::Span::new(0, 10),
1868                        source_span: oxc_span::Span::default(),
1869                    },
1870                    target: ResolveResult::InternalModule(FileId(1)),
1871                }],
1872                ..Default::default()
1873            },
1874            ResolvedModule {
1875                file_id: FileId(4),
1876                path: PathBuf::from("/project/src/covered.ts"),
1877                exports: vec![fallow_types::extract::ExportInfo {
1878                    name: ExportName::Named("covered".to_string()),
1879                    local_name: Some("covered".to_string()),
1880                    is_type_only: false,
1881                    visibility: VisibilityTag::None,
1882                    expected_unused_reason: None,
1883                    span: oxc_span::Span::new(0, 20),
1884                    members: vec![],
1885                    is_side_effect_used: false,
1886                    super_class: None,
1887                    deprecated: false,
1888                    deprecated_reason: None,
1889                }]
1890                .into(),
1891                ..Default::default()
1892            },
1893        ];
1894
1895        let graph = ModuleGraph::build_with_reachability_roots(
1896            &resolved_modules,
1897            &all_entry_points,
1898            &runtime_entry_points,
1899            &test_entry_points,
1900            &files,
1901        );
1902
1903        assert!(graph.modules[1].is_reachable());
1904        assert!(graph.modules[1].is_runtime_reachable());
1905        assert!(
1906            !graph.modules[1].is_test_reachable(),
1907            "support roots should not make runtime-only modules test reachable"
1908        );
1909
1910        assert!(graph.modules[4].is_reachable());
1911        assert!(graph.modules[4].is_test_reachable());
1912        assert!(
1913            !graph.modules[4].is_runtime_reachable(),
1914            "test-only reachability should stay separate from runtime roots"
1915        );
1916    }
1917
1918    #[test]
1919    fn graph_export_has_reference() {
1920        let graph = build_simple_graph();
1921        let utils = &graph.modules[1];
1922        let foo_export = utils
1923            .exports
1924            .iter()
1925            .find(|e| e.name.to_string() == "foo")
1926            .unwrap();
1927        assert!(
1928            !foo_export.references.is_empty(),
1929            "foo should have references"
1930        );
1931    }
1932
1933    #[test]
1934    fn graph_unused_export_no_reference() {
1935        let graph = build_simple_graph();
1936        let utils = &graph.modules[1];
1937        let bar_export = utils
1938            .exports
1939            .iter()
1940            .find(|e| e.name.to_string() == "bar")
1941            .unwrap();
1942        assert!(
1943            bar_export.references.is_empty(),
1944            "bar should have no references"
1945        );
1946    }
1947
1948    #[test]
1949    fn graph_no_namespace_import() {
1950        let graph = build_simple_graph();
1951        assert!(!graph.has_namespace_import(FileId(0)));
1952        assert!(!graph.has_namespace_import(FileId(1)));
1953    }
1954
1955    #[test]
1956    fn graph_has_namespace_import() {
1957        let files = vec![
1958            DiscoveredFile {
1959                id: FileId(0),
1960                path: PathBuf::from("/project/entry.ts"),
1961                size_bytes: 100,
1962            },
1963            DiscoveredFile {
1964                id: FileId(1),
1965                path: PathBuf::from("/project/utils.ts"),
1966                size_bytes: 50,
1967            },
1968        ];
1969
1970        let entry_points = vec![EntryPoint {
1971            path: PathBuf::from("/project/entry.ts"),
1972            source: EntryPointSource::PackageJsonMain,
1973        }];
1974
1975        let resolved_modules = vec![
1976            ResolvedModule {
1977                file_id: FileId(0),
1978                path: PathBuf::from("/project/entry.ts"),
1979                resolved_imports: vec![ResolvedImport {
1980                    info: ImportInfo {
1981                        source: "./utils".to_string(),
1982                        imported_name: ImportedName::Namespace,
1983                        local_name: "utils".to_string(),
1984                        is_type_only: false,
1985                        is_type_only_star: false,
1986                        from_style: false,
1987                        span: oxc_span::Span::new(0, 10),
1988                        source_span: oxc_span::Span::default(),
1989                    },
1990                    target: ResolveResult::InternalModule(FileId(1)),
1991                }],
1992                ..Default::default()
1993            },
1994            ResolvedModule {
1995                file_id: FileId(1),
1996                path: PathBuf::from("/project/utils.ts"),
1997                exports: vec![fallow_types::extract::ExportInfo {
1998                    name: ExportName::Named("foo".to_string()),
1999                    local_name: Some("foo".to_string()),
2000                    is_type_only: false,
2001                    visibility: VisibilityTag::None,
2002                    expected_unused_reason: None,
2003                    span: oxc_span::Span::new(0, 20),
2004                    members: vec![],
2005                    is_side_effect_used: false,
2006                    super_class: None,
2007                    deprecated: false,
2008                    deprecated_reason: None,
2009                }]
2010                .into(),
2011                ..Default::default()
2012            },
2013        ];
2014
2015        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2016        assert!(
2017            graph.has_namespace_import(FileId(1)),
2018            "utils should have namespace import"
2019        );
2020    }
2021
2022    #[test]
2023    fn graph_has_namespace_import_out_of_bounds() {
2024        let graph = build_simple_graph();
2025        assert!(!graph.has_namespace_import(FileId(999)));
2026    }
2027
2028    /// The persisted graph cache skips `namespace_imported` and rebuilds it from
2029    /// the edge set on load. This asserts the reconstruction reproduces the
2030    /// fresh-built bitset BIT-FOR-BIT on a graph that exercises `import * as ns`,
2031    /// matching what `build.rs` records at build time.
2032    #[test]
2033    fn reconstruct_namespace_imported_matches_fresh_build() {
2034        let files = vec![
2035            DiscoveredFile {
2036                id: FileId(0),
2037                path: PathBuf::from("/project/entry.ts"),
2038                size_bytes: 100,
2039            },
2040            DiscoveredFile {
2041                id: FileId(1),
2042                path: PathBuf::from("/project/utils.ts"),
2043                size_bytes: 50,
2044            },
2045            DiscoveredFile {
2046                id: FileId(2),
2047                path: PathBuf::from("/project/named-only.ts"),
2048                size_bytes: 50,
2049            },
2050        ];
2051        let entry_points = vec![EntryPoint {
2052            path: PathBuf::from("/project/entry.ts"),
2053            source: EntryPointSource::PackageJsonMain,
2054        }];
2055        let resolved_modules = vec![
2056            ResolvedModule {
2057                file_id: FileId(0),
2058                path: PathBuf::from("/project/entry.ts"),
2059                resolved_imports: vec![
2060                    ResolvedImport {
2061                        info: ImportInfo {
2062                            source: "./utils".to_string(),
2063                            imported_name: ImportedName::Namespace,
2064                            local_name: "utils".to_string(),
2065                            is_type_only: false,
2066                            is_type_only_star: false,
2067                            from_style: false,
2068                            span: oxc_span::Span::new(0, 10),
2069                            source_span: oxc_span::Span::default(),
2070                        },
2071                        target: ResolveResult::InternalModule(FileId(1)),
2072                    },
2073                    ResolvedImport {
2074                        info: ImportInfo {
2075                            source: "./named-only".to_string(),
2076                            imported_name: ImportedName::Named("foo".to_string()),
2077                            local_name: "foo".to_string(),
2078                            is_type_only: false,
2079                            is_type_only_star: false,
2080                            from_style: false,
2081                            span: oxc_span::Span::new(11, 20),
2082                            source_span: oxc_span::Span::default(),
2083                        },
2084                        target: ResolveResult::InternalModule(FileId(2)),
2085                    },
2086                ],
2087                ..Default::default()
2088            },
2089            ResolvedModule {
2090                file_id: FileId(1),
2091                path: PathBuf::from("/project/utils.ts"),
2092                ..Default::default()
2093            },
2094            ResolvedModule {
2095                file_id: FileId(2),
2096                path: PathBuf::from("/project/named-only.ts"),
2097                exports: vec![fallow_types::extract::ExportInfo {
2098                    name: ExportName::Named("foo".to_string()),
2099                    local_name: Some("foo".to_string()),
2100                    is_type_only: false,
2101                    visibility: VisibilityTag::None,
2102                    expected_unused_reason: None,
2103                    span: oxc_span::Span::new(0, 20),
2104                    members: vec![],
2105                    is_side_effect_used: false,
2106                    super_class: None,
2107                    deprecated: false,
2108                    deprecated_reason: None,
2109                }]
2110                .into(),
2111                ..Default::default()
2112            },
2113        ];
2114
2115        let mut graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2116        let fresh = graph.namespace_imported.clone();
2117
2118        // Sanity: the namespace target is set, the named-only target is not.
2119        assert!(graph.has_namespace_import(FileId(1)));
2120        assert!(!graph.has_namespace_import(FileId(2)));
2121
2122        // Simulate the cache load: the bitset arrives empty (serde-skipped), then
2123        // the loader reconstructs it from the persisted edges.
2124        graph.namespace_imported = FixedBitSet::default();
2125        graph.reconstruct_namespace_imported();
2126
2127        assert_eq!(
2128            graph.namespace_imported, fresh,
2129            "reconstructed namespace_imported must equal the fresh-built bitset"
2130        );
2131        assert!(graph.has_namespace_import(FileId(1)));
2132        assert!(!graph.has_namespace_import(FileId(2)));
2133    }
2134
2135    #[test]
2136    fn graph_unreachable_module() {
2137        let files = vec![
2138            DiscoveredFile {
2139                id: FileId(0),
2140                path: PathBuf::from("/project/entry.ts"),
2141                size_bytes: 100,
2142            },
2143            DiscoveredFile {
2144                id: FileId(1),
2145                path: PathBuf::from("/project/utils.ts"),
2146                size_bytes: 50,
2147            },
2148            DiscoveredFile {
2149                id: FileId(2),
2150                path: PathBuf::from("/project/orphan.ts"),
2151                size_bytes: 30,
2152            },
2153        ];
2154
2155        let entry_points = vec![EntryPoint {
2156            path: PathBuf::from("/project/entry.ts"),
2157            source: EntryPointSource::PackageJsonMain,
2158        }];
2159
2160        let resolved_modules = vec![
2161            ResolvedModule {
2162                file_id: FileId(0),
2163                path: PathBuf::from("/project/entry.ts"),
2164                resolved_imports: vec![ResolvedImport {
2165                    info: ImportInfo {
2166                        source: "./utils".to_string(),
2167                        imported_name: ImportedName::Named("foo".to_string()),
2168                        local_name: "foo".to_string(),
2169                        is_type_only: false,
2170                        is_type_only_star: false,
2171                        from_style: false,
2172                        span: oxc_span::Span::new(0, 10),
2173                        source_span: oxc_span::Span::default(),
2174                    },
2175                    target: ResolveResult::InternalModule(FileId(1)),
2176                }],
2177                ..Default::default()
2178            },
2179            ResolvedModule {
2180                file_id: FileId(1),
2181                path: PathBuf::from("/project/utils.ts"),
2182                exports: vec![fallow_types::extract::ExportInfo {
2183                    name: ExportName::Named("foo".to_string()),
2184                    local_name: Some("foo".to_string()),
2185                    is_type_only: false,
2186                    visibility: VisibilityTag::None,
2187                    expected_unused_reason: None,
2188                    span: oxc_span::Span::new(0, 20),
2189                    members: vec![],
2190                    is_side_effect_used: false,
2191                    super_class: None,
2192                    deprecated: false,
2193                    deprecated_reason: None,
2194                }]
2195                .into(),
2196                ..Default::default()
2197            },
2198            ResolvedModule {
2199                file_id: FileId(2),
2200                path: PathBuf::from("/project/orphan.ts"),
2201                exports: vec![fallow_types::extract::ExportInfo {
2202                    name: ExportName::Named("orphan".to_string()),
2203                    local_name: Some("orphan".to_string()),
2204                    is_type_only: false,
2205                    visibility: VisibilityTag::None,
2206                    expected_unused_reason: None,
2207                    span: oxc_span::Span::new(0, 20),
2208                    members: vec![],
2209                    is_side_effect_used: false,
2210                    super_class: None,
2211                    deprecated: false,
2212                    deprecated_reason: None,
2213                }]
2214                .into(),
2215                ..Default::default()
2216            },
2217        ];
2218
2219        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2220
2221        assert!(graph.modules[0].is_reachable(), "entry should be reachable");
2222        assert!(graph.modules[1].is_reachable(), "utils should be reachable");
2223        assert!(
2224            !graph.modules[2].is_reachable(),
2225            "orphan should NOT be reachable"
2226        );
2227    }
2228
2229    #[test]
2230    fn graph_package_usage_tracked() {
2231        let files = vec![DiscoveredFile {
2232            id: FileId(0),
2233            path: PathBuf::from("/project/entry.ts"),
2234            size_bytes: 100,
2235        }];
2236
2237        let entry_points = vec![EntryPoint {
2238            path: PathBuf::from("/project/entry.ts"),
2239            source: EntryPointSource::PackageJsonMain,
2240        }];
2241
2242        let resolved_modules = vec![ResolvedModule {
2243            file_id: FileId(0),
2244            path: PathBuf::from("/project/entry.ts"),
2245            exports: vec![].into(),
2246            re_exports: vec![],
2247            resolved_imports: vec![
2248                ResolvedImport {
2249                    info: ImportInfo {
2250                        source: "react".to_string(),
2251                        imported_name: ImportedName::Default,
2252                        local_name: "React".to_string(),
2253                        is_type_only: false,
2254                        is_type_only_star: false,
2255                        from_style: false,
2256                        span: oxc_span::Span::new(0, 10),
2257                        source_span: oxc_span::Span::default(),
2258                    },
2259                    target: ResolveResult::NpmPackage("react".to_string()),
2260                },
2261                ResolvedImport {
2262                    info: ImportInfo {
2263                        source: "lodash".to_string(),
2264                        imported_name: ImportedName::Named("merge".to_string()),
2265                        local_name: "merge".to_string(),
2266                        is_type_only: false,
2267                        is_type_only_star: false,
2268                        from_style: false,
2269                        span: oxc_span::Span::new(15, 30),
2270                        source_span: oxc_span::Span::default(),
2271                    },
2272                    target: ResolveResult::NpmPackage("lodash".to_string()),
2273                },
2274            ],
2275            ..Default::default()
2276        }];
2277
2278        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2279        assert!(graph.package_usage.contains_key("react"));
2280        assert!(graph.package_usage.contains_key("lodash"));
2281        assert!(!graph.package_usage.contains_key("express"));
2282    }
2283
2284    #[test]
2285    fn graph_empty() {
2286        let graph = ModuleGraph::build(&[], &[], &[]);
2287        assert_eq!(graph.module_count(), 0);
2288        assert_eq!(graph.edge_count(), 0);
2289    }
2290
2291    /// The persisted graph cache postcard-encodes the whole `ModuleGraph` and
2292    /// decodes it on a warm run. This proves the serde round-trip is lossless
2293    /// for the structural surface analysis reads: module / edge / export /
2294    /// reference counts and the `namespace_imported` bitset (reconstructed on
2295    /// load) all survive.
2296    #[test]
2297    fn graph_postcard_round_trip_is_lossless() {
2298        let graph = build_simple_graph();
2299
2300        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
2301        let mut decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
2302        // The store does this on load; do it here so the bitset is restored.
2303        decoded.reconstruct_namespace_imported();
2304
2305        assert_eq!(decoded.module_count(), graph.module_count());
2306        assert_eq!(decoded.edge_count(), graph.edge_count());
2307        assert_eq!(decoded.namespace_imported, graph.namespace_imported);
2308
2309        // Export + reference + member surface survives byte-for-byte.
2310        let utils = &decoded.modules[1];
2311        let foo = utils
2312            .exports
2313            .iter()
2314            .find(|e| e.name.to_string() == "foo")
2315            .expect("foo export survives round-trip");
2316        assert!(!foo.references.is_empty());
2317        let bar = utils
2318            .exports
2319            .iter()
2320            .find(|e| e.name.to_string() == "bar")
2321            .expect("bar export survives round-trip");
2322        assert!(bar.references.is_empty());
2323
2324        // Reachability flags and entry-point sets survive.
2325        assert!(decoded.modules[0].is_entry_point());
2326        assert!(decoded.modules[0].is_reachable());
2327        assert!(decoded.modules[1].is_reachable());
2328        assert_eq!(decoded.entry_points, graph.entry_points);
2329    }
2330
2331    #[test]
2332    fn graph_cjs_exports_tracked() {
2333        let files = vec![DiscoveredFile {
2334            id: FileId(0),
2335            path: PathBuf::from("/project/entry.ts"),
2336            size_bytes: 100,
2337        }];
2338
2339        let entry_points = vec![EntryPoint {
2340            path: PathBuf::from("/project/entry.ts"),
2341            source: EntryPointSource::PackageJsonMain,
2342        }];
2343
2344        let resolved_modules = vec![ResolvedModule {
2345            file_id: FileId(0),
2346            path: PathBuf::from("/project/entry.ts"),
2347            has_cjs_exports: true,
2348            has_angular_component_template_url: false,
2349            ..Default::default()
2350        }];
2351
2352        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2353        assert!(graph.modules[0].has_cjs_exports());
2354    }
2355
2356    #[test]
2357    fn graph_edges_for_returns_targets() {
2358        let graph = build_simple_graph();
2359        let targets = graph.edges_for(FileId(0));
2360        assert_eq!(targets, vec![FileId(1)]);
2361    }
2362
2363    #[test]
2364    fn graph_edges_for_no_imports() {
2365        let graph = build_simple_graph();
2366        let targets = graph.edges_for(FileId(1));
2367        assert!(targets.is_empty());
2368    }
2369
2370    #[test]
2371    fn graph_edges_for_out_of_bounds() {
2372        let graph = build_simple_graph();
2373        let targets = graph.edges_for(FileId(999));
2374        assert!(targets.is_empty());
2375    }
2376
2377    #[test]
2378    fn graph_direct_importer_summaries_include_symbols() {
2379        let graph = build_simple_graph();
2380        let summaries = graph.direct_importer_summaries(FileId(1));
2381
2382        assert_eq!(
2383            summaries,
2384            vec![DirectImporterSummary {
2385                source: FileId(0),
2386                symbols: vec![ImportedSymbolSummary {
2387                    imported: "foo".to_string(),
2388                    local: "foo".to_string(),
2389                    type_only: false,
2390                }],
2391            }]
2392        );
2393    }
2394
2395    #[test]
2396    fn graph_find_import_span_start_found() {
2397        let graph = build_simple_graph();
2398        let span_start = graph.find_import_span_start(FileId(0), FileId(1));
2399        assert!(span_start.is_some());
2400        assert_eq!(span_start.unwrap(), 0);
2401    }
2402
2403    #[test]
2404    fn graph_find_import_span_start_prefers_value_import_on_mixed_edge() {
2405        let files = vec![
2406            DiscoveredFile {
2407                id: FileId(0),
2408                path: PathBuf::from("/project/entry.ts"),
2409                size_bytes: 100,
2410            },
2411            DiscoveredFile {
2412                id: FileId(1),
2413                path: PathBuf::from("/project/utils.ts"),
2414                size_bytes: 50,
2415            },
2416        ];
2417        let entry_points = vec![EntryPoint {
2418            path: PathBuf::from("/project/entry.ts"),
2419            source: EntryPointSource::PackageJsonMain,
2420        }];
2421        let resolved_modules = vec![
2422            ResolvedModule {
2423                file_id: FileId(0),
2424                path: PathBuf::from("/project/entry.ts"),
2425                resolved_imports: vec![
2426                    ResolvedImport {
2427                        info: ImportInfo {
2428                            source: "./utils".to_string(),
2429                            imported_name: ImportedName::Named("Foo".to_string()),
2430                            local_name: "Foo".to_string(),
2431                            is_type_only: true,
2432                            is_type_only_star: false,
2433                            from_style: false,
2434                            span: oxc_span::Span::new(10, 20),
2435                            source_span: oxc_span::Span::default(),
2436                        },
2437                        target: ResolveResult::InternalModule(FileId(1)),
2438                    },
2439                    ResolvedImport {
2440                        info: ImportInfo {
2441                            source: "./utils".to_string(),
2442                            imported_name: ImportedName::Named("foo".to_string()),
2443                            local_name: "foo".to_string(),
2444                            is_type_only: false,
2445                            is_type_only_star: false,
2446                            from_style: false,
2447                            span: oxc_span::Span::new(50, 60),
2448                            source_span: oxc_span::Span::default(),
2449                        },
2450                        target: ResolveResult::InternalModule(FileId(1)),
2451                    },
2452                ],
2453                ..Default::default()
2454            },
2455            ResolvedModule {
2456                file_id: FileId(1),
2457                path: PathBuf::from("/project/utils.ts"),
2458                ..Default::default()
2459            },
2460        ];
2461
2462        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2463        assert_eq!(graph.find_import_span_start(FileId(0), FileId(1)), Some(50));
2464    }
2465
2466    #[test]
2467    fn graph_find_import_span_start_wrong_target() {
2468        let graph = build_simple_graph();
2469        let span_start = graph.find_import_span_start(FileId(0), FileId(0));
2470        assert!(span_start.is_none());
2471    }
2472
2473    #[test]
2474    fn graph_find_import_span_start_source_out_of_bounds() {
2475        let graph = build_simple_graph();
2476        let span_start = graph.find_import_span_start(FileId(999), FileId(1));
2477        assert!(span_start.is_none());
2478    }
2479
2480    #[test]
2481    fn graph_find_import_span_start_no_edges() {
2482        let graph = build_simple_graph();
2483        let span_start = graph.find_import_span_start(FileId(1), FileId(0));
2484        assert!(span_start.is_none());
2485    }
2486
2487    #[test]
2488    fn graph_reverse_deps_populated() {
2489        let graph = build_simple_graph();
2490        assert!(graph.reverse_deps[1].contains(&FileId(0)));
2491        assert!(graph.reverse_deps[0].is_empty());
2492    }
2493
2494    #[test]
2495    fn graph_type_only_package_usage_tracked() {
2496        let files = vec![DiscoveredFile {
2497            id: FileId(0),
2498            path: PathBuf::from("/project/entry.ts"),
2499            size_bytes: 100,
2500        }];
2501        let entry_points = vec![EntryPoint {
2502            path: PathBuf::from("/project/entry.ts"),
2503            source: EntryPointSource::PackageJsonMain,
2504        }];
2505        let resolved_modules = vec![ResolvedModule {
2506            file_id: FileId(0),
2507            path: PathBuf::from("/project/entry.ts"),
2508            resolved_imports: vec![
2509                ResolvedImport {
2510                    info: ImportInfo {
2511                        source: "react".to_string(),
2512                        imported_name: ImportedName::Named("FC".to_string()),
2513                        local_name: "FC".to_string(),
2514                        is_type_only: true,
2515                        is_type_only_star: false,
2516                        from_style: false,
2517                        span: oxc_span::Span::new(0, 10),
2518                        source_span: oxc_span::Span::default(),
2519                    },
2520                    target: ResolveResult::NpmPackage("react".to_string()),
2521                },
2522                ResolvedImport {
2523                    info: ImportInfo {
2524                        source: "react".to_string(),
2525                        imported_name: ImportedName::Named("useState".to_string()),
2526                        local_name: "useState".to_string(),
2527                        is_type_only: false,
2528                        is_type_only_star: false,
2529                        from_style: false,
2530                        span: oxc_span::Span::new(15, 30),
2531                        source_span: oxc_span::Span::default(),
2532                    },
2533                    target: ResolveResult::NpmPackage("react".to_string()),
2534                },
2535            ],
2536            ..Default::default()
2537        }];
2538
2539        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2540        assert!(graph.package_usage.contains_key("react"));
2541        assert!(graph.type_only_package_usage.contains_key("react"));
2542    }
2543
2544    #[test]
2545    fn graph_default_import_reference() {
2546        let files = vec![
2547            DiscoveredFile {
2548                id: FileId(0),
2549                path: PathBuf::from("/project/entry.ts"),
2550                size_bytes: 100,
2551            },
2552            DiscoveredFile {
2553                id: FileId(1),
2554                path: PathBuf::from("/project/utils.ts"),
2555                size_bytes: 50,
2556            },
2557        ];
2558        let entry_points = vec![EntryPoint {
2559            path: PathBuf::from("/project/entry.ts"),
2560            source: EntryPointSource::PackageJsonMain,
2561        }];
2562        let resolved_modules = vec![
2563            ResolvedModule {
2564                file_id: FileId(0),
2565                path: PathBuf::from("/project/entry.ts"),
2566                resolved_imports: vec![ResolvedImport {
2567                    info: ImportInfo {
2568                        source: "./utils".to_string(),
2569                        imported_name: ImportedName::Default,
2570                        local_name: "Utils".to_string(),
2571                        is_type_only: false,
2572                        is_type_only_star: false,
2573                        from_style: false,
2574                        span: oxc_span::Span::new(0, 10),
2575                        source_span: oxc_span::Span::default(),
2576                    },
2577                    target: ResolveResult::InternalModule(FileId(1)),
2578                }],
2579                ..Default::default()
2580            },
2581            ResolvedModule {
2582                file_id: FileId(1),
2583                path: PathBuf::from("/project/utils.ts"),
2584                exports: vec![fallow_types::extract::ExportInfo {
2585                    name: ExportName::Default,
2586                    local_name: None,
2587                    is_type_only: false,
2588                    visibility: VisibilityTag::None,
2589                    expected_unused_reason: None,
2590                    span: oxc_span::Span::new(0, 20),
2591                    members: vec![],
2592                    is_side_effect_used: false,
2593                    super_class: None,
2594                    deprecated: false,
2595                    deprecated_reason: None,
2596                }]
2597                .into(),
2598                ..Default::default()
2599            },
2600        ];
2601
2602        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2603        let utils = &graph.modules[1];
2604        let default_export = utils
2605            .exports
2606            .iter()
2607            .find(|e| matches!(e.name, ExportName::Default))
2608            .unwrap();
2609        assert!(!default_export.references.is_empty());
2610        assert_eq!(
2611            default_export.references[0].kind,
2612            ReferenceKind::DefaultImport
2613        );
2614    }
2615
2616    #[test]
2617    fn graph_side_effect_import_no_export_reference() {
2618        let files = vec![
2619            DiscoveredFile {
2620                id: FileId(0),
2621                path: PathBuf::from("/project/entry.ts"),
2622                size_bytes: 100,
2623            },
2624            DiscoveredFile {
2625                id: FileId(1),
2626                path: PathBuf::from("/project/styles.ts"),
2627                size_bytes: 50,
2628            },
2629        ];
2630        let entry_points = vec![EntryPoint {
2631            path: PathBuf::from("/project/entry.ts"),
2632            source: EntryPointSource::PackageJsonMain,
2633        }];
2634        let resolved_modules = vec![
2635            ResolvedModule {
2636                file_id: FileId(0),
2637                path: PathBuf::from("/project/entry.ts"),
2638                resolved_imports: vec![ResolvedImport {
2639                    info: ImportInfo {
2640                        source: "./styles".to_string(),
2641                        imported_name: ImportedName::SideEffect,
2642                        local_name: String::new(),
2643                        is_type_only: false,
2644                        is_type_only_star: false,
2645                        from_style: false,
2646                        span: oxc_span::Span::new(0, 10),
2647                        source_span: oxc_span::Span::default(),
2648                    },
2649                    target: ResolveResult::InternalModule(FileId(1)),
2650                }],
2651                ..Default::default()
2652            },
2653            ResolvedModule {
2654                file_id: FileId(1),
2655                path: PathBuf::from("/project/styles.ts"),
2656                exports: vec![fallow_types::extract::ExportInfo {
2657                    name: ExportName::Named("primaryColor".to_string()),
2658                    local_name: Some("primaryColor".to_string()),
2659                    is_type_only: false,
2660                    visibility: VisibilityTag::None,
2661                    expected_unused_reason: None,
2662                    span: oxc_span::Span::new(0, 20),
2663                    members: vec![],
2664                    is_side_effect_used: false,
2665                    super_class: None,
2666                    deprecated: false,
2667                    deprecated_reason: None,
2668                }]
2669                .into(),
2670                ..Default::default()
2671            },
2672        ];
2673
2674        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2675        assert_eq!(graph.edge_count(), 1);
2676        let styles = &graph.modules[1];
2677        assert!(styles.is_reachable());
2678        let export = &styles.exports[0];
2679        assert!(
2680            export.references.is_empty(),
2681            "side-effect import should not reference named exports"
2682        );
2683
2684        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
2685        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
2686        assert_eq!(decoded.edge_count(), 1);
2687        assert!(decoded.modules[1].is_reachable());
2688        assert!(decoded.modules[1].exports[0].references.is_empty());
2689    }
2690
2691    #[test]
2692    fn graph_multiple_entry_points() {
2693        let files = vec![
2694            DiscoveredFile {
2695                id: FileId(0),
2696                path: PathBuf::from("/project/main.ts"),
2697                size_bytes: 100,
2698            },
2699            DiscoveredFile {
2700                id: FileId(1),
2701                path: PathBuf::from("/project/worker.ts"),
2702                size_bytes: 100,
2703            },
2704            DiscoveredFile {
2705                id: FileId(2),
2706                path: PathBuf::from("/project/shared.ts"),
2707                size_bytes: 50,
2708            },
2709        ];
2710        let entry_points = vec![
2711            EntryPoint {
2712                path: PathBuf::from("/project/main.ts"),
2713                source: EntryPointSource::PackageJsonMain,
2714            },
2715            EntryPoint {
2716                path: PathBuf::from("/project/worker.ts"),
2717                source: EntryPointSource::PackageJsonMain,
2718            },
2719        ];
2720        let resolved_modules = vec![
2721            ResolvedModule {
2722                file_id: FileId(0),
2723                path: PathBuf::from("/project/main.ts"),
2724                resolved_imports: vec![ResolvedImport {
2725                    info: ImportInfo {
2726                        source: "./shared".to_string(),
2727                        imported_name: ImportedName::Named("helper".to_string()),
2728                        local_name: "helper".to_string(),
2729                        is_type_only: false,
2730                        is_type_only_star: false,
2731                        from_style: false,
2732                        span: oxc_span::Span::new(0, 10),
2733                        source_span: oxc_span::Span::default(),
2734                    },
2735                    target: ResolveResult::InternalModule(FileId(2)),
2736                }],
2737                ..Default::default()
2738            },
2739            ResolvedModule {
2740                file_id: FileId(1),
2741                path: PathBuf::from("/project/worker.ts"),
2742                ..Default::default()
2743            },
2744            ResolvedModule {
2745                file_id: FileId(2),
2746                path: PathBuf::from("/project/shared.ts"),
2747                exports: vec![fallow_types::extract::ExportInfo {
2748                    name: ExportName::Named("helper".to_string()),
2749                    local_name: Some("helper".to_string()),
2750                    is_type_only: false,
2751                    visibility: VisibilityTag::None,
2752                    expected_unused_reason: None,
2753                    span: oxc_span::Span::new(0, 20),
2754                    members: vec![],
2755                    is_side_effect_used: false,
2756                    super_class: None,
2757                    deprecated: false,
2758                    deprecated_reason: None,
2759                }]
2760                .into(),
2761                ..Default::default()
2762            },
2763        ];
2764
2765        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
2766        assert!(graph.modules[0].is_entry_point());
2767        assert!(graph.modules[1].is_entry_point());
2768        assert!(!graph.modules[2].is_entry_point());
2769        assert!(graph.modules[0].is_reachable());
2770        assert!(graph.modules[1].is_reachable());
2771        assert!(graph.modules[2].is_reachable());
2772    }
2773}