Skip to main content

fallow_graph/graph/
reachability.rs

1//! Phase 3: BFS reachability from entry points.
2
3use std::collections::VecDeque;
4
5use fixedbitset::FixedBitSet;
6use rustc_hash::{FxHashMap, FxHashSet};
7
8use crate::resolve::ResolvedReplacedModuleTarget;
9use fallow_types::discover::FileId;
10use fallow_types::extract::ModuleLoadMechanism;
11
12use super::{Edge, ModuleGraph, TestReachabilityIndex};
13
14/// Upper bound on distinct replacement-mask profiles before profiled
15/// reachability falls back to the legacy coarse bitset pass.
16///
17/// Follows the `re_export_transition_safety_cap` precedent of bounding an
18/// otherwise unbounded blowup. `TestReachabilityIndex` storage is
19/// O(files * profile_count / 64) u64 words and worklist propagation touches
20/// every profile word per edge visit, so at 1024 profiles each file costs 16
21/// words (128 bytes): about 12 MiB of index for a 100k-file monorepo. Beyond
22/// that the memory and propagation cost outweigh the masking precision, and
23/// the legacy pass is a safe over-approximation (fail-open, pre-#2068
24/// behavior).
25const PROFILE_COUNT_SAFETY_CAP: usize = 1024;
26
27#[derive(Debug, PartialEq, Eq)]
28pub(super) struct TestReachabilityProfile {
29    masked_targets: Vec<FileId>,
30    roots: Vec<FileId>,
31}
32
33pub(super) enum TestReachabilityPlan<'roots> {
34    NoRoots,
35    Legacy {
36        roots: &'roots FxHashSet<FileId>,
37        /// True when replacement masks exist but their profile count passed
38        /// [`PROFILE_COUNT_SAFETY_CAP`], so masking is off.
39        capped: bool,
40    },
41    Profiled {
42        profiles: Vec<TestReachabilityProfile>,
43    },
44}
45
46impl<'roots> TestReachabilityPlan<'roots> {
47    pub(super) fn new(
48        test_entry_points: &'roots FxHashSet<FileId>,
49        replaced_module_targets: &[ResolvedReplacedModuleTarget],
50        total_capacity: usize,
51    ) -> Self {
52        if test_entry_points.is_empty() {
53            return Self::NoRoots;
54        }
55
56        let mut targets_by_root: FxHashMap<FileId, Vec<FileId>> = FxHashMap::default();
57        for replacement in replaced_module_targets {
58            if test_entry_points.contains(&replacement.source_file)
59                && (replacement.target_file.0 as usize) < total_capacity
60            {
61                targets_by_root
62                    .entry(replacement.source_file)
63                    .or_default()
64                    .push(replacement.target_file);
65            }
66        }
67        for targets in targets_by_root.values_mut() {
68            targets.sort_unstable_by_key(|target| target.0);
69            targets.dedup();
70        }
71
72        if targets_by_root.is_empty() {
73            return Self::Legacy {
74                roots: test_entry_points,
75                capped: false,
76            };
77        }
78
79        let mut roots_by_mask: FxHashMap<Vec<FileId>, Vec<FileId>> = FxHashMap::default();
80        for &root in test_entry_points {
81            let mask = targets_by_root.remove(&root).unwrap_or_default();
82            roots_by_mask.entry(mask).or_default().push(root);
83        }
84
85        if roots_by_mask.len() > PROFILE_COUNT_SAFETY_CAP {
86            tracing::warn!(
87                profile_count = roots_by_mask.len(),
88                safety_cap = PROFILE_COUNT_SAFETY_CAP,
89                "Test-reachability profile count exceeded its safety cap; \
90                 falling back to coarse test reachability without replacement \
91                 masking. Mocked modules stay test-reachable (fail-open)."
92            );
93            return Self::Legacy {
94                roots: test_entry_points,
95                capped: true,
96            };
97        }
98
99        let mut profiles: Vec<_> = roots_by_mask
100            .into_iter()
101            .map(|(masked_targets, mut roots)| {
102                roots.sort_unstable_by_key(|root| root.0);
103                roots.dedup();
104                TestReachabilityProfile {
105                    masked_targets,
106                    roots,
107                }
108            })
109            .collect();
110        profiles.sort_by(|left, right| {
111            left.masked_targets
112                .iter()
113                .map(|file_id| file_id.0)
114                .cmp(right.masked_targets.iter().map(|file_id| file_id.0))
115        });
116
117        Self::Profiled { profiles }
118    }
119
120    pub(super) const fn requires_reference_provenance(&self) -> bool {
121        matches!(self, Self::Profiled { .. })
122    }
123}
124
125enum TestReachability {
126    NoRoots,
127    Legacy {
128        reachable: FixedBitSet,
129        capped: bool,
130    },
131    Profiled {
132        reachable: FixedBitSet,
133        index: TestReachabilityIndex,
134        #[cfg(test)]
135        dirty_word_pops: usize,
136    },
137}
138
139impl TestReachability {
140    fn into_parts(self) -> (Option<FixedBitSet>, TestReachabilityIndex) {
141        match self {
142            Self::NoRoots => (None, TestReachabilityIndex::default()),
143            Self::Legacy { reachable, capped } => (
144                Some(reachable),
145                TestReachabilityIndex {
146                    masking_capped: capped,
147                    ..TestReachabilityIndex::default()
148                },
149            ),
150            Self::Profiled {
151                reachable, index, ..
152            } => (Some(reachable), index),
153        }
154    }
155
156    #[cfg(test)]
157    const fn dirty_word_pop_count(&self) -> usize {
158        match self {
159            Self::Profiled {
160                dirty_word_pops, ..
161            } => *dirty_word_pops,
162            Self::NoRoots | Self::Legacy { .. } => 0,
163        }
164    }
165}
166
167/// Owns the transient state for one bit-parallel profiled reachability pass.
168///
169/// Only `index` and `all_reachable` survive the pass. Pending deltas, queue
170/// membership, and the target-sparse mask map remain local to propagation.
171struct ProfileWorklist {
172    index: TestReachabilityIndex,
173    masked_profiles: FxHashMap<FileId, Vec<u64>>,
174    all_reachable: FixedBitSet,
175    pending_profiles: Vec<u64>,
176    queued: FixedBitSet,
177    queue: VecDeque<(FileId, usize)>,
178    dirty_word_pops: usize,
179}
180
181impl ProfileWorklist {
182    fn new(profiles: &[TestReachabilityProfile], total_capacity: usize) -> Self {
183        let profile_count = profiles.len();
184        let mut index = TestReachabilityIndex::new(total_capacity, profile_count);
185        index.profile_roots = profiles
186            .iter()
187            .map(|profile| profile.roots.clone())
188            .collect();
189        let words_per_file = index.words_per_file;
190        let mut masked_profiles: FxHashMap<FileId, Vec<u64>> = FxHashMap::default();
191
192        for (profile, reachability_profile) in profiles.iter().enumerate() {
193            let word_index = profile / u64::BITS as usize;
194            let profile_bit = 1_u64 << (profile % u64::BITS as usize);
195            for &target in &reachability_profile.masked_targets {
196                masked_profiles
197                    .entry(target)
198                    .or_insert_with(|| vec![0; words_per_file])[word_index] |= profile_bit;
199            }
200        }
201
202        let pending_profiles = vec![0_u64; index.reachable_profiles.len()];
203        let mut worklist = Self {
204            index,
205            masked_profiles,
206            all_reachable: FixedBitSet::with_capacity(total_capacity),
207            pending_profiles,
208            queued: FixedBitSet::with_capacity(total_capacity.saturating_mul(words_per_file)),
209            queue: VecDeque::new(),
210            dirty_word_pops: 0,
211        };
212
213        for (profile, reachability_profile) in profiles.iter().enumerate() {
214            let word_index = profile / u64::BITS as usize;
215            let profile_bit = 1_u64 << (profile % u64::BITS as usize);
216            for &root in &reachability_profile.roots {
217                let root_index = root.0 as usize;
218                if root_index >= total_capacity {
219                    continue;
220                }
221                let Some(slot) = root_index
222                    .checked_mul(words_per_file)
223                    .and_then(|start| start.checked_add(word_index))
224                else {
225                    continue;
226                };
227                let Some(reachable_word) = worklist.index.reachable_profiles.get_mut(slot) else {
228                    continue;
229                };
230                if *reachable_word & profile_bit != 0 {
231                    continue;
232                }
233                *reachable_word |= profile_bit;
234                worklist.pending_profiles[slot] |= profile_bit;
235                worklist.all_reachable.insert(root_index);
236                if !worklist.queued.contains(slot) {
237                    worklist.queued.insert(slot);
238                    worklist.queue.push_back((root, word_index));
239                }
240            }
241        }
242
243        worklist
244    }
245
246    fn run(mut self, graph: &ModuleGraph) -> (FixedBitSet, TestReachabilityIndex, usize) {
247        let words_per_file = self.index.words_per_file;
248
249        while let Some((file_id, word_index)) = self.queue.pop_front() {
250            self.dirty_word_pops += 1;
251            let file_index = file_id.0 as usize;
252            let Some(source_slot) = file_index
253                .checked_mul(words_per_file)
254                .and_then(|start| start.checked_add(word_index))
255            else {
256                continue;
257            };
258            self.queued.remove(source_slot);
259            let Some(source_delta) = self.pending_profiles.get_mut(source_slot) else {
260                continue;
261            };
262            let delta_word = *source_delta;
263            *source_delta = 0;
264            if delta_word == 0 {
265                continue;
266            }
267
268            let Some(module) = graph.modules.get(file_index) else {
269                continue;
270            };
271            for edge in &graph.edges[module.edge_range.clone()] {
272                let target_idx = edge.target.0 as usize;
273                if target_idx >= self.all_reachable.len() || !edge.runs_target_code_in_tests() {
274                    continue;
275                }
276                let Some(target_slot) = target_idx
277                    .checked_mul(words_per_file)
278                    .and_then(|start| start.checked_add(word_index))
279                else {
280                    continue;
281                };
282                let edge_is_esm_only = edge.symbols.iter().all(|symbol| {
283                    !matches!(symbol.mechanism, ModuleLoadMechanism::CommonJsRequire)
284                });
285                let edge_mask = if edge_is_esm_only {
286                    self.masked_profiles.get(&edge.target)
287                } else {
288                    None
289                };
290
291                let propagated = edge_mask
292                    .and_then(|mask| mask.get(word_index))
293                    .map_or(delta_word, |mask_word| delta_word & !mask_word);
294                let Some(reachable_word) = self.index.reachable_profiles.get_mut(target_slot)
295                else {
296                    continue;
297                };
298                let new_profiles = propagated & !*reachable_word;
299                if new_profiles == 0 {
300                    continue;
301                }
302                *reachable_word |= new_profiles;
303                self.pending_profiles[target_slot] |= new_profiles;
304
305                self.all_reachable.insert(target_idx);
306                if !self.queued.contains(target_slot) {
307                    self.queued.insert(target_slot);
308                    self.queue.push_back((edge.target, word_index));
309                }
310            }
311        }
312
313        self.index.set_sparse_masks(self.masked_profiles);
314        (self.all_reachable, self.index, self.dirty_word_pops)
315    }
316}
317
318impl ModuleGraph {
319    /// BFS over the edge list from `entry_points`.
320    ///
321    /// Reads edges only, so the result is stable from the moment
322    /// `populate_edges` finishes; the graph build calls it once and hands the
323    /// same bitset to the exposed namespace closure and to `mark_reachable`.
324    pub(super) fn collect_reachable(
325        &self,
326        entry_points: &FxHashSet<FileId>,
327        total_capacity: usize,
328    ) -> FixedBitSet {
329        self.collect_reachable_along(entry_points, total_capacity, Edge::runs_target_code)
330    }
331
332    /// BFS over the edges that `follows` accepts.
333    fn collect_reachable_along(
334        &self,
335        entry_points: &FxHashSet<FileId>,
336        total_capacity: usize,
337        follows: fn(&Edge) -> bool,
338    ) -> FixedBitSet {
339        #[cfg(test)]
340        tests::record_traversal();
341
342        let mut visited = FixedBitSet::with_capacity(total_capacity);
343        let mut queue = VecDeque::new();
344
345        for &ep_id in entry_points {
346            if (ep_id.0 as usize) < total_capacity {
347                visited.insert(ep_id.0 as usize);
348                queue.push_back(ep_id);
349            }
350        }
351
352        while let Some(file_id) = queue.pop_front() {
353            if (file_id.0 as usize) >= self.modules.len() {
354                continue;
355            }
356            let module = &self.modules[file_id.0 as usize];
357            for edge in &self.edges[module.edge_range.clone()] {
358                // An asset reference keeps its target in use through
359                // `has_reachable_importer`, but the target never runs, so its
360                // own imports stay out of reach.
361                if !follows(edge) {
362                    continue;
363                }
364                let target_idx = edge.target.0 as usize;
365                if target_idx < total_capacity && !visited.contains(target_idx) {
366                    visited.insert(target_idx);
367                    queue.push_back(edge.target);
368                }
369            }
370        }
371
372        visited
373    }
374
375    fn collect_profiled_reachable(
376        &self,
377        profiles: &[TestReachabilityProfile],
378        total_capacity: usize,
379    ) -> (FixedBitSet, TestReachabilityIndex, usize) {
380        #[cfg(test)]
381        tests::record_traversal();
382
383        ProfileWorklist::new(profiles, total_capacity).run(self)
384    }
385
386    fn collect_test_reachable(
387        &self,
388        plan: TestReachabilityPlan<'_>,
389        total_capacity: usize,
390    ) -> TestReachability {
391        match plan {
392            TestReachabilityPlan::NoRoots => TestReachability::NoRoots,
393            TestReachabilityPlan::Legacy { roots, capped } => TestReachability::Legacy {
394                reachable: self.collect_reachable_along(
395                    roots,
396                    total_capacity,
397                    Edge::runs_target_code_in_tests,
398                ),
399                capped,
400            },
401            TestReachabilityPlan::Profiled { profiles } => {
402                let (reachable, index, dirty_word_pops) =
403                    self.collect_profiled_reachable(&profiles, total_capacity);
404                #[cfg(not(test))]
405                let _ = dirty_word_pops;
406
407                TestReachability::Profiled {
408                    reachable,
409                    index,
410                    #[cfg(test)]
411                    dirty_word_pops,
412                }
413            }
414        }
415    }
416
417    /// Mark modules reachable from overall, runtime, and test entry points via BFS.
418    ///
419    /// Skips redundant BFS passes when entry point sets are identical or empty.
420    /// `visited` is the overall entry-point pass, already computed by the
421    /// caller through [`ModuleGraph::collect_reachable`].
422    pub(super) fn mark_reachable(
423        &mut self,
424        visited: &FixedBitSet,
425        entry_points: &FxHashSet<FileId>,
426        runtime_entry_points: &FxHashSet<FileId>,
427        test_reachability_plan: TestReachabilityPlan<'_>,
428        total_capacity: usize,
429    ) {
430        let runtime_same = runtime_entry_points == entry_points;
431        let runtime_visited = if runtime_same {
432            None
433        } else {
434            Some(self.collect_reachable(runtime_entry_points, total_capacity))
435        };
436
437        let requires_reference_provenance = test_reachability_plan.requires_reference_provenance();
438        let (test_visited, test_reachability_index) = self
439            .collect_test_reachable(test_reachability_plan, total_capacity)
440            .into_parts();
441        debug_assert_eq!(
442            requires_reference_provenance,
443            test_reachability_index.profile_count > 0
444        );
445        self.test_reachability_index = test_reachability_index;
446
447        for (idx, module) in self.modules.iter_mut().enumerate() {
448            module.set_reachable(visited.contains(idx));
449            module.set_runtime_reachable(
450                runtime_visited
451                    .as_ref()
452                    .map_or_else(|| visited.contains(idx), |rv| rv.contains(idx)),
453            );
454            module.set_test_reachable(test_visited.as_ref().is_some_and(|tv| tv.contains(idx)));
455        }
456    }
457
458    /// The test entry points that reach each file of `files`, sorted by id.
459    ///
460    /// Each test entry point has its own traversal with its own `vi.mock`
461    /// replacement mask, so a test that replaces the file, or a module on
462    /// each import path to it, does not reach it. The traversal is the same
463    /// profiled pass that sets [`ModuleGraph::is_test_reachable`], with one
464    /// profile for each test entry point. A file is test-reachable exactly
465    /// when its list is not empty. When the profile count of the graph build
466    /// exceeded its safety cap, the masks are off, as in that build.
467    ///
468    /// The query runs one pass over the graph for each 64 test entry points.
469    #[must_use]
470    pub fn test_entry_points_reaching(&self, files: &[FileId]) -> FxHashMap<FileId, Vec<FileId>> {
471        let mut reaching: FxHashMap<FileId, Vec<FileId>> =
472            files.iter().map(|&file| (file, Vec::new())).collect();
473        let total_capacity = self.modules.len();
474        let mut roots: Vec<FileId> = self
475            .test_entry_points
476            .iter()
477            .copied()
478            .filter(|root| (root.0 as usize) < total_capacity)
479            .collect();
480        if files.is_empty() || roots.is_empty() {
481            return reaching;
482        }
483        roots.sort_unstable_by_key(|root| root.0);
484        let mut masks = self.test_reachability_index.root_masks();
485        for batch in roots.chunks(u64::BITS as usize) {
486            let profiles: Vec<TestReachabilityProfile> = batch
487                .iter()
488                .map(|&root| TestReachabilityProfile {
489                    masked_targets: masks.remove(&root).unwrap_or_default(),
490                    roots: vec![root],
491                })
492                .collect();
493            let (_, index, _) = ProfileWorklist::new(&profiles, total_capacity).run(self);
494            for (&file, entries) in &mut reaching {
495                let Some(&word) = index
496                    .profiles_for(&index.reachable_profiles, file)
497                    .and_then(|words| words.first())
498                else {
499                    continue;
500                };
501                entries.extend(
502                    batch
503                        .iter()
504                        .enumerate()
505                        .filter(|&(bit, _)| word & (1_u64 << bit) != 0)
506                        .map(|(_, &root)| root),
507                );
508            }
509        }
510        reaching
511    }
512}
513
514#[cfg(test)]
515mod tests {
516    use std::path::PathBuf;
517
518    use rustc_hash::FxHashSet;
519
520    use super::{TestReachabilityPlan, TestReachabilityProfile};
521    use crate::graph::{ExportNamespace, ExportTestReach, ModuleGraph, TestMaskingState};
522    use crate::resolve::{
523        ResolveResult, ResolvedImport, ResolvedModule, ResolvedReExport,
524        ResolvedReplacedModuleTarget,
525    };
526    use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource, FileId};
527    use fallow_types::extract::{
528        ExportName, ImportInfo, ImportedName, ModuleLoadMechanism, ReExportInfo, VisibilityTag,
529    };
530
531    std::thread_local! {
532        static TRAVERSALS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
533    }
534
535    pub(super) fn record_traversal() {
536        TRAVERSALS.with(|count| count.set(count.get() + 1));
537    }
538
539    fn capture_traversals<T>(run: impl FnOnce() -> T) -> (T, usize) {
540        let before = TRAVERSALS.with(std::cell::Cell::get);
541        let result = run();
542        let traversals = TRAVERSALS.with(|count| count.get() - before);
543        (result, traversals)
544    }
545
546    /// Build a graph with separate runtime and test entry point sets.
547    ///
548    /// `file_count` nodes are created, `edges_spec` defines directed edges,
549    /// `runtime_eps` and `test_eps` are file indices for each entry point
550    /// category. All entry points (union of runtime + test) form the overall
551    /// entry set.
552    fn build_reachability_graph(
553        file_count: usize,
554        edges_spec: &[(u32, u32)],
555        runtime_eps: &[u32],
556        test_eps: &[u32],
557    ) -> ModuleGraph {
558        let edges: Vec<_> = edges_spec
559            .iter()
560            .map(|&(source, target)| (source, target, false))
561            .collect();
562        build_reachability_graph_with_replacements(file_count, &edges, runtime_eps, test_eps, &[])
563    }
564
565    fn build_reachability_graph_with_replacements(
566        file_count: usize,
567        edges_spec: &[(u32, u32, bool)],
568        runtime_eps: &[u32],
569        test_eps: &[u32],
570        replacements: &[ResolvedReplacedModuleTarget],
571    ) -> ModuleGraph {
572        let edges: Vec<_> = edges_spec
573            .iter()
574            .map(|&(source, target, is_commonjs)| ReachabilityEdge {
575                source,
576                target,
577                is_commonjs,
578                is_type_only: false,
579            })
580            .collect();
581        build_reachability_graph_with_edges(file_count, &edges, runtime_eps, test_eps, replacements)
582    }
583
584    struct ReachabilityEdge {
585        source: u32,
586        target: u32,
587        is_commonjs: bool,
588        is_type_only: bool,
589    }
590
591    #[expect(
592        clippy::cast_possible_truncation,
593        reason = "test file counts are trivially small"
594    )]
595    fn build_reachability_graph_with_edges(
596        file_count: usize,
597        edges_spec: &[ReachabilityEdge],
598        runtime_eps: &[u32],
599        test_eps: &[u32],
600        replacements: &[ResolvedReplacedModuleTarget],
601    ) -> ModuleGraph {
602        let files: Vec<DiscoveredFile> = (0..file_count)
603            .map(|i| DiscoveredFile {
604                id: FileId(i as u32),
605                path: PathBuf::from(format!("/project/file{i}.ts")),
606                size_bytes: 100,
607            })
608            .collect();
609
610        let resolved_modules: Vec<ResolvedModule> = (0..file_count)
611            .map(|i| {
612                let imports: Vec<ResolvedImport> = edges_spec
613                    .iter()
614                    .filter(|edge| edge.source == i as u32)
615                    .map(|edge| ResolvedImport {
616                        info: ImportInfo {
617                            source: format!("./file{}", edge.target),
618                            imported_name: ImportedName::Named("x".to_string()),
619                            local_name: "x".to_string(),
620                            is_type_only: edge.is_type_only,
621                            is_type_only_star: false,
622                            from_style: false,
623                            span: oxc_span::Span::new(0, 10),
624                            source_span: oxc_span::Span::default(),
625                        },
626                        target: if edge.is_commonjs {
627                            ResolveResult::CommonJsInternalModule(FileId(edge.target))
628                        } else {
629                            ResolveResult::InternalModule(FileId(edge.target))
630                        },
631                    })
632                    .collect();
633
634                ResolvedModule {
635                    file_id: FileId(i as u32),
636                    path: PathBuf::from(format!("/project/file{i}.ts")),
637                    exports: vec![fallow_types::extract::ExportInfo {
638                        name: ExportName::Named("x".to_string()),
639                        local_name: Some("x".to_string()),
640                        is_type_only: false,
641                        visibility: VisibilityTag::None,
642                        expected_unused_reason: None,
643                        span: oxc_span::Span::new(0, 20),
644                        members: vec![],
645                        is_side_effect_used: false,
646                        super_class: None,
647                        deprecated: false,
648                        deprecated_reason: None,
649                    }]
650                    .into(),
651                    re_exports: vec![],
652                    resolved_imports: imports,
653                    resolved_dynamic_imports: vec![],
654                    resolved_dynamic_patterns: vec![],
655                    member_accesses: vec![].into(),
656                    semantic_facts: std::sync::Arc::default(),
657                    whole_object_uses: std::sync::Arc::default(),
658                    has_cjs_exports: false,
659                    has_angular_component_template_url: false,
660                    unused_import_bindings: FxHashSet::default(),
661                    type_referenced_import_bindings: vec![],
662                    value_referenced_import_bindings: vec![],
663                    namespace_object_aliases: vec![],
664                    exported_factory_returns: std::sync::Arc::default(),
665                    exported_factory_return_object_shapes: std::sync::Arc::default(),
666                    type_member_types: std::sync::Arc::default(),
667                    missing_export_targets: vec![],
668                }
669            })
670            .collect();
671
672        let runtime_entry_points: Vec<EntryPoint> = runtime_eps
673            .iter()
674            .map(|&i| EntryPoint {
675                path: PathBuf::from(format!("/project/file{i}.ts")),
676                source: EntryPointSource::PackageJsonMain,
677            })
678            .collect();
679
680        let test_entry_points: Vec<EntryPoint> = test_eps
681            .iter()
682            .map(|&i| EntryPoint {
683                path: PathBuf::from(format!("/project/file{i}.ts")),
684                source: EntryPointSource::TestFile,
685            })
686            .collect();
687
688        let mut all_entry_points = runtime_entry_points.clone();
689        all_entry_points.extend(test_entry_points.iter().cloned());
690
691        ModuleGraph::build_with_reachability_roots_and_replacements(
692            &resolved_modules,
693            replacements,
694            &all_entry_points,
695            &runtime_entry_points,
696            &test_entry_points,
697            &files,
698        )
699    }
700
701    fn build_masked_re_export_graph(
702        commonjs_to_barrel: bool,
703        commonjs_to_target: bool,
704    ) -> ModuleGraph {
705        let files: Vec<_> = (0..3)
706            .map(|id| DiscoveredFile {
707                id: FileId(id),
708                path: PathBuf::from(format!("/project/file{id}.ts")),
709                size_bytes: 100,
710            })
711            .collect();
712        let mut test_imports = vec![ResolvedImport {
713            info: ImportInfo {
714                source: "./barrel".to_string(),
715                imported_name: ImportedName::Named("value".to_string()),
716                local_name: "value".to_string(),
717                is_type_only: false,
718                is_type_only_star: false,
719                from_style: false,
720                span: oxc_span::Span::new(0, 10),
721                source_span: oxc_span::Span::default(),
722            },
723            target: if commonjs_to_barrel {
724                ResolveResult::CommonJsInternalModule(FileId(1))
725            } else {
726                ResolveResult::InternalModule(FileId(1))
727            },
728        }];
729        if commonjs_to_target {
730            test_imports.push(ResolvedImport {
731                info: ImportInfo {
732                    source: "./target".to_string(),
733                    imported_name: ImportedName::Named("value".to_string()),
734                    local_name: "requiredValue".to_string(),
735                    is_type_only: false,
736                    is_type_only_star: false,
737                    from_style: false,
738                    span: oxc_span::Span::new(20, 30),
739                    source_span: oxc_span::Span::default(),
740                },
741                target: ResolveResult::CommonJsInternalModule(FileId(2)),
742            });
743        }
744        let modules = vec![
745            ResolvedModule {
746                file_id: FileId(0),
747                path: files[0].path.clone(),
748                resolved_imports: test_imports,
749                ..ResolvedModule::default()
750            },
751            ResolvedModule {
752                file_id: FileId(1),
753                path: files[1].path.clone(),
754                re_exports: vec![ResolvedReExport {
755                    info: ReExportInfo {
756                        source: "./target".to_string(),
757                        imported_name: "value".to_string(),
758                        exported_name: "value".to_string(),
759                        is_type_only: false,
760                        span: oxc_span::Span::new(0, 10),
761                        ..Default::default()
762                    },
763                    target: ResolveResult::InternalModule(FileId(2)),
764                }],
765                ..ResolvedModule::default()
766            },
767            ResolvedModule {
768                file_id: FileId(2),
769                path: files[2].path.clone(),
770                exports: vec![fallow_types::extract::ExportInfo {
771                    name: ExportName::Named("value".to_string()),
772                    local_name: Some("value".to_string()),
773                    is_type_only: false,
774                    visibility: VisibilityTag::None,
775                    expected_unused_reason: None,
776                    span: oxc_span::Span::new(0, 20),
777                    members: Vec::new(),
778                    is_side_effect_used: false,
779                    super_class: None,
780                    deprecated: false,
781                    deprecated_reason: None,
782                }]
783                .into(),
784                ..ResolvedModule::default()
785            },
786        ];
787        let test_entry_points = vec![EntryPoint {
788            path: files[0].path.clone(),
789            source: EntryPointSource::TestFile,
790        }];
791        ModuleGraph::build_with_reachability_roots_and_replacements(
792            &modules,
793            &[ResolvedReplacedModuleTarget {
794                source_file: FileId(0),
795                target_file: FileId(2),
796            }],
797            &test_entry_points,
798            &[],
799            &test_entry_points,
800            &files,
801        )
802    }
803
804    fn build_masked_pattern_graph(mechanisms: &[ModuleLoadMechanism]) -> ModuleGraph {
805        let files: Vec<_> = (0..2)
806            .map(|id| DiscoveredFile {
807                id: FileId(id),
808                path: PathBuf::from(format!("/project/file{id}.ts")),
809                size_bytes: 100,
810            })
811            .collect();
812        let modules = vec![
813            ResolvedModule {
814                file_id: FileId(0),
815                path: files[0].path.clone(),
816                resolved_dynamic_patterns: mechanisms
817                    .iter()
818                    .copied()
819                    .map(|mechanism| {
820                        (
821                            fallow_types::extract::DynamicImportPattern {
822                                prefix: "./modules/".to_string(),
823                                suffix: None,
824                                span: oxc_span::Span::new(0, 10),
825                                mechanism,
826                                excludes: Vec::new(),
827                            },
828                            vec![FileId(1)],
829                        )
830                    })
831                    .collect(),
832                ..ResolvedModule::default()
833            },
834            ResolvedModule {
835                file_id: FileId(1),
836                path: files[1].path.clone(),
837                exports: vec![fallow_types::extract::ExportInfo {
838                    name: ExportName::Named("value".to_string()),
839                    local_name: Some("value".to_string()),
840                    is_type_only: false,
841                    visibility: VisibilityTag::None,
842                    expected_unused_reason: None,
843                    span: oxc_span::Span::new(0, 20),
844                    members: Vec::new(),
845                    is_side_effect_used: false,
846                    super_class: None,
847                    deprecated: false,
848                    deprecated_reason: None,
849                }]
850                .into(),
851                ..ResolvedModule::default()
852            },
853        ];
854        let test_entry_points = vec![EntryPoint {
855            path: files[0].path.clone(),
856            source: EntryPointSource::TestFile,
857        }];
858        ModuleGraph::build_with_reachability_roots_and_replacements(
859            &modules,
860            &[ResolvedReplacedModuleTarget {
861                source_file: FileId(0),
862                target_file: FileId(1),
863            }],
864            &test_entry_points,
865            &[],
866            &test_entry_points,
867            &files,
868        )
869    }
870
871    fn intermediate_import(
872        source: &str,
873        target: FileId,
874        imported_name: ImportedName,
875        commonjs: bool,
876    ) -> ResolvedImport {
877        ResolvedImport {
878            info: ImportInfo {
879                source: source.to_string(),
880                imported_name,
881                local_name: "value".to_string(),
882                is_type_only: false,
883                is_type_only_star: false,
884                from_style: false,
885                span: oxc_span::Span::new(0, 10),
886                source_span: oxc_span::Span::default(),
887            },
888            target: if commonjs {
889                ResolveResult::CommonJsInternalModule(target)
890            } else {
891                ResolveResult::InternalModule(target)
892            },
893        }
894    }
895
896    fn intermediate_modules(
897        files: &[DiscoveredFile],
898        commonjs_to_barrel: bool,
899        include_cycle: bool,
900    ) -> Vec<ResolvedModule> {
901        let mut target_re_exports = Vec::new();
902        if include_cycle {
903            target_re_exports.push(ResolvedReExport {
904                info: ReExportInfo {
905                    source: "./barrel".to_string(),
906                    imported_name: "*".to_string(),
907                    exported_name: "*".to_string(),
908                    is_type_only: false,
909                    span: oxc_span::Span::new(20, 30),
910                    ..Default::default()
911                },
912                target: ResolveResult::InternalModule(FileId(1)),
913            });
914        }
915        vec![
916            ResolvedModule {
917                file_id: FileId(0),
918                path: files[0].path.clone(),
919                resolved_imports: vec![
920                    intermediate_import(
921                        "./barrel",
922                        FileId(1),
923                        ImportedName::Named("value".to_string()),
924                        commonjs_to_barrel,
925                    ),
926                    intermediate_import("./alternate", FileId(3), ImportedName::SideEffect, false),
927                ],
928                ..ResolvedModule::default()
929            },
930            ResolvedModule {
931                file_id: FileId(1),
932                path: files[1].path.clone(),
933                re_exports: vec![ResolvedReExport {
934                    info: ReExportInfo {
935                        source: "./target".to_string(),
936                        imported_name: "value".to_string(),
937                        exported_name: "value".to_string(),
938                        is_type_only: false,
939                        span: oxc_span::Span::new(0, 10),
940                        ..Default::default()
941                    },
942                    target: ResolveResult::InternalModule(FileId(2)),
943                }],
944                ..ResolvedModule::default()
945            },
946            ResolvedModule {
947                file_id: FileId(2),
948                path: files[2].path.clone(),
949                exports: vec![fallow_types::extract::ExportInfo {
950                    name: ExportName::Named("value".to_string()),
951                    local_name: Some("value".to_string()),
952                    is_type_only: false,
953                    visibility: VisibilityTag::None,
954                    expected_unused_reason: None,
955                    span: oxc_span::Span::new(0, 20),
956                    members: Vec::new(),
957                    is_side_effect_used: false,
958                    super_class: None,
959                    deprecated: false,
960                    deprecated_reason: None,
961                }]
962                .into(),
963                re_exports: target_re_exports,
964                ..ResolvedModule::default()
965            },
966            ResolvedModule {
967                file_id: FileId(3),
968                path: files[3].path.clone(),
969                resolved_imports: vec![intermediate_import(
970                    "./target",
971                    FileId(2),
972                    ImportedName::SideEffect,
973                    false,
974                )],
975                ..ResolvedModule::default()
976            },
977        ]
978    }
979
980    fn build_intermediate_replacement_graph(
981        commonjs_to_barrel: bool,
982        include_cycle: bool,
983        mask_final_target: bool,
984    ) -> ModuleGraph {
985        let files: Vec<_> = (0..4)
986            .map(|id| DiscoveredFile {
987                id: FileId(id),
988                path: PathBuf::from(format!("/project/file{id}.ts")),
989                size_bytes: 100,
990            })
991            .collect();
992        let modules = intermediate_modules(&files, commonjs_to_barrel, include_cycle);
993        let test_entry_points = vec![EntryPoint {
994            path: files[0].path.clone(),
995            source: EntryPointSource::TestFile,
996        }];
997        let mut replacements = vec![ResolvedReplacedModuleTarget {
998            source_file: FileId(0),
999            target_file: FileId(1),
1000        }];
1001        if mask_final_target {
1002            replacements.push(ResolvedReplacedModuleTarget {
1003                source_file: FileId(0),
1004                target_file: FileId(2),
1005            });
1006        }
1007
1008        ModuleGraph::build_with_reachability_roots_and_replacements(
1009            &modules,
1010            &replacements,
1011            &test_entry_points,
1012            &[],
1013            &test_entry_points,
1014            &files,
1015        )
1016    }
1017
1018    #[test]
1019    fn entry_point_is_reachable() {
1020        let graph = build_reachability_graph(1, &[], &[0], &[]);
1021        assert!(graph.modules[0].is_reachable());
1022    }
1023
1024    #[test]
1025    fn direct_dependency_is_reachable() {
1026        let graph = build_reachability_graph(2, &[(0, 1)], &[0], &[]);
1027        assert!(graph.modules[0].is_reachable());
1028        assert!(graph.modules[1].is_reachable());
1029    }
1030
1031    #[test]
1032    fn chain_reachability_a_b_c() {
1033        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[0], &[]);
1034        assert!(graph.modules[0].is_reachable());
1035        assert!(graph.modules[1].is_reachable());
1036        assert!(graph.modules[2].is_reachable());
1037    }
1038
1039    #[test]
1040    fn deep_chain_all_reachable() {
1041        let graph = build_reachability_graph(5, &[(0, 1), (1, 2), (2, 3), (3, 4)], &[0], &[]);
1042        for i in 0..5 {
1043            assert!(
1044                graph.modules[i].is_reachable(),
1045                "file{i} should be reachable through chain"
1046            );
1047        }
1048    }
1049
1050    #[test]
1051    fn disconnected_file_is_unreachable() {
1052        let graph = build_reachability_graph(3, &[(0, 1)], &[0], &[]);
1053        assert!(graph.modules[0].is_reachable());
1054        assert!(graph.modules[1].is_reachable());
1055        assert!(!graph.modules[2].is_reachable());
1056    }
1057
1058    #[test]
1059    fn no_entry_points_all_unreachable() {
1060        let graph = build_reachability_graph(2, &[(0, 1)], &[], &[]);
1061        assert!(!graph.modules[0].is_reachable());
1062        assert!(!graph.modules[1].is_reachable());
1063    }
1064
1065    #[test]
1066    fn cycle_both_reachable_when_entry() {
1067        let graph = build_reachability_graph(2, &[(0, 1), (1, 0)], &[0], &[]);
1068        assert!(graph.modules[0].is_reachable());
1069        assert!(graph.modules[1].is_reachable());
1070    }
1071
1072    #[test]
1073    fn three_node_cycle_all_reachable() {
1074        let graph = build_reachability_graph(3, &[(0, 1), (1, 2), (2, 0)], &[0], &[]);
1075        for i in 0..3 {
1076            assert!(
1077                graph.modules[i].is_reachable(),
1078                "file{i} in cycle should be reachable"
1079            );
1080        }
1081    }
1082
1083    #[test]
1084    fn cycle_not_reachable_from_entry() {
1085        let graph = build_reachability_graph(3, &[(1, 2), (2, 1)], &[0], &[]);
1086        assert!(graph.modules[0].is_reachable());
1087        assert!(!graph.modules[1].is_reachable());
1088        assert!(!graph.modules[2].is_reachable());
1089    }
1090
1091    #[test]
1092    fn runtime_reachable_only_from_runtime_entries() {
1093        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0], &[2]);
1094        assert!(graph.modules[0].is_runtime_reachable());
1095        assert!(graph.modules[1].is_runtime_reachable());
1096        assert!(!graph.modules[2].is_runtime_reachable());
1097        assert!(!graph.modules[3].is_runtime_reachable());
1098    }
1099
1100    #[test]
1101    fn test_reachable_only_from_test_entries() {
1102        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0], &[2]);
1103        assert!(!graph.modules[0].is_test_reachable());
1104        assert!(!graph.modules[1].is_test_reachable());
1105        assert!(graph.modules[2].is_test_reachable());
1106        assert!(graph.modules[3].is_test_reachable());
1107    }
1108
1109    /// File 0 is a test root. It imports `x` from file 1, with `import type`
1110    /// when `type_only` is set. With `masked`, file 0 also mocks the
1111    /// unrelated file 2, so the graph uses the profiled traversal instead of
1112    /// the plain BFS.
1113    fn build_type_only_test_import_graph(type_only: bool, masked: bool) -> ModuleGraph {
1114        let edges = [ReachabilityEdge {
1115            source: 0,
1116            target: 1,
1117            is_commonjs: false,
1118            is_type_only: type_only,
1119        }];
1120        let replacements = if masked {
1121            vec![ResolvedReplacedModuleTarget {
1122                source_file: FileId(0),
1123                target_file: FileId(2),
1124            }]
1125        } else {
1126            Vec::new()
1127        };
1128        build_reachability_graph_with_edges(3, &edges, &[], &[0], &replacements)
1129    }
1130
1131    #[test]
1132    fn type_only_test_import_gives_no_export_coverage() {
1133        for masked in [false, true] {
1134            let graph = build_type_only_test_import_graph(true, masked);
1135            assert_eq!(graph.test_reachability_index.profile_count > 0, masked);
1136            let export = &graph.modules[1].exports[0];
1137            assert_eq!(export.references.len(), 1, "masked: {masked}");
1138            assert_eq!(
1139                export.references[0].namespace,
1140                ExportNamespace::Type,
1141                "masked: {masked}"
1142            );
1143
1144            assert!(
1145                !graph.is_test_reference_covered(export, 0),
1146                "masked: {masked}"
1147            );
1148            assert!(
1149                !graph.is_any_test_reference_covered(export),
1150                "masked: {masked}"
1151            );
1152        }
1153    }
1154
1155    /// File 0 is a test root and file 3 a runtime root. Both import file 1,
1156    /// the test with `import type` when `type_only` is set. File 1 imports
1157    /// file 2 by value. With `masked`, file 0 also mocks the unrelated file 4.
1158    fn build_type_only_test_chain_graph(type_only: bool, masked: bool) -> ModuleGraph {
1159        let edge = |source, target, is_type_only| ReachabilityEdge {
1160            source,
1161            target,
1162            is_commonjs: false,
1163            is_type_only,
1164        };
1165        let edges = [edge(0, 1, type_only), edge(1, 2, false), edge(3, 1, false)];
1166        let replacements = if masked {
1167            vec![ResolvedReplacedModuleTarget {
1168                source_file: FileId(0),
1169                target_file: FileId(4),
1170            }]
1171        } else {
1172            Vec::new()
1173        };
1174        build_reachability_graph_with_edges(5, &edges, &[3], &[0], &replacements)
1175    }
1176
1177    #[test]
1178    fn type_only_test_import_gives_no_file_test_reach() {
1179        for masked in [false, true] {
1180            let graph = build_type_only_test_chain_graph(true, masked);
1181            assert_eq!(graph.test_reachability_index.profile_count > 0, masked);
1182            assert!(graph.modules[0].is_test_reachable(), "masked: {masked}");
1183            assert!(!graph.modules[1].is_test_reachable(), "masked: {masked}");
1184            assert!(!graph.modules[2].is_test_reachable(), "masked: {masked}");
1185            assert!(
1186                graph
1187                    .test_entry_points_reaching(&[FileId(1), FileId(2)])
1188                    .values()
1189                    .all(Vec::is_empty),
1190                "masked: {masked}"
1191            );
1192            // Dead-code reachability still follows the type-only edge.
1193            assert!(graph.modules[1].is_reachable(), "masked: {masked}");
1194            assert!(graph.modules[2].is_reachable(), "masked: {masked}");
1195        }
1196    }
1197
1198    #[test]
1199    fn value_test_import_gives_file_test_reach() {
1200        for masked in [false, true] {
1201            let graph = build_type_only_test_chain_graph(false, masked);
1202            assert!(graph.modules[1].is_test_reachable(), "masked: {masked}");
1203            assert!(graph.modules[2].is_test_reachable(), "masked: {masked}");
1204            let reaching = graph.test_entry_points_reaching(&[FileId(2)]);
1205            assert_eq!(reaching[&FileId(2)], vec![FileId(0)], "masked: {masked}");
1206        }
1207    }
1208
1209    #[test]
1210    fn value_test_import_gives_export_coverage() {
1211        for masked in [false, true] {
1212            let graph = build_type_only_test_import_graph(false, masked);
1213            let export = &graph.modules[1].exports[0];
1214
1215            assert!(
1216                graph.is_test_reference_covered(export, 0),
1217                "masked: {masked}"
1218            );
1219        }
1220    }
1221
1222    #[test]
1223    fn esm_replacement_masks_target_only_from_test_reachability() {
1224        let graph = build_reachability_graph_with_replacements(
1225            3,
1226            &[(0, 1, false), (1, 2, false)],
1227            &[],
1228            &[0],
1229            &[ResolvedReplacedModuleTarget {
1230                source_file: FileId(0),
1231                target_file: FileId(1),
1232            }],
1233        );
1234
1235        assert!(graph.modules[1].is_reachable());
1236        assert!(!graph.modules[1].is_test_reachable());
1237        assert!(!graph.modules[2].is_test_reachable());
1238        assert_eq!(graph.test_reachability_index.profile_count, 1);
1239        assert!(graph.test_reachability_index.profile_reaches(FileId(0), 0));
1240        assert!(!graph.test_reachability_index.profile_reaches(FileId(1), 0));
1241    }
1242
1243    #[test]
1244    fn commonjs_path_preserves_a_replaced_target() {
1245        let graph = build_reachability_graph_with_replacements(
1246            2,
1247            &[(0, 1, true)],
1248            &[],
1249            &[0],
1250            &[ResolvedReplacedModuleTarget {
1251                source_file: FileId(0),
1252                target_file: FileId(1),
1253            }],
1254        );
1255
1256        assert!(graph.modules[1].is_test_reachable());
1257    }
1258
1259    #[test]
1260    fn mixed_commonjs_and_esm_symbols_preserve_a_replaced_target() {
1261        let graph = build_reachability_graph_with_replacements(
1262            2,
1263            &[(0, 1, false), (0, 1, true)],
1264            &[],
1265            &[0],
1266            &[ResolvedReplacedModuleTarget {
1267                source_file: FileId(0),
1268                target_file: FileId(1),
1269            }],
1270        );
1271
1272        assert!(graph.modules[1].is_test_reachable());
1273    }
1274
1275    #[test]
1276    fn replacement_masks_a_target_behind_an_esm_re_export() {
1277        let graph = build_masked_re_export_graph(false, false);
1278        let target_export = &graph.modules[2].exports[0];
1279        assert!(
1280            !target_export.references.is_empty(),
1281            "barrel consumer reference should propagate"
1282        );
1283
1284        assert!(graph.modules[1].is_test_reachable());
1285        assert!(!graph.modules[2].is_test_reachable());
1286        assert_eq!(
1287            graph.reference_path_hops(target_export, 0)[0].1,
1288            ModuleLoadMechanism::EsModule
1289        );
1290        assert!(!graph.is_test_reference_covered(target_export, 0));
1291    }
1292
1293    #[test]
1294    fn commonjs_loaded_barrel_does_not_bypass_its_esm_re_export() {
1295        let graph = build_masked_re_export_graph(true, false);
1296        let target_export = &graph.modules[2].exports[0];
1297        assert!(
1298            !target_export.references.is_empty(),
1299            "barrel consumer reference should propagate"
1300        );
1301
1302        assert!(graph.modules[1].is_test_reachable());
1303        assert!(!graph.modules[2].is_test_reachable());
1304        assert_eq!(
1305            graph.reference_path_hops(target_export, 0)[0].1,
1306            ModuleLoadMechanism::EsModule
1307        );
1308        assert!(!graph.is_test_reference_covered(target_export, 0));
1309    }
1310
1311    #[test]
1312    fn direct_commonjs_and_esm_re_export_retain_distinct_coverage() {
1313        let graph = build_masked_re_export_graph(false, true);
1314        let export = &graph.modules[2].exports[0];
1315
1316        assert_eq!(export.references.len(), 2);
1317        let esm = (0..export.references.len())
1318            .find(|&index| {
1319                graph.reference_path_hops(export, index)[0].1 == ModuleLoadMechanism::EsModule
1320            })
1321            .expect("ESM re-export reference");
1322        let commonjs = (0..export.references.len())
1323            .find(|&index| {
1324                graph.reference_path_hops(export, index)[0].1
1325                    == ModuleLoadMechanism::CommonJsRequire
1326            })
1327            .expect("direct CommonJS reference");
1328        assert!(!graph.is_test_reference_covered(export, esm));
1329        assert!(graph.is_test_reference_covered(export, commonjs));
1330    }
1331
1332    #[test]
1333    fn mocked_intermediate_barrel_blocks_a_reference_despite_an_alternate_target_route() {
1334        let graph = build_intermediate_replacement_graph(false, false, false);
1335        let export = &graph.modules[2].exports[0];
1336        let hops = graph.reference_path_hops(export, 0);
1337
1338        assert!(graph.modules[2].is_test_reachable());
1339        assert_eq!(
1340            hops,
1341            vec![
1342                (FileId(2), ModuleLoadMechanism::EsModule),
1343                (FileId(1), ModuleLoadMechanism::EsModule),
1344            ]
1345        );
1346        assert!(!graph.is_test_reference_covered(export, 0));
1347    }
1348
1349    #[test]
1350    fn mocked_re_export_cycle_member_blocks_the_cyclic_reference_path() {
1351        let graph = build_intermediate_replacement_graph(false, true, false);
1352        let export = &graph.modules[2].exports[0];
1353
1354        assert!(
1355            graph
1356                .re_export_cycles
1357                .iter()
1358                .any(|cycle| cycle.file_ids == vec![FileId(1), FileId(2)])
1359        );
1360        assert!(graph.modules[2].is_test_reachable());
1361        assert!(!graph.is_test_reference_covered(export, 0));
1362    }
1363
1364    #[test]
1365    fn commonjs_barrel_hop_bypasses_only_its_own_replacement() {
1366        let graph = build_intermediate_replacement_graph(true, false, false);
1367        let export = &graph.modules[2].exports[0];
1368
1369        assert_eq!(
1370            graph.reference_path_hops(export, 0),
1371            vec![
1372                (FileId(2), ModuleLoadMechanism::EsModule),
1373                (FileId(1), ModuleLoadMechanism::CommonJsRequire),
1374            ]
1375        );
1376        assert!(graph.is_test_reference_covered(export, 0));
1377    }
1378
1379    #[test]
1380    fn commonjs_barrel_hop_does_not_bypass_a_replaced_esm_target() {
1381        let graph = build_intermediate_replacement_graph(true, false, true);
1382        let export = &graph.modules[2].exports[0];
1383
1384        assert!(!graph.is_test_reference_covered(export, 0));
1385    }
1386
1387    #[test]
1388    fn reference_paths_survive_graph_cache_serialization() {
1389        let graph = build_intermediate_replacement_graph(false, false, false);
1390        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
1391        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
1392        let export = &decoded.modules[2].exports[0];
1393
1394        assert_eq!(
1395            decoded.reference_path_hops(export, 0),
1396            vec![
1397                (FileId(2), ModuleLoadMechanism::EsModule),
1398                (FileId(1), ModuleLoadMechanism::EsModule),
1399            ]
1400        );
1401        assert!(!decoded.is_test_reference_covered(export, 0));
1402    }
1403
1404    #[test]
1405    fn require_context_keeps_a_replaced_target_covered() {
1406        let graph = build_masked_pattern_graph(&[ModuleLoadMechanism::CommonJsRequire]);
1407        let export = &graph.modules[1].exports[0];
1408
1409        assert!(graph.modules[1].is_test_reachable());
1410        assert_eq!(
1411            graph.reference_path_hops(export, 0)[0].1,
1412            ModuleLoadMechanism::CommonJsRequire
1413        );
1414        assert!(graph.is_test_reference_covered(export, 0));
1415    }
1416
1417    #[test]
1418    fn overlapping_patterns_preserve_exact_esm_and_commonjs_coverage() {
1419        let graph = build_masked_pattern_graph(&[
1420            ModuleLoadMechanism::EsModule,
1421            ModuleLoadMechanism::CommonJsRequire,
1422        ]);
1423        let export = &graph.modules[1].exports[0];
1424
1425        assert!(graph.modules[1].is_test_reachable());
1426        assert_eq!(export.references.len(), 2);
1427        let esm = (0..export.references.len())
1428            .find(|&index| {
1429                graph.reference_path_hops(export, index)[0].1 == ModuleLoadMechanism::EsModule
1430            })
1431            .expect("ESM pattern reference");
1432        let commonjs = (0..export.references.len())
1433            .find(|&index| {
1434                graph.reference_path_hops(export, index)[0].1
1435                    == ModuleLoadMechanism::CommonJsRequire
1436            })
1437            .expect("CommonJS pattern reference");
1438        assert!(!graph.is_test_reference_covered(export, esm));
1439        assert!(graph.is_test_reference_covered(export, commonjs));
1440    }
1441
1442    #[test]
1443    fn replacement_stops_before_a_masked_cycle_member() {
1444        let graph = build_reachability_graph_with_replacements(
1445            3,
1446            &[(0, 1, false), (1, 2, false), (2, 1, false)],
1447            &[],
1448            &[0],
1449            &[ResolvedReplacedModuleTarget {
1450                source_file: FileId(0),
1451                target_file: FileId(2),
1452            }],
1453        );
1454
1455        assert!(graph.modules[0].is_test_reachable());
1456        assert!(graph.modules[1].is_test_reachable());
1457        assert!(!graph.modules[2].is_test_reachable());
1458    }
1459
1460    #[test]
1461    fn identical_masks_share_one_reachability_profile() {
1462        let graph = build_reachability_graph_with_replacements(
1463            3,
1464            &[(0, 2, false), (1, 2, false)],
1465            &[],
1466            &[0, 1],
1467            &[
1468                ResolvedReplacedModuleTarget {
1469                    source_file: FileId(1),
1470                    target_file: FileId(2),
1471                },
1472                ResolvedReplacedModuleTarget {
1473                    source_file: FileId(0),
1474                    target_file: FileId(2),
1475                },
1476            ],
1477        );
1478
1479        assert_eq!(graph.test_reachability_index.profile_count, 1);
1480        assert!(graph.test_reachability_index.profile_masks(FileId(2), 0));
1481        assert!(graph.test_reachability_index.profile_reaches(FileId(0), 0));
1482        assert!(graph.test_reachability_index.profile_reaches(FileId(1), 0));
1483        assert!(!graph.modules[2].is_test_reachable());
1484    }
1485
1486    #[test]
1487    fn an_unmasked_root_keeps_the_shared_target_test_reachable() {
1488        let graph = build_reachability_graph_with_replacements(
1489            3,
1490            &[(0, 2, false), (1, 2, false)],
1491            &[],
1492            &[0, 1],
1493            &[ResolvedReplacedModuleTarget {
1494                source_file: FileId(0),
1495                target_file: FileId(2),
1496            }],
1497        );
1498
1499        assert_eq!(graph.test_reachability_index.profile_count, 2);
1500        assert!(graph.modules[2].is_test_reachable());
1501        assert!(!graph.test_reachability_index.profile_masks(FileId(2), 0));
1502        assert!(graph.test_reachability_index.profile_reaches(FileId(1), 0));
1503        assert!(graph.test_reachability_index.profile_reaches(FileId(2), 0));
1504        assert!(graph.test_reachability_index.profile_masks(FileId(2), 1));
1505        assert!(graph.test_reachability_index.profile_reaches(FileId(0), 1));
1506        let export = &graph.modules[2].exports[0];
1507        let reference_from = |source| {
1508            export
1509                .references
1510                .iter()
1511                .position(|reference| reference.from_file == source)
1512                .expect("both test roots reference the target export")
1513        };
1514        assert!(!graph.is_test_reference_covered(export, reference_from(FileId(0))));
1515        assert!(graph.is_test_reference_covered(export, reference_from(FileId(1))));
1516    }
1517
1518    #[test]
1519    fn replacement_declared_outside_a_test_root_keeps_the_fast_path() {
1520        let graph = build_reachability_graph_with_replacements(
1521            3,
1522            &[(0, 1, false)],
1523            &[],
1524            &[0],
1525            &[ResolvedReplacedModuleTarget {
1526                source_file: FileId(2),
1527                target_file: FileId(1),
1528            }],
1529        );
1530
1531        assert_eq!(graph.test_reachability_index.profile_count, 0);
1532        assert!(graph.modules[1].is_test_reachable());
1533    }
1534
1535    #[test]
1536    fn test_reachability_plan_uses_no_roots_without_test_entries() {
1537        let test_roots = FxHashSet::default();
1538
1539        let plan = TestReachabilityPlan::new(&test_roots, &[], 3);
1540
1541        assert!(matches!(&plan, TestReachabilityPlan::NoRoots));
1542        assert!(!plan.requires_reference_provenance());
1543    }
1544
1545    #[test]
1546    fn test_reachability_plan_ignores_replacements_outside_test_roots() {
1547        let test_roots = FxHashSet::from_iter([FileId(0)]);
1548        let replacements = [ResolvedReplacedModuleTarget {
1549            source_file: FileId(1),
1550            target_file: FileId(2),
1551        }];
1552
1553        let plan = TestReachabilityPlan::new(&test_roots, &replacements, 3);
1554
1555        assert!(matches!(&plan, TestReachabilityPlan::Legacy { .. }));
1556        assert!(!plan.requires_reference_provenance());
1557    }
1558
1559    #[test]
1560    fn test_reachability_plan_ignores_out_of_capacity_targets() {
1561        let test_roots = FxHashSet::from_iter([FileId(0)]);
1562        let replacements = [ResolvedReplacedModuleTarget {
1563            source_file: FileId(0),
1564            target_file: FileId(3),
1565        }];
1566
1567        let plan = TestReachabilityPlan::new(&test_roots, &replacements, 3);
1568
1569        assert!(matches!(&plan, TestReachabilityPlan::Legacy { .. }));
1570        assert!(!plan.requires_reference_provenance());
1571    }
1572
1573    #[test]
1574    fn test_reachability_plan_groups_roots_by_normalized_replacement_mask() {
1575        let test_roots = FxHashSet::from_iter([FileId(0), FileId(1), FileId(2)]);
1576        let replacements = [
1577            ResolvedReplacedModuleTarget {
1578                source_file: FileId(0),
1579                target_file: FileId(4),
1580            },
1581            ResolvedReplacedModuleTarget {
1582                source_file: FileId(0),
1583                target_file: FileId(4),
1584            },
1585            ResolvedReplacedModuleTarget {
1586                source_file: FileId(1),
1587                target_file: FileId(4),
1588            },
1589        ];
1590
1591        let plan = TestReachabilityPlan::new(&test_roots, &replacements, 5);
1592
1593        assert!(plan.requires_reference_provenance());
1594        let TestReachabilityPlan::Profiled { profiles } = plan else {
1595            panic!("valid test-root replacements must use profiled reachability");
1596        };
1597        assert_eq!(
1598            profiles,
1599            vec![
1600                TestReachabilityProfile {
1601                    masked_targets: Vec::new(),
1602                    roots: vec![FileId(2)],
1603                },
1604                TestReachabilityProfile {
1605                    masked_targets: vec![FileId(4)],
1606                    roots: vec![FileId(0), FileId(1)],
1607                },
1608            ]
1609        );
1610    }
1611
1612    type UniqueMaskInputs = (
1613        Vec<u32>,
1614        Vec<(u32, u32, bool)>,
1615        Vec<ResolvedReplacedModuleTarget>,
1616    );
1617
1618    /// Build roots 0..count, each importing and mocking a unique target at
1619    /// count + root, so every root lands in its own mask profile.
1620    fn unique_mask_graph_inputs(count: u32) -> UniqueMaskInputs {
1621        let test_roots: Vec<u32> = (0..count).collect();
1622        let mut edges = Vec::with_capacity(test_roots.len());
1623        let mut replacements = Vec::with_capacity(test_roots.len());
1624        for &root in &test_roots {
1625            let masked_target = count + root;
1626            edges.push((root, masked_target, false));
1627            replacements.push(ResolvedReplacedModuleTarget {
1628                source_file: FileId(root),
1629                target_file: FileId(masked_target),
1630            });
1631        }
1632        (test_roots, edges, replacements)
1633    }
1634
1635    #[test]
1636    #[cfg_attr(
1637        miri,
1638        ignore = "thousands of synthetic profiles are too slow under miri"
1639    )]
1640    fn profile_count_at_the_safety_cap_keeps_profiled_masking() {
1641        let count = u32::try_from(super::PROFILE_COUNT_SAFETY_CAP).expect("cap fits in u32");
1642        let total = count as usize * 2;
1643        let (test_roots, edges, replacements) = unique_mask_graph_inputs(count);
1644        let graph = build_reachability_graph_with_replacements(
1645            total,
1646            &edges,
1647            &[],
1648            &test_roots,
1649            &replacements,
1650        );
1651
1652        assert_eq!(
1653            graph.test_reachability_index.profile_count,
1654            super::PROFILE_COUNT_SAFETY_CAP
1655        );
1656        // Profiles sort by mask, so profile 0 belongs to root 0 whose unique
1657        // target is FileId(count).
1658        assert!(
1659            graph
1660                .test_reachability_index
1661                .profile_masks(FileId(count), 0)
1662        );
1663        assert!(graph.modules[0].is_test_reachable());
1664        // Masking still applies under the cap: the mocked target is only
1665        // imported by the root that replaces it, so it stays unreachable.
1666        assert!(!graph.modules[count as usize].is_test_reachable());
1667        assert_eq!(graph.test_masking_state(), TestMaskingState::Active);
1668    }
1669
1670    #[test]
1671    #[cfg_attr(
1672        miri,
1673        ignore = "thousands of synthetic profiles are too slow under miri"
1674    )]
1675    fn profile_count_above_the_safety_cap_falls_back_to_coarse_reachability() {
1676        let count = u32::try_from(super::PROFILE_COUNT_SAFETY_CAP * 4).expect("cap fits in u32");
1677        let total = count as usize * 2;
1678        let (test_roots, edges, replacements) = unique_mask_graph_inputs(count);
1679        let graph = build_reachability_graph_with_replacements(
1680            total,
1681            &edges,
1682            &[],
1683            &test_roots,
1684            &replacements,
1685        );
1686        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1687
1688        let plan = TestReachabilityPlan::new(&root_set, &replacements, total);
1689        assert!(matches!(
1690            &plan,
1691            TestReachabilityPlan::Legacy { capped: true, .. }
1692        ));
1693        assert!(!plan.requires_reference_provenance());
1694
1695        // Fail-open: no profiles survive, and mocked targets stay
1696        // test-reachable exactly as the pre-profile coarse pass reported them.
1697        assert_eq!(graph.test_reachability_index.profile_count, 0);
1698        for &root in &test_roots {
1699            assert!(graph.modules[root as usize].is_test_reachable());
1700            assert!(graph.modules[(count + root) as usize].is_test_reachable());
1701        }
1702
1703        // The capped state is visible, and a mocked export keeps its reach
1704        // class instead of `MockedOnly`.
1705        assert_eq!(graph.test_masking_state(), TestMaskingState::Capped);
1706        let mocked = &graph.modules[count as usize];
1707        let reach =
1708            graph.export_test_reach(mocked.file_id, &mocked.exports[0], &|file| file.0 < count);
1709        assert_eq!(reach.reach, ExportTestReach::Direct);
1710    }
1711
1712    #[test]
1713    fn replacement_profiles_survive_graph_cache_serialization() {
1714        let graph = build_reachability_graph_with_replacements(
1715            2,
1716            &[(0, 1, false)],
1717            &[],
1718            &[0],
1719            &[ResolvedReplacedModuleTarget {
1720                source_file: FileId(0),
1721                target_file: FileId(1),
1722            }],
1723        );
1724
1725        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
1726        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
1727
1728        assert_eq!(decoded.test_reachability_index.profile_count, 1);
1729        assert!(decoded.test_reachability_index.profile_masks(FileId(1), 0));
1730        assert!(
1731            decoded
1732                .test_reachability_index
1733                .profile_reaches(FileId(0), 0)
1734        );
1735        assert!(
1736            !decoded
1737                .test_reachability_index
1738                .profile_reaches(FileId(1), 0)
1739        );
1740    }
1741
1742    #[test]
1743    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1744    fn many_unmasked_roots_use_one_test_traversal() {
1745        let test_roots: Vec<u32> = (0..512).collect();
1746        let graph = build_reachability_graph(512, &[], &[], &test_roots);
1747        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1748
1749        let plan = TestReachabilityPlan::new(&root_set, &[], 512);
1750        let (reachability, traversals) =
1751            capture_traversals(|| graph.collect_test_reachable(plan, 512));
1752
1753        assert_eq!(traversals, 1);
1754        let (reachable, _) = reachability.into_parts();
1755        let reachable = reachable.expect("test roots have a reachability bitset");
1756        assert!(
1757            root_set
1758                .iter()
1759                .all(|root| reachable.contains(root.0 as usize))
1760        );
1761    }
1762
1763    #[test]
1764    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1765    fn many_roots_share_one_profile_worklist() {
1766        let test_roots: Vec<u32> = (0..128).collect();
1767        let edges: Vec<_> = test_roots
1768            .iter()
1769            .copied()
1770            .map(|root| (root, 128, false))
1771            .collect();
1772        let replacements: Vec<_> = (0..64)
1773            .map(|root| ResolvedReplacedModuleTarget {
1774                source_file: FileId(root),
1775                target_file: FileId(128),
1776            })
1777            .collect();
1778        let graph = build_reachability_graph_with_replacements(
1779            129,
1780            &edges,
1781            &[],
1782            &test_roots,
1783            &replacements,
1784        );
1785        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1786
1787        let plan = TestReachabilityPlan::new(&root_set, &replacements, 129);
1788        let (reachability, traversals) =
1789            capture_traversals(|| graph.collect_test_reachable(plan, 129));
1790
1791        assert_eq!(traversals, 1);
1792        assert_eq!(reachability.dirty_word_pop_count(), 129);
1793    }
1794
1795    #[test]
1796    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1797    fn unique_masks_cross_profile_words_in_one_deterministic_worklist() {
1798        let test_roots: Vec<u32> = (0..65).collect();
1799        let mut edges = Vec::with_capacity(test_roots.len() * 2);
1800        let mut replacements = Vec::with_capacity(test_roots.len());
1801        for &root in &test_roots {
1802            let masked_target = 65 + root;
1803            edges.push((root, masked_target, false));
1804            edges.push((root, 130, false));
1805            replacements.push(ResolvedReplacedModuleTarget {
1806                source_file: FileId(root),
1807                target_file: FileId(masked_target),
1808            });
1809        }
1810        let graph = build_reachability_graph_with_replacements(
1811            131,
1812            &edges,
1813            &[],
1814            &test_roots,
1815            &replacements,
1816        );
1817        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1818
1819        let plan = TestReachabilityPlan::new(&root_set, &replacements, 131);
1820        let (reachability, traversals) =
1821            capture_traversals(|| graph.collect_test_reachable(plan, 131));
1822
1823        assert_eq!(traversals, 1);
1824        assert_eq!(reachability.dirty_word_pop_count(), 67);
1825        assert_eq!(graph.test_reachability_index.profile_count, 65);
1826        assert_eq!(graph.test_reachability_index.words_per_file, 2);
1827        assert_eq!(graph.test_reachability_index.masked_profiles.len(), 65);
1828        assert!(
1829            graph
1830                .test_reachability_index
1831                .profile_reaches(FileId(130), 0)
1832        );
1833        assert!(
1834            graph
1835                .test_reachability_index
1836                .profile_reaches(FileId(130), 64)
1837        );
1838        assert!(graph.test_reachability_index.profile_masks(FileId(65), 0));
1839        assert!(graph.test_reachability_index.profile_masks(FileId(129), 64));
1840        assert!(!graph.test_reachability_index.profile_reaches(FileId(65), 0));
1841        assert!(
1842            !graph
1843                .test_reachability_index
1844                .profile_reaches(FileId(129), 64)
1845        );
1846
1847        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
1848        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
1849        assert_eq!(decoded.test_reachability_index.profile_count, 65);
1850        assert_eq!(decoded.test_reachability_index.words_per_file, 2);
1851        assert_eq!(decoded.test_reachability_index.masked_profiles.len(), 65);
1852        assert!(
1853            decoded
1854                .test_reachability_index
1855                .profile_reaches(FileId(130), 64)
1856        );
1857        assert!(
1858            decoded
1859                .test_reachability_index
1860                .profile_masks(FileId(129), 64)
1861        );
1862    }
1863
1864    #[test]
1865    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1866    fn staggered_profile_words_propagate_without_clean_word_scans() {
1867        const PROFILE_COUNT: u32 = 65;
1868        const MASK_START: u32 = PROFILE_COUNT;
1869        const FANOUT_START: u32 = MASK_START + PROFILE_COUNT;
1870        const FANOUT_COUNT: u32 = 8;
1871
1872        let test_roots: Vec<u32> = (0..PROFILE_COUNT).collect();
1873        let mut edges = Vec::new();
1874        for root in 1..PROFILE_COUNT {
1875            edges.push((root, root - 1, false));
1876        }
1877        for target in FANOUT_START..FANOUT_START + FANOUT_COUNT {
1878            edges.push((0, target, false));
1879        }
1880        let replacements: Vec<_> = test_roots
1881            .iter()
1882            .copied()
1883            .map(|root| ResolvedReplacedModuleTarget {
1884                source_file: FileId(root),
1885                target_file: FileId(MASK_START + root),
1886            })
1887            .collect();
1888        let file_count = (FANOUT_START + FANOUT_COUNT) as usize;
1889        let graph = build_reachability_graph_with_replacements(
1890            file_count,
1891            &edges,
1892            &[],
1893            &test_roots,
1894            &replacements,
1895        );
1896        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1897
1898        let plan = TestReachabilityPlan::new(&root_set, &replacements, file_count);
1899        let reachability = graph.collect_test_reachable(plan, file_count);
1900
1901        assert_eq!(graph.test_reachability_index.words_per_file, 2);
1902        let expected_dirty_word_pops =
1903            (PROFILE_COUNT * (PROFILE_COUNT + 1) / 2 + FANOUT_COUNT * PROFILE_COUNT) as usize;
1904        assert_eq!(
1905            reachability.dirty_word_pop_count(),
1906            expected_dirty_word_pops
1907        );
1908        for target in FANOUT_START..FANOUT_START + FANOUT_COUNT {
1909            assert!(
1910                graph
1911                    .test_reachability_index
1912                    .profile_reaches(FileId(target), 0)
1913            );
1914            assert!(
1915                graph
1916                    .test_reachability_index
1917                    .profile_reaches(FileId(target), 64)
1918            );
1919        }
1920    }
1921
1922    #[test]
1923    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1924    fn no_profile_coverage_omits_unused_reference_provenance() {
1925        const CHAIN_LENGTH: u32 = 128;
1926
1927        let files: Vec<_> = (0..=CHAIN_LENGTH)
1928            .map(|id| DiscoveredFile {
1929                id: FileId(id),
1930                path: PathBuf::from(format!("/project/file{id}.ts")),
1931                size_bytes: 100,
1932            })
1933            .collect();
1934        let mut modules = Vec::with_capacity(files.len());
1935        modules.push(ResolvedModule {
1936            file_id: FileId(0),
1937            path: files[0].path.clone(),
1938            resolved_imports: vec![intermediate_import(
1939                "./file1",
1940                FileId(1),
1941                ImportedName::Named("value".to_string()),
1942                false,
1943            )],
1944            ..ResolvedModule::default()
1945        });
1946        for id in 1..CHAIN_LENGTH {
1947            modules.push(ResolvedModule {
1948                file_id: FileId(id),
1949                path: files[id as usize].path.clone(),
1950                re_exports: vec![ResolvedReExport {
1951                    info: ReExportInfo {
1952                        source: format!("./file{}", id + 1),
1953                        imported_name: "value".to_string(),
1954                        exported_name: "value".to_string(),
1955                        is_type_only: false,
1956                        span: oxc_span::Span::new(0, 10),
1957                        ..Default::default()
1958                    },
1959                    target: ResolveResult::InternalModule(FileId(id + 1)),
1960                }],
1961                ..ResolvedModule::default()
1962            });
1963        }
1964        modules.push(ResolvedModule {
1965            file_id: FileId(CHAIN_LENGTH),
1966            path: files[CHAIN_LENGTH as usize].path.clone(),
1967            exports: vec![fallow_types::extract::ExportInfo {
1968                name: ExportName::Named("value".to_string()),
1969                local_name: Some("value".to_string()),
1970                is_type_only: false,
1971                visibility: VisibilityTag::None,
1972                expected_unused_reason: None,
1973                span: oxc_span::Span::new(0, 20),
1974                members: Vec::new(),
1975                is_side_effect_used: false,
1976                super_class: None,
1977                deprecated: false,
1978                deprecated_reason: None,
1979            }]
1980            .into(),
1981            ..ResolvedModule::default()
1982        });
1983        let test_entry_points = vec![EntryPoint {
1984            path: files[0].path.clone(),
1985            source: EntryPointSource::TestFile,
1986        }];
1987        let graph = ModuleGraph::build_with_reachability_roots_and_replacements(
1988            &modules,
1989            &[],
1990            &test_entry_points,
1991            &[],
1992            &test_entry_points,
1993            &files,
1994        );
1995        let export = &graph.modules[CHAIN_LENGTH as usize].exports[0];
1996
1997        assert_eq!(graph.test_reachability_index.profile_count, 0);
1998        assert!(
1999            export.reference_paths.is_empty(),
2000            "the provenance side table must stay unallocated on the fast path"
2001        );
2002        assert!(graph.reference_paths.is_empty());
2003        assert!(graph.is_test_reference_covered(export, 0));
2004    }
2005
2006    #[test]
2007    fn overall_reachable_is_union_of_runtime_and_test() {
2008        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0], &[2]);
2009        for i in 0..4 {
2010            assert!(
2011                graph.modules[i].is_reachable(),
2012                "file{i} should be overall-reachable"
2013            );
2014        }
2015    }
2016
2017    #[test]
2018    fn shared_dependency_is_both_runtime_and_test_reachable() {
2019        let graph = build_reachability_graph(3, &[(0, 2), (1, 2)], &[0], &[1]);
2020        assert!(graph.modules[2].is_runtime_reachable());
2021        assert!(graph.modules[2].is_test_reachable());
2022        assert!(graph.modules[2].is_reachable());
2023    }
2024
2025    #[test]
2026    fn runtime_same_as_overall_reuses_bfs() {
2027        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[0], &[]);
2028        for i in 0..3 {
2029            assert_eq!(
2030                graph.modules[i].is_reachable(),
2031                graph.modules[i].is_runtime_reachable(),
2032                "file{i}: reachable and runtime_reachable should match when runtime==overall"
2033            );
2034        }
2035    }
2036
2037    #[test]
2038    fn empty_test_entries_none_test_reachable() {
2039        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[0], &[]);
2040        for i in 0..3 {
2041            assert!(
2042                !graph.modules[i].is_test_reachable(),
2043                "file{i} should not be test-reachable when no test entries exist"
2044            );
2045        }
2046    }
2047
2048    #[test]
2049    fn only_test_entries_runtime_unreachable() {
2050        let graph = build_reachability_graph(2, &[(0, 1)], &[], &[0]);
2051        assert!(graph.modules[0].is_test_reachable());
2052        assert!(graph.modules[1].is_test_reachable());
2053        assert!(!graph.modules[0].is_runtime_reachable());
2054        assert!(!graph.modules[1].is_runtime_reachable());
2055        assert!(graph.modules[0].is_reachable());
2056        assert!(graph.modules[1].is_reachable());
2057    }
2058
2059    #[test]
2060    fn diamond_dependency_all_reachable() {
2061        let graph = build_reachability_graph(4, &[(0, 1), (0, 2), (1, 3), (2, 3)], &[0], &[]);
2062        for i in 0..4 {
2063            assert!(
2064                graph.modules[i].is_reachable(),
2065                "file{i} in diamond should be reachable"
2066            );
2067        }
2068    }
2069
2070    #[test]
2071    fn multiple_entry_points_reach_disjoint_subtrees() {
2072        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0, 2], &[]);
2073        for i in 0..4 {
2074            assert!(
2075                graph.modules[i].is_reachable(),
2076                "file{i} should be reachable from one of the entry points"
2077            );
2078        }
2079    }
2080
2081    #[test]
2082    fn empty_graph_no_panics() {
2083        let graph = build_reachability_graph(0, &[], &[], &[]);
2084        assert_eq!(graph.module_count(), 0);
2085    }
2086
2087    fn reaching(graph: &ModuleGraph, file: u32) -> Vec<u32> {
2088        let map = graph.test_entry_points_reaching(&[FileId(file)]);
2089        map[&FileId(file)].iter().map(|root| root.0).collect()
2090    }
2091
2092    #[test]
2093    fn per_entry_reach_applies_the_replacement_mask_of_each_test() {
2094        // 0 is a test that mocks 2 and imports it through 1.
2095        // 3 is a test that imports 2 directly.
2096        let graph = build_reachability_graph_with_replacements(
2097            4,
2098            &[(0, 1, false), (1, 2, false), (3, 2, false)],
2099            &[],
2100            &[0, 3],
2101            &[ResolvedReplacedModuleTarget {
2102                source_file: FileId(0),
2103                target_file: FileId(2),
2104            }],
2105        );
2106
2107        assert_eq!(reaching(&graph, 2), vec![3]);
2108        assert_eq!(reaching(&graph, 1), vec![0]);
2109    }
2110
2111    #[test]
2112    fn per_entry_reach_keeps_a_masked_target_behind_a_commonjs_edge() {
2113        let graph = build_reachability_graph_with_replacements(
2114            3,
2115            &[(0, 1, true), (2, 1, false)],
2116            &[],
2117            &[0, 2],
2118            &[ResolvedReplacedModuleTarget {
2119                source_file: FileId(0),
2120                target_file: FileId(1),
2121            }],
2122        );
2123
2124        assert_eq!(reaching(&graph, 1), vec![0, 2]);
2125    }
2126
2127    #[test]
2128    fn per_entry_reach_without_masks_lists_each_test_that_imports_the_file() {
2129        let graph = build_reachability_graph(5, &[(0, 1), (1, 2), (3, 2), (4, 1)], &[], &[0, 3]);
2130
2131        assert_eq!(reaching(&graph, 2), vec![0, 3]);
2132        assert_eq!(reaching(&graph, 1), vec![0]);
2133        assert!(reaching(&graph, 4).is_empty());
2134    }
2135
2136    #[test]
2137    fn per_entry_reach_spans_more_tests_than_one_profile_word() {
2138        // 70 tests import file 70. Test 0 mocks it, so 69 tests reach it.
2139        let tests: Vec<u32> = (0..70).collect();
2140        let edges: Vec<(u32, u32, bool)> = tests.iter().map(|&test| (test, 70, false)).collect();
2141        let graph = build_reachability_graph_with_replacements(
2142            71,
2143            &edges,
2144            &[],
2145            &tests,
2146            &[ResolvedReplacedModuleTarget {
2147                source_file: FileId(0),
2148                target_file: FileId(70),
2149            }],
2150        );
2151
2152        assert_eq!(reaching(&graph, 70), (1..70).collect::<Vec<u32>>());
2153        assert!(graph.modules[70].is_test_reachable());
2154    }
2155
2156    #[test]
2157    fn per_entry_reach_agrees_with_test_reachability() {
2158        let graph = build_reachability_graph_with_replacements(
2159            6,
2160            &[(0, 1, false), (1, 2, false), (3, 4, false), (4, 2, false)],
2161            &[],
2162            &[0, 3],
2163            &[
2164                ResolvedReplacedModuleTarget {
2165                    source_file: FileId(0),
2166                    target_file: FileId(2),
2167                },
2168                ResolvedReplacedModuleTarget {
2169                    source_file: FileId(3),
2170                    target_file: FileId(4),
2171                },
2172            ],
2173        );
2174
2175        let files: Vec<FileId> = (0..6).map(FileId).collect();
2176        let map = graph.test_entry_points_reaching(&files);
2177        for file in &files {
2178            assert_eq!(
2179                !map[file].is_empty(),
2180                graph.modules[file.0 as usize].is_test_reachable(),
2181                "file{}",
2182                file.0
2183            );
2184        }
2185        assert_eq!(map[&FileId(1)], vec![FileId(0)]);
2186        assert!(map[&FileId(2)].is_empty());
2187    }
2188
2189    /// Classify the first export of `file` with the given test files.
2190    fn reach_of(
2191        graph: &ModuleGraph,
2192        file: u32,
2193        tests: &[u32],
2194    ) -> crate::graph::ExportTestReachResult {
2195        let module = &graph.modules[file as usize];
2196        graph.export_test_reach(module.file_id, &module.exports[0], &|id| {
2197            tests.contains(&id.0)
2198        })
2199    }
2200
2201    #[test]
2202    fn test_reach_without_mocks_reports_no_mocks() {
2203        let graph = build_reachability_graph(2, &[(0, 1)], &[], &[0]);
2204
2205        assert_eq!(graph.test_masking_state(), TestMaskingState::NoMocks);
2206        let reach = reach_of(&graph, 1, &[0]);
2207        assert_eq!(reach.reach, ExportTestReach::Direct);
2208        assert_eq!(reach.tests, vec![FileId(0)]);
2209    }
2210
2211    #[test]
2212    fn test_reach_through_a_non_test_module_is_transitive() {
2213        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[], &[0]);
2214
2215        assert_eq!(reach_of(&graph, 2, &[0]).reach, ExportTestReach::Transitive);
2216    }
2217
2218    #[test]
2219    fn test_reach_without_a_reference_separates_file_reach() {
2220        let files: Vec<_> = (0..3)
2221            .map(|id| DiscoveredFile {
2222                id: FileId(id),
2223                path: PathBuf::from(format!("/project/file{id}.ts")),
2224                size_bytes: 100,
2225            })
2226            .collect();
2227        let export = || {
2228            vec![fallow_types::extract::ExportInfo {
2229                name: ExportName::Named("value".to_string()),
2230                local_name: Some("value".to_string()),
2231                is_type_only: false,
2232                visibility: VisibilityTag::None,
2233                expected_unused_reason: None,
2234                span: oxc_span::Span::new(0, 20),
2235                members: Vec::new(),
2236                is_side_effect_used: false,
2237                super_class: None,
2238                deprecated: false,
2239                deprecated_reason: None,
2240            }]
2241            .into()
2242        };
2243        let modules = vec![
2244            ResolvedModule {
2245                file_id: FileId(0),
2246                path: files[0].path.clone(),
2247                resolved_imports: vec![intermediate_import(
2248                    "./file1",
2249                    FileId(1),
2250                    ImportedName::SideEffect,
2251                    false,
2252                )],
2253                ..ResolvedModule::default()
2254            },
2255            ResolvedModule {
2256                file_id: FileId(1),
2257                path: files[1].path.clone(),
2258                exports: export(),
2259                ..ResolvedModule::default()
2260            },
2261            ResolvedModule {
2262                file_id: FileId(2),
2263                path: files[2].path.clone(),
2264                exports: export(),
2265                ..ResolvedModule::default()
2266            },
2267        ];
2268        let test_entry_points = vec![EntryPoint {
2269            path: files[0].path.clone(),
2270            source: EntryPointSource::TestFile,
2271        }];
2272        let graph = ModuleGraph::build_with_reachability_roots_and_replacements(
2273            &modules,
2274            &[],
2275            &test_entry_points,
2276            &[],
2277            &test_entry_points,
2278            &files,
2279        );
2280
2281        assert_eq!(reach_of(&graph, 1, &[0]).reach, ExportTestReach::None);
2282        assert_eq!(reach_of(&graph, 2, &[0]).reach, ExportTestReach::NoneFile);
2283    }
2284
2285    #[test]
2286    fn test_reach_reports_an_esm_mask_on_a_direct_import() {
2287        let graph = build_reachability_graph_with_replacements(
2288            2,
2289            &[(0, 1, false)],
2290            &[],
2291            &[0],
2292            &[ResolvedReplacedModuleTarget {
2293                source_file: FileId(0),
2294                target_file: FileId(1),
2295            }],
2296        );
2297
2298        assert_eq!(graph.test_masking_state(), TestMaskingState::Active);
2299        // The masked module is not test-reachable, so without the mask check
2300        // the export would read as `NoneFile`.
2301        assert!(!graph.modules[1].is_test_reachable());
2302        let reach = reach_of(&graph, 1, &[0]);
2303        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2304        assert_eq!(reach.tests, vec![FileId(0)]);
2305        assert_eq!(reach.mocked_targets, vec![FileId(1)]);
2306    }
2307
2308    #[test]
2309    fn test_reach_reports_a_mask_behind_a_barrel() {
2310        let graph = build_masked_re_export_graph(false, false);
2311        let reach = reach_of(&graph, 2, &[0]);
2312
2313        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2314        assert_eq!(reach.mocked_targets, vec![FileId(2)]);
2315    }
2316
2317    #[test]
2318    fn test_reach_names_a_mocked_intermediate_barrel() {
2319        let graph = build_intermediate_replacement_graph(false, false, false);
2320        let reach = reach_of(&graph, 2, &[0]);
2321
2322        // An alternate route keeps the target test-reachable, but the only
2323        // reference passes through the mocked barrel.
2324        assert!(graph.modules[2].is_test_reachable());
2325        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2326        assert_eq!(reach.mocked_targets, vec![FileId(1)]);
2327    }
2328
2329    #[test]
2330    fn test_reach_keeps_a_commonjs_require_unmasked() {
2331        let graph = build_reachability_graph_with_replacements(
2332            2,
2333            &[(0, 1, true)],
2334            &[],
2335            &[0],
2336            &[ResolvedReplacedModuleTarget {
2337                source_file: FileId(0),
2338                target_file: FileId(1),
2339            }],
2340        );
2341
2342        assert_eq!(reach_of(&graph, 1, &[0]).reach, ExportTestReach::Direct);
2343    }
2344
2345    #[test]
2346    fn test_reach_through_a_required_barrel_checks_only_esm_hops() {
2347        let barrel_mocked = build_intermediate_replacement_graph(true, false, false);
2348        assert_eq!(
2349            reach_of(&barrel_mocked, 2, &[0]).reach,
2350            ExportTestReach::Direct
2351        );
2352
2353        let target_mocked = build_intermediate_replacement_graph(true, false, true);
2354        let reach = reach_of(&target_mocked, 2, &[0]);
2355        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2356        assert_eq!(reach.mocked_targets, vec![FileId(2)]);
2357    }
2358
2359    #[test]
2360    fn test_reach_with_an_unmasked_second_root_is_direct() {
2361        let graph = build_reachability_graph_with_replacements(
2362            3,
2363            &[(0, 2, false), (1, 2, false)],
2364            &[],
2365            &[0, 1],
2366            &[ResolvedReplacedModuleTarget {
2367                source_file: FileId(0),
2368                target_file: FileId(2),
2369            }],
2370        );
2371        let reach = reach_of(&graph, 2, &[0, 1]);
2372
2373        assert_eq!(reach.reach, ExportTestReach::Direct);
2374        assert_eq!(reach.tests, vec![FileId(1)]);
2375    }
2376
2377    #[test]
2378    fn test_reach_survives_graph_cache_serialization() {
2379        let graph = build_masked_re_export_graph(false, false);
2380        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
2381        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
2382
2383        assert_eq!(decoded.test_masking_state(), TestMaskingState::Active);
2384        assert_eq!(
2385            reach_of(&decoded, 2, &[0]).reach,
2386            ExportTestReach::MockedOnly
2387        );
2388    }
2389}