use std::collections::HashSet;
use std::hash::Hash;
use petgraph::graph::NodeIndex;
use petgraph::Direction as PgDirection;
use super::CodeGraph;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Dir {
Callers,
Callees,
}
impl Dir {
fn via(self) -> &'static str {
match self {
Dir::Callees => "calls",
Dir::Callers => "called_by",
}
}
}
#[derive(Debug, Clone)]
pub struct Reached {
pub name: String,
pub file: String,
pub start_line: usize,
pub distance: u32,
pub via: &'static str,
}
pub struct NodeMeta {
pub name: String,
pub file: String,
pub start_line: usize,
}
pub trait Adjacency {
type Node: Copy + Eq + Hash;
fn seeds(&self, name: &str) -> Vec<Self::Node>;
fn neighbors(&self, node: Self::Node, dir: Dir) -> Vec<Self::Node>;
fn meta(&self, node: Self::Node) -> NodeMeta;
}
#[must_use]
pub fn reachable_over<A: Adjacency>(adj: &A, seed: &str, dir: Dir, max_hops: u32) -> Vec<Reached> {
let seeds = adj.seeds(seed);
if seeds.is_empty() {
return Vec::new();
}
let via = dir.via();
let mut visited: HashSet<A::Node> = seeds.iter().copied().collect();
let mut frontier = seeds;
let mut reached = Vec::new();
let mut hop = 0;
while hop < max_hops && !frontier.is_empty() {
hop += 1;
let mut next = Vec::new();
for node in frontier {
for neighbor in adj.neighbors(node, dir) {
if visited.insert(neighbor) {
let m = adj.meta(neighbor);
reached.push(Reached {
name: m.name,
file: m.file,
start_line: m.start_line,
distance: hop,
via,
});
next.push(neighbor);
}
}
}
frontier = next;
}
reached
}
impl Adjacency for CodeGraph {
type Node = NodeIndex;
fn seeds(&self, name: &str) -> Vec<NodeIndex> {
self.by_name.get(name).cloned().unwrap_or_default()
}
fn neighbors(&self, node: NodeIndex, dir: Dir) -> Vec<NodeIndex> {
let pg_dir = match dir {
Dir::Callees => PgDirection::Outgoing,
Dir::Callers => PgDirection::Incoming,
};
self.graph.neighbors_directed(node, pg_dir).collect()
}
fn meta(&self, node: NodeIndex) -> NodeMeta {
let symbol = &self.graph[node];
NodeMeta {
name: symbol.name.clone(),
file: symbol.file.clone(),
start_line: symbol.start_line,
}
}
}