Skip to main content

fallow_graph/graph/
types.rs

1//! Shared graph types: module nodes, re-export edges, export symbols, and references.
2
3use std::cmp::Ordering;
4use std::num::NonZeroU32;
5use std::ops::Range;
6use std::path::PathBuf;
7
8use fallow_types::discover::FileId;
9use fallow_types::extract::{ExportName, ModuleLoadMechanism, VisibilityTag};
10use rustc_hash::{FxHashMap, FxHashSet};
11
12/// A single module in the graph.
13///
14/// Boolean flags are packed into a `u8` to keep the struct at 96 bytes
15/// (down from 104 with 5 separate `bool` fields), improving cache line
16/// utilization in hot graph traversal loops.
17#[derive(Debug, serde::Serialize, serde::Deserialize)]
18pub struct ModuleNode {
19    /// Unique identifier for this module.
20    pub file_id: FileId,
21    /// Absolute path to the module file.
22    pub path: PathBuf,
23    /// Range into the flat `edges` array.
24    pub edge_range: Range<usize>,
25    /// Exports declared by this module.
26    pub exports: Vec<ExportSymbol>,
27    /// Re-exports from this module (export { x } from './y', export * from './z').
28    pub re_exports: Vec<ReExportEdge>,
29    /// Packed boolean flags (entry point, reachability, CJS).
30    pub(crate) flags: u8,
31}
32
33const FLAG_ENTRY_POINT: u8 = 1 << 0;
34const FLAG_REACHABLE: u8 = 1 << 1;
35const FLAG_RUNTIME_REACHABLE: u8 = 1 << 2;
36const FLAG_TEST_REACHABLE: u8 = 1 << 3;
37const FLAG_CJS_EXPORTS: u8 = 1 << 4;
38
39impl ModuleNode {
40    /// Whether this module is an entry point.
41    #[inline]
42    pub const fn is_entry_point(&self) -> bool {
43        self.flags & FLAG_ENTRY_POINT != 0
44    }
45
46    /// Whether the export `name` carries a visibility tag such as `@public`
47    /// that marks it as used by code outside the project. Such an export
48    /// exposes what it forwards the same way an entry-point export does.
49    pub(crate) fn export_is_public(&self, name: &str) -> bool {
50        self.exports
51            .iter()
52            .any(|export| export.visibility.suppresses_unused() && export.name.matches_str(name))
53    }
54
55    /// Whether this module is reachable from any entry point.
56    #[inline]
57    pub const fn is_reachable(&self) -> bool {
58        self.flags & FLAG_REACHABLE != 0
59    }
60
61    /// Whether this module is reachable from a runtime/application root.
62    #[inline]
63    pub const fn is_runtime_reachable(&self) -> bool {
64        self.flags & FLAG_RUNTIME_REACHABLE != 0
65    }
66
67    /// Whether this module is reachable from a test root.
68    #[inline]
69    pub const fn is_test_reachable(&self) -> bool {
70        self.flags & FLAG_TEST_REACHABLE != 0
71    }
72
73    /// Whether this module has CJS exports (module.exports / exports.*).
74    #[inline]
75    pub const fn has_cjs_exports(&self) -> bool {
76        self.flags & FLAG_CJS_EXPORTS != 0
77    }
78
79    /// Whether the module object of this module is its forwarded default
80    /// export, as with `import x from './y'; export = x`.
81    ///
82    /// Each read of a member of the module object (`m.run()` on a require
83    /// binding, `import { run }`, `const { run } = require(..)`) reads a member
84    /// of that default export (issue #3392). A file that mixes CommonJS
85    /// exports with an ES `default` re-export also matches. The extra credit
86    /// that follows can only hide a finding, never add one.
87    #[must_use]
88    pub fn forwards_default_as_module_object(&self) -> bool {
89        self.has_cjs_exports()
90            && self
91                .re_exports
92                .iter()
93                .any(|re_export| re_export.exported_name == "default")
94    }
95
96    /// Set whether this module is reachable from any entry point.
97    #[inline]
98    pub fn set_reachable(&mut self, v: bool) {
99        if v {
100            self.flags |= FLAG_REACHABLE;
101        } else {
102            self.flags &= !FLAG_REACHABLE;
103        }
104    }
105
106    /// Set whether this module is reachable from a runtime/application root.
107    #[inline]
108    pub(crate) fn set_runtime_reachable(&mut self, v: bool) {
109        if v {
110            self.flags |= FLAG_RUNTIME_REACHABLE;
111        } else {
112            self.flags &= !FLAG_RUNTIME_REACHABLE;
113        }
114    }
115
116    /// Set whether this module is reachable from a test root.
117    #[inline]
118    pub(crate) fn set_test_reachable(&mut self, v: bool) {
119        if v {
120            self.flags |= FLAG_TEST_REACHABLE;
121        } else {
122            self.flags &= !FLAG_TEST_REACHABLE;
123        }
124    }
125
126    /// Set whether this module has CJS exports.
127    #[inline]
128    pub fn set_cjs_exports(&mut self, v: bool) {
129        if v {
130            self.flags |= FLAG_CJS_EXPORTS;
131        } else {
132            self.flags &= !FLAG_CJS_EXPORTS;
133        }
134    }
135
136    /// Build flags byte from individual booleans (used by graph construction).
137    #[inline]
138    pub(crate) fn flags_from(
139        is_entry_point: bool,
140        is_runtime_reachable: bool,
141        has_cjs_exports: bool,
142    ) -> u8 {
143        let mut f = 0u8;
144        if is_entry_point {
145            f |= FLAG_ENTRY_POINT;
146        }
147        if is_runtime_reachable {
148            f |= FLAG_RUNTIME_REACHABLE;
149        }
150        if has_cjs_exports {
151            f |= FLAG_CJS_EXPORTS;
152        }
153        f
154    }
155}
156
157/// A re-export edge, tracking which exports are forwarded from which module.
158#[derive(Debug, serde::Serialize, serde::Deserialize)]
159pub struct ReExportEdge {
160    /// The module being re-exported from.
161    pub source_file: FileId,
162    /// The name imported from the source (or "*" for star re-exports).
163    pub imported_name: String,
164    /// The name exported from this module.
165    pub exported_name: String,
166    /// Whether this is a type-only re-export.
167    pub is_type_only: bool,
168    /// Source span of the re-export declaration on this module, used for
169    /// line-number reporting. `(0, 0)` for re-exports synthesized inside the
170    /// graph layer (e.g., `export *` chain propagation, namespace narrowing).
171    #[serde(with = "crate::cache::span_serde")]
172    pub span: oxc_span::Span,
173}
174
175/// An export with reference tracking.
176#[derive(Debug, serde::Serialize, serde::Deserialize)]
177pub struct ExportSymbol {
178    /// The exported name (named or default).
179    pub name: ExportName,
180    /// Whether this is a type-only export.
181    pub is_type_only: bool,
182    /// Whether this export is registered through a runtime side effect at module
183    /// load time (e.g. a Lit `@customElement('tag')` decorator or a
184    /// `customElements.define('tag', ClassRef)` call). The unused-export
185    /// detector treats this as an effective reference.
186    pub is_side_effect_used: bool,
187    /// Visibility tag from JSDoc/TSDoc comment (`@public`, `@internal`, `@alpha`, `@beta`).
188    /// Exports with any visibility tag are never reported as unused.
189    pub visibility: VisibilityTag,
190    /// Human-authored reason on `@expected-unused -- <reason>`, when present.
191    pub expected_unused_reason: Option<String>,
192    /// Whether the leading JSDoc carries a `@deprecated` tag.
193    pub deprecated: bool,
194    /// Plain-text `@deprecated` message, `None` for a bare tag.
195    pub deprecated_reason: Option<Box<str>>,
196    /// Source span of the export declaration.
197    #[serde(with = "crate::cache::span_serde")]
198    pub span: oxc_span::Span,
199    /// Which files reference this export.
200    pub references: Vec<SymbolReference>,
201    /// Interned provenance paths parallel to `references`, keyed by reference
202    /// index (issue #2083).
203    ///
204    /// Only populated when the test-reachability plan requires reference
205    /// provenance (a replacement mock exists). It stays empty for every other
206    /// project so the reference list itself remains 16 bytes per entry and the
207    /// side table allocates nothing. Entries can be `None` even when populated:
208    /// legacy reachability stores no path, profiled reachability always does.
209    #[serde(default)]
210    pub reference_paths: Vec<Option<ReferencePathId>>,
211    /// Members of this export (enum members, class members).
212    ///
213    /// `MemberInfo` is a shared `fallow-types` struct whose serde shape is
214    /// serialize-only (its `span` uses `serialize_with` with no matching
215    /// deserializer), so it cannot round-trip through a plain derive. The cache
216    /// routes it through a dedicated lossless mirror in `crate::cache`.
217    #[serde(with = "crate::cache::member_serde")]
218    pub members: Vec<fallow_types::extract::MemberInfo>,
219}
220
221/// A reference to an export from another file.
222#[derive(Debug, Clone, Copy, serde::Serialize, serde::Deserialize)]
223pub struct SymbolReference {
224    /// The file that references this export.
225    pub from_file: FileId,
226    /// How the export is referenced.
227    pub kind: ReferenceKind,
228    /// Semantic namespace used by this reference.
229    pub namespace: super::ExportNamespace,
230    /// Byte span of the import statement in the referencing file.
231    /// Used by the LSP to locate references for Code Lens navigation.
232    #[serde(with = "crate::cache::span_serde")]
233    pub import_span: oxc_span::Span,
234}
235
236/// Compact identifier for an interned reference path.
237///
238/// Opaque outside the graph crate; it only appears in the public API as the
239/// element type of [`ExportSymbol::reference_paths`].
240#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
241pub struct ReferencePathId(NonZeroU32);
242
243/// A symbol reference paired with its optional provenance path while build
244/// passes route it between exports, before it lands in a reference list plus
245/// its provenance side table.
246#[derive(Clone, Copy)]
247pub(crate) struct RoutedReference {
248    pub(crate) reference: SymbolReference,
249    pub(crate) path: Option<ReferencePathId>,
250}
251
252pub(crate) type RoutedReferenceKey = (
253    FileId,
254    oxc_span::Span,
255    Option<ReferencePathId>,
256    super::ExportNamespace,
257);
258
259impl RoutedReference {
260    pub(crate) const fn key(self) -> RoutedReferenceKey {
261        (
262            self.reference.from_file,
263            self.reference.import_span,
264            self.path,
265            self.reference.namespace,
266        )
267    }
268}
269
270impl ExportSymbol {
271    const INLINE_PHYSICAL_REFERENCE_LIMIT: usize = 8;
272
273    /// References that use one semantic namespace.
274    pub fn references_in(
275        &self,
276        namespace: super::ExportNamespace,
277    ) -> impl Iterator<Item = &SymbolReference> {
278        self.references
279            .iter()
280            .filter(move |reference| reference.namespace == namespace)
281    }
282
283    /// Distinct physical reference sites, collapsing Type and Value uses of
284    /// the same import while preserving different resolved routes.
285    pub fn physical_references(&self) -> impl Iterator<Item = &SymbolReference> {
286        let mut seen = (self.references.len() > Self::INLINE_PHYSICAL_REFERENCE_LIMIT)
287            .then(FxHashSet::default);
288        self.references
289            .iter()
290            .enumerate()
291            .filter(move |(index, reference)| {
292                let key = (
293                    reference.from_file,
294                    reference.import_span,
295                    self.reference_path(*index),
296                );
297                if let Some(seen) = &mut seen {
298                    return seen.insert(key);
299                }
300                !(0..*index).any(|prior_index| {
301                    let prior = &self.references[prior_index];
302                    key == (
303                        prior.from_file,
304                        prior.import_span,
305                        self.reference_path(prior_index),
306                    )
307                })
308            })
309            .map(|(_, reference)| reference)
310    }
311
312    /// Provenance path recorded for the reference at `index`, when tracked.
313    pub(crate) fn reference_path(&self, index: usize) -> Option<ReferencePathId> {
314        self.reference_paths.get(index).copied().flatten()
315    }
316
317    /// Whether a reference from `from_file` with this exact provenance path is
318    /// already attached.
319    pub(crate) fn has_reference_from(
320        &self,
321        from_file: FileId,
322        import_span: oxc_span::Span,
323        path: Option<ReferencePathId>,
324        namespace: super::ExportNamespace,
325    ) -> bool {
326        self.references
327            .iter()
328            .enumerate()
329            .any(|(index, reference)| {
330                reference.from_file == from_file
331                    && reference.import_span == import_span
332                    && self.reference_path(index) == path
333                    && reference.namespace == namespace
334            })
335    }
336
337    /// Attach `reference`, recording `path` in the provenance side table.
338    ///
339    /// The side table stays untouched until the first tracked path arrives, so
340    /// projects without replacement mocks never allocate it.
341    pub(crate) fn push_reference(
342        &mut self,
343        reference: SymbolReference,
344        path: Option<ReferencePathId>,
345    ) {
346        if path.is_some() || !self.reference_paths.is_empty() {
347            self.reference_paths.resize(self.references.len(), None);
348            self.reference_paths.push(path);
349        }
350        self.references.push(reference);
351    }
352
353    /// Iterate references together with their recorded provenance paths.
354    pub(crate) fn routed_references(&self) -> impl Iterator<Item = RoutedReference> + '_ {
355        self.references
356            .iter()
357            .enumerate()
358            .map(|(index, reference)| RoutedReference {
359                reference: *reference,
360                path: self.reference_path(index),
361            })
362    }
363}
364
365/// One conjunctive step in an interned export-reference route.
366#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
367pub(crate) enum ReferencePathNode {
368    /// One ordinary module-load hop.
369    Hop {
370        /// Previous conjunctive step, or `None` for a direct load.
371        parent: Option<ReferencePathId>,
372        /// Module loaded by this hop.
373        target: FileId,
374        /// Runtime mechanism used by this hop.
375        mechanism: ModuleLoadMechanism,
376    },
377    /// One existential traversal through a compact namespace transition graph.
378    Route {
379        /// Previous conjunctive step, used when a namespace route is followed
380        /// by another namespace segment.
381        parent: Option<ReferencePathId>,
382        /// Canonical transition graph containing `start` and `terminal`.
383        graph: ReferenceRouteGraphId,
384        /// Local graph node where traversal begins.
385        start: ReferenceRouteNodeId,
386        /// Local graph node that must be reachable.
387        terminal: ReferenceRouteNodeId,
388        /// Mechanism used by the consumer to load `start`. `None` means the
389        /// reference source already owns the start module (entry points and
390        /// concatenated route segments).
391        start_mechanism: Option<ModuleLoadMechanism>,
392    },
393}
394
395impl ReferencePathNode {
396    pub(crate) const fn parent(self) -> Option<ReferencePathId> {
397        match self {
398            Self::Hop { parent, .. } | Self::Route { parent, .. } => parent,
399        }
400    }
401
402    fn remap_parent(&mut self, remap: &[ReferencePathId]) {
403        match self {
404            Self::Hop { parent, .. } | Self::Route { parent, .. } => {
405                *parent = parent.map(|path| remap[path.index()]);
406            }
407        }
408    }
409}
410
411/// Build-time identifier for one compact namespace transition graph.
412#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
413pub(crate) struct ReferenceRouteGraphId(pub(crate) u32);
414
415/// Node identifier local to one namespace transition graph.
416#[derive(
417    Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize, serde::Deserialize,
418)]
419pub(crate) struct ReferenceRouteNodeId(pub(crate) u32);
420
421/// One canonical node in a build-time namespace transition graph.
422#[derive(Debug, Clone, PartialEq, Eq, Hash)]
423pub(crate) struct ReferenceRouteNodeSpec {
424    target: FileId,
425    mechanism: ModuleLoadMechanism,
426    successors: Vec<ReferenceRouteNodeId>,
427}
428
429impl ReferenceRouteNodeSpec {
430    pub(crate) fn new(
431        target: FileId,
432        mechanism: ModuleLoadMechanism,
433        mut successors: Vec<ReferenceRouteNodeId>,
434    ) -> Self {
435        successors.sort_unstable_by_key(|successor| successor.0);
436        successors.dedup();
437        Self {
438            target,
439            mechanism,
440            successors,
441        }
442    }
443}
444
445/// Canonical build-time representation of one namespace transition graph.
446#[derive(Debug, Clone, PartialEq, Eq, Hash)]
447pub(crate) struct ReferenceRouteGraphSpec {
448    nodes: Vec<ReferenceRouteNodeSpec>,
449}
450
451impl ReferenceRouteGraphSpec {
452    pub(crate) fn new(nodes: Vec<ReferenceRouteNodeSpec>) -> Self {
453        debug_assert!(nodes.iter().all(|node| {
454            node.successors
455                .iter()
456                .all(|successor| successor.0 < nodes.len() as u32)
457        }));
458        Self { nodes }
459    }
460}
461
462/// Persisted range for one canonical namespace transition graph.
463#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
464pub(crate) struct ReferenceRouteGraph {
465    pub(crate) nodes: Range<u32>,
466}
467
468/// One persisted namespace transition node.
469#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
470pub(crate) struct ReferenceRouteNode {
471    pub(crate) target: FileId,
472    pub(crate) mechanism: ModuleLoadMechanism,
473    pub(crate) successors: Range<u32>,
474}
475
476/// Cache-friendly persisted namespace transition graphs.
477#[derive(Debug, Default, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
478pub(crate) struct ReferenceRoutes {
479    pub(crate) graphs: Vec<ReferenceRouteGraph>,
480    pub(crate) nodes: Vec<ReferenceRouteNode>,
481    pub(crate) edges: Vec<ReferenceRouteNodeId>,
482}
483
484impl ReferenceRoutes {
485    #[cfg(test)]
486    pub(crate) fn canonical_hops(
487        &self,
488        graph_id: ReferenceRouteGraphId,
489        start: ReferenceRouteNodeId,
490        terminal: ReferenceRouteNodeId,
491        start_mechanism: Option<ModuleLoadMechanism>,
492    ) -> Vec<(FileId, ModuleLoadMechanism)> {
493        let Some(graph) = self.graphs.get(graph_id.0 as usize) else {
494            return Vec::new();
495        };
496        let node_count = graph.nodes.end.saturating_sub(graph.nodes.start) as usize;
497        let start_index = start.0 as usize;
498        let terminal_index = terminal.0 as usize;
499        if start_index >= node_count || terminal_index >= node_count {
500            return Vec::new();
501        }
502
503        let mut predecessor = vec![None; node_count];
504        let mut visited = vec![false; node_count];
505        let mut queue = std::collections::VecDeque::from([start_index]);
506        visited[start_index] = true;
507        while let Some(local_index) = queue.pop_front() {
508            if local_index == terminal_index {
509                break;
510            }
511            let Some(node) = self.nodes.get(graph.nodes.start as usize + local_index) else {
512                return Vec::new();
513            };
514            let Some(successors) = self
515                .edges
516                .get(node.successors.start as usize..node.successors.end as usize)
517            else {
518                return Vec::new();
519            };
520            for successor in successors {
521                let successor_index = successor.0 as usize;
522                if successor_index >= node_count || visited[successor_index] {
523                    continue;
524                }
525                visited[successor_index] = true;
526                predecessor[successor_index] = Some(local_index);
527                queue.push_back(successor_index);
528            }
529        }
530        if !visited[terminal_index] {
531            return Vec::new();
532        }
533
534        let mut hops = Vec::new();
535        let mut current = terminal_index;
536        loop {
537            let node = &self.nodes[graph.nodes.start as usize + current];
538            if current == start_index {
539                if let Some(mechanism) = start_mechanism {
540                    hops.push((node.target, mechanism));
541                }
542                break;
543            }
544            hops.push((node.target, node.mechanism));
545            let Some(parent) = predecessor[current] else {
546                return Vec::new();
547            };
548            current = parent;
549        }
550        hops
551    }
552}
553
554/// Finalized linear paths plus compact namespace transition graphs.
555#[derive(Debug, PartialEq, Eq)]
556pub(crate) struct FinalizedReferencePaths {
557    pub(crate) paths: Vec<ReferencePathNode>,
558    pub(crate) routes: ReferenceRoutes,
559}
560
561/// Build-time interner for shared linked reference paths.
562pub(crate) struct ReferencePathInterner {
563    track_provenance: bool,
564    nodes: Vec<ReferencePathNode>,
565    metadata: Vec<ReferencePathMetadata>,
566    ids: FxHashMap<ReferencePathNode, ReferencePathId>,
567    route_graphs: Vec<ReferenceRouteGraphSpec>,
568    route_graph_ids: FxHashMap<ReferenceRouteGraphSpec, ReferenceRouteGraphId>,
569}
570
571#[derive(Clone, Copy)]
572struct ReferencePathMetadata {
573    depth: usize,
574    hop_target_bounds: Option<(FileId, FileId)>,
575}
576
577impl Default for ReferencePathInterner {
578    fn default() -> Self {
579        Self::new(true)
580    }
581}
582
583impl ReferencePathInterner {
584    pub(crate) fn new(track_provenance: bool) -> Self {
585        Self {
586            track_provenance,
587            nodes: Vec::new(),
588            metadata: Vec::new(),
589            ids: FxHashMap::default(),
590            route_graphs: Vec::new(),
591            route_graph_ids: FxHashMap::default(),
592        }
593    }
594
595    pub(crate) const fn tracks_provenance(&self) -> bool {
596        self.track_provenance
597    }
598
599    /// Intern a direct consumer-to-target path.
600    pub(crate) fn direct(
601        &mut self,
602        target: FileId,
603        mechanism: ModuleLoadMechanism,
604    ) -> Option<ReferencePathId> {
605        self.track_provenance.then(|| {
606            self.intern(ReferencePathNode::Hop {
607                parent: None,
608                target,
609                mechanism,
610            })
611        })
612    }
613
614    /// Append one typed hop to an existing path.
615    pub(crate) fn extend(
616        &mut self,
617        parent: Option<ReferencePathId>,
618        target: FileId,
619        mechanism: ModuleLoadMechanism,
620    ) -> Option<ReferencePathId> {
621        if !self.track_provenance {
622            debug_assert!(parent.is_none());
623            return None;
624        }
625        let Some(parent) = parent else {
626            debug_assert!(false, "tracked reference paths require an interned parent");
627            return None;
628        };
629        let may_contain_target = self
630            .metadata
631            .get(parent.index())
632            .and_then(|metadata| metadata.hop_target_bounds)
633            .is_some_and(|(minimum, maximum)| target.0 >= minimum.0 && target.0 <= maximum.0);
634        if may_contain_target && self.contains_target(parent, target) {
635            return Some(parent);
636        }
637        Some(self.intern(ReferencePathNode::Hop {
638            parent: Some(parent),
639            target,
640            mechanism,
641        }))
642    }
643
644    /// Intern one compact namespace transition graph.
645    pub(crate) fn intern_route_graph(
646        &mut self,
647        graph: ReferenceRouteGraphSpec,
648    ) -> ReferenceRouteGraphId {
649        debug_assert!(self.track_provenance);
650        if let Some(id) = self.route_graph_ids.get(&graph) {
651            return *id;
652        }
653        let id = ReferenceRouteGraphId(self.route_graphs.len() as u32);
654        self.route_graphs.push(graph.clone());
655        self.route_graph_ids.insert(graph, id);
656        id
657    }
658
659    /// Intern one existential traversal through a compact route graph.
660    pub(crate) fn route(
661        &mut self,
662        parent: Option<ReferencePathId>,
663        graph: ReferenceRouteGraphId,
664        start: ReferenceRouteNodeId,
665        terminal: ReferenceRouteNodeId,
666        start_mechanism: Option<ModuleLoadMechanism>,
667    ) -> Option<ReferencePathId> {
668        if !self.track_provenance {
669            return None;
670        }
671        Some(self.intern(ReferencePathNode::Route {
672            parent,
673            graph,
674            start,
675            terminal,
676            start_mechanism,
677        }))
678    }
679
680    fn contains_target(&self, mut path: ReferencePathId, target: FileId) -> bool {
681        loop {
682            let Some(node) = self.nodes.get(path.index()) else {
683                return false;
684            };
685            if let ReferencePathNode::Hop {
686                target: hop_target, ..
687            } = node
688                && *hop_target == target
689            {
690                return true;
691            }
692            let Some(parent) = node.parent() else {
693                return false;
694            };
695            path = parent;
696        }
697    }
698
699    fn intern(&mut self, node: ReferencePathNode) -> ReferencePathId {
700        if let Some(path) = self.ids.get(&node) {
701            return *path;
702        }
703        let path = ReferencePathId::from_index(self.nodes.len());
704        let parent_metadata = node
705            .parent()
706            .and_then(|parent| self.metadata.get(parent.index()).copied());
707        let depth = parent_metadata.map_or(0, |metadata| metadata.depth + 1);
708        let hop_target_bounds = match node {
709            ReferencePathNode::Hop { target, .. } => Some(
710                parent_metadata
711                    .and_then(|metadata| metadata.hop_target_bounds)
712                    .map_or((target, target), |(minimum, maximum)| {
713                        (
714                            FileId(minimum.0.min(target.0)),
715                            FileId(maximum.0.max(target.0)),
716                        )
717                    }),
718            ),
719            ReferencePathNode::Route { .. } => {
720                parent_metadata.and_then(|metadata| metadata.hop_target_bounds)
721            }
722        };
723        self.nodes.push(node);
724        self.metadata.push(ReferencePathMetadata {
725            depth,
726            hop_target_bounds,
727        });
728        self.ids.insert(node, path);
729        path
730    }
731
732    /// Finalize cache-friendly storage and assign canonical IDs.
733    ///
734    /// Paths are ordered depth-by-depth so every parent already has its final
735    /// ID before its children are sorted. This keeps serialized graphs stable
736    /// when equivalent imports or re-exports are discovered in another order.
737    pub(crate) fn finalize(self, modules: &mut [ModuleNode]) -> FinalizedReferencePaths {
738        if self.nodes.is_empty() && self.route_graphs.is_empty() {
739            return FinalizedReferencePaths {
740                paths: Vec::new(),
741                routes: ReferenceRoutes::default(),
742            };
743        }
744
745        let (routes, route_remap) = finalize_route_graphs(&self.route_graphs);
746        let max_depth = self
747            .metadata
748            .iter()
749            .map(|metadata| metadata.depth)
750            .max()
751            .unwrap_or(0);
752
753        let mut paths_by_depth = vec![Vec::new(); max_depth.saturating_add(1)];
754        for (old_index, metadata) in self.metadata.iter().enumerate() {
755            paths_by_depth[metadata.depth].push(old_index);
756        }
757
758        let mut remap = vec![ReferencePathId::from_index(0); self.nodes.len()];
759        let mut finalized = Vec::with_capacity(self.nodes.len());
760        for mut paths in paths_by_depth {
761            paths.sort_unstable_by(|&left, &right| {
762                compare_path_nodes(self.nodes[left], self.nodes[right], &remap, &route_remap)
763            });
764            for old_index in paths {
765                let mut node = self.nodes[old_index];
766                node.remap_parent(&remap);
767                if let ReferencePathNode::Route { graph, .. } = &mut node {
768                    *graph = route_remap[graph.0 as usize];
769                }
770                let canonical = ReferencePathId::from_index(finalized.len());
771                remap[old_index] = canonical;
772                finalized.push(node);
773            }
774        }
775
776        for path in modules
777            .iter_mut()
778            .flat_map(|module| &mut module.exports)
779            .flat_map(|export| &mut export.reference_paths)
780        {
781            if let Some(existing) = *path {
782                *path = Some(remap[existing.index()]);
783            }
784        }
785
786        FinalizedReferencePaths {
787            paths: finalized,
788            routes,
789        }
790    }
791}
792
793fn compare_path_nodes(
794    left: ReferencePathNode,
795    right: ReferencePathNode,
796    path_remap: &[ReferencePathId],
797    route_remap: &[ReferenceRouteGraphId],
798) -> Ordering {
799    let left_parent = left.parent().map(|parent| path_remap[parent.index()].0);
800    let right_parent = right.parent().map(|parent| path_remap[parent.index()].0);
801    left_parent
802        .cmp(&right_parent)
803        .then_with(|| match (left, right) {
804            (
805                ReferencePathNode::Hop {
806                    target: left_target,
807                    mechanism: left_mechanism,
808                    ..
809                },
810                ReferencePathNode::Hop {
811                    target: right_target,
812                    mechanism: right_mechanism,
813                    ..
814                },
815            ) => {
816                (left_target.0, left_mechanism as u8).cmp(&(right_target.0, right_mechanism as u8))
817            }
818            (ReferencePathNode::Hop { .. }, ReferencePathNode::Route { .. }) => Ordering::Less,
819            (ReferencePathNode::Route { .. }, ReferencePathNode::Hop { .. }) => Ordering::Greater,
820            (
821                ReferencePathNode::Route {
822                    graph: left_graph,
823                    start: left_start,
824                    terminal: left_terminal,
825                    start_mechanism: left_mechanism,
826                    ..
827                },
828                ReferencePathNode::Route {
829                    graph: right_graph,
830                    start: right_start,
831                    terminal: right_terminal,
832                    start_mechanism: right_mechanism,
833                    ..
834                },
835            ) => (
836                route_remap[left_graph.0 as usize].0,
837                left_start.0,
838                left_terminal.0,
839                left_mechanism.map(|mechanism| mechanism as u8),
840            )
841                .cmp(&(
842                    route_remap[right_graph.0 as usize].0,
843                    right_start.0,
844                    right_terminal.0,
845                    right_mechanism.map(|mechanism| mechanism as u8),
846                )),
847        })
848}
849
850fn compare_route_graph_specs(
851    left: &ReferenceRouteGraphSpec,
852    right: &ReferenceRouteGraphSpec,
853) -> Ordering {
854    left.nodes.len().cmp(&right.nodes.len()).then_with(|| {
855        left.nodes
856            .iter()
857            .zip(&right.nodes)
858            .find_map(|(left_node, right_node)| {
859                let ordering = (
860                    left_node.target.0,
861                    left_node.mechanism as u8,
862                    &left_node.successors,
863                )
864                    .cmp(&(
865                        right_node.target.0,
866                        right_node.mechanism as u8,
867                        &right_node.successors,
868                    ));
869                (ordering != Ordering::Equal).then_some(ordering)
870            })
871            .unwrap_or(Ordering::Equal)
872    })
873}
874
875fn finalize_route_graphs(
876    graphs: &[ReferenceRouteGraphSpec],
877) -> (ReferenceRoutes, Vec<ReferenceRouteGraphId>) {
878    let mut order: Vec<usize> = (0..graphs.len()).collect();
879    order
880        .sort_unstable_by(|&left, &right| compare_route_graph_specs(&graphs[left], &graphs[right]));
881
882    let mut remap = vec![ReferenceRouteGraphId(0); graphs.len()];
883    let mut finalized = ReferenceRoutes::default();
884    for old_index in order {
885        let graph_id = ReferenceRouteGraphId(finalized.graphs.len() as u32);
886        remap[old_index] = graph_id;
887        let node_start = finalized.nodes.len() as u32;
888        for node in &graphs[old_index].nodes {
889            let edge_start = finalized.edges.len() as u32;
890            finalized.edges.extend_from_slice(&node.successors);
891            finalized.nodes.push(ReferenceRouteNode {
892                target: node.target,
893                mechanism: node.mechanism,
894                successors: edge_start..finalized.edges.len() as u32,
895            });
896        }
897        finalized.graphs.push(ReferenceRouteGraph {
898            nodes: node_start..finalized.nodes.len() as u32,
899        });
900    }
901    (finalized, remap)
902}
903
904impl ReferencePathId {
905    fn from_index(index: usize) -> Self {
906        let Some(encoded) = u32::try_from(index)
907            .ok()
908            .and_then(|index| index.checked_add(1))
909            .and_then(NonZeroU32::new)
910        else {
911            panic!("a process cannot allocate more than u32::MAX reference path nodes");
912        };
913        Self(encoded)
914    }
915
916    pub(crate) const fn index(self) -> usize {
917        (self.0.get() - 1) as usize
918    }
919}
920
921/// How an export is referenced.
922#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
923pub enum ReferenceKind {
924    /// A named import (`import { foo }`).
925    NamedImport,
926    /// A default import (`import Foo`).
927    DefaultImport,
928    /// A namespace import (`import * as ns`).
929    NamespaceImport,
930    /// A re-export (`export { foo } from './bar'`).
931    ReExport,
932    /// A dynamic import (`import('./foo')`).
933    DynamicImport,
934    /// A side-effect import (`import './styles'`).
935    SideEffectImport,
936}
937
938#[cfg(target_pointer_width = "64")]
939const _: () = assert!(std::mem::size_of::<ExportSymbol>() == 152);
940#[cfg(target_pointer_width = "64")]
941const _: () = assert!(std::mem::size_of::<SymbolReference>() == 16);
942#[cfg(target_pointer_width = "64")]
943const _: () = assert!(std::mem::size_of::<ReExportEdge>() == 64);
944#[cfg(all(target_pointer_width = "64", unix))]
945const _: () = assert!(std::mem::size_of::<ModuleNode>() == 96);
946
947#[cfg(test)]
948mod tests {
949    use super::*;
950    use crate::graph::ExportNamespace;
951
952    fn module_with_reference_paths(paths: &[Option<ReferencePathId>]) -> ModuleNode {
953        ModuleNode {
954            file_id: FileId(0),
955            path: PathBuf::from("/project/source.ts"),
956            edge_range: 0..0,
957            exports: vec![ExportSymbol {
958                name: ExportName::Named("value".to_string()),
959                is_type_only: false,
960                is_side_effect_used: false,
961                visibility: VisibilityTag::None,
962                expected_unused_reason: None,
963                span: oxc_span::Span::default(),
964                references: paths
965                    .iter()
966                    .map(|_| SymbolReference {
967                        from_file: FileId(0),
968                        kind: ReferenceKind::NamedImport,
969                        namespace: ExportNamespace::Value,
970                        import_span: oxc_span::Span::default(),
971                    })
972                    .collect(),
973                reference_paths: paths.to_vec(),
974                members: Vec::new(),
975                deprecated: false,
976                deprecated_reason: None,
977            }],
978            re_exports: Vec::new(),
979            flags: 0,
980        }
981    }
982
983    fn export_with_reference_files(files: &[u32]) -> ExportSymbol {
984        ExportSymbol {
985            name: ExportName::Named("value".to_string()),
986            is_type_only: false,
987            is_side_effect_used: false,
988            visibility: VisibilityTag::None,
989            expected_unused_reason: None,
990            span: oxc_span::Span::default(),
991            references: files
992                .iter()
993                .map(|file| SymbolReference {
994                    from_file: FileId(*file),
995                    kind: ReferenceKind::NamedImport,
996                    namespace: ExportNamespace::Value,
997                    import_span: oxc_span::Span::default(),
998                })
999                .collect(),
1000            reference_paths: Vec::new(),
1001            members: Vec::new(),
1002            deprecated: false,
1003            deprecated_reason: None,
1004        }
1005    }
1006
1007    #[test]
1008    fn physical_references_deduplicate_small_and_large_sets() {
1009        let small = export_with_reference_files(&[0, 1, 2, 3, 4, 5, 6, 0]);
1010        let large = export_with_reference_files(&[0, 1, 2, 3, 4, 5, 6, 7, 0]);
1011
1012        assert_eq!(small.physical_references().count(), 7);
1013        assert_eq!(large.physical_references().count(), 8);
1014    }
1015
1016    #[test]
1017    fn reference_path_metadata_tracks_exact_depth_and_hop_bounds() {
1018        let mut interner = ReferencePathInterner::default();
1019        let root = interner
1020            .direct(FileId(10), ModuleLoadMechanism::EsModule)
1021            .expect("tracked interner must return a path");
1022        let lower = interner
1023            .extend(Some(root), FileId(5), ModuleLoadMechanism::EsModule)
1024            .expect("tracked interner must extend a path");
1025        let upper = interner
1026            .extend(Some(lower), FileId(20), ModuleLoadMechanism::EsModule)
1027            .expect("tracked interner must extend a path");
1028
1029        assert_eq!(interner.metadata[root.index()].depth, 0);
1030        assert_eq!(
1031            interner.metadata[lower.index()].hop_target_bounds,
1032            Some((FileId(5), FileId(10)))
1033        );
1034        assert_eq!(interner.metadata[upper.index()].depth, 2);
1035        assert_eq!(
1036            interner.metadata[upper.index()].hop_target_bounds,
1037            Some((FileId(5), FileId(20)))
1038        );
1039
1040        let repeated = interner.extend(Some(upper), FileId(10), ModuleLoadMechanism::EsModule);
1041        assert_eq!(repeated, Some(upper));
1042    }
1043
1044    #[test]
1045    fn finalized_reference_paths_are_independent_of_interning_order() {
1046        let mut first = ReferencePathInterner::default();
1047        let first_parent = first.direct(FileId(1), ModuleLoadMechanism::EsModule);
1048        let first_direct = first.direct(FileId(2), ModuleLoadMechanism::CommonJsRequire);
1049        let first_chain = first.extend(first_parent, FileId(3), ModuleLoadMechanism::EsModule);
1050        let mut first_modules = vec![module_with_reference_paths(&[first_direct, first_chain])];
1051        let first_nodes = first.finalize(&mut first_modules);
1052
1053        let mut second = ReferencePathInterner::default();
1054        let second_direct = second.direct(FileId(2), ModuleLoadMechanism::CommonJsRequire);
1055        let second_parent = second.direct(FileId(1), ModuleLoadMechanism::EsModule);
1056        let second_chain = second.extend(second_parent, FileId(3), ModuleLoadMechanism::EsModule);
1057        let mut second_modules = vec![module_with_reference_paths(&[second_direct, second_chain])];
1058        let second_nodes = second.finalize(&mut second_modules);
1059
1060        assert_eq!(first_nodes, second_nodes);
1061        assert_eq!(
1062            first_modules[0].exports[0].reference_paths,
1063            second_modules[0].exports[0].reference_paths
1064        );
1065    }
1066
1067    fn two_hop_route(first: FileId, second: FileId) -> ReferenceRouteGraphSpec {
1068        ReferenceRouteGraphSpec::new(vec![
1069            ReferenceRouteNodeSpec::new(
1070                first,
1071                ModuleLoadMechanism::EsModule,
1072                vec![ReferenceRouteNodeId(1)],
1073            ),
1074            ReferenceRouteNodeSpec::new(second, ModuleLoadMechanism::EsModule, Vec::new()),
1075        ])
1076    }
1077
1078    #[test]
1079    fn finalized_reference_routes_are_independent_of_interning_order() {
1080        let route_a = two_hop_route(FileId(1), FileId(2));
1081        let route_b = two_hop_route(FileId(3), FileId(4));
1082
1083        let mut first = ReferencePathInterner::default();
1084        let first_a = first.intern_route_graph(route_a.clone());
1085        let first_b = first.intern_route_graph(route_b.clone());
1086        let first_b_path = first.route(
1087            None,
1088            first_b,
1089            ReferenceRouteNodeId(0),
1090            ReferenceRouteNodeId(1),
1091            Some(ModuleLoadMechanism::CommonJsRequire),
1092        );
1093        let first_a_path = first.route(
1094            None,
1095            first_a,
1096            ReferenceRouteNodeId(0),
1097            ReferenceRouteNodeId(1),
1098            Some(ModuleLoadMechanism::EsModule),
1099        );
1100        let mut first_modules = vec![module_with_reference_paths(&[first_b_path, first_a_path])];
1101        let first_paths = first.finalize(&mut first_modules);
1102
1103        let mut second = ReferencePathInterner::default();
1104        let second_b = second.intern_route_graph(route_b);
1105        let second_a = second.intern_route_graph(route_a);
1106        let second_b_path = second.route(
1107            None,
1108            second_b,
1109            ReferenceRouteNodeId(0),
1110            ReferenceRouteNodeId(1),
1111            Some(ModuleLoadMechanism::CommonJsRequire),
1112        );
1113        let second_a_path = second.route(
1114            None,
1115            second_a,
1116            ReferenceRouteNodeId(0),
1117            ReferenceRouteNodeId(1),
1118            Some(ModuleLoadMechanism::EsModule),
1119        );
1120        let mut second_modules = vec![module_with_reference_paths(&[second_b_path, second_a_path])];
1121        let second_paths = second.finalize(&mut second_modules);
1122
1123        assert_eq!(first_paths, second_paths);
1124        assert_eq!(
1125            first_modules[0].exports[0].reference_paths,
1126            second_modules[0].exports[0].reference_paths
1127        );
1128    }
1129
1130    #[test]
1131    fn push_reference_without_paths_never_allocates_the_side_table() {
1132        let mut export = ExportSymbol {
1133            name: ExportName::Named("value".to_string()),
1134            is_type_only: false,
1135            is_side_effect_used: false,
1136            visibility: VisibilityTag::None,
1137            expected_unused_reason: None,
1138            span: oxc_span::Span::default(),
1139            references: Vec::new(),
1140            reference_paths: Vec::new(),
1141            members: Vec::new(),
1142            deprecated: false,
1143            deprecated_reason: None,
1144        };
1145        for id in 0..3 {
1146            export.push_reference(
1147                SymbolReference {
1148                    from_file: FileId(id),
1149                    kind: ReferenceKind::NamedImport,
1150                    namespace: ExportNamespace::Value,
1151                    import_span: oxc_span::Span::default(),
1152                },
1153                None,
1154            );
1155        }
1156        assert_eq!(export.references.len(), 3);
1157        assert!(export.reference_paths.is_empty());
1158        assert_eq!(export.reference_paths.capacity(), 0);
1159        assert_eq!(export.reference_path(1), None);
1160        assert!(export.has_reference_from(
1161            FileId(1),
1162            oxc_span::Span::default(),
1163            None,
1164            ExportNamespace::Value
1165        ));
1166        assert!(!export.has_reference_from(
1167            FileId(9),
1168            oxc_span::Span::default(),
1169            None,
1170            ExportNamespace::Value
1171        ));
1172    }
1173
1174    #[test]
1175    fn push_reference_backfills_the_side_table_on_the_first_tracked_path() {
1176        let mut export = ExportSymbol {
1177            name: ExportName::Named("value".to_string()),
1178            is_type_only: false,
1179            is_side_effect_used: false,
1180            visibility: VisibilityTag::None,
1181            expected_unused_reason: None,
1182            span: oxc_span::Span::default(),
1183            references: Vec::new(),
1184            reference_paths: Vec::new(),
1185            members: Vec::new(),
1186            deprecated: false,
1187            deprecated_reason: None,
1188        };
1189        let reference = SymbolReference {
1190            from_file: FileId(0),
1191            kind: ReferenceKind::NamedImport,
1192            namespace: ExportNamespace::Value,
1193            import_span: oxc_span::Span::default(),
1194        };
1195        export.push_reference(reference, None);
1196        let tracked = ReferencePathId::from_index(4);
1197        export.push_reference(reference, Some(tracked));
1198        export.push_reference(reference, None);
1199
1200        assert_eq!(export.reference_paths, vec![None, Some(tracked), None]);
1201        assert_eq!(export.reference_path(0), None);
1202        assert_eq!(export.reference_path(1), Some(tracked));
1203        assert!(export.has_reference_from(
1204            FileId(0),
1205            reference.import_span,
1206            Some(tracked),
1207            ExportNamespace::Value
1208        ));
1209        assert!(!export.has_reference_from(
1210            FileId(0),
1211            reference.import_span,
1212            Some(ReferencePathId::from_index(7)),
1213            ExportNamespace::Value
1214        ));
1215    }
1216
1217    #[test]
1218    fn module_node_construction() {
1219        let mut node = ModuleNode {
1220            file_id: FileId(0),
1221            path: PathBuf::from("/project/src/index.ts"),
1222            edge_range: 0..5,
1223            exports: vec![],
1224            re_exports: vec![],
1225            flags: ModuleNode::flags_from(true, true, false),
1226        };
1227        node.set_reachable(true);
1228        assert_eq!(node.file_id, FileId(0));
1229        assert!(node.is_entry_point());
1230        assert!(node.is_reachable());
1231        assert!(node.is_runtime_reachable());
1232        assert!(!node.is_test_reachable());
1233        assert!(!node.has_cjs_exports());
1234        assert_eq!(node.edge_range, 0..5);
1235    }
1236
1237    #[test]
1238    fn module_node_non_entry_unreachable() {
1239        let node = ModuleNode {
1240            file_id: FileId(5),
1241            path: PathBuf::from("/project/src/orphan.ts"),
1242            edge_range: 0..0,
1243            exports: vec![],
1244            re_exports: vec![],
1245            flags: ModuleNode::flags_from(false, false, false),
1246        };
1247        assert!(!node.is_entry_point());
1248        assert!(!node.is_reachable());
1249        assert!(!node.is_runtime_reachable());
1250        assert!(!node.is_test_reachable());
1251        assert!(node.edge_range.is_empty());
1252    }
1253
1254    #[test]
1255    fn module_node_cjs_exports() {
1256        let mut node = ModuleNode {
1257            file_id: FileId(2),
1258            path: PathBuf::from("/project/lib/legacy.js"),
1259            edge_range: 3..7,
1260            exports: vec![],
1261            re_exports: vec![],
1262            flags: ModuleNode::flags_from(false, true, true),
1263        };
1264        node.set_reachable(true);
1265        assert!(node.has_cjs_exports());
1266        assert!(node.is_runtime_reachable());
1267        assert_eq!(node.edge_range.len(), 4);
1268    }
1269
1270    #[test]
1271    fn module_node_with_exports_and_re_exports() {
1272        let node = ModuleNode {
1273            file_id: FileId(1),
1274            path: PathBuf::from("/project/src/barrel.ts"),
1275            edge_range: 0..3,
1276            exports: vec![ExportSymbol {
1277                name: ExportName::Named("localFn".to_string()),
1278                is_type_only: false,
1279                is_side_effect_used: false,
1280                visibility: VisibilityTag::None,
1281                expected_unused_reason: None,
1282                span: oxc_span::Span::new(0, 20),
1283                references: vec![],
1284                reference_paths: Vec::new(),
1285                members: vec![],
1286                deprecated: false,
1287                deprecated_reason: None,
1288            }],
1289            re_exports: vec![ReExportEdge {
1290                source_file: FileId(2),
1291                imported_name: "*".to_string(),
1292                exported_name: "*".to_string(),
1293                is_type_only: false,
1294                span: oxc_span::Span::default(),
1295            }],
1296            flags: ModuleNode::flags_from(false, true, false),
1297        };
1298        assert_eq!(node.exports.len(), 1);
1299        assert_eq!(node.re_exports.len(), 1);
1300        assert_eq!(node.re_exports[0].source_file, FileId(2));
1301    }
1302}