Skip to main content

fallow_graph/graph/
effective_re_exports.rs

1//! Effective outward re-export routes for one canonical binding.
2
3use std::collections::VecDeque;
4
5use fallow_types::discover::FileId;
6use rustc_hash::{FxHashMap, FxHashSet};
7
8use fallow_types::extract::ModuleLoadMechanism;
9
10use super::effective_exports::{EffectiveExportBinding, EffectiveExportIndex};
11use super::types::{
12    ModuleNode, ReferencePathId, ReferencePathInterner, ReferenceRouteGraphId,
13    ReferenceRouteGraphSpec, ReferenceRouteNodeId, ReferenceRouteNodeSpec,
14};
15use super::{EffectiveExportResolution, ExportNamespace, ModuleGraph};
16
17/// One module/name pair that effectively exposes a traced binding.
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct EffectiveReExportRoute {
20    barrel_file: FileId,
21    exported_name: String,
22}
23
24impl EffectiveReExportRoute {
25    /// Module exposing the binding at this step.
26    #[must_use]
27    pub const fn barrel_file(&self) -> FileId {
28        self.barrel_file
29    }
30
31    /// Name exposed by this module.
32    #[must_use]
33    pub fn exported_name(&self) -> &str {
34        &self.exported_name
35    }
36}
37
38impl ModuleGraph {
39    /// Every effective outward route from one exported binding.
40    ///
41    /// Routes carry aliases across named re-exports, omit ambiguous and
42    /// shadowed paths, deduplicate convergent diamonds, and terminate on cycles.
43    #[must_use]
44    pub fn effective_re_export_routes(
45        &self,
46        source_file: FileId,
47        source_name: &str,
48        namespace: ExportNamespace,
49    ) -> Vec<EffectiveReExportRoute> {
50        let EffectiveExportResolution::Unique(source_binding) =
51            self.resolve_export(source_file, source_name, namespace)
52        else {
53            return Vec::new();
54        };
55
56        let mut re_exports_by_source: FxHashMap<FileId, Vec<(FileId, usize)>> =
57            FxHashMap::default();
58        for module in &self.modules {
59            for (index, re_export) in module.re_exports.iter().enumerate() {
60                re_exports_by_source
61                    .entry(re_export.source_file)
62                    .or_default()
63                    .push((module.file_id, index));
64            }
65        }
66
67        let initial = (source_file, source_name.to_string());
68        let mut visited = FxHashSet::from_iter([initial.clone()]);
69        let mut queue = VecDeque::from([initial]);
70        let mut routes = Vec::new();
71
72        while let Some((current_file, current_name)) = queue.pop_front() {
73            let Some(re_exports) = re_exports_by_source.get(&current_file) else {
74                continue;
75            };
76            for &(barrel_file, re_export_index) in re_exports {
77                let re_export = &self.modules[barrel_file.0 as usize].re_exports[re_export_index];
78                let Some(exported_name) =
79                    effective_destination_name(re_export, &current_name, namespace)
80                else {
81                    continue;
82                };
83                if self.resolve_export(barrel_file, exported_name, namespace)
84                    != EffectiveExportResolution::Unique(source_binding)
85                {
86                    continue;
87                }
88
89                let destination = (barrel_file, exported_name.to_string());
90                if !visited.insert(destination.clone()) {
91                    continue;
92                }
93                routes.push(EffectiveReExportRoute {
94                    barrel_file,
95                    exported_name: destination.1.clone(),
96                });
97                queue.push_back(destination);
98            }
99        }
100
101        routes
102    }
103}
104
105pub(in crate::graph) struct EffectiveDeclarationRoute {
106    pub(in crate::graph) binding: EffectiveExportBinding,
107    graph: ReferenceRouteGraphSpec,
108    start: ReferenceRouteNodeId,
109    terminal: ReferenceRouteNodeId,
110}
111
112impl EffectiveDeclarationRoute {
113    pub(in crate::graph) fn intern(
114        self,
115        reference_paths: &mut ReferencePathInterner,
116    ) -> InternedEffectiveDeclarationRoute {
117        let graph = reference_paths
118            .tracks_provenance()
119            .then(|| reference_paths.intern_route_graph(self.graph));
120        InternedEffectiveDeclarationRoute {
121            graph,
122            start: self.start,
123            terminal: self.terminal,
124        }
125    }
126}
127
128#[derive(Clone, Copy)]
129pub(in crate::graph) struct InternedEffectiveDeclarationRoute {
130    graph: Option<ReferenceRouteGraphId>,
131    start: ReferenceRouteNodeId,
132    terminal: ReferenceRouteNodeId,
133}
134
135impl InternedEffectiveDeclarationRoute {
136    pub(in crate::graph) fn extend_path(
137        &self,
138        parent: Option<ReferencePathId>,
139        reference_paths: &mut ReferencePathInterner,
140    ) -> Option<ReferencePathId> {
141        let graph = self.graph?;
142        reference_paths.route(
143            parent,
144            graph,
145            self.start,
146            self.terminal,
147            Some(ModuleLoadMechanism::EsModule),
148        )
149    }
150}
151
152pub(in crate::graph) fn effective_declaration_route(
153    modules: &[ModuleNode],
154    index: &EffectiveExportIndex,
155    file: FileId,
156    name: &str,
157    namespace: ExportNamespace,
158) -> Option<EffectiveDeclarationRoute> {
159    let EffectiveExportResolution::Unique(binding) = index.resolve(file, name, namespace) else {
160        return None;
161    };
162    binding.origin_slot()?;
163
164    // States borrow their names from the module re-export edges, so the search
165    // walks the topology without allocating one string per visited hop.
166    let initial: (FileId, &str) = (file, name);
167    let mut states = vec![initial];
168    let mut state_ids: FxHashMap<(FileId, &str), usize> = FxHashMap::from_iter([(initial, 0)]);
169    let mut successors: Vec<Vec<usize>> = vec![Vec::new()];
170    let mut frontier = VecDeque::from([0_usize]);
171    let mut terminal = None;
172
173    while let Some(state_id) = frontier.pop_front() {
174        let (current_file, current_name) = states[state_id];
175        if current_file == binding.origin_file() {
176            terminal = Some(state_id);
177            continue;
178        }
179        let module = modules.get(current_file.0 as usize)?;
180        for edge in &module.re_exports {
181            let Some(source_name) = effective_source_name(edge, current_name, namespace) else {
182                continue;
183            };
184            if index.resolve(edge.source_file, source_name, namespace)
185                != EffectiveExportResolution::Unique(binding)
186            {
187                continue;
188            }
189            let state = (edge.source_file, source_name);
190            let next_id = if let Some(next_id) = state_ids.get(&state) {
191                *next_id
192            } else {
193                let next_id = states.len();
194                states.push(state);
195                state_ids.insert(state, next_id);
196                successors.push(Vec::new());
197                frontier.push_back(next_id);
198                next_id
199            };
200            successors[state_id].push(next_id);
201        }
202    }
203
204    let terminal = terminal?;
205    for next in &mut successors {
206        next.sort_unstable();
207        next.dedup();
208    }
209    let nodes = states
210        .iter()
211        .zip(successors)
212        .map(|((target, _), successors)| {
213            ReferenceRouteNodeSpec::new(
214                *target,
215                ModuleLoadMechanism::EsModule,
216                successors
217                    .into_iter()
218                    .map(|id| ReferenceRouteNodeId(id as u32))
219                    .collect(),
220            )
221        })
222        .collect();
223    Some(EffectiveDeclarationRoute {
224        binding,
225        graph: ReferenceRouteGraphSpec::new(nodes),
226        start: ReferenceRouteNodeId(0),
227        terminal: ReferenceRouteNodeId(terminal as u32),
228    })
229}
230
231fn effective_destination_name<'a>(
232    re_export: &'a super::ReExportEdge,
233    source_name: &'a str,
234    namespace: ExportNamespace,
235) -> Option<&'a str> {
236    if namespace == ExportNamespace::Value && re_export.is_type_only {
237        return None;
238    }
239    if re_export.exported_name == "*" {
240        return (source_name != "default").then_some(source_name);
241    }
242    if re_export.imported_name == "*" || re_export.imported_name != source_name {
243        return None;
244    }
245    Some(&re_export.exported_name)
246}
247
248fn effective_source_name<'a>(
249    re_export: &'a super::ReExportEdge,
250    exported_name: &'a str,
251    namespace: ExportNamespace,
252) -> Option<&'a str> {
253    if namespace == ExportNamespace::Value && re_export.is_type_only {
254        return None;
255    }
256    if re_export.exported_name == "*" {
257        return (exported_name != "default").then_some(exported_name);
258    }
259    if re_export.exported_name != exported_name || re_export.imported_name == "*" {
260        return None;
261    }
262    Some(&re_export.imported_name)
263}
264
265#[cfg(test)]
266mod tests {
267    use std::path::PathBuf;
268
269    use fallow_types::extract::{ExportInfo, ExportName, ReExportInfo, VisibilityTag};
270    use oxc_span::Span;
271
272    use super::*;
273    use crate::graph::ReExportEdge;
274    use crate::graph::types::{ExportSymbol, ReferencePathNode};
275    use crate::resolve::{ResolveResult, ResolvedModule, ResolvedReExport};
276
277    fn source_export() -> ExportInfo {
278        ExportInfo {
279            name: ExportName::Named("foo".to_string()),
280            local_name: Some("foo".to_string()),
281            is_type_only: false,
282            is_side_effect_used: false,
283            visibility: VisibilityTag::None,
284            expected_unused_reason: None,
285            span: Span::new(0, 3),
286            members: Vec::new(),
287            super_class: None,
288            deprecated: false,
289            deprecated_reason: None,
290        }
291    }
292
293    fn re_export(target: FileId, imported_name: &str, exported_name: &str) -> ResolvedReExport {
294        ResolvedReExport {
295            info: ReExportInfo {
296                source: "./source".to_string(),
297                imported_name: imported_name.to_string(),
298                exported_name: exported_name.to_string(),
299                is_type_only: false,
300                span: Span::default(),
301                statement_span: Span::default(),
302                source_span: Span::default(),
303                visibility: VisibilityTag::None,
304                expected_unused_reason: None,
305            },
306            target: ResolveResult::InternalModule(target),
307        }
308    }
309
310    fn re_export_edge(
311        source_file: FileId,
312        imported_name: &str,
313        exported_name: &str,
314    ) -> ReExportEdge {
315        ReExportEdge {
316            source_file,
317            imported_name: imported_name.to_string(),
318            exported_name: exported_name.to_string(),
319            is_type_only: false,
320            span: Span::default(),
321        }
322    }
323
324    fn module(
325        file_id: FileId,
326        path: &str,
327        exports: Vec<ExportSymbol>,
328        re_exports: Vec<ReExportEdge>,
329    ) -> ModuleNode {
330        ModuleNode {
331            file_id,
332            path: PathBuf::from(path),
333            edge_range: 0..0,
334            exports,
335            re_exports,
336            flags: 0,
337        }
338    }
339
340    fn source_symbol() -> ExportSymbol {
341        ExportSymbol {
342            name: ExportName::Named("foo".to_string()),
343            is_type_only: false,
344            is_side_effect_used: false,
345            visibility: VisibilityTag::None,
346            expected_unused_reason: None,
347            span: Span::new(0, 3),
348            references: Vec::new(),
349            reference_paths: Vec::new(),
350            members: Vec::new(),
351            deprecated: false,
352            deprecated_reason: None,
353        }
354    }
355
356    #[test]
357    fn declaration_route_retains_star_surface_and_origin_hops() {
358        let resolved = vec![
359            ResolvedModule {
360                file_id: FileId(0),
361                re_exports: vec![re_export(FileId(1), "*", "*")],
362                ..Default::default()
363            },
364            ResolvedModule {
365                file_id: FileId(1),
366                exports: vec![source_export()].into(),
367                ..Default::default()
368            },
369        ];
370        let mut modules = vec![
371            module(
372                FileId(0),
373                "/project/inner.ts",
374                Vec::new(),
375                vec![re_export_edge(FileId(1), "*", "*")],
376            ),
377            module(
378                FileId(1),
379                "/project/source.ts",
380                vec![source_symbol()],
381                Vec::new(),
382            ),
383        ];
384        let index = EffectiveExportIndex::build(&resolved);
385
386        let route =
387            effective_declaration_route(&modules, &index, FileId(0), "foo", ExportNamespace::Value)
388                .expect("the star surface must retain a route to its declaration");
389
390        assert_eq!(route.binding.origin_file(), FileId(1));
391        let mut paths = ReferencePathInterner::new(true);
392        let route = route.intern(&mut paths);
393        let path = route
394            .extend_path(None, &mut paths)
395            .expect("tracked routes return one interned path");
396        let finalized = paths.finalize(&mut modules);
397        let ReferencePathNode::Route {
398            graph,
399            start,
400            terminal,
401            start_mechanism,
402            ..
403        } = finalized.paths[path.index()]
404        else {
405            panic!("effective declaration routes use the compact route contract");
406        };
407        assert_eq!(
408            finalized
409                .routes
410                .canonical_hops(graph, start, terminal, start_mechanism),
411            vec![
412                (FileId(1), ModuleLoadMechanism::EsModule),
413                (FileId(0), ModuleLoadMechanism::EsModule),
414            ]
415        );
416    }
417
418    #[test]
419    fn declaration_route_retains_rename_star_and_origin_hops() {
420        let resolved = vec![
421            ResolvedModule {
422                file_id: FileId(0),
423                re_exports: vec![re_export(FileId(1), "foo", "alias")],
424                ..Default::default()
425            },
426            ResolvedModule {
427                file_id: FileId(1),
428                re_exports: vec![re_export(FileId(2), "*", "*")],
429                ..Default::default()
430            },
431            ResolvedModule {
432                file_id: FileId(2),
433                exports: vec![source_export()].into(),
434                ..Default::default()
435            },
436        ];
437        let mut modules = vec![
438            module(
439                FileId(0),
440                "/project/rename.ts",
441                Vec::new(),
442                vec![re_export_edge(FileId(1), "foo", "alias")],
443            ),
444            module(
445                FileId(1),
446                "/project/inner.ts",
447                Vec::new(),
448                vec![re_export_edge(FileId(2), "*", "*")],
449            ),
450            module(
451                FileId(2),
452                "/project/source.ts",
453                vec![source_symbol()],
454                Vec::new(),
455            ),
456        ];
457        let index = EffectiveExportIndex::build(&resolved);
458        let route = effective_declaration_route(
459            &modules,
460            &index,
461            FileId(0),
462            "alias",
463            ExportNamespace::Value,
464        )
465        .expect("the renamed star surface must retain its declaration route");
466
467        assert_eq!(route.binding.origin_file(), FileId(2));
468        let mut paths = ReferencePathInterner::new(true);
469        let route = route.intern(&mut paths);
470        let path = route
471            .extend_path(None, &mut paths)
472            .expect("tracked routes return one interned path");
473        let finalized = paths.finalize(&mut modules);
474        let ReferencePathNode::Route {
475            graph,
476            start,
477            terminal,
478            start_mechanism,
479            ..
480        } = finalized.paths[path.index()]
481        else {
482            panic!("effective declaration routes use the compact route contract");
483        };
484        assert_eq!(
485            finalized
486                .routes
487                .canonical_hops(graph, start, terminal, start_mechanism),
488            vec![
489                (FileId(2), ModuleLoadMechanism::EsModule),
490                (FileId(1), ModuleLoadMechanism::EsModule),
491                (FileId(0), ModuleLoadMechanism::EsModule),
492            ]
493        );
494    }
495}