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