fallow_graph/graph/

mod.rs

//! Module dependency graph with re-export chain propagation and reachability analysis.
//!
//! The graph is built from resolved modules and entry points, then used to determine
//! which files are reachable and which exports are referenced.

mod build;
mod cycles;
mod fan_io;
mod impact_closure;
mod namespace_aliases;
mod namespace_indexes;
mod namespace_re_exports;
mod narrowing;
mod partition_order;
mod public_exports;
mod re_exports;
mod reachability;
pub mod types;

use std::path::Path;

use fixedbitset::FixedBitSet;
use rustc_hash::{FxHashMap, FxHashSet};

use crate::resolve::{ResolvedModule, ResolvedReplacedModuleTarget};
use fallow_types::discover::{DiscoveredFile, EntryPoint, FileId};
use fallow_types::extract::{ImportedName, ModuleLoadMechanism};
use types::{ReferencePathInterner, ReferencePathNode, ReferenceRouteNodeId, ReferenceRoutes};

pub use fan_io::{FocusFileFacts, FocusFileFactsPaths};
pub use impact_closure::{
    CoordinationGap, CoordinationGapPaths, ImpactClosure, ImpactClosurePaths,
};
pub use partition_order::{PartitionOrder, PartitionOrderPaths, ReviewUnit, ReviewUnitPaths};
pub use re_exports::GraphReExportCycle;
pub use types::{
    ExportSymbol, ModuleNode, ReExportEdge, ReferenceKind, ReferencePathId, SymbolReference,
};

/// True when the path's final component looks like a TypeScript declaration
/// file (`.d.ts`, `.d.mts`, `.d.cts`). Used to seed declaration files as
/// overall entry points so ambient `typeof import()` references stay alive.
///
/// Keep in sync with the analysis-layer declaration-file predicate. The graph
/// crate cannot depend on the detector backend, so the predicate is duplicated.
fn is_declaration_file_path(path: &Path) -> bool {
    path.file_name()
        .and_then(|n| n.to_str())
        .is_some_and(|name| {
            name.ends_with(".d.ts") || name.ends_with(".d.mts") || name.ends_with(".d.cts")
        })
}

/// The core module dependency graph.
///
/// Derives `serde` so the whole graph can be persisted to `.fallow/graph-cache.bin`
/// (see `crate::cache`) and skipped on a re-run whose inputs are byte-identical.
/// `namespace_imported` is a derived `FixedBitSet` reconstructed from the edge
/// set on cache load (`reconstruct_namespace_imported`), so it is
/// `#[serde(skip, default)]` rather than persisted.
#[derive(Debug, serde::Serialize, serde::Deserialize)]
pub struct ModuleGraph {
    /// All modules indexed by `FileId`.
    ///
    /// Invariant: `modules[file_id.0 as usize].file_id == file_id` for every
    /// `FileId` in the graph. Holds because `discover/walk.rs` assigns FileIds
    /// sequentially via `.enumerate()` after path-sorting, and
    /// `build::populate_edges` pushes one `ModuleNode` per file in iteration
    /// order. Detectors rely on this for O(1) FileId-to-module lookup
    /// (`graph.modules.get(file_id.0 as usize)`) instead of building a
    /// per-call `FxHashMap<FileId, &ModuleNode>`.
    pub modules: Vec<ModuleNode>,
    /// Flat edge storage for cache-friendly iteration.
    edges: Vec<Edge>,
    /// Maps npm package names to the set of `FileId`s that import them.
    pub package_usage: FxHashMap<String, Vec<FileId>>,
    /// Maps npm package names to the set of `FileId`s that import them with type-only imports.
    /// A package appearing here but not in `package_usage` (or only in both) indicates
    /// it's only used for types and could be a devDependency.
    pub type_only_package_usage: FxHashMap<String, Vec<FileId>>,
    /// All entry point `FileId`s.
    pub entry_points: FxHashSet<FileId>,
    /// Runtime/application entry point `FileId`s.
    pub runtime_entry_points: FxHashSet<FileId>,
    /// Test entry point `FileId`s.
    pub test_entry_points: FxHashSet<FileId>,
    /// Compact correlation index for distinct test-root replacement profiles.
    ///
    /// Empty when no test root declares a project-internal replacement. That
    /// preserves the ordinary single-BFS test reachability path.
    test_reachability_index: TestReachabilityIndex,
    /// Flat interned linked paths used by exact export references.
    reference_paths: Vec<ReferencePathNode>,
    /// Compact transition graphs used by namespace-derived references.
    reference_routes: ReferenceRoutes,
    /// Reverse index: for each `FileId`, which files import it.
    pub reverse_deps: Vec<Vec<FileId>>,
    /// Precomputed: which modules have namespace imports (import * as ns).
    ///
    /// Derived entirely from the edge set (a module is namespace-imported iff
    /// some edge to it carries an `ImportedName::Namespace` symbol), so it is
    /// not persisted: on cache load it is rebuilt by
    /// [`ModuleGraph::reconstruct_namespace_imported`], which replicates the
    /// exact insertion logic from `build.rs`.
    #[serde(skip, default)]
    namespace_imported: FixedBitSet,
    /// Re-export cycles and self-loops detected during Phase 4 chain
    /// resolution. Each entry names the participating files (sorted
    /// lexicographically) and a `is_self_loop` flag distinguishing
    /// single-file self-re-exports from multi-node cycles. Populated by
    /// `re_exports::find_re_export_cycles` and consumed by the analysis
    /// backend, which wraps each entry in a typed `ReExportCycleFinding`.
    pub re_export_cycles: Vec<GraphReExportCycle>,
}

/// An edge in the module graph.
///
/// Public consumers inspect relationships through summary methods such as
/// [`ModuleGraph::direct_importer_summaries`] and
/// [`ModuleGraph::outgoing_edge_summaries`]. Keeping the raw storage private
/// preserves graph invariants and the `Edge == 32` size assertion below.
#[derive(Debug, serde::Serialize, serde::Deserialize)]
pub struct Edge {
    /// Source module of this import edge.
    source: FileId,
    /// Target module imported by `source`.
    target: FileId,
    /// Symbols imported across this edge.
    symbols: Vec<ImportedSymbol>,
}

/// A symbol imported across an edge.
#[derive(Debug, serde::Serialize, serde::Deserialize)]
pub struct ImportedSymbol {
    /// The name as imported from the target (`Named`, `Default`, `Namespace`,
    /// `SideEffect`).
    pub imported_name: ImportedName,
    /// Local binding name in the importing file.
    pub local_name: String,
    /// Byte span of the import statement in the source file.
    #[serde(with = "crate::cache::span_serde")]
    pub import_span: oxc_span::Span,
    /// Whether this import is type-only (`import type { ... }`).
    /// Used to skip type-only edges in circular dependency detection.
    pub is_type_only: bool,
    /// Runtime module mechanism that created this symbol edge.
    mechanism: ModuleLoadMechanism,
}

