1use 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#[derive(Debug, serde::Serialize, serde::Deserialize)]
18pub struct ModuleNode {
19 pub file_id: FileId,
21 pub path: PathBuf,
23 pub edge_range: Range<usize>,
25 pub exports: Vec<ExportSymbol>,
27 pub re_exports: Vec<ReExportEdge>,
29 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 #[inline]
42 pub const fn is_entry_point(&self) -> bool {
43 self.flags & FLAG_ENTRY_POINT != 0
44 }
45
46 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 #[inline]
57 pub const fn is_reachable(&self) -> bool {
58 self.flags & FLAG_REACHABLE != 0
59 }
60
61 #[inline]
63 pub const fn is_runtime_reachable(&self) -> bool {
64 self.flags & FLAG_RUNTIME_REACHABLE != 0
65 }
66
67 #[inline]
69 pub const fn is_test_reachable(&self) -> bool {
70 self.flags & FLAG_TEST_REACHABLE != 0
71 }
72
73 #[inline]
75 pub const fn has_cjs_exports(&self) -> bool {
76 self.flags & FLAG_CJS_EXPORTS != 0
77 }
78
79 #[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 #[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 #[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 #[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 #[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 #[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#[derive(Debug, serde::Serialize, serde::Deserialize)]
159pub struct ReExportEdge {
160 pub source_file: FileId,
162 pub imported_name: String,
164 pub exported_name: String,
166 pub is_type_only: bool,
168 #[serde(with = "crate::cache::span_serde")]
172 pub span: oxc_span::Span,
173}
174
175#[derive(Debug, serde::Serialize, serde::Deserialize)]
177pub struct ExportSymbol {
178 pub name: ExportName,
180 pub is_type_only: bool,
182 pub is_side_effect_used: bool,
187 pub visibility: VisibilityTag,
190 pub expected_unused_reason: Option<String>,
192 pub deprecated: bool,
194 pub deprecated_reason: Option<Box<str>>,
196 #[serde(with = "crate::cache::span_serde")]
198 pub span: oxc_span::Span,
199 pub references: Vec<SymbolReference>,
201 #[serde(default)]
210 pub reference_paths: Vec<Option<ReferencePathId>>,
211 #[serde(with = "crate::cache::member_serde")]
218 pub members: Vec<fallow_types::extract::MemberInfo>,
219}
220
221#[derive(Debug, Clone, Copy, serde::Serialize, serde::Deserialize)]
223pub struct SymbolReference {
224 pub from_file: FileId,
226 pub kind: ReferenceKind,
228 pub namespace: super::ExportNamespace,
230 #[serde(with = "crate::cache::span_serde")]
233 pub import_span: oxc_span::Span,
234}
235
236#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
241pub struct ReferencePathId(NonZeroU32);
242
243#[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 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 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 pub(crate) fn reference_path(&self, index: usize) -> Option<ReferencePathId> {
314 self.reference_paths.get(index).copied().flatten()
315 }
316
317 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 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 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#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
367pub(crate) enum ReferencePathNode {
368 Hop {
370 parent: Option<ReferencePathId>,
372 target: FileId,
374 mechanism: ModuleLoadMechanism,
376 },
377 Route {
379 parent: Option<ReferencePathId>,
382 graph: ReferenceRouteGraphId,
384 start: ReferenceRouteNodeId,
386 terminal: ReferenceRouteNodeId,
388 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#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
413pub(crate) struct ReferenceRouteGraphId(pub(crate) u32);
414
415#[derive(
417 Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize, serde::Deserialize,
418)]
419pub(crate) struct ReferenceRouteNodeId(pub(crate) u32);
420
421#[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#[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#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
464pub(crate) struct ReferenceRouteGraph {
465 pub(crate) nodes: Range<u32>,
466}
467
468#[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#[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#[derive(Debug, PartialEq, Eq)]
556pub(crate) struct FinalizedReferencePaths {
557 pub(crate) paths: Vec<ReferencePathNode>,
558 pub(crate) routes: ReferenceRoutes,
559}
560
561pub(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 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 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 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 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 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#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
923pub enum ReferenceKind {
924 NamedImport,
926 DefaultImport,
928 NamespaceImport,
930 ReExport,
932 DynamicImport,
934 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}