Skip to main content

import_lint/
graph.rs

1//! The whole-project module graph assembled after the link phase (PLAN-v1.md §2.1 step
2//! 4, §2.2, M2).
3//!
4//! `build` is a pure, single-threaded assembly step: the CLI crate parallelizes
5//! extraction and resolution (rayon) and hands the results here once per run (or
6//! per watch re-link, PLAN-v1.md §7) — no rayon in core.
7
8use std::collections::{HashMap, HashSet};
9use std::path::{Path, PathBuf};
10use std::sync::Arc;
11
12use oxc_str::CompactStr;
13
14use crate::extract::FileModuleInfo;
15use crate::resolve::{Provenance, is_non_ts_path};
16
17/// Every extracted file, every computed resolution, and the reverse edges derived
18/// from them.
19pub struct ModuleGraph {
20    /// Every extracted file: files discovered by the walker plus any file only
21    /// reached as an internal resolution target (it still needs to be in here as
22    /// an export-table lookup target for the one-hop check).
23    pub files: HashMap<PathBuf, Arc<FileModuleInfo>>,
24    /// `(importer file, specifier)` -> how that specifier resolved.
25    pub resolutions: HashMap<(PathBuf, CompactStr), Provenance>,
26    /// Reverse index: target file -> files with *any* edge into it (import,
27    /// default import, re-export, or star export specifier that resolved to it).
28    /// Watch mode's dirty-set computation (PLAN-v1.md §7) starts here.
29    pub importers: HashMap<PathBuf, HashSet<PathBuf>>,
30    /// Reverse index restricted to `export * from` edges: target file -> files
31    /// that star-export it. A subset of `importers`, kept separate because watch
32    /// mode needs to know specifically which files might need to re-descend a
33    /// star-export chain when a file's export surface changes (PLAN-v1.md §7).
34    pub star_importers: HashMap<PathBuf, HashSet<PathBuf>>,
35    /// Files discovered by the walker (as opposed to files only present because
36    /// they're a resolution target) — only these files' `checked_entries` get
37    /// linted.
38    pub lint_targets: HashSet<PathBuf>,
39    /// Internal resolution targets that are non-TS files (`.css`, `.json`, ... —
40    /// see [`is_non_ts_path`]): reachable through the non-TS resolver fallback,
41    /// never extracted, so they have no entry in `files`. The rule engine checks
42    /// imports from these against the `nonTsFiles` option instead of an export
43    /// table. Derived here from `resolutions`, not supplied by the caller.
44    pub non_ts_files: HashSet<PathBuf>,
45}
46
47impl ModuleGraph {
48    /// Assemble the graph. `resolutions` must already contain an entry for every
49    /// `(file.path, specifier)` pair reachable from `files`' `specifiers` lists
50    /// (the link phase's job); both reverse indexes are derived purely from that
51    /// map plus each file's `star_exports`.
52    pub fn build(
53        files: Vec<Arc<FileModuleInfo>>,
54        resolutions: HashMap<(PathBuf, CompactStr), Provenance>,
55        lint_targets: HashSet<PathBuf>,
56    ) -> Self {
57        // Every `(file, specifier)` pair that's a star-export edge, so the single
58        // pass over `resolutions` below can tell star edges apart from ordinary
59        // ones without doing a second keyed lookup per file.
60        let star_edges: HashSet<(PathBuf, CompactStr)> = files
61            .iter()
62            .flat_map(|file| {
63                file.star_exports
64                    .iter()
65                    .map(move |specifier| (file.path.clone(), specifier.clone()))
66            })
67            .collect();
68
69        let mut importers: HashMap<PathBuf, HashSet<PathBuf>> = HashMap::new();
70        let mut star_importers: HashMap<PathBuf, HashSet<PathBuf>> = HashMap::new();
71        for (key, provenance) in &resolutions {
72            let Provenance::Internal(target) = provenance else {
73                continue;
74            };
75            let (importer, _) = key;
76            importers
77                .entry(target.clone())
78                .or_default()
79                .insert(importer.clone());
80            if star_edges.contains(key) {
81                star_importers
82                    .entry(target.clone())
83                    .or_default()
84                    .insert(importer.clone());
85            }
86        }
87
88        let files: HashMap<PathBuf, Arc<FileModuleInfo>> =
89            files.into_iter().map(|f| (f.path.clone(), f)).collect();
90
91        // A non-TS internal target is recognizable from its path alone; the
92        // `files` guard is belt-and-braces (extraction never parses such a path,
93        // so it can never appear in `files`).
94        let non_ts_files: HashSet<PathBuf> = resolutions
95            .values()
96            .filter_map(|provenance| match provenance {
97                Provenance::Internal(path) if !files.contains_key(path) && is_non_ts_path(path) => {
98                    Some(path.clone())
99                }
100                _ => None,
101            })
102            .collect();
103
104        Self {
105            files,
106            resolutions,
107            importers,
108            star_importers,
109            lint_targets,
110            non_ts_files,
111        }
112    }
113
114    /// Look up how `specifier` resolved from `importer`. Allocates to build the
115    /// lookup key (tuple keys can't be queried componentwise); callers on a hot
116    /// path over many entries for the same importer should iterate `resolutions`
117    /// directly instead.
118    pub fn resolution(&self, importer: &Path, specifier: &str) -> Option<&Provenance> {
119        self.resolutions
120            .get(&(importer.to_path_buf(), CompactStr::from(specifier)))
121    }
122
123    pub fn file(&self, path: &Path) -> Option<&Arc<FileModuleInfo>> {
124        self.files.get(path)
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use std::collections::HashMap;
131
132    use super::*;
133
134    fn file(path: &str, specifiers: &[&str], star_exports: &[&str]) -> Arc<FileModuleInfo> {
135        Arc::new(FileModuleInfo {
136            path: PathBuf::from(path),
137            checked_entries: Vec::new(),
138            export_table: HashMap::new(),
139            star_exports: star_exports.iter().map(|s| CompactStr::from(*s)).collect(),
140            ambient_modules: Vec::new(),
141            specifiers: specifiers.iter().map(|s| CompactStr::from(*s)).collect(),
142            suppressions: Vec::new(),
143        })
144    }
145
146    #[test]
147    fn reverse_indexes_and_star_importer_separation() {
148        // a.ts imports "./b" (an ordinary import) and star-exports "./c"; both
149        // resolve to internal files. importers should record both edges; only the
150        // star-export edge should show up in star_importers.
151        let a = file("/proj/a.ts", &["./b", "./c"], &["./c"]);
152        let b = file("/proj/b.ts", &[], &[]);
153        let c = file("/proj/c.ts", &[], &[]);
154
155        let mut resolutions = HashMap::new();
156        resolutions.insert(
157            (a.path.clone(), CompactStr::from("./b")),
158            Provenance::Internal(b.path.clone()),
159        );
160        resolutions.insert(
161            (a.path.clone(), CompactStr::from("./c")),
162            Provenance::Internal(c.path.clone()),
163        );
164
165        let lint_targets = HashSet::from([a.path.clone()]);
166        let graph = ModuleGraph::build(
167            vec![a.clone(), b.clone(), c.clone()],
168            resolutions,
169            lint_targets,
170        );
171
172        assert_eq!(
173            graph.importers.get(&b.path).cloned().unwrap_or_default(),
174            HashSet::from([a.path.clone()])
175        );
176        assert_eq!(
177            graph.importers.get(&c.path).cloned().unwrap_or_default(),
178            HashSet::from([a.path.clone()])
179        );
180        // b is imported ordinarily, never star-exported: absent from star_importers.
181        assert!(!graph.star_importers.contains_key(&b.path));
182        // c is star-exported: present, and only via the star edge.
183        assert_eq!(
184            graph
185                .star_importers
186                .get(&c.path)
187                .cloned()
188                .unwrap_or_default(),
189            HashSet::from([a.path.clone()])
190        );
191
192        assert_eq!(
193            graph.resolution(&a.path, "./b"),
194            Some(&Provenance::Internal(b.path.clone()))
195        );
196        assert_eq!(graph.resolution(&a.path, "./nope"), None);
197        assert!(graph.file(&a.path).is_some());
198        assert!(graph.file(Path::new("/proj/does-not-exist.ts")).is_none());
199        assert!(graph.lint_targets.contains(&a.path));
200        assert!(!graph.lint_targets.contains(&b.path));
201    }
202
203    #[test]
204    fn non_ts_internal_targets_are_recorded() {
205        let a = file("/proj/a.ts", &["./styles.css", "./b"], &[]);
206        let b = file("/proj/b.ts", &[], &[]);
207
208        let mut resolutions = HashMap::new();
209        resolutions.insert(
210            (a.path.clone(), CompactStr::from("./styles.css")),
211            Provenance::Internal(PathBuf::from("/proj/styles.css")),
212        );
213        resolutions.insert(
214            (a.path.clone(), CompactStr::from("./b")),
215            Provenance::Internal(b.path.clone()),
216        );
217
218        let graph = ModuleGraph::build(vec![a.clone(), b.clone()], resolutions, HashSet::new());
219
220        assert_eq!(
221            graph.non_ts_files,
222            HashSet::from([PathBuf::from("/proj/styles.css")])
223        );
224        // The non-TS target still gets a reverse importer edge (watch mode's
225        // dirty-set computation relies on `importers` covering every internal
226        // edge).
227        assert_eq!(
228            graph
229                .importers
230                .get(Path::new("/proj/styles.css"))
231                .cloned()
232                .unwrap_or_default(),
233            HashSet::from([a.path.clone()])
234        );
235    }
236
237    #[test]
238    fn external_and_unresolved_resolutions_do_not_create_reverse_edges() {
239        let a = file("/proj/a.ts", &["pkg", "./missing"], &[]);
240
241        let mut resolutions = HashMap::new();
242        resolutions.insert(
243            (a.path.clone(), CompactStr::from("pkg")),
244            Provenance::External,
245        );
246        resolutions.insert(
247            (a.path.clone(), CompactStr::from("./missing")),
248            Provenance::Unresolved,
249        );
250
251        let graph = ModuleGraph::build(vec![a.clone()], resolutions, HashSet::new());
252
253        assert!(graph.importers.is_empty());
254        assert!(graph.star_importers.is_empty());
255    }
256}