Skip to main content

fallow_graph/graph/
cycles.rs

1//! Circular dependency detection via Tarjan's SCC algorithm + elementary cycle enumeration.
2
3use 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/// Options for [`ModuleGraph::find_cycles_with`].
14#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
15pub struct CycleOptions {
16    /// Skip edges on which no symbol loads its target eagerly with a runtime
17    /// value, so an edge made only of `import()`, lazy patterns or
18    /// other-thread loads does not take part in cycle detection. An edge
19    /// that also carries an eager import stays.
20    pub ignore_lazy_imports: bool,
21}
22
23/// The most cycles that the detector lists for one strongly connected group
24/// of files. A dense group has very many cycles, so the detector stops here.
25pub const MAX_CYCLES_PER_SCC: usize = 20;
26
27/// The most files that a listed cycle has. The detector does not look for
28/// longer cycles.
29pub const MAX_CYCLE_LENGTH: usize = 12;
30
31/// The result of [`ModuleGraph::find_cycles_accepting`].
32#[derive(Debug, Default, Clone, PartialEq, Eq)]
33pub struct CycleSearch {
34    /// The listed cycles that the `accept` callback did not accept, in the
35    /// order of [`ModuleGraph::find_cycles`].
36    pub cycles: Vec<Vec<FileId>>,
37    /// The strongly connected groups whose enumeration stopped at
38    /// [`MAX_CYCLES_PER_SCC`]. Such a group can have cycles that are not
39    /// listed and not given to the `accept` callback.
40    pub capped_sccs: Vec<Vec<FileId>>,
41}
42
43impl ModuleGraph {
44    /// Find all circular dependency cycles in the module graph.
45    ///
46    /// Uses an iterative implementation of Tarjan's strongly connected components
47    /// algorithm (O(V + E)) to find all SCCs with 2 or more nodes. Each such SCC
48    /// represents a set of files involved in a circular dependency.
49    ///
50    /// Returns cycles sorted by length (shortest first), with files within each
51    /// cycle sorted by path for deterministic output.
52    ///
53    /// # Panics
54    ///
55    /// Panics if the internal file-to-path lookup is inconsistent with the module list.
56    #[must_use]
57    pub fn find_cycles(&self) -> Vec<Vec<FileId>> {
58        self.find_cycles_with(CycleOptions::default())
59    }
60
61    /// Find all circular dependency cycles, with the edge filter that
62    /// `options` selects. See [`Self::find_cycles`] for the output order.
63    ///
64    /// The filter runs before the SCC pass, so a skipped edge cannot merge
65    /// files into one SCC and cannot use a slot of the per-SCC cycle cap.
66    #[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    /// Find the cycles like [`Self::find_cycles_with`], and drop each cycle
72    /// that `accept` accepts. An accepted cycle does not use a slot of the
73    /// per-group cycle limit, so the enumeration continues past it. The
74    /// callback gets each cycle once, in cycle order.
75    #[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    /// Build the flattened runtime-successor adjacency (type-only edges,
100    /// edges that do not load their target, lazy edges when `options` asks
101    /// for it, and duplicate targets excluded)
102    /// plus the per-node range index into it.
103    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    /// Enumerate individual elementary cycles from SCCs and return sorted results.
139    #[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
204/// One iterative-DFS frame for the Tarjan SCC pass over runtime successors.
205struct SccFrame {
206    node: usize,
207    succ_pos: usize,
208    succ_end: usize,
209}
210
211/// Mutable Tarjan SCC state for `find_cycles`, collecting SCCs of size >= 2.
212struct 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    /// Assign the next DFS index to `node` and push it onto the SCC stack.
234    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    /// Build a frame spanning the successor range of `node`.
243    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    /// Run the iterative Tarjan DFS rooted at `start`, appending discovered
253    /// SCCs of size >= 2 to `self.sccs`.
254    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    /// Advance one successor of `frame`, discovering a new child (returned for
277    /// descent) or updating the lowlink for an on-stack back edge.
278    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    /// When `v` is an SCC root, pop its members off the stack and record the
294    /// SCC if it has at least two nodes.
295    #[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
322/// Rotate a cycle so the node with the smallest path is first (canonical form for dedup).
323fn 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
370/// Run a bounded DFS from `start`, looking for elementary cycles of exactly `depth_limit` nodes.
371///
372/// Appends any newly found cycles to `cycles` (deduped via `seen`).
373/// Stops early once `cycles.len() >= max_cycles`.
374struct 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
445/// Enumerate individual elementary cycles within an SCC using depth-limited DFS.
446///
447/// Uses iterative deepening: first finds all 2-node cycles, then 3-node, etc.
448/// This ensures the shortest, most actionable cycles are always found first.
449/// Stops after `max_cycles` total cycles to bound work on dense SCCs. A
450/// cycle that `accept` accepts does not count. The flag is `true` when the
451/// enumeration stopped at `max_cycles`.
452fn 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    /// Helper: build a graph from files+edges, no entry points needed for cycle detection.
511    #[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    /// Build lightweight `ModuleNode` stubs and successor data for unit tests.
729    ///
730    /// `edges_spec` is a list of (source, target) pairs (0-indexed).
731    /// Returns (modules, all_succs, succ_ranges) suitable for constructing a `SuccessorMap`.
732    #[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            /// A DAG (directed acyclic graph) should always have zero cycles.
1484            /// We construct a DAG by only allowing edges from lower to higher node indices.
1485            #[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            /// Adding mutual edges A->B->A should always detect a cycle.
1505            #[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            /// All cycle members should be valid FileId indices.
1521            #[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            /// Cycles should be sorted by length (shortest first).
1546            #[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    /// Build a cycle graph where specific edges are type-only.
1570    fn build_cycle_graph_with_type_only(
1571        file_count: usize,
1572        edges_spec: &[(u32, u32, bool)], // (source, target, is_type_only)
1573    ) -> 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}