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        }
250    }
251
252    fn default_export() -> ExportInfo {
253        ExportInfo {
254            name: ExportName::Default,
255            local_name: Some("Component".to_string()),
256            is_type_only: false,
257            visibility: VisibilityTag::None,
258            expected_unused_reason: None,
259            span: oxc_span::Span::default(),
260            members: vec![],
261            is_side_effect_used: false,
262            super_class: None,
263        }
264    }
265
266    fn star_re_export(target: u32) -> ResolvedReExport {
267        ResolvedReExport {
268            info: ReExportInfo {
269                source: format!("./module-{target}"),
270                imported_name: "*".to_string(),
271                exported_name: "*".to_string(),
272                is_type_only: false,
273                span: oxc_span::Span::default(),
274                statement_span: oxc_span::Span::default(),
275                source_span: oxc_span::Span::default(),
276            },
277            target: ResolveResult::InternalModule(FileId(target)),
278        }
279    }
280
281    fn type_only_star_re_export(target: u32) -> ResolvedReExport {
282        let mut re_export = star_re_export(target);
283        re_export.info.is_type_only = true;
284        re_export
285    }
286
287    fn named_re_export(target: u32, imported_name: &str, exported_name: &str) -> ResolvedReExport {
288        ResolvedReExport {
289            info: ReExportInfo {
290                source: format!("./module-{target}"),
291                imported_name: imported_name.to_string(),
292                exported_name: exported_name.to_string(),
293                is_type_only: false,
294                span: oxc_span::Span::default(),
295                statement_span: oxc_span::Span::default(),
296                source_span: oxc_span::Span::default(),
297            },
298            target: ResolveResult::InternalModule(FileId(target)),
299        }
300    }
301
302    /// Barrel 0 `export type *`s 1 and 2, which both export `class Foo`.
303    ///
304    /// The collision exists only in the type-fallback lane: the type-only star
305    /// drops the value lane and neither source declares a real type.
306    fn type_only_colliding_star_graph() -> ModuleGraph {
307        let files: Vec<_> = (0..3)
308            .map(|index| DiscoveredFile {
309                id: FileId(index),
310                path: PathBuf::from(format!("/project/module-{index}.ts")),
311                size_bytes: 10,
312            })
313            .collect();
314        let modules = vec![
315            ResolvedModule {
316                file_id: FileId(0),
317                path: files[0].path.clone(),
318                re_exports: vec![type_only_star_re_export(1), type_only_star_re_export(2)],
319                ..Default::default()
320            },
321            ResolvedModule {
322                file_id: FileId(1),
323                path: files[1].path.clone(),
324                exports: vec![value_export("Foo")].into(),
325                ..Default::default()
326            },
327            ResolvedModule {
328                file_id: FileId(2),
329                path: files[2].path.clone(),
330                exports: vec![value_export("Foo")].into(),
331                ..Default::default()
332            },
333        ];
334        ModuleGraph::build(&modules, &[], &files)
335    }
336
337    /// Barrel 0 stars 1 and 2, both of which export `foo`.
338    fn colliding_star_graph(extra_barrel: bool) -> ModuleGraph {
339        let count = if extra_barrel { 4 } else { 3 };
340        let files: Vec<_> = (0..count)
341            .map(|index| DiscoveredFile {
342                id: FileId(index),
343                path: PathBuf::from(format!("/project/module-{index}.ts")),
344                size_bytes: 10,
345            })
346            .collect();
347        let mut modules: Vec<ResolvedModule> = vec![
348            ResolvedModule {
349                file_id: FileId(0),
350                path: files[0].path.clone(),
351                re_exports: vec![star_re_export(1), star_re_export(2)],
352                ..Default::default()
353            },
354            ResolvedModule {
355                file_id: FileId(1),
356                path: files[1].path.clone(),
357                exports: vec![value_export("foo")].into(),
358                ..Default::default()
359            },
360            ResolvedModule {
361                file_id: FileId(2),
362                path: files[2].path.clone(),
363                exports: vec![value_export("foo"), value_export("bar")].into(),
364                ..Default::default()
365            },
366        ];
367        if extra_barrel {
368            modules.push(ResolvedModule {
369                file_id: FileId(3),
370                path: files[3].path.clone(),
371                re_exports: vec![star_re_export(0)],
372                ..Default::default()
373            });
374        }
375        ModuleGraph::build(&modules, &[], &files)
376    }
377
378    #[test]
379    fn colliding_star_sources_are_reported_with_both_contributors() {
380        let graph = colliding_star_graph(false);
381
382        let collisions = graph.ambiguous_star_exports();
383
384        assert_eq!(
385            collisions,
386            vec![AmbiguousStarExport {
387                barrel: FileId(0),
388                name: Box::from("foo"),
389                namespace: ExportNamespace::Value,
390                contributors: Box::from([FileId(1), FileId(2)]),
391            }]
392        );
393    }
394
395    #[test]
396    fn colliding_type_only_star_sources_are_reported_in_the_type_namespace() {
397        let graph = type_only_colliding_star_graph();
398
399        assert_eq!(
400            graph.ambiguous_star_exports(),
401            vec![AmbiguousStarExport {
402                barrel: FileId(0),
403                name: Box::from("Foo"),
404                namespace: ExportNamespace::Type,
405                contributors: Box::from([FileId(1), FileId(2)]),
406            }]
407        );
408    }
409
410    #[test]
411    fn a_value_declaration_behind_a_type_only_star_collision_is_a_participant() {
412        let participants = type_only_colliding_star_graph().ambiguity_participants();
413
414        assert!(participants.contains_declaration(FileId(1), "Foo", false));
415        assert!(participants.contains_declaration(FileId(2), "Foo", false));
416        assert!(!participants.contains_declaration(FileId(1), "Bar", false));
417    }
418
419    #[test]
420    fn aliased_default_origins_are_participants_under_their_declaration_name() {
421        let files: Vec<_> = (0..5)
422            .map(|index| DiscoveredFile {
423                id: FileId(index),
424                path: PathBuf::from(format!("/project/module-{index}.ts")),
425                size_bytes: 10,
426            })
427            .collect();
428        let modules = vec![
429            ResolvedModule {
430                file_id: FileId(0),
431                path: files[0].path.clone(),
432                re_exports: vec![star_re_export(1), star_re_export(2)],
433                ..Default::default()
434            },
435            ResolvedModule {
436                file_id: FileId(1),
437                path: files[1].path.clone(),
438                re_exports: vec![named_re_export(3, "default", "Widget")],
439                ..Default::default()
440            },
441            ResolvedModule {
442                file_id: FileId(2),
443                path: files[2].path.clone(),
444                re_exports: vec![named_re_export(4, "default", "Widget")],
445                ..Default::default()
446            },
447            ResolvedModule {
448                file_id: FileId(3),
449                path: files[3].path.clone(),
450                exports: vec![default_export()].into(),
451                ..Default::default()
452            },
453            ResolvedModule {
454                file_id: FileId(4),
455                path: files[4].path.clone(),
456                exports: vec![default_export()].into(),
457                ..Default::default()
458            },
459        ];
460        let graph = ModuleGraph::build(&modules, &[], &files);
461
462        let participants = graph.ambiguity_participants();
463
464        assert!(participants.contains_declaration(FileId(3), "default", false));
465        assert!(participants.contains_declaration(FileId(4), "default", false));
466        assert!(!participants.contains_declaration(FileId(1), "Widget", false));
467        assert_eq!(
468            graph.ambiguous_star_exports()[0].contributors.as_ref(),
469            &[FileId(3), FileId(4)]
470        );
471    }
472
473    /// A value star collision on a barrel that also takes part in the
474    /// type-fallback lane, because a type-only re-export reads the barrel.
475    ///
476    /// Both the value lane and the fallback lane collide here, and the fallback
477    /// collision is the synthesized shadow of the value one.
478    #[test]
479    fn a_value_star_collision_is_not_reported_twice_across_namespaces() {
480        let files: Vec<_> = (0..4)
481            .map(|index| DiscoveredFile {
482                id: FileId(index),
483                path: PathBuf::from(format!("/project/module-{index}.ts")),
484                size_bytes: 10,
485            })
486            .collect();
487        let type_only_named = ResolvedReExport {
488            info: ReExportInfo {
489                source: "./module-0".to_string(),
490                imported_name: "foo".to_string(),
491                exported_name: "foo".to_string(),
492                is_type_only: true,
493                span: oxc_span::Span::default(),
494                statement_span: oxc_span::Span::default(),
495                source_span: oxc_span::Span::default(),
496            },
497            target: ResolveResult::InternalModule(FileId(0)),
498        };
499        let modules = vec![
500            ResolvedModule {
501                file_id: FileId(0),
502                path: files[0].path.clone(),
503                re_exports: vec![star_re_export(1), star_re_export(2)],
504                ..Default::default()
505            },
506            ResolvedModule {
507                file_id: FileId(1),
508                path: files[1].path.clone(),
509                exports: vec![value_export("foo")].into(),
510                ..Default::default()
511            },
512            ResolvedModule {
513                file_id: FileId(2),
514                path: files[2].path.clone(),
515                exports: vec![value_export("foo")].into(),
516                ..Default::default()
517            },
518            ResolvedModule {
519                file_id: FileId(3),
520                path: files[3].path.clone(),
521                re_exports: vec![type_only_named],
522                ..Default::default()
523            },
524        ];
525        let graph = ModuleGraph::build(&modules, &[], &files);
526
527        let collisions = graph.ambiguous_star_exports();
528
529        assert_eq!(collisions.len(), 1, "{collisions:?}");
530        assert_eq!(collisions[0].namespace, ExportNamespace::Value);
531    }
532
533    #[test]
534    fn participants_cover_only_the_colliding_name() {
535        let participants = colliding_star_graph(false).ambiguity_participants();
536
537        assert!(participants.contains_in_namespace(FileId(1), "foo", ExportNamespace::Value));
538        assert!(participants.contains_in_namespace(FileId(2), "foo", ExportNamespace::Value));
539        assert!(!participants.contains_in_namespace(FileId(2), "bar", ExportNamespace::Value));
540        assert!(!participants.contains_in_namespace(FileId(1), "foo", ExportNamespace::Type));
541    }
542
543    #[test]
544    fn a_collision_forwarded_by_a_second_barrel_keeps_the_same_contributors() {
545        let graph = colliding_star_graph(true);
546
547        let forwarded = graph.ambiguous_star_exports_on(FileId(3));
548
549        assert_eq!(
550            forwarded,
551            vec![AmbiguousStarExport {
552                barrel: FileId(3),
553                name: Box::from("foo"),
554                namespace: ExportNamespace::Value,
555                contributors: Box::from([FileId(1), FileId(2)]),
556            }]
557        );
558    }
559
560    #[test]
561    fn a_project_without_star_re_exports_reports_nothing() {
562        let files = vec![DiscoveredFile {
563            id: FileId(0),
564            path: PathBuf::from("/project/only.ts"),
565            size_bytes: 10,
566        }];
567        let modules = vec![ResolvedModule {
568            file_id: FileId(0),
569            path: files[0].path.clone(),
570            exports: vec![value_export("foo")].into(),
571            ..Default::default()
572        }];
573        let graph = ModuleGraph::build(&modules, &[], &files);
574
575        assert!(graph.ambiguous_star_exports().is_empty());
576        assert!(
577            !graph
578                .ambiguity_participants()
579                .contains_declaration(FileId(0), "foo", false)
580        );
581    }
582}
fallow_graph/graph/ambiguity.rs

fallow_graph/graph/
ambiguity.rs
