use std::cmp::Ordering;
use std::collections::{HashMap, HashSet, VecDeque};
use std::hash::{Hash, Hasher};
use super::store::LiveIndex;
use crate::domain::{ReferenceKind, SymbolKind};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SymbolId {
pub path: String,
pub name: String,
pub kind: SymbolKind,
}
impl Hash for SymbolId {
fn hash<H: Hasher>(&self, state: &mut H) {
self.path.hash(state);
self.name.hash(state);
(self.kind as u8).hash(state);
}
}
impl Ord for SymbolId {
fn cmp(&self, other: &Self) -> Ordering {
self.path
.cmp(&other.path)
.then_with(|| self.name.cmp(&other.name))
.then_with(|| (self.kind as u8).cmp(&(other.kind as u8)))
}
}
impl PartialOrd for SymbolId {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
pub struct GraphProjection {
in_edges: HashMap<SymbolId, Vec<SymbolId>>,
node_count: usize,
edge_count: usize,
}
impl GraphProjection {
pub fn from_index(index: &LiveIndex) -> Self {
let mut defs_by_name: HashMap<&str, Vec<SymbolId>> = HashMap::new();
let mut node_count = 0usize;
for (path, file) in &index.files {
for sym in &file.symbols {
node_count += 1;
defs_by_name
.entry(sym.name.as_str())
.or_default()
.push(SymbolId {
path: path.clone(),
name: sym.name.clone(),
kind: sym.kind,
});
}
}
let mut in_edges: HashMap<SymbolId, Vec<SymbolId>> = HashMap::new();
for (path, file) in &index.files {
for r in &file.references {
if r.kind != ReferenceKind::Call {
continue;
}
let Some(enc_idx) = r.enclosing_symbol_index else {
continue;
};
let Some(caller_sym) = file.symbols.get(enc_idx as usize) else {
continue;
};
let caller = SymbolId {
path: path.clone(),
name: caller_sym.name.clone(),
kind: caller_sym.kind,
};
let Some(callees) = defs_by_name.get(r.name.as_str()) else {
continue;
};
for callee in callees {
if *callee == caller {
continue; }
in_edges
.entry(callee.clone())
.or_default()
.push(caller.clone());
}
}
}
let mut edge_count = 0usize;
for callers in in_edges.values_mut() {
callers.sort();
callers.dedup();
edge_count += callers.len();
}
Self {
in_edges,
node_count,
edge_count,
}
}
pub fn node_count(&self) -> usize {
self.node_count
}
pub fn edge_count(&self) -> usize {
self.edge_count
}
pub fn top_inbound_targets(&self, n: usize) -> Vec<SymbolId> {
let mut ranked: Vec<(&SymbolId, usize)> = self
.in_edges
.iter()
.map(|(id, callers)| (id, callers.len()))
.collect();
ranked.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(b.0)));
ranked
.into_iter()
.take(n)
.map(|(id, _)| id.clone())
.collect()
}
pub fn inbound_bfs(
&self,
start: &SymbolId,
max_depth: u32,
max_nodes: usize,
) -> Vec<(SymbolId, u32)> {
let mut visited: HashSet<SymbolId> = HashSet::new();
visited.insert(start.clone());
let mut queue: VecDeque<(SymbolId, u32)> = VecDeque::new();
queue.push_back((start.clone(), 0));
let mut results: Vec<(SymbolId, u32)> = Vec::new();
while let Some((node, depth)) = queue.pop_front() {
if results.len() >= max_nodes {
break;
}
if depth > 0 {
results.push((node.clone(), depth));
}
if depth >= max_depth {
continue;
}
if let Some(callers) = self.in_edges.get(&node) {
for caller in callers {
if visited.insert(caller.clone()) {
queue.push_back((caller.clone(), depth + 1));
}
}
}
}
results
}
}
const INBOUND_BFS_SAFETY_CAP: usize = 100_000;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum RiskTier {
Critical,
High,
Medium,
Low,
}
impl RiskTier {
pub fn as_str(self) -> &'static str {
match self {
RiskTier::Critical => "critical",
RiskTier::High => "high",
RiskTier::Medium => "medium",
RiskTier::Low => "low",
}
}
pub fn severity_rank(self) -> u8 {
match self {
RiskTier::Critical => 3,
RiskTier::High => 2,
RiskTier::Medium => 1,
RiskTier::Low => 0,
}
}
fn for_hop(hop: u32, is_entry_point: bool) -> Self {
if hop <= 1 {
if hop == 1 && is_entry_point {
RiskTier::Critical
} else {
RiskTier::High
}
} else if hop == 2 {
RiskTier::Medium
} else {
RiskTier::Low
}
}
}
#[derive(Clone, Debug)]
pub struct BlastNode {
pub symbol: SymbolId,
pub hop: u32,
pub risk: RiskTier,
}
fn is_entry_point(id: &SymbolId) -> bool {
id.name == "main" && matches!(id.kind, SymbolKind::Function | SymbolKind::Method)
}
pub fn compute_impact(
graph: &GraphProjection,
changed: &[SymbolId],
max_depth: u32,
) -> Vec<BlastNode> {
let changed_set: HashSet<&SymbolId> = changed.iter().collect();
let mut best_hop: HashMap<SymbolId, u32> = HashMap::new();
for start in changed {
for (reached, hop) in graph.inbound_bfs(start, max_depth, INBOUND_BFS_SAFETY_CAP) {
if changed_set.contains(&reached) {
continue; }
best_hop
.entry(reached)
.and_modify(|existing| *existing = (*existing).min(hop))
.or_insert(hop);
}
}
let mut nodes: Vec<BlastNode> = best_hop
.into_iter()
.map(|(symbol, hop)| {
let risk = RiskTier::for_hop(hop, is_entry_point(&symbol));
BlastNode { symbol, hop, risk }
})
.collect();
nodes.sort_by(|a, b| a.hop.cmp(&b.hop).then_with(|| a.symbol.cmp(&b.symbol)));
nodes
}
#[cfg(test)]
mod tests {
use super::*;
use crate::live_index::LiveIndex;
fn build_graph(files: &[(&str, &str)]) -> GraphProjection {
let dir = tempfile::tempdir().expect("tempdir");
for (rel, content) in files {
let path = dir.path().join(rel);
if let Some(parent) = path.parent() {
std::fs::create_dir_all(parent).expect("create parent dir");
}
std::fs::write(&path, content).expect("write fixture file");
}
let shared = LiveIndex::load(dir.path()).expect("load index");
let index = shared.read();
GraphProjection::from_index(&index)
}
fn sym(path: &str, name: &str) -> SymbolId {
SymbolId {
path: path.to_string(),
name: name.to_string(),
kind: SymbolKind::Function,
}
}
#[test]
fn compute_impact_excludes_hop_zero_and_is_empty_with_no_callers() {
let graph = build_graph(&[
("lib.rs", "pub fn core() -> u32 { 1 }\n"),
("a.rs", "pub fn call_a() -> u32 { core() }\n"),
]);
let changed = vec![sym("a.rs", "call_a")];
let blast = compute_impact(&graph, &changed, 2);
assert!(
blast.is_empty(),
"call_a has no callers in this fixture: {blast:?}"
);
}
#[test]
fn compute_impact_risk_tiers_by_hop() {
let graph = build_graph(&[
("lib.rs", "pub fn core() -> u32 { 1 }\n"),
("a.rs", "pub fn call_a() -> u32 { core() }\n"),
("main.rs", "fn main() { call_a(); }\n"),
]);
let changed = vec![sym("lib.rs", "core")];
let blast = compute_impact(&graph, &changed, 2);
let call_a = blast
.iter()
.find(|n| n.symbol.name == "call_a")
.expect("call_a reached at hop 1");
assert_eq!(call_a.hop, 1);
assert_eq!(call_a.risk.as_str(), "high");
let main = blast
.iter()
.find(|n| n.symbol.name == "main")
.expect("main reached at hop 2");
assert_eq!(main.hop, 2);
assert_eq!(main.risk.as_str(), "medium");
}
#[test]
fn compute_impact_entry_point_critical_at_hop_one() {
let graph = build_graph(&[
("lib.rs", "pub fn core() -> u32 { 1 }\n"),
("main.rs", "fn main() { core(); }\n"),
]);
let changed = vec![sym("lib.rs", "core")];
let blast = compute_impact(&graph, &changed, 1);
assert_eq!(blast.len(), 1);
assert_eq!(blast[0].symbol.name, "main");
assert_eq!(blast[0].hop, 1);
assert_eq!(blast[0].risk.as_str(), "critical");
}
#[test]
fn compute_impact_nearest_hop_wins_across_changed_seeds() {
let graph = build_graph(&[
("lib.rs", "pub fn core() -> u32 { 1 }\n"),
("a.rs", "pub fn call_a() -> u32 { core() }\n"),
("b.rs", "pub fn call_b() -> u32 { core() }\n"),
("main.rs", "fn main() { call_a(); call_b(); }\n"),
]);
let changed = vec![sym("lib.rs", "core"), sym("a.rs", "call_a")];
let blast = compute_impact(&graph, &changed, 3);
let main = blast
.iter()
.find(|n| n.symbol.name == "main")
.expect("main reached");
assert_eq!(main.hop, 1, "nearest hop across changed seeds must win");
}
#[test]
fn compute_impact_reaches_across_qualified_module_call() {
let graph = build_graph(&[
("lib.rs", "pub fn core() -> u32 { 1 }\n"),
("a.rs", "pub fn call_a() -> u32 { core() }\n"),
("main.rs", "mod a;\nfn main() { a::call_a(); }\n"),
]);
let changed = vec![sym("a.rs", "call_a")];
let blast = compute_impact(&graph, &changed, 1);
assert_eq!(
blast.len(),
1,
"main() calling a::call_a() must resolve as a caller: {blast:?}"
);
assert_eq!(blast[0].symbol.name, "main");
}
#[test]
fn compute_impact_empty_changed_set_yields_empty_blast() {
let graph = build_graph(&[("lib.rs", "pub fn core() -> u32 { 1 }\n")]);
assert!(compute_impact(&graph, &[], 5).is_empty());
}
}