1use std::collections::{HashMap, HashSet};
5use std::path::{Path, PathBuf};
6
7#[derive(Debug, Default)]
8pub struct ModuleNode {
9 pub importers: HashSet<PathBuf>,
10 pub imports: HashSet<PathBuf>,
11 pub is_self_accepting: bool,
12}
13
14#[derive(Debug, Default)]
15pub struct ModuleGraph {
16 modules: HashMap<PathBuf, ModuleNode>,
17}
18
19#[derive(Debug, PartialEq, Eq)]
20pub struct UpdatePlan {
21 pub dirty: Vec<PathBuf>,
22 pub boundaries: Vec<PathBuf>,
23}
24
25#[derive(Debug, PartialEq, Eq)]
26pub enum HmrDecision {
27 Update { boundaries: Vec<PathBuf> },
28 FullReload { reason: String },
29}
30
31impl ModuleGraph {
32 pub fn new() -> Self {
33 Self::default()
34 }
35
36 pub fn ensure_module(&mut self, path: &Path) -> &mut ModuleNode {
37 self.modules.entry(path.to_path_buf()).or_default()
38 }
39
40 pub fn add_import(&mut self, importer: &Path, imported: &Path) {
41 self.ensure_module(importer)
42 .imports
43 .insert(imported.to_path_buf());
44 self.ensure_module(imported)
45 .importers
46 .insert(importer.to_path_buf());
47 }
48
49 pub fn set_self_accepting(&mut self, path: &Path, accepting: bool) {
50 self.ensure_module(path).is_self_accepting = accepting;
51 }
52
53 pub fn set_imports(&mut self, importer: &Path, imports: &[PathBuf]) {
54 let stale: Vec<PathBuf> = self
55 .ensure_module(importer)
56 .imports
57 .iter()
58 .filter(|old| !imports.contains(old))
59 .cloned()
60 .collect();
61 for old in stale {
62 if let Some(node) = self.modules.get_mut(&old) {
63 node.importers.remove(importer);
64 }
65 self.ensure_module(importer).imports.remove(&old);
66 }
67 for import in imports {
68 self.add_import(importer, import);
69 }
70 }
71
72 pub fn contains(&self, path: &Path) -> bool {
73 self.modules.contains_key(path)
74 }
75
76 pub fn module_paths(&self) -> Vec<PathBuf> {
77 let mut paths: Vec<PathBuf> = self.modules.keys().cloned().collect();
78 paths.sort();
79 paths
80 }
81
82 pub fn propagate_update(&self, changed: &Path) -> HmrDecision {
83 if !self.modules.contains_key(changed) {
84 return HmrDecision::FullReload {
85 reason: format!("{} is not in the module graph", changed.display()),
86 };
87 }
88 match self.collect_boundaries(&[changed], &[]) {
89 Ok(mut boundaries) => {
90 boundaries.sort();
91 boundaries.dedup();
92 HmrDecision::Update { boundaries }
93 }
94 Err(reason) => HmrDecision::FullReload { reason },
95 }
96 }
97
98 pub fn update_plan(&self, changed: &Path) -> Result<UpdatePlan, String> {
99 match self.propagate_update(changed) {
100 HmrDecision::FullReload { reason } => Err(reason),
101 HmrDecision::Update { boundaries } => Ok(UpdatePlan {
102 dirty: self.dirty_closure(changed),
103 boundaries,
104 }),
105 }
106 }
107
108 pub fn update_plan_from_importers(&self, changed: &Path) -> Result<UpdatePlan, String> {
109 match self.propagate_update_from_importers(changed) {
110 HmrDecision::FullReload { reason } => Err(reason),
111 HmrDecision::Update { boundaries } => Ok(UpdatePlan {
112 dirty: self.dirty_closure(changed),
113 boundaries,
114 }),
115 }
116 }
117
118 fn dirty_closure(&self, changed: &Path) -> Vec<PathBuf> {
119 let mut dirty: Vec<PathBuf> = vec![changed.to_path_buf()];
120 let mut queue = vec![changed.to_path_buf()];
121 let mut seen: HashSet<PathBuf> = queue.iter().cloned().collect();
122 while let Some(current) = queue.pop() {
123 let Some(node) = self.modules.get(¤t) else {
124 continue;
125 };
126 if node.is_self_accepting && current != changed {
127 continue;
128 }
129 for importer in &node.importers {
130 if seen.insert(importer.clone()) {
131 dirty.push(importer.clone());
132 queue.push(importer.clone());
133 }
134 }
135 }
136 dirty.sort();
137 dirty
138 }
139
140 pub fn propagate_update_from_importers(&self, changed: &Path) -> HmrDecision {
141 let Some(node) = self.modules.get(changed) else {
142 return HmrDecision::FullReload {
143 reason: format!("{} is not in the module graph", changed.display()),
144 };
145 };
146 if node.importers.is_empty() {
147 return HmrDecision::FullReload {
148 reason: format!("{} invalidated at an entry", changed.display()),
149 };
150 }
151
152 let seeds: Vec<&Path> = node.importers.iter().map(PathBuf::as_path).collect();
153 match self.collect_boundaries(&seeds, &[changed]) {
154 Ok(mut boundaries) => {
155 boundaries.sort();
156 boundaries.dedup();
157 HmrDecision::Update { boundaries }
158 }
159 Err(reason) => HmrDecision::FullReload { reason },
160 }
161 }
162
163 fn collect_boundaries<'a>(
164 &'a self,
165 seeds: &[&'a Path],
166 pre_stack: &[&'a Path],
167 ) -> Result<Vec<PathBuf>, String> {
168 let mut colors: HashMap<&'a Path, Color> = HashMap::new();
169 for module in pre_stack {
170 colors.insert(module, Color::Gray);
171 }
172 let mut boundaries: Vec<PathBuf> = Vec::new();
173 for seed in seeds {
174 self.climb(seed, &mut colors, &mut boundaries)?;
175 }
176 Ok(boundaries)
177 }
178
179 fn climb<'a>(
180 &'a self,
181 current: &'a Path,
182 colors: &mut HashMap<&'a Path, Color>,
183 boundaries: &mut Vec<PathBuf>,
184 ) -> Result<(), String> {
185 match colors.get(current) {
186 Some(Color::Black) => return Ok(()),
187 Some(Color::Gray) => {
188 return Err(format!("circular import involving {}", current.display()));
189 }
190 None => {}
191 }
192 let node = &self.modules[current];
193 if node.is_self_accepting {
194 boundaries.push(current.to_path_buf());
195 colors.insert(current, Color::Black);
196 return Ok(());
197 }
198 if node.importers.is_empty() {
199 return Err(format!(
200 "update reached entry {} with no accepting boundary",
201 current.display()
202 ));
203 }
204 colors.insert(current, Color::Gray);
205 let mut importers: Vec<&Path> = node.importers.iter().map(PathBuf::as_path).collect();
206 importers.sort();
207 for importer in importers {
208 self.climb(importer, colors, boundaries)?;
209 }
210 colors.insert(current, Color::Black);
211 Ok(())
212 }
213}
214
215#[derive(Clone, Copy, PartialEq)]
216enum Color {
217 Gray,
218 Black,
219}
220
221#[cfg(test)]
222mod tests {
223 use super::*;
224
225 fn p(s: &str) -> PathBuf {
226 PathBuf::from(s)
227 }
228
229 fn graph() -> ModuleGraph {
230 let mut g = ModuleGraph::new();
231 g.add_import(&p("main.tsx"), &p("App.tsx"));
232 g.add_import(&p("App.tsx"), &p("Button.tsx"));
233 g.set_self_accepting(&p("App.tsx"), true);
234 g.set_self_accepting(&p("Button.tsx"), true);
235 g
236 }
237
238 #[test]
239 fn change_to_self_accepting_leaf_updates_in_place() {
240 let decision = graph().propagate_update(&p("Button.tsx"));
241 assert_eq!(
242 decision,
243 HmrDecision::Update {
244 boundaries: vec![p("Button.tsx")]
245 }
246 );
247 }
248
249 #[test]
250 fn change_propagates_up_to_nearest_boundary() {
251 let mut g = graph();
252 g.add_import(&p("Button.tsx"), &p("utils.ts"));
253 let decision = g.propagate_update(&p("utils.ts"));
254 assert_eq!(
255 decision,
256 HmrDecision::Update {
257 boundaries: vec![p("Button.tsx")]
258 }
259 );
260 }
261
262 #[test]
263 fn dead_end_at_entry_forces_full_reload() {
264 let mut g = graph();
265 g.set_self_accepting(&p("App.tsx"), false);
266 g.add_import(&p("App.tsx"), &p("config.ts"));
267 assert!(matches!(
268 g.propagate_update(&p("config.ts")),
269 HmrDecision::FullReload { .. }
270 ));
271 }
272
273 #[test]
274 fn unknown_module_forces_full_reload() {
275 assert!(matches!(
276 graph().propagate_update(&p("never-imported.ts")),
277 HmrDecision::FullReload { .. }
278 ));
279 }
280
281 #[test]
282 fn update_plan_collects_dirty_chain_through_non_boundaries() {
283 let mut g = graph();
284 g.add_import(&p("Button.tsx"), &p("utils.ts"));
285 let plan = g.update_plan(&p("utils.ts")).unwrap();
286 assert_eq!(plan.boundaries, vec![p("Button.tsx")]);
287 assert_eq!(plan.dirty, vec![p("Button.tsx"), p("utils.ts")]);
288 assert!(!plan.dirty.contains(&p("App.tsx")));
289 assert!(g.update_plan(&p("main.tsx")).is_err());
290 }
291
292 #[test]
293 fn invalidate_skips_own_acceptance_and_climbs_to_importer() {
294 let decision = graph().propagate_update_from_importers(&p("Button.tsx"));
295 assert_eq!(
296 decision,
297 HmrDecision::Update {
298 boundaries: vec![p("App.tsx")]
299 }
300 );
301 assert!(matches!(
302 graph().propagate_update_from_importers(&p("App.tsx")),
303 HmrDecision::FullReload { .. }
304 ));
305 }
306
307 #[test]
308 fn set_imports_drops_stale_reverse_edges() {
309 let mut g = graph();
310 g.add_import(&p("App.tsx"), &p("old-dep.ts"));
311 g.set_imports(&p("App.tsx"), &[p("Button.tsx")]);
312 assert!(matches!(
313 g.propagate_update(&p("old-dep.ts")),
314 HmrDecision::FullReload { .. }
315 ));
316 assert_eq!(
317 g.propagate_update(&p("Button.tsx")),
318 HmrDecision::Update {
319 boundaries: vec![p("Button.tsx")]
320 }
321 );
322 }
323
324 #[test]
325 fn diamond_graphs_dedupe_boundaries() {
326 let mut g = ModuleGraph::new();
327 for parent in ["A.tsx", "B.tsx"] {
328 g.add_import(&p("main.tsx"), &p(parent));
329 g.add_import(&p(parent), &p("shared.ts"));
330 g.set_self_accepting(&p(parent), true);
331 }
332 let decision = g.propagate_update(&p("shared.ts"));
333 assert_eq!(
334 decision,
335 HmrDecision::Update {
336 boundaries: vec![p("A.tsx"), p("B.tsx")]
337 }
338 );
339 let plan = g.update_plan(&p("shared.ts")).unwrap();
340 assert_eq!(plan.dirty, vec![p("A.tsx"), p("B.tsx"), p("shared.ts")]);
341 }
342
343 #[test]
344 fn invalidate_plan_escalates_to_importer_boundaries() {
345 let plan = graph()
346 .update_plan_from_importers(&p("Button.tsx"))
347 .unwrap();
348 assert_eq!(plan.boundaries, vec![p("App.tsx")]);
349 assert!(
350 plan.dirty.contains(&p("Button.tsx")),
351 "changed module is dirty"
352 );
353 assert!(
354 plan.dirty.contains(&p("App.tsx")),
355 "importer boundary is dirty"
356 );
357 assert!(graph().update_plan_from_importers(&p("App.tsx")).is_err());
358 }
359
360 #[test]
361 fn diamond_ladder_is_linear_not_exponential() {
362 let n = 60;
363 let mut g = ModuleGraph::new();
364 let m = |i: usize| p(&format!("M{i}.ts"));
365 for i in 0..n {
366 for side in ["A", "B"] {
367 let mid = p(&format!("{side}{i}.ts"));
368 g.add_import(&mid, &m(i));
369 g.add_import(&m(i + 1), &mid);
370 }
371 }
372 g.add_import(&p("Root.tsx"), &m(n));
373 g.set_self_accepting(&p("Root.tsx"), true);
374
375 assert_eq!(
376 g.propagate_update(&m(0)),
377 HmrDecision::Update {
378 boundaries: vec![p("Root.tsx")]
379 }
380 );
381 }
382
383 #[test]
384 fn import_cycles_do_not_hang_propagation() {
385 let mut g = ModuleGraph::new();
386 g.add_import(&p("a.ts"), &p("b.ts"));
387 g.add_import(&p("b.ts"), &p("a.ts"));
388 assert!(matches!(
389 g.propagate_update(&p("a.ts")),
390 HmrDecision::FullReload { .. }
391 ));
392 }
393}