fallow_graph/graph/
ambiguity.rs

1//! Star-export collisions and the declarations that participate in them.
2//!
3//! When two different `export *` sources supply the same name, ECMA-262
4//! ResolveExport returns `ambiguous` and the barrel does not export the name at
5//! all. The effective export index records that as
6//! [`EffectiveExportResolution::Ambiguous`] and every consumer abstains, which
7//! leaves the contributing declarations with no credit and no explanation. This
8//! module turns the abstention into data: which barrel collides on which name,
9//! and which declarations lost their credit to it.
10
11use rustc_hash::{FxHashMap, FxHashSet};
12
13use fallow_types::discover::FileId;
14
15use super::{EffectiveExportBinding, EffectiveExportResolution, ExportNamespace, ModuleGraph};
16
17/// One `export *` collision on a barrel module.
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct AmbiguousStarExport {
20    /// The barrel whose star sources collide on this name.
21    pub barrel: FileId,
22    /// The colliding exported name.
23    pub name: Box<str>,
24    /// The namespace the collision occurs in.
25    pub namespace: ExportNamespace,
26    /// Files declaring a colliding declaration, sorted and deduplicated.
27    pub contributors: Box<[FileId]>,
28}
29
30/// Declarations whose export credit is lost to a star-export collision.
31///
32/// A participant is neither used nor provably dead: the barrel that would carry
33/// its credit exports nothing under that name. Detectors abstain from reporting
34/// participants rather than attributing a barrel mistake to the source files.
35/// Names identify the canonical defining declaration, so a re-export alias such
36/// as `default as Widget` records `default` on the component file.
37#[derive(Debug, Default)]
38pub struct AmbiguityParticipants {
39    names_by_file: FxHashMap<(FileId, ExportNamespace), FxHashSet<Box<str>>>,
40}
41
42impl AmbiguityParticipants {
43    /// Whether this declaration lost its credit to a star-export collision in
44    /// one specific namespace.
45    #[must_use]
46    pub fn contains_in_namespace(
47        &self,
48        file_id: FileId,
49        name: &str,
50        namespace: ExportNamespace,
51    ) -> bool {
52        self.names_by_file
53            .get(&(file_id, namespace))
54            .is_some_and(|names| names.contains(name))
55    }
56
57    /// Whether an exported declaration lost its credit in any namespace it
58    /// occupies.
59    ///
60    /// A plain value declaration also occupies type space: `class` and `enum`
61    /// carry a type meaning, and a `export type *` barrel collides on that
62    /// meaning alone while the value namespace stays clean. Such a declaration
63    /// has lost its credit just as thoroughly as a value-space participant.
64    #[must_use]
65    pub fn contains_declaration(&self, file_id: FileId, name: &str, is_type_only: bool) -> bool {
66        self.contains_in_namespace(file_id, name, ExportNamespace::Type)
67            || (!is_type_only && self.contains_in_namespace(file_id, name, ExportNamespace::Value))
68    }
69}
70
71impl ModuleGraph {
72    /// Every `export *` collision in the project, sorted deterministically.
73    #[must_use]
74    pub fn ambiguous_star_exports(&self) -> Vec<AmbiguousStarExport> {
75        if !self.has_star_re_exports() {
76            return Vec::new();
77        }
78        self.collect_ambiguous_star_exports(self.effective_exports.ambiguous_names())
79    }
80
81    /// `export *` collisions on one module, for single-symbol queries.
82    #[must_use]
83    pub fn ambiguous_star_exports_on(&self, file_id: FileId) -> Vec<AmbiguousStarExport> {
84        if !self.has_star_re_exports() {
85            return Vec::new();
86        }
87        self.collect_ambiguous_star_exports(self.effective_exports.ambiguous_names_on(file_id))
88    }
89
90    /// Declarations that lost export credit to a collision anywhere in the project.
91    #[must_use]
92    pub fn ambiguity_participants(&self) -> AmbiguityParticipants {
93        if !self.has_star_re_exports() {
94            return AmbiguityParticipants::default();
95        }
96
97        let mut participants = AmbiguityParticipants::default();
98        for (barrel, name, namespace) in self.effective_exports.ambiguous_names() {
99            for binding in self.star_contributor_bindings(barrel, name, namespace) {
100                let declaration = self
101                    .export_binding_origin(binding)
102                    .map(|origin| {
103                        (
104                            origin.file_id(),
105                            Box::<str>::from(origin.export().name.to_string()),
106                        )
107                    })
108                    .or_else(|| {
109                        binding
110                            .is_implicit_default()
111                            .then(|| (binding.origin_file(), Box::<str>::from("default")))
112                    });
113                let Some((file_id, declaration_name)) = declaration else {
114                    continue;
115                };
116                participants
117                    .names_by_file
118                    .entry((file_id, namespace))
119                    .or_default()
120                    .insert(declaration_name);
121            }
122        }
123        participants
124    }
125
126    fn collect_ambiguous_star_exports(
127        &self,
128        ambiguous: Vec<(FileId, &str, ExportNamespace)>,
129    ) -> Vec<AmbiguousStarExport> {
130        let mut collisions: Vec<AmbiguousStarExport> = ambiguous
131            .into_iter()
132            .filter_map(|(barrel, name, namespace)| {
133                let contributors = self.star_contributors(barrel, name, namespace);
134                (!contributors.is_empty()).then(|| AmbiguousStarExport {
135                    barrel,
136                    name: Box::from(name),
137                    namespace,
138                    contributors,
139                })
140            })
141            .collect();
142        collisions.sort_by(|left, right| {
143            (left.barrel.0, &left.name, namespace_order(left.namespace)).cmp(&(
144                right.barrel.0,
145                &right.name,
146                namespace_order(right.namespace),
147            ))
148        });
149        collisions
150    }
151
152    fn has_star_re_exports(&self) -> bool {
153        self.modules
154            .iter()
155            .any(|module| module.re_exports.iter().any(is_star_re_export))
156    }
157
158    /// Files declaring a colliding declaration reachable from `barrel`.
159    ///
160    /// A star source that is itself ambiguous forwards the collision, so the
161    /// walk descends into it to reach the declarations that actually lost
162    /// credit. Star graphs may contain cycles, hence the visited set.
163    fn star_contributors(
164        &self,
165        barrel: FileId,
166        name: &str,
167        namespace: ExportNamespace,
168    ) -> Box<[FileId]> {
169        let mut contributors: Vec<FileId> = self
170            .star_contributor_bindings(barrel, name, namespace)
171            .into_iter()
172            .map(|binding| binding.origin_file())
173            .collect();
174        contributors.sort_unstable_by_key(|file_id| file_id.0);
175        contributors.dedup();
176        contributors.into_boxed_slice()
177    }
178
179    /// Canonical bindings supplied by the star sources for one ambiguous name.
180    fn star_contributor_bindings(
181        &self,
182        barrel: FileId,
183        name: &str,
184        namespace: ExportNamespace,
185    ) -> FxHashSet<EffectiveExportBinding> {
186        if name == "default" {
187            return FxHashSet::default();
188        }
189        let mut contributors: FxHashSet<EffectiveExportBinding> = FxHashSet::default();
190        let mut visited: FxHashSet<FileId> = FxHashSet::from_iter([barrel]);
191        let mut pending = vec![barrel];
192        while let Some(current) = pending.pop() {
193            let Some(module) = self.modules.get(current.0 as usize) else {
194                continue;
195            };
196            for re_export in module.re_exports.iter().filter(|re| is_star_re_export(re)) {
197                if namespace == ExportNamespace::Value && re_export.is_type_only {
198                    continue;
199                }
200                let source = re_export.source_file;
201                if !visited.insert(source) {
202                    continue;
203                }
204                match self.resolve_export(source, name, namespace) {
205                    EffectiveExportResolution::Unique(binding) => {
206                        contributors.insert(binding);
207                    }
208                    EffectiveExportResolution::Ambiguous => pending.push(source),
209                    EffectiveExportResolution::Missing => {}
210                }
211            }
212        }
213        contributors
214    }
215}
216
217fn is_star_re_export(re_export: &super::ReExportEdge) -> bool {
218    re_export.imported_name == "*" && re_export.exported_name == "*"
219}
220
221const fn namespace_order(namespace: ExportNamespace) -> u8 {
222    match namespace {
223        ExportNamespace::Type => 0,
224        ExportNamespace::Value => 1,
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use std::path::PathBuf;
231
232    use fallow_types::discover::DiscoveredFile;
233    use fallow_types::extract::{ExportInfo, ExportName, ReExportInfo, VisibilityTag};
234
235    use super::{AmbiguousStarExport, ExportNamespace, FileId, ModuleGraph};
236    use crate::resolve::{ResolveResult, ResolvedModule, ResolvedReExport};
237
238    fn value_export(name: &str) -> ExportInfo {
239        ExportInfo {
240            name: ExportName::Named(name.to_string()),
241            local_name: Some(name.to_string()),
242            is_type_only: false,
243            visibility: VisibilityTag::None,
244            expected_unused_reason: None,
245            span: oxc_span::Span::default(),
246            members: vec![],
247            is_side_effect_used: false,
248            super_class: None,
249            deprecated: false,
250            deprecated_reason: None,
251        }
252    }
253
254    fn default_export() -> ExportInfo {
255        ExportInfo {
256            name: ExportName::Default,
257            local_name: Some("Component".to_string()),
258            is_type_only: false,
259            visibility: VisibilityTag::None,
260            expected_unused_reason: None,
261            span: oxc_span::Span::default(),
262            members: vec![],
263            is_side_effect_used: false,
264            super_class: None,
265            deprecated: false,
266            deprecated_reason: None,
267        }
268    }
269
270    fn star_re_export(target: u32) -> ResolvedReExport {
271        ResolvedReExport {
272            info: ReExportInfo {
273                source: format!("./module-{target}"),
274                imported_name: "*".to_string(),
275                exported_name: "*".to_string(),
276                is_type_only: false,
277                span: oxc_span::Span::default(),
278                statement_span: oxc_span::Span::default(),
279                source_span: oxc_span::Span::default(),
280            },
281            target: ResolveResult::InternalModule(FileId(target)),
282        }
283    }
284
285    fn type_only_star_re_export(target: u32) -> ResolvedReExport {
286        let mut re_export = star_re_export(target);
287        re_export.info.is_type_only = true;
288        re_export
289    }
290
291    fn named_re_export(target: u32, imported_name: &str, exported_name: &str) -> ResolvedReExport {
292        ResolvedReExport {
293            info: ReExportInfo {
294                source: format!("./module-{target}"),
295                imported_name: imported_name.to_string(),
296                exported_name: exported_name.to_string(),
297                is_type_only: false,
298                span: oxc_span::Span::default(),
299                statement_span: oxc_span::Span::default(),
300                source_span: oxc_span::Span::default(),
301            },
302            target: ResolveResult::InternalModule(FileId(target)),
303        }
304    }
305
306    /// Barrel 0 `export type *`s 1 and 2, which both export `class Foo`.
307    ///
308    /// The collision exists only in the type-fallback lane: the type-only star
309    /// drops the value lane and neither source declares a real type.
310    fn type_only_colliding_star_graph() -> ModuleGraph {
311        let files: Vec<_> = (0..3)
312            .map(|index| DiscoveredFile {
313                id: FileId(index),
314                path: PathBuf::from(format!("/project/module-{index}.ts")),
315                size_bytes: 10,
316            })
317            .collect();
318        let modules = vec![
319            ResolvedModule {
320                file_id: FileId(0),
321                path: files[0].path.clone(),
322                re_exports: vec![type_only_star_re_export(1), type_only_star_re_export(2)],
323                ..Default::default()
324            },
325            ResolvedModule {
326                file_id: FileId(1),
327                path: files[1].path.clone(),
328                exports: vec![value_export("Foo")].into(),
329                ..Default::default()
330            },
331            ResolvedModule {
332                file_id: FileId(2),
333                path: files[2].path.clone(),
334                exports: vec![value_export("Foo")].into(),
335                ..Default::default()
336            },
337        ];
338        ModuleGraph::build(&modules, &[], &files)
339    }
340
341    /// Barrel 0 stars 1 and 2, both of which export `foo`.
342    fn colliding_star_graph(extra_barrel: bool) -> ModuleGraph {
343        let count = if extra_barrel { 4 } else { 3 };
344        let files: Vec<_> = (0..count)
345            .map(|index| DiscoveredFile {
346                id: FileId(index),
347                path: PathBuf::from(format!("/project/module-{index}.ts")),
348                size_bytes: 10,
349            })
350            .collect();
351        let mut modules: Vec<ResolvedModule> = vec![
352            ResolvedModule {
353                file_id: FileId(0),
354                path: files[0].path.clone(),
355                re_exports: vec![star_re_export(1), star_re_export(2)],
356                ..Default::default()
357            },
358            ResolvedModule {
359                file_id: FileId(1),
360                path: files[1].path.clone(),
361                exports: vec![value_export("foo")].into(),
362                ..Default::default()
363            },
364            ResolvedModule {
365                file_id: FileId(2),
366                path: files[2].path.clone(),
367                exports: vec![value_export("foo"), value_export("bar")].into(),
368                ..Default::default()
369            },
370        ];
371        if extra_barrel {
372            modules.push(ResolvedModule {
373                file_id: FileId(3),
374                path: files[3].path.clone(),
375                re_exports: vec![star_re_export(0)],
376                ..Default::default()
377            });
378        }
379        ModuleGraph::build(&modules, &[], &files)
380    }
381
382    #[test]
383    fn colliding_star_sources_are_reported_with_both_contributors() {
384        let graph = colliding_star_graph(false);
385
386        let collisions = graph.ambiguous_star_exports();
387
388        assert_eq!(
389            collisions,
390            vec![AmbiguousStarExport {
391                barrel: FileId(0),
392                name: Box::from("foo"),
393                namespace: ExportNamespace::Value,
394                contributors: Box::from([FileId(1), FileId(2)]),
395            }]
396        );
397    }
398
399    #[test]
400    fn colliding_type_only_star_sources_are_reported_in_the_type_namespace() {
401        let graph = type_only_colliding_star_graph();
402
403        assert_eq!(
404            graph.ambiguous_star_exports(),
405            vec![AmbiguousStarExport {
406                barrel: FileId(0),
407                name: Box::from("Foo"),
408                namespace: ExportNamespace::Type,
409                contributors: Box::from([FileId(1), FileId(2)]),
410            }]
411        );
412    }
413
414    #[test]
415    fn a_value_declaration_behind_a_type_only_star_collision_is_a_participant() {
416        let participants = type_only_colliding_star_graph().ambiguity_participants();
417
418        assert!(participants.contains_declaration(FileId(1), "Foo", false));
419        assert!(participants.contains_declaration(FileId(2), "Foo", false));
420        assert!(!participants.contains_declaration(FileId(1), "Bar", false));
421    }
422
423    #[test]
424    fn aliased_default_origins_are_participants_under_their_declaration_name() {
425        let files: Vec<_> = (0..5)
426            .map(|index| DiscoveredFile {
427                id: FileId(index),
428                path: PathBuf::from(format!("/project/module-{index}.ts")),
429                size_bytes: 10,
430            })
431            .collect();
432        let modules = vec![
433            ResolvedModule {
434                file_id: FileId(0),
435                path: files[0].path.clone(),
436                re_exports: vec![star_re_export(1), star_re_export(2)],
437                ..Default::default()
438            },
439            ResolvedModule {
440                file_id: FileId(1),
441                path: files[1].path.clone(),
442                re_exports: vec![named_re_export(3, "default", "Widget")],
443                ..Default::default()
444            },
445            ResolvedModule {
446                file_id: FileId(2),
447                path: files[2].path.clone(),
448                re_exports: vec![named_re_export(4, "default", "Widget")],
449                ..Default::default()
450            },
451            ResolvedModule {
452                file_id: FileId(3),
453                path: files[3].path.clone(),
454                exports: vec![default_export()].into(),
455                ..Default::default()
456            },
457            ResolvedModule {
458                file_id: FileId(4),
459                path: files[4].path.clone(),
460                exports: vec![default_export()].into(),
461                ..Default::default()
462            },
463        ];
464        let graph = ModuleGraph::build(&modules, &[], &files);
465
466        let participants = graph.ambiguity_participants();
467
468        assert!(participants.contains_declaration(FileId(3), "default", false));
469        assert!(participants.contains_declaration(FileId(4), "default", false));
470        assert!(!participants.contains_declaration(FileId(1), "Widget", false));
471        assert_eq!(
472            graph.ambiguous_star_exports()[0].contributors.as_ref(),
473            &[FileId(3), FileId(4)]
474        );
475    }
476
477    /// A value star collision on a barrel that also takes part in the
478    /// type-fallback lane, because a type-only re-export reads the barrel.
479    ///
480    /// Both the value lane and the fallback lane collide here, and the fallback
481    /// collision is the synthesized shadow of the value one.
482    #[test]
483    fn a_value_star_collision_is_not_reported_twice_across_namespaces() {
484        let files: Vec<_> = (0..4)
485            .map(|index| DiscoveredFile {
486                id: FileId(index),
487                path: PathBuf::from(format!("/project/module-{index}.ts")),
488                size_bytes: 10,
489            })
490            .collect();
491        let type_only_named = ResolvedReExport {
492            info: ReExportInfo {
493                source: "./module-0".to_string(),
494                imported_name: "foo".to_string(),
495                exported_name: "foo".to_string(),
496                is_type_only: true,
497                span: oxc_span::Span::default(),
498                statement_span: oxc_span::Span::default(),
499                source_span: oxc_span::Span::default(),
500            },
501            target: ResolveResult::InternalModule(FileId(0)),
502        };
503        let modules = vec![
504            ResolvedModule {
505                file_id: FileId(0),
506                path: files[0].path.clone(),
507                re_exports: vec![star_re_export(1), star_re_export(2)],
508                ..Default::default()
509            },
510            ResolvedModule {
511                file_id: FileId(1),
512                path: files[1].path.clone(),
513                exports: vec![value_export("foo")].into(),
514                ..Default::default()
515            },
516            ResolvedModule {
517                file_id: FileId(2),
518                path: files[2].path.clone(),
519                exports: vec![value_export("foo")].into(),
520                ..Default::default()
521            },
522            ResolvedModule {
523                file_id: FileId(3),
524                path: files[3].path.clone(),
525                re_exports: vec![type_only_named],
526                ..Default::default()
527            },
528        ];
529        let graph = ModuleGraph::build(&modules, &[], &files);
530
531        let collisions = graph.ambiguous_star_exports();
532
533        assert_eq!(collisions.len(), 1, "{collisions:?}");
534        assert_eq!(collisions[0].namespace, ExportNamespace::Value);
535    }
536
537    #[test]
538    fn participants_cover_only_the_colliding_name() {
539        let participants = colliding_star_graph(false).ambiguity_participants();
540
541        assert!(participants.contains_in_namespace(FileId(1), "foo", ExportNamespace::Value));
542        assert!(participants.contains_in_namespace(FileId(2), "foo", ExportNamespace::Value));
543        assert!(!participants.contains_in_namespace(FileId(2), "bar", ExportNamespace::Value));
544        assert!(!participants.contains_in_namespace(FileId(1), "foo", ExportNamespace::Type));
545    }
546
547    #[test]
548    fn a_collision_forwarded_by_a_second_barrel_keeps_the_same_contributors() {
549        let graph = colliding_star_graph(true);
550
551        let forwarded = graph.ambiguous_star_exports_on(FileId(3));
552
553        assert_eq!(
554            forwarded,
555            vec![AmbiguousStarExport {
556                barrel: FileId(3),
557                name: Box::from("foo"),
558                namespace: ExportNamespace::Value,
559                contributors: Box::from([FileId(1), FileId(2)]),
560            }]
561        );
562    }
563
564    #[test]
565    fn a_project_without_star_re_exports_reports_nothing() {
566        let files = vec![DiscoveredFile {
567            id: FileId(0),
568            path: PathBuf::from("/project/only.ts"),
569            size_bytes: 10,
570        }];
571        let modules = vec![ResolvedModule {
572            file_id: FileId(0),
573            path: files[0].path.clone(),
574            exports: vec![value_export("foo")].into(),
575            ..Default::default()
576        }];
577        let graph = ModuleGraph::build(&modules, &[], &files);
578
579        assert!(graph.ambiguous_star_exports().is_empty());
580        assert!(
581            !graph
582                .ambiguity_participants()
583                .contains_declaration(FileId(0), "foo", false)
584        );
585    }
586}
fallow_graph/graph/ambiguity.rs

fallow_graph/graph/
ambiguity.rs
