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
112struct ReExportContext<'a> {
113 entry_star_targets: &'a FxHashSet<FileId>,
114 edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
115 binding_usage: &'a ImportBindingUsageIndex,
116 effective_exports: &'a super::effective_exports::EffectiveExportIndex,
117 existing_refs: &'a mut FxHashSet<RoutedReferenceKey>,
118 synthetic_stubs: &'a mut FxHashSet<(FileId, String, bool)>,
119 declaration_routes: &'a mut EffectiveDeclarationRouteCache,
120 scratch: &'a mut NamedPropagationScratch,
121 reference_paths: &'a mut ReferencePathInterner,
122 named_star_refs: &'a mut NamedStarRefCache,
123}
124
125#[derive(Clone, Copy, PartialEq, Eq, Debug)]
130enum Exposure {
131 StarSurface,
133 NamespaceObject,
136}
137
138#[derive(Default)]
146pub(in crate::graph) struct WholeModuleObservations {
147 ambient: FxHashMap<FileId, Exposure>,
149 observed: FxHashSet<FileId>,
151}
152
153impl WholeModuleObservations {
154 pub(in crate::graph) fn observe(&mut self, target: FileId) {
156 self.observed.insert(target);
157 }
158
159 pub(in crate::graph) fn observe_ambient_star(&mut self, target: FileId) {
161 self.ambient.entry(target).or_insert(Exposure::StarSurface);
162 }
163
164 pub(in crate::graph) fn observe_ambient_namespace(&mut self, target: FileId) {
166 self.ambient.insert(target, Exposure::NamespaceObject);
167 }
168
169 fn seeds<'a>(
172 &'a self,
173 entry_reachable: &'a FixedBitSet,
174 ) -> impl Iterator<Item = (FileId, Exposure)> + 'a {
175 self.ambient
176 .iter()
177 .map(|(&target, &exposure)| (target, exposure))
178 .chain(
179 self.observed
180 .iter()
181 .copied()
182 .filter(|target| entry_reachable.contains(target.0 as usize))
183 .map(|target| (target, Exposure::NamespaceObject)),
184 )
185 }
186}
187
188pub(in crate::graph) struct ExposedNamespaceTargets {
195 members: FxHashMap<FileId, Exposure>,
196}
197
198impl ExposedNamespaceTargets {
199 pub(in crate::graph) fn is_empty(&self) -> bool {
201 self.members.is_empty()
202 }
203
204 pub(in crate::graph) fn exposes_name(&self, file_id: FileId, exported_name: &str) -> bool {
211 match self.members.get(&file_id) {
212 Some(Exposure::NamespaceObject) => true,
213 Some(Exposure::StarSurface) => exported_name != "default",
214 None => false,
215 }
216 }
217
218 fn files(&self) -> impl Iterator<Item = FileId> + '_ {
224 self.members.keys().copied()
225 }
226
227 fn record(&mut self, stack: &mut Vec<(FileId, Exposure)>, file_id: FileId, exposure: Exposure) {
230 match self.members.entry(file_id) {
231 std::collections::hash_map::Entry::Occupied(mut slot) => {
232 if *slot.get() == Exposure::StarSurface && exposure == Exposure::NamespaceObject {
233 slot.insert(exposure);
234 stack.push((file_id, exposure));
235 }
236 }
237 std::collections::hash_map::Entry::Vacant(slot) => {
238 slot.insert(exposure);
239 stack.push((file_id, exposure));
240 }
241 }
242 }
243}
244
245fn is_namespace_re_export(re: &super::types::ReExportEdge) -> bool {
248 re.imported_name == "*" && re.exported_name != "*"
249}
250
251struct NameForwarders<'a> {
257 named: FxHashMap<(FileId, &'a str), Vec<(FileId, &'a str)>>,
260 stars: FxHashMap<FileId, Vec<FileId>>,
262}
263
264#[derive(Default)]
272struct NameSearchScratch<'a> {
273 visited: FxHashSet<(FileId, &'a str)>,
274 frontier: Vec<(FileId, &'a str)>,
275 failed: FxHashSet<(FileId, &'a str)>,
276}
277
278impl<'a> NameForwarders<'a> {
279 fn build(modules: &'a [super::types::ModuleNode]) -> Self {
280 let mut named: FxHashMap<(FileId, &'a str), Vec<(FileId, &'a str)>> = FxHashMap::default();
281 let mut stars: FxHashMap<FileId, Vec<FileId>> = FxHashMap::default();
282 for module in modules {
283 for re in &module.re_exports {
284 if re.imported_name == "*" {
285 if re.exported_name == "*" {
286 stars
287 .entry(re.source_file)
288 .or_default()
289 .push(module.file_id);
290 }
291 } else {
292 named
293 .entry((re.source_file, re.imported_name.as_str()))
294 .or_default()
295 .push((module.file_id, re.exported_name.as_str()));
296 }
297 }
298 }
299 Self { named, stars }
300 }
301}
302
303fn extend_forwarding_sources(
313 modules: &[super::types::ModuleNode],
314 may_reach: &mut FxHashSet<FileId>,
315 seeds: impl IntoIterator<Item = FileId>,
316) {
317 let mut stack: Vec<FileId> = seeds
318 .into_iter()
319 .filter(|seed| may_reach.insert(*seed))
320 .collect();
321 while let Some(barrel) = stack.pop() {
322 let Some(module) = modules.get(barrel.0 as usize) else {
323 continue;
324 };
325 for re in &module.re_exports {
326 if !is_namespace_re_export(re) && may_reach.insert(re.source_file) {
327 stack.push(re.source_file);
328 }
329 }
330 }
331}
332
333struct ExposedNameSearch<'a> {
343 forwarders: NameForwarders<'a>,
344 whole_object_names: FxHashMap<FileId, Vec<String>>,
349 may_reach: FxHashSet<FileId>,
357 scratch: NameSearchScratch<'a>,
358}
359
360impl<'a> ExposedNameSearch<'a> {
361 fn build(
362 modules: &'a [super::types::ModuleNode],
363 module_by_id: &FxHashMap<FileId, &ResolvedModule>,
364 ) -> Self {
365 let mut whole_object_names: FxHashMap<FileId, Vec<String>> = FxHashMap::default();
366 for consumer in module_by_id.values() {
367 if consumer.whole_object_uses.is_empty() {
368 continue;
369 }
370 for import in &consumer.resolved_imports {
371 let Some(target) = import.target.internal_file_id() else {
372 continue;
373 };
374 let imported_name = match &import.info.imported_name {
375 fallow_types::extract::ImportedName::Named(name) => name.as_str(),
376 fallow_types::extract::ImportedName::Default => "default",
377 _ => continue,
378 };
379 let local_name = import.info.local_name.as_str();
380 if local_name.is_empty()
381 || !consumer
382 .whole_object_uses
383 .iter()
384 .any(|used| used == local_name)
385 {
386 continue;
387 }
388 let names = whole_object_names.entry(target).or_default();
389 if !names.iter().any(|name| name == imported_name) {
390 names.push(imported_name.to_string());
391 }
392 }
393 }
394
395 let mut may_reach = FxHashSet::default();
396 extend_forwarding_sources(
397 modules,
398 &mut may_reach,
399 modules
400 .iter()
401 .filter(|m| m.is_entry_point())
402 .map(|m| m.file_id)
403 .chain(whole_object_names.keys().copied()),
404 );
405
406 Self {
407 forwarders: NameForwarders::build(modules),
408 whole_object_names,
409 may_reach,
410 scratch: NameSearchScratch::default(),
411 }
412 }
413
414 fn refresh(
421 &mut self,
422 modules: &'a [super::types::ModuleNode],
423 closure: &ExposedNamespaceTargets,
424 ) {
425 extend_forwarding_sources(
426 modules,
427 &mut self.may_reach,
428 closure.members.keys().copied(),
429 );
430 self.scratch.failed.clear();
431 }
432
433 fn reaches_exposure(
444 &mut self,
445 graph: &ModuleGraph,
446 closure: &ExposedNamespaceTargets,
447 file: FileId,
448 name: &'a str,
449 ) -> bool {
450 if !self.may_reach.contains(&file) || self.scratch.failed.contains(&(file, name)) {
451 return false;
452 }
453 let Self {
454 forwarders,
455 whole_object_names,
456 may_reach,
457 scratch,
458 } = self;
459 scratch.visited.clear();
460 scratch.frontier.clear();
461 scratch.visited.insert((file, name));
462 scratch.frontier.push((file, name));
463 while let Some((current, current_name)) = scratch.frontier.pop() {
464 if exposes_here(graph, closure, whole_object_names, current, current_name) {
465 return true;
466 }
467 if let Some(barrels) = forwarders.named.get(&(current, current_name)) {
468 for &(barrel, exported_name) in barrels {
469 if may_reach.contains(&barrel)
470 && graph.forwards_binding(current, current_name, barrel, exported_name)
471 && !scratch.failed.contains(&(barrel, exported_name))
472 && scratch.visited.insert((barrel, exported_name))
473 {
474 scratch.frontier.push((barrel, exported_name));
475 }
476 }
477 }
478 if current_name == "default" {
479 continue;
480 }
481 if let Some(barrels) = forwarders.stars.get(¤t) {
482 for &barrel in barrels {
483 if may_reach.contains(&barrel)
484 && graph.forwards_binding(current, current_name, barrel, current_name)
485 && !scratch.failed.contains(&(barrel, current_name))
486 && scratch.visited.insert((barrel, current_name))
487 {
488 scratch.frontier.push((barrel, current_name));
489 }
490 }
491 }
492 }
493 scratch.failed.extend(scratch.visited.iter().copied());
494 false
495 }
496}
497
498fn exposes_here(
505 graph: &ModuleGraph,
506 closure: &ExposedNamespaceTargets,
507 whole_object_names: &FxHashMap<FileId, Vec<String>>,
508 file: FileId,
509 name: &str,
510) -> bool {
511 graph.is_entry_point_file(file)
512 || closure.exposes_name(file, name)
513 || whole_object_names
514 .get(&file)
515 .is_some_and(|names| names.iter().any(|candidate| candidate == name))
516}
517
518struct ReExportFixpointInput<'a> {
519 re_export_info: &'a [ReExportTuple],
520 entry_star_targets: &'a FxHashSet<FileId>,
521 edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
522 module_by_id: &'a FxHashMap<FileId, &'a ResolvedModule>,
523 reference_paths: &'a mut ReferencePathInterner,
524}
525
526#[cfg(test)]
527struct LegacyReExportFullScan<'a> {
528 modules: &'a mut [super::types::ModuleNode],
529 edges: &'a [Edge],
530 re_export_info: &'a [ReExportTuple],
531 entry_star_targets: &'a FxHashSet<FileId>,
532 edges_by_target: &'a FxHashMap<FileId, Vec<usize>>,
533 module_by_id: &'a FxHashMap<FileId, &'a ResolvedModule>,
534 effective_exports: &'a super::effective_exports::EffectiveExportIndex,
535 reference_paths: &'a mut ReferencePathInterner,
536}
537
538struct ReExportPropagationPlan {
545 observers_by_module: FxHashMap<FileId, Vec<usize>>,
546 queue: VecDeque<usize>,
547 enqueued: Vec<bool>,
548}
549
550impl ReExportPropagationPlan {
551 fn new(re_export_info: &[ReExportTuple]) -> Self {
552 let mut observers_by_module: FxHashMap<FileId, Vec<usize>> = FxHashMap::default();
553 for (idx, entry) in re_export_info.iter().enumerate() {
554 observers_by_module
555 .entry(entry.barrel)
556 .or_default()
557 .push(idx);
558 }
559
560 Self {
561 observers_by_module,
562 queue: (0..re_export_info.len()).collect(),
563 enqueued: vec![true; re_export_info.len()],
564 }
565 }
566
567 fn pop_front(&mut self) -> Option<usize> {
568 let idx = self.queue.pop_front()?;
569 self.enqueued[idx] = false;
570 Some(idx)
571 }
572
573 fn enqueue_observers(&mut self, changed_module: FileId) {
574 let Some(observers) = self.observers_by_module.get(&changed_module) else {
575 return;
576 };
577 for &idx in observers {
578 if !self.enqueued[idx] {
579 self.enqueued[idx] = true;
580 self.queue.push_back(idx);
581 }
582 }
583 }
584}
585
586impl ModuleGraph {
587 pub(super) fn resolve_re_export_chains(
596 &mut self,
597 module_by_id: &FxHashMap<FileId, &ResolvedModule>,
598 exposed_namespace_targets: &ExposedNamespaceTargets,
599 reference_paths: &mut ReferencePathInterner,
600 ) -> Vec<GraphReExportCycle> {
601 let re_export_info = self.collect_re_export_tuples();
602
603 if re_export_info.is_empty() {
604 return Vec::new();
605 }
606
607 let cycles = find_re_export_cycles(&self.modules, &re_export_info);
608
609 let entry_star_targets = self.collect_entry_star_targets(exposed_namespace_targets);
610 let edges_by_target = self.build_edges_by_target();
611
612 self.run_re_export_fixpoint(ReExportFixpointInput {
613 re_export_info: &re_export_info,
614 entry_star_targets: &entry_star_targets,
615 edges_by_target: &edges_by_target,
616 module_by_id,
617 reference_paths,
618 });
619
620 cycles
621 }
622
623 fn collect_re_export_tuples(&self) -> Vec<ReExportTuple> {
630 let asset_only = self.asset_only_modules();
631 self.modules
632 .iter()
633 .filter(|m| !asset_only.contains(m.file_id.0 as usize))
634 .flat_map(|m| {
635 m.re_exports.iter().map(move |re| ReExportTuple {
636 barrel: m.file_id,
637 source: re.source_file,
638 imported_name: re.imported_name.clone(),
639 exported_name: re.exported_name.clone(),
640 is_type_only: re.is_type_only,
641 })
642 })
643 .collect()
644 }
645
646 fn asset_only_modules(&self) -> FixedBitSet {
649 let total = self.modules.len();
650 let mut asset_loaded = FixedBitSet::with_capacity(total);
651 let mut run_loaded = FixedBitSet::with_capacity(total);
652 for edge in &self.edges {
653 let target = edge.target.0 as usize;
654 if target >= total {
655 continue;
656 }
657 if edge.runs_target_code() {
658 run_loaded.insert(target);
659 } else {
660 asset_loaded.insert(target);
661 }
662 }
663 asset_loaded.difference_with(&run_loaded);
664 for module in &self.modules {
665 if module.is_entry_point() {
666 asset_loaded.set(module.file_id.0 as usize, false);
667 }
668 }
669 asset_loaded
670 }
671
672 fn collect_entry_star_targets(
678 &self,
679 exposed_namespace_targets: &ExposedNamespaceTargets,
680 ) -> FxHashSet<FileId> {
681 let mut entry_star_targets: FxHashSet<FileId> = exposed_namespace_targets.files().collect();
682 entry_star_targets.extend(self.modules.iter().filter(|m| m.is_entry_point()).flat_map(
683 |m| {
684 m.re_exports
685 .iter()
686 .filter(|re| re.exported_name == "*")
687 .map(|re| re.source_file)
688 },
689 ));
690 self.extend_plain_star_closure(&mut entry_star_targets);
691 entry_star_targets
692 }
693
694 pub(in crate::graph) fn collect_exposed_namespace_targets(
741 &self,
742 whole_module_targets: &WholeModuleObservations,
743 entry_reachable: &FixedBitSet,
744 module_by_id: &FxHashMap<FileId, &ResolvedModule>,
745 ) -> ExposedNamespaceTargets {
746 let mut closure = ExposedNamespaceTargets {
747 members: FxHashMap::default(),
748 };
749 let mut stack: Vec<(FileId, Exposure)> = Vec::new();
750 for (seed, exposure) in whole_module_targets.seeds(entry_reachable) {
751 closure.record(&mut stack, seed, exposure);
752 }
753
754 let mut pending: Vec<(FileId, &str, FileId)> = self
755 .modules
756 .iter()
757 .flat_map(|m| {
758 m.re_exports
759 .iter()
760 .filter(|re| is_namespace_re_export(re))
761 .map(move |re| (m.file_id, re.exported_name.as_str(), re.source_file))
762 })
763 .filter(|(_, _, source)| entry_reachable.contains(source.0 as usize))
764 .collect();
765 let mut search =
766 (!pending.is_empty()).then(|| ExposedNameSearch::build(&self.modules, module_by_id));
767
768 loop {
769 self.extend_exposure_walk(&mut closure, &mut stack);
770 let Some(search) = search.as_mut() else { break };
771 if pending.is_empty() {
772 break;
773 }
774 search.refresh(&self.modules, &closure);
775 let mut widened = false;
776 let mut still_pending = Vec::with_capacity(pending.len());
777 for (barrel, exported_name, source) in std::mem::take(&mut pending) {
778 if closure.members.get(&source) == Some(&Exposure::NamespaceObject) {
779 continue;
780 }
781 if search.reaches_exposure(self, &closure, barrel, exported_name) {
782 closure.record(&mut stack, source, Exposure::NamespaceObject);
783 widened = true;
784 } else {
785 still_pending.push((barrel, exported_name, source));
786 }
787 }
788 pending = still_pending;
789 if !widened {
790 break;
791 }
792 }
793 closure
794 }
795
796 fn extend_exposure_walk(
804 &self,
805 closure: &mut ExposedNamespaceTargets,
806 stack: &mut Vec<(FileId, Exposure)>,
807 ) {
808 while let Some((file_id, exposure)) = stack.pop() {
809 let Some(module) = self.modules.get(file_id.0 as usize) else {
810 continue;
811 };
812 for re in &module.re_exports {
813 if re.imported_name != "*" {
814 continue;
815 }
816 let next = if re.exported_name == "*" {
817 Exposure::StarSurface
818 } else if exposure == Exposure::NamespaceObject || re.exported_name != "default" {
819 Exposure::NamespaceObject
820 } else {
821 continue;
822 };
823 closure.record(stack, re.source_file, next);
824 }
825 }
826 }
827
828 fn forwards_binding(
838 &self,
839 source: FileId,
840 source_name: &str,
841 barrel: FileId,
842 barrel_name: &str,
843 ) -> bool {
844 for namespace in [super::ExportNamespace::Value, super::ExportNamespace::Type] {
845 if !matches!(
846 self.resolve_export(source, source_name, namespace),
847 super::EffectiveExportResolution::Unique(_)
848 ) {
849 continue;
850 }
851 return super::namespace_indexes::uniquely_forwards_binding(
852 self,
853 source,
854 source_name,
855 barrel,
856 barrel_name,
857 namespace,
858 );
859 }
860 false
861 }
862
863 fn is_entry_point_file(&self, file_id: FileId) -> bool {
865 self.modules
866 .get(file_id.0 as usize)
867 .is_some_and(super::types::ModuleNode::is_entry_point)
868 }
869
870 fn extend_plain_star_closure(&self, targets: &mut FxHashSet<FileId>) {
873 let mut stack: Vec<FileId> = targets.iter().copied().collect();
874 while let Some(file_id) = stack.pop() {
875 let Some(module) = self.modules.get(file_id.0 as usize) else {
876 continue;
877 };
878 for re in module
879 .re_exports
880 .iter()
881 .filter(|re| re.imported_name == "*" && re.exported_name == "*")
882 {
883 if targets.insert(re.source_file) {
884 stack.push(re.source_file);
885 }
886 }
887 }
888 }
889
890 fn build_edges_by_target(&self) -> FxHashMap<FileId, Vec<usize>> {
892 let mut edges_by_target: FxHashMap<FileId, Vec<usize>> = FxHashMap::default();
893 for (idx, edge) in self.edges.iter().enumerate() {
894 edges_by_target.entry(edge.target).or_default().push(idx);
895 }
896 edges_by_target
897 }
898
899 fn run_re_export_fixpoint(&mut self, input: ReExportFixpointInput<'_>) {
901 let ReExportFixpointInput {
902 re_export_info,
903 entry_star_targets,
904 edges_by_target,
905 module_by_id,
906 reference_paths,
907 } = input;
908 #[cfg(test)]
909 let mut legacy_modules: Option<Vec<super::types::ModuleNode>> = DIFFERENTIAL_CHECK_ENABLED
910 .with(|enabled| {
911 enabled.get().then(|| {
912 serde_json::from_value(
913 serde_json::to_value(&self.modules)
914 .expect("module graph should serialize for differential testing"),
915 )
916 .expect("module graph should deserialize for differential testing")
917 })
918 });
919
920 let safety_cap = self.re_export_transition_safety_cap(re_export_info);
921 let mut processed = 0usize;
922 let mut plan = ReExportPropagationPlan::new(re_export_info);
923 let mut existing_refs: FxHashSet<RoutedReferenceKey> = FxHashSet::default();
924 let mut synthetic_stubs: FxHashSet<(FileId, String, bool)> = FxHashSet::default();
925 let binding_usage = ImportBindingUsageIndex::build(module_by_id);
926 let mut declaration_routes = EffectiveDeclarationRouteCache::default();
927 let mut scratch = NamedPropagationScratch::default();
928 let mut named_star_refs = NamedStarRefCache::default();
929
930 while let Some(entry_idx) = plan.pop_front() {
931 if processed >= safety_cap {
932 tracing::error!(
933 processed,
934 safety_cap,
935 re_export_edges = re_export_info.len(),
936 "Re-export propagation exceeded its finite-state safety cap; \
937 propagation may be non-monotonic. Please file a bug at \
938 https://github.com/fallow-rs/fallow/issues with the repro."
939 );
940 break;
941 }
942 processed += 1;
943
944 let mut context = ReExportContext {
945 entry_star_targets,
946 edges_by_target,
947 binding_usage: &binding_usage,
948 effective_exports: &self.effective_exports,
949 existing_refs: &mut existing_refs,
950 synthetic_stubs: &mut synthetic_stubs,
951 declaration_routes: &mut declaration_routes,
952 scratch: &mut scratch,
953 reference_paths,
954 named_star_refs: &mut named_star_refs,
955 };
956
957 let entry = &re_export_info[entry_idx];
958 #[cfg(test)]
959 record_propagation_visit(entry);
960 if Self::propagate_re_export_entry(&mut self.modules, &self.edges, entry, &mut context)
961 {
962 plan.enqueue_observers(entry.source);
963 }
964 }
965
966 #[cfg(test)]
967 if let Some(legacy_modules) = legacy_modules.as_mut() {
968 propagate::without_star_source_filter(|| {
971 Self::run_re_export_full_scan(LegacyReExportFullScan {
972 modules: legacy_modules,
973 edges: &self.edges,
974 re_export_info,
975 entry_star_targets,
976 edges_by_target,
977 module_by_id,
978 effective_exports: &self.effective_exports,
979 reference_paths,
980 });
981 });
982 assert_eq!(
983 serde_json::to_value(legacy_modules)
984 .expect("legacy module graph should serialize for comparison"),
985 serde_json::to_value(&self.modules)
986 .expect("queue module graph should serialize for comparison"),
987 "work-queue propagation must match the legacy full-scan fixpoint"
988 );
989 }
990 }
991
992 fn re_export_transition_safety_cap(&self, re_export_info: &[ReExportTuple]) -> usize {
995 let initial_exports = self
996 .modules
997 .iter()
998 .map(|module| module.exports.len())
999 .sum::<usize>();
1000 let named_inputs = self
1001 .edges
1002 .iter()
1003 .flat_map(|edge| &edge.symbols)
1004 .filter(|symbol| {
1005 matches!(
1006 &symbol.imported_name,
1007 fallow_types::extract::ImportedName::Named(_)
1008 )
1009 })
1010 .count()
1011 .saturating_add(initial_exports)
1012 .saturating_add(re_export_info.len());
1013
1014 let module_count = self.modules.len();
1015 let synthetic_export_hosts = self
1016 .modules
1017 .iter()
1018 .filter(|module| {
1019 module
1020 .re_exports
1021 .iter()
1022 .any(|re_export| re_export.exported_name == "*")
1023 })
1024 .count();
1025 let synthetic_exports = synthetic_export_hosts
1026 .saturating_mul(named_inputs)
1027 .saturating_mul(2);
1028 let max_exports = initial_exports.saturating_add(synthetic_exports);
1029 let reference_additions = max_exports.saturating_mul(module_count).saturating_mul(2);
1030 let state_changes = synthetic_exports.saturating_add(reference_additions);
1031
1032 re_export_info
1033 .len()
1034 .saturating_add(state_changes.saturating_mul(re_export_info.len()))
1035 .max(re_export_info.len())
1036 }
1037
1038 fn propagate_re_export_entry(
1040 modules: &mut [super::types::ModuleNode],
1041 edges: &[Edge],
1042 entry: &ReExportTuple,
1043 context: &mut ReExportContext<'_>,
1044 ) -> bool {
1045 let barrel_idx = entry.barrel.0 as usize;
1046 let source_idx = entry.source.0 as usize;
1047
1048 if barrel_idx >= modules.len() || source_idx >= modules.len() {
1049 return false;
1050 }
1051
1052 if entry.exported_name == "*" {
1053 propagate_star_re_export(StarReExportPropagation {
1054 modules,
1055 edges,
1056 edges_by_target: context.edges_by_target,
1057 binding_usage: context.binding_usage,
1058 effective_exports: context.effective_exports,
1059 barrel_id: entry.barrel,
1060 barrel_idx,
1061 source_id: entry.source,
1062 source_idx,
1063 entry_star_targets: context.entry_star_targets,
1064 triggering_is_type_only: entry.is_type_only,
1065 synthetic_stubs: context.synthetic_stubs,
1066 reference_paths: context.reference_paths,
1067 named_star_refs: context.named_star_refs,
1068 })
1069 } else {
1070 propagate_named_re_export(NamedReExportPropagation {
1071 modules,
1072 effective_exports: context.effective_exports,
1073 barrel_id: entry.barrel,
1074 barrel_idx,
1075 source_id: entry.source,
1076 source_idx,
1077 imported_name: &entry.imported_name,
1078 exported_name: &entry.exported_name,
1079 is_type_only: entry.is_type_only,
1080 existing_refs: context.existing_refs,
1081 declaration_routes: context.declaration_routes,
1082 scratch: context.scratch,
1083 reference_paths: context.reference_paths,
1084 })
1085 }
1086 }
1087
1088 #[cfg(test)]
1089 fn run_re_export_full_scan(input: LegacyReExportFullScan<'_>) {
1090 let LegacyReExportFullScan {
1091 modules,
1092 edges,
1093 re_export_info,
1094 entry_star_targets,
1095 edges_by_target,
1096 module_by_id,
1097 effective_exports,
1098 reference_paths,
1099 } = input;
1100 let max_iterations = re_export_info.len().saturating_add(1);
1101 let mut existing_refs: FxHashSet<RoutedReferenceKey> = FxHashSet::default();
1102 let mut synthetic_stubs: FxHashSet<(FileId, String, bool)> = FxHashSet::default();
1103 let binding_usage = ImportBindingUsageIndex::build(module_by_id);
1104 let mut declaration_routes = EffectiveDeclarationRouteCache::default();
1105 let mut scratch = NamedPropagationScratch::default();
1106
1107 for _ in 0..max_iterations {
1108 let mut changed = false;
1109 for entry in re_export_info {
1110 let mut context = ReExportContext {
1111 entry_star_targets,
1112 edges_by_target,
1113 binding_usage: &binding_usage,
1114 effective_exports,
1115 existing_refs: &mut existing_refs,
1116 synthetic_stubs: &mut synthetic_stubs,
1117 declaration_routes: &mut declaration_routes,
1118 scratch: &mut scratch,
1119 reference_paths,
1120 named_star_refs: &mut NamedStarRefCache::default(),
1123 };
1124 changed |= Self::propagate_re_export_entry(modules, edges, entry, &mut context);
1125 }
1126 if !changed {
1127 break;
1128 }
1129 }
1130 }
1131}
1132
1133fn find_re_export_cycles(
1142 modules: &[super::types::ModuleNode],
1143 re_export_info: &[ReExportTuple],
1144) -> Vec<GraphReExportCycle> {
1145 let mut cycles: Vec<GraphReExportCycle> = Vec::new();
1146
1147 let (node_index, nodes) = build_re_export_node_index(re_export_info);
1148 let n = nodes.len();
1149 if n == 0 {
1150 return cycles;
1151 }
1152
1153 let adj = build_re_export_adjacency(re_export_info, &node_index, modules, &mut cycles);
1154
1155 let sccs = tarjan_scc(n, &adj);
1156
1157 for scc in &sccs {
1158 cycles.push(build_multi_node_cycle(scc, &nodes, modules));
1159 }
1160
1161 cycles
1162}
1163
1164fn build_re_export_node_index(
1166 re_export_info: &[ReExportTuple],
1167) -> (FxHashMap<FileId, usize>, Vec<FileId>) {
1168 let mut node_index: FxHashMap<FileId, usize> = FxHashMap::default();
1169 let mut nodes: Vec<FileId> = Vec::new();
1170 for entry in re_export_info {
1171 for &id in &[entry.barrel, entry.source] {
1172 node_index.entry(id).or_insert_with(|| {
1173 let idx = nodes.len();
1174 nodes.push(id);
1175 idx
1176 });
1177 }
1178 }
1179 (node_index, nodes)
1180}
1181
1182fn build_re_export_adjacency(
1185 re_export_info: &[ReExportTuple],
1186 node_index: &FxHashMap<FileId, usize>,
1187 modules: &[super::types::ModuleNode],
1188 cycles: &mut Vec<GraphReExportCycle>,
1189) -> Vec<Vec<usize>> {
1190 let mut adj: Vec<Vec<usize>> = vec![Vec::new(); node_index.len()];
1191 let mut seen_edge: FxHashSet<(usize, usize)> = FxHashSet::default();
1192 let mut seen_self_loop: FxHashSet<FileId> = FxHashSet::default();
1193 for entry in re_export_info {
1194 let from = node_index[&entry.barrel];
1195 let to = node_index[&entry.source];
1196 if from == to {
1197 if seen_self_loop.insert(entry.barrel) {
1198 cycles.push(build_self_loop_cycle(entry.barrel, modules));
1199 }
1200 continue;
1201 }
1202 if seen_edge.insert((from, to)) {
1203 adj[from].push(to);
1204 }
1205 }
1206 adj
1207}
1208
1209fn build_self_loop_cycle(
1211 barrel: FileId,
1212 modules: &[super::types::ModuleNode],
1213) -> GraphReExportCycle {
1214 let (path_buf, path_display) = module_path_and_display(barrel, modules);
1215 tracing::warn!(
1216 file = path_display.as_str(),
1217 "Re-export self-loop detected: this file re-exports from \
1218 itself. Chain propagation is structurally a no-op for \
1219 these edges. Inspect the barrel for an accidental \
1220 `export * from './<this-file>'` after a rename or move."
1221 );
1222 GraphReExportCycle {
1223 files: vec![path_buf],
1224 file_ids: vec![barrel],
1225 is_self_loop: true,
1226 }
1227}
1228
1229fn build_multi_node_cycle(
1231 scc: &[usize],
1232 nodes: &[FileId],
1233 modules: &[super::types::ModuleNode],
1234) -> GraphReExportCycle {
1235 let mut triples: Vec<(PathBuf, String, FileId)> = scc
1236 .iter()
1237 .map(|&idx| {
1238 let file_id = nodes[idx];
1239 let (path, display) = module_path_and_display(file_id, modules);
1240 (path, display, file_id)
1241 })
1242 .collect();
1243 triples.sort_by(|a, b| a.1.cmp(&b.1));
1244 let members = triples
1245 .iter()
1246 .map(|(_, d, _)| d.as_str())
1247 .collect::<Vec<_>>()
1248 .join(" <-> ");
1249 tracing::warn!(
1250 target: fallow_types::ANALYSIS_DIAGNOSTIC_LOG_TARGET,
1251 cycle_size = scc.len(),
1252 members = members.as_str(),
1253 "Re-export cycle detected: chain propagation may be incomplete \
1254 for symbols on this barrel loop. Break the cycle to restore \
1255 full reachability analysis."
1256 );
1257 let (files, file_ids) = triples.into_iter().fold(
1258 (Vec::new(), Vec::new()),
1259 |(mut paths, mut ids), (p, _, id)| {
1260 paths.push(p);
1261 ids.push(id);
1262 (paths, ids)
1263 },
1264 );
1265 GraphReExportCycle {
1266 files,
1267 file_ids,
1268 is_self_loop: false,
1269 }
1270}
1271
1272fn module_path_and_display(
1275 file_id: FileId,
1276 modules: &[super::types::ModuleNode],
1277) -> (PathBuf, String) {
1278 let i = file_id.0 as usize;
1279 if i < modules.len() {
1280 let p = modules[i].path.clone();
1281 let d = p.display().to_string();
1282 (p, d)
1283 } else {
1284 let placeholder = format!("<file id {i}>");
1285 (PathBuf::from(&placeholder), placeholder)
1286 }
1287}
1288
1289struct TarjanFrame {
1290 node: usize,
1291 next_succ: usize,
1292}
1293
1294struct TarjanState {
1296 index_counter: u32,
1297 indices: Vec<u32>,
1298 lowlinks: Vec<u32>,
1299 on_stack: fixedbitset::FixedBitSet,
1300 stack: Vec<usize>,
1301 sccs: Vec<Vec<usize>>,
1302}
1303
1304impl TarjanState {
1305 fn new(n: usize) -> Self {
1306 Self {
1307 index_counter: 0,
1308 indices: vec![u32::MAX; n],
1309 lowlinks: vec![0; n],
1310 on_stack: fixedbitset::FixedBitSet::with_capacity(n),
1311 stack: Vec::new(),
1312 sccs: Vec::new(),
1313 }
1314 }
1315
1316 fn discover(&mut self, node: usize) {
1318 self.indices[node] = self.index_counter;
1319 self.lowlinks[node] = self.index_counter;
1320 self.index_counter = self.index_counter.saturating_add(1);
1321 self.stack.push(node);
1322 self.on_stack.insert(node);
1323 }
1324
1325 fn step_successor(&mut self, frame: &mut TarjanFrame, adj: &[Vec<usize>]) -> Option<usize> {
1328 let v = frame.node;
1329 let w = adj[v][frame.next_succ];
1330 frame.next_succ = frame.next_succ.saturating_add(1);
1331 if self.indices[w] == u32::MAX {
1332 self.discover(w);
1333 Some(w)
1334 } else {
1335 if self.on_stack.contains(w) {
1336 self.lowlinks[v] = self.lowlinks[v].min(self.indices[w]);
1337 }
1338 None
1339 }
1340 }
1341
1342 fn finish_frame(&mut self, v: usize, parent: Option<usize>) {
1349 if self.lowlinks[v] == self.indices[v] {
1350 if self.stack.last() == Some(&v) {
1351 self.stack.pop();
1352 self.on_stack.remove(v);
1353 } else {
1354 let mut scc = Vec::new();
1355 while let Some(w) = self.stack.pop() {
1356 self.on_stack.remove(w);
1357 scc.push(w);
1358 if w == v {
1359 break;
1360 }
1361 }
1362 self.sccs.push(scc);
1363 }
1364 }
1365 if let Some(pv) = parent {
1366 self.lowlinks[pv] = self.lowlinks[pv].min(self.lowlinks[v]);
1367 }
1368 }
1369}
1370
1371fn tarjan_scc(n: usize, adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
1375 let mut state = TarjanState::new(n);
1376
1377 for start in 0..n {
1378 if state.indices[start] != u32::MAX {
1379 continue;
1380 }
1381 state.discover(start);
1382 let mut dfs: Vec<TarjanFrame> = vec![TarjanFrame {
1383 node: start,
1384 next_succ: 0,
1385 }];
1386
1387 while let Some(frame) = dfs.last_mut() {
1388 let v = frame.node;
1389 if frame.next_succ < adj[v].len() {
1390 if let Some(child) = state.step_successor(frame, adj) {
1391 dfs.push(TarjanFrame {
1392 node: child,
1393 next_succ: 0,
1394 });
1395 }
1396 } else {
1397 dfs.pop();
1398 state.finish_frame(v, dfs.last().map(|parent| parent.node));
1399 }
1400 }
1401 }
1402
1403 state.sccs
1404}