1mod 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#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
80pub struct GraphReExportCycle {
81 pub files: Vec<PathBuf>,
85 pub file_ids: Vec<FileId>,
90 pub is_self_loop: bool,
93 #[serde(default)]
97 pub anchor_span_start: Option<u32>,
98}
99
100struct ReExportTuple {
106 barrel: FileId,
107 source: FileId,
108 imported_name: String,
109 exported_name: String,
110 is_type_only: bool,
115}
116
117impl ReExportTuple {
118 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#[derive(Clone, Copy, PartialEq, Eq, Debug)]
142enum Exposure {
143 StarSurface,
145 NamespaceObject,
148}
149
150#[derive(Default)]
158pub(in crate::graph) struct WholeModuleObservations {
159 ambient: FxHashMap<FileId, Exposure>,
161 observed: FxHashSet<FileId>,
163}
164
165impl WholeModuleObservations {
166 pub(in crate::graph) fn observe(&mut self, target: FileId) {
168 self.observed.insert(target);
169 }
170
171 pub(in crate::graph) fn observe_ambient_star(&mut self, target: FileId) {
173 self.ambient.entry(target).or_insert(Exposure::StarSurface);
174 }
175
176 pub(in crate::graph) fn observe_ambient_namespace(&mut self, target: FileId) {
178 self.ambient.insert(target, Exposure::NamespaceObject);
179 }
180
181 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
200pub(in crate::graph) struct ExposedNamespaceTargets {
207 members: FxHashMap<FileId, Exposure>,
208}
209
210impl ExposedNamespaceTargets {
211 pub(in crate::graph) fn is_empty(&self) -> bool {
213 self.members.is_empty()
214 }
215
216 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 fn files(&self) -> impl Iterator<Item = FileId> + '_ {
236 self.members.keys().copied()
237 }
238
239 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
257fn is_namespace_re_export(re: &super::types::ReExportEdge) -> bool {
260 re.imported_name == "*" && re.exported_name != "*"
261}
262
263struct NameForwarders<'a> {
269 named: FxHashMap<(FileId, &'a str), Vec<(FileId, &'a str)>>,
272 stars: FxHashMap<FileId, Vec<FileId>>,
274}
275
276#[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
315fn 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
345struct ExposedNameSearch<'a> {
355 forwarders: NameForwarders<'a>,
356 whole_object_names: FxHashMap<FileId, Vec<String>>,
361 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 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 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(¤t) {
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
510fn 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
550struct 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
1149fn 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
1184fn 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
1203fn 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
1221fn 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
1254fn 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
1275fn 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
1319fn 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
1341struct 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 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 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 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
1418fn 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}