codelens_engine/
circular.rs

1use crate::import_graph::{GraphCache, build_graph_pub};
2use crate::project::ProjectRoot;
3use anyhow::Result;
4use petgraph::algo::tarjan_scc;
5use petgraph::graph::DiGraph;
6use serde::Serialize;
7use std::collections::HashMap;
8
9#[derive(Debug, Clone, Serialize)]
10pub struct CircularDependency {
11    pub cycle: Vec<String>,
12    pub length: usize,
13}
14
15/// Find all circular dependency cycles in the project's import graph.
16pub fn find_circular_dependencies(
17    project: &ProjectRoot,
18    max_results: usize,
19    cache: &GraphCache,
20) -> Result<Vec<CircularDependency>> {
21    let graph = build_graph_pub(project, cache)?;
22
23    // Build petgraph DiGraph
24    let mut digraph: DiGraph<String, ()> = DiGraph::new();
25    let mut node_indices: HashMap<String, petgraph::graph::NodeIndex> = HashMap::new();
26
27    for file in graph.as_ref().keys() {
28        let idx = digraph.add_node(file.clone());
29        node_indices.insert(file.clone(), idx);
30    }
31
32    for (file, node) in graph.iter() {
33        let from_idx = node_indices[file];
34        for import in &node.imports {
35            if let Some(&to_idx) = node_indices.get(import) {
36                digraph.add_edge(from_idx, to_idx, ());
37            }
38        }
39    }
40
41    // Run Tarjan's SCC — components with size > 1 are cycles
42    let sccs = tarjan_scc(&digraph);
43    let mut cycles: Vec<CircularDependency> = sccs
44        .into_iter()
45        .filter(|scc| scc.len() > 1)
46        .map(|scc| {
47            let mut cycle: Vec<String> = scc.iter().map(|&idx| digraph[idx].clone()).collect();
48            cycle.sort();
49            let length = cycle.len();
50            CircularDependency { cycle, length }
51        })
52        .collect();
53
54    // Sort by cycle length descending, then alphabetically
55    cycles.sort_by(|a, b| b.length.cmp(&a.length).then(a.cycle.cmp(&b.cycle)));
56
57    if max_results > 0 && cycles.len() > max_results {
58        cycles.truncate(max_results);
59    }
60
61    Ok(cycles)
62}
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67    use crate::import_graph::GraphCache;
68    use std::fs;
69
70    fn temp_project_dir(name: &str) -> std::path::PathBuf {
71        let dir = std::env::temp_dir().join(format!(
72            "codelens-core-circular-{name}-{}",
73            std::time::SystemTime::now()
74                .duration_since(std::time::UNIX_EPOCH)
75                .expect("time")
76                .as_nanos()
77        ));
78        fs::create_dir_all(&dir).expect("create tempdir");
79        dir
80    }
81
82    #[test]
83    fn detects_simple_cycle() {
84        let dir = temp_project_dir("simple");
85        // a.py -> b.py -> a.py (cycle)
86        fs::write(dir.join("a.py"), "from b import foo\n").expect("write a");
87        fs::write(dir.join("b.py"), "from a import bar\n").expect("write b");
88        fs::write(dir.join("c.py"), "import os\n").expect("write c (no cycle)");
89
90        let project = ProjectRoot::new(&dir).expect("project");
91        let cache = GraphCache::new(0);
92        let cycles = find_circular_dependencies(&project, 50, &cache).expect("cycles");
93        assert!(!cycles.is_empty(), "should find at least one cycle");
94        let first = &cycles[0];
95        assert_eq!(first.length, 2);
96        assert!(first.cycle.contains(&"a.py".to_owned()));
97        assert!(first.cycle.contains(&"b.py".to_owned()));
98    }
99
100    #[test]
101    fn no_cycles_in_dag() {
102        let dir = temp_project_dir("dag");
103        fs::write(dir.join("main.py"), "from utils import greet\n").expect("write main");
104        fs::write(dir.join("utils.py"), "from models import User\n").expect("write utils");
105        fs::write(dir.join("models.py"), "class User:\n    pass\n").expect("write models");
106
107        let project = ProjectRoot::new(&dir).expect("project");
108        let cache = GraphCache::new(0);
109        let cycles = find_circular_dependencies(&project, 50, &cache).expect("cycles");
110        assert!(cycles.is_empty(), "DAG should have no cycles");
111    }
112}
codelens_engine/circular.rs

codelens_engine/
circular.rs
