1use std::path::Path;
16
17use super::relativize;
18
19use fallow_types::discover::FileId;
20use fixedbitset::FixedBitSet;
21use rustc_hash::FxHashMap;
22
23use super::ModuleGraph;
24
25#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct CoordinationGap {
31 changed_file: FileId,
33 consumer_file: FileId,
35 consumed_symbols: Vec<String>,
37}
38
39#[derive(Debug, Clone, Default)]
43pub struct ImpactClosure {
44 in_diff: Vec<FileId>,
46 affected_not_shown: Vec<FileId>,
49 coordination_gap: Vec<CoordinationGap>,
51}
52
53#[derive(Debug, Clone, Default)]
56pub struct ImpactClosurePaths {
57 pub in_diff: Vec<String>,
59 pub affected_not_shown: Vec<String>,
61 pub coordination_gap: Vec<CoordinationGapPaths>,
63}
64
65#[derive(Debug, Clone, PartialEq, Eq)]
67pub struct CoordinationGapPaths {
68 pub changed_file: String,
70 pub consumer_file: String,
72 pub consumed_symbols: Vec<String>,
74}
75
76impl ModuleGraph {
77 #[must_use]
90 pub fn impact_closure(&self, changed: &[FileId]) -> ImpactClosure {
91 let capacity = self.modules.len();
92 let mut in_diff_set = FixedBitSet::with_capacity(capacity);
93 for &id in changed {
94 let idx = id.0 as usize;
95 if idx < capacity {
96 in_diff_set.insert(idx);
97 }
98 }
99
100 let affected = self.collect_reverse_closure(&in_diff_set, capacity);
101 let coordination_gap = self.collect_coordination_gaps(&in_diff_set);
102
103 ImpactClosure {
104 in_diff: in_diff_set.ones().map(|i| FileId(i as u32)).collect(),
105 affected_not_shown: affected.ones().map(|i| FileId(i as u32)).collect(),
106 coordination_gap,
107 }
108 }
109
110 fn collect_reverse_closure(&self, seed: &FixedBitSet, capacity: usize) -> FixedBitSet {
113 let mut visited = seed.clone();
114 let mut stack: Vec<FileId> = seed.ones().map(|i| FileId(i as u32)).collect();
115
116 while let Some(current) = stack.pop() {
117 let Some(importers) = self.reverse_deps.get(current.0 as usize) else {
118 continue;
119 };
120 for &importer in importers {
121 let idx = importer.0 as usize;
122 if idx >= capacity || visited.contains(idx) {
123 continue;
124 }
125 visited.insert(idx);
126 stack.push(importer);
127 }
128 }
129 visited.difference_with(seed);
130 visited
131 }
132
133 fn collect_coordination_gaps(&self, in_diff_set: &FixedBitSet) -> Vec<CoordinationGap> {
137 let mut gaps: Vec<CoordinationGap> = Vec::new();
138 for changed_idx in in_diff_set.ones() {
139 let Some(module) = self.modules.get(changed_idx) else {
140 continue;
141 };
142 let mut by_consumer: FxHashMap<FileId, Vec<String>> = FxHashMap::default();
145 for export in &module.exports {
146 if export.is_type_only {
147 continue;
148 }
149 let symbol_name = export.name.to_string();
150 for reference in &export.references {
151 let consumer_idx = reference.from_file.0 as usize;
152 if in_diff_set.contains(consumer_idx) {
153 continue;
155 }
156 if self
162 .modules
163 .get(consumer_idx)
164 .is_some_and(|m| is_dev_glue_path(&m.path))
165 {
166 continue;
167 }
168 by_consumer
169 .entry(reference.from_file)
170 .or_default()
171 .push(symbol_name.clone());
172 }
173 }
174 for (consumer_file, mut symbols) in by_consumer {
175 symbols.sort_unstable();
176 symbols.dedup();
177 gaps.push(CoordinationGap {
178 changed_file: FileId(changed_idx as u32),
179 consumer_file,
180 consumed_symbols: symbols,
181 });
182 }
183 }
184 gaps.sort_unstable_by(|a, b| {
185 a.changed_file
186 .0
187 .cmp(&b.changed_file.0)
188 .then_with(|| a.consumer_file.0.cmp(&b.consumer_file.0))
189 });
190 gaps
191 }
192
193 #[must_use]
196 pub fn closure_with_paths(&self, closure: &ImpactClosure, root: &Path) -> ImpactClosurePaths {
197 let resolve = |id: FileId| -> Option<String> {
198 self.modules
199 .get(id.0 as usize)
200 .map(|m| relativize(&m.path, root))
201 };
202
203 let mut in_diff: Vec<String> = closure
204 .in_diff
205 .iter()
206 .filter_map(|&id| resolve(id))
207 .collect();
208 in_diff.sort();
209 let mut affected_not_shown: Vec<String> = closure
210 .affected_not_shown
211 .iter()
212 .filter_map(|&id| resolve(id))
213 .collect();
214 affected_not_shown.sort();
215
216 let mut coordination_gap: Vec<CoordinationGapPaths> = closure
217 .coordination_gap
218 .iter()
219 .filter_map(|gap| {
220 Some(CoordinationGapPaths {
221 changed_file: resolve(gap.changed_file)?,
222 consumer_file: resolve(gap.consumer_file)?,
223 consumed_symbols: gap.consumed_symbols.clone(),
224 })
225 })
226 .collect();
227 coordination_gap.sort_by(|a, b| {
228 a.changed_file
229 .cmp(&b.changed_file)
230 .then_with(|| a.consumer_file.cmp(&b.consumer_file))
231 });
232
233 ImpactClosurePaths {
234 in_diff,
235 affected_not_shown,
236 coordination_gap,
237 }
238 }
239}
240
241fn is_dev_glue_path(path: &Path) -> bool {
253 let name = path
254 .file_name()
255 .and_then(|n| n.to_str())
256 .unwrap_or_default();
257 if [".stories.", ".story.", ".spec.", ".test.", ".cy."]
258 .iter()
259 .any(|marker| name.contains(marker))
260 {
261 return true;
262 }
263 path.components().any(|component| {
264 matches!(
265 component.as_os_str().to_str(),
266 Some("__tests__" | "__mocks__" | "__stories__")
267 )
268 })
269}
270
271#[cfg(test)]
272mod tests {
273 use super::*;
274 use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
275 use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource};
276 use fallow_types::extract::{ExportInfo, ExportName, ImportInfo, ImportedName, VisibilityTag};
277 use std::path::PathBuf;
278
279 fn file(id: u32, path: &str) -> DiscoveredFile {
280 DiscoveredFile {
281 id: FileId(id),
282 path: PathBuf::from(path),
283 size_bytes: 10,
284 }
285 }
286
287 fn named_import(source: &str, name: &str, target: FileId) -> ResolvedImport {
288 ResolvedImport {
289 info: ImportInfo {
290 source: source.to_string(),
291 imported_name: ImportedName::Named(name.to_string()),
292 local_name: name.to_string(),
293 is_type_only: false,
294 is_type_only_star: false,
295 from_style: false,
296 span: oxc_span::Span::new(0, 10),
297 source_span: oxc_span::Span::default(),
298 },
299 target: ResolveResult::InternalModule(target),
300 }
301 }
302
303 fn named_export(name: &str) -> ExportInfo {
304 ExportInfo {
305 name: ExportName::Named(name.to_string()),
306 local_name: Some(name.to_string()),
307 is_type_only: false,
308 visibility: VisibilityTag::None,
309 expected_unused_reason: None,
310 span: oxc_span::Span::new(0, 20),
311 members: vec![],
312 is_side_effect_used: false,
313 super_class: None,
314 deprecated: false,
315 deprecated_reason: None,
316 }
317 }
318
319 fn build_reverse_dep_graph() -> ModuleGraph {
322 let files = vec![
323 file(0, "/p/src/core.ts"),
324 file(1, "/p/src/mid.ts"),
325 file(2, "/p/src/app.ts"),
326 ];
327 let entry_points = vec![EntryPoint {
328 path: PathBuf::from("/p/src/app.ts"),
329 source: EntryPointSource::PackageJsonMain,
330 }];
331 let resolved = vec![
332 ResolvedModule {
333 file_id: FileId(0),
334 path: PathBuf::from("/p/src/core.ts"),
335 exports: vec![named_export("compute")].into(),
336 ..Default::default()
337 },
338 ResolvedModule {
339 file_id: FileId(1),
340 path: PathBuf::from("/p/src/mid.ts"),
341 resolved_imports: vec![named_import("./core", "compute", FileId(0))],
342 exports: vec![named_export("midFn")].into(),
343 ..Default::default()
344 },
345 ResolvedModule {
346 file_id: FileId(2),
347 path: PathBuf::from("/p/src/app.ts"),
348 resolved_imports: vec![named_import("./mid", "midFn", FileId(1))],
349 ..Default::default()
350 },
351 ];
352 ModuleGraph::build(&resolved, &entry_points, &files)
353 }
354
355 fn build_re_export_graph() -> ModuleGraph {
358 use crate::resolve::ResolvedReExport;
359 use fallow_types::extract::ReExportInfo;
360
361 let files = vec![
362 file(0, "/p/src/impl.ts"),
363 file(1, "/p/src/barrel.ts"),
364 file(2, "/p/src/consumer.ts"),
365 ];
366 let entry_points = vec![EntryPoint {
367 path: PathBuf::from("/p/src/consumer.ts"),
368 source: EntryPointSource::PackageJsonMain,
369 }];
370 let resolved = vec![
371 ResolvedModule {
372 file_id: FileId(0),
373 path: PathBuf::from("/p/src/impl.ts"),
374 exports: vec![named_export("widget")].into(),
375 ..Default::default()
376 },
377 ResolvedModule {
378 file_id: FileId(1),
379 path: PathBuf::from("/p/src/barrel.ts"),
380 re_exports: vec![ResolvedReExport {
381 info: ReExportInfo {
382 source: "./impl".to_string(),
383 imported_name: "widget".to_string(),
384 exported_name: "widget".to_string(),
385 is_type_only: false,
386 span: oxc_span::Span::new(0, 10),
387 statement_span: oxc_span::Span::new(0, 0),
388 source_span: oxc_span::Span::new(0, 0),
389 visibility: VisibilityTag::None,
390 expected_unused_reason: None,
391 },
392 target: ResolveResult::InternalModule(FileId(0)),
393 }],
394 ..Default::default()
395 },
396 ResolvedModule {
397 file_id: FileId(2),
398 path: PathBuf::from("/p/src/consumer.ts"),
399 resolved_imports: vec![named_import("./barrel", "widget", FileId(1))],
400 ..Default::default()
401 },
402 ];
403 ModuleGraph::build(&resolved, &entry_points, &files)
404 }
405
406 #[test]
407 fn reverse_dep_closure_equals_hand_computed_set() {
408 let graph = build_reverse_dep_graph();
409 let closure = graph.impact_closure(&[FileId(0)]);
411 assert_eq!(closure.in_diff, vec![FileId(0)]);
412 assert_eq!(closure.affected_not_shown, vec![FileId(1), FileId(2)]);
413 }
414
415 #[test]
416 fn coordination_gap_fires_when_consumer_outside_diff() {
417 let graph = build_reverse_dep_graph();
418 let closure = graph.impact_closure(&[FileId(0)]);
420 assert_eq!(closure.coordination_gap.len(), 1);
421 let gap = &closure.coordination_gap[0];
422 assert_eq!(gap.changed_file, FileId(0));
423 assert_eq!(gap.consumer_file, FileId(1));
424 assert_eq!(gap.consumed_symbols, vec!["compute".to_string()]);
425 }
426
427 #[test]
428 fn coordination_gap_skips_story_and_test_consumers() {
429 use fallow_types::discover::{EntryPoint, EntryPointSource};
430 let files = vec![
434 file(0, "/p/src/button.component.ts"),
435 file(1, "/p/src/button.stories.ts"),
436 file(2, "/p/src/panel.component.ts"),
437 ];
438 let entry_points = vec![EntryPoint {
439 path: PathBuf::from("/p/src/panel.component.ts"),
440 source: EntryPointSource::PackageJsonMain,
441 }];
442 let resolved = vec![
443 ResolvedModule {
444 file_id: FileId(0),
445 path: PathBuf::from("/p/src/button.component.ts"),
446 exports: vec![named_export("BzmButton")].into(),
447 ..Default::default()
448 },
449 ResolvedModule {
450 file_id: FileId(1),
451 path: PathBuf::from("/p/src/button.stories.ts"),
452 resolved_imports: vec![named_import("./button.component", "BzmButton", FileId(0))],
453 ..Default::default()
454 },
455 ResolvedModule {
456 file_id: FileId(2),
457 path: PathBuf::from("/p/src/panel.component.ts"),
458 resolved_imports: vec![named_import("./button.component", "BzmButton", FileId(0))],
459 ..Default::default()
460 },
461 ];
462 let graph = ModuleGraph::build(&resolved, &entry_points, &files);
463 let closure = graph.impact_closure(&[FileId(0)]);
464 assert_eq!(closure.coordination_gap.len(), 1);
466 assert_eq!(closure.coordination_gap[0].consumer_file, FileId(2));
467 assert!(closure.affected_not_shown.contains(&FileId(1)));
469 }
470
471 #[test]
472 fn coordination_gap_does_not_fire_when_consumer_inside_diff() {
473 let graph = build_reverse_dep_graph();
474 let closure = graph.impact_closure(&[FileId(0), FileId(1)]);
479 assert!(
480 closure
481 .coordination_gap
482 .iter()
483 .all(|gap| gap.consumer_file != FileId(0) && gap.consumer_file != FileId(1)),
484 "no gap may name an in-diff consumer: {:?}",
485 closure.coordination_gap
486 );
487 assert!(
489 !closure
490 .coordination_gap
491 .iter()
492 .any(|gap| gap.changed_file == FileId(0) && gap.consumer_file == FileId(1)),
493 "core->mid must not fire when mid is in the diff"
494 );
495 }
496
497 #[test]
498 fn re_export_chain_closure_equals_hand_computed_set() {
499 let graph = build_re_export_graph();
500 let closure = graph.impact_closure(&[FileId(0)]);
504 assert_eq!(closure.in_diff, vec![FileId(0)]);
505 assert_eq!(closure.affected_not_shown, vec![FileId(1), FileId(2)]);
506 }
507
508 #[test]
509 fn re_export_chain_coordination_gap_fires_through_barrel() {
510 let graph = build_re_export_graph();
511 let closure = graph.impact_closure(&[FileId(0)]);
516 assert_eq!(closure.coordination_gap.len(), 1);
517 let gap = &closure.coordination_gap[0];
518 assert_eq!(gap.changed_file, FileId(0));
519 assert_eq!(gap.consumer_file, FileId(2));
520 assert_eq!(gap.consumed_symbols, vec!["widget".to_string()]);
521 }
522
523 #[test]
524 fn coordination_gap_dedups_per_consumer_pair_r2() {
525 let files = vec![file(0, "/p/src/core.ts"), file(1, "/p/src/app.ts")];
528 let entry_points = vec![EntryPoint {
529 path: PathBuf::from("/p/src/app.ts"),
530 source: EntryPointSource::PackageJsonMain,
531 }];
532 let resolved = vec![
533 ResolvedModule {
534 file_id: FileId(0),
535 path: PathBuf::from("/p/src/core.ts"),
536 exports: vec![named_export("alpha"), named_export("beta")].into(),
537 ..Default::default()
538 },
539 ResolvedModule {
540 file_id: FileId(1),
541 path: PathBuf::from("/p/src/app.ts"),
542 resolved_imports: vec![
543 named_import("./core", "alpha", FileId(0)),
544 named_import("./core", "beta", FileId(0)),
545 ],
546 ..Default::default()
547 },
548 ];
549 let graph = ModuleGraph::build(&resolved, &entry_points, &files);
550 let closure = graph.impact_closure(&[FileId(0)]);
551 assert_eq!(
552 closure.coordination_gap.len(),
553 1,
554 "R2: one entry per consumer pair"
555 );
556 assert_eq!(
557 closure.coordination_gap[0].consumed_symbols,
558 vec!["alpha".to_string(), "beta".to_string()]
559 );
560 }
561
562 #[test]
563 fn closure_with_paths_relativizes_and_sorts() {
564 let graph = build_reverse_dep_graph();
565 let closure = graph.impact_closure(&[FileId(0)]);
566 let paths = graph.closure_with_paths(&closure, Path::new("/p"));
567 assert_eq!(paths.in_diff, vec!["src/core.ts".to_string()]);
568 assert_eq!(
569 paths.affected_not_shown,
570 vec!["src/app.ts".to_string(), "src/mid.ts".to_string()]
571 );
572 assert_eq!(paths.coordination_gap.len(), 1);
573 assert_eq!(paths.coordination_gap[0].changed_file, "src/core.ts");
574 assert_eq!(paths.coordination_gap[0].consumer_file, "src/mid.ts");
575 }
576
577 #[test]
578 fn closure_partitions_cyclic_graph_with_repeated_and_invalid_seeds() {
579 let mut graph = build_reverse_dep_graph();
580 graph.reverse_deps[2].push(FileId(0));
581 graph.reverse_deps[1].push(FileId(u32::MAX));
582
583 let closure = graph.impact_closure(&[FileId(1), FileId(u32::MAX), FileId(0), FileId(1)]);
584
585 assert_eq!(closure.in_diff, vec![FileId(0), FileId(1)]);
586 assert_eq!(closure.affected_not_shown, vec![FileId(2)]);
587 }
588
589 #[test]
590 fn empty_changed_set_yields_empty_closure() {
591 let graph = build_reverse_dep_graph();
592 let closure = graph.impact_closure(&[]);
593 assert!(closure.in_diff.is_empty());
594 assert!(closure.affected_not_shown.is_empty());
595 assert!(closure.coordination_gap.is_empty());
596 }
597}