/// Flat bitset index mapping files to the test profiles that reach them.
///
/// Each file owns `words_per_file` contiguous reachable-profile words. Masks are
/// target-sparse: only explicit replacement targets own a row, while every row
/// retains dense profile words for constant-time word lookup. Retained storage
/// is `O((files + replaced_targets) * ceil(profiles / 64))`; correlation queries
/// intersect machine words instead of scanning profile file lists.
#[derive(Debug, Default, serde::Serialize, serde::Deserialize)]
struct TestReachabilityIndex {
    profile_count: usize,
    words_per_file: usize,
    reachable_profiles: Vec<u64>,
    masked_profiles: Vec<MaskedTestProfiles>,
}

/// Sparse profile-mask row for one replaced target.
#[derive(Debug, serde::Serialize, serde::Deserialize)]
struct MaskedTestProfiles {
    target: FileId,
    profiles: Vec<u64>,
}

impl TestReachabilityIndex {
    fn new(file_capacity: usize, profile_count: usize) -> Self {
        let words_per_file = profile_count.div_ceil(u64::BITS as usize);
        let storage_len = file_capacity.saturating_mul(words_per_file);
        Self {
            profile_count,
            words_per_file,
            reachable_profiles: vec![0; storage_len],
            masked_profiles: Vec::new(),
        }
    }

    fn set_sparse_masks(&mut self, masks: FxHashMap<FileId, Vec<u64>>) {
        let mut rows: Vec<_> = masks
            .into_iter()
            .map(|(target, profiles)| MaskedTestProfiles { target, profiles })
            .collect();
        rows.sort_unstable_by_key(|row| row.target.0);
        self.masked_profiles = rows;
    }

    fn profiles_for<'a>(&self, storage: &'a [u64], file_id: FileId) -> Option<&'a [u64]> {
        let start = (file_id.0 as usize).checked_mul(self.words_per_file)?;
        let end = start.checked_add(self.words_per_file)?;
        storage.get(start..end)
    }

    fn masked_profiles_for(&self, file_id: FileId) -> Option<&[u64]> {
        self.masked_profiles
            .binary_search_by_key(&file_id.0, |row| row.target.0)
            .ok()
            .map(|index| self.masked_profiles[index].profiles.as_slice())
    }

    fn covers_reference_path(
        &self,
        source: FileId,
        path: types::ReferencePathId,
        paths: &[ReferencePathNode],
        routes: &ReferenceRoutes,
    ) -> bool {
        let Some(source_profiles) = self.profiles_for(&self.reachable_profiles, source) else {
            return false;
        };

        for (word_index, &source_word) in source_profiles.iter().enumerate() {
            let mut active_profiles = source_word;
            if active_profiles == 0 {
                continue;
            }

            let mut next = Some(path);
            while let Some(path_id) = next {
                let Some(path_node) = paths.get(path_id.index()) else {
                    return false;
                };
                next = path_node.parent();
                active_profiles = match *path_node {
                    ReferencePathNode::Hop {
                        target, mechanism, ..
                    } => self.active_hop_profiles(target, mechanism, word_index, active_profiles),
                    ReferencePathNode::Route {
                        graph,
                        start,
                        terminal,
                        start_mechanism,
                        ..
                    } => self.active_route_profiles(
                        routes,
                        graph,
                        start,
                        terminal,
                        start_mechanism,
                        word_index,
                        active_profiles,
                    ),
                };
                if active_profiles == 0 {
                    break;
                }
            }

            if active_profiles != 0 {
                return true;
            }
        }

        false
    }

    #[cfg(test)]
    fn covers_path<I>(&self, source: FileId, hops: &I) -> bool
    where
        I: Iterator<Item = (FileId, ModuleLoadMechanism)> + Clone,
    {
        let Some(source_profiles) = self.profiles_for(&self.reachable_profiles, source) else {
            return false;
        };
        for (word_index, &source_word) in source_profiles.iter().enumerate() {
            let mut active_profiles = source_word;
            for (target, mechanism) in (*hops).clone() {
                active_profiles =
                    self.active_hop_profiles(target, mechanism, word_index, active_profiles);
                if active_profiles == 0 {
                    break;
                }
            }
            if active_profiles != 0 {
                return true;
            }
        }
        false
    }

    fn active_hop_profiles(
        &self,
        target: FileId,
        mechanism: ModuleLoadMechanism,
        word_index: usize,
        mut active_profiles: u64,
    ) -> u64 {
        let Some(target_word) = self
            .profiles_for(&self.reachable_profiles, target)
            .and_then(|profiles| profiles.get(word_index))
        else {
            return 0;
        };
        active_profiles &= target_word;
        if matches!(mechanism, ModuleLoadMechanism::EsModule)
            && let Some(masked_profiles) = self.masked_profiles_for(target)
        {
            let Some(masked_word) = masked_profiles.get(word_index) else {
                return 0;
            };
            active_profiles &= !masked_word;
        }
        active_profiles
    }

    /// Evaluate one compact namespace transition graph with a monotone
    /// profile-bit worklist. Each `(route node, profile bit)` is processed at
    /// most once, including cyclic graphs.
    #[expect(
        clippy::too_many_arguments,
        reason = "the route identity and profile word form one evaluation contract"
    )]
    fn active_route_profiles(
        &self,
        routes: &ReferenceRoutes,
        graph_id: types::ReferenceRouteGraphId,
        start: ReferenceRouteNodeId,
        terminal: ReferenceRouteNodeId,
        start_mechanism: Option<ModuleLoadMechanism>,
        word_index: usize,
        candidate_profiles: u64,
    ) -> u64 {
        let Some(graph) = routes.graphs.get(graph_id.0 as usize) else {
            return 0;
        };
        let node_count = graph.nodes.end.saturating_sub(graph.nodes.start) as usize;
        let start_index = start.0 as usize;
        let terminal_index = terminal.0 as usize;
        if start_index >= node_count || terminal_index >= node_count {
            return 0;
        }

        let mut attempted = vec![0_u64; node_count];
        let mut pending = vec![0_u64; node_count];
        let mut queued = vec![false; node_count];
        let mut queue = std::collections::VecDeque::from([start_index]);
        pending[start_index] = candidate_profiles;
        queued[start_index] = true;
        let mut successful_profiles = 0_u64;

        while let Some(local_index) = queue.pop_front() {
            queued[local_index] = false;
            let incoming = pending[local_index] & !attempted[local_index];
            pending[local_index] = 0;
            attempted[local_index] |= incoming;
            if incoming == 0 {
                continue;
            }

            let Some(node) = routes.nodes.get(graph.nodes.start as usize + local_index) else {
                return 0;
            };
            let active = if local_index == start_index {
                start_mechanism.map_or(incoming, |mechanism| {
                    self.active_hop_profiles(node.target, mechanism, word_index, incoming)
                })
            } else {
                self.active_hop_profiles(node.target, node.mechanism, word_index, incoming)
            };
            if active == 0 {
                continue;
            }
            if local_index == terminal_index {
                successful_profiles |= active;
                continue;
            }

            let Some(successors) = routes
                .edges
                .get(node.successors.start as usize..node.successors.end as usize)
            else {
                return 0;
            };
            for successor in successors {
                let successor_index = successor.0 as usize;
                if successor_index >= node_count {
                    return 0;
                }
                let new_profiles = active & !attempted[successor_index] & !pending[successor_index];
                if new_profiles == 0 {
                    continue;
                }
                pending[successor_index] |= new_profiles;
                if !queued[successor_index] {
                    queued[successor_index] = true;
                    queue.push_back(successor_index);
                }
            }
        }

        successful_profiles
    }

    #[cfg(test)]
    fn profile_contains(&self, storage: &[u64], file_id: FileId, profile: usize) -> bool {
        self.profiles_for(storage, file_id)
            .and_then(|words| words.get(profile / u64::BITS as usize))
            .is_some_and(|word| word & (1_u64 << (profile % u64::BITS as usize)) != 0)
    }

    #[cfg(test)]
    fn profile_reaches(&self, file_id: FileId, profile: usize) -> bool {
        self.profile_contains(&self.reachable_profiles, file_id, profile)
    }

    #[cfg(test)]
    fn profile_masks(&self, file_id: FileId, profile: usize) -> bool {
        self.masked_profiles_for(file_id)
            .and_then(|words| words.get(profile / u64::BITS as usize))
            .is_some_and(|word| word & (1_u64 << (profile % u64::BITS as usize)) != 0)
    }
}

