1use 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#[derive(Debug, Clone, Copy)]
14pub struct ReachabilityRoots<'a> {
15 pub all: &'a [EntryPoint],
17 pub runtime: &'a [EntryPoint],
19 pub test: &'a [EntryPoint],
21 pub consumer_checked: &'a FxHashSet<FileId>,
25}
26
27#[derive(Debug, serde::Serialize, serde::Deserialize)]
33pub struct ModuleNode {
34 pub file_id: FileId,
36 pub path: PathBuf,
38 pub edge_range: Range<usize>,
40 pub exports: Vec<ExportSymbol>,
42 pub re_exports: Vec<ReExportEdge>,
44 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 #[inline]
57 pub const fn is_entry_point(&self) -> bool {
58 self.flags & FLAG_ENTRY_POINT != 0
59 }
60
61 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 #[inline]
72 pub const fn is_reachable(&self) -> bool {
73 self.flags & FLAG_REACHABLE != 0
74 }
75
76 #[inline]
78 pub const fn is_runtime_reachable(&self) -> bool {
79 self.flags & FLAG_RUNTIME_REACHABLE != 0
80 }
81
82 #[inline]
84 pub const fn is_test_reachable(&self) -> bool {
85 self.flags & FLAG_TEST_REACHABLE != 0
86 }
87
88 #[inline]
90 pub const fn has_cjs_exports(&self) -> bool {
91 self.flags & FLAG_CJS_EXPORTS != 0
92 }
93
94 #[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 #[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 #[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 #[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 #[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 #[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#[derive(Debug, serde::Serialize, serde::Deserialize)]
174pub struct ReExportEdge {
175 pub source_file: FileId,
177 pub imported_name: String,
179 pub exported_name: String,
181 pub is_type_only: bool,
183 #[serde(with = "crate::cache::span_serde")]
187 pub span: oxc_span::Span,
188}
189
190#[derive(Debug, serde::Serialize, serde::Deserialize)]
192pub struct ExportSymbol {
193 pub name: ExportName,
195 pub is_type_only: bool,
197 pub is_side_effect_used: bool,
202 pub visibility: VisibilityTag,
205 pub expected_unused_reason: Option<String>,
207 pub deprecated: bool,
209 pub deprecated_reason: Option<Box<str>>,
211 #[serde(with = "crate::cache::span_serde")]
213 pub span: oxc_span::Span,
214 pub references: Vec<SymbolReference>,
216 #[serde(default)]
225 pub reference_paths: Vec<Option<ReferencePathId>>,
226 #[serde(with = "crate::cache::member_serde")]
233 pub members: Vec<fallow_types::extract::MemberInfo>,
234}
235
236#[derive(Debug, Clone, Copy, serde::Serialize, serde::Deserialize)]
238pub struct SymbolReference {
239 pub from_file: FileId,
241 pub kind: ReferenceKind,
243 pub namespace: super::ExportNamespace,
245 #[serde(with = "crate::cache::span_serde")]
248 pub import_span: oxc_span::Span,
249}
250
251#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
256pub struct ReferencePathId(NonZeroU32);
257
258#[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 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 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 pub(crate) fn reference_path(&self, index: usize) -> Option<ReferencePathId> {
329 self.reference_paths.get(index).copied().flatten()
330 }
331
332 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 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 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#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
382pub(crate) enum ReferencePathNode {
383 Hop {
385 parent: Option<ReferencePathId>,
387 target: FileId,
389 mechanism: ModuleLoadMechanism,
391 },
392 Route {
394 parent: Option<ReferencePathId>,
397 graph: ReferenceRouteGraphId,
399 start: ReferenceRouteNodeId,
401 terminal: ReferenceRouteNodeId,
403 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#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
428pub(crate) struct ReferenceRouteGraphId(pub(crate) u32);
429
430#[derive(
432 Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize, serde::Deserialize,
433)]
434pub(crate) struct ReferenceRouteNodeId(pub(crate) u32);
435
436#[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#[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#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
479pub(crate) struct ReferenceRouteGraph {
480 pub(crate) nodes: Range<u32>,
481}
482
483#[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#[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#[derive(Debug, PartialEq, Eq)]
571pub(crate) struct FinalizedReferencePaths {
572 pub(crate) paths: Vec<ReferencePathNode>,
573 pub(crate) routes: ReferenceRoutes,
574}
575
576pub(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 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 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 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 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 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#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
938pub enum ReferenceKind {
939 NamedImport,
941 DefaultImport,
943 NamespaceImport,
945 ReExport,
947 DynamicImport,
949 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}