1use std::ops::Range;
4
5use fixedbitset::FixedBitSet;
6use rustc_hash::FxHashSet;
7
8use fallow_types::discover::FileId;
9
10use super::types::ModuleNode;
11use super::{ImportedSymbol, ModuleGraph};
12
13#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
15pub struct CycleOptions {
16 pub ignore_lazy_imports: bool,
21}
22
23pub const MAX_CYCLES_PER_SCC: usize = 20;
26
27pub const MAX_CYCLE_LENGTH: usize = 12;
30
31#[derive(Debug, Default, Clone, PartialEq, Eq)]
33pub struct CycleSearch {
34 pub cycles: Vec<Vec<FileId>>,
37 pub capped_sccs: Vec<Vec<FileId>>,
41}
42
43impl ModuleGraph {
44 #[must_use]
57 pub fn find_cycles(&self) -> Vec<Vec<FileId>> {
58 self.find_cycles_with(CycleOptions::default())
59 }
60
61 #[must_use]
67 pub fn find_cycles_with(&self, options: CycleOptions) -> Vec<Vec<FileId>> {
68 self.find_cycles_accepting(options, &mut |_| false).cycles
69 }
70
71 #[must_use]
76 pub fn find_cycles_accepting(
77 &self,
78 options: CycleOptions,
79 accept: &mut dyn FnMut(&[FileId]) -> bool,
80 ) -> CycleSearch {
81 let n = self.modules.len();
82 if n == 0 {
83 return CycleSearch::default();
84 }
85
86 let (all_succs, succ_ranges) = self.build_runtime_successors(n, options);
87
88 let mut state = SccState::new(n);
89 for start_node in 0..n {
90 if state.indices[start_node] != u32::MAX {
91 continue;
92 }
93 state.run_dfs_from(start_node, &all_succs, &succ_ranges);
94 }
95
96 self.enumerate_cycles_from_sccs(&state.sccs, &all_succs, &succ_ranges, accept)
97 }
98
99 fn build_runtime_successors(
104 &self,
105 n: usize,
106 options: CycleOptions,
107 ) -> (Vec<usize>, Vec<Range<usize>>) {
108 let mut all_succs: Vec<usize> = Vec::with_capacity(self.edges.len());
109 let mut succ_ranges: Vec<Range<usize>> = Vec::with_capacity(n);
110 let mut seen_set = FxHashSet::default();
111 for module in &self.modules {
112 let start = all_succs.len();
113 seen_set.clear();
114 for edge in &self.edges[module.edge_range.clone()] {
115 if edge
116 .symbols
117 .iter()
118 .all(|s| s.is_type_only || !s.loads_target())
119 {
120 continue;
121 }
122 if options.ignore_lazy_imports
123 && !edge.symbols.iter().any(ImportedSymbol::is_eager_value)
124 {
125 continue;
126 }
127 let target = edge.target.0 as usize;
128 if target < n && seen_set.insert(target) {
129 all_succs.push(target);
130 }
131 }
132 let end = all_succs.len();
133 succ_ranges.push(start..end);
134 }
135 (all_succs, succ_ranges)
136 }
137
138 #[expect(
140 clippy::cast_possible_truncation,
141 reason = "file count is bounded by project size, well under u32::MAX"
142 )]
143 fn enumerate_cycles_from_sccs(
144 &self,
145 sccs: &[Vec<FileId>],
146 all_succs: &[usize],
147 succ_ranges: &[Range<usize>],
148 accept: &mut dyn FnMut(&[FileId]) -> bool,
149 ) -> CycleSearch {
150 let succs = SuccessorMap {
151 all_succs,
152 succ_ranges,
153 modules: &self.modules,
154 };
155
156 let mut result: Vec<Vec<FileId>> = Vec::new();
157 let mut capped_sccs: Vec<Vec<FileId>> = Vec::new();
158 let mut seen_cycles: FxHashSet<Vec<u32>> = FxHashSet::default();
159
160 for scc in sccs {
161 if scc.len() == 2 {
162 let mut cycle = vec![scc[0].0 as usize, scc[1].0 as usize];
163 if self.modules[cycle[1]].path < self.modules[cycle[0]].path {
164 cycle.swap(0, 1);
165 }
166 let key: Vec<u32> = cycle.iter().map(|&n| n as u32).collect();
167 let files: Vec<FileId> = cycle.into_iter().map(|n| FileId(n as u32)).collect();
168 if seen_cycles.insert(key) && !accept(&files) {
169 result.push(files);
170 }
171 continue;
172 }
173
174 let scc_nodes: Vec<usize> = scc.iter().map(|id| id.0 as usize).collect();
175 let (elementary, capped) =
176 enumerate_elementary_cycles(&scc_nodes, &succs, MAX_CYCLES_PER_SCC, accept);
177 if capped {
178 capped_sccs.push(scc.clone());
179 }
180
181 for cycle in elementary {
182 let key: Vec<u32> = cycle.iter().map(|&n| n as u32).collect();
183 if seen_cycles.insert(key) {
184 result.push(cycle.into_iter().map(|n| FileId(n as u32)).collect());
185 }
186 }
187 }
188
189 result.sort_by(|a, b| {
190 a.len().cmp(&b.len()).then_with(|| {
191 self.modules[a[0].0 as usize]
192 .path
193 .cmp(&self.modules[b[0].0 as usize].path)
194 })
195 });
196
197 CycleSearch {
198 cycles: result,
199 capped_sccs,
200 }
201 }
202}
203
204struct SccFrame {
206 node: usize,
207 succ_pos: usize,
208 succ_end: usize,
209}
210
211struct SccState {
213 index_counter: u32,
214 indices: Vec<u32>,
215 lowlinks: Vec<u32>,
216 on_stack: FixedBitSet,
217 stack: Vec<usize>,
218 sccs: Vec<Vec<FileId>>,
219}
220
221impl SccState {
222 fn new(n: usize) -> Self {
223 Self {
224 index_counter: 0,
225 indices: vec![u32::MAX; n],
226 lowlinks: vec![0; n],
227 on_stack: FixedBitSet::with_capacity(n),
228 stack: Vec::new(),
229 sccs: Vec::new(),
230 }
231 }
232
233 fn discover(&mut self, node: usize) {
235 self.indices[node] = self.index_counter;
236 self.lowlinks[node] = self.index_counter;
237 self.index_counter += 1;
238 self.on_stack.insert(node);
239 self.stack.push(node);
240 }
241
242 fn frame_for(node: usize, succ_ranges: &[Range<usize>]) -> SccFrame {
244 let range = &succ_ranges[node];
245 SccFrame {
246 node,
247 succ_pos: range.start,
248 succ_end: range.end,
249 }
250 }
251
252 fn run_dfs_from(&mut self, start: usize, all_succs: &[usize], succ_ranges: &[Range<usize>]) {
255 self.discover(start);
256 let mut dfs_stack: Vec<SccFrame> = vec![Self::frame_for(start, succ_ranges)];
257
258 while let Some(frame) = dfs_stack.last_mut() {
259 if frame.succ_pos < frame.succ_end {
260 if let Some(child) = self.advance_frame(frame, all_succs) {
261 dfs_stack.push(Self::frame_for(child, succ_ranges));
262 }
263 } else {
264 let v = frame.node;
265 let v_lowlink = self.lowlinks[v];
266 dfs_stack.pop();
267 if let Some(parent) = dfs_stack.last() {
268 let pv = parent.node;
269 self.lowlinks[pv] = self.lowlinks[pv].min(v_lowlink);
270 }
271 self.collect_root_scc(v);
272 }
273 }
274 }
275
276 fn advance_frame(&mut self, frame: &mut SccFrame, all_succs: &[usize]) -> Option<usize> {
279 let w = all_succs[frame.succ_pos];
280 frame.succ_pos += 1;
281 if self.indices[w] == u32::MAX {
282 self.discover(w);
283 Some(w)
284 } else {
285 if self.on_stack.contains(w) {
286 let v = frame.node;
287 self.lowlinks[v] = self.lowlinks[v].min(self.indices[w]);
288 }
289 None
290 }
291 }
292
293 #[expect(
296 clippy::cast_possible_truncation,
297 reason = "file count is bounded by project size, well under u32::MAX"
298 )]
299 #[expect(
300 clippy::expect_used,
301 reason = "Tarjan traversal only pops nodes that were pushed onto the SCC stack"
302 )]
303 fn collect_root_scc(&mut self, v: usize) {
304 if self.lowlinks[v] != self.indices[v] {
305 return;
306 }
307 let mut scc = Vec::new();
308 loop {
309 let w = self.stack.pop().expect("SCC stack should not be empty");
310 self.on_stack.set(w, false);
311 scc.push(FileId(w as u32));
312 if w == v {
313 break;
314 }
315 }
316 if scc.len() >= 2 {
317 self.sccs.push(scc);
318 }
319 }
320}
321
322fn canonical_cycle(cycle: &[usize], modules: &[ModuleNode]) -> Vec<usize> {
324 if cycle.is_empty() {
325 return Vec::new();
326 }
327 let min_pos = cycle
328 .iter()
329 .enumerate()
330 .min_by(|(_, a), (_, b)| modules[**a].path.cmp(&modules[**b].path))
331 .map_or(0, |(i, _)| i);
332 let mut result = cycle[min_pos..].to_vec();
333 result.extend_from_slice(&cycle[..min_pos]);
334 result
335}
336
337struct CycleFrame {
338 succ_pos: usize,
339 succ_end: usize,
340}
341
342struct SuccessorMap<'a> {
343 all_succs: &'a [usize],
344 succ_ranges: &'a [Range<usize>],
345 modules: &'a [ModuleNode],
346}
347
348#[expect(
349 clippy::cast_possible_truncation,
350 reason = "file count is bounded by project size, well under u32::MAX"
351)]
352fn try_record_cycle(
353 path: &[usize],
354 modules: &[ModuleNode],
355 seen: &mut FxHashSet<Vec<u32>>,
356 cycles: &mut Vec<Vec<usize>>,
357 accept: &mut dyn FnMut(&[FileId]) -> bool,
358) {
359 let canonical = canonical_cycle(path, modules);
360 let key: Vec<u32> = canonical.iter().map(|&n| n as u32).collect();
361 if !seen.insert(key) {
362 return;
363 }
364 let files: Vec<FileId> = canonical.iter().map(|&n| FileId(n as u32)).collect();
365 if !accept(&files) {
366 cycles.push(canonical);
367 }
368}
369
370struct DfsCycleInput<'a> {
375 start: usize,
376 depth_limit: usize,
377 scc_set: &'a FxHashSet<usize>,
378 succs: &'a SuccessorMap<'a>,
379 max_cycles: usize,
380 seen: &'a mut FxHashSet<Vec<u32>>,
381 cycles: &'a mut Vec<Vec<usize>>,
382 accept: &'a mut dyn FnMut(&[FileId]) -> bool,
383}
384
385fn dfs_find_cycles_from(input: &mut DfsCycleInput<'_>) {
386 let mut path: Vec<usize> = vec![input.start];
387 let mut path_set = FixedBitSet::with_capacity(input.succs.modules.len());
388 path_set.insert(input.start);
389
390 let range = &input.succs.succ_ranges[input.start];
391 let mut dfs: Vec<CycleFrame> = vec![CycleFrame {
392 succ_pos: range.start,
393 succ_end: range.end,
394 }];
395
396 while let Some(frame) = dfs.last_mut() {
397 if input.cycles.len() >= input.max_cycles {
398 return;
399 }
400
401 if frame.succ_pos >= frame.succ_end {
402 dfs.pop();
403 if path.len() > 1 {
404 let Some(removed) = path.pop() else {
405 continue;
406 };
407 path_set.set(removed, false);
408 }
409 continue;
410 }
411
412 let w = input.succs.all_succs[frame.succ_pos];
413 frame.succ_pos += 1;
414
415 if !input.scc_set.contains(&w) {
416 continue;
417 }
418
419 if w == input.start && path.len() >= 2 && path.len() == input.depth_limit {
420 try_record_cycle(
421 &path,
422 input.succs.modules,
423 input.seen,
424 input.cycles,
425 input.accept,
426 );
427 continue;
428 }
429
430 if path_set.contains(w) || path.len() >= input.depth_limit {
431 continue;
432 }
433
434 path.push(w);
435 path_set.insert(w);
436
437 let range = &input.succs.succ_ranges[w];
438 dfs.push(CycleFrame {
439 succ_pos: range.start,
440 succ_end: range.end,
441 });
442 }
443}
444
445fn enumerate_elementary_cycles(
453 scc_nodes: &[usize],
454 succs: &SuccessorMap<'_>,
455 max_cycles: usize,
456 accept: &mut dyn FnMut(&[FileId]) -> bool,
457) -> (Vec<Vec<usize>>, bool) {
458 let scc_set: FxHashSet<usize> = scc_nodes.iter().copied().collect();
459 let mut cycles: Vec<Vec<usize>> = Vec::new();
460 let mut seen: FxHashSet<Vec<u32>> = FxHashSet::default();
461
462 let mut sorted_nodes: Vec<usize> = scc_nodes.to_vec();
463 sorted_nodes.sort_by(|a, b| succs.modules[*a].path.cmp(&succs.modules[*b].path));
464
465 let max_depth = scc_nodes.len().min(MAX_CYCLE_LENGTH);
466 for depth_limit in 2..=max_depth {
467 if cycles.len() >= max_cycles {
468 break;
469 }
470
471 for &start in &sorted_nodes {
472 if cycles.len() >= max_cycles {
473 break;
474 }
475
476 dfs_find_cycles_from(&mut DfsCycleInput {
477 start,
478 depth_limit,
479 scc_set: &scc_set,
480 succs,
481 max_cycles,
482 seen: &mut seen,
483 cycles: &mut cycles,
484 accept,
485 });
486 }
487 }
488
489 let capped = cycles.len() >= max_cycles;
490 (cycles, capped)
491}
492
493#[cfg(test)]
494mod tests {
495 use std::ops::Range;
496 use std::path::PathBuf;
497
498 use rustc_hash::FxHashSet;
499
500 use crate::graph::types::ModuleNode;
501 use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};
502 use fallow_types::discover::{DiscoveredFile, EntryPoint, EntryPointSource, FileId};
503 use fallow_types::extract::{ExportName, ImportInfo, ImportedName, VisibilityTag};
504
505 use super::{
506 DfsCycleInput, ModuleGraph, SuccessorMap, canonical_cycle, dfs_find_cycles_from,
507 enumerate_elementary_cycles, try_record_cycle,
508 };
509
510 #[expect(
512 clippy::cast_possible_truncation,
513 reason = "test file counts are trivially small"
514 )]
515 fn build_cycle_graph(file_count: usize, edges_spec: &[(u32, u32)]) -> ModuleGraph {
516 let files: Vec<DiscoveredFile> = (0..file_count)
517 .map(|i| DiscoveredFile {
518 id: FileId(i as u32),
519 path: PathBuf::from(format!("/project/file{i}.ts")),
520 size_bytes: 100,
521 })
522 .collect();
523
524 let resolved_modules: Vec<ResolvedModule> = (0..file_count)
525 .map(|i| {
526 let imports: Vec<ResolvedImport> = edges_spec
527 .iter()
528 .filter(|(src, _)| *src == i as u32)
529 .map(|(_, tgt)| ResolvedImport {
530 info: ImportInfo {
531 source: format!("./file{tgt}"),
532 imported_name: ImportedName::Named("x".to_string()),
533 local_name: "x".to_string(),
534 is_type_only: false,
535 is_type_only_star: false,
536 from_style: false,
537 span: oxc_span::Span::new(0, 10),
538 source_span: oxc_span::Span::default(),
539 },
540 target: ResolveResult::InternalModule(FileId(*tgt)),
541 })
542 .collect();
543
544 ResolvedModule {
545 file_id: FileId(i as u32),
546 path: PathBuf::from(format!("/project/file{i}.ts")),
547 exports: vec![fallow_types::extract::ExportInfo {
548 name: ExportName::Named("x".to_string()),
549 local_name: Some("x".to_string()),
550 is_type_only: false,
551 visibility: VisibilityTag::None,
552 expected_unused_reason: None,
553 span: oxc_span::Span::new(0, 20),
554 members: vec![],
555 is_side_effect_used: false,
556 super_class: None,
557 deprecated: false,
558 deprecated_reason: None,
559 }]
560 .into(),
561 re_exports: vec![],
562 resolved_imports: imports,
563 resolved_dynamic_imports: vec![],
564 resolved_dynamic_patterns: vec![],
565 member_accesses: vec![].into(),
566 semantic_facts: std::sync::Arc::default(),
567 whole_object_uses: std::sync::Arc::default(),
568 has_cjs_exports: false,
569 has_angular_component_template_url: false,
570 unused_import_bindings: FxHashSet::default(),
571 type_referenced_import_bindings: vec![],
572 value_referenced_import_bindings: vec![],
573 namespace_object_aliases: vec![],
574 exported_factory_returns: std::sync::Arc::default(),
575 exported_factory_return_object_shapes: std::sync::Arc::default(),
576 type_member_types: std::sync::Arc::default(),
577 missing_export_targets: vec![],
578 }
579 })
580 .collect();
581
582 let entry_points = vec![EntryPoint {
583 path: PathBuf::from("/project/file0.ts"),
584 source: EntryPointSource::PackageJsonMain,
585 }];
586
587 ModuleGraph::build(&resolved_modules, &entry_points, &files)
588 }
589
590 fn dfs_find_cycles_from_for_test(mut input: DfsCycleInput<'_>) {
591 dfs_find_cycles_from(&mut input);
592 }
593
594 #[test]
595 fn find_cycles_empty_graph() {
596 let graph = ModuleGraph::build(&[], &[], &[]);
597 assert!(graph.find_cycles().is_empty());
598 }
599
600 #[test]
601 fn find_cycles_no_cycles() {
602 let graph = build_cycle_graph(3, &[(0, 1), (1, 2)]);
603 assert!(graph.find_cycles().is_empty());
604 }
605
606 #[test]
607 fn find_cycles_simple_two_node_cycle() {
608 let graph = build_cycle_graph(2, &[(0, 1), (1, 0)]);
609 let cycles = graph.find_cycles();
610 assert_eq!(cycles.len(), 1);
611 assert_eq!(cycles[0].len(), 2);
612 }
613
614 #[test]
615 fn find_cycles_three_node_cycle() {
616 let graph = build_cycle_graph(3, &[(0, 1), (1, 2), (2, 0)]);
617 let cycles = graph.find_cycles();
618 assert_eq!(cycles.len(), 1);
619 assert_eq!(cycles[0].len(), 3);
620 }
621
622 #[test]
623 fn find_cycles_self_import_ignored() {
624 let graph = build_cycle_graph(1, &[(0, 0)]);
625 let cycles = graph.find_cycles();
626 assert!(
627 cycles.is_empty(),
628 "self-imports should not be reported as cycles"
629 );
630 }
631
632 #[test]
633 fn find_cycles_multiple_independent_cycles() {
634 let graph = build_cycle_graph(4, &[(0, 1), (1, 0), (2, 3), (3, 2)]);
635 let cycles = graph.find_cycles();
636 assert_eq!(cycles.len(), 2);
637 assert!(cycles.iter().all(|c| c.len() == 2));
638 }
639
640 #[test]
641 fn find_cycles_linear_chain_with_back_edge() {
642 let graph = build_cycle_graph(4, &[(0, 1), (1, 2), (2, 3), (3, 1)]);
643 let cycles = graph.find_cycles();
644 assert_eq!(cycles.len(), 1);
645 assert_eq!(cycles[0].len(), 3);
646 let ids: Vec<u32> = cycles[0].iter().map(|f| f.0).collect();
647 assert!(ids.contains(&1));
648 assert!(ids.contains(&2));
649 assert!(ids.contains(&3));
650 assert!(!ids.contains(&0));
651 }
652
653 #[test]
654 fn find_cycles_overlapping_cycles_enumerated() {
655 let graph = build_cycle_graph(3, &[(0, 1), (1, 0), (1, 2), (2, 1)]);
656 let cycles = graph.find_cycles();
657 assert_eq!(
658 cycles.len(),
659 2,
660 "should find 2 elementary cycles, not 1 SCC"
661 );
662 assert!(
663 cycles.iter().all(|c| c.len() == 2),
664 "both cycles should have length 2"
665 );
666 }
667
668 #[test]
669 fn find_cycles_deterministic_ordering() {
670 let graph1 = build_cycle_graph(3, &[(0, 1), (1, 2), (2, 0)]);
671 let graph2 = build_cycle_graph(3, &[(0, 1), (1, 2), (2, 0)]);
672 let cycles1 = graph1.find_cycles();
673 let cycles2 = graph2.find_cycles();
674 assert_eq!(cycles1.len(), cycles2.len());
675 for (c1, c2) in cycles1.iter().zip(cycles2.iter()) {
676 let paths1: Vec<&PathBuf> = c1
677 .iter()
678 .map(|f| &graph1.modules[f.0 as usize].path)
679 .collect();
680 let paths2: Vec<&PathBuf> = c2
681 .iter()
682 .map(|f| &graph2.modules[f.0 as usize].path)
683 .collect();
684 assert_eq!(paths1, paths2);
685 }
686 }
687
688 #[test]
689 fn find_cycles_sorted_by_length() {
690 let graph = build_cycle_graph(5, &[(0, 1), (1, 0), (2, 3), (3, 4), (4, 2)]);
691 let cycles = graph.find_cycles();
692 assert_eq!(cycles.len(), 2);
693 assert!(
694 cycles[0].len() <= cycles[1].len(),
695 "cycles should be sorted by length"
696 );
697 }
698
699 #[test]
700 fn find_cycles_large_cycle() {
701 let edges: Vec<(u32, u32)> = (0..10).map(|i| (i, (i + 1) % 10)).collect();
702 let graph = build_cycle_graph(10, &edges);
703 let cycles = graph.find_cycles();
704 assert_eq!(cycles.len(), 1);
705 assert_eq!(cycles[0].len(), 10);
706 }
707
708 #[test]
709 fn find_cycles_complex_scc_multiple_elementary() {
710 let graph = build_cycle_graph(4, &[(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]);
711 let cycles = graph.find_cycles();
712 assert!(
713 cycles.len() >= 2,
714 "should find at least 2 elementary cycles, got {}",
715 cycles.len()
716 );
717 assert!(cycles.iter().all(|c| c.len() <= 4));
718 }
719
720 #[test]
721 fn find_cycles_no_duplicate_cycles() {
722 let graph = build_cycle_graph(3, &[(0, 1), (1, 2), (2, 0)]);
723 let cycles = graph.find_cycles();
724 assert_eq!(cycles.len(), 1, "triangle should produce exactly 1 cycle");
725 assert_eq!(cycles[0].len(), 3);
726 }
727
728 #[expect(
733 clippy::cast_possible_truncation,
734 reason = "test file counts are trivially small"
735 )]
736 fn build_test_succs(
737 file_count: usize,
738 edges_spec: &[(usize, usize)],
739 ) -> (Vec<ModuleNode>, Vec<usize>, Vec<Range<usize>>) {
740 let modules: Vec<ModuleNode> = (0..file_count)
741 .map(|i| {
742 let mut node = ModuleNode {
743 file_id: FileId(i as u32),
744 path: PathBuf::from(format!("/project/file{i}.ts")),
745 edge_range: 0..0,
746 exports: vec![],
747 re_exports: vec![],
748 flags: ModuleNode::flags_from(i == 0, true, false),
749 };
750 node.set_reachable(true);
751 node
752 })
753 .collect();
754
755 let mut all_succs: Vec<usize> = Vec::new();
756 let mut succ_ranges: Vec<Range<usize>> = Vec::with_capacity(file_count);
757 for src in 0..file_count {
758 let start = all_succs.len();
759 let mut seen = FxHashSet::default();
760 for &(s, t) in edges_spec {
761 if s == src && t < file_count && seen.insert(t) {
762 all_succs.push(t);
763 }
764 }
765 let end = all_succs.len();
766 succ_ranges.push(start..end);
767 }
768
769 (modules, all_succs, succ_ranges)
770 }
771
772 #[test]
773 fn canonical_cycle_empty() {
774 let modules: Vec<ModuleNode> = vec![];
775 assert!(canonical_cycle(&[], &modules).is_empty());
776 }
777
778 #[test]
779 fn canonical_cycle_rotates_to_smallest_path() {
780 let (modules, _, _) = build_test_succs(3, &[]);
781 let result = canonical_cycle(&[2, 0, 1], &modules);
782 assert_eq!(result, vec![0, 1, 2]);
783 }
784
785 #[test]
786 fn canonical_cycle_already_canonical() {
787 let (modules, _, _) = build_test_succs(3, &[]);
788 let result = canonical_cycle(&[0, 1, 2], &modules);
789 assert_eq!(result, vec![0, 1, 2]);
790 }
791
792 #[test]
793 fn canonical_cycle_single_node() {
794 let (modules, _, _) = build_test_succs(1, &[]);
795 let result = canonical_cycle(&[0], &modules);
796 assert_eq!(result, vec![0]);
797 }
798
799 #[test]
800 fn try_record_cycle_inserts_new_cycle() {
801 let (modules, _, _) = build_test_succs(3, &[]);
802 let mut seen = FxHashSet::default();
803 let mut cycles = Vec::new();
804
805 try_record_cycle(&[0, 1, 2], &modules, &mut seen, &mut cycles, &mut |_| false);
806 assert_eq!(cycles.len(), 1);
807 assert_eq!(cycles[0], vec![0, 1, 2]);
808 }
809
810 #[test]
811 fn try_record_cycle_deduplicates_rotated_cycle() {
812 let (modules, _, _) = build_test_succs(3, &[]);
813 let mut seen = FxHashSet::default();
814 let mut cycles = Vec::new();
815
816 try_record_cycle(&[0, 1, 2], &modules, &mut seen, &mut cycles, &mut |_| false);
817 try_record_cycle(&[1, 2, 0], &modules, &mut seen, &mut cycles, &mut |_| false);
818 try_record_cycle(&[2, 0, 1], &modules, &mut seen, &mut cycles, &mut |_| false);
819
820 assert_eq!(
821 cycles.len(),
822 1,
823 "rotations of the same cycle should be deduped"
824 );
825 }
826
827 #[test]
828 fn try_record_cycle_single_node_self_loop() {
829 let (modules, _, _) = build_test_succs(1, &[]);
830 let mut seen = FxHashSet::default();
831 let mut cycles = Vec::new();
832
833 try_record_cycle(&[0], &modules, &mut seen, &mut cycles, &mut |_| false);
834 assert_eq!(cycles.len(), 1);
835 assert_eq!(cycles[0], vec![0]);
836 }
837
838 #[test]
839 fn try_record_cycle_distinct_cycles_both_recorded() {
840 let (modules, _, _) = build_test_succs(4, &[]);
841 let mut seen = FxHashSet::default();
842 let mut cycles = Vec::new();
843
844 try_record_cycle(&[0, 1], &modules, &mut seen, &mut cycles, &mut |_| false);
845 try_record_cycle(&[2, 3], &modules, &mut seen, &mut cycles, &mut |_| false);
846
847 assert_eq!(cycles.len(), 2);
848 }
849
850 #[test]
851 fn successor_map_empty_graph() {
852 let (modules, all_succs, succ_ranges) = build_test_succs(0, &[]);
853 let succs = SuccessorMap {
854 all_succs: &all_succs,
855 succ_ranges: &succ_ranges,
856 modules: &modules,
857 };
858 assert!(succs.all_succs.is_empty());
859 assert!(succs.succ_ranges.is_empty());
860 }
861
862 #[test]
863 fn successor_map_single_node_self_edge() {
864 let (modules, all_succs, succ_ranges) = build_test_succs(1, &[(0, 0)]);
865 let succs = SuccessorMap {
866 all_succs: &all_succs,
867 succ_ranges: &succ_ranges,
868 modules: &modules,
869 };
870 assert_eq!(succs.all_succs.len(), 1);
871 assert_eq!(succs.all_succs[0], 0);
872 assert_eq!(succs.succ_ranges[0], 0..1);
873 }
874
875 #[test]
876 fn successor_map_deduplicates_edges() {
877 let (modules, all_succs, succ_ranges) = build_test_succs(2, &[(0, 1), (0, 1)]);
878 let succs = SuccessorMap {
879 all_succs: &all_succs,
880 succ_ranges: &succ_ranges,
881 modules: &modules,
882 };
883 let range = &succs.succ_ranges[0];
884 assert_eq!(
885 range.end - range.start,
886 1,
887 "duplicate edges should be deduped"
888 );
889 }
890
891 #[test]
892 fn successor_map_multiple_successors() {
893 let (modules, all_succs, succ_ranges) = build_test_succs(4, &[(0, 1), (0, 2), (0, 3)]);
894 let succs = SuccessorMap {
895 all_succs: &all_succs,
896 succ_ranges: &succ_ranges,
897 modules: &modules,
898 };
899 let range = &succs.succ_ranges[0];
900 assert_eq!(range.end - range.start, 3);
901 for r in &succs.succ_ranges[1..4] {
902 assert_eq!(r.end - r.start, 0);
903 }
904 }
905
906 #[test]
907 fn dfs_find_cycles_from_isolated_node() {
908 let (modules, all_succs, succ_ranges) = build_test_succs(1, &[]);
909 let succs = SuccessorMap {
910 all_succs: &all_succs,
911 succ_ranges: &succ_ranges,
912 modules: &modules,
913 };
914 let scc_set: FxHashSet<usize> = std::iter::once(0).collect();
915 let mut seen = FxHashSet::default();
916 let mut cycles = Vec::new();
917
918 dfs_find_cycles_from_for_test(DfsCycleInput {
919 start: 0,
920 depth_limit: 2,
921 scc_set: &scc_set,
922 succs: &succs,
923 max_cycles: 10,
924 accept: &mut |_| false,
925 seen: &mut seen,
926 cycles: &mut cycles,
927 });
928 assert!(cycles.is_empty(), "isolated node should have no cycles");
929 }
930
931 #[test]
932 fn dfs_find_cycles_from_simple_two_cycle() {
933 let (modules, all_succs, succ_ranges) = build_test_succs(2, &[(0, 1), (1, 0)]);
934 let succs = SuccessorMap {
935 all_succs: &all_succs,
936 succ_ranges: &succ_ranges,
937 modules: &modules,
938 };
939 let scc_set: FxHashSet<usize> = [0, 1].into_iter().collect();
940 let mut seen = FxHashSet::default();
941 let mut cycles = Vec::new();
942
943 dfs_find_cycles_from_for_test(DfsCycleInput {
944 start: 0,
945 depth_limit: 2,
946 scc_set: &scc_set,
947 succs: &succs,
948 max_cycles: 10,
949 accept: &mut |_| false,
950 seen: &mut seen,
951 cycles: &mut cycles,
952 });
953 assert_eq!(cycles.len(), 1);
954 assert_eq!(cycles[0].len(), 2);
955 }
956
957 #[test]
958 fn dfs_find_cycles_from_diamond_graph() {
959 let (modules, all_succs, succ_ranges) =
960 build_test_succs(4, &[(0, 1), (0, 2), (1, 3), (2, 3), (3, 0)]);
961 let succs = SuccessorMap {
962 all_succs: &all_succs,
963 succ_ranges: &succ_ranges,
964 modules: &modules,
965 };
966 let scc_set: FxHashSet<usize> = [0, 1, 2, 3].into_iter().collect();
967 let mut seen = FxHashSet::default();
968 let mut cycles = Vec::new();
969
970 dfs_find_cycles_from_for_test(DfsCycleInput {
971 start: 0,
972 depth_limit: 3,
973 scc_set: &scc_set,
974 succs: &succs,
975 max_cycles: 10,
976 accept: &mut |_| false,
977 seen: &mut seen,
978 cycles: &mut cycles,
979 });
980 assert_eq!(cycles.len(), 2, "diamond should have two 3-node cycles");
981 assert!(cycles.iter().all(|c| c.len() == 3));
982 }
983
984 #[test]
985 fn dfs_find_cycles_from_depth_limit_prevents_longer_cycles() {
986 let (modules, all_succs, succ_ranges) =
987 build_test_succs(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]);
988 let succs = SuccessorMap {
989 all_succs: &all_succs,
990 succ_ranges: &succ_ranges,
991 modules: &modules,
992 };
993 let scc_set: FxHashSet<usize> = [0, 1, 2, 3].into_iter().collect();
994 let mut seen = FxHashSet::default();
995 let mut cycles = Vec::new();
996
997 dfs_find_cycles_from_for_test(DfsCycleInput {
998 start: 0,
999 depth_limit: 3,
1000 scc_set: &scc_set,
1001 succs: &succs,
1002 max_cycles: 10,
1003 accept: &mut |_| false,
1004 seen: &mut seen,
1005 cycles: &mut cycles,
1006 });
1007 assert!(
1008 cycles.is_empty(),
1009 "depth_limit=3 should prevent finding a 4-node cycle"
1010 );
1011 }
1012
1013 #[test]
1014 fn dfs_find_cycles_from_depth_limit_exact_match() {
1015 let (modules, all_succs, succ_ranges) =
1016 build_test_succs(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]);
1017 let succs = SuccessorMap {
1018 all_succs: &all_succs,
1019 succ_ranges: &succ_ranges,
1020 modules: &modules,
1021 };
1022 let scc_set: FxHashSet<usize> = [0, 1, 2, 3].into_iter().collect();
1023 let mut seen = FxHashSet::default();
1024 let mut cycles = Vec::new();
1025
1026 dfs_find_cycles_from_for_test(DfsCycleInput {
1027 start: 0,
1028 depth_limit: 4,
1029 scc_set: &scc_set,
1030 succs: &succs,
1031 max_cycles: 10,
1032 accept: &mut |_| false,
1033 seen: &mut seen,
1034 cycles: &mut cycles,
1035 });
1036 assert_eq!(
1037 cycles.len(),
1038 1,
1039 "depth_limit=4 should find the 4-node cycle"
1040 );
1041 assert_eq!(cycles[0].len(), 4);
1042 }
1043
1044 #[test]
1045 fn dfs_find_cycles_from_respects_max_cycles() {
1046 let edges: Vec<(usize, usize)> = (0..4)
1047 .flat_map(|i| (0..4).filter(move |&j| i != j).map(move |j| (i, j)))
1048 .collect();
1049 let (modules, all_succs, succ_ranges) = build_test_succs(4, &edges);
1050 let succs = SuccessorMap {
1051 all_succs: &all_succs,
1052 succ_ranges: &succ_ranges,
1053 modules: &modules,
1054 };
1055 let scc_set: FxHashSet<usize> = (0..4).collect();
1056 let mut seen = FxHashSet::default();
1057 let mut cycles = Vec::new();
1058
1059 dfs_find_cycles_from_for_test(DfsCycleInput {
1060 start: 0,
1061 depth_limit: 2,
1062 scc_set: &scc_set,
1063 succs: &succs,
1064 max_cycles: 2,
1065 accept: &mut |_| false,
1066 seen: &mut seen,
1067 cycles: &mut cycles,
1068 });
1069 assert!(
1070 cycles.len() <= 2,
1071 "should respect max_cycles limit, got {}",
1072 cycles.len()
1073 );
1074 }
1075
1076 #[test]
1077 fn dfs_find_cycles_from_ignores_nodes_outside_scc() {
1078 let (modules, all_succs, succ_ranges) = build_test_succs(3, &[(0, 1), (1, 2), (2, 0)]);
1079 let succs = SuccessorMap {
1080 all_succs: &all_succs,
1081 succ_ranges: &succ_ranges,
1082 modules: &modules,
1083 };
1084 let scc_set: FxHashSet<usize> = [0, 1].into_iter().collect();
1085 let mut seen = FxHashSet::default();
1086 let mut cycles = Vec::new();
1087
1088 for depth in 2..=3 {
1089 dfs_find_cycles_from_for_test(DfsCycleInput {
1090 start: 0,
1091 depth_limit: depth,
1092 scc_set: &scc_set,
1093 succs: &succs,
1094 max_cycles: 10,
1095 accept: &mut |_| false,
1096 seen: &mut seen,
1097 cycles: &mut cycles,
1098 });
1099 }
1100 assert!(
1101 cycles.is_empty(),
1102 "should not find cycles through nodes outside the SCC set"
1103 );
1104 }
1105
1106 #[test]
1107 fn enumerate_elementary_cycles_empty_scc() {
1108 let (modules, all_succs, succ_ranges) = build_test_succs(0, &[]);
1109 let succs = SuccessorMap {
1110 all_succs: &all_succs,
1111 succ_ranges: &succ_ranges,
1112 modules: &modules,
1113 };
1114 let cycles = enumerate_elementary_cycles(&[], &succs, 10, &mut |_| false).0;
1115 assert!(cycles.is_empty());
1116 }
1117
1118 #[test]
1119 fn enumerate_elementary_cycles_max_cycles_limit() {
1120 let edges: Vec<(usize, usize)> = (0..4)
1121 .flat_map(|i| (0..4).filter(move |&j| i != j).map(move |j| (i, j)))
1122 .collect();
1123 let (modules, all_succs, succ_ranges) = build_test_succs(4, &edges);
1124 let succs = SuccessorMap {
1125 all_succs: &all_succs,
1126 succ_ranges: &succ_ranges,
1127 modules: &modules,
1128 };
1129 let scc_nodes: Vec<usize> = (0..4).collect();
1130
1131 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 3, &mut |_| false).0;
1132 assert!(
1133 cycles.len() <= 3,
1134 "should respect max_cycles=3 limit, got {}",
1135 cycles.len()
1136 );
1137 }
1138
1139 #[test]
1140 fn enumerate_elementary_cycles_finds_all_in_triangle() {
1141 let (modules, all_succs, succ_ranges) = build_test_succs(3, &[(0, 1), (1, 2), (2, 0)]);
1142 let succs = SuccessorMap {
1143 all_succs: &all_succs,
1144 succ_ranges: &succ_ranges,
1145 modules: &modules,
1146 };
1147 let scc_nodes: Vec<usize> = vec![0, 1, 2];
1148
1149 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 20, &mut |_| false).0;
1150 assert_eq!(cycles.len(), 1);
1151 assert_eq!(cycles[0].len(), 3);
1152 }
1153
1154 #[test]
1155 fn enumerate_elementary_cycles_iterative_deepening_order() {
1156 let (modules, all_succs, succ_ranges) =
1157 build_test_succs(3, &[(0, 1), (1, 0), (1, 2), (2, 0)]);
1158 let succs = SuccessorMap {
1159 all_succs: &all_succs,
1160 succ_ranges: &succ_ranges,
1161 modules: &modules,
1162 };
1163 let scc_nodes: Vec<usize> = vec![0, 1, 2];
1164
1165 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 20, &mut |_| false).0;
1166 assert!(cycles.len() >= 2, "should find at least 2 cycles");
1167 assert!(
1168 cycles[0].len() <= cycles[cycles.len() - 1].len(),
1169 "shorter cycles should be found before longer ones"
1170 );
1171 }
1172
1173 #[test]
1174 fn find_cycles_max_cycles_per_scc_respected() {
1175 let edges: Vec<(u32, u32)> = (0..5)
1176 .flat_map(|i| (0..5).filter(move |&j| i != j).map(move |j| (i, j)))
1177 .collect();
1178 let graph = build_cycle_graph(5, &edges);
1179 let cycles = graph.find_cycles();
1180 assert!(
1181 cycles.len() <= 20,
1182 "should cap at MAX_CYCLES_PER_SCC, got {}",
1183 cycles.len()
1184 );
1185 assert!(
1186 !cycles.is_empty(),
1187 "dense graph should still find some cycles"
1188 );
1189 }
1190
1191 #[test]
1192 fn find_cycles_graph_with_no_cycles_returns_empty() {
1193 let graph = build_cycle_graph(5, &[(0, 1), (0, 2), (0, 3), (0, 4)]);
1194 assert!(graph.find_cycles().is_empty());
1195 }
1196
1197 #[test]
1198 fn find_cycles_diamond_no_cycle() {
1199 let graph = build_cycle_graph(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
1200 assert!(graph.find_cycles().is_empty());
1201 }
1202
1203 #[test]
1204 fn find_cycles_diamond_with_back_edge() {
1205 let graph = build_cycle_graph(4, &[(0, 1), (0, 2), (1, 3), (2, 3), (3, 0)]);
1206 let cycles = graph.find_cycles();
1207 assert!(
1208 cycles.len() >= 2,
1209 "diamond with back-edge should have at least 2 elementary cycles, got {}",
1210 cycles.len()
1211 );
1212 assert_eq!(cycles[0].len(), 3);
1213 }
1214
1215 #[test]
1216 fn canonical_cycle_non_sequential_indices() {
1217 let (modules, _, _) = build_test_succs(5, &[]);
1218 let result = canonical_cycle(&[3, 1, 4], &modules);
1219 assert_eq!(result, vec![1, 4, 3]);
1220 }
1221
1222 #[test]
1223 fn canonical_cycle_different_starting_points_same_result() {
1224 let (modules, _, _) = build_test_succs(4, &[]);
1225 let r1 = canonical_cycle(&[0, 1, 2, 3], &modules);
1226 let r2 = canonical_cycle(&[1, 2, 3, 0], &modules);
1227 let r3 = canonical_cycle(&[2, 3, 0, 1], &modules);
1228 let r4 = canonical_cycle(&[3, 0, 1, 2], &modules);
1229 assert_eq!(r1, r2);
1230 assert_eq!(r2, r3);
1231 assert_eq!(r3, r4);
1232 assert_eq!(r1, vec![0, 1, 2, 3]);
1233 }
1234
1235 #[test]
1236 fn canonical_cycle_two_node_both_rotations() {
1237 let (modules, _, _) = build_test_succs(2, &[]);
1238 assert_eq!(canonical_cycle(&[0, 1], &modules), vec![0, 1]);
1239 assert_eq!(canonical_cycle(&[1, 0], &modules), vec![0, 1]);
1240 }
1241
1242 #[test]
1243 fn dfs_find_cycles_from_self_loop_not_found() {
1244 let (modules, all_succs, succ_ranges) = build_test_succs(1, &[(0, 0)]);
1245 let succs = SuccessorMap {
1246 all_succs: &all_succs,
1247 succ_ranges: &succ_ranges,
1248 modules: &modules,
1249 };
1250 let scc_set: FxHashSet<usize> = std::iter::once(0).collect();
1251 let mut seen = FxHashSet::default();
1252 let mut cycles = Vec::new();
1253
1254 for depth in 1..=3 {
1255 dfs_find_cycles_from_for_test(DfsCycleInput {
1256 start: 0,
1257 depth_limit: depth,
1258 scc_set: &scc_set,
1259 succs: &succs,
1260 max_cycles: 10,
1261 accept: &mut |_| false,
1262 seen: &mut seen,
1263 cycles: &mut cycles,
1264 });
1265 }
1266 assert!(
1267 cycles.is_empty(),
1268 "self-loop should not be detected as a cycle by dfs_find_cycles_from"
1269 );
1270 }
1271
1272 #[test]
1273 fn enumerate_elementary_cycles_self_loop_not_found() {
1274 let (modules, all_succs, succ_ranges) = build_test_succs(1, &[(0, 0)]);
1275 let succs = SuccessorMap {
1276 all_succs: &all_succs,
1277 succ_ranges: &succ_ranges,
1278 modules: &modules,
1279 };
1280 let cycles = enumerate_elementary_cycles(&[0], &succs, 20, &mut |_| false).0;
1281 assert!(
1282 cycles.is_empty(),
1283 "self-loop should not produce elementary cycles"
1284 );
1285 }
1286
1287 #[test]
1288 fn find_cycles_two_cycles_sharing_edge() {
1289 let graph = build_cycle_graph(4, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 0)]);
1290 let cycles = graph.find_cycles();
1291 assert_eq!(
1292 cycles.len(),
1293 2,
1294 "two cycles sharing edge A->B should both be found, got {}",
1295 cycles.len()
1296 );
1297 assert!(
1298 cycles.iter().all(|c| c.len() == 3),
1299 "both cycles should have length 3"
1300 );
1301 }
1302
1303 #[test]
1304 fn enumerate_elementary_cycles_shared_edge() {
1305 let (modules, all_succs, succ_ranges) =
1306 build_test_succs(4, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 0)]);
1307 let succs = SuccessorMap {
1308 all_succs: &all_succs,
1309 succ_ranges: &succ_ranges,
1310 modules: &modules,
1311 };
1312 let scc_nodes: Vec<usize> = vec![0, 1, 2, 3];
1313 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 20, &mut |_| false).0;
1314 assert_eq!(
1315 cycles.len(),
1316 2,
1317 "should find exactly 2 elementary cycles sharing edge 0->1, got {}",
1318 cycles.len()
1319 );
1320 }
1321
1322 #[test]
1323 fn enumerate_elementary_cycles_pentagon_with_chords() {
1324 let (modules, all_succs, succ_ranges) =
1325 build_test_succs(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2), (0, 3)]);
1326 let succs = SuccessorMap {
1327 all_succs: &all_succs,
1328 succ_ranges: &succ_ranges,
1329 modules: &modules,
1330 };
1331 let scc_nodes: Vec<usize> = vec![0, 1, 2, 3, 4];
1332 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 20, &mut |_| false).0;
1333
1334 assert!(
1335 cycles.len() >= 3,
1336 "pentagon with chords should have at least 3 elementary cycles, got {}",
1337 cycles.len()
1338 );
1339 let unique: FxHashSet<Vec<usize>> = cycles.iter().cloned().collect();
1340 assert_eq!(
1341 unique.len(),
1342 cycles.len(),
1343 "all enumerated cycles should be unique"
1344 );
1345 assert_eq!(
1346 cycles[0].len(),
1347 3,
1348 "shortest cycle in pentagon with chords should be length 3"
1349 );
1350 }
1351
1352 #[test]
1353 fn find_cycles_large_scc_complete_graph_k6() {
1354 let edges: Vec<(u32, u32)> = (0..6)
1355 .flat_map(|i| (0..6).filter(move |&j| i != j).map(move |j| (i, j)))
1356 .collect();
1357 let graph = build_cycle_graph(6, &edges);
1358 let cycles = graph.find_cycles();
1359
1360 assert!(
1361 cycles.len() <= 20,
1362 "should cap at MAX_CYCLES_PER_SCC (20), got {}",
1363 cycles.len()
1364 );
1365 assert_eq!(
1366 cycles.len(),
1367 20,
1368 "K6 has far more than 20 elementary cycles, so we should hit the cap"
1369 );
1370 assert_eq!(cycles[0].len(), 2, "shortest cycles in K6 should be 2-node");
1371 }
1372
1373 #[test]
1374 fn enumerate_elementary_cycles_respects_depth_cap_of_12() {
1375 let edges: Vec<(usize, usize)> = (0..15).map(|i| (i, (i + 1) % 15)).collect();
1376 let (modules, all_succs, succ_ranges) = build_test_succs(15, &edges);
1377 let succs = SuccessorMap {
1378 all_succs: &all_succs,
1379 succ_ranges: &succ_ranges,
1380 modules: &modules,
1381 };
1382 let scc_nodes: Vec<usize> = (0..15).collect();
1383 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 20, &mut |_| false).0;
1384
1385 assert!(
1386 cycles.is_empty(),
1387 "a pure 15-node cycle should not be found with depth cap of 12, got {} cycles",
1388 cycles.len()
1389 );
1390 }
1391
1392 #[test]
1393 fn enumerate_elementary_cycles_finds_cycle_at_depth_cap_boundary() {
1394 let edges: Vec<(usize, usize)> = (0..12).map(|i| (i, (i + 1) % 12)).collect();
1395 let (modules, all_succs, succ_ranges) = build_test_succs(12, &edges);
1396 let succs = SuccessorMap {
1397 all_succs: &all_succs,
1398 succ_ranges: &succ_ranges,
1399 modules: &modules,
1400 };
1401 let scc_nodes: Vec<usize> = (0..12).collect();
1402 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 20, &mut |_| false).0;
1403
1404 assert_eq!(
1405 cycles.len(),
1406 1,
1407 "a pure 12-node cycle should be found at the depth cap boundary"
1408 );
1409 assert_eq!(cycles[0].len(), 12);
1410 }
1411
1412 #[test]
1413 fn enumerate_elementary_cycles_13_node_pure_cycle_not_found() {
1414 let edges: Vec<(usize, usize)> = (0..13).map(|i| (i, (i + 1) % 13)).collect();
1415 let (modules, all_succs, succ_ranges) = build_test_succs(13, &edges);
1416 let succs = SuccessorMap {
1417 all_succs: &all_succs,
1418 succ_ranges: &succ_ranges,
1419 modules: &modules,
1420 };
1421 let scc_nodes: Vec<usize> = (0..13).collect();
1422 let cycles = enumerate_elementary_cycles(&scc_nodes, &succs, 20, &mut |_| false).0;
1423
1424 assert!(
1425 cycles.is_empty(),
1426 "13-node pure cycle exceeds depth cap of 12"
1427 );
1428 }
1429
1430 #[test]
1431 fn find_cycles_max_cycles_per_scc_enforced_on_k7() {
1432 let edges: Vec<(u32, u32)> = (0..7)
1433 .flat_map(|i| (0..7).filter(move |&j| i != j).map(move |j| (i, j)))
1434 .collect();
1435 let graph = build_cycle_graph(7, &edges);
1436 let cycles = graph.find_cycles();
1437
1438 assert!(
1439 cycles.len() <= 20,
1440 "K7 should cap at MAX_CYCLES_PER_SCC (20), got {}",
1441 cycles.len()
1442 );
1443 assert_eq!(
1444 cycles.len(),
1445 20,
1446 "K7 has far more than 20 elementary cycles, should hit the cap exactly"
1447 );
1448 }
1449
1450 #[test]
1451 fn find_cycles_two_dense_sccs_each_capped() {
1452 let mut edges: Vec<(u32, u32)> = Vec::new();
1453 for i in 0..4 {
1454 for j in 0..4 {
1455 if i != j {
1456 edges.push((i, j));
1457 }
1458 }
1459 }
1460 for i in 4..8 {
1461 for j in 4..8 {
1462 if i != j {
1463 edges.push((i, j));
1464 }
1465 }
1466 }
1467 let graph = build_cycle_graph(8, &edges);
1468 let cycles = graph.find_cycles();
1469
1470 assert!(!cycles.is_empty(), "two dense SCCs should produce cycles");
1471 assert!(
1472 cycles.len() > 2,
1473 "should find multiple cycles across both SCCs, got {}",
1474 cycles.len()
1475 );
1476 }
1477
1478 mod proptests {
1479 use super::*;
1480 use proptest::prelude::*;
1481
1482 proptest! {
1483 #[test]
1486 fn dag_has_no_cycles(
1487 file_count in 2..20usize,
1488 edge_pairs in prop::collection::vec((0..19u32, 0..19u32), 0..30),
1489 ) {
1490 let dag_edges: Vec<(u32, u32)> = edge_pairs
1491 .into_iter()
1492 .filter(|(a, b)| (*a as usize) < file_count && (*b as usize) < file_count && a < b)
1493 .collect();
1494
1495 let graph = build_cycle_graph(file_count, &dag_edges);
1496 let cycles = graph.find_cycles();
1497 prop_assert!(
1498 cycles.is_empty(),
1499 "DAG should have no cycles, but found {}",
1500 cycles.len()
1501 );
1502 }
1503
1504 #[test]
1506 fn mutual_edges_always_detect_cycle(extra_nodes in 0..10usize) {
1507 let file_count = 2 + extra_nodes;
1508 let graph = build_cycle_graph(file_count, &[(0, 1), (1, 0)]);
1509 let cycles = graph.find_cycles();
1510 prop_assert!(
1511 !cycles.is_empty(),
1512 "A->B->A should always produce at least one cycle"
1513 );
1514 let has_pair_cycle = cycles.iter().any(|c| {
1515 c.contains(&FileId(0)) && c.contains(&FileId(1))
1516 });
1517 prop_assert!(has_pair_cycle, "Should find a cycle containing nodes 0 and 1");
1518 }
1519
1520 #[test]
1522 fn cycle_members_are_valid_indices(
1523 file_count in 2..15usize,
1524 edge_pairs in prop::collection::vec((0..14u32, 0..14u32), 1..20),
1525 ) {
1526 let edges: Vec<(u32, u32)> = edge_pairs
1527 .into_iter()
1528 .filter(|(a, b)| (*a as usize) < file_count && (*b as usize) < file_count && a != b)
1529 .collect();
1530
1531 let graph = build_cycle_graph(file_count, &edges);
1532 let cycles = graph.find_cycles();
1533 for cycle in &cycles {
1534 prop_assert!(cycle.len() >= 2, "Cycles must have at least 2 nodes");
1535 for file_id in cycle {
1536 prop_assert!(
1537 (file_id.0 as usize) < file_count,
1538 "FileId {} exceeds file count {}",
1539 file_id.0, file_count
1540 );
1541 }
1542 }
1543 }
1544
1545 #[test]
1547 fn cycles_sorted_by_length(
1548 file_count in 3..12usize,
1549 edge_pairs in prop::collection::vec((0..11u32, 0..11u32), 2..25),
1550 ) {
1551 let edges: Vec<(u32, u32)> = edge_pairs
1552 .into_iter()
1553 .filter(|(a, b)| (*a as usize) < file_count && (*b as usize) < file_count && a != b)
1554 .collect();
1555
1556 let graph = build_cycle_graph(file_count, &edges);
1557 let cycles = graph.find_cycles();
1558 for window in cycles.windows(2) {
1559 prop_assert!(
1560 window[0].len() <= window[1].len(),
1561 "Cycles should be sorted by length: {} > {}",
1562 window[0].len(), window[1].len()
1563 );
1564 }
1565 }
1566 }
1567 }
1568
1569 fn build_cycle_graph_with_type_only(
1571 file_count: usize,
1572 edges_spec: &[(u32, u32, bool)], ) -> ModuleGraph {
1574 let files: Vec<DiscoveredFile> = (0..file_count)
1575 .map(|i| DiscoveredFile {
1576 id: FileId(i as u32),
1577 path: PathBuf::from(format!("/project/file{i}.ts")),
1578 size_bytes: 100,
1579 })
1580 .collect();
1581
1582 let resolved_modules: Vec<ResolvedModule> = (0..file_count)
1583 .map(|i| {
1584 let imports: Vec<ResolvedImport> = edges_spec
1585 .iter()
1586 .filter(|(src, _, _)| *src == i as u32)
1587 .map(|(_, tgt, type_only)| ResolvedImport {
1588 info: ImportInfo {
1589 source: format!("./file{tgt}"),
1590 imported_name: ImportedName::Named("x".to_string()),
1591 local_name: "x".to_string(),
1592 is_type_only: *type_only,
1593 is_type_only_star: false,
1594 from_style: false,
1595 span: oxc_span::Span::new(0, 10),
1596 source_span: oxc_span::Span::default(),
1597 },
1598 target: ResolveResult::InternalModule(FileId(*tgt)),
1599 })
1600 .collect();
1601
1602 ResolvedModule {
1603 file_id: FileId(i as u32),
1604 path: PathBuf::from(format!("/project/file{i}.ts")),
1605 exports: vec![fallow_types::extract::ExportInfo {
1606 name: ExportName::Named("x".to_string()),
1607 local_name: Some("x".to_string()),
1608 is_type_only: false,
1609 visibility: VisibilityTag::None,
1610 expected_unused_reason: None,
1611 span: oxc_span::Span::new(0, 20),
1612 members: vec![],
1613 is_side_effect_used: false,
1614 super_class: None,
1615 deprecated: false,
1616 deprecated_reason: None,
1617 }]
1618 .into(),
1619 re_exports: vec![],
1620 resolved_imports: imports,
1621 resolved_dynamic_imports: vec![],
1622 resolved_dynamic_patterns: vec![],
1623 member_accesses: vec![].into(),
1624 semantic_facts: std::sync::Arc::default(),
1625 whole_object_uses: std::sync::Arc::default(),
1626 has_cjs_exports: false,
1627 has_angular_component_template_url: false,
1628 unused_import_bindings: FxHashSet::default(),
1629 type_referenced_import_bindings: vec![],
1630 value_referenced_import_bindings: vec![],
1631 namespace_object_aliases: vec![],
1632 exported_factory_returns: std::sync::Arc::default(),
1633 exported_factory_return_object_shapes: std::sync::Arc::default(),
1634 type_member_types: std::sync::Arc::default(),
1635 missing_export_targets: vec![],
1636 }
1637 })
1638 .collect();
1639
1640 let entry_points = vec![EntryPoint {
1641 path: PathBuf::from("/project/file0.ts"),
1642 source: EntryPointSource::PackageJsonMain,
1643 }];
1644
1645 ModuleGraph::build(&resolved_modules, &entry_points, &files)
1646 }
1647
1648 #[test]
1649 fn type_only_bidirectional_import_not_a_cycle() {
1650 let graph = build_cycle_graph_with_type_only(2, &[(0, 1, true), (1, 0, true)]);
1651 let cycles = graph.find_cycles();
1652 assert!(
1653 cycles.is_empty(),
1654 "type-only bidirectional imports should not be reported as cycles"
1655 );
1656 }
1657
1658 #[test]
1659 fn mixed_type_and_value_import_not_a_cycle() {
1660 let graph = build_cycle_graph_with_type_only(2, &[(0, 1, false), (1, 0, true)]);
1661 let cycles = graph.find_cycles();
1662 assert!(
1663 cycles.is_empty(),
1664 "A->B (value) + B->A (type-only) is not a runtime cycle"
1665 );
1666 }
1667
1668 #[test]
1669 fn both_value_imports_with_one_type_still_a_cycle() {
1670 let graph = build_cycle_graph_with_type_only(2, &[(0, 1, false), (1, 0, false)]);
1671 let cycles = graph.find_cycles();
1672 assert!(
1673 !cycles.is_empty(),
1674 "bidirectional value imports should be reported as a cycle"
1675 );
1676 }
1677
1678 #[test]
1679 fn all_value_imports_still_a_cycle() {
1680 let graph = build_cycle_graph_with_type_only(2, &[(0, 1, false), (1, 0, false)]);
1681 let cycles = graph.find_cycles();
1682 assert_eq!(cycles.len(), 1);
1683 }
1684
1685 #[test]
1686 fn three_node_type_only_cycle_not_reported() {
1687 let graph =
1688 build_cycle_graph_with_type_only(3, &[(0, 1, true), (1, 2, true), (2, 0, true)]);
1689 let cycles = graph.find_cycles();
1690 assert!(
1691 cycles.is_empty(),
1692 "three-node type-only cycle should not be reported"
1693 );
1694 }
1695
1696 #[test]
1697 fn three_node_cycle_one_value_edge_still_reported() {
1698 let graph =
1699 build_cycle_graph_with_type_only(3, &[(0, 1, false), (1, 2, true), (2, 0, true)]);
1700 let cycles = graph.find_cycles();
1701 assert!(
1702 cycles.is_empty(),
1703 "cycle broken by type-only edge in the middle should not be reported"
1704 );
1705 }
1706
1707 #[test]
1708 fn accepted_cycles_leave_their_slots_to_other_cycles() {
1709 let mut edges = Vec::new();
1710 for from in 0..5_u32 {
1711 for to in 0..5_u32 {
1712 if from != to {
1713 edges.push((from, to));
1714 }
1715 }
1716 }
1717 let graph = build_cycle_graph(5, &edges);
1718 let all = graph.find_cycles_accepting(super::CycleOptions::default(), &mut |_| false);
1719 assert_eq!(all.cycles.len(), super::MAX_CYCLES_PER_SCC);
1720 assert_eq!(all.capped_sccs.len(), 1);
1721
1722 let mut offered = 0;
1723 let rest = graph.find_cycles_accepting(super::CycleOptions::default(), &mut |cycle| {
1724 offered += 1;
1725 cycle.len() == 2
1726 });
1727 assert_eq!(rest.cycles.len(), super::MAX_CYCLES_PER_SCC);
1728 assert!(rest.cycles.iter().all(|cycle| cycle.len() > 2));
1729 assert_eq!(offered, 10 + super::MAX_CYCLES_PER_SCC);
1730 }
1731}