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