fallow_graph/graph/
shortest_import_path.rs

1//! Shortest import path between two modules.
2//!
3//! `impact_closure` answers "what does a change reach"; this answers "HOW does
4//! one module reach another". It is a plain FIFO breadth-first search over the
5//! forward import edges, so the first path found is a shortest one.
6//!
7//! Determinism is a contract, not a coincidence: the JSON must stay
8//! byte-identical across runs and platforms. Successors are expanded in
9//! ascending `FileId` order and a node keeps the predecessor that discovered it
10//! first, which makes the reported route the lexicographically smallest
11//! `FileId` sequence among all shortest routes. The proof is inductive: the
12//! level-0 frontier is the single source, and a level is enqueued while its
13//! predecessors are dequeued in that same order, so within every level the
14//! queue order equals the lexicographic order of the routes reaching it.
15//!
16//! Type-only hops are REPORTED, never skipped. An `import type` chain is a real
17//! compile-time coupling, and silently dropping it would answer "unreachable"
18//! for a route a reader can see in the source.
19
20use std::collections::VecDeque;
21
22use fallow_types::discover::FileId;
23use fixedbitset::FixedBitSet;
24use rustc_hash::FxHashMap;
25
26use super::ModuleGraph;
27
28/// One import edge on a shortest import path.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub struct ImportPathHop {
31    /// The importing module.
32    pub from: FileId,
33    /// The imported module.
34    pub to: FileId,
35    /// Whether every symbol on this edge is type-only, so the hop exists at
36    /// compile time only. Reported rather than skipped.
37    pub all_type_only: bool,
38    /// Byte offset in `from` of the imported binding that creates this edge,
39    /// as [`ModuleGraph::outgoing_edge_summaries`] reports it: the first
40    /// value-carrying symbol, or the first symbol when every symbol is
41    /// type-only. The caller owns the source text and resolves it to a line.
42    /// On an eager-only route it is the first static value symbol.
43    pub import_span_start: Option<u32>,
44    /// Whether the edge carries a runtime value but no static one, so the
45    /// target loads only on demand (`import()`, a lazy pattern) or on another
46    /// thread. False for a static hop and for a type-only hop.
47    pub dynamic: bool,
48}
49
50impl ModuleGraph {
51    /// The shortest import path from `from` to `to`, following import edges in
52    /// the import direction.
53    ///
54    /// Returns `None` when `to` is not reachable from `from`, and
55    /// `Some(empty)` when `from` and `to` are the same module: zero hops is a
56    /// real answer, distinct from no answer at all. Out-of-range file ids have
57    /// no outgoing edges and therefore reach nothing.
58    #[must_use]
59    pub fn shortest_import_path(&self, from: FileId, to: FileId) -> Option<Vec<ImportPathHop>> {
60        self.shortest_import_path_over(from, to, false)
61    }
62
63    /// [`Self::shortest_import_path`] over eager edges only: edges with a
64    /// static symbol that carries a runtime value. The route answers why a
65    /// module loads before `from` runs; `import()`, lazy patterns, worker
66    /// loads and `import type` never qualify.
67    #[must_use]
68    pub fn shortest_eager_import_path(
69        &self,
70        from: FileId,
71        to: FileId,
72    ) -> Option<Vec<ImportPathHop>> {
73        self.shortest_import_path_over(from, to, true)
74    }
75
76    fn shortest_import_path_over(
77        &self,
78        from: FileId,
79        to: FileId,
80        eager_only: bool,
81    ) -> Option<Vec<ImportPathHop>> {
82        if from == to {
83            return Some(Vec::new());
84        }
85        let capacity = self.modules.len();
86        if from.0 as usize >= capacity || to.0 as usize >= capacity {
87            return None;
88        }
89
90        let mut visited = FixedBitSet::with_capacity(capacity);
91        visited.insert(from.0 as usize);
92        let mut predecessor: FxHashMap<FileId, ImportPathHop> = FxHashMap::default();
93        let mut queue: VecDeque<FileId> = VecDeque::new();
94        queue.push_back(from);
95
96        while let Some(current) = queue.pop_front() {
97            for hop in self.ordered_outgoing_hops(current, eager_only) {
98                let idx = hop.to.0 as usize;
99                if idx >= capacity || visited.contains(idx) {
100                    continue;
101                }
102                visited.insert(idx);
103                predecessor.insert(hop.to, hop);
104                if hop.to == to {
105                    return Some(rebuild_path(&predecessor, from, to));
106                }
107                queue.push_back(hop.to);
108            }
109        }
110        None
111    }
112
113    /// Outgoing edges of `file_id` as hops, in ascending target order and with
114    /// one hop per target. When a target is reachable over both a value edge
115    /// and a type-only edge, the value edge wins: it is the hop a reader can
116    /// follow at runtime. With `eager_only`, only edges with a static value
117    /// symbol qualify, and the hop anchors on that symbol.
118    fn ordered_outgoing_hops(&self, file_id: FileId, eager_only: bool) -> Vec<ImportPathHop> {
119        let mut hops: Vec<ImportPathHop> = self
120            .outgoing_symbol_edges(file_id)
121            .filter(|&(target, _)| target != file_id)
122            .filter_map(|(target, symbols)| {
123                let eager = symbols.iter().find(|s| s.is_eager_value());
124                if eager_only && eager.is_none() {
125                    return None;
126                }
127                let all_type_only = !symbols.is_empty() && symbols.iter().all(|s| s.is_type_only);
128                let anchor = if eager_only {
129                    eager
130                } else {
131                    symbols
132                        .iter()
133                        .find(|s| !s.is_type_only)
134                        .or_else(|| symbols.first())
135                };
136                Some(ImportPathHop {
137                    from: file_id,
138                    to: target,
139                    all_type_only,
140                    import_span_start: anchor.map(|s| s.import_span.start),
141                    dynamic: !all_type_only && eager.is_none(),
142                })
143            })
144            .collect();
145        hops.sort_unstable_by_key(|hop| (hop.to.0, hop.all_type_only, hop.import_span_start));
146        hops.dedup_by_key(|hop| hop.to);
147        hops
148    }
149}
150
151/// Walk the predecessor chain back from `to` and return it in import order.
152fn rebuild_path(
153    predecessor: &FxHashMap<FileId, ImportPathHop>,
154    from: FileId,
155    to: FileId,
156) -> Vec<ImportPathHop> {
157    let mut reversed = Vec::new();
158    let mut cursor = to;
159    while cursor != from {
160        let Some(&hop) = predecessor.get(&cursor) else {
161            break;
162        };
163        reversed.push(hop);
164        cursor = hop.from;
165    }
166    reversed.reverse();
167    reversed
168}
169
170#[cfg(test)]
171mod tests {
172    use super::*;
173    use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
174    use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource};
175    use fallow_types::extract::{ExportInfo, ExportName, ImportInfo, ImportedName, VisibilityTag};
176    use std::path::PathBuf;
177
178    fn module_path(id: u32) -> PathBuf {
179        PathBuf::from(format!("/p/src/m{id}.ts"))
180    }
181
182    fn import(target: u32, span_start: u32, type_only: bool) -> ResolvedImport {
183        ResolvedImport {
184            info: ImportInfo {
185                source: format!("./m{target}"),
186                imported_name: ImportedName::Named("value".to_string()),
187                local_name: "value".to_string(),
188                is_type_only: type_only,
189                is_type_only_star: false,
190                from_style: false,
191                span: oxc_span::Span::new(span_start, span_start + 10),
192                source_span: oxc_span::Span::default(),
193            },
194            target: ResolveResult::InternalModule(FileId(target)),
195        }
196    }
197
198    fn value_export() -> ExportInfo {
199        ExportInfo {
200            name: ExportName::Named("value".to_string()),
201            local_name: Some("value".to_string()),
202            is_type_only: false,
203            visibility: VisibilityTag::None,
204            expected_unused_reason: None,
205            span: oxc_span::Span::new(0, 20),
206            members: vec![],
207            is_side_effect_used: false,
208            super_class: None,
209            deprecated: false,
210            deprecated_reason: None,
211        }
212    }
213
214    /// Build a graph from `(source, targets)` pairs. Every edge carries one
215    /// value symbol whose import span starts at `source * 100 + target`, so a
216    /// hop's reported span identifies the edge it came from.
217    fn graph_with_edges(module_count: u32, edges: &[(u32, &[u32])]) -> ModuleGraph {
218        graph_with_typed_edges(module_count, edges, &[])
219    }
220
221    /// Same, with `type_only_edges` naming the `(source, target)` pairs whose
222    /// import is spelled `import type`.
223    fn graph_with_typed_edges(
224        module_count: u32,
225        edges: &[(u32, &[u32])],
226        type_only_edges: &[(u32, u32)],
227    ) -> ModuleGraph {
228        let files: Vec<DiscoveredFile> = (0..module_count)
229            .map(|id| DiscoveredFile {
230                id: FileId(id),
231                path: module_path(id),
232                size_bytes: 10,
233            })
234            .collect();
235        let entry_points = vec![EntryPoint {
236            path: module_path(0),
237            source: EntryPointSource::PackageJsonMain,
238        }];
239        let resolved: Vec<ResolvedModule> = (0..module_count)
240            .map(|id| {
241                let resolved_imports = edges
242                    .iter()
243                    .find(|(source, _)| *source == id)
244                    .map(|(source, targets)| {
245                        targets
246                            .iter()
247                            .map(|&target| {
248                                import(
249                                    target,
250                                    source * 100 + target,
251                                    type_only_edges.contains(&(*source, target)),
252                                )
253                            })
254                            .collect()
255                    })
256                    .unwrap_or_default();
257                ResolvedModule {
258                    file_id: FileId(id),
259                    path: module_path(id),
260                    resolved_imports,
261                    exports: vec![value_export()].into(),
262                    ..Default::default()
263                }
264            })
265            .collect();
266        ModuleGraph::build(&resolved, &entry_points, &files)
267    }
268
269    #[test]
270    fn same_module_is_zero_hops_not_unreachable() {
271        let graph = graph_with_edges(2, &[(0, &[1])]);
272        assert_eq!(
273            graph.shortest_import_path(FileId(0), FileId(0)),
274            Some(vec![])
275        );
276    }
277
278    #[test]
279    fn unreachable_target_has_no_path() {
280        let graph = graph_with_edges(3, &[(0, &[1])]);
281        assert_eq!(graph.shortest_import_path(FileId(0), FileId(2)), None);
282        // Edges are directed: the importer is not reachable from the imported.
283        assert_eq!(graph.shortest_import_path(FileId(1), FileId(0)), None);
284    }
285
286    #[test]
287    fn direct_import_is_one_hop_with_its_import_span() {
288        let graph = graph_with_edges(2, &[(0, &[1])]);
289        let path = graph
290            .shortest_import_path(FileId(0), FileId(1))
291            .expect("direct import is reachable");
292        assert_eq!(path.len(), 1);
293        assert_eq!(path[0].from, FileId(0));
294        assert_eq!(path[0].to, FileId(1));
295        assert!(!path[0].all_type_only);
296        assert_eq!(path[0].import_span_start, Some(1));
297    }
298
299    #[test]
300    fn breadth_first_prefers_the_shorter_route() {
301        // Two routes to 5: two hops through 1, four hops through 2. A LIFO walk
302        // drains the deeper branch first and reports the four-hop detour.
303        let graph = graph_with_edges(
304            6,
305            &[(0, &[1, 2]), (1, &[5]), (2, &[3]), (3, &[4]), (4, &[5])],
306        );
307        let path = graph
308            .shortest_import_path(FileId(0), FileId(5))
309            .expect("target is reachable");
310        assert_eq!(
311            path.iter().map(|hop| hop.to).collect::<Vec<_>>(),
312            vec![FileId(1), FileId(5)]
313        );
314    }
315
316    #[test]
317    fn equal_length_routes_resolve_to_the_smallest_file_id_sequence() {
318        // Two two-hop routes to 3: through 2 and through 1. The smaller
319        // intermediate wins regardless of the order the edges were declared in.
320        let graph = graph_with_edges(4, &[(0, &[2, 1]), (1, &[3]), (2, &[3])]);
321        let path = graph
322            .shortest_import_path(FileId(0), FileId(3))
323            .expect("target is reachable");
324        assert_eq!(
325            path.iter().map(|hop| hop.to).collect::<Vec<_>>(),
326            vec![FileId(1), FileId(3)]
327        );
328    }
329
330    #[test]
331    fn a_cycle_does_not_stall_the_walk() {
332        let graph = graph_with_edges(4, &[(0, &[1]), (1, &[2]), (2, &[1, 3])]);
333        let path = graph
334            .shortest_import_path(FileId(0), FileId(3))
335            .expect("target is reachable behind a cycle");
336        assert_eq!(path.len(), 3);
337    }
338
339    #[test]
340    fn out_of_range_ids_reach_nothing() {
341        let graph = graph_with_edges(2, &[(0, &[1])]);
342        assert_eq!(graph.shortest_import_path(FileId(0), FileId(9)), None);
343        assert_eq!(graph.shortest_import_path(FileId(9), FileId(1)), None);
344    }
345
346    #[test]
347    fn a_type_only_hop_is_reported_not_skipped() {
348        let graph = graph_with_typed_edges(2, &[(0, &[1])], &[(0, 1)]);
349        let path = graph
350            .shortest_import_path(FileId(0), FileId(1))
351            .expect("a type-only import is still a route");
352        assert_eq!(path.len(), 1);
353        assert!(path[0].all_type_only);
354        assert!(!path[0].dynamic, "a type-only hop is not a lazy load");
355        assert_eq!(
356            graph.shortest_eager_import_path(FileId(0), FileId(1)),
357            None,
358            "import type loads nothing, so no eager route exists"
359        );
360    }
361
362    #[test]
363    fn the_eager_route_matches_the_plain_route_over_static_edges() {
364        let graph = graph_with_edges(3, &[(0, &[1]), (1, &[2])]);
365        let plain = graph.shortest_import_path(FileId(0), FileId(2));
366        assert_eq!(
367            graph.shortest_eager_import_path(FileId(0), FileId(2)),
368            plain
369        );
370        assert!(plain.expect("reachable").iter().all(|hop| !hop.dynamic));
371    }
372}
fallow_graph/graph/shortest_import_path.rs

fallow_graph/graph/
shortest_import_path.rs