/// Importer details for one file that directly imports a target module.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DirectImporterSummary {
    /// Source file that imports the requested target.
    pub source: FileId,
    /// Symbols imported from the target by this source file.
    pub symbols: Vec<ImportedSymbolSummary>,
}

/// Symbol details for a direct import edge.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ImportedSymbolSummary {
    /// Imported binding name, using `default`, `*`, and `side-effect` for
    /// non-named imports.
    pub imported: String,
    /// Local binding name in the importing file.
    pub local: String,
    /// Whether this symbol came from a type-only import.
    pub type_only: bool,
}

#[cfg(target_pointer_width = "64")]
const _: () = assert!(std::mem::size_of::<Edge>() == 32);
#[cfg(target_pointer_width = "64")]
const _: () = assert!(std::mem::size_of::<ImportedSymbol>() == 64);

#[cold]
#[inline(never)]
fn propagate_namespace_references(
    graph: &mut ModuleGraph,
    module_by_id: &FxHashMap<FileId, &ResolvedModule>,
    features: build::NamespaceFeatures,
    reference_paths: &mut ReferencePathInterner,
) {
    let indexes = namespace_indexes::NamespacePropagationIndexes::new(graph, module_by_id);
    if features.has_aliases {
        namespace_aliases::propagate_cross_package_aliases(
            graph,
            module_by_id,
            &indexes,
            reference_paths,
        );
    }
    if features.has_re_exports {
        namespace_re_exports::propagate_namespace_re_exports(graph, &indexes, reference_paths);
    }
}

impl ModuleGraph {
    fn resolve_entry_point_ids(
        entry_points: &[EntryPoint],
        path_to_id: &FxHashMap<&Path, FileId>,
    ) -> FxHashSet<FileId> {
        entry_points
            .iter()
            .filter_map(|ep| {
                path_to_id.get(ep.path.as_path()).copied().or_else(|| {
                    dunce::canonicalize(&ep.path)
                        .ok()
                        .and_then(|path| path_to_id.get(path.as_path()).copied())
                })
            })
            .collect()
    }

    /// Build the module graph from resolved modules and entry points.
    pub fn build(
        resolved_modules: &[ResolvedModule],
        entry_points: &[EntryPoint],
        files: &[DiscoveredFile],
    ) -> Self {
        Self::build_with_reachability_roots(
            resolved_modules,
            entry_points,
            entry_points,
            &[],
            files,
        )
    }

    /// Build the module graph with explicit runtime and test reachability roots.
    pub fn build_with_reachability_roots(
        resolved_modules: &[ResolvedModule],
        entry_points: &[EntryPoint],
        runtime_entry_points: &[EntryPoint],
        test_entry_points: &[EntryPoint],
        files: &[DiscoveredFile],
    ) -> Self {
        Self::build_with_reachability_roots_and_replacements(
            resolved_modules,
            &[],
            entry_points,
            runtime_entry_points,
            test_entry_points,
            files,
        )
    }

    /// Build the module graph with root-specific test-time module replacements.
    pub fn build_with_reachability_roots_and_replacements(
        resolved_modules: &[ResolvedModule],
        replaced_module_targets: &[ResolvedReplacedModuleTarget],
        entry_points: &[EntryPoint],
        runtime_entry_points: &[EntryPoint],
        test_entry_points: &[EntryPoint],
        files: &[DiscoveredFile],
    ) -> Self {
        let _span = tracing::info_span!("build_graph").entered();

        let module_count = files.len();

        let max_file_id = files
            .iter()
            .map(|f| f.id.0 as usize)
            .max()
            .map_or(0, |m| m + 1);
        let total_capacity = max_file_id.max(module_count);

        let path_to_id: FxHashMap<&Path, FileId> =
            files.iter().map(|f| (f.path.as_path(), f.id)).collect();

        let module_by_id: FxHashMap<FileId, &ResolvedModule> =
            resolved_modules.iter().map(|m| (m.file_id, m)).collect();

        let mut entry_point_ids = Self::resolve_entry_point_ids(entry_points, &path_to_id);
        let runtime_entry_point_ids =
            Self::resolve_entry_point_ids(runtime_entry_points, &path_to_id);
        let test_entry_point_ids = Self::resolve_entry_point_ids(test_entry_points, &path_to_id);

        for file in files {
            if is_declaration_file_path(&file.path) {
                entry_point_ids.insert(file.id);
            }
        }

        let (mut graph, namespace_features) = Self::populate_edges(&build::PopulateEdgesInput {
            files,
            module_by_id: &module_by_id,
            entry_point_ids: &entry_point_ids,
            runtime_entry_point_ids: &runtime_entry_point_ids,
            test_entry_point_ids: &test_entry_point_ids,
            module_count,
            total_capacity,
        });

        let test_reachability_plan = reachability::TestReachabilityPlan::new(
            &test_entry_point_ids,
            replaced_module_targets,
            total_capacity,
        );

        let mut reference_paths =
            ReferencePathInterner::new(test_reachability_plan.requires_reference_provenance());
        graph.populate_references(&module_by_id, &entry_point_ids, &mut reference_paths);

        if namespace_features.has_aliases || namespace_features.has_re_exports {
            propagate_namespace_references(
                &mut graph,
                &module_by_id,
                namespace_features,
                &mut reference_paths,
            );
        }

        graph.mark_reachable(
            &entry_point_ids,
            &runtime_entry_point_ids,
            test_reachability_plan,
            total_capacity,
        );

        graph.re_export_cycles =
            graph.resolve_re_export_chains(&module_by_id, &mut reference_paths);
        let finalized_paths = reference_paths.finalize(&mut graph.modules);
        graph.reference_paths = finalized_paths.paths;
        graph.reference_routes = finalized_paths.routes;

        graph
    }

