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                        let pattern = fallow_types::extract::DynamicImportPattern {
821                            prefix: "./modules/".to_string(),
822                            suffix: None,
823                            span: oxc_span::Span::new(0, 10),
824                            mechanism,
825                            excludes: Vec::new(),
826                            imported_name: fallow_types::extract::ImportedName::Namespace,
827                        };
828                        (pattern, vec![FileId(1)])
829                    })
830                    .collect(),
831                ..ResolvedModule::default()
832            },
833            ResolvedModule {
834                file_id: FileId(1),
835                path: files[1].path.clone(),
836                exports: vec![fallow_types::extract::ExportInfo {
837                    name: ExportName::Named("value".to_string()),
838                    local_name: Some("value".to_string()),
839                    is_type_only: false,
840                    visibility: VisibilityTag::None,
841                    expected_unused_reason: None,
842                    span: oxc_span::Span::new(0, 20),
843                    members: Vec::new(),
844                    is_side_effect_used: false,
845                    super_class: None,
846                    deprecated: false,
847                    deprecated_reason: None,
848                }]
849                .into(),
850                ..ResolvedModule::default()
851            },
852        ];
853        let test_entry_points = vec![EntryPoint {
854            path: files[0].path.clone(),
855            source: EntryPointSource::TestFile,
856        }];
857        ModuleGraph::build_with_reachability_roots_and_replacements(
858            &modules,
859            &[ResolvedReplacedModuleTarget {
860                source_file: FileId(0),
861                target_file: FileId(1),
862            }],
863            &test_entry_points,
864            &[],
865            &test_entry_points,
866            &files,
867        )
868    }
869
870    fn intermediate_import(
871        source: &str,
872        target: FileId,
873        imported_name: ImportedName,
874        commonjs: bool,
875    ) -> ResolvedImport {
876        ResolvedImport {
877            info: ImportInfo {
878                source: source.to_string(),
879                imported_name,
880                local_name: "value".to_string(),
881                is_type_only: false,
882                is_type_only_star: false,
883                from_style: false,
884                span: oxc_span::Span::new(0, 10),
885                source_span: oxc_span::Span::default(),
886            },
887            target: if commonjs {
888                ResolveResult::CommonJsInternalModule(target)
889            } else {
890                ResolveResult::InternalModule(target)
891            },
892        }
893    }
894
895    fn intermediate_modules(
896        files: &[DiscoveredFile],
897        commonjs_to_barrel: bool,
898        include_cycle: bool,
899    ) -> Vec<ResolvedModule> {
900        let mut target_re_exports = Vec::new();
901        if include_cycle {
902            target_re_exports.push(ResolvedReExport {
903                info: ReExportInfo {
904                    source: "./barrel".to_string(),
905                    imported_name: "*".to_string(),
906                    exported_name: "*".to_string(),
907                    is_type_only: false,
908                    span: oxc_span::Span::new(20, 30),
909                    ..Default::default()
910                },
911                target: ResolveResult::InternalModule(FileId(1)),
912            });
913        }
914        vec![
915            ResolvedModule {
916                file_id: FileId(0),
917                path: files[0].path.clone(),
918                resolved_imports: vec![
919                    intermediate_import(
920                        "./barrel",
921                        FileId(1),
922                        ImportedName::Named("value".to_string()),
923                        commonjs_to_barrel,
924                    ),
925                    intermediate_import("./alternate", FileId(3), ImportedName::SideEffect, false),
926                ],
927                ..ResolvedModule::default()
928            },
929            ResolvedModule {
930                file_id: FileId(1),
931                path: files[1].path.clone(),
932                re_exports: vec![ResolvedReExport {
933                    info: ReExportInfo {
934                        source: "./target".to_string(),
935                        imported_name: "value".to_string(),
936                        exported_name: "value".to_string(),
937                        is_type_only: false,
938                        span: oxc_span::Span::new(0, 10),
939                        ..Default::default()
940                    },
941                    target: ResolveResult::InternalModule(FileId(2)),
942                }],
943                ..ResolvedModule::default()
944            },
945            ResolvedModule {
946                file_id: FileId(2),
947                path: files[2].path.clone(),
948                exports: vec![fallow_types::extract::ExportInfo {
949                    name: ExportName::Named("value".to_string()),
950                    local_name: Some("value".to_string()),
951                    is_type_only: false,
952                    visibility: VisibilityTag::None,
953                    expected_unused_reason: None,
954                    span: oxc_span::Span::new(0, 20),
955                    members: Vec::new(),
956                    is_side_effect_used: false,
957                    super_class: None,
958                    deprecated: false,
959                    deprecated_reason: None,
960                }]
961                .into(),
962                re_exports: target_re_exports,
963                ..ResolvedModule::default()
964            },
965            ResolvedModule {
966                file_id: FileId(3),
967                path: files[3].path.clone(),
968                resolved_imports: vec![intermediate_import(
969                    "./target",
970                    FileId(2),
971                    ImportedName::SideEffect,
972                    false,
973                )],
974                ..ResolvedModule::default()
975            },
976        ]
977    }
978
979    fn build_intermediate_replacement_graph(
980        commonjs_to_barrel: bool,
981        include_cycle: bool,
982        mask_final_target: bool,
983    ) -> ModuleGraph {
984        let files: Vec<_> = (0..4)
985            .map(|id| DiscoveredFile {
986                id: FileId(id),
987                path: PathBuf::from(format!("/project/file{id}.ts")),
988                size_bytes: 100,
989            })
990            .collect();
991        let modules = intermediate_modules(&files, commonjs_to_barrel, include_cycle);
992        let test_entry_points = vec![EntryPoint {
993            path: files[0].path.clone(),
994            source: EntryPointSource::TestFile,
995        }];
996        let mut replacements = vec![ResolvedReplacedModuleTarget {
997            source_file: FileId(0),
998            target_file: FileId(1),
999        }];
1000        if mask_final_target {
1001            replacements.push(ResolvedReplacedModuleTarget {
1002                source_file: FileId(0),
1003                target_file: FileId(2),
1004            });
1005        }
1006
1007        ModuleGraph::build_with_reachability_roots_and_replacements(
1008            &modules,
1009            &replacements,
1010            &test_entry_points,
1011            &[],
1012            &test_entry_points,
1013            &files,
1014        )
1015    }
1016
1017    #[test]
1018    fn entry_point_is_reachable() {
1019        let graph = build_reachability_graph(1, &[], &[0], &[]);
1020        assert!(graph.modules[0].is_reachable());
1021    }
1022
1023    #[test]
1024    fn direct_dependency_is_reachable() {
1025        let graph = build_reachability_graph(2, &[(0, 1)], &[0], &[]);
1026        assert!(graph.modules[0].is_reachable());
1027        assert!(graph.modules[1].is_reachable());
1028    }
1029
1030    #[test]
1031    fn chain_reachability_a_b_c() {
1032        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[0], &[]);
1033        assert!(graph.modules[0].is_reachable());
1034        assert!(graph.modules[1].is_reachable());
1035        assert!(graph.modules[2].is_reachable());
1036    }
1037
1038    #[test]
1039    fn deep_chain_all_reachable() {
1040        let graph = build_reachability_graph(5, &[(0, 1), (1, 2), (2, 3), (3, 4)], &[0], &[]);
1041        for (i, module) in graph.modules.iter().enumerate() {
1042            assert!(
1043                module.is_reachable(),
1044                "file{i} should be reachable through chain"
1045            );
1046        }
1047    }
1048
1049    #[test]
1050    fn disconnected_file_is_unreachable() {
1051        let graph = build_reachability_graph(3, &[(0, 1)], &[0], &[]);
1052        assert!(graph.modules[0].is_reachable());
1053        assert!(graph.modules[1].is_reachable());
1054        assert!(!graph.modules[2].is_reachable());
1055    }
1056
1057    #[test]
1058    fn no_entry_points_all_unreachable() {
1059        let graph = build_reachability_graph(2, &[(0, 1)], &[], &[]);
1060        assert!(!graph.modules[0].is_reachable());
1061        assert!(!graph.modules[1].is_reachable());
1062    }
1063
1064    #[test]
1065    fn cycle_both_reachable_when_entry() {
1066        let graph = build_reachability_graph(2, &[(0, 1), (1, 0)], &[0], &[]);
1067        assert!(graph.modules[0].is_reachable());
1068        assert!(graph.modules[1].is_reachable());
1069    }
1070
1071    #[test]
1072    fn three_node_cycle_all_reachable() {
1073        let graph = build_reachability_graph(3, &[(0, 1), (1, 2), (2, 0)], &[0], &[]);
1074        for (i, module) in graph.modules.iter().enumerate() {
1075            assert!(
1076                module.is_reachable(),
1077                "file{i} in cycle should be reachable"
1078            );
1079        }
1080    }
1081
1082    #[test]
1083    fn cycle_not_reachable_from_entry() {
1084        let graph = build_reachability_graph(3, &[(1, 2), (2, 1)], &[0], &[]);
1085        assert!(graph.modules[0].is_reachable());
1086        assert!(!graph.modules[1].is_reachable());
1087        assert!(!graph.modules[2].is_reachable());
1088    }
1089
1090    #[test]
1091    fn runtime_reachable_only_from_runtime_entries() {
1092        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0], &[2]);
1093        assert!(graph.modules[0].is_runtime_reachable());
1094        assert!(graph.modules[1].is_runtime_reachable());
1095        assert!(!graph.modules[2].is_runtime_reachable());
1096        assert!(!graph.modules[3].is_runtime_reachable());
1097    }
1098
1099    #[test]
1100    fn test_reachable_only_from_test_entries() {
1101        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0], &[2]);
1102        assert!(!graph.modules[0].is_test_reachable());
1103        assert!(!graph.modules[1].is_test_reachable());
1104        assert!(graph.modules[2].is_test_reachable());
1105        assert!(graph.modules[3].is_test_reachable());
1106    }
1107
1108    /// File 0 is a test root. It imports `x` from file 1, with `import type`
1109    /// when `type_only` is set. With `masked`, file 0 also mocks the
1110    /// unrelated file 2, so the graph uses the profiled traversal instead of
1111    /// the plain BFS.
1112    fn build_type_only_test_import_graph(type_only: bool, masked: bool) -> ModuleGraph {
1113        let edges = [ReachabilityEdge {
1114            source: 0,
1115            target: 1,
1116            is_commonjs: false,
1117            is_type_only: type_only,
1118        }];
1119        let replacements = if masked {
1120            vec![ResolvedReplacedModuleTarget {
1121                source_file: FileId(0),
1122                target_file: FileId(2),
1123            }]
1124        } else {
1125            Vec::new()
1126        };
1127        build_reachability_graph_with_edges(3, &edges, &[], &[0], &replacements)
1128    }
1129
1130    #[test]
1131    fn type_only_test_import_gives_no_export_coverage() {
1132        for masked in [false, true] {
1133            let graph = build_type_only_test_import_graph(true, masked);
1134            assert_eq!(graph.test_reachability_index.profile_count > 0, masked);
1135            let export = &graph.modules[1].exports[0];
1136            assert_eq!(export.references.len(), 1, "masked: {masked}");
1137            assert_eq!(
1138                export.references[0].namespace,
1139                ExportNamespace::Type,
1140                "masked: {masked}"
1141            );
1142
1143            assert!(
1144                !graph.is_test_reference_covered(export, 0),
1145                "masked: {masked}"
1146            );
1147            assert!(
1148                !graph.is_any_test_reference_covered(export),
1149                "masked: {masked}"
1150            );
1151        }
1152    }
1153
1154    /// File 0 is a test root and file 3 a runtime root. Both import file 1,
1155    /// the test with `import type` when `type_only` is set. File 1 imports
1156    /// file 2 by value. With `masked`, file 0 also mocks the unrelated file 4.
1157    fn build_type_only_test_chain_graph(type_only: bool, masked: bool) -> ModuleGraph {
1158        let edge = |source, target, is_type_only| ReachabilityEdge {
1159            source,
1160            target,
1161            is_commonjs: false,
1162            is_type_only,
1163        };
1164        let edges = [edge(0, 1, type_only), edge(1, 2, false), edge(3, 1, false)];
1165        let replacements = if masked {
1166            vec![ResolvedReplacedModuleTarget {
1167                source_file: FileId(0),
1168                target_file: FileId(4),
1169            }]
1170        } else {
1171            Vec::new()
1172        };
1173        build_reachability_graph_with_edges(5, &edges, &[3], &[0], &replacements)
1174    }
1175
1176    #[test]
1177    fn type_only_test_import_gives_no_file_test_reach() {
1178        for masked in [false, true] {
1179            let graph = build_type_only_test_chain_graph(true, masked);
1180            assert_eq!(graph.test_reachability_index.profile_count > 0, masked);
1181            assert!(graph.modules[0].is_test_reachable(), "masked: {masked}");
1182            assert!(!graph.modules[1].is_test_reachable(), "masked: {masked}");
1183            assert!(!graph.modules[2].is_test_reachable(), "masked: {masked}");
1184            assert!(
1185                graph
1186                    .test_entry_points_reaching(&[FileId(1), FileId(2)])
1187                    .values()
1188                    .all(Vec::is_empty),
1189                "masked: {masked}"
1190            );
1191            // Dead-code reachability still follows the type-only edge.
1192            assert!(graph.modules[1].is_reachable(), "masked: {masked}");
1193            assert!(graph.modules[2].is_reachable(), "masked: {masked}");
1194        }
1195    }
1196
1197    #[test]
1198    fn value_test_import_gives_file_test_reach() {
1199        for masked in [false, true] {
1200            let graph = build_type_only_test_chain_graph(false, masked);
1201            assert!(graph.modules[1].is_test_reachable(), "masked: {masked}");
1202            assert!(graph.modules[2].is_test_reachable(), "masked: {masked}");
1203            let reaching = graph.test_entry_points_reaching(&[FileId(2)]);
1204            assert_eq!(reaching[&FileId(2)], vec![FileId(0)], "masked: {masked}");
1205        }
1206    }
1207
1208    #[test]
1209    fn value_test_import_gives_export_coverage() {
1210        for masked in [false, true] {
1211            let graph = build_type_only_test_import_graph(false, masked);
1212            let export = &graph.modules[1].exports[0];
1213
1214            assert!(
1215                graph.is_test_reference_covered(export, 0),
1216                "masked: {masked}"
1217            );
1218        }
1219    }
1220
1221    #[test]
1222    fn esm_replacement_masks_target_only_from_test_reachability() {
1223        let graph = build_reachability_graph_with_replacements(
1224            3,
1225            &[(0, 1, false), (1, 2, false)],
1226            &[],
1227            &[0],
1228            &[ResolvedReplacedModuleTarget {
1229                source_file: FileId(0),
1230                target_file: FileId(1),
1231            }],
1232        );
1233
1234        assert!(graph.modules[1].is_reachable());
1235        assert!(!graph.modules[1].is_test_reachable());
1236        assert!(!graph.modules[2].is_test_reachable());
1237        assert_eq!(graph.test_reachability_index.profile_count, 1);
1238        assert!(graph.test_reachability_index.profile_reaches(FileId(0), 0));
1239        assert!(!graph.test_reachability_index.profile_reaches(FileId(1), 0));
1240    }
1241
1242    #[test]
1243    fn commonjs_path_preserves_a_replaced_target() {
1244        let graph = build_reachability_graph_with_replacements(
1245            2,
1246            &[(0, 1, true)],
1247            &[],
1248            &[0],
1249            &[ResolvedReplacedModuleTarget {
1250                source_file: FileId(0),
1251                target_file: FileId(1),
1252            }],
1253        );
1254
1255        assert!(graph.modules[1].is_test_reachable());
1256    }
1257
1258    #[test]
1259    fn mixed_commonjs_and_esm_symbols_preserve_a_replaced_target() {
1260        let graph = build_reachability_graph_with_replacements(
1261            2,
1262            &[(0, 1, false), (0, 1, true)],
1263            &[],
1264            &[0],
1265            &[ResolvedReplacedModuleTarget {
1266                source_file: FileId(0),
1267                target_file: FileId(1),
1268            }],
1269        );
1270
1271        assert!(graph.modules[1].is_test_reachable());
1272    }
1273
1274    #[test]
1275    fn replacement_masks_a_target_behind_an_esm_re_export() {
1276        let graph = build_masked_re_export_graph(false, false);
1277        let target_export = &graph.modules[2].exports[0];
1278        assert!(
1279            !target_export.references.is_empty(),
1280            "barrel consumer reference should propagate"
1281        );
1282
1283        assert!(graph.modules[1].is_test_reachable());
1284        assert!(!graph.modules[2].is_test_reachable());
1285        assert_eq!(
1286            graph.reference_path_hops(target_export, 0)[0].1,
1287            ModuleLoadMechanism::EsModule
1288        );
1289        assert!(!graph.is_test_reference_covered(target_export, 0));
1290    }
1291
1292    #[test]
1293    fn commonjs_loaded_barrel_does_not_bypass_its_esm_re_export() {
1294        let graph = build_masked_re_export_graph(true, false);
1295        let target_export = &graph.modules[2].exports[0];
1296        assert!(
1297            !target_export.references.is_empty(),
1298            "barrel consumer reference should propagate"
1299        );
1300
1301        assert!(graph.modules[1].is_test_reachable());
1302        assert!(!graph.modules[2].is_test_reachable());
1303        assert_eq!(
1304            graph.reference_path_hops(target_export, 0)[0].1,
1305            ModuleLoadMechanism::EsModule
1306        );
1307        assert!(!graph.is_test_reference_covered(target_export, 0));
1308    }
1309
1310    #[test]
1311    fn direct_commonjs_and_esm_re_export_retain_distinct_coverage() {
1312        let graph = build_masked_re_export_graph(false, true);
1313        let export = &graph.modules[2].exports[0];
1314
1315        assert_eq!(export.references.len(), 2);
1316        let esm = (0..export.references.len())
1317            .find(|&index| {
1318                graph.reference_path_hops(export, index)[0].1 == ModuleLoadMechanism::EsModule
1319            })
1320            .expect("ESM re-export reference");
1321        let commonjs = (0..export.references.len())
1322            .find(|&index| {
1323                graph.reference_path_hops(export, index)[0].1
1324                    == ModuleLoadMechanism::CommonJsRequire
1325            })
1326            .expect("direct CommonJS reference");
1327        assert!(!graph.is_test_reference_covered(export, esm));
1328        assert!(graph.is_test_reference_covered(export, commonjs));
1329    }
1330
1331    #[test]
1332    fn mocked_intermediate_barrel_blocks_a_reference_despite_an_alternate_target_route() {
1333        let graph = build_intermediate_replacement_graph(false, false, false);
1334        let export = &graph.modules[2].exports[0];
1335        let hops = graph.reference_path_hops(export, 0);
1336
1337        assert!(graph.modules[2].is_test_reachable());
1338        assert_eq!(
1339            hops,
1340            vec![
1341                (FileId(2), ModuleLoadMechanism::EsModule),
1342                (FileId(1), ModuleLoadMechanism::EsModule),
1343            ]
1344        );
1345        assert!(!graph.is_test_reference_covered(export, 0));
1346    }
1347
1348    #[test]
1349    fn mocked_re_export_cycle_member_blocks_the_cyclic_reference_path() {
1350        let graph = build_intermediate_replacement_graph(false, true, false);
1351        let export = &graph.modules[2].exports[0];
1352
1353        assert!(
1354            graph
1355                .re_export_cycles
1356                .iter()
1357                .any(|cycle| cycle.file_ids == vec![FileId(1), FileId(2)])
1358        );
1359        assert!(graph.modules[2].is_test_reachable());
1360        assert!(!graph.is_test_reference_covered(export, 0));
1361    }
1362
1363    #[test]
1364    fn commonjs_barrel_hop_bypasses_only_its_own_replacement() {
1365        let graph = build_intermediate_replacement_graph(true, false, false);
1366        let export = &graph.modules[2].exports[0];
1367
1368        assert_eq!(
1369            graph.reference_path_hops(export, 0),
1370            vec![
1371                (FileId(2), ModuleLoadMechanism::EsModule),
1372                (FileId(1), ModuleLoadMechanism::CommonJsRequire),
1373            ]
1374        );
1375        assert!(graph.is_test_reference_covered(export, 0));
1376    }
1377
1378    #[test]
1379    fn commonjs_barrel_hop_does_not_bypass_a_replaced_esm_target() {
1380        let graph = build_intermediate_replacement_graph(true, false, true);
1381        let export = &graph.modules[2].exports[0];
1382
1383        assert!(!graph.is_test_reference_covered(export, 0));
1384    }
1385
1386    #[test]
1387    fn reference_paths_survive_graph_cache_serialization() {
1388        let graph = build_intermediate_replacement_graph(false, false, false);
1389        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
1390        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
1391        let export = &decoded.modules[2].exports[0];
1392
1393        assert_eq!(
1394            decoded.reference_path_hops(export, 0),
1395            vec![
1396                (FileId(2), ModuleLoadMechanism::EsModule),
1397                (FileId(1), ModuleLoadMechanism::EsModule),
1398            ]
1399        );
1400        assert!(!decoded.is_test_reference_covered(export, 0));
1401    }
1402
1403    #[test]
1404    fn require_context_keeps_a_replaced_target_covered() {
1405        let graph = build_masked_pattern_graph(&[ModuleLoadMechanism::CommonJsRequire]);
1406        let export = &graph.modules[1].exports[0];
1407
1408        assert!(graph.modules[1].is_test_reachable());
1409        assert_eq!(
1410            graph.reference_path_hops(export, 0)[0].1,
1411            ModuleLoadMechanism::CommonJsRequire
1412        );
1413        assert!(graph.is_test_reference_covered(export, 0));
1414    }
1415
1416    #[test]
1417    fn overlapping_patterns_preserve_exact_esm_and_commonjs_coverage() {
1418        let graph = build_masked_pattern_graph(&[
1419            ModuleLoadMechanism::EsModule,
1420            ModuleLoadMechanism::CommonJsRequire,
1421        ]);
1422        let export = &graph.modules[1].exports[0];
1423
1424        assert!(graph.modules[1].is_test_reachable());
1425        assert_eq!(export.references.len(), 2);
1426        let esm = (0..export.references.len())
1427            .find(|&index| {
1428                graph.reference_path_hops(export, index)[0].1 == ModuleLoadMechanism::EsModule
1429            })
1430            .expect("ESM pattern reference");
1431        let commonjs = (0..export.references.len())
1432            .find(|&index| {
1433                graph.reference_path_hops(export, index)[0].1
1434                    == ModuleLoadMechanism::CommonJsRequire
1435            })
1436            .expect("CommonJS pattern reference");
1437        assert!(!graph.is_test_reference_covered(export, esm));
1438        assert!(graph.is_test_reference_covered(export, commonjs));
1439    }
1440
1441    #[test]
1442    fn replacement_stops_before_a_masked_cycle_member() {
1443        let graph = build_reachability_graph_with_replacements(
1444            3,
1445            &[(0, 1, false), (1, 2, false), (2, 1, false)],
1446            &[],
1447            &[0],
1448            &[ResolvedReplacedModuleTarget {
1449                source_file: FileId(0),
1450                target_file: FileId(2),
1451            }],
1452        );
1453
1454        assert!(graph.modules[0].is_test_reachable());
1455        assert!(graph.modules[1].is_test_reachable());
1456        assert!(!graph.modules[2].is_test_reachable());
1457    }
1458
1459    #[test]
1460    fn identical_masks_share_one_reachability_profile() {
1461        let graph = build_reachability_graph_with_replacements(
1462            3,
1463            &[(0, 2, false), (1, 2, false)],
1464            &[],
1465            &[0, 1],
1466            &[
1467                ResolvedReplacedModuleTarget {
1468                    source_file: FileId(1),
1469                    target_file: FileId(2),
1470                },
1471                ResolvedReplacedModuleTarget {
1472                    source_file: FileId(0),
1473                    target_file: FileId(2),
1474                },
1475            ],
1476        );
1477
1478        assert_eq!(graph.test_reachability_index.profile_count, 1);
1479        assert!(graph.test_reachability_index.profile_masks(FileId(2), 0));
1480        assert!(graph.test_reachability_index.profile_reaches(FileId(0), 0));
1481        assert!(graph.test_reachability_index.profile_reaches(FileId(1), 0));
1482        assert!(!graph.modules[2].is_test_reachable());
1483    }
1484
1485    #[test]
1486    fn an_unmasked_root_keeps_the_shared_target_test_reachable() {
1487        let graph = build_reachability_graph_with_replacements(
1488            3,
1489            &[(0, 2, false), (1, 2, false)],
1490            &[],
1491            &[0, 1],
1492            &[ResolvedReplacedModuleTarget {
1493                source_file: FileId(0),
1494                target_file: FileId(2),
1495            }],
1496        );
1497
1498        assert_eq!(graph.test_reachability_index.profile_count, 2);
1499        assert!(graph.modules[2].is_test_reachable());
1500        assert!(!graph.test_reachability_index.profile_masks(FileId(2), 0));
1501        assert!(graph.test_reachability_index.profile_reaches(FileId(1), 0));
1502        assert!(graph.test_reachability_index.profile_reaches(FileId(2), 0));
1503        assert!(graph.test_reachability_index.profile_masks(FileId(2), 1));
1504        assert!(graph.test_reachability_index.profile_reaches(FileId(0), 1));
1505        let export = &graph.modules[2].exports[0];
1506        let reference_from = |source| {
1507            export
1508                .references
1509                .iter()
1510                .position(|reference| reference.from_file == source)
1511                .expect("both test roots reference the target export")
1512        };
1513        assert!(!graph.is_test_reference_covered(export, reference_from(FileId(0))));
1514        assert!(graph.is_test_reference_covered(export, reference_from(FileId(1))));
1515    }
1516
1517    #[test]
1518    fn replacement_declared_outside_a_test_root_keeps_the_fast_path() {
1519        let graph = build_reachability_graph_with_replacements(
1520            3,
1521            &[(0, 1, false)],
1522            &[],
1523            &[0],
1524            &[ResolvedReplacedModuleTarget {
1525                source_file: FileId(2),
1526                target_file: FileId(1),
1527            }],
1528        );
1529
1530        assert_eq!(graph.test_reachability_index.profile_count, 0);
1531        assert!(graph.modules[1].is_test_reachable());
1532    }
1533
1534    #[test]
1535    fn test_reachability_plan_uses_no_roots_without_test_entries() {
1536        let test_roots = FxHashSet::default();
1537
1538        let plan = TestReachabilityPlan::new(&test_roots, &[], 3);
1539
1540        assert!(matches!(&plan, TestReachabilityPlan::NoRoots));
1541        assert!(!plan.requires_reference_provenance());
1542    }
1543
1544    #[test]
1545    fn test_reachability_plan_ignores_replacements_outside_test_roots() {
1546        let test_roots = FxHashSet::from_iter([FileId(0)]);
1547        let replacements = [ResolvedReplacedModuleTarget {
1548            source_file: FileId(1),
1549            target_file: FileId(2),
1550        }];
1551
1552        let plan = TestReachabilityPlan::new(&test_roots, &replacements, 3);
1553
1554        assert!(matches!(&plan, TestReachabilityPlan::Legacy { .. }));
1555        assert!(!plan.requires_reference_provenance());
1556    }
1557
1558    #[test]
1559    fn test_reachability_plan_ignores_out_of_capacity_targets() {
1560        let test_roots = FxHashSet::from_iter([FileId(0)]);
1561        let replacements = [ResolvedReplacedModuleTarget {
1562            source_file: FileId(0),
1563            target_file: FileId(3),
1564        }];
1565
1566        let plan = TestReachabilityPlan::new(&test_roots, &replacements, 3);
1567
1568        assert!(matches!(&plan, TestReachabilityPlan::Legacy { .. }));
1569        assert!(!plan.requires_reference_provenance());
1570    }
1571
1572    #[test]
1573    fn test_reachability_plan_groups_roots_by_normalized_replacement_mask() {
1574        let test_roots = FxHashSet::from_iter([FileId(0), FileId(1), FileId(2)]);
1575        let replacements = [
1576            ResolvedReplacedModuleTarget {
1577                source_file: FileId(0),
1578                target_file: FileId(4),
1579            },
1580            ResolvedReplacedModuleTarget {
1581                source_file: FileId(0),
1582                target_file: FileId(4),
1583            },
1584            ResolvedReplacedModuleTarget {
1585                source_file: FileId(1),
1586                target_file: FileId(4),
1587            },
1588        ];
1589
1590        let plan = TestReachabilityPlan::new(&test_roots, &replacements, 5);
1591
1592        assert!(plan.requires_reference_provenance());
1593        let TestReachabilityPlan::Profiled { profiles } = plan else {
1594            panic!("valid test-root replacements must use profiled reachability");
1595        };
1596        assert_eq!(
1597            profiles,
1598            vec![
1599                TestReachabilityProfile {
1600                    masked_targets: Vec::new(),
1601                    roots: vec![FileId(2)],
1602                },
1603                TestReachabilityProfile {
1604                    masked_targets: vec![FileId(4)],
1605                    roots: vec![FileId(0), FileId(1)],
1606                },
1607            ]
1608        );
1609    }
1610
1611    type UniqueMaskInputs = (
1612        Vec<u32>,
1613        Vec<(u32, u32, bool)>,
1614        Vec<ResolvedReplacedModuleTarget>,
1615    );
1616
1617    /// Build roots 0..count, each importing and mocking a unique target at
1618    /// count + root, so every root lands in its own mask profile.
1619    fn unique_mask_graph_inputs(count: u32) -> UniqueMaskInputs {
1620        let test_roots: Vec<u32> = (0..count).collect();
1621        let mut edges = Vec::with_capacity(test_roots.len());
1622        let mut replacements = Vec::with_capacity(test_roots.len());
1623        for &root in &test_roots {
1624            let masked_target = count + root;
1625            edges.push((root, masked_target, false));
1626            replacements.push(ResolvedReplacedModuleTarget {
1627                source_file: FileId(root),
1628                target_file: FileId(masked_target),
1629            });
1630        }
1631        (test_roots, edges, replacements)
1632    }
1633
1634    #[test]
1635    #[cfg_attr(
1636        miri,
1637        ignore = "thousands of synthetic profiles are too slow under miri"
1638    )]
1639    fn profile_count_at_the_safety_cap_keeps_profiled_masking() {
1640        let count = u32::try_from(super::PROFILE_COUNT_SAFETY_CAP).expect("cap fits in u32");
1641        let total = count as usize * 2;
1642        let (test_roots, edges, replacements) = unique_mask_graph_inputs(count);
1643        let graph = build_reachability_graph_with_replacements(
1644            total,
1645            &edges,
1646            &[],
1647            &test_roots,
1648            &replacements,
1649        );
1650
1651        assert_eq!(
1652            graph.test_reachability_index.profile_count,
1653            super::PROFILE_COUNT_SAFETY_CAP
1654        );
1655        // Profiles sort by mask, so profile 0 belongs to root 0 whose unique
1656        // target is FileId(count).
1657        assert!(
1658            graph
1659                .test_reachability_index
1660                .profile_masks(FileId(count), 0)
1661        );
1662        assert!(graph.modules[0].is_test_reachable());
1663        // Masking still applies under the cap: the mocked target is only
1664        // imported by the root that replaces it, so it stays unreachable.
1665        assert!(!graph.modules[count as usize].is_test_reachable());
1666        assert_eq!(graph.test_masking_state(), TestMaskingState::Active);
1667    }
1668
1669    #[test]
1670    #[cfg_attr(
1671        miri,
1672        ignore = "thousands of synthetic profiles are too slow under miri"
1673    )]
1674    fn profile_count_above_the_safety_cap_falls_back_to_coarse_reachability() {
1675        let count = u32::try_from(super::PROFILE_COUNT_SAFETY_CAP * 4).expect("cap fits in u32");
1676        let total = count as usize * 2;
1677        let (test_roots, edges, replacements) = unique_mask_graph_inputs(count);
1678        let graph = build_reachability_graph_with_replacements(
1679            total,
1680            &edges,
1681            &[],
1682            &test_roots,
1683            &replacements,
1684        );
1685        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1686
1687        let plan = TestReachabilityPlan::new(&root_set, &replacements, total);
1688        assert!(matches!(
1689            &plan,
1690            TestReachabilityPlan::Legacy { capped: true, .. }
1691        ));
1692        assert!(!plan.requires_reference_provenance());
1693
1694        // Fail-open: no profiles survive, and mocked targets stay
1695        // test-reachable exactly as the pre-profile coarse pass reported them.
1696        assert_eq!(graph.test_reachability_index.profile_count, 0);
1697        for &root in &test_roots {
1698            assert!(graph.modules[root as usize].is_test_reachable());
1699            assert!(graph.modules[(count + root) as usize].is_test_reachable());
1700        }
1701
1702        // The capped state is visible, and a mocked export keeps its reach
1703        // class instead of `MockedOnly`.
1704        assert_eq!(graph.test_masking_state(), TestMaskingState::Capped);
1705        let mocked = &graph.modules[count as usize];
1706        let reach =
1707            graph.export_test_reach(mocked.file_id, &mocked.exports[0], &|file| file.0 < count);
1708        assert_eq!(reach.reach, ExportTestReach::Direct);
1709    }
1710
1711    #[test]
1712    fn replacement_profiles_survive_graph_cache_serialization() {
1713        let graph = build_reachability_graph_with_replacements(
1714            2,
1715            &[(0, 1, false)],
1716            &[],
1717            &[0],
1718            &[ResolvedReplacedModuleTarget {
1719                source_file: FileId(0),
1720                target_file: FileId(1),
1721            }],
1722        );
1723
1724        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
1725        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
1726
1727        assert_eq!(decoded.test_reachability_index.profile_count, 1);
1728        assert!(decoded.test_reachability_index.profile_masks(FileId(1), 0));
1729        assert!(
1730            decoded
1731                .test_reachability_index
1732                .profile_reaches(FileId(0), 0)
1733        );
1734        assert!(
1735            !decoded
1736                .test_reachability_index
1737                .profile_reaches(FileId(1), 0)
1738        );
1739    }
1740
1741    #[test]
1742    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1743    fn many_unmasked_roots_use_one_test_traversal() {
1744        let test_roots: Vec<u32> = (0..512).collect();
1745        let graph = build_reachability_graph(512, &[], &[], &test_roots);
1746        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1747
1748        let plan = TestReachabilityPlan::new(&root_set, &[], 512);
1749        let (reachability, traversals) =
1750            capture_traversals(|| graph.collect_test_reachable(plan, 512));
1751
1752        assert_eq!(traversals, 1);
1753        let (reachable, _) = reachability.into_parts();
1754        let reachable = reachable.expect("test roots have a reachability bitset");
1755        assert!(
1756            root_set
1757                .iter()
1758                .all(|root| reachable.contains(root.0 as usize))
1759        );
1760    }
1761
1762    #[test]
1763    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1764    fn many_roots_share_one_profile_worklist() {
1765        let test_roots: Vec<u32> = (0..128).collect();
1766        let edges: Vec<_> = test_roots
1767            .iter()
1768            .copied()
1769            .map(|root| (root, 128, false))
1770            .collect();
1771        let replacements: Vec<_> = (0..64)
1772            .map(|root| ResolvedReplacedModuleTarget {
1773                source_file: FileId(root),
1774                target_file: FileId(128),
1775            })
1776            .collect();
1777        let graph = build_reachability_graph_with_replacements(
1778            129,
1779            &edges,
1780            &[],
1781            &test_roots,
1782            &replacements,
1783        );
1784        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1785
1786        let plan = TestReachabilityPlan::new(&root_set, &replacements, 129);
1787        let (reachability, traversals) =
1788            capture_traversals(|| graph.collect_test_reachable(plan, 129));
1789
1790        assert_eq!(traversals, 1);
1791        assert_eq!(reachability.dirty_word_pop_count(), 129);
1792    }
1793
1794    #[test]
1795    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1796    fn unique_masks_cross_profile_words_in_one_deterministic_worklist() {
1797        let test_roots: Vec<u32> = (0..65).collect();
1798        let mut edges = Vec::with_capacity(test_roots.len() * 2);
1799        let mut replacements = Vec::with_capacity(test_roots.len());
1800        for &root in &test_roots {
1801            let masked_target = 65 + root;
1802            edges.push((root, masked_target, false));
1803            edges.push((root, 130, false));
1804            replacements.push(ResolvedReplacedModuleTarget {
1805                source_file: FileId(root),
1806                target_file: FileId(masked_target),
1807            });
1808        }
1809        let graph = build_reachability_graph_with_replacements(
1810            131,
1811            &edges,
1812            &[],
1813            &test_roots,
1814            &replacements,
1815        );
1816        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1817
1818        let plan = TestReachabilityPlan::new(&root_set, &replacements, 131);
1819        let (reachability, traversals) =
1820            capture_traversals(|| graph.collect_test_reachable(plan, 131));
1821
1822        assert_eq!(traversals, 1);
1823        assert_eq!(reachability.dirty_word_pop_count(), 67);
1824        assert_eq!(graph.test_reachability_index.profile_count, 65);
1825        assert_eq!(graph.test_reachability_index.words_per_file, 2);
1826        assert_eq!(graph.test_reachability_index.masked_profiles.len(), 65);
1827        assert!(
1828            graph
1829                .test_reachability_index
1830                .profile_reaches(FileId(130), 0)
1831        );
1832        assert!(
1833            graph
1834                .test_reachability_index
1835                .profile_reaches(FileId(130), 64)
1836        );
1837        assert!(graph.test_reachability_index.profile_masks(FileId(65), 0));
1838        assert!(graph.test_reachability_index.profile_masks(FileId(129), 64));
1839        assert!(!graph.test_reachability_index.profile_reaches(FileId(65), 0));
1840        assert!(
1841            !graph
1842                .test_reachability_index
1843                .profile_reaches(FileId(129), 64)
1844        );
1845
1846        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
1847        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
1848        assert_eq!(decoded.test_reachability_index.profile_count, 65);
1849        assert_eq!(decoded.test_reachability_index.words_per_file, 2);
1850        assert_eq!(decoded.test_reachability_index.masked_profiles.len(), 65);
1851        assert!(
1852            decoded
1853                .test_reachability_index
1854                .profile_reaches(FileId(130), 64)
1855        );
1856        assert!(
1857            decoded
1858                .test_reachability_index
1859                .profile_masks(FileId(129), 64)
1860        );
1861    }
1862
1863    #[test]
1864    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1865    fn staggered_profile_words_propagate_without_clean_word_scans() {
1866        const PROFILE_COUNT: u32 = 65;
1867        const MASK_START: u32 = PROFILE_COUNT;
1868        const FANOUT_START: u32 = MASK_START + PROFILE_COUNT;
1869        const FANOUT_COUNT: u32 = 8;
1870
1871        let test_roots: Vec<u32> = (0..PROFILE_COUNT).collect();
1872        let mut edges = Vec::new();
1873        for root in 1..PROFILE_COUNT {
1874            edges.push((root, root - 1, false));
1875        }
1876        for target in FANOUT_START..FANOUT_START + FANOUT_COUNT {
1877            edges.push((0, target, false));
1878        }
1879        let replacements: Vec<_> = test_roots
1880            .iter()
1881            .copied()
1882            .map(|root| ResolvedReplacedModuleTarget {
1883                source_file: FileId(root),
1884                target_file: FileId(MASK_START + root),
1885            })
1886            .collect();
1887        let file_count = (FANOUT_START + FANOUT_COUNT) as usize;
1888        let graph = build_reachability_graph_with_replacements(
1889            file_count,
1890            &edges,
1891            &[],
1892            &test_roots,
1893            &replacements,
1894        );
1895        let root_set: FxHashSet<_> = test_roots.iter().copied().map(FileId).collect();
1896
1897        let plan = TestReachabilityPlan::new(&root_set, &replacements, file_count);
1898        let reachability = graph.collect_test_reachable(plan, file_count);
1899
1900        assert_eq!(graph.test_reachability_index.words_per_file, 2);
1901        let expected_dirty_word_pops =
1902            (PROFILE_COUNT * (PROFILE_COUNT + 1) / 2 + FANOUT_COUNT * PROFILE_COUNT) as usize;
1903        assert_eq!(
1904            reachability.dirty_word_pop_count(),
1905            expected_dirty_word_pops
1906        );
1907        for target in FANOUT_START..FANOUT_START + FANOUT_COUNT {
1908            assert!(
1909                graph
1910                    .test_reachability_index
1911                    .profile_reaches(FileId(target), 0)
1912            );
1913            assert!(
1914                graph
1915                    .test_reachability_index
1916                    .profile_reaches(FileId(target), 64)
1917            );
1918        }
1919    }
1920
1921    #[test]
1922    #[cfg_attr(miri, ignore = "too slow under Miri: a scale test of safe code")]
1923    fn no_profile_coverage_omits_unused_reference_provenance() {
1924        const CHAIN_LENGTH: u32 = 128;
1925
1926        let files: Vec<_> = (0..=CHAIN_LENGTH)
1927            .map(|id| DiscoveredFile {
1928                id: FileId(id),
1929                path: PathBuf::from(format!("/project/file{id}.ts")),
1930                size_bytes: 100,
1931            })
1932            .collect();
1933        let mut modules = Vec::with_capacity(files.len());
1934        modules.push(ResolvedModule {
1935            file_id: FileId(0),
1936            path: files[0].path.clone(),
1937            resolved_imports: vec![intermediate_import(
1938                "./file1",
1939                FileId(1),
1940                ImportedName::Named("value".to_string()),
1941                false,
1942            )],
1943            ..ResolvedModule::default()
1944        });
1945        for id in 1..CHAIN_LENGTH {
1946            modules.push(ResolvedModule {
1947                file_id: FileId(id),
1948                path: files[id as usize].path.clone(),
1949                re_exports: vec![ResolvedReExport {
1950                    info: ReExportInfo {
1951                        source: format!("./file{}", id + 1),
1952                        imported_name: "value".to_string(),
1953                        exported_name: "value".to_string(),
1954                        is_type_only: false,
1955                        span: oxc_span::Span::new(0, 10),
1956                        ..Default::default()
1957                    },
1958                    target: ResolveResult::InternalModule(FileId(id + 1)),
1959                }],
1960                ..ResolvedModule::default()
1961            });
1962        }
1963        modules.push(ResolvedModule {
1964            file_id: FileId(CHAIN_LENGTH),
1965            path: files[CHAIN_LENGTH as usize].path.clone(),
1966            exports: vec![fallow_types::extract::ExportInfo {
1967                name: ExportName::Named("value".to_string()),
1968                local_name: Some("value".to_string()),
1969                is_type_only: false,
1970                visibility: VisibilityTag::None,
1971                expected_unused_reason: None,
1972                span: oxc_span::Span::new(0, 20),
1973                members: Vec::new(),
1974                is_side_effect_used: false,
1975                super_class: None,
1976                deprecated: false,
1977                deprecated_reason: None,
1978            }]
1979            .into(),
1980            ..ResolvedModule::default()
1981        });
1982        let test_entry_points = vec![EntryPoint {
1983            path: files[0].path.clone(),
1984            source: EntryPointSource::TestFile,
1985        }];
1986        let graph = ModuleGraph::build_with_reachability_roots_and_replacements(
1987            &modules,
1988            &[],
1989            &test_entry_points,
1990            &[],
1991            &test_entry_points,
1992            &files,
1993        );
1994        let export = &graph.modules[CHAIN_LENGTH as usize].exports[0];
1995
1996        assert_eq!(graph.test_reachability_index.profile_count, 0);
1997        assert!(
1998            export.reference_paths.is_empty(),
1999            "the provenance side table must stay unallocated on the fast path"
2000        );
2001        assert!(graph.reference_paths.is_empty());
2002        assert!(graph.is_test_reference_covered(export, 0));
2003    }
2004
2005    #[test]
2006    fn overall_reachable_is_union_of_runtime_and_test() {
2007        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0], &[2]);
2008        for (i, module) in graph.modules.iter().enumerate() {
2009            assert!(module.is_reachable(), "file{i} should be overall-reachable");
2010        }
2011    }
2012
2013    #[test]
2014    fn shared_dependency_is_both_runtime_and_test_reachable() {
2015        let graph = build_reachability_graph(3, &[(0, 2), (1, 2)], &[0], &[1]);
2016        assert!(graph.modules[2].is_runtime_reachable());
2017        assert!(graph.modules[2].is_test_reachable());
2018        assert!(graph.modules[2].is_reachable());
2019    }
2020
2021    #[test]
2022    fn runtime_same_as_overall_reuses_bfs() {
2023        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[0], &[]);
2024        for (i, module) in graph.modules.iter().enumerate() {
2025            assert_eq!(
2026                module.is_reachable(),
2027                module.is_runtime_reachable(),
2028                "file{i}: reachable and runtime_reachable should match when runtime==overall"
2029            );
2030        }
2031    }
2032
2033    #[test]
2034    fn empty_test_entries_none_test_reachable() {
2035        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[0], &[]);
2036        for (i, module) in graph.modules.iter().enumerate() {
2037            assert!(
2038                !module.is_test_reachable(),
2039                "file{i} should not be test-reachable when no test entries exist"
2040            );
2041        }
2042    }
2043
2044    #[test]
2045    fn only_test_entries_runtime_unreachable() {
2046        let graph = build_reachability_graph(2, &[(0, 1)], &[], &[0]);
2047        assert!(graph.modules[0].is_test_reachable());
2048        assert!(graph.modules[1].is_test_reachable());
2049        assert!(!graph.modules[0].is_runtime_reachable());
2050        assert!(!graph.modules[1].is_runtime_reachable());
2051        assert!(graph.modules[0].is_reachable());
2052        assert!(graph.modules[1].is_reachable());
2053    }
2054
2055    #[test]
2056    fn diamond_dependency_all_reachable() {
2057        let graph = build_reachability_graph(4, &[(0, 1), (0, 2), (1, 3), (2, 3)], &[0], &[]);
2058        for (i, module) in graph.modules.iter().enumerate() {
2059            assert!(
2060                module.is_reachable(),
2061                "file{i} in diamond should be reachable"
2062            );
2063        }
2064    }
2065
2066    #[test]
2067    fn multiple_entry_points_reach_disjoint_subtrees() {
2068        let graph = build_reachability_graph(4, &[(0, 1), (2, 3)], &[0, 2], &[]);
2069        for (i, module) in graph.modules.iter().enumerate() {
2070            assert!(
2071                module.is_reachable(),
2072                "file{i} should be reachable from one of the entry points"
2073            );
2074        }
2075    }
2076
2077    #[test]
2078    fn empty_graph_no_panics() {
2079        let graph = build_reachability_graph(0, &[], &[], &[]);
2080        assert_eq!(graph.module_count(), 0);
2081    }
2082
2083    fn reaching(graph: &ModuleGraph, file: u32) -> Vec<u32> {
2084        let map = graph.test_entry_points_reaching(&[FileId(file)]);
2085        map[&FileId(file)].iter().map(|root| root.0).collect()
2086    }
2087
2088    #[test]
2089    fn per_entry_reach_applies_the_replacement_mask_of_each_test() {
2090        // 0 is a test that mocks 2 and imports it through 1.
2091        // 3 is a test that imports 2 directly.
2092        let graph = build_reachability_graph_with_replacements(
2093            4,
2094            &[(0, 1, false), (1, 2, false), (3, 2, false)],
2095            &[],
2096            &[0, 3],
2097            &[ResolvedReplacedModuleTarget {
2098                source_file: FileId(0),
2099                target_file: FileId(2),
2100            }],
2101        );
2102
2103        assert_eq!(reaching(&graph, 2), vec![3]);
2104        assert_eq!(reaching(&graph, 1), vec![0]);
2105    }
2106
2107    #[test]
2108    fn per_entry_reach_keeps_a_masked_target_behind_a_commonjs_edge() {
2109        let graph = build_reachability_graph_with_replacements(
2110            3,
2111            &[(0, 1, true), (2, 1, false)],
2112            &[],
2113            &[0, 2],
2114            &[ResolvedReplacedModuleTarget {
2115                source_file: FileId(0),
2116                target_file: FileId(1),
2117            }],
2118        );
2119
2120        assert_eq!(reaching(&graph, 1), vec![0, 2]);
2121    }
2122
2123    #[test]
2124    fn per_entry_reach_without_masks_lists_each_test_that_imports_the_file() {
2125        let graph = build_reachability_graph(5, &[(0, 1), (1, 2), (3, 2), (4, 1)], &[], &[0, 3]);
2126
2127        assert_eq!(reaching(&graph, 2), vec![0, 3]);
2128        assert_eq!(reaching(&graph, 1), vec![0]);
2129        assert!(reaching(&graph, 4).is_empty());
2130    }
2131
2132    #[test]
2133    fn per_entry_reach_spans_more_tests_than_one_profile_word() {
2134        // 70 tests import file 70. Test 0 mocks it, so 69 tests reach it.
2135        let tests: Vec<u32> = (0..70).collect();
2136        let edges: Vec<(u32, u32, bool)> = tests.iter().map(|&test| (test, 70, false)).collect();
2137        let graph = build_reachability_graph_with_replacements(
2138            71,
2139            &edges,
2140            &[],
2141            &tests,
2142            &[ResolvedReplacedModuleTarget {
2143                source_file: FileId(0),
2144                target_file: FileId(70),
2145            }],
2146        );
2147
2148        assert_eq!(reaching(&graph, 70), (1..70).collect::<Vec<u32>>());
2149        assert!(graph.modules[70].is_test_reachable());
2150    }
2151
2152    #[test]
2153    fn per_entry_reach_agrees_with_test_reachability() {
2154        let graph = build_reachability_graph_with_replacements(
2155            6,
2156            &[(0, 1, false), (1, 2, false), (3, 4, false), (4, 2, false)],
2157            &[],
2158            &[0, 3],
2159            &[
2160                ResolvedReplacedModuleTarget {
2161                    source_file: FileId(0),
2162                    target_file: FileId(2),
2163                },
2164                ResolvedReplacedModuleTarget {
2165                    source_file: FileId(3),
2166                    target_file: FileId(4),
2167                },
2168            ],
2169        );
2170
2171        let files: Vec<FileId> = (0..6).map(FileId).collect();
2172        let map = graph.test_entry_points_reaching(&files);
2173        for file in &files {
2174            assert_eq!(
2175                !map[file].is_empty(),
2176                graph.modules[file.0 as usize].is_test_reachable(),
2177                "file{}",
2178                file.0
2179            );
2180        }
2181        assert_eq!(map[&FileId(1)], vec![FileId(0)]);
2182        assert!(map[&FileId(2)].is_empty());
2183    }
2184
2185    /// Classify the first export of `file` with the given test files.
2186    fn reach_of(
2187        graph: &ModuleGraph,
2188        file: u32,
2189        tests: &[u32],
2190    ) -> crate::graph::ExportTestReachResult {
2191        let module = &graph.modules[file as usize];
2192        graph.export_test_reach(module.file_id, &module.exports[0], &|id| {
2193            tests.contains(&id.0)
2194        })
2195    }
2196
2197    #[test]
2198    fn test_reach_without_mocks_reports_no_mocks() {
2199        let graph = build_reachability_graph(2, &[(0, 1)], &[], &[0]);
2200
2201        assert_eq!(graph.test_masking_state(), TestMaskingState::NoMocks);
2202        let reach = reach_of(&graph, 1, &[0]);
2203        assert_eq!(reach.reach, ExportTestReach::Direct);
2204        assert_eq!(reach.tests, vec![FileId(0)]);
2205    }
2206
2207    #[test]
2208    fn test_reach_through_a_non_test_module_is_transitive() {
2209        let graph = build_reachability_graph(3, &[(0, 1), (1, 2)], &[], &[0]);
2210
2211        assert_eq!(reach_of(&graph, 2, &[0]).reach, ExportTestReach::Transitive);
2212    }
2213
2214    #[test]
2215    fn test_reach_without_a_reference_separates_file_reach() {
2216        let files: Vec<_> = (0..3)
2217            .map(|id| DiscoveredFile {
2218                id: FileId(id),
2219                path: PathBuf::from(format!("/project/file{id}.ts")),
2220                size_bytes: 100,
2221            })
2222            .collect();
2223        let export = || {
2224            vec![fallow_types::extract::ExportInfo {
2225                name: ExportName::Named("value".to_string()),
2226                local_name: Some("value".to_string()),
2227                is_type_only: false,
2228                visibility: VisibilityTag::None,
2229                expected_unused_reason: None,
2230                span: oxc_span::Span::new(0, 20),
2231                members: Vec::new(),
2232                is_side_effect_used: false,
2233                super_class: None,
2234                deprecated: false,
2235                deprecated_reason: None,
2236            }]
2237            .into()
2238        };
2239        let modules = vec![
2240            ResolvedModule {
2241                file_id: FileId(0),
2242                path: files[0].path.clone(),
2243                resolved_imports: vec![intermediate_import(
2244                    "./file1",
2245                    FileId(1),
2246                    ImportedName::SideEffect,
2247                    false,
2248                )],
2249                ..ResolvedModule::default()
2250            },
2251            ResolvedModule {
2252                file_id: FileId(1),
2253                path: files[1].path.clone(),
2254                exports: export(),
2255                ..ResolvedModule::default()
2256            },
2257            ResolvedModule {
2258                file_id: FileId(2),
2259                path: files[2].path.clone(),
2260                exports: export(),
2261                ..ResolvedModule::default()
2262            },
2263        ];
2264        let test_entry_points = vec![EntryPoint {
2265            path: files[0].path.clone(),
2266            source: EntryPointSource::TestFile,
2267        }];
2268        let graph = ModuleGraph::build_with_reachability_roots_and_replacements(
2269            &modules,
2270            &[],
2271            &test_entry_points,
2272            &[],
2273            &test_entry_points,
2274            &files,
2275        );
2276
2277        assert_eq!(reach_of(&graph, 1, &[0]).reach, ExportTestReach::None);
2278        assert_eq!(reach_of(&graph, 2, &[0]).reach, ExportTestReach::NoneFile);
2279    }
2280
2281    #[test]
2282    fn test_reach_reports_an_esm_mask_on_a_direct_import() {
2283        let graph = build_reachability_graph_with_replacements(
2284            2,
2285            &[(0, 1, false)],
2286            &[],
2287            &[0],
2288            &[ResolvedReplacedModuleTarget {
2289                source_file: FileId(0),
2290                target_file: FileId(1),
2291            }],
2292        );
2293
2294        assert_eq!(graph.test_masking_state(), TestMaskingState::Active);
2295        // The masked module is not test-reachable, so without the mask check
2296        // the export would read as `NoneFile`.
2297        assert!(!graph.modules[1].is_test_reachable());
2298        let reach = reach_of(&graph, 1, &[0]);
2299        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2300        assert_eq!(reach.tests, vec![FileId(0)]);
2301        assert_eq!(reach.mocked_targets, vec![FileId(1)]);
2302    }
2303
2304    #[test]
2305    fn test_reach_reports_a_mask_behind_a_barrel() {
2306        let graph = build_masked_re_export_graph(false, false);
2307        let reach = reach_of(&graph, 2, &[0]);
2308
2309        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2310        assert_eq!(reach.mocked_targets, vec![FileId(2)]);
2311    }
2312
2313    #[test]
2314    fn test_reach_names_a_mocked_intermediate_barrel() {
2315        let graph = build_intermediate_replacement_graph(false, false, false);
2316        let reach = reach_of(&graph, 2, &[0]);
2317
2318        // An alternate route keeps the target test-reachable, but the only
2319        // reference passes through the mocked barrel.
2320        assert!(graph.modules[2].is_test_reachable());
2321        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2322        assert_eq!(reach.mocked_targets, vec![FileId(1)]);
2323    }
2324
2325    #[test]
2326    fn test_reach_keeps_a_commonjs_require_unmasked() {
2327        let graph = build_reachability_graph_with_replacements(
2328            2,
2329            &[(0, 1, true)],
2330            &[],
2331            &[0],
2332            &[ResolvedReplacedModuleTarget {
2333                source_file: FileId(0),
2334                target_file: FileId(1),
2335            }],
2336        );
2337
2338        assert_eq!(reach_of(&graph, 1, &[0]).reach, ExportTestReach::Direct);
2339    }
2340
2341    #[test]
2342    fn test_reach_through_a_required_barrel_checks_only_esm_hops() {
2343        let barrel_mocked = build_intermediate_replacement_graph(true, false, false);
2344        assert_eq!(
2345            reach_of(&barrel_mocked, 2, &[0]).reach,
2346            ExportTestReach::Direct
2347        );
2348
2349        let target_mocked = build_intermediate_replacement_graph(true, false, true);
2350        let reach = reach_of(&target_mocked, 2, &[0]);
2351        assert_eq!(reach.reach, ExportTestReach::MockedOnly);
2352        assert_eq!(reach.mocked_targets, vec![FileId(2)]);
2353    }
2354
2355    #[test]
2356    fn test_reach_with_an_unmasked_second_root_is_direct() {
2357        let graph = build_reachability_graph_with_replacements(
2358            3,
2359            &[(0, 2, false), (1, 2, false)],
2360            &[],
2361            &[0, 1],
2362            &[ResolvedReplacedModuleTarget {
2363                source_file: FileId(0),
2364                target_file: FileId(2),
2365            }],
2366        );
2367        let reach = reach_of(&graph, 2, &[0, 1]);
2368
2369        assert_eq!(reach.reach, ExportTestReach::Direct);
2370        assert_eq!(reach.tests, vec![FileId(1)]);
2371    }
2372
2373    #[test]
2374    fn test_reach_survives_graph_cache_serialization() {
2375        let graph = build_masked_re_export_graph(false, false);
2376        let encoded = postcard::to_allocvec(&graph).expect("encode graph");
2377        let decoded: ModuleGraph = postcard::from_bytes(&encoded).expect("decode graph");
2378
2379        assert_eq!(decoded.test_masking_state(), TestMaskingState::Active);
2380        assert_eq!(
2381            reach_of(&decoded, 2, &[0]).reach,
2382            ExportTestReach::MockedOnly
2383        );
2384    }
2385}