use crate::error::Result;
use crate::types::{AnalysisResult, Edge, Node, NodeId};
use std::collections::{HashMap, HashSet};
use std::process::Command;
pub struct Analyzer;
impl Analyzer {
pub fn god_nodes(&self, nodes: &[Node], edges: &[Edge], top_n: usize) -> Vec<Node> {
let mut degree: HashMap<&str, usize> = HashMap::new();
for edge in edges {
*degree.entry(edge.source.as_str()).or_insert(0) += 1;
*degree.entry(edge.target.as_str()).or_insert(0) += 1;
}
let mut candidates: Vec<&Node> = nodes
.iter()
.filter(|n| {
let deg = *degree.get(n.id.as_str()).unwrap_or(&0);
!n.label.ends_with(".py")
&& !n.label.ends_with(".js")
&& !n.label.ends_with(".ts")
&& !n.label.ends_with(".rs")
&& !n.label.ends_with(".go")
&& !n.label.ends_with(".java")
&& !n.label.ends_with(".c")
&& !n.label.ends_with(".cpp")
&& !n.label.ends_with(".h")
&& !n.label.contains("().")
&& !(n.label.starts_with(".") && n.label.ends_with("()"))
&& !(n.label.ends_with("()") && deg <= 1)
})
.collect();
candidates.sort_by(|a, b| {
let deg_a = degree.get(a.id.as_str()).unwrap_or(&0);
let deg_b = degree.get(b.id.as_str()).unwrap_or(&0);
deg_b.cmp(deg_a)
});
candidates.truncate(top_n);
candidates.into_iter().cloned().collect()
}
pub fn surprising_connections(
&self,
edges: &[Edge],
cross_language_suppression: bool,
) -> Vec<Edge> {
if cross_language_suppression {
edges
.iter()
.filter(|e| {
e.confidence == "INFERRED"
&& e.source_file.as_deref().is_none_or(|sf| {
sf.ends_with(".py")
|| sf.ends_with(".js")
|| sf.ends_with(".ts")
|| sf.ends_with(".rs")
|| sf.ends_with(".go")
})
})
.cloned()
.collect()
} else {
edges
.iter()
.filter(|e| e.confidence == "INFERRED")
.cloned()
.collect()
}
}
pub fn suggest_questions(&self, nodes: &[Node], edges: &[Edge]) -> Vec<String> {
let mut questions = Vec::new();
questions.push("What are the core modules and how do they relate?".to_string());
questions.push("Which components have the most dependencies?".to_string());
let has_cycles = self.detect_cycles(nodes, edges);
if has_cycles {
questions.push("Are there any circular dependencies between modules?".to_string());
}
questions.push("How does data flow through the system?".to_string());
let lang_count = self.count_languages(nodes);
if lang_count.len() > 1 {
questions.push(format!(
"How do the {} different languages interact?",
lang_count.len()
));
}
questions
}
pub fn cohesion_score(
&self,
_nodes: &[Node],
edges: &[Edge],
community_nodes: &[NodeId],
) -> f64 {
if community_nodes.len() <= 1 {
return 1.0;
}
let node_set: HashSet<&str> = community_nodes.iter().map(|s| s.as_str()).collect();
let internal_edges = edges
.iter()
.filter(|e| {
node_set.contains(e.source.as_str()) && node_set.contains(e.target.as_str())
})
.count();
let max_possible = community_nodes.len() * (community_nodes.len() - 1) / 2;
if max_possible == 0 {
return 1.0;
}
internal_edges as f64 / max_possible as f64
}
pub fn pagerank(&self, edges: &[Edge], damping: f64, max_iter: usize) -> HashMap<String, f64> {
let mut node_degree: HashMap<&str, f64> = HashMap::new();
let mut outlinks: HashMap<&str, Vec<&str>> = HashMap::new();
let mut all_nodes: HashSet<&str> = HashSet::new();
for edge in edges {
all_nodes.insert(edge.source.as_str());
all_nodes.insert(edge.target.as_str());
*node_degree.entry(edge.source.as_str()).or_insert(0.0) += 1.0;
outlinks
.entry(edge.source.as_str())
.or_default()
.push(edge.target.as_str());
}
let n = all_nodes.len() as f64;
if n == 0.0 {
return HashMap::new();
}
let mut ranks: HashMap<String, f64> = all_nodes
.iter()
.map(|&id| (id.to_string(), 1.0 / n))
.collect();
for _iter in 0..max_iter {
let mut new_ranks: HashMap<String, f64> = HashMap::new();
let dangling_sum: f64 = all_nodes
.iter()
.filter(|id| outlinks.get(*id).is_none_or(|v| v.is_empty()))
.map(|id| ranks[*id])
.sum();
for &node in &all_nodes {
let mut score = (1.0 - damping) / n;
score += damping * dangling_sum / n;
for (&src, targets) in &outlinks {
if targets.contains(&node) {
score +=
damping * ranks.get(src).copied().unwrap_or(0.0) / targets.len() as f64;
}
}
new_ranks.insert(node.to_string(), score);
}
ranks = new_ranks;
}
ranks
}
pub fn graph_diff(&self, old: &[Edge], new: &[Edge]) -> (Vec<Edge>, Vec<Edge>) {
let old_set: HashSet<(&str, &str, &str)> = old
.iter()
.map(|e| (e.source.as_str(), e.target.as_str(), e.relation.as_str()))
.collect();
let new_set: HashSet<(&str, &str, &str)> = new
.iter()
.map(|e| (e.source.as_str(), e.target.as_str(), e.relation.as_str()))
.collect();
let added: Vec<Edge> = new
.iter()
.filter(|e| {
!old_set.contains(&(e.source.as_str(), e.target.as_str(), e.relation.as_str()))
})
.cloned()
.collect();
let removed: Vec<Edge> = old
.iter()
.filter(|e| {
!new_set.contains(&(e.source.as_str(), e.target.as_str(), e.relation.as_str()))
})
.cloned()
.collect();
(added, removed)
}
fn detect_cycles(&self, _nodes: &[Node], edges: &[Edge]) -> bool {
let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();
for edge in edges {
graph
.entry(edge.source.as_str())
.or_default()
.push(edge.target.as_str());
}
let mut visited: HashSet<&str> = HashSet::new();
let mut stack: HashSet<&str> = HashSet::new();
fn dfs<'a>(
node: &'a str,
graph: &HashMap<&'a str, Vec<&'a str>>,
visited: &mut HashSet<&'a str>,
stack: &mut HashSet<&'a str>,
) -> bool {
if stack.contains(node) {
return true;
}
if visited.contains(node) {
return false;
}
visited.insert(node);
stack.insert(node);
if let Some(neighbors) = graph.get(node) {
for &next in neighbors {
if dfs(next, graph, visited, stack) {
return true;
}
}
}
stack.remove(node);
false
}
let all_nodes: Vec<&str> = graph.keys().copied().collect();
for node in all_nodes {
if dfs(node, &graph, &mut visited, &mut stack) {
return true;
}
}
false
}
fn count_languages(&self, nodes: &[Node]) -> HashMap<String, usize> {
let mut counts: HashMap<String, usize> = HashMap::new();
for node in nodes {
let lang = language_from_file(&node.source_file);
*counts.entry(lang).or_insert(0) += 1;
}
counts
}
pub fn tarjan_scc(&self, edges: &[Edge]) -> Vec<Vec<String>> {
let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();
for edge in edges {
graph
.entry(edge.source.as_str())
.or_default()
.push(edge.target.as_str());
graph.entry(edge.target.as_str()).or_default();
}
let mut index_counter = 0usize;
let mut index: HashMap<&str, usize> = HashMap::new();
let mut lowlink: HashMap<&str, usize> = HashMap::new();
let mut stack: Vec<&str> = Vec::new();
let mut on_stack: HashSet<&str> = HashSet::new();
let mut sccs: Vec<Vec<String>> = Vec::new();
#[allow(clippy::too_many_arguments)]
fn strongconnect<'a>(
v: &'a str,
graph: &HashMap<&'a str, Vec<&'a str>>,
index_counter: &mut usize,
index: &mut HashMap<&'a str, usize>,
lowlink: &mut HashMap<&'a str, usize>,
stack: &mut Vec<&'a str>,
on_stack: &mut HashSet<&'a str>,
sccs: &mut Vec<Vec<String>>,
) {
index.insert(v, *index_counter);
lowlink.insert(v, *index_counter);
*index_counter += 1;
stack.push(v);
on_stack.insert(v);
if let Some(neighbors) = graph.get(v) {
for &w in neighbors {
if !index.contains_key(w) {
strongconnect(
w,
graph,
index_counter,
index,
lowlink,
stack,
on_stack,
sccs,
);
let v_low = lowlink[v].min(lowlink[w]);
lowlink.insert(v, v_low);
} else if on_stack.contains(w) {
let v_low = lowlink[v].min(index[w]);
lowlink.insert(v, v_low);
}
}
}
if lowlink[v] == index[v] {
let mut scc = Vec::new();
loop {
let w = stack.pop().unwrap();
on_stack.remove(w);
scc.push(w.to_string());
if w == v {
break;
}
}
sccs.push(scc);
}
}
let all_nodes: Vec<&str> = graph.keys().copied().collect();
for node in all_nodes {
if !index.contains_key(node) {
strongconnect(
node,
&graph,
&mut index_counter,
&mut index,
&mut lowlink,
&mut stack,
&mut on_stack,
&mut sccs,
);
}
}
sccs
}
pub fn bridge_edges(&self, nodes: &[Node], edges: &[Edge]) -> Vec<Edge> {
if nodes.is_empty() || edges.is_empty() {
return vec![];
}
let id_to_idx: HashMap<&str, usize> = nodes
.iter()
.enumerate()
.map(|(i, n)| (n.id.as_str(), i))
.collect();
let n = nodes.len();
let mut adj: Vec<Vec<(usize, usize)>> = vec![vec![]; n];
for (ei, edge) in edges.iter().enumerate() {
if let (Some(&si), Some(&ti)) = (
id_to_idx.get(edge.source.as_str()),
id_to_idx.get(edge.target.as_str()),
) {
adj[si].push((ti, ei));
adj[ti].push((si, ei));
}
}
let mut visited = vec![false; n];
let mut tin = vec![0usize; n];
let mut low = vec![0usize; n];
let mut timer = 0usize;
let mut is_bridge = vec![false; edges.len()];
#[allow(clippy::too_many_arguments)]
fn dfs(
v: usize,
p: Option<usize>,
adj: &[Vec<(usize, usize)>],
visited: &mut [bool],
tin: &mut [usize],
low: &mut [usize],
timer: &mut usize,
is_bridge: &mut [bool],
) {
visited[v] = true;
tin[v] = *timer;
low[v] = *timer;
*timer += 1;
for &(to, ei) in &adj[v] {
if Some(to) == p {
continue;
}
if visited[to] {
low[v] = low[v].min(tin[to]);
} else {
dfs(to, Some(v), adj, visited, tin, low, timer, is_bridge);
low[v] = low[v].min(low[to]);
if low[to] > tin[v] {
is_bridge[ei] = true;
}
}
}
}
for i in 0..n {
if !visited[i] {
dfs(
i,
None,
&adj,
&mut visited,
&mut tin,
&mut low,
&mut timer,
&mut is_bridge,
);
}
}
edges
.iter()
.enumerate()
.filter(|(i, _)| is_bridge[*i])
.map(|(_, e)| e.clone())
.collect()
}
pub fn topological_sort(&self, edges: &[Edge]) -> Vec<String> {
let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();
let mut in_degree: HashMap<&str, usize> = HashMap::new();
for edge in edges {
graph
.entry(edge.source.as_str())
.or_default()
.push(edge.target.as_str());
in_degree.entry(edge.source.as_str()).or_insert(0);
*in_degree.entry(edge.target.as_str()).or_insert(0) += 1;
}
let mut queue = std::collections::VecDeque::new();
for (&node, °) in &in_degree {
if deg == 0 {
queue.push_back(node);
}
}
let mut result = Vec::new();
while let Some(node) = queue.pop_front() {
result.push(node.to_string());
if let Some(neighbors) = graph.get(node) {
for &next in neighbors {
if let Some(d) = in_degree.get_mut(next) {
*d -= 1;
if *d == 0 {
queue.push_back(next);
}
}
}
}
}
result
}
pub fn analyze(&self, nodes: &[Node], edges: &[Edge]) -> Result<AnalysisResult> {
let god_nodes = self.god_nodes(nodes, edges, 10);
let surprising = self.surprising_connections(edges, false);
let questions = self.suggest_questions(nodes, edges);
Ok(AnalysisResult {
god_nodes,
surprising_connections: surprising,
suggested_questions: questions,
community_cohesion: vec![],
})
}
pub fn find_similar(&self, edges: &[Edge], node_id: &str, top_n: usize) -> Vec<(String, f64)> {
let pairs: Vec<(String, String)> = edges
.iter()
.map(|e| (e.source.clone(), e.target.clone()))
.collect();
let n2v = crate::embedding::Node2Vec::new(64, 1.0, 1.0);
let embeddings = n2v.train(&pairs);
n2v.find_similar(&embeddings, node_id, top_n)
}
pub fn compute_temporal_risk(&self, nodes: &mut [Node], edges: &[Edge]) -> Result<()> {
let is_git_repo = Command::new("git")
.arg("rev-parse")
.arg("--is-inside-work-tree")
.output()
.map(|output| output.status.success())
.unwrap_or(false);
if !is_git_repo {
return Ok(());
}
let mut churn_map: HashMap<String, usize> = HashMap::new();
for node in nodes.iter() {
if node.file_type != "file" {
continue;
}
let mut churn = 0usize;
if let Ok(output) = Command::new("git")
.arg("rev-list")
.arg("--count")
.arg("HEAD")
.arg("--")
.arg(&node.source_file)
.output()
{
if output.status.success() {
let stdout = String::from_utf8_lossy(&output.stdout);
if let Ok(count) = stdout.trim().parse::<usize>() {
churn = count;
}
}
}
churn_map.insert(node.id.clone(), churn);
}
self.apply_risk_scores(nodes, edges, &churn_map);
Ok(())
}
pub(crate) fn apply_risk_scores(
&self,
nodes: &mut [Node],
edges: &[Edge],
churn_map: &HashMap<String, usize>,
) {
let mut degree: HashMap<String, usize> = HashMap::new();
for edge in edges {
*degree.entry(edge.source.clone()).or_insert(0) += 1;
*degree.entry(edge.target.clone()).or_insert(0) += 1;
}
let bridges = self.bridge_edges(nodes, edges);
let mut bridge_count: HashMap<String, usize> = HashMap::new();
for bridge in &bridges {
*bridge_count.entry(bridge.source.clone()).or_insert(0) += 1;
*bridge_count.entry(bridge.target.clone()).or_insert(0) += 1;
}
for node in nodes.iter_mut() {
if node.file_type != "file" {
continue;
}
let churn = churn_map.get(&node.id).copied().unwrap_or(0);
let deg = degree.get(&node.id).copied().unwrap_or(0);
let bridge_factor = 1.0 + bridge_count.get(&node.id).copied().unwrap_or(0) as f64;
let risk_score = churn as f64 * deg as f64 * bridge_factor;
node.metadata
.insert("risk_score".to_string(), risk_score.to_string());
node.rationale = Some(format!(
"Risk score: {risk_score:.2} (churn={churn}, degree={deg}, bridge_factor={bridge_factor:.1})"
));
}
}
}
fn language_from_file(path: &str) -> String {
if path.ends_with(".py") {
"Python".to_string()
} else if path.ends_with(".js") || path.ends_with(".jsx") {
"JavaScript".to_string()
} else if path.ends_with(".ts") || path.ends_with(".tsx") {
"TypeScript".to_string()
} else if path.ends_with(".rs") {
"Rust".to_string()
} else if path.ends_with(".go") {
"Go".to_string()
} else if path.ends_with(".java") {
"Java".to_string()
} else if path.ends_with(".c") || path.ends_with(".h") {
"C".to_string()
} else if path.ends_with(".cpp") || path.ends_with(".hpp") {
"C++".to_string()
} else if path.ends_with(".rb") {
"Ruby".to_string()
} else if path.ends_with(".php") {
"PHP".to_string()
} else if path.ends_with(".swift") {
"Swift".to_string()
} else if path.ends_with(".kt") || path.ends_with(".kts") {
"Kotlin".to_string()
} else {
"Other".to_string()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashMap;
fn make_node(id: &str, label: &str, source_file: &str) -> Node {
Node {
id: id.to_string(),
label: label.to_string(),
file_type: "code".to_string(),
source_file: source_file.to_string(),
source_location: None,
community: None,
rationale: None,
docstring: None,
metadata: HashMap::new(),
}
}
fn make_node_id(id: &str) -> Node {
make_node(id, id, "test.py")
}
fn make_edge(src: &str, tgt: &str, relation: &str, confidence: &str) -> Edge {
Edge {
source: src.to_string(),
target: tgt.to_string(),
relation: relation.to_string(),
confidence: confidence.to_string(),
source_file: Some("test.py".to_string()),
weight: 1.0,
context: None,
}
}
fn make_edge_with_file(
src: &str,
tgt: &str,
relation: &str,
confidence: &str,
file: &str,
) -> Edge {
Edge {
source: src.to_string(),
target: tgt.to_string(),
relation: relation.to_string(),
confidence: confidence.to_string(),
source_file: Some(file.to_string()),
weight: 1.0,
context: None,
}
}
#[test]
fn test_god_nodes_basic() {
let nodes = vec![make_node_id("a"), make_node_id("b"), make_node_id("c")];
let edges = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("a", "c", "imports", "EXTRACTED"),
];
let analyzer = Analyzer;
let gods = analyzer.god_nodes(&nodes, &edges, 10);
assert_eq!(gods[0].id, "a");
}
#[test]
fn test_god_nodes_exclude_file() {
let nodes = vec![
make_node("a", "A", "test.py"),
make_node("main.py", "main.py", "test.py"),
];
let edges = vec![make_edge("main.py", "a", "contains", "EXTRACTED")];
let analyzer = Analyzer;
let gods = analyzer.god_nodes(&nodes, &edges, 10);
assert_eq!(gods.len(), 1);
assert_eq!(gods[0].id, "a");
}
#[test]
fn test_god_nodes_exclude_method_stub() {
let nodes = vec![
make_node("hub", "HubClass", "app.py"),
make_node("stub_method", ".init()", "app.py"),
make_node("stub_fn", "setup()", "app.py"),
];
let edges = vec![
make_edge("hub", "a", "calls", "EXTRACTED"),
make_edge("hub", "b", "calls", "EXTRACTED"),
make_edge("hub", "c", "calls", "EXTRACTED"),
make_edge("hub", "stub_fn", "contains", "EXTRACTED"),
];
let analyzer = Analyzer;
let gods = analyzer.god_nodes(&nodes, &edges, 10);
assert!(
gods.iter().all(|n| n.id != "stub_method"),
"method stub should be excluded"
);
assert!(
gods.iter().all(|n| n.id != "stub_fn"),
"isolated fn stub should be excluded"
);
}
#[test]
fn test_surprising_connections_basic() {
let edges = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("c", "d", "calls", "INFERRED"),
];
let analyzer = Analyzer;
let surprising = analyzer.surprising_connections(&edges, false);
assert_eq!(surprising.len(), 1);
assert_eq!(surprising[0].relation, "calls");
}
#[test]
fn test_surprising_cross_language_suppression() {
let edges = vec![
make_edge_with_file("a", "b", "imports", "INFERRED", "source.py"),
make_edge_with_file("c", "d", "imports", "INFERRED", "data.json"),
];
let analyzer = Analyzer;
let filtered = analyzer.surprising_connections(&edges, true);
assert_eq!(filtered.len(), 1);
assert_eq!(filtered[0].source_file.as_deref(), Some("source.py"));
}
#[test]
fn test_suggest_questions_basic() {
let analyzer = Analyzer;
let questions = analyzer.suggest_questions(&[], &[]);
assert!(questions.len() >= 3);
}
#[test]
fn test_suggest_questions_with_cycle() {
let nodes = vec![make_node_id("a"), make_node_id("b")];
let edges = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("b", "a", "imports", "EXTRACTED"),
];
let analyzer = Analyzer;
let questions = analyzer.suggest_questions(&nodes, &edges);
let has_cycle_q = questions.iter().any(|q| q.contains("circular"));
assert!(has_cycle_q);
}
#[test]
fn test_suggest_questions_multi_lang() {
let nodes = vec![
make_node("a", "A", "main.py"),
make_node("b", "B", "utils.ts"),
];
let analyzer = Analyzer;
let questions = analyzer.suggest_questions(&nodes, &[]);
let has_lang_q = questions.iter().any(|q| q.contains("languages"));
assert!(has_lang_q);
}
#[test]
fn test_cohesion_complete() {
let nodes = ["a", "b", "c"];
let edges = vec![
make_edge("a", "b", "connects", "EXTRACTED"),
make_edge("a", "c", "connects", "EXTRACTED"),
make_edge("b", "c", "connects", "EXTRACTED"),
];
let analyzer = Analyzer;
let score = analyzer.cohesion_score(
&[],
&edges,
&nodes.iter().map(|s| s.to_string()).collect::<Vec<_>>(),
);
assert!((score - 1.0).abs() < 0.01);
}
#[test]
fn test_cohesion_empty() {
let analyzer = Analyzer;
let score = analyzer.cohesion_score(&[], &[], &[]);
assert!((score - 1.0).abs() < 0.01);
}
#[test]
fn test_cohesion_single() {
let analyzer = Analyzer;
let score = analyzer.cohesion_score(&[], &[], &["a".to_string()]);
assert!((score - 1.0).abs() < 0.01);
}
#[test]
fn test_pagerank_basic() {
let edges = vec![
make_edge("a", "b", "links", "EXTRACTED"),
make_edge("b", "c", "links", "EXTRACTED"),
make_edge("c", "a", "links", "EXTRACTED"),
];
let analyzer = Analyzer;
let ranks = analyzer.pagerank(&edges, 0.85, 100);
assert!((ranks["a"] - ranks["b"]).abs() < 0.01);
assert!((ranks["b"] - ranks["c"]).abs() < 0.01);
}
#[test]
fn test_pagerank_skewed() {
let edges = vec![
make_edge("hub", "a", "links", "EXTRACTED"),
make_edge("hub", "b", "links", "EXTRACTED"),
make_edge("hub", "c", "links", "EXTRACTED"),
];
let analyzer = Analyzer;
let ranks = analyzer.pagerank(&edges, 0.85, 100);
assert!(ranks["hub"] > 0.0);
assert!(ranks["a"] > 0.0);
}
#[test]
fn test_graph_diff_added() {
let old = vec![make_edge("a", "b", "imports", "EXTRACTED")];
let new = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("a", "c", "imports", "EXTRACTED"),
];
let analyzer = Analyzer;
let (added, removed) = analyzer.graph_diff(&old, &new);
assert_eq!(added.len(), 1);
assert_eq!(added[0].target, "c");
assert!(removed.is_empty());
}
#[test]
fn test_graph_diff_removed() {
let old = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("a", "c", "imports", "EXTRACTED"),
];
let new = vec![make_edge("a", "b", "imports", "EXTRACTED")];
let analyzer = Analyzer;
let (added, removed) = analyzer.graph_diff(&old, &new);
assert!(added.is_empty());
assert_eq!(removed.len(), 1);
assert_eq!(removed[0].target, "c");
}
#[test]
fn test_detect_cycles() {
let nodes = vec![make_node_id("a"), make_node_id("b")];
let edges = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("b", "a", "imports", "EXTRACTED"),
];
let analyzer = Analyzer;
assert!(analyzer.detect_cycles(&nodes, &edges));
}
#[test]
fn test_detect_no_cycles() {
let nodes = vec![make_node_id("a"), make_node_id("b"), make_node_id("c")];
let edges = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("b", "c", "imports", "EXTRACTED"),
];
let analyzer = Analyzer;
assert!(!analyzer.detect_cycles(&nodes, &edges));
}
#[test]
fn test_tarjan_scc_simple() {
let edges = vec![
make_edge("a", "b", "links", "EXTRACTED"),
make_edge("b", "c", "links", "EXTRACTED"),
make_edge("c", "a", "links", "EXTRACTED"),
];
let analyzer = Analyzer;
let sccs = analyzer.tarjan_scc(&edges);
let large_scc = sccs.iter().find(|s| s.len() >= 3);
assert!(large_scc.is_some(), "a->b->c->a should be one SCC");
}
#[test]
fn test_tarjan_scc_no_cycle() {
let edges = vec![
make_edge("a", "b", "links", "EXTRACTED"),
make_edge("b", "c", "links", "EXTRACTED"),
];
let analyzer = Analyzer;
let sccs = analyzer.tarjan_scc(&edges);
for scc in &sccs {
assert_eq!(scc.len(), 1, "DAG should only have singleton SCCs");
}
}
#[test]
fn test_tarjan_scc_empty() {
let analyzer = Analyzer;
let sccs = analyzer.tarjan_scc(&[]);
assert!(sccs.is_empty());
}
#[test]
fn test_bridge_edges_simple() {
let nodes = vec![make_node_id("a"), make_node_id("b"), make_node_id("c")];
let edges = vec![
make_edge("a", "b", "connects", "EXTRACTED"),
make_edge("b", "c", "connects", "EXTRACTED"),
];
let analyzer = Analyzer;
let bridges = analyzer.bridge_edges(&nodes, &edges);
assert_eq!(bridges.len(), 2, "both edges are bridges");
}
#[test]
fn test_bridge_edges_cycle() {
let nodes = vec![make_node_id("a"), make_node_id("b"), make_node_id("c")];
let edges = vec![
make_edge("a", "b", "connects", "EXTRACTED"),
make_edge("b", "c", "connects", "EXTRACTED"),
make_edge("c", "a", "connects", "EXTRACTED"),
];
let analyzer = Analyzer;
let bridges = analyzer.bridge_edges(&nodes, &edges);
assert_eq!(bridges.len(), 0, "cycle has no bridges");
}
#[test]
fn test_bridge_edges_empty() {
let analyzer = Analyzer;
let bridges = analyzer.bridge_edges(&[], &[]);
assert!(bridges.is_empty());
}
fn make_file_node(id: &str) -> Node {
Node {
id: id.to_string(),
label: id.to_string(),
file_type: "file".to_string(),
source_file: format!("{id}.py"),
source_location: None,
community: None,
rationale: None,
docstring: None,
metadata: HashMap::new(),
}
}
#[test]
fn test_risk_scores_bridge_factor() {
let mut nodes = vec![
make_file_node("a"),
make_file_node("b"),
make_file_node("c"),
];
let edges = vec![
make_edge("a", "b", "imports", "EXTRACTED"),
make_edge("b", "c", "imports", "EXTRACTED"),
];
let churn_map: HashMap<String, usize> = [
("a".to_string(), 2),
("b".to_string(), 3),
("c".to_string(), 1),
]
.into_iter()
.collect();
let analyzer = Analyzer;
analyzer.apply_risk_scores(&mut nodes, &edges, &churn_map);
let risk_a: f64 = nodes[0].metadata["risk_score"].parse().unwrap();
let risk_b: f64 = nodes[1].metadata["risk_score"].parse().unwrap();
let risk_c: f64 = nodes[2].metadata["risk_score"].parse().unwrap();
assert!((risk_a - 4.0).abs() < 0.01, "a risk={risk_a}");
assert!((risk_b - 18.0).abs() < 0.01, "b risk={risk_b}");
assert!((risk_c - 2.0).abs() < 0.01, "c risk={risk_c}");
}
#[test]
fn test_risk_scores_no_bridges_in_cycle() {
let mut nodes = vec![
make_file_node("a"),
make_file_node("b"),
make_file_node("c"),
];
let edges = vec![
make_edge("a", "b", "connects", "EXTRACTED"),
make_edge("b", "c", "connects", "EXTRACTED"),
make_edge("c", "a", "connects", "EXTRACTED"),
];
let churn_map: HashMap<String, usize> = [
("a".to_string(), 2),
("b".to_string(), 2),
("c".to_string(), 2),
]
.into_iter()
.collect();
let analyzer = Analyzer;
analyzer.apply_risk_scores(&mut nodes, &edges, &churn_map);
for node in &nodes {
let risk: f64 = node.metadata["risk_score"].parse().unwrap();
assert!((risk - 4.0).abs() < 0.01, "{} risk={risk}", node.id);
}
}
#[test]
fn test_risk_scores_skips_non_file_nodes() {
let mut nodes = vec![make_node_id("a")]; let churn_map: HashMap<String, usize> = [("a".to_string(), 5)].into_iter().collect();
let analyzer = Analyzer;
analyzer.apply_risk_scores(&mut nodes, &[], &churn_map);
assert!(!nodes[0].metadata.contains_key("risk_score"));
}
#[test]
fn test_risk_scores_rationale_contains_bridge_factor() {
let mut nodes = vec![make_file_node("a"), make_file_node("b")];
let edges = vec![make_edge("a", "b", "imports", "EXTRACTED")];
let churn_map: HashMap<String, usize> = [("a".to_string(), 1), ("b".to_string(), 1)]
.into_iter()
.collect();
let analyzer = Analyzer;
analyzer.apply_risk_scores(&mut nodes, &edges, &churn_map);
for node in &nodes {
let rationale = node.rationale.as_deref().unwrap_or("");
assert!(
rationale.contains("bridge_factor="),
"rationale missing bridge_factor: {rationale}"
);
}
}
#[test]
fn test_topological_sort_simple() {
let edges = vec![
make_edge("a", "b", "depends", "EXTRACTED"),
make_edge("b", "c", "depends", "EXTRACTED"),
];
let analyzer = Analyzer;
let sorted = analyzer.topological_sort(&edges);
let pos = |id: &str| sorted.iter().position(|s| s == id).unwrap();
assert!(pos("a") < pos("b"), "a should come before b");
assert!(pos("b") < pos("c"), "b should come before c");
}
#[test]
fn test_topological_sort_empty() {
let analyzer = Analyzer;
let sorted = analyzer.topological_sort(&[]);
assert!(sorted.is_empty());
}
#[test]
fn test_topological_sort_isolated() {
let edges = vec![make_edge("a", "b", "depends", "EXTRACTED")];
let analyzer = Analyzer;
let sorted = analyzer.topological_sort(&edges);
assert_eq!(sorted.len(), 2);
assert_eq!(sorted[0], "a");
assert_eq!(sorted[1], "b");
}
}