    /// Total number of modules.
    #[must_use]
    pub const fn module_count(&self) -> usize {
        self.modules.len()
    }

    /// Total number of edges.
    #[must_use]
    pub const fn edge_count(&self) -> usize {
        self.edges.len()
    }

    /// Return whether any test-root traversal reaches `file_id`.
    #[must_use]
    pub fn is_test_reachable(&self, file_id: FileId) -> bool {
        self.modules
            .get(file_id.0 as usize)
            .is_some_and(ModuleNode::is_test_reachable)
    }

    /// Return whether one test-root traversal covers the export reference at
    /// `reference_index` on `export`.
    ///
    /// Coverage requires one profile that reaches the referencing file and
    /// every target hop. ESM hops also require that profile not to replace the
    /// hop target; CommonJS hops remain active because Vitest replacement mocks
    /// do not intercept `require()`.
    #[must_use]
    pub fn is_test_reference_covered(&self, export: &ExportSymbol, reference_index: usize) -> bool {
        let Some(reference) = export.references.get(reference_index) else {
            return false;
        };
        if self.test_reachability_index.profile_count == 0 {
            return self.is_test_reachable(reference.from_file);
        }

        let Some(path) = export.reference_path(reference_index) else {
            return false;
        };

        self.test_reachability_index.covers_reference_path(
            reference.from_file,
            path,
            &self.reference_paths,
            &self.reference_routes,
        )
    }

    /// Return whether any reference on `export` is covered by a test-root
    /// traversal.
    #[must_use]
    pub fn is_any_test_reference_covered(&self, export: &ExportSymbol) -> bool {
        (0..export.references.len())
            .any(|reference_index| self.is_test_reference_covered(export, reference_index))
    }

    #[cfg(test)]
    fn reference_path_hops(
        &self,
        export: &ExportSymbol,
        reference_index: usize,
    ) -> Vec<(FileId, ModuleLoadMechanism)> {
        let mut hops = Vec::new();
        let mut next = export.reference_path(reference_index);
        while let Some(path_id) = next {
            let Some(node) = self.reference_paths.get(path_id.index()) else {
                return Vec::new();
            };
            next = node.parent();
            match *node {
                ReferencePathNode::Hop {
                    target, mechanism, ..
                } => hops.push((target, mechanism)),
                ReferencePathNode::Route {
                    graph,
                    start,
                    terminal,
                    start_mechanism,
                    ..
                } => hops.extend(self.reference_routes.canonical_hops(
                    graph,
                    start,
                    terminal,
                    start_mechanism,
                )),
            }
        }
        hops
    }

    /// Rebuild the `namespace_imported` bitset from the edge set.
    ///
    /// `namespace_imported` is `#[serde(skip)]`, so a graph loaded from the
    /// persisted cache (`crate::cache`) arrives with an empty default bitset.
    /// This restores it by replicating the EXACT insertion rule from
    /// `build.rs`: a target `FileId` is namespace-imported iff some edge to it
    /// carries an `ImportedName::Namespace` symbol. Both build-time insertion
    /// sites (static / dynamic `import * as ns` in `collect_import_edge`, and
    /// glob dynamic-import patterns in `collect_edges_for_module`) push a
    /// `Namespace` symbol onto the target's edge, so iterating the persisted
    /// edges and checking for a `Namespace` symbol reproduces the original
    /// bitset bit-for-bit. The capacity matches `build.rs`'s
    /// `max_file_id.max(module_count)`, which equals `modules.len()` under the
    /// dense path-sorted FileId invariant.
    pub(crate) fn reconstruct_namespace_imported(&mut self) {
        let capacity = self
            .edges
            .iter()
            .map(|edge| edge.target.0 as usize + 1)
            .max()
            .unwrap_or(0)
            .max(self.modules.len());
        let mut bitset = FixedBitSet::with_capacity(capacity);
        for edge in &self.edges {
            if edge
                .symbols
                .iter()
                .any(|sym| matches!(sym.imported_name, ImportedName::Namespace))
            {
                let idx = edge.target.0 as usize;
                if idx < capacity {
                    bitset.insert(idx);
                }
            }
        }
        self.namespace_imported = bitset;
    }

    /// Check if any importer uses `import * as ns` for this module.
    /// Uses precomputed bitset, O(1) lookup.
    #[must_use]
    pub fn has_namespace_import(&self, file_id: FileId) -> bool {
        let idx = file_id.0 as usize;
        if idx >= self.namespace_imported.len() {
            return false;
        }
        self.namespace_imported.contains(idx)
    }

    /// Get the target `FileId`s of all outgoing edges for a module.
    #[must_use]
    pub fn edges_for(&self, file_id: FileId) -> Vec<FileId> {
        let idx = file_id.0 as usize;
        if idx >= self.modules.len() {
            return Vec::new();
        }
        let range = &self.modules[idx].edge_range;
        self.edges[range.clone()].iter().map(|e| e.target).collect()
    }

