use std::collections::{BTreeMap, HashMap};
use petgraph::graph::NodeIndex;
use super::CodeGraph;
use crate::types::Tier;
#[derive(Debug, Clone)]
pub struct CommunityMember {
pub name: String,
pub kind: String,
pub file: String,
pub start_line: usize,
pub tier: Tier,
}
#[derive(Debug, Clone)]
pub struct Community {
pub id: usize,
pub members: Vec<CommunityMember>,
}
impl CodeGraph {
#[must_use]
pub fn communities(&self) -> Vec<Community> {
let n = self.graph.node_count();
if n == 0 {
return Vec::new();
}
let mut weights: HashMap<(usize, usize), f64> = HashMap::new();
for edge in self.graph.edge_indices() {
let Some((a, b)) = self.graph.edge_endpoints(edge) else {
continue;
};
let (a, b) = (a.index(), b.index());
if a == b {
continue;
}
let key = if a < b { (a, b) } else { (b, a) };
*weights.entry(key).or_insert(0.0) += 1.0;
}
let edges: Vec<(usize, usize, f64)> =
weights.into_iter().map(|((a, b), w)| (a, b, w)).collect();
let labels = crate::community::louvain(n, &edges);
let mut groups: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for (idx, &label) in labels.iter().enumerate() {
groups.entry(label).or_default().push(idx);
}
let mut clusters: Vec<Vec<CommunityMember>> = groups
.into_values()
.map(|nodes| {
let mut members: Vec<CommunityMember> = nodes
.into_iter()
.map(|i| {
let symbol = &self.graph[NodeIndex::new(i)];
CommunityMember {
name: symbol.name.clone(),
kind: symbol.kind.clone(),
file: symbol.file.clone(),
start_line: symbol.start_line,
tier: symbol.tier,
}
})
.collect();
members.sort_by(|a, b| {
(a.file.as_str(), a.start_line, a.name.as_str()).cmp(&(
b.file.as_str(),
b.start_line,
b.name.as_str(),
))
});
members
})
.collect();
clusters.sort_by(|a, b| {
b.len().cmp(&a.len()).then_with(|| {
let key = |m: &[CommunityMember]| {
m.first()
.map(|f| (f.file.clone(), f.start_line, f.name.clone()))
};
key(a).cmp(&key(b))
})
});
clusters
.into_iter()
.enumerate()
.map(|(id, members)| Community { id, members })
.collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn write(dir: &std::path::Path, name: &str, body: &str) {
std::fs::write(dir.join(name), body).unwrap();
}
#[test]
fn communities_split_two_call_clusters() {
let dir = tempfile::tempdir().unwrap();
write(
dir.path(),
"lib.rs",
"\
fn a_leaf() {}
fn a_mid() { a_leaf(); }
fn a_top() { a_mid(); a_leaf(); }
fn b_leaf() {}
fn b_mid() { b_leaf(); }
fn b_top() { b_mid(); b_leaf(); }
",
);
let graph = CodeGraph::build(dir.path()).unwrap();
let comms = graph.communities();
assert_eq!(comms.len(), 2, "expected two clusters: {comms:?}");
assert_eq!(comms[0].id, 0);
assert_eq!(comms[1].id, 1);
for comm in &comms {
let prefixes: std::collections::BTreeSet<&str> =
comm.members.iter().map(|m| &m.name[..2]).collect();
assert_eq!(prefixes.len(), 1, "cluster mixes chains: {comm:?}");
}
let again = CodeGraph::build(dir.path()).unwrap().communities();
let names = |cs: &[Community]| -> Vec<Vec<String>> {
cs.iter()
.map(|c| c.members.iter().map(|m| m.name.clone()).collect())
.collect()
};
assert_eq!(names(&comms), names(&again));
}
}