Skip to main content

fallow_graph/graph/re_exports/
mod.rs

1//! Phase 4: Re-export chain resolution, propagate references through barrel files.
2
3mod propagate;
4#[cfg(test)]
5mod test_support;
6#[cfg(test)]
7mod tests;
8#[cfg(test)]
9mod tests_exposure_walk;
10#[cfg(test)]
11mod tests_name_search;
12#[cfg(test)]
13mod tests_namespace_targets;
14#[cfg(test)]
15mod tests_star_propagate;
16
17use std::collections::VecDeque;
18use std::path::PathBuf;
19
20use fixedbitset::FixedBitSet;
21use rustc_hash::{FxHashMap, FxHashSet};
22
23#[cfg(test)]
24use std::cell::{Cell, RefCell};
25
26use crate::resolve::ResolvedModule;
27use fallow_types::discover::FileId;
28
29use super::types::{ReferencePathInterner, RoutedReferenceKey};
30use super::{Edge, ModuleGraph};
31
32use propagate::{
33    EffectiveDeclarationRouteCache, ImportBindingUsageIndex, NamedPropagationScratch,
34    NamedReExportPropagation, NamedStarRefCache, StarReExportPropagation,
35    propagate_named_re_export, propagate_star_re_export,
36};
37
38#[cfg(test)]
39thread_local! {
40    static PROPAGATION_VISITS: RefCell<Option<Vec<(FileId, FileId)>>> =
41        const { RefCell::new(None) };
42    static DIFFERENTIAL_CHECK_ENABLED: Cell<bool> = const { Cell::new(false) };
43}
44
45#[cfg(test)]
46fn record_propagation_visit(entry: &ReExportTuple) {
47    PROPAGATION_VISITS.with(|visits| {
48        if let Some(visits) = visits.borrow_mut().as_mut() {
49            visits.push((entry.barrel, entry.source));
50        }
51    });
52}
53
54#[cfg(test)]
55fn capture_propagation_visits<T>(run: impl FnOnce() -> T) -> (T, Vec<(FileId, FileId)>) {
56    PROPAGATION_VISITS.with(|visits| *visits.borrow_mut() = Some(Vec::new()));
57    let result = run();
58    let visits = PROPAGATION_VISITS.with(|visits| visits.borrow_mut().take().unwrap_or_default());
59    (result, visits)
60}
61
62#[cfg(test)]
63fn with_re_export_differential_check<T>(run: impl FnOnce() -> T) -> T {
64    DIFFERENTIAL_CHECK_ENABLED.with(|enabled| {
65        let previous = enabled.replace(true);
66        let result = run();
67        enabled.set(previous);
68        result
69    })
70}
71
72/// A re-export cycle or self-loop detected during Phase 4 chain resolution.
73///
74/// The graph-layer mirror of `fallow_types::results::ReExportCycle`. Kept in
75/// the graph crate so the types crate does not need a dependency arrow back
76/// into graph for the conversion. The analysis backend performs the
77/// `GraphReExportCycle` to `ReExportCycle` mapping by reading `is_self_loop`
78/// and routing to the matching `ReExportCycleKind` variant.
79#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
80pub struct GraphReExportCycle {
81    /// Member files participating in the cycle, sorted lexicographically by
82    /// the `Path::display()` form (matches the existing diagnostic-output
83    /// sort). For a self-loop, exactly one entry.
84    pub files: Vec<PathBuf>,
85    /// Parallel array to `files`: the FileId for each member. Kept alongside
86    /// the paths so the core-layer detector can call
87    /// `suppressions.is_file_suppressed(id, IssueKind::ReExportCycle)`
88    /// without an extra path-to-FileId lookup.
89    pub file_ids: Vec<FileId>,
90    /// `true` for single-file self-re-exports (`export * from './'`), `false`
91    /// for multi-node strongly connected components.
92    pub is_self_loop: bool,
93}
94
95/// A single re-export edge collected from the module graph.
96///
97/// Replaces an earlier ad-hoc 5-tuple so the propagation loop is more
98/// readable and the new `is_type_only` field carried into
99/// [`propagate_star_re_export`] does not get lost in tuple-index plumbing.
100struct ReExportTuple {
101    barrel: FileId,
102    source: FileId,
103    imported_name: String,
104    exported_name: String,
105    /// `true` when the triggering re-export edge is `export type * from ...`
106    /// or `export type { foo } from ...`. Threaded into star propagation so
107    /// any synthetic stub created on the source module reflects the chain's
108    /// type-only-ness instead of defaulting to `false`.
109    is_type_only: bool,
110}
111
112struct ReExportContext<'a> {
113    entry_star_targets: &'a FxHashSet<FileId>,
114    edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
115    binding_usage: &'a ImportBindingUsageIndex,
116    effective_exports: &'a super::effective_exports::EffectiveExportIndex,
117    existing_refs: &'a mut FxHashSet<RoutedReferenceKey>,
118    synthetic_stubs: &'a mut FxHashSet<(FileId, String, bool)>,
119    declaration_routes: &'a mut EffectiveDeclarationRouteCache,
120    scratch: &'a mut NamedPropagationScratch,
121    reference_paths: &'a mut ReferencePathInterner,
122    named_star_refs: &'a mut NamedStarRefCache,
123}
124
125/// How much of a closure member the consumers that cannot be enumerated see.
126///
127/// The two differ on `default` alone, because a plain `export *` forwards
128/// every named export of its source and never the source's `default`.
129#[derive(Clone, Copy, PartialEq, Eq, Debug)]
130enum Exposure {
131    /// Reached through a plain `export *`: every export except `default`.
132    StarSurface,
133    /// The whole namespace object is observed: every export, `default`
134    /// included.
135    NamespaceObject,
136}
137
138/// The targets whose module surface Phase 2 saw observed, split by whether
139/// the observation survives the target being unreachable.
140///
141/// Ambient module declarations expose an external module id, so their
142/// observation stands at any reachability. Every other observer is a real
143/// consumer in this graph and is retained only while an entry point reaches
144/// its target.
145#[derive(Default)]
146pub(in crate::graph) struct WholeModuleObservations {
147    /// Targets an ambient module body re-exports from, at any reachability.
148    ambient: FxHashMap<FileId, Exposure>,
149    /// Targets a consumer in this graph observes as a whole object.
150    observed: FxHashSet<FileId>,
151}
152
153impl WholeModuleObservations {
154    /// Record a whole-object observation made by a consumer in this graph.
155    pub(in crate::graph) fn observe(&mut self, target: FileId) {
156        self.observed.insert(target);
157    }
158
159    /// Record the target of an ambient plain `export *`.
160    pub(in crate::graph) fn observe_ambient_star(&mut self, target: FileId) {
161        self.ambient.entry(target).or_insert(Exposure::StarSurface);
162    }
163
164    /// Record the target of an ambient `export * as ns`.
165    pub(in crate::graph) fn observe_ambient_namespace(&mut self, target: FileId) {
166        self.ambient.insert(target, Exposure::NamespaceObject);
167    }
168
169    /// The closure seeds: every ambient target, plus the observed targets an
170    /// entry point reaches.
171    fn seeds<'a>(
172        &'a self,
173        entry_reachable: &'a FixedBitSet,
174    ) -> impl Iterator<Item = (FileId, Exposure)> + 'a {
175        self.ambient
176            .iter()
177            .map(|(&target, &exposure)| (target, exposure))
178            .chain(
179                self.observed
180                    .iter()
181                    .copied()
182                    .filter(|target| entry_reachable.contains(target.0 as usize))
183                    .map(|target| (target, Exposure::NamespaceObject)),
184            )
185    }
186}
187
188/// The exposed namespace closure: every module whose names reach consumers
189/// the graph cannot enumerate, with the part of its export surface they see.
190///
191/// Built by [`ModuleGraph::collect_exposed_namespace_targets`], computed once
192/// per graph build and read by Phase 2c (namespace re-export propagation) and
193/// Phase 4 (the entry-star seed).
194pub(in crate::graph) struct ExposedNamespaceTargets {
195    members: FxHashMap<FileId, Exposure>,
196}
197
198impl ExposedNamespaceTargets {
199    /// Whether the closure has no members at all.
200    pub(in crate::graph) fn is_empty(&self) -> bool {
201        self.members.is_empty()
202    }
203
204    /// Whether the member exposes `exported_name`.
205    ///
206    /// A member reached through a plain `export *` does not expose `default`:
207    /// the star that carried its names onward never forwards it, so an
208    /// `export * as default` declared on such a member hands its target's
209    /// namespace object to nobody.
210    pub(in crate::graph) fn exposes_name(&self, file_id: FileId, exported_name: &str) -> bool {
211        match self.members.get(&file_id) {
212            Some(Exposure::NamespaceObject) => true,
213            Some(Exposure::StarSurface) => exported_name != "default",
214            None => false,
215        }
216    }
217
218    /// Every member, at either exposure.
219    ///
220    /// Phase 4 star propagation credits the named exports of a member's
221    /// `export *` sources and never their `default`, which both exposures
222    /// forward alike, so it reads the membership alone.
223    fn files(&self) -> impl Iterator<Item = FileId> + '_ {
224        self.members.keys().copied()
225    }
226
227    /// Record a member, re-walking it when a wider exposure than a previous
228    /// visit arrives. Each member is walked at most twice.
229    fn record(&mut self, stack: &mut Vec<(FileId, Exposure)>, file_id: FileId, exposure: Exposure) {
230        match self.members.entry(file_id) {
231            std::collections::hash_map::Entry::Occupied(mut slot) => {
232                if *slot.get() == Exposure::StarSurface && exposure == Exposure::NamespaceObject {
233                    slot.insert(exposure);
234                    stack.push((file_id, exposure));
235                }
236            }
237            std::collections::hash_map::Entry::Vacant(slot) => {
238                slot.insert(exposure);
239                stack.push((file_id, exposure));
240            }
241        }
242    }
243}
244
245/// `export * as ns from './x'`: the barrel exposes x's namespace object under
246/// a single name instead of forwarding x's names.
247fn is_namespace_re_export(re: &super::types::ReExportEdge) -> bool {
248    re.imported_name == "*" && re.exported_name != "*"
249}
250
251/// Reverse index of the re-export edges that carry one exported name outward,
252/// from the module that declares it toward the barrels that forward it.
253///
254/// A namespace re-export (`export * as ns`) is not a forwarder: it bundles the
255/// source's names into one object instead of passing them along.
256struct NameForwarders<'a> {
257    /// `(source, imported name)` to the barrels re-exporting it, each with the
258    /// name it exports it under, so renames are followed exactly.
259    named: FxHashMap<(FileId, &'a str), Vec<(FileId, &'a str)>>,
260    /// Source file to the barrels that re-export all of its names.
261    stars: FxHashMap<FileId, Vec<FileId>>,
262}
263
264/// Reusable state for [`ExposedNameSearch::reaches_exposure`].
265///
266/// `failed` outlives a single search within one round: an exhausted search
267/// proves that every state it visited fails too, so a forwarding chain shared
268/// by many namespace edges is walked once instead of once per edge. A round
269/// that widens the closure clears it, because a state that failed against the
270/// smaller closure can succeed against the wider one.
271#[derive(Default)]
272struct NameSearchScratch<'a> {
273    visited: FxHashSet<(FileId, &'a str)>,
274    frontier: Vec<(FileId, &'a str)>,
275    failed: FxHashSet<(FileId, &'a str)>,
276}
277
278impl<'a> NameForwarders<'a> {
279    fn build(modules: &'a [super::types::ModuleNode]) -> Self {
280        let mut named: FxHashMap<(FileId, &'a str), Vec<(FileId, &'a str)>> = FxHashMap::default();
281        let mut stars: FxHashMap<FileId, Vec<FileId>> = FxHashMap::default();
282        for module in modules {
283            for re in &module.re_exports {
284                if re.imported_name == "*" {
285                    if re.exported_name == "*" {
286                        stars
287                            .entry(re.source_file)
288                            .or_default()
289                            .push(module.file_id);
290                    }
291                } else {
292                    named
293                        .entry((re.source_file, re.imported_name.as_str()))
294                        .or_default()
295                        .push((module.file_id, re.exported_name.as_str()));
296                }
297            }
298        }
299        Self { named, stars }
300    }
301}
302
303/// Extend `may_reach` with every module `seeds` re-exports from, transitively,
304/// following named and plain-star edges and ignoring names.
305///
306/// `export * as ns` is left out: it bundles its source's names into one object
307/// instead of forwarding them, so it never carries a name outward.
308///
309/// A seed already in `may_reach` is skipped with its whole subtree, which is
310/// what lets the closure fixpoint widen the prune round by round instead of
311/// rebuilding it from scratch.
312fn extend_forwarding_sources(
313    modules: &[super::types::ModuleNode],
314    may_reach: &mut FxHashSet<FileId>,
315    seeds: impl IntoIterator<Item = FileId>,
316) {
317    let mut stack: Vec<FileId> = seeds
318        .into_iter()
319        .filter(|seed| may_reach.insert(*seed))
320        .collect();
321    while let Some(barrel) = stack.pop() {
322        let Some(module) = modules.get(barrel.0 as usize) else {
323            continue;
324        };
325        for re in &module.re_exports {
326            if !is_namespace_re_export(re) && may_reach.insert(re.source_file) {
327                stack.push(re.source_file);
328            }
329        }
330    }
331}
332
333/// The outward search that decides whether one `export * as ns` edge hands its
334/// target's namespace object to consumers the graph cannot enumerate.
335///
336/// A name reaches such a consumer when it arrives, through named and plain-star
337/// re-exports, at an entry point's own export surface, at a module already in
338/// the exposed namespace closure, or at a name some importer uses as a whole
339/// object. The three are the same three decisions Phase 2c makes for the
340/// namespace edges it credits, so seeding from them keeps the closure and
341/// Phase 2c from disagreeing about which objects are observed.
342struct ExposedNameSearch<'a> {
343    forwarders: NameForwarders<'a>,
344    /// Per target file, the imported names whose local binding some importer
345    /// uses as a whole object (`Object.values(ns)`, a spread, a
346    /// destructure-with-rest). Named imports only: a namespace import is
347    /// already a `whole_module_targets` seed.
348    whole_object_names: FxHashMap<FileId, Vec<String>>,
349    /// Every module some acceptance point re-exports from, transitively, names
350    /// ignored.
351    ///
352    /// A name can only travel from a module to an acceptance point along
353    /// forwarding edges, so a module outside this set answers the search in
354    /// constant time however deep its own chains run. Recomputed per round,
355    /// because a round that widens the closure adds acceptance points.
356    may_reach: FxHashSet<FileId>,
357    scratch: NameSearchScratch<'a>,
358}
359
360impl<'a> ExposedNameSearch<'a> {
361    fn build(
362        modules: &'a [super::types::ModuleNode],
363        module_by_id: &FxHashMap<FileId, &ResolvedModule>,
364    ) -> Self {
365        let mut whole_object_names: FxHashMap<FileId, Vec<String>> = FxHashMap::default();
366        for consumer in module_by_id.values() {
367            if consumer.whole_object_uses.is_empty() {
368                continue;
369            }
370            for import in &consumer.resolved_imports {
371                let Some(target) = import.target.internal_file_id() else {
372                    continue;
373                };
374                let imported_name = match &import.info.imported_name {
375                    fallow_types::extract::ImportedName::Named(name) => name.as_str(),
376                    fallow_types::extract::ImportedName::Default => "default",
377                    _ => continue,
378                };
379                let local_name = import.info.local_name.as_str();
380                if local_name.is_empty()
381                    || !consumer
382                        .whole_object_uses
383                        .iter()
384                        .any(|used| used == local_name)
385                {
386                    continue;
387                }
388                let names = whole_object_names.entry(target).or_default();
389                if !names.iter().any(|name| name == imported_name) {
390                    names.push(imported_name.to_string());
391                }
392            }
393        }
394
395        let mut may_reach = FxHashSet::default();
396        extend_forwarding_sources(
397            modules,
398            &mut may_reach,
399            modules
400                .iter()
401                .filter(|m| m.is_entry_point())
402                .map(|m| m.file_id)
403                .chain(whole_object_names.keys().copied()),
404        );
405
406        Self {
407            forwarders: NameForwarders::build(modules),
408            whole_object_names,
409            may_reach,
410            scratch: NameSearchScratch::default(),
411        }
412    }
413
414    /// Widen the reachability prune with the members the last round added and
415    /// drop the memoised failures for a round against the wider closure.
416    ///
417    /// The prune only ever grows, so the members already walked keep their
418    /// subtree and each re-export edge is visited at most once across every
419    /// round instead of once per round.
420    fn refresh(
421        &mut self,
422        modules: &'a [super::types::ModuleNode],
423        closure: &ExposedNamespaceTargets,
424    ) {
425        extend_forwarding_sources(
426            modules,
427            &mut self.may_reach,
428            closure.members.keys().copied(),
429        );
430        self.scratch.failed.clear();
431    }
432
433    /// Whether `name`, as exported by `file`, reaches an acceptance point
434    /// through named and plain-star re-exports.
435    ///
436    /// Each hop must really forward the binding: a barrel that declares its
437    /// own `name`, or that receives it from two stars at once, exports a
438    /// different binding under that name and the chain stops there. Being on
439    /// an entry point's plain-`export *` closure is not on its own proof that
440    /// the name survives to the entry, so no hop is skipped for it. A plain
441    /// `export *` also never carries `default`, so a `default`-named state
442    /// takes named hops only.
443    fn reaches_exposure(
444        &mut self,
445        graph: &ModuleGraph,
446        closure: &ExposedNamespaceTargets,
447        file: FileId,
448        name: &'a str,
449    ) -> bool {
450        if !self.may_reach.contains(&file) || self.scratch.failed.contains(&(file, name)) {
451            return false;
452        }
453        let Self {
454            forwarders,
455            whole_object_names,
456            may_reach,
457            scratch,
458        } = self;
459        scratch.visited.clear();
460        scratch.frontier.clear();
461        scratch.visited.insert((file, name));
462        scratch.frontier.push((file, name));
463        while let Some((current, current_name)) = scratch.frontier.pop() {
464            if exposes_here(graph, closure, whole_object_names, current, current_name) {
465                return true;
466            }
467            if let Some(barrels) = forwarders.named.get(&(current, current_name)) {
468                for &(barrel, exported_name) in barrels {
469                    if may_reach.contains(&barrel)
470                        && graph.forwards_binding(current, current_name, barrel, exported_name)
471                        && !scratch.failed.contains(&(barrel, exported_name))
472                        && scratch.visited.insert((barrel, exported_name))
473                    {
474                        scratch.frontier.push((barrel, exported_name));
475                    }
476                }
477            }
478            if current_name == "default" {
479                continue;
480            }
481            if let Some(barrels) = forwarders.stars.get(&current) {
482                for &barrel in barrels {
483                    if may_reach.contains(&barrel)
484                        && graph.forwards_binding(current, current_name, barrel, current_name)
485                        && !scratch.failed.contains(&(barrel, current_name))
486                        && scratch.visited.insert((barrel, current_name))
487                    {
488                        scratch.frontier.push((barrel, current_name));
489                    }
490                }
491            }
492        }
493        scratch.failed.extend(scratch.visited.iter().copied());
494        false
495    }
496}
497
498/// Whether the module that exports `name` already hands it to a consumer the
499/// graph cannot enumerate, with no further re-export hop needed.
500///
501/// An entry point exposes every name it exports, `default` included: it is the
502/// public API. A closure member exposes what its own exposure allows. A name
503/// some importer uses as a whole object is observed in full by that importer.
504fn exposes_here(
505    graph: &ModuleGraph,
506    closure: &ExposedNamespaceTargets,
507    whole_object_names: &FxHashMap<FileId, Vec<String>>,
508    file: FileId,
509    name: &str,
510) -> bool {
511    graph.is_entry_point_file(file)
512        || closure.exposes_name(file, name)
513        || whole_object_names
514            .get(&file)
515            .is_some_and(|names| names.iter().any(|candidate| candidate == name))
516}
517
518struct ReExportFixpointInput<'a> {
519    re_export_info: &'a [ReExportTuple],
520    entry_star_targets: &'a FxHashSet<FileId>,
521    edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
522    module_by_id: &'a FxHashMap<FileId, &'a ResolvedModule>,
523    reference_paths: &'a mut ReferencePathInterner,
524}
525
526#[cfg(test)]
527struct LegacyReExportFullScan<'a> {
528    modules: &'a mut [super::types::ModuleNode],
529    edges: &'a [Edge],
530    re_export_info: &'a [ReExportTuple],
531    entry_star_targets: &'a FxHashSet<FileId>,
532    edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
533    module_by_id: &'a FxHashMap<FileId, &'a ResolvedModule>,
534    effective_exports: &'a super::effective_exports::EffectiveExportIndex,
535    reference_paths: &'a mut ReferencePathInterner,
536}
537
538/// Deterministic scheduler for monotone re-export propagation.
539///
540/// Each tuple reads export state from `barrel` and may add references or
541/// synthetic exports to `source`. When `source` changes, only tuples whose
542/// `barrel` is that module can observe the new state, so those tuple indices
543/// are re-enqueued in their original stable order.
544struct ReExportPropagationPlan {
545    observers_by_module: FxHashMap<FileId, Vec<usize>>,
546    queue: VecDeque<usize>,
547    enqueued: Vec<bool>,
548}
549
550impl ReExportPropagationPlan {
551    fn new(re_export_info: &[ReExportTuple]) -> Self {
552        let mut observers_by_module: FxHashMap<FileId, Vec<usize>> = FxHashMap::default();
553        for (idx, entry) in re_export_info.iter().enumerate() {
554            observers_by_module
555                .entry(entry.barrel)
556                .or_default()
557                .push(idx);
558        }
559
560        Self {
561            observers_by_module,
562            queue: (0..re_export_info.len()).collect(),
563            enqueued: vec![true; re_export_info.len()],
564        }
565    }
566
567    fn pop_front(&mut self) -> Option<usize> {
568        let idx = self.queue.pop_front()?;
569        self.enqueued[idx] = false;
570        Some(idx)
571    }
572
573    fn enqueue_observers(&mut self, changed_module: FileId) {
574        let Some(observers) = self.observers_by_module.get(&changed_module) else {
575            return;
576        };
577        for &idx in observers {
578            if !self.enqueued[idx] {
579                self.enqueued[idx] = true;
580                self.queue.push_back(idx);
581            }
582        }
583    }
584}
585
586impl ModuleGraph {
587    /// Resolve re-export chains: when module A re-exports from B,
588    /// any reference to A's re-exported symbol should also count as a reference
589    /// to B's original export (and transitively through the chain).
590    ///
591    /// Returns the list of re-export cycles and self-loops detected during
592    /// the upfront Tarjan SCC pass. The caller stores this on the
593    /// `ModuleGraph` so the `re-export-cycle` finding type can surface them
594    /// to users instead of relying on `RUST_LOG=warn` (see issue #515).
595    pub(super) fn resolve_re_export_chains(
596        &mut self,
597        module_by_id: &FxHashMap<FileId, &ResolvedModule>,
598        exposed_namespace_targets: &ExposedNamespaceTargets,
599        reference_paths: &mut ReferencePathInterner,
600    ) -> Vec<GraphReExportCycle> {
601        let re_export_info = self.collect_re_export_tuples();
602
603        if re_export_info.is_empty() {
604            return Vec::new();
605        }
606
607        let cycles = find_re_export_cycles(&self.modules, &re_export_info);
608
609        let entry_star_targets = self.collect_entry_star_targets(exposed_namespace_targets);
610        let edges_by_target = self.build_edges_by_target();
611
612        self.run_re_export_fixpoint(ReExportFixpointInput {
613            re_export_info: &re_export_info,
614            entry_star_targets: &entry_star_targets,
615            edges_by_target: &edges_by_target,
616            module_by_id,
617            reference_paths,
618        });
619
620        cycles
621    }
622
623    /// Flatten every module's re-export edges into a single tuple list.
624    ///
625    /// A module that only asset references load (a `raw-loader!` resource)
626    /// never runs, so its re-exports forward nothing. The edge that loads it
627    /// already credits its own exports, and its sources stay out of reach,
628    /// the same as its imports.
629    fn collect_re_export_tuples(&self) -> Vec<ReExportTuple> {
630        let asset_only = self.asset_only_modules();
631        self.modules
632            .iter()
633            .filter(|m| !asset_only.contains(m.file_id.0 as usize))
634            .flat_map(|m| {
635                m.re_exports.iter().map(move |re| ReExportTuple {
636                    barrel: m.file_id,
637                    source: re.source_file,
638                    imported_name: re.imported_name.clone(),
639                    exported_name: re.exported_name.clone(),
640                    is_type_only: re.is_type_only,
641                })
642            })
643            .collect()
644    }
645
646    /// The modules that are not entry points and that only edges which do not
647    /// run their target load.
648    fn asset_only_modules(&self) -> FixedBitSet {
649        let total = self.modules.len();
650        let mut asset_loaded = FixedBitSet::with_capacity(total);
651        let mut run_loaded = FixedBitSet::with_capacity(total);
652        for edge in &self.edges {
653            let target = edge.target.0 as usize;
654            if target >= total {
655                continue;
656            }
657            if edge.runs_target_code() {
658                run_loaded.insert(target);
659            } else {
660                asset_loaded.insert(target);
661            }
662        }
663        asset_loaded.difference_with(&run_loaded);
664        for module in &self.modules {
665            if module.is_entry_point() {
666                asset_loaded.set(module.file_id.0 as usize, false);
667            }
668        }
669        asset_loaded
670    }
671
672    /// Compute the transitive closure of `export *` source files whose every
673    /// named export is credited: star sources of entry-point barrels, closed
674    /// over plain `export *` chains, plus every member of the exposed
675    /// namespace closure (`collect_exposed_namespace_targets`, computed once
676    /// per build and threaded in).
677    fn collect_entry_star_targets(
678        &self,
679        exposed_namespace_targets: &ExposedNamespaceTargets,
680    ) -> FxHashSet<FileId> {
681        let mut entry_star_targets: FxHashSet<FileId> = exposed_namespace_targets.files().collect();
682        entry_star_targets.extend(self.modules.iter().filter(|m| m.is_entry_point()).flat_map(
683            |m| {
684                m.re_exports
685                    .iter()
686                    .filter(|re| re.exported_name == "*")
687                    .map(|re| re.source_file)
688            },
689        ));
690        self.extend_plain_star_closure(&mut entry_star_targets);
691        entry_star_targets
692    }
693
694    /// Every module whose full namespace object is handed to consumers the
695    /// graph cannot enumerate per name (issues #2357, #2372, #2373).
696    ///
697    /// The seeds are the targets whose whole namespace object Phase 2
698    /// observed (`whole_module_targets`: an ambient-module star, a
699    /// dynamic-import pattern match, a bindingless side-effect `require()`, or
700    /// a namespace import the graph could not narrow because it is used as a
701    /// whole object, handed on without member access, or re-exported from a
702    /// non-entry module) plus every `export * as ns` source whose name reaches
703    /// an entry point's own export surface, an existing closure member, or an
704    /// importer that uses the binding as a whole object. Every such consumer
705    /// sees every name on the namespace object, including the names that only
706    /// arrive through the target's own `export *` and `export * as ns` chains,
707    /// and per-name propagation cannot credit those because no name is ever
708    /// imported. The closure therefore follows both chain forms: star
709    /// propagation treats each member like an entry barrel for its `export *`
710    /// sources (named exports, never `default`), and namespace re-export
711    /// propagation credits every export of each member's `export * as ns`
712    /// sources (`default` included, because the namespace object exposes it).
713    ///
714    /// A member reached through a plain `export *` carries the weaker
715    /// [`Exposure::StarSurface`]: the star forwarded its named exports and not
716    /// its `default`, so an `export * as default` declared on it exposes
717    /// nothing and stops the walk.
718    ///
719    /// The namespace-edge seeds and the closure walk run to a fixpoint against
720    /// each other: a target that joins the closure can itself expose a name a
721    /// further `export * as ns` edge forwards to it, and that edge only
722    /// qualifies once the target is a member. The rounds are the same
723    /// exposure decision Phase 2c makes per namespace edge, so the closure
724    /// Phase 2c reads already contains every target Phase 2c would credit in
725    /// full, instead of stopping one namespace level short of it.
726    ///
727    /// `entry_reachable` is the entry-point reachability bitset. It gates the
728    /// two seed kinds issues #2372 and #2373 add (an observed whole-object
729    /// target and an `export * as ns` source), and nothing else: withholding
730    /// those can only withhold credit the pre-existing closure never gave.
731    /// The ambient seeds and the walk stay ungated, because a chain that
732    /// starts at an unreachable shim routinely re-enters a module an entry
733    /// point imports directly, and gating it would report exports on files
734    /// the report calls reachable.
735    ///
736    /// Computed once per graph build and threaded into both phases that read
737    /// it; it depends only on `re_exports`, the entry-point flags, the
738    /// consumers' whole-object uses, and reachability, none of which any later
739    /// phase mutates.
740    pub(in crate::graph) fn collect_exposed_namespace_targets(
741        &self,
742        whole_module_targets: &WholeModuleObservations,
743        entry_reachable: &FixedBitSet,
744        module_by_id: &FxHashMap<FileId, &ResolvedModule>,
745    ) -> ExposedNamespaceTargets {
746        let mut closure = ExposedNamespaceTargets {
747            members: FxHashMap::default(),
748        };
749        let mut stack: Vec<(FileId, Exposure)> = Vec::new();
750        for (seed, exposure) in whole_module_targets.seeds(entry_reachable) {
751            closure.record(&mut stack, seed, exposure);
752        }
753
754        let mut pending: Vec<(FileId, &str, FileId)> = self
755            .modules
756            .iter()
757            .flat_map(|m| {
758                m.re_exports
759                    .iter()
760                    .filter(|re| is_namespace_re_export(re))
761                    .map(move |re| (m.file_id, re.exported_name.as_str(), re.source_file))
762            })
763            .filter(|(_, _, source)| entry_reachable.contains(source.0 as usize))
764            .collect();
765        let mut search =
766            (!pending.is_empty()).then(|| ExposedNameSearch::build(&self.modules, module_by_id));
767
768        loop {
769            self.extend_exposure_walk(&mut closure, &mut stack);
770            let Some(search) = search.as_mut() else { break };
771            if pending.is_empty() {
772                break;
773            }
774            search.refresh(&self.modules, &closure);
775            let mut widened = false;
776            let mut still_pending = Vec::with_capacity(pending.len());
777            for (barrel, exported_name, source) in std::mem::take(&mut pending) {
778                if closure.members.get(&source) == Some(&Exposure::NamespaceObject) {
779                    continue;
780                }
781                if search.reaches_exposure(self, &closure, barrel, exported_name) {
782                    closure.record(&mut stack, source, Exposure::NamespaceObject);
783                    widened = true;
784                } else {
785                    still_pending.push((barrel, exported_name, source));
786                }
787            }
788            pending = still_pending;
789            if !widened {
790                break;
791            }
792        }
793        closure
794    }
795
796    /// Drain the closure's work stack, carrying each member's exposure along
797    /// its own `export *` and `export * as ns` edges.
798    ///
799    /// No hop is dropped for reachability. A re-export edge makes its source
800    /// reachable whenever the barrel is, so only the ambient seeds can ever
801    /// walk from an unreachable member, and their chains routinely re-enter
802    /// modules an entry point imports directly.
803    fn extend_exposure_walk(
804        &self,
805        closure: &mut ExposedNamespaceTargets,
806        stack: &mut Vec<(FileId, Exposure)>,
807    ) {
808        while let Some((file_id, exposure)) = stack.pop() {
809            let Some(module) = self.modules.get(file_id.0 as usize) else {
810                continue;
811            };
812            for re in &module.re_exports {
813                if re.imported_name != "*" {
814                    continue;
815                }
816                let next = if re.exported_name == "*" {
817                    Exposure::StarSurface
818                } else if exposure == Exposure::NamespaceObject || re.exported_name != "default" {
819                    Exposure::NamespaceObject
820                } else {
821                    continue;
822                };
823                closure.record(stack, re.source_file, next);
824            }
825        }
826    }
827
828    /// Whether `barrel` re-exports under `barrel_name` the very binding
829    /// `source` exports under `source_name`.
830    ///
831    /// Only the namespace choice lives here: the value namespace decides
832    /// whenever the source exports the name there (a namespace object is a
833    /// value binding), and a type-only surface falls back to the type
834    /// namespace. The per-namespace comparison itself is Phase 2c's own
835    /// `uniquely_forwards_binding`, so the closure's outward search and the
836    /// phase it pre-computes for cannot drift apart on what a hop forwards.
837    fn forwards_binding(
838        &self,
839        source: FileId,
840        source_name: &str,
841        barrel: FileId,
842        barrel_name: &str,
843    ) -> bool {
844        for namespace in [super::ExportNamespace::Value, super::ExportNamespace::Type] {
845            if !matches!(
846                self.resolve_export(source, source_name, namespace),
847                super::EffectiveExportResolution::Unique(_)
848            ) {
849                continue;
850            }
851            return super::namespace_indexes::uniquely_forwards_binding(
852                self,
853                source,
854                source_name,
855                barrel,
856                barrel_name,
857                namespace,
858            );
859        }
860        false
861    }
862
863    /// Whether the file is an entry point of this graph.
864    fn is_entry_point_file(&self, file_id: FileId) -> bool {
865        self.modules
866            .get(file_id.0 as usize)
867            .is_some_and(super::types::ModuleNode::is_entry_point)
868    }
869
870    /// Extend `targets` with every module its members reach through plain
871    /// `export *` chains, transitively.
872    fn extend_plain_star_closure(&self, targets: &mut FxHashSet<FileId>) {
873        let mut stack: Vec<FileId> = targets.iter().copied().collect();
874        while let Some(file_id) = stack.pop() {
875            let Some(module) = self.modules.get(file_id.0 as usize) else {
876                continue;
877            };
878            for re in module
879                .re_exports
880                .iter()
881                .filter(|re| re.imported_name == "*" && re.exported_name == "*")
882            {
883                if targets.insert(re.source_file) {
884                    stack.push(re.source_file);
885                }
886            }
887        }
888    }
889
890    /// Index every edge by its target file for fast star-propagation lookups.
891    fn build_edges_by_target(&self) -> FxHashMap<FileId, Vec<usize>> {
892        let mut edges_by_target: FxHashMap<FileId, Vec<usize>> = FxHashMap::default();
893        for (idx, edge) in self.edges.iter().enumerate() {
894            edges_by_target.entry(edge.target).or_default().push(idx);
895        }
896        edges_by_target
897    }
898
899    /// Run monotone propagation, revisiting only tuples affected by new state.
900    fn run_re_export_fixpoint(&mut self, input: ReExportFixpointInput<'_>) {
901        let ReExportFixpointInput {
902            re_export_info,
903            entry_star_targets,
904            edges_by_target,
905            module_by_id,
906            reference_paths,
907        } = input;
908        #[cfg(test)]
909        let mut legacy_modules: Option<Vec<super::types::ModuleNode>> = DIFFERENTIAL_CHECK_ENABLED
910            .with(|enabled| {
911                enabled.get().then(|| {
912                    serde_json::from_value(
913                        serde_json::to_value(&self.modules)
914                            .expect("module graph should serialize for differential testing"),
915                    )
916                    .expect("module graph should deserialize for differential testing")
917                })
918            });
919
920        let safety_cap = self.re_export_transition_safety_cap(re_export_info);
921        let mut processed = 0usize;
922        let mut plan = ReExportPropagationPlan::new(re_export_info);
923        let mut existing_refs: FxHashSet<RoutedReferenceKey> = FxHashSet::default();
924        let mut synthetic_stubs: FxHashSet<(FileId, String, bool)> = FxHashSet::default();
925        let binding_usage = ImportBindingUsageIndex::build(module_by_id);
926        let mut declaration_routes = EffectiveDeclarationRouteCache::default();
927        let mut scratch = NamedPropagationScratch::default();
928        let mut named_star_refs = NamedStarRefCache::default();
929
930        while let Some(entry_idx) = plan.pop_front() {
931            if processed >= safety_cap {
932                tracing::error!(
933                    processed,
934                    safety_cap,
935                    re_export_edges = re_export_info.len(),
936                    "Re-export propagation exceeded its finite-state safety cap; \
937                     propagation may be non-monotonic. Please file a bug at \
938                     https://github.com/fallow-rs/fallow/issues with the repro."
939                );
940                break;
941            }
942            processed += 1;
943
944            let mut context = ReExportContext {
945                entry_star_targets,
946                edges_by_target,
947                binding_usage: &binding_usage,
948                effective_exports: &self.effective_exports,
949                existing_refs: &mut existing_refs,
950                synthetic_stubs: &mut synthetic_stubs,
951                declaration_routes: &mut declaration_routes,
952                scratch: &mut scratch,
953                reference_paths,
954                named_star_refs: &mut named_star_refs,
955            };
956
957            let entry = &re_export_info[entry_idx];
958            #[cfg(test)]
959            record_propagation_visit(entry);
960            if Self::propagate_re_export_entry(&mut self.modules, &self.edges, entry, &mut context)
961            {
962                plan.enqueue_observers(entry.source);
963            }
964        }
965
966        #[cfg(test)]
967        if let Some(legacy_modules) = legacy_modules.as_mut() {
968            // The oracle checks every name against every star source, so it
969            // also proves that the source-name filter drops nothing.
970            propagate::without_star_source_filter(|| {
971                Self::run_re_export_full_scan(LegacyReExportFullScan {
972                    modules: legacy_modules,
973                    edges: &self.edges,
974                    re_export_info,
975                    entry_star_targets,
976                    edges_by_target,
977                    module_by_id,
978                    effective_exports: &self.effective_exports,
979                    reference_paths,
980                });
981            });
982            assert_eq!(
983                serde_json::to_value(legacy_modules)
984                    .expect("legacy module graph should serialize for comparison"),
985                serde_json::to_value(&self.modules)
986                    .expect("queue module graph should serialize for comparison"),
987                "work-queue propagation must match the legacy full-scan fixpoint"
988            );
989        }
990    }
991
992    /// Bound scheduler work by the finite set of exports, synthetic names, and
993    /// interned reference paths that monotone propagation can add.
994    fn re_export_transition_safety_cap(&self, re_export_info: &[ReExportTuple]) -> usize {
995        let initial_exports = self
996            .modules
997            .iter()
998            .map(|module| module.exports.len())
999            .sum::<usize>();
1000        let named_inputs = self
1001            .edges
1002            .iter()
1003            .flat_map(|edge| &edge.symbols)
1004            .filter(|symbol| {
1005                matches!(
1006                    &symbol.imported_name,
1007                    fallow_types::extract::ImportedName::Named(_)
1008                )
1009            })
1010            .count()
1011            .saturating_add(initial_exports)
1012            .saturating_add(re_export_info.len());
1013
1014        let module_count = self.modules.len();
1015        let synthetic_export_hosts = self
1016            .modules
1017            .iter()
1018            .filter(|module| {
1019                module
1020                    .re_exports
1021                    .iter()
1022                    .any(|re_export| re_export.exported_name == "*")
1023            })
1024            .count();
1025        let synthetic_exports = synthetic_export_hosts
1026            .saturating_mul(named_inputs)
1027            .saturating_mul(2);
1028        let max_exports = initial_exports.saturating_add(synthetic_exports);
1029        let reference_additions = max_exports.saturating_mul(module_count).saturating_mul(2);
1030        let state_changes = synthetic_exports.saturating_add(reference_additions);
1031
1032        re_export_info
1033            .len()
1034            .saturating_add(state_changes.saturating_mul(re_export_info.len()))
1035            .max(re_export_info.len())
1036    }
1037
1038    /// Propagate references for one re-export edge, dispatching star vs named.
1039    fn propagate_re_export_entry(
1040        modules: &mut [super::types::ModuleNode],
1041        edges: &[Edge],
1042        entry: &ReExportTuple,
1043        context: &mut ReExportContext<'_>,
1044    ) -> bool {
1045        let barrel_idx = entry.barrel.0 as usize;
1046        let source_idx = entry.source.0 as usize;
1047
1048        if barrel_idx >= modules.len() || source_idx >= modules.len() {
1049            return false;
1050        }
1051
1052        if entry.exported_name == "*" {
1053            propagate_star_re_export(StarReExportPropagation {
1054                modules,
1055                edges,
1056                edges_by_target: context.edges_by_target,
1057                binding_usage: context.binding_usage,
1058                effective_exports: context.effective_exports,
1059                barrel_id: entry.barrel,
1060                barrel_idx,
1061                source_id: entry.source,
1062                source_idx,
1063                entry_star_targets: context.entry_star_targets,
1064                triggering_is_type_only: entry.is_type_only,
1065                synthetic_stubs: context.synthetic_stubs,
1066                reference_paths: context.reference_paths,
1067                named_star_refs: context.named_star_refs,
1068            })
1069        } else {
1070            propagate_named_re_export(NamedReExportPropagation {
1071                modules,
1072                effective_exports: context.effective_exports,
1073                barrel_id: entry.barrel,
1074                barrel_idx,
1075                source_id: entry.source,
1076                source_idx,
1077                imported_name: &entry.imported_name,
1078                exported_name: &entry.exported_name,
1079                is_type_only: entry.is_type_only,
1080                existing_refs: context.existing_refs,
1081                declaration_routes: context.declaration_routes,
1082                scratch: context.scratch,
1083                reference_paths: context.reference_paths,
1084            })
1085        }
1086    }
1087
1088    #[cfg(test)]
1089    fn run_re_export_full_scan(input: LegacyReExportFullScan<'_>) {
1090        let LegacyReExportFullScan {
1091            modules,
1092            edges,
1093            re_export_info,
1094            entry_star_targets,
1095            edges_by_target,
1096            module_by_id,
1097            effective_exports,
1098            reference_paths,
1099        } = input;
1100        let max_iterations = re_export_info.len().saturating_add(1);
1101        let mut existing_refs: FxHashSet<RoutedReferenceKey> = FxHashSet::default();
1102        let mut synthetic_stubs: FxHashSet<(FileId, String, bool)> = FxHashSet::default();
1103        let binding_usage = ImportBindingUsageIndex::build(module_by_id);
1104        let mut declaration_routes = EffectiveDeclarationRouteCache::default();
1105        let mut scratch = NamedPropagationScratch::default();
1106
1107        for _ in 0..max_iterations {
1108            let mut changed = false;
1109            for entry in re_export_info {
1110                let mut context = ReExportContext {
1111                    entry_star_targets,
1112                    edges_by_target,
1113                    binding_usage: &binding_usage,
1114                    effective_exports,
1115                    existing_refs: &mut existing_refs,
1116                    synthetic_stubs: &mut synthetic_stubs,
1117                    declaration_routes: &mut declaration_routes,
1118                    scratch: &mut scratch,
1119                    reference_paths,
1120                    // A fresh cache per entry keeps the reference scan
1121                    // independent of the per-barrel cache it checks.
1122                    named_star_refs: &mut NamedStarRefCache::default(),
1123                };
1124                changed |= Self::propagate_re_export_entry(modules, edges, entry, &mut context);
1125            }
1126            if !changed {
1127                break;
1128            }
1129        }
1130    }
1131}
1132
1133/// Find SCCs of size >= 2 in the re-export subgraph and self-re-export
1134/// edges, emit one `tracing::warn!` per cycle, AND return structured cycle
1135/// data for the user-visible `re-export-cycle` finding type.
1136///
1137/// The `tracing::warn!` emissions remain unchanged from #442 (RUST_LOG=warn
1138/// operators still see them). The returned `Vec<GraphReExportCycle>` is the
1139/// structured surface that the analysis backend consumes and wraps in typed
1140/// `ReExportCycleFinding`s for end-user output. See issue #515.
1141fn find_re_export_cycles(
1142    modules: &[super::types::ModuleNode],
1143    re_export_info: &[ReExportTuple],
1144) -> Vec<GraphReExportCycle> {
1145    let mut cycles: Vec<GraphReExportCycle> = Vec::new();
1146
1147    let (node_index, nodes) = build_re_export_node_index(re_export_info);
1148    let n = nodes.len();
1149    if n == 0 {
1150        return cycles;
1151    }
1152
1153    let adj = build_re_export_adjacency(re_export_info, &node_index, modules, &mut cycles);
1154
1155    let sccs = tarjan_scc(n, &adj);
1156
1157    for scc in &sccs {
1158        cycles.push(build_multi_node_cycle(scc, &nodes, modules));
1159    }
1160
1161    cycles
1162}
1163
1164/// Assign a dense node index to every distinct barrel / source file id.
1165fn build_re_export_node_index(
1166    re_export_info: &[ReExportTuple],
1167) -> (FxHashMap<FileId, usize>, Vec<FileId>) {
1168    let mut node_index: FxHashMap<FileId, usize> = FxHashMap::default();
1169    let mut nodes: Vec<FileId> = Vec::new();
1170    for entry in re_export_info {
1171        for &id in &[entry.barrel, entry.source] {
1172            node_index.entry(id).or_insert_with(|| {
1173                let idx = nodes.len();
1174                nodes.push(id);
1175                idx
1176            });
1177        }
1178    }
1179    (node_index, nodes)
1180}
1181
1182/// Build the adjacency list for the re-export subgraph, emitting a self-loop
1183/// `GraphReExportCycle` for any barrel that re-exports from itself.
1184fn build_re_export_adjacency(
1185    re_export_info: &[ReExportTuple],
1186    node_index: &FxHashMap<FileId, usize>,
1187    modules: &[super::types::ModuleNode],
1188    cycles: &mut Vec<GraphReExportCycle>,
1189) -> Vec<Vec<usize>> {
1190    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); node_index.len()];
1191    let mut seen_edge: FxHashSet<(usize, usize)> = FxHashSet::default();
1192    let mut seen_self_loop: FxHashSet<FileId> = FxHashSet::default();
1193    for entry in re_export_info {
1194        let from = node_index[&entry.barrel];
1195        let to = node_index[&entry.source];
1196        if from == to {
1197            if seen_self_loop.insert(entry.barrel) {
1198                cycles.push(build_self_loop_cycle(entry.barrel, modules));
1199            }
1200            continue;
1201        }
1202        if seen_edge.insert((from, to)) {
1203            adj[from].push(to);
1204        }
1205    }
1206    adj
1207}
1208
1209/// Emit the `tracing::warn!` and structured cycle for a self-re-export edge.
1210fn build_self_loop_cycle(
1211    barrel: FileId,
1212    modules: &[super::types::ModuleNode],
1213) -> GraphReExportCycle {
1214    let (path_buf, path_display) = module_path_and_display(barrel, modules);
1215    tracing::warn!(
1216        file = path_display.as_str(),
1217        "Re-export self-loop detected: this file re-exports from \
1218         itself. Chain propagation is structurally a no-op for \
1219         these edges. Inspect the barrel for an accidental \
1220         `export * from './<this-file>'` after a rename or move."
1221    );
1222    GraphReExportCycle {
1223        files: vec![path_buf],
1224        file_ids: vec![barrel],
1225        is_self_loop: true,
1226    }
1227}
1228
1229/// Emit the `tracing::warn!` and structured cycle for a multi-node SCC.
1230fn build_multi_node_cycle(
1231    scc: &[usize],
1232    nodes: &[FileId],
1233    modules: &[super::types::ModuleNode],
1234) -> GraphReExportCycle {
1235    let mut triples: Vec<(PathBuf, String, FileId)> = scc
1236        .iter()
1237        .map(|&idx| {
1238            let file_id = nodes[idx];
1239            let (path, display) = module_path_and_display(file_id, modules);
1240            (path, display, file_id)
1241        })
1242        .collect();
1243    triples.sort_by(|a, b| a.1.cmp(&b.1));
1244    let members = triples
1245        .iter()
1246        .map(|(_, d, _)| d.as_str())
1247        .collect::<Vec<_>>()
1248        .join(" <-> ");
1249    tracing::warn!(
1250        target: fallow_types::ANALYSIS_DIAGNOSTIC_LOG_TARGET,
1251        cycle_size = scc.len(),
1252        members = members.as_str(),
1253        "Re-export cycle detected: chain propagation may be incomplete \
1254         for symbols on this barrel loop. Break the cycle to restore \
1255         full reachability analysis."
1256    );
1257    let (files, file_ids) = triples.into_iter().fold(
1258        (Vec::new(), Vec::new()),
1259        |(mut paths, mut ids), (p, _, id)| {
1260            paths.push(p);
1261            ids.push(id);
1262            (paths, ids)
1263        },
1264    );
1265    GraphReExportCycle {
1266        files,
1267        file_ids,
1268        is_self_loop: false,
1269    }
1270}
1271
1272/// Resolve a `FileId` to its `(PathBuf, display string)`, falling back to a
1273/// placeholder when the id is outside the module list.
1274fn module_path_and_display(
1275    file_id: FileId,
1276    modules: &[super::types::ModuleNode],
1277) -> (PathBuf, String) {
1278    let i = file_id.0 as usize;
1279    if i < modules.len() {
1280        let p = modules[i].path.clone();
1281        let d = p.display().to_string();
1282        (p, d)
1283    } else {
1284        let placeholder = format!("<file id {i}>");
1285        (PathBuf::from(&placeholder), placeholder)
1286    }
1287}
1288
1289struct TarjanFrame {
1290    node: usize,
1291    next_succ: usize,
1292}
1293
1294/// Mutable Tarjan SCC state shared across the iterative DFS.
1295struct TarjanState {
1296    index_counter: u32,
1297    indices: Vec<u32>,
1298    lowlinks: Vec<u32>,
1299    on_stack: fixedbitset::FixedBitSet,
1300    stack: Vec<usize>,
1301    sccs: Vec<Vec<usize>>,
1302}
1303
1304impl TarjanState {
1305    fn new(n: usize) -> Self {
1306        Self {
1307            index_counter: 0,
1308            indices: vec![u32::MAX; n],
1309            lowlinks: vec![0; n],
1310            on_stack: fixedbitset::FixedBitSet::with_capacity(n),
1311            stack: Vec::new(),
1312            sccs: Vec::new(),
1313        }
1314    }
1315
1316    /// Assign the next DFS index to `node` and push it onto the SCC stack.
1317    fn discover(&mut self, node: usize) {
1318        self.indices[node] = self.index_counter;
1319        self.lowlinks[node] = self.index_counter;
1320        self.index_counter = self.index_counter.saturating_add(1);
1321        self.stack.push(node);
1322        self.on_stack.insert(node);
1323    }
1324
1325    /// Advance one successor of the current frame, pushing a child frame when a
1326    /// new node is discovered. Returns the child node to descend into, if any.
1327    fn step_successor(&mut self, frame: &mut TarjanFrame, adj: &[Vec<usize>]) -> Option<usize> {
1328        let v = frame.node;
1329        let w = adj[v][frame.next_succ];
1330        frame.next_succ = frame.next_succ.saturating_add(1);
1331        if self.indices[w] == u32::MAX {
1332            self.discover(w);
1333            Some(w)
1334        } else {
1335            if self.on_stack.contains(w) {
1336                self.lowlinks[v] = self.lowlinks[v].min(self.indices[w]);
1337            }
1338            None
1339        }
1340    }
1341
1342    /// Finish the current frame: emit its SCC if it is a multi-node root, then
1343    /// propagate its lowlink to the parent frame.
1344    ///
1345    /// Single-node components are popped without an allocation. An acyclic
1346    /// barrel chain has one component per node, and callers only report
1347    /// components with two or more nodes.
1348    fn finish_frame(&mut self, v: usize, parent: Option<usize>) {
1349        if self.lowlinks[v] == self.indices[v] {
1350            if self.stack.last() == Some(&v) {
1351                self.stack.pop();
1352                self.on_stack.remove(v);
1353            } else {
1354                let mut scc = Vec::new();
1355                while let Some(w) = self.stack.pop() {
1356                    self.on_stack.remove(w);
1357                    scc.push(w);
1358                    if w == v {
1359                        break;
1360                    }
1361                }
1362                self.sccs.push(scc);
1363            }
1364        }
1365        if let Some(pv) = parent {
1366            self.lowlinks[pv] = self.lowlinks[pv].min(self.lowlinks[v]);
1367        }
1368    }
1369}
1370
1371/// Iterative Tarjan's strongly connected components, returns the SCCs that
1372/// contain two or more nodes. The graph is given as adjacency-by-index;
1373/// the caller maps node indices back to FileIds.
1374fn tarjan_scc(n: usize, adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
1375    let mut state = TarjanState::new(n);
1376
1377    for start in 0..n {
1378        if state.indices[start] != u32::MAX {
1379            continue;
1380        }
1381        state.discover(start);
1382        let mut dfs: Vec<TarjanFrame> = vec![TarjanFrame {
1383            node: start,
1384            next_succ: 0,
1385        }];
1386
1387        while let Some(frame) = dfs.last_mut() {
1388            let v = frame.node;
1389            if frame.next_succ < adj[v].len() {
1390                if let Some(child) = state.step_successor(frame, adj) {
1391                    dfs.push(TarjanFrame {
1392                        node: child,
1393                        next_succ: 0,
1394                    });
1395                }
1396            } else {
1397                dfs.pop();
1398                state.finish_frame(v, dfs.last().map(|parent| parent.node));
1399            }
1400        }
1401    }
1402
1403    state.sccs
1404}