Skip to main content

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