    /// Iterate the outgoing edges of `file_id` with full per-symbol data.
    ///
    /// `fallow trace` needs the raw `ImportedSymbol` set on each edge in
    /// both directions, which the flattened summary structs cannot express.
    /// Returns an empty iterator for out-of-range file ids.
    pub fn outgoing_symbol_edges(
        &self,
        file_id: FileId,
    ) -> impl Iterator<Item = (FileId, &[ImportedSymbol])> + '_ {
        let idx = file_id.0 as usize;
        let range = if idx < self.modules.len() {
            self.modules[idx].edge_range.clone()
        } else {
            0..0
        };
        self.edges[range]
            .iter()
            .map(|edge| (edge.target, edge.symbols.as_slice()))
    }

    /// The importer `FileId`s that directly import `target` (reverse-dep view).
    ///
    /// Returns an empty slice when `target` is out of range.
    #[must_use]
    pub fn importers_of(&self, target: FileId) -> &[FileId] {
        self.reverse_deps
            .get(target.0 as usize)
            .map_or(&[], Vec::as_slice)
    }

    /// Summarize files that directly import `target`.
    ///
    /// Uses existing reverse dependency and edge indexes. Returns an empty
    /// list when the target is out of range or has no importers.
    #[must_use]
    pub fn direct_importer_summaries(&self, target: FileId) -> Vec<DirectImporterSummary> {
        let Some(importers) = self.reverse_deps.get(target.0 as usize) else {
            return Vec::new();
        };

        let mut summaries = Vec::new();
        for &source in importers {
            let idx = source.0 as usize;
            let Some(source_node) = self.modules.get(idx) else {
                continue;
            };
            let mut symbols = Vec::new();
            for edge in &self.edges[source_node.edge_range.clone()] {
                if edge.target != target {
                    continue;
                }
                symbols.extend(edge.symbols.iter().map(|symbol| ImportedSymbolSummary {
                    imported: imported_name_label(&symbol.imported_name),
                    local: symbol.local_name.clone(),
                    type_only: symbol.is_type_only,
                }));
            }
            symbols.sort_by(|a, b| {
                a.imported
                    .cmp(&b.imported)
                    .then_with(|| a.local.cmp(&b.local))
                    .then_with(|| a.type_only.cmp(&b.type_only))
            });
            symbols.dedup();
            summaries.push(DirectImporterSummary { source, symbols });
        }
        summaries.sort_by_key(|summary| summary.source.0);
        summaries
    }

    /// Find the byte offset of the import statement from `source` to `target`.
    ///
    /// Mixed type/value imports to the same target are stored as one edge. Prefer
    /// the first value-carrying import so runtime-cycle diagnostics and line
    /// suppressions anchor on the import that actually participates in the cycle.
    /// Returns `None` if no edge exists or the edge has no symbols.
    #[must_use]
    pub fn find_import_span_start(&self, source: FileId, target: FileId) -> Option<u32> {
        let idx = source.0 as usize;
        if idx >= self.modules.len() {
            return None;
        }
        let range = &self.modules[idx].edge_range;
        for edge in &self.edges[range.clone()] {
            if edge.target == target {
                return edge
                    .symbols
                    .iter()
                    .find(|s| !s.is_type_only)
                    .or_else(|| edge.symbols.first())
                    .map(|s| s.import_span.start);
            }
        }
        None
    }

    /// Iterate outgoing edges with the data the boundary detector needs in a
    /// single pass: target file id, whether every symbol on the edge is
    /// type-only (matches the predicate used by cycle detection), and the
    /// span start of the first value-carrying symbol (or the first symbol
    /// when every symbol is type-only).
    ///
    /// When `featureB` has both `import type { Foo } from './x'` and
    /// `import { bar } from './x'`, fallow groups them into ONE edge with the
    /// type-only symbol first and the value symbol second. Consumers need the
    /// value span so findings anchor on the runtime import line; otherwise a
    /// `// fallow-ignore-next-line` above the type-only line would silently
    /// suppress the real violation.
    ///
    /// Returns an empty iterator for out-of-range file ids.
    pub fn outgoing_edge_summaries(
        &self,
        file_id: FileId,
    ) -> impl Iterator<Item = (FileId, bool, Option<u32>)> + '_ {
        let idx = file_id.0 as usize;
        let range = if idx < self.modules.len() {
            self.modules[idx].edge_range.clone()
        } else {
            0..0
        };
        self.edges[range].iter().map(|edge| {
            let all_type_only =
                !edge.symbols.is_empty() && edge.symbols.iter().all(|s| s.is_type_only);
            let span = edge
                .symbols
                .iter()
                .find(|s| !s.is_type_only)
                .or_else(|| edge.symbols.first())
                .map(|s| s.import_span.start);
            (edge.target, all_type_only, span)
        })
    }

    /// Like [`Self::outgoing_edge_summaries`] but additionally reports, as a
    /// fourth boolean, whether EVERY non-type-only symbol on the edge has an
    /// `import_span` start in `excluded_span_starts` (`all_client_only`). The
    /// security `client-server-leak` BFS passes the `next/dynamic ssr:false`
    /// dynamic-import span starts so it can skip an edge reached ONLY through the
    /// client-only escape hatch. An edge with no non-type-only symbols, or with at
    /// least one non-type-only symbol whose span is not excluded, reports `false`
    /// (so a target also reached via a real static import stays in the cone).
    ///
    /// Returns an empty iterator for out-of-range file ids.
    pub fn outgoing_edge_summaries_with_exclusions<'a>(
        &'a self,
        file_id: FileId,
        excluded_span_starts: &'a FxHashSet<u32>,
    ) -> impl Iterator<Item = (FileId, bool, Option<u32>, bool)> + 'a {
        let idx = file_id.0 as usize;
        let range = if idx < self.modules.len() {
            self.modules[idx].edge_range.clone()
        } else {
            0..0
        };
        self.edges[range].iter().map(move |edge| {
            let all_type_only =
                !edge.symbols.is_empty() && edge.symbols.iter().all(|s| s.is_type_only);
            let span = edge
                .symbols
                .iter()
                .find(|s| !s.is_type_only)
                .or_else(|| edge.symbols.first())
                .map(|s| s.import_span.start);
            // `all_client_only`: there is at least one non-type-only symbol and
            // every such symbol's import span is in the excluded set. A
            // non-excluded value symbol keeps the edge live.
            let mut value_symbols = edge.symbols.iter().filter(|s| !s.is_type_only).peekable();
            let all_client_only = value_symbols.peek().is_some()
                && value_symbols.all(|s| excluded_span_starts.contains(&s.import_span.start));
            (edge.target, all_type_only, span, all_client_only)
        })
    }
}

