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