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