fn imported_name_label(name: &ImportedName) -> String {
    match name {
        ImportedName::Named(name) => name.clone(),
        ImportedName::Default => "default".to_string(),
        ImportedName::Namespace => "*".to_string(),
        ImportedName::SideEffect => "side-effect".to_string(),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
    use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource, FileId};
    use fallow_types::extract::{ExportName, ImportInfo, ImportedName, VisibilityTag};
    use std::path::PathBuf;

    fn build_simple_graph() -> ModuleGraph {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/src/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/src/utils.ts"),
                size_bytes: 50,
            },
        ];

        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/src/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];

        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/src/entry.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./utils".to_string(),
                        imported_name: ImportedName::Named("foo".to_string()),
                        local_name: "foo".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/src/utils.ts"),
                exports: vec![
                    fallow_types::extract::ExportInfo {
                        name: ExportName::Named("foo".to_string()),
                        local_name: Some("foo".to_string()),
                        is_type_only: false,
                        visibility: VisibilityTag::None,
                        expected_unused_reason: None,
                        span: oxc_span::Span::new(0, 20),
                        members: vec![],
                        is_side_effect_used: false,
                        super_class: None,
                    },
                    fallow_types::extract::ExportInfo {
                        name: ExportName::Named("bar".to_string()),
                        local_name: Some("bar".to_string()),
                        is_type_only: false,
                        visibility: VisibilityTag::None,
                        expected_unused_reason: None,
                        span: oxc_span::Span::new(25, 45),
                        members: vec![],
                        is_side_effect_used: false,
                        super_class: None,
                    },
                ]
                .into(),
                ..Default::default()
            },
        ];

        ModuleGraph::build(&resolved_modules, &entry_points, &files)
    }

    #[test]
    fn graph_module_count() {
        let graph = build_simple_graph();
        assert_eq!(graph.module_count(), 2);
    }

    #[test]
    fn graph_edge_count() {
        let graph = build_simple_graph();
        assert_eq!(graph.edge_count(), 1);
    }

    #[test]
    fn graph_entry_point_is_reachable() {
        let graph = build_simple_graph();
        assert!(graph.modules[0].is_entry_point());
        assert!(graph.modules[0].is_reachable());
    }

    #[test]
    fn graph_imported_module_is_reachable() {
        let graph = build_simple_graph();
        assert!(!graph.modules[1].is_entry_point());
        assert!(graph.modules[1].is_reachable());
    }

    #[test]
    #[expect(
        clippy::too_many_lines,
        reason = "this test fixture exercises four reachability roles end-to-end; splitting it \
                  would obscure the cross-role assertions"
    )]
    fn graph_distinguishes_runtime_test_and_support_reachability() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/src/main.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/src/runtime-only.ts"),
                size_bytes: 50,
            },
            DiscoveredFile {
                id: FileId(2),
                path: PathBuf::from("/project/tests/app.test.ts"),
                size_bytes: 50,
            },
            DiscoveredFile {
                id: FileId(3),
                path: PathBuf::from("/project/tests/setup.ts"),
                size_bytes: 50,
            },
            DiscoveredFile {
                id: FileId(4),
                path: PathBuf::from("/project/src/covered.ts"),
                size_bytes: 50,
            },
        ];

        let all_entry_points = vec![
            EntryPoint {
                path: PathBuf::from("/project/src/main.ts"),
                source: EntryPointSource::PackageJsonMain,
            },
            EntryPoint {
                path: PathBuf::from("/project/tests/app.test.ts"),
                source: EntryPointSource::TestFile,
            },
            EntryPoint {
                path: PathBuf::from("/project/tests/setup.ts"),
                source: EntryPointSource::Plugin {
                    name: "vitest".to_string(),
                },
            },
        ];
        let runtime_entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/src/main.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let test_entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/tests/app.test.ts"),
            source: EntryPointSource::TestFile,
        }];

        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/src/main.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./runtime-only".to_string(),
                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
                        local_name: "runtimeOnly".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/src/runtime-only.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("runtimeOnly".to_string()),
                    local_name: Some("runtimeOnly".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(2),
                path: PathBuf::from("/project/tests/app.test.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "../src/covered".to_string(),
                        imported_name: ImportedName::Named("covered".to_string()),
                        local_name: "covered".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(4)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(3),
                path: PathBuf::from("/project/tests/setup.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "../src/runtime-only".to_string(),
                        imported_name: ImportedName::Named("runtimeOnly".to_string()),
                        local_name: "runtimeOnly".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(4),
                path: PathBuf::from("/project/src/covered.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("covered".to_string()),
                    local_name: Some("covered".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
        ];

        let graph = ModuleGraph::build_with_reachability_roots(
            &resolved_modules,
            &all_entry_points,
            &runtime_entry_points,
            &test_entry_points,
            &files,
        );

        assert!(graph.modules[1].is_reachable());
        assert!(graph.modules[1].is_runtime_reachable());
        assert!(
            !graph.modules[1].is_test_reachable(),
            "support roots should not make runtime-only modules test reachable"
        );

        assert!(graph.modules[4].is_reachable());
        assert!(graph.modules[4].is_test_reachable());
        assert!(
            !graph.modules[4].is_runtime_reachable(),
            "test-only reachability should stay separate from runtime roots"
        );
    }

    #[test]
    fn graph_export_has_reference() {
        let graph = build_simple_graph();
        let utils = &graph.modules[1];
        let foo_export = utils
            .exports
            .iter()
            .find(|e| e.name.to_string() == "foo")
            .unwrap();
        assert!(
            !foo_export.references.is_empty(),
            "foo should have references"
        );
    }

    #[test]
    fn graph_unused_export_no_reference() {
        let graph = build_simple_graph();
        let utils = &graph.modules[1];
        let bar_export = utils
            .exports
            .iter()
            .find(|e| e.name.to_string() == "bar")
            .unwrap();
        assert!(
            bar_export.references.is_empty(),
            "bar should have no references"
        );
    }

    #[test]
    fn graph_no_namespace_import() {
        let graph = build_simple_graph();
        assert!(!graph.has_namespace_import(FileId(0)));
        assert!(!graph.has_namespace_import(FileId(1)));
    }

    #[test]
    fn graph_has_namespace_import() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                size_bytes: 50,
            },
        ];

        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];

        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./utils".to_string(),
                        imported_name: ImportedName::Namespace,
                        local_name: "utils".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("foo".to_string()),
                    local_name: Some("foo".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
        ];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        assert!(
            graph.has_namespace_import(FileId(1)),
            "utils should have namespace import"
        );
    }

    #[test]
    fn graph_has_namespace_import_out_of_bounds() {
        let graph = build_simple_graph();
        assert!(!graph.has_namespace_import(FileId(999)));
    }

    /// The persisted graph cache skips `namespace_imported` and rebuilds it from
    /// the edge set on load. This asserts the reconstruction reproduces the
    /// fresh-built bitset BIT-FOR-BIT on a graph that exercises `import * as ns`,
    /// matching what `build.rs` records at build time.
    #[test]
    fn reconstruct_namespace_imported_matches_fresh_build() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                size_bytes: 50,
            },
            DiscoveredFile {
                id: FileId(2),
                path: PathBuf::from("/project/named-only.ts"),
                size_bytes: 50,
            },
        ];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                resolved_imports: vec![
                    ResolvedImport {
                        info: ImportInfo {
                            source: "./utils".to_string(),
                            imported_name: ImportedName::Namespace,
                            local_name: "utils".to_string(),
                            is_type_only: false,
                            from_style: false,
                            span: oxc_span::Span::new(0, 10),
                            source_span: oxc_span::Span::default(),
                        },
                        target: ResolveResult::InternalModule(FileId(1)),
                    },
                    ResolvedImport {
                        info: ImportInfo {
                            source: "./named-only".to_string(),
                            imported_name: ImportedName::Named("foo".to_string()),
                            local_name: "foo".to_string(),
                            is_type_only: false,
                            from_style: false,
                            span: oxc_span::Span::new(11, 20),
                            source_span: oxc_span::Span::default(),
                        },
                        target: ResolveResult::InternalModule(FileId(2)),
                    },
                ],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(2),
                path: PathBuf::from("/project/named-only.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("foo".to_string()),
                    local_name: Some("foo".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
        ];

        let mut graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        let fresh = graph.namespace_imported.clone();

        // Sanity: the namespace target is set, the named-only target is not.
        assert!(graph.has_namespace_import(FileId(1)));
        assert!(!graph.has_namespace_import(FileId(2)));

        // Simulate the cache load: the bitset arrives empty (serde-skipped), then
        // the loader reconstructs it from the persisted edges.
        graph.namespace_imported = FixedBitSet::default();
        graph.reconstruct_namespace_imported();

        assert_eq!(
            graph.namespace_imported, fresh,
            "reconstructed namespace_imported must equal the fresh-built bitset"
        );
        assert!(graph.has_namespace_import(FileId(1)));
        assert!(!graph.has_namespace_import(FileId(2)));
    }

    #[test]
    fn graph_unreachable_module() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                size_bytes: 50,
            },
            DiscoveredFile {
                id: FileId(2),
                path: PathBuf::from("/project/orphan.ts"),
                size_bytes: 30,
            },
        ];

        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];

        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./utils".to_string(),
                        imported_name: ImportedName::Named("foo".to_string()),
                        local_name: "foo".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("foo".to_string()),
                    local_name: Some("foo".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(2),
                path: PathBuf::from("/project/orphan.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("orphan".to_string()),
                    local_name: Some("orphan".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
        ];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);

        assert!(graph.modules[0].is_reachable(), "entry should be reachable");
        assert!(graph.modules[1].is_reachable(), "utils should be reachable");
        assert!(
            !graph.modules[2].is_reachable(),
            "orphan should NOT be reachable"
        );
    }

    #[test]
    fn graph_package_usage_tracked() {
        let files = vec![DiscoveredFile {
            id: FileId(0),
            path: PathBuf::from("/project/entry.ts"),
            size_bytes: 100,
        }];

        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];

        let resolved_modules = vec![ResolvedModule {
            file_id: FileId(0),
            path: PathBuf::from("/project/entry.ts"),
            exports: vec![].into(),
            re_exports: vec![],
            resolved_imports: vec![
                ResolvedImport {
                    info: ImportInfo {
                        source: "react".to_string(),
                        imported_name: ImportedName::Default,
                        local_name: "React".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::NpmPackage("react".to_string()),
                },
                ResolvedImport {
                    info: ImportInfo {
                        source: "lodash".to_string(),
                        imported_name: ImportedName::Named("merge".to_string()),
                        local_name: "merge".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(15, 30),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::NpmPackage("lodash".to_string()),
                },
            ],
            ..Default::default()
        }];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        assert!(graph.package_usage.contains_key("react"));
        assert!(graph.package_usage.contains_key("lodash"));
        assert!(!graph.package_usage.contains_key("express"));
    }

    #[test]
    fn graph_empty() {
        let graph = ModuleGraph::build(&[], &[], &[]);
        assert_eq!(graph.module_count(), 0);
        assert_eq!(graph.edge_count(), 0);
    }

    /// The persisted graph cache postcard-encodes the whole `ModuleGraph` and
    /// decodes it on a warm run. This proves the serde round-trip is lossless
    /// for the structural surface analysis reads: module / edge / export /
    /// reference counts and the `namespace_imported` bitset (reconstructed on
    /// load) all survive.
    #[test]
    fn graph_postcard_round_trip_is_lossless() {
        let graph = build_simple_graph();

        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
        let mut decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
        // The store does this on load; do it here so the bitset is restored.
        decoded.reconstruct_namespace_imported();

        assert_eq!(decoded.module_count(), graph.module_count());
        assert_eq!(decoded.edge_count(), graph.edge_count());
        assert_eq!(decoded.namespace_imported, graph.namespace_imported);

        // Export + reference + member surface survives byte-for-byte.
        let utils = &decoded.modules[1];
        let foo = utils
            .exports
            .iter()
            .find(|e| e.name.to_string() == "foo")
            .expect("foo export survives round-trip");
        assert!(!foo.references.is_empty());
        let bar = utils
            .exports
            .iter()
            .find(|e| e.name.to_string() == "bar")
            .expect("bar export survives round-trip");
        assert!(bar.references.is_empty());

        // Reachability flags and entry-point sets survive.
        assert!(decoded.modules[0].is_entry_point());
        assert!(decoded.modules[0].is_reachable());
        assert!(decoded.modules[1].is_reachable());
        assert_eq!(decoded.entry_points, graph.entry_points);
    }

    #[test]
    fn graph_cjs_exports_tracked() {
        let files = vec![DiscoveredFile {
            id: FileId(0),
            path: PathBuf::from("/project/entry.ts"),
            size_bytes: 100,
        }];

        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];

        let resolved_modules = vec![ResolvedModule {
            file_id: FileId(0),
            path: PathBuf::from("/project/entry.ts"),
            has_cjs_exports: true,
            has_angular_component_template_url: false,
            ..Default::default()
        }];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        assert!(graph.modules[0].has_cjs_exports());
    }

    #[test]
    fn graph_edges_for_returns_targets() {
        let graph = build_simple_graph();
        let targets = graph.edges_for(FileId(0));
        assert_eq!(targets, vec![FileId(1)]);
    }

    #[test]
    fn graph_edges_for_no_imports() {
        let graph = build_simple_graph();
        let targets = graph.edges_for(FileId(1));
        assert!(targets.is_empty());
    }

    #[test]
    fn graph_edges_for_out_of_bounds() {
        let graph = build_simple_graph();
        let targets = graph.edges_for(FileId(999));
        assert!(targets.is_empty());
    }

    #[test]
    fn graph_direct_importer_summaries_include_symbols() {
        let graph = build_simple_graph();
        let summaries = graph.direct_importer_summaries(FileId(1));

        assert_eq!(
            summaries,
            vec![DirectImporterSummary {
                source: FileId(0),
                symbols: vec![ImportedSymbolSummary {
                    imported: "foo".to_string(),
                    local: "foo".to_string(),
                    type_only: false,
                }],
            }]
        );
    }

    #[test]
    fn graph_find_import_span_start_found() {
        let graph = build_simple_graph();
        let span_start = graph.find_import_span_start(FileId(0), FileId(1));
        assert!(span_start.is_some());
        assert_eq!(span_start.unwrap(), 0);
    }

    #[test]
    fn graph_find_import_span_start_prefers_value_import_on_mixed_edge() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                size_bytes: 50,
            },
        ];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                resolved_imports: vec![
                    ResolvedImport {
                        info: ImportInfo {
                            source: "./utils".to_string(),
                            imported_name: ImportedName::Named("Foo".to_string()),
                            local_name: "Foo".to_string(),
                            is_type_only: true,
                            from_style: false,
                            span: oxc_span::Span::new(10, 20),
                            source_span: oxc_span::Span::default(),
                        },
                        target: ResolveResult::InternalModule(FileId(1)),
                    },
                    ResolvedImport {
                        info: ImportInfo {
                            source: "./utils".to_string(),
                            imported_name: ImportedName::Named("foo".to_string()),
                            local_name: "foo".to_string(),
                            is_type_only: false,
                            from_style: false,
                            span: oxc_span::Span::new(50, 60),
                            source_span: oxc_span::Span::default(),
                        },
                        target: ResolveResult::InternalModule(FileId(1)),
                    },
                ],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                ..Default::default()
            },
        ];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        assert_eq!(graph.find_import_span_start(FileId(0), FileId(1)), Some(50));
    }

    #[test]
    fn graph_find_import_span_start_wrong_target() {
        let graph = build_simple_graph();
        let span_start = graph.find_import_span_start(FileId(0), FileId(0));
        assert!(span_start.is_none());
    }

    #[test]
    fn graph_find_import_span_start_source_out_of_bounds() {
        let graph = build_simple_graph();
        let span_start = graph.find_import_span_start(FileId(999), FileId(1));
        assert!(span_start.is_none());
    }

    #[test]
    fn graph_find_import_span_start_no_edges() {
        let graph = build_simple_graph();
        let span_start = graph.find_import_span_start(FileId(1), FileId(0));
        assert!(span_start.is_none());
    }

    #[test]
    fn graph_reverse_deps_populated() {
        let graph = build_simple_graph();
        assert!(graph.reverse_deps[1].contains(&FileId(0)));
        assert!(graph.reverse_deps[0].is_empty());
    }

    #[test]
    fn graph_type_only_package_usage_tracked() {
        let files = vec![DiscoveredFile {
            id: FileId(0),
            path: PathBuf::from("/project/entry.ts"),
            size_bytes: 100,
        }];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![ResolvedModule {
            file_id: FileId(0),
            path: PathBuf::from("/project/entry.ts"),
            resolved_imports: vec![
                ResolvedImport {
                    info: ImportInfo {
                        source: "react".to_string(),
                        imported_name: ImportedName::Named("FC".to_string()),
                        local_name: "FC".to_string(),
                        is_type_only: true,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::NpmPackage("react".to_string()),
                },
                ResolvedImport {
                    info: ImportInfo {
                        source: "react".to_string(),
                        imported_name: ImportedName::Named("useState".to_string()),
                        local_name: "useState".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(15, 30),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::NpmPackage("react".to_string()),
                },
            ],
            ..Default::default()
        }];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        assert!(graph.package_usage.contains_key("react"));
        assert!(graph.type_only_package_usage.contains_key("react"));
    }

    #[test]
    fn graph_default_import_reference() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                size_bytes: 50,
            },
        ];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./utils".to_string(),
                        imported_name: ImportedName::Default,
                        local_name: "Utils".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/utils.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Default,
                    local_name: None,
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
        ];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        let utils = &graph.modules[1];
        let default_export = utils
            .exports
            .iter()
            .find(|e| matches!(e.name, ExportName::Default))
            .unwrap();
        assert!(!default_export.references.is_empty());
        assert_eq!(
            default_export.references[0].kind,
            ReferenceKind::DefaultImport
        );
    }

    #[test]
    fn graph_side_effect_import_no_export_reference() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/styles.ts"),
                size_bytes: 50,
            },
        ];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/entry.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./styles".to_string(),
                        imported_name: ImportedName::SideEffect,
                        local_name: String::new(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/styles.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("primaryColor".to_string()),
                    local_name: Some("primaryColor".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
        ];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        assert_eq!(graph.edge_count(), 1);
        let styles = &graph.modules[1];
        let export = &styles.exports[0];
        assert!(
            export.references.is_empty(),
            "side-effect import should not reference named exports"
        );
    }

    #[test]
    fn graph_multiple_entry_points() {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/main.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/worker.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(2),
                path: PathBuf::from("/project/shared.ts"),
                size_bytes: 50,
            },
        ];
        let entry_points = vec![
            EntryPoint {
                path: PathBuf::from("/project/main.ts"),
                source: EntryPointSource::PackageJsonMain,
            },
            EntryPoint {
                path: PathBuf::from("/project/worker.ts"),
                source: EntryPointSource::PackageJsonMain,
            },
        ];
        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/main.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./shared".to_string(),
                        imported_name: ImportedName::Named("helper".to_string()),
                        local_name: "helper".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(2)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/worker.ts"),
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(2),
                path: PathBuf::from("/project/shared.ts"),
                exports: vec![fallow_types::extract::ExportInfo {
                    name: ExportName::Named("helper".to_string()),
                    local_name: Some("helper".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 20),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }]
                .into(),
                ..Default::default()
            },
        ];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        assert!(graph.modules[0].is_entry_point());
        assert!(graph.modules[1].is_entry_point());
        assert!(!graph.modules[2].is_entry_point());
        assert!(graph.modules[0].is_reachable());
        assert!(graph.modules[1].is_reachable());
        assert!(graph.modules[2].is_reachable());
    }
}