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}
94
95struct ReExportTuple {
101 barrel: FileId,
102 source: FileId,
103 imported_name: String,
104 exported_name: String,
105 is_type_only: bool,
110}
111
112impl ReExportTuple {
113 fn is_namespace(&self) -> bool {
115 self.imported_name == "*" && self.exported_name != "*"
116 }
117}
118
119struct ReExportContext<'a> {
120 entry_star_targets: &'a FxHashSet<FileId>,
121 edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
122 binding_usage: &'a ImportBindingUsageIndex,
123 effective_exports: &'a super::effective_exports::EffectiveExportIndex,
124 existing_refs: &'a mut FxHashSet<RoutedReferenceKey>,
125 synthetic_stubs: &'a mut FxHashSet<(FileId, String, bool)>,
126 declaration_routes: &'a mut EffectiveDeclarationRouteCache,
127 scratch: &'a mut NamedPropagationScratch,
128 reference_paths: &'a mut ReferencePathInterner,
129 named_star_refs: &'a mut NamedStarRefCache,
130}
131
132#[derive(Clone, Copy, PartialEq, Eq, Debug)]
137enum Exposure {
138 StarSurface,
140 NamespaceObject,
143}
144
145#[derive(Default)]
153pub(in crate::graph) struct WholeModuleObservations {
154 ambient: FxHashMap<FileId, Exposure>,
156 observed: FxHashSet<FileId>,
158}
159
160impl WholeModuleObservations {
161 pub(in crate::graph) fn observe(&mut self, target: FileId) {
163 self.observed.insert(target);
164 }
165
166 pub(in crate::graph) fn observe_ambient_star(&mut self, target: FileId) {
168 self.ambient.entry(target).or_insert(Exposure::StarSurface);
169 }
170
171 pub(in crate::graph) fn observe_ambient_namespace(&mut self, target: FileId) {
173 self.ambient.insert(target, Exposure::NamespaceObject);
174 }
175
176 fn seeds<'a>(
179 &'a self,
180 entry_reachable: &'a FixedBitSet,
181 ) -> impl Iterator<Item = (FileId, Exposure)> + 'a {
182 self.ambient
183 .iter()
184 .map(|(&target, &exposure)| (target, exposure))
185 .chain(
186 self.observed
187 .iter()
188 .copied()
189 .filter(|target| entry_reachable.contains(target.0 as usize))
190 .map(|target| (target, Exposure::NamespaceObject)),
191 )
192 }
193}
194
195pub(in crate::graph) struct ExposedNamespaceTargets {
202 members: FxHashMap<FileId, Exposure>,
203}
204
205impl ExposedNamespaceTargets {
206 pub(in crate::graph) fn is_empty(&self) -> bool {
208 self.members.is_empty()
209 }
210
211 pub(in crate::graph) fn exposes_name(&self, file_id: FileId, exported_name: &str) -> bool {
218 match self.members.get(&file_id) {
219 Some(Exposure::NamespaceObject) => true,
220 Some(Exposure::StarSurface) => exported_name != "default",
221 None => false,
222 }
223 }
224
225 fn files(&self) -> impl Iterator<Item = FileId> + '_ {
231 self.members.keys().copied()
232 }
233
234 fn record(&mut self, stack: &mut Vec<(FileId, Exposure)>, file_id: FileId, exposure: Exposure) {
237 match self.members.entry(file_id) {
238 std::collections::hash_map::Entry::Occupied(mut slot) => {
239 if *slot.get() == Exposure::StarSurface && exposure == Exposure::NamespaceObject {
240 slot.insert(exposure);
241 stack.push((file_id, exposure));
242 }
243 }
244 std::collections::hash_map::Entry::Vacant(slot) => {
245 slot.insert(exposure);
246 stack.push((file_id, exposure));
247 }
248 }
249 }
250}
251
252fn is_namespace_re_export(re: &super::types::ReExportEdge) -> bool {
255 re.imported_name == "*" && re.exported_name != "*"
256}
257
258struct NameForwarders<'a> {
264 named: FxHashMap<(FileId, &'a str), Vec<(FileId, &'a str)>>,
267 stars: FxHashMap<FileId, Vec<FileId>>,
269}
270
271#[derive(Default)]
279struct NameSearchScratch<'a> {
280 visited: FxHashSet<(FileId, &'a str)>,
281 frontier: Vec<(FileId, &'a str)>,
282 failed: FxHashSet<(FileId, &'a str)>,
283}
284
285impl<'a> NameForwarders<'a> {
286 fn build(modules: &'a [super::types::ModuleNode]) -> Self {
287 let mut named: FxHashMap<(FileId, &'a str), Vec<(FileId, &'a str)>> = FxHashMap::default();
288 let mut stars: FxHashMap<FileId, Vec<FileId>> = FxHashMap::default();
289 for module in modules {
290 for re in &module.re_exports {
291 if re.imported_name == "*" {
292 if re.exported_name == "*" {
293 stars
294 .entry(re.source_file)
295 .or_default()
296 .push(module.file_id);
297 }
298 } else {
299 named
300 .entry((re.source_file, re.imported_name.as_str()))
301 .or_default()
302 .push((module.file_id, re.exported_name.as_str()));
303 }
304 }
305 }
306 Self { named, stars }
307 }
308}
309
310fn extend_forwarding_sources(
320 modules: &[super::types::ModuleNode],
321 may_reach: &mut FxHashSet<FileId>,
322 seeds: impl IntoIterator<Item = FileId>,
323) {
324 let mut stack: Vec<FileId> = seeds
325 .into_iter()
326 .filter(|seed| may_reach.insert(*seed))
327 .collect();
328 while let Some(barrel) = stack.pop() {
329 let Some(module) = modules.get(barrel.0 as usize) else {
330 continue;
331 };
332 for re in &module.re_exports {
333 if !is_namespace_re_export(re) && may_reach.insert(re.source_file) {
334 stack.push(re.source_file);
335 }
336 }
337 }
338}
339
340struct ExposedNameSearch<'a> {
350 forwarders: NameForwarders<'a>,
351 whole_object_names: FxHashMap<FileId, Vec<String>>,
356 may_reach: FxHashSet<FileId>,
364 scratch: NameSearchScratch<'a>,
365}
366
367impl<'a> ExposedNameSearch<'a> {
368 fn build(
369 modules: &'a [super::types::ModuleNode],
370 module_by_id: &FxHashMap<FileId, &ResolvedModule>,
371 ) -> Self {
372 let mut whole_object_names: FxHashMap<FileId, Vec<String>> = FxHashMap::default();
373 for consumer in module_by_id.values() {
374 if consumer.whole_object_uses.is_empty() {
375 continue;
376 }
377 for import in &consumer.resolved_imports {
378 let Some(target) = import.target.internal_file_id() else {
379 continue;
380 };
381 let imported_name = match &import.info.imported_name {
382 fallow_types::extract::ImportedName::Named(name) => name.as_str(),
383 fallow_types::extract::ImportedName::Default => "default",
384 _ => continue,
385 };
386 let local_name = import.info.local_name.as_str();
387 if local_name.is_empty()
388 || !consumer
389 .whole_object_uses
390 .iter()
391 .any(|used| used == local_name)
392 {
393 continue;
394 }
395 let names = whole_object_names.entry(target).or_default();
396 if !names.iter().any(|name| name == imported_name) {
397 names.push(imported_name.to_string());
398 }
399 }
400 }
401
402 let mut may_reach = FxHashSet::default();
403 extend_forwarding_sources(
404 modules,
405 &mut may_reach,
406 modules
407 .iter()
408 .filter(|m| m.is_entry_point())
409 .map(|m| m.file_id)
410 .chain(whole_object_names.keys().copied()),
411 );
412
413 Self {
414 forwarders: NameForwarders::build(modules),
415 whole_object_names,
416 may_reach,
417 scratch: NameSearchScratch::default(),
418 }
419 }
420
421 fn refresh(
428 &mut self,
429 modules: &'a [super::types::ModuleNode],
430 closure: &ExposedNamespaceTargets,
431 ) {
432 extend_forwarding_sources(
433 modules,
434 &mut self.may_reach,
435 closure.members.keys().copied(),
436 );
437 self.scratch.failed.clear();
438 }
439
440 fn reaches_exposure(
451 &mut self,
452 graph: &ModuleGraph,
453 closure: &ExposedNamespaceTargets,
454 file: FileId,
455 name: &'a str,
456 ) -> bool {
457 if !self.may_reach.contains(&file) || self.scratch.failed.contains(&(file, name)) {
458 return false;
459 }
460 let Self {
461 forwarders,
462 whole_object_names,
463 may_reach,
464 scratch,
465 } = self;
466 scratch.visited.clear();
467 scratch.frontier.clear();
468 scratch.visited.insert((file, name));
469 scratch.frontier.push((file, name));
470 while let Some((current, current_name)) = scratch.frontier.pop() {
471 if exposes_here(graph, closure, whole_object_names, current, current_name) {
472 return true;
473 }
474 if let Some(barrels) = forwarders.named.get(&(current, current_name)) {
475 for &(barrel, exported_name) in barrels {
476 if may_reach.contains(&barrel)
477 && graph.forwards_binding(current, current_name, barrel, exported_name)
478 && !scratch.failed.contains(&(barrel, exported_name))
479 && scratch.visited.insert((barrel, exported_name))
480 {
481 scratch.frontier.push((barrel, exported_name));
482 }
483 }
484 }
485 if current_name == "default" {
486 continue;
487 }
488 if let Some(barrels) = forwarders.stars.get(¤t) {
489 for &barrel in barrels {
490 if may_reach.contains(&barrel)
491 && graph.forwards_binding(current, current_name, barrel, current_name)
492 && !scratch.failed.contains(&(barrel, current_name))
493 && scratch.visited.insert((barrel, current_name))
494 {
495 scratch.frontier.push((barrel, current_name));
496 }
497 }
498 }
499 }
500 scratch.failed.extend(scratch.visited.iter().copied());
501 false
502 }
503}
504
505fn exposes_here(
512 graph: &ModuleGraph,
513 closure: &ExposedNamespaceTargets,
514 whole_object_names: &FxHashMap<FileId, Vec<String>>,
515 file: FileId,
516 name: &str,
517) -> bool {
518 graph.is_entry_point_file(file)
519 || closure.exposes_name(file, name)
520 || whole_object_names
521 .get(&file)
522 .is_some_and(|names| names.iter().any(|candidate| candidate == name))
523}
524
525struct ReExportFixpointInput<'a> {
526 re_export_info: &'a [ReExportTuple],
527 entry_star_targets: &'a FxHashSet<FileId>,
528 edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
529 module_by_id: &'a FxHashMap<FileId, &'a ResolvedModule>,
530 reference_paths: &'a mut ReferencePathInterner,
531}
532
533#[cfg(test)]
534struct LegacyReExportFullScan<'a> {
535 modules: &'a mut [super::types::ModuleNode],
536 edges: &'a [Edge],
537 re_export_info: &'a [ReExportTuple],
538 entry_star_targets: &'a FxHashSet<FileId>,
539 edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
540 module_by_id: &'a FxHashMap<FileId, &'a ResolvedModule>,
541 effective_exports: &'a super::effective_exports::EffectiveExportIndex,
542 reference_paths: &'a mut ReferencePathInterner,
543}
544
545struct ReExportPropagationPlan {
552 observers_by_module: FxHashMap<FileId, Vec<usize>>,
553 queue: VecDeque<usize>,
554 enqueued: Vec<bool>,
555}
556
557impl ReExportPropagationPlan {
558 fn new(re_export_info: &[ReExportTuple]) -> Self {
559 let mut observers_by_module: FxHashMap<FileId, Vec<usize>> = FxHashMap::default();
560 for (idx, entry) in re_export_info.iter().enumerate() {
561 observers_by_module
562 .entry(entry.barrel)
563 .or_default()
564 .push(idx);
565 }
566
567 Self {
568 observers_by_module,
569 queue: (0..re_export_info.len()).collect(),
570 enqueued: vec![true; re_export_info.len()],
571 }
572 }
573
574 fn pop_front(&mut self) -> Option<usize> {
575 let idx = self.queue.pop_front()?;
576 self.enqueued[idx] = false;
577 Some(idx)
578 }
579
580 fn enqueue_observers(&mut self, changed_module: FileId) {
581 let Some(observers) = self.observers_by_module.get(&changed_module) else {
582 return;
583 };
584 for &idx in observers {
585 if !self.enqueued[idx] {
586 self.enqueued[idx] = true;
587 self.queue.push_back(idx);
588 }
589 }
590 }
591}
592
593impl ModuleGraph {
594 pub(super) fn resolve_re_export_chains(
603 &mut self,
604 module_by_id: &FxHashMap<FileId, &ResolvedModule>,
605 exposed_namespace_targets: &ExposedNamespaceTargets,
606 reference_paths: &mut ReferencePathInterner,
607 ) -> Vec<GraphReExportCycle> {
608 let re_export_info = self.collect_re_export_tuples();
609
610 if re_export_info.is_empty() {
611 return Vec::new();
612 }
613
614 let cycles = find_re_export_cycles(&self.modules, &re_export_info);
615
616 let entry_star_targets = self.collect_entry_star_targets(exposed_namespace_targets);
617 let edges_by_target = self.build_edges_by_target();
618
619 self.run_re_export_fixpoint(ReExportFixpointInput {
620 re_export_info: &re_export_info,
621 entry_star_targets: &entry_star_targets,
622 edges_by_target: &edges_by_target,
623 module_by_id,
624 reference_paths,
625 });
626
627 cycles
628 }
629
630 fn collect_re_export_tuples(&self) -> Vec<ReExportTuple> {
637 let asset_only = self.asset_only_modules();
638 self.modules
639 .iter()
640 .filter(|m| !asset_only.contains(m.file_id.0 as usize))
641 .flat_map(|m| {
642 m.re_exports.iter().map(move |re| ReExportTuple {
643 barrel: m.file_id,
644 source: re.source_file,
645 imported_name: re.imported_name.clone(),
646 exported_name: re.exported_name.clone(),
647 is_type_only: re.is_type_only,
648 })
649 })
650 .collect()
651 }
652
653 fn asset_only_modules(&self) -> FixedBitSet {
656 let total = self.modules.len();
657 let mut asset_loaded = FixedBitSet::with_capacity(total);
658 let mut run_loaded = FixedBitSet::with_capacity(total);
659 for edge in &self.edges {
660 let target = edge.target.0 as usize;
661 if target >= total {
662 continue;
663 }
664 if edge.runs_target_code() {
665 run_loaded.insert(target);
666 } else {
667 asset_loaded.insert(target);
668 }
669 }
670 asset_loaded.difference_with(&run_loaded);
671 for module in &self.modules {
672 if module.is_entry_point() {
673 asset_loaded.set(module.file_id.0 as usize, false);
674 }
675 }
676 asset_loaded
677 }
678
679 fn collect_entry_star_targets(
685 &self,
686 exposed_namespace_targets: &ExposedNamespaceTargets,
687 ) -> FxHashSet<FileId> {
688 let mut entry_star_targets: FxHashSet<FileId> = exposed_namespace_targets.files().collect();
689 entry_star_targets.extend(self.modules.iter().filter(|m| m.is_entry_point()).flat_map(
690 |m| {
691 m.re_exports
692 .iter()
693 .filter(|re| re.exported_name == "*")
694 .map(|re| re.source_file)
695 },
696 ));
697 self.extend_plain_star_closure(&mut entry_star_targets);
698 entry_star_targets
699 }
700
701 pub(in crate::graph) fn collect_exposed_namespace_targets(
748 &self,
749 whole_module_targets: &WholeModuleObservations,
750 entry_reachable: &FixedBitSet,
751 module_by_id: &FxHashMap<FileId, &ResolvedModule>,
752 ) -> ExposedNamespaceTargets {
753 let mut closure = ExposedNamespaceTargets {
754 members: FxHashMap::default(),
755 };
756 let mut stack: Vec<(FileId, Exposure)> = Vec::new();
757 for (seed, exposure) in whole_module_targets.seeds(entry_reachable) {
758 closure.record(&mut stack, seed, exposure);
759 }
760
761 let mut pending: Vec<(FileId, &str, FileId)> = self
762 .modules
763 .iter()
764 .flat_map(|m| {
765 m.re_exports
766 .iter()
767 .filter(|re| is_namespace_re_export(re))
768 .map(move |re| (m.file_id, re.exported_name.as_str(), re.source_file))
769 })
770 .filter(|(_, _, source)| entry_reachable.contains(source.0 as usize))
771 .collect();
772 let mut search =
773 (!pending.is_empty()).then(|| ExposedNameSearch::build(&self.modules, module_by_id));
774
775 loop {
776 self.extend_exposure_walk(&mut closure, &mut stack);
777 let Some(search) = search.as_mut() else { break };
778 if pending.is_empty() {
779 break;
780 }
781 search.refresh(&self.modules, &closure);
782 let mut widened = false;
783 let mut still_pending = Vec::with_capacity(pending.len());
784 for (barrel, exported_name, source) in std::mem::take(&mut pending) {
785 if closure.members.get(&source) == Some(&Exposure::NamespaceObject) {
786 continue;
787 }
788 if search.reaches_exposure(self, &closure, barrel, exported_name) {
789 closure.record(&mut stack, source, Exposure::NamespaceObject);
790 widened = true;
791 } else {
792 still_pending.push((barrel, exported_name, source));
793 }
794 }
795 pending = still_pending;
796 if !widened {
797 break;
798 }
799 }
800 closure
801 }
802
803 fn extend_exposure_walk(
811 &self,
812 closure: &mut ExposedNamespaceTargets,
813 stack: &mut Vec<(FileId, Exposure)>,
814 ) {
815 while let Some((file_id, exposure)) = stack.pop() {
816 let Some(module) = self.modules.get(file_id.0 as usize) else {
817 continue;
818 };
819 for re in &module.re_exports {
820 if re.imported_name != "*" {
821 continue;
822 }
823 let next = if re.exported_name == "*" {
824 Exposure::StarSurface
825 } else if exposure == Exposure::NamespaceObject || re.exported_name != "default" {
826 Exposure::NamespaceObject
827 } else {
828 continue;
829 };
830 closure.record(stack, re.source_file, next);
831 }
832 }
833 }
834
835 fn forwards_binding(
845 &self,
846 source: FileId,
847 source_name: &str,
848 barrel: FileId,
849 barrel_name: &str,
850 ) -> bool {
851 for namespace in [super::ExportNamespace::Value, super::ExportNamespace::Type] {
852 if !matches!(
853 self.resolve_export(source, source_name, namespace),
854 super::EffectiveExportResolution::Unique(_)
855 ) {
856 continue;
857 }
858 return super::namespace_indexes::uniquely_forwards_binding(
859 self,
860 source,
861 source_name,
862 barrel,
863 barrel_name,
864 namespace,
865 );
866 }
867 false
868 }
869
870 fn is_entry_point_file(&self, file_id: FileId) -> bool {
872 self.modules
873 .get(file_id.0 as usize)
874 .is_some_and(super::types::ModuleNode::is_entry_point)
875 }
876
877 fn extend_plain_star_closure(&self, targets: &mut FxHashSet<FileId>) {
880 let mut stack: Vec<FileId> = targets.iter().copied().collect();
881 while let Some(file_id) = stack.pop() {
882 let Some(module) = self.modules.get(file_id.0 as usize) else {
883 continue;
884 };
885 for re in module
886 .re_exports
887 .iter()
888 .filter(|re| re.imported_name == "*" && re.exported_name == "*")
889 {
890 if targets.insert(re.source_file) {
891 stack.push(re.source_file);
892 }
893 }
894 }
895 }
896
897 fn build_edges_by_target(&self) -> FxHashMap<FileId, Vec<usize>> {
899 let mut edges_by_target: FxHashMap<FileId, Vec<usize>> = FxHashMap::default();
900 for (idx, edge) in self.edges.iter().enumerate() {
901 edges_by_target.entry(edge.target).or_default().push(idx);
902 }
903 edges_by_target
904 }
905
906 fn run_re_export_fixpoint(&mut self, input: ReExportFixpointInput<'_>) {
908 let ReExportFixpointInput {
909 re_export_info,
910 entry_star_targets,
911 edges_by_target,
912 module_by_id,
913 reference_paths,
914 } = input;
915 #[cfg(test)]
916 let mut legacy_modules: Option<Vec<super::types::ModuleNode>> = DIFFERENTIAL_CHECK_ENABLED
917 .with(|enabled| {
918 enabled.get().then(|| {
919 serde_json::from_value(
920 serde_json::to_value(&self.modules)
921 .expect("module graph should serialize for differential testing"),
922 )
923 .expect("module graph should deserialize for differential testing")
924 })
925 });
926
927 let safety_cap = self.re_export_transition_safety_cap(re_export_info);
928 let mut processed = 0usize;
929 let mut plan = ReExportPropagationPlan::new(re_export_info);
930 let mut existing_refs: FxHashSet<RoutedReferenceKey> = FxHashSet::default();
931 let mut synthetic_stubs: FxHashSet<(FileId, String, bool)> = FxHashSet::default();
932 let binding_usage = ImportBindingUsageIndex::build(module_by_id);
933 let mut declaration_routes = EffectiveDeclarationRouteCache::default();
934 let mut scratch = NamedPropagationScratch::default();
935 let mut named_star_refs = NamedStarRefCache::default();
936
937 while let Some(entry_idx) = plan.pop_front() {
938 if processed >= safety_cap {
939 tracing::error!(
940 processed,
941 safety_cap,
942 re_export_edges = re_export_info.len(),
943 "Re-export propagation exceeded its finite-state safety cap; \
944 propagation may be non-monotonic. Please file a bug at \
945 https://github.com/fallow-rs/fallow/issues with the repro."
946 );
947 break;
948 }
949 processed += 1;
950
951 let mut context = ReExportContext {
952 entry_star_targets,
953 edges_by_target,
954 binding_usage: &binding_usage,
955 effective_exports: &self.effective_exports,
956 existing_refs: &mut existing_refs,
957 synthetic_stubs: &mut synthetic_stubs,
958 declaration_routes: &mut declaration_routes,
959 scratch: &mut scratch,
960 reference_paths,
961 named_star_refs: &mut named_star_refs,
962 };
963
964 let entry = &re_export_info[entry_idx];
965 #[cfg(test)]
966 record_propagation_visit(entry);
967 if Self::propagate_re_export_entry(&mut self.modules, &self.edges, entry, &mut context)
968 {
969 plan.enqueue_observers(entry.source);
970 }
971 }
972
973 #[cfg(test)]
974 if let Some(legacy_modules) = legacy_modules.as_mut() {
975 propagate::without_star_source_filter(|| {
978 Self::run_re_export_full_scan(LegacyReExportFullScan {
979 modules: legacy_modules,
980 edges: &self.edges,
981 re_export_info,
982 entry_star_targets,
983 edges_by_target,
984 module_by_id,
985 effective_exports: &self.effective_exports,
986 reference_paths,
987 });
988 });
989 assert_eq!(
990 serde_json::to_value(legacy_modules)
991 .expect("legacy module graph should serialize for comparison"),
992 serde_json::to_value(&self.modules)
993 .expect("queue module graph should serialize for comparison"),
994 "work-queue propagation must match the legacy full-scan fixpoint"
995 );
996 }
997 }
998
999 fn re_export_transition_safety_cap(&self, re_export_info: &[ReExportTuple]) -> usize {
1002 let initial_exports = self
1003 .modules
1004 .iter()
1005 .map(|module| module.exports.len())
1006 .sum::<usize>();
1007 let named_inputs = self
1008 .edges
1009 .iter()
1010 .flat_map(|edge| &edge.symbols)
1011 .filter(|symbol| {
1012 matches!(
1013 &symbol.imported_name,
1014 fallow_types::extract::ImportedName::Named(_)
1015 )
1016 })
1017 .count()
1018 .saturating_add(initial_exports)
1019 .saturating_add(re_export_info.len());
1020
1021 let module_count = self.modules.len();
1022 let synthetic_export_hosts = self
1023 .modules
1024 .iter()
1025 .filter(|module| {
1026 module
1027 .re_exports
1028 .iter()
1029 .any(|re_export| re_export.exported_name == "*")
1030 })
1031 .count();
1032 let synthetic_exports = synthetic_export_hosts
1033 .saturating_mul(named_inputs)
1034 .saturating_mul(2);
1035 let max_exports = initial_exports.saturating_add(synthetic_exports);
1036 let reference_additions = max_exports.saturating_mul(module_count).saturating_mul(2);
1037 let state_changes = synthetic_exports.saturating_add(reference_additions);
1038
1039 re_export_info
1040 .len()
1041 .saturating_add(state_changes.saturating_mul(re_export_info.len()))
1042 .max(re_export_info.len())
1043 }
1044
1045 fn propagate_re_export_entry(
1047 modules: &mut [super::types::ModuleNode],
1048 edges: &[Edge],
1049 entry: &ReExportTuple,
1050 context: &mut ReExportContext<'_>,
1051 ) -> bool {
1052 let barrel_idx = entry.barrel.0 as usize;
1053 let source_idx = entry.source.0 as usize;
1054
1055 if barrel_idx >= modules.len() || source_idx >= modules.len() {
1056 return false;
1057 }
1058
1059 if entry.exported_name == "*" {
1060 propagate_star_re_export(StarReExportPropagation {
1061 modules,
1062 edges,
1063 edges_by_target: context.edges_by_target,
1064 binding_usage: context.binding_usage,
1065 effective_exports: context.effective_exports,
1066 barrel_id: entry.barrel,
1067 barrel_idx,
1068 source_id: entry.source,
1069 source_idx,
1070 entry_star_targets: context.entry_star_targets,
1071 triggering_is_type_only: entry.is_type_only,
1072 synthetic_stubs: context.synthetic_stubs,
1073 reference_paths: context.reference_paths,
1074 named_star_refs: context.named_star_refs,
1075 })
1076 } else {
1077 propagate_named_re_export(NamedReExportPropagation {
1078 modules,
1079 effective_exports: context.effective_exports,
1080 barrel_id: entry.barrel,
1081 barrel_idx,
1082 source_id: entry.source,
1083 source_idx,
1084 imported_name: &entry.imported_name,
1085 exported_name: &entry.exported_name,
1086 is_type_only: entry.is_type_only,
1087 existing_refs: context.existing_refs,
1088 declaration_routes: context.declaration_routes,
1089 scratch: context.scratch,
1090 reference_paths: context.reference_paths,
1091 })
1092 }
1093 }
1094
1095 #[cfg(test)]
1096 fn run_re_export_full_scan(input: LegacyReExportFullScan<'_>) {
1097 let LegacyReExportFullScan {
1098 modules,
1099 edges,
1100 re_export_info,
1101 entry_star_targets,
1102 edges_by_target,
1103 module_by_id,
1104 effective_exports,
1105 reference_paths,
1106 } = input;
1107 let max_iterations = re_export_info.len().saturating_add(1);
1108 let mut existing_refs: FxHashSet<RoutedReferenceKey> = FxHashSet::default();
1109 let mut synthetic_stubs: FxHashSet<(FileId, String, bool)> = FxHashSet::default();
1110 let binding_usage = ImportBindingUsageIndex::build(module_by_id);
1111 let mut declaration_routes = EffectiveDeclarationRouteCache::default();
1112 let mut scratch = NamedPropagationScratch::default();
1113
1114 for _ in 0..max_iterations {
1115 let mut changed = false;
1116 for entry in re_export_info {
1117 let mut context = ReExportContext {
1118 entry_star_targets,
1119 edges_by_target,
1120 binding_usage: &binding_usage,
1121 effective_exports,
1122 existing_refs: &mut existing_refs,
1123 synthetic_stubs: &mut synthetic_stubs,
1124 declaration_routes: &mut declaration_routes,
1125 scratch: &mut scratch,
1126 reference_paths,
1127 named_star_refs: &mut NamedStarRefCache::default(),
1130 };
1131 changed |= Self::propagate_re_export_entry(modules, edges, entry, &mut context);
1132 }
1133 if !changed {
1134 break;
1135 }
1136 }
1137 }
1138}
1139
1140fn find_re_export_cycles(
1149 modules: &[super::types::ModuleNode],
1150 re_export_info: &[ReExportTuple],
1151) -> Vec<GraphReExportCycle> {
1152 let mut cycles: Vec<GraphReExportCycle> = Vec::new();
1153
1154 let (node_index, nodes) = build_re_export_node_index(re_export_info);
1155 let n = nodes.len();
1156 if n == 0 {
1157 return cycles;
1158 }
1159
1160 let adj = build_re_export_adjacency(re_export_info, &node_index, modules, &mut cycles);
1161
1162 let sccs = tarjan_scc(n, &adj);
1163
1164 for scc in &sccs {
1165 cycles.push(build_multi_node_cycle(scc, &nodes, modules));
1166 }
1167
1168 cycles
1169}
1170
1171fn build_re_export_node_index(
1173 re_export_info: &[ReExportTuple],
1174) -> (FxHashMap<FileId, usize>, Vec<FileId>) {
1175 let mut node_index: FxHashMap<FileId, usize> = FxHashMap::default();
1176 let mut nodes: Vec<FileId> = Vec::new();
1177 for entry in re_export_info {
1178 for &id in &[entry.barrel, entry.source] {
1179 node_index.entry(id).or_insert_with(|| {
1180 let idx = nodes.len();
1181 nodes.push(id);
1182 idx
1183 });
1184 }
1185 }
1186 (node_index, nodes)
1187}
1188
1189fn build_re_export_adjacency(
1195 re_export_info: &[ReExportTuple],
1196 node_index: &FxHashMap<FileId, usize>,
1197 modules: &[super::types::ModuleNode],
1198 cycles: &mut Vec<GraphReExportCycle>,
1199) -> Vec<Vec<usize>> {
1200 let mut adj: Vec<Vec<usize>> = vec![Vec::new(); node_index.len()];
1201 let mut seen_edge: FxHashSet<(usize, usize)> = FxHashSet::default();
1202 let mut seen_self_loop: FxHashSet<FileId> = FxHashSet::default();
1203 for entry in re_export_info {
1204 if entry.is_namespace() {
1205 continue;
1206 }
1207 let from = node_index[&entry.barrel];
1208 let to = node_index[&entry.source];
1209 if from == to {
1210 if seen_self_loop.insert(entry.barrel) {
1211 cycles.push(build_self_loop_cycle(entry.barrel, modules));
1212 }
1213 continue;
1214 }
1215 if seen_edge.insert((from, to)) {
1216 adj[from].push(to);
1217 }
1218 }
1219 adj
1220}
1221
1222fn build_self_loop_cycle(
1224 barrel: FileId,
1225 modules: &[super::types::ModuleNode],
1226) -> GraphReExportCycle {
1227 let (path_buf, path_display) = module_path_and_display(barrel, modules);
1228 tracing::warn!(
1229 file = path_display.as_str(),
1230 "Re-export self-loop detected: this file re-exports from \
1231 itself. Chain propagation is structurally a no-op for \
1232 these edges. Inspect the barrel for an accidental \
1233 `export * from './<this-file>'` after a rename or move."
1234 );
1235 GraphReExportCycle {
1236 files: vec![path_buf],
1237 file_ids: vec![barrel],
1238 is_self_loop: true,
1239 }
1240}
1241
1242fn build_multi_node_cycle(
1244 scc: &[usize],
1245 nodes: &[FileId],
1246 modules: &[super::types::ModuleNode],
1247) -> GraphReExportCycle {
1248 let mut triples: Vec<(PathBuf, String, FileId)> = scc
1249 .iter()
1250 .map(|&idx| {
1251 let file_id = nodes[idx];
1252 let (path, display) = module_path_and_display(file_id, modules);
1253 (path, display, file_id)
1254 })
1255 .collect();
1256 triples.sort_by(|a, b| a.1.cmp(&b.1));
1257 let members = triples
1258 .iter()
1259 .map(|(_, d, _)| d.as_str())
1260 .collect::<Vec<_>>()
1261 .join(" <-> ");
1262 tracing::warn!(
1263 target: fallow_types::ANALYSIS_DIAGNOSTIC_LOG_TARGET,
1264 cycle_size = scc.len(),
1265 members = members.as_str(),
1266 "Re-export cycle detected: chain propagation may be incomplete \
1267 for symbols on this barrel loop. Break the cycle to restore \
1268 full reachability analysis."
1269 );
1270 let (files, file_ids) = triples.into_iter().fold(
1271 (Vec::new(), Vec::new()),
1272 |(mut paths, mut ids), (p, _, id)| {
1273 paths.push(p);
1274 ids.push(id);
1275 (paths, ids)
1276 },
1277 );
1278 GraphReExportCycle {
1279 files,
1280 file_ids,
1281 is_self_loop: false,
1282 }
1283}
1284
1285fn module_path_and_display(
1288 file_id: FileId,
1289 modules: &[super::types::ModuleNode],
1290) -> (PathBuf, String) {
1291 let i = file_id.0 as usize;
1292 if i < modules.len() {
1293 let p = modules[i].path.clone();
1294 let d = p.display().to_string();
1295 (p, d)
1296 } else {
1297 let placeholder = format!("<file id {i}>");
1298 (PathBuf::from(&placeholder), placeholder)
1299 }
1300}
1301
1302struct TarjanFrame {
1303 node: usize,
1304 next_succ: usize,
1305}
1306
1307struct TarjanState {
1309 index_counter: u32,
1310 indices: Vec<u32>,
1311 lowlinks: Vec<u32>,
1312 on_stack: fixedbitset::FixedBitSet,
1313 stack: Vec<usize>,
1314 sccs: Vec<Vec<usize>>,
1315}
1316
1317impl TarjanState {
1318 fn new(n: usize) -> Self {
1319 Self {
1320 index_counter: 0,
1321 indices: vec![u32::MAX; n],
1322 lowlinks: vec![0; n],
1323 on_stack: fixedbitset::FixedBitSet::with_capacity(n),
1324 stack: Vec::new(),
1325 sccs: Vec::new(),
1326 }
1327 }
1328
1329 fn discover(&mut self, node: usize) {
1331 self.indices[node] = self.index_counter;
1332 self.lowlinks[node] = self.index_counter;
1333 self.index_counter = self.index_counter.saturating_add(1);
1334 self.stack.push(node);
1335 self.on_stack.insert(node);
1336 }
1337
1338 fn step_successor(&mut self, frame: &mut TarjanFrame, adj: &[Vec<usize>]) -> Option<usize> {
1341 let v = frame.node;
1342 let w = adj[v][frame.next_succ];
1343 frame.next_succ = frame.next_succ.saturating_add(1);
1344 if self.indices[w] == u32::MAX {
1345 self.discover(w);
1346 Some(w)
1347 } else {
1348 if self.on_stack.contains(w) {
1349 self.lowlinks[v] = self.lowlinks[v].min(self.indices[w]);
1350 }
1351 None
1352 }
1353 }
1354
1355 fn finish_frame(&mut self, v: usize, parent: Option<usize>) {
1362 if self.lowlinks[v] == self.indices[v] {
1363 if self.stack.last() == Some(&v) {
1364 self.stack.pop();
1365 self.on_stack.remove(v);
1366 } else {
1367 let mut scc = Vec::new();
1368 while let Some(w) = self.stack.pop() {
1369 self.on_stack.remove(w);
1370 scc.push(w);
1371 if w == v {
1372 break;
1373 }
1374 }
1375 self.sccs.push(scc);
1376 }
1377 }
1378 if let Some(pv) = parent {
1379 self.lowlinks[pv] = self.lowlinks[pv].min(self.lowlinks[v]);
1380 }
1381 }
1382}
1383
1384fn tarjan_scc(n: usize, adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
1388 let mut state = TarjanState::new(n);
1389
1390 for start in 0..n {
1391 if state.indices[start] != u32::MAX {
1392 continue;
1393 }
1394 state.discover(start);
1395 let mut dfs: Vec<TarjanFrame> = vec![TarjanFrame {
1396 node: start,
1397 next_succ: 0,
1398 }];
1399
1400 while let Some(frame) = dfs.last_mut() {
1401 let v = frame.node;
1402 if frame.next_succ < adj[v].len() {
1403 if let Some(child) = state.step_successor(frame, adj) {
1404 dfs.push(TarjanFrame {
1405 node: child,
1406 next_succ: 0,
1407 });
1408 }
1409 } else {
1410 dfs.pop();
1411 state.finish_frame(v, dfs.last().map(|parent| parent.node));
1412 }
1413 }
1414 }
1415
1416 state.sccs
1417}