use std::collections::{HashMap, HashSet};
use std::path::Path;
use tree_sitter::{Node, Parser};
use crate::errors::{Error, Result};
use crate::extract::rust_files;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum FlowDir {
DependsOn,
FlowsInto,
}
impl FlowDir {
#[must_use]
pub fn as_str(self) -> &'static str {
match self {
FlowDir::DependsOn => "depends_on",
FlowDir::FlowsInto => "flows_into",
}
}
}
#[derive(Debug, Clone)]
pub struct FlowStep {
pub name: String,
pub distance: u32,
}
#[derive(Debug, Clone)]
pub struct DepEdge {
pub dependent: String,
pub depends_on: String,
pub line: usize,
}
#[derive(Default)]
struct FnAccum {
locals: HashSet<String>,
edges: Vec<DepEdge>,
}
struct FnData {
depends: HashMap<String, Vec<String>>,
flows_into: HashMap<String, Vec<String>>,
edges: Vec<DepEdge>,
}
pub struct Dataflow {
functions: HashMap<String, FnData>,
}
impl Dataflow {
pub fn build(root: &Path) -> Result<Self> {
let mut acc: HashMap<String, FnAccum> = HashMap::new();
for file in rust_files(root) {
if let Ok(source) = std::fs::read_to_string(&file) {
let _ = collect_file(&source, &mut acc);
}
}
let mut functions = HashMap::new();
for (name, accum) in acc {
let mut depends: HashMap<String, Vec<String>> = HashMap::new();
let mut flows_into: HashMap<String, Vec<String>> = HashMap::new();
let mut edges = Vec::new();
for edge in accum.edges {
if edge.dependent != edge.depends_on && accum.locals.contains(&edge.depends_on) {
depends
.entry(edge.dependent.clone())
.or_default()
.push(edge.depends_on.clone());
flows_into
.entry(edge.depends_on.clone())
.or_default()
.push(edge.dependent.clone());
edges.push(edge);
}
}
functions.insert(
name,
FnData {
depends,
flows_into,
edges,
},
);
}
Ok(Self { functions })
}
#[must_use]
pub fn has_function(&self, function: &str) -> bool {
self.functions.contains_key(function)
}
#[must_use]
pub fn edges(&self, function: &str) -> &[DepEdge] {
self.functions.get(function).map_or(&[], |f| &f.edges)
}
#[must_use]
pub fn flow(&self, function: &str, var: &str, dir: FlowDir, max_hops: u32) -> Vec<FlowStep> {
let Some(data) = self.functions.get(function) else {
return Vec::new();
};
let adjacency = match dir {
FlowDir::DependsOn => &data.depends,
FlowDir::FlowsInto => &data.flows_into,
};
let mut visited: HashSet<String> = HashSet::from([var.to_string()]);
let mut frontier = vec![var.to_string()];
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 {
if let Some(neighbors) = adjacency.get(node) {
for neighbor in neighbors {
if visited.insert(neighbor.clone()) {
reached.push(FlowStep {
name: neighbor.clone(),
distance: hop,
});
next.push(neighbor.clone());
}
}
}
}
frontier = next;
}
reached
}
}
fn collect_file(source: &str, acc: &mut HashMap<String, FnAccum>) -> Result<()> {
let mut parser = Parser::new();
parser
.set_language(&tree_sitter_rust::LANGUAGE.into())
.map_err(|e| Error::Parse(e.to_string()))?;
let tree = parser
.parse(source, None)
.ok_or_else(|| Error::Parse("tree-sitter produced no tree".to_string()))?;
let bytes = source.as_bytes();
let mut stack: Vec<(Node, Option<String>)> = vec![(tree.root_node(), None)];
while let Some((node, enclosing)) = stack.pop() {
let mut inner = enclosing.clone();
match node.kind() {
"function_item" => {
if let Some(name) = node
.child_by_field_name("name")
.and_then(|n| n.utf8_text(bytes).ok())
{
inner = Some(name.to_string());
let mut params = Vec::new();
if let Some(parameters) = node.child_by_field_name("parameters") {
collect_idents(parameters, bytes, &mut |id| params.push(id));
}
let entry = acc.entry(name.to_string()).or_default();
for id in params {
entry.locals.insert(id);
}
}
}
"let_declaration" => add_edges(node, "pattern", "value", &enclosing, bytes, acc, true),
"assignment_expression" => {
add_edges(node, "left", "right", &enclosing, bytes, acc, false);
}
_ => {}
}
let mut cursor = node.walk();
for child in node.children(&mut cursor) {
stack.push((child, inner.clone()));
}
}
Ok(())
}
fn add_edges(
node: Node,
target_field: &str,
value_field: &str,
enclosing: &Option<String>,
bytes: &[u8],
acc: &mut HashMap<String, FnAccum>,
declares: bool,
) {
let Some(function) = enclosing else {
return;
};
let Some(target) = node
.child_by_field_name(target_field)
.and_then(|n| ident_text(n, bytes))
else {
return;
};
let line = node.start_position().row + 1;
let mut used = Vec::new();
if let Some(value) = node.child_by_field_name(value_field) {
collect_idents(value, bytes, &mut |id| used.push(id));
}
let entry = acc.entry(function.clone()).or_default();
if declares {
entry.locals.insert(target.clone());
}
for id in used {
entry.edges.push(DepEdge {
dependent: target.clone(),
depends_on: id,
line,
});
}
}
fn collect_idents(node: Node, bytes: &[u8], f: &mut dyn FnMut(String)) {
let mut stack = vec![node];
while let Some(current) = stack.pop() {
if current.kind() == "identifier" {
if let Ok(text) = current.utf8_text(bytes) {
f(text.to_string());
}
}
let mut cursor = current.walk();
for child in current.children(&mut cursor) {
stack.push(child);
}
}
}
fn ident_text(node: Node, bytes: &[u8]) -> Option<String> {
let mut stack = vec![node];
while let Some(current) = stack.pop() {
if current.kind() == "identifier" {
return current.utf8_text(bytes).ok().map(str::to_string);
}
let mut cursor = current.walk();
for child in current.children(&mut cursor) {
stack.push(child);
}
}
None
}
#[cfg(test)]
mod tests {
use super::*;
fn build(src: &str) -> Dataflow {
let dir = tempfile::tempdir().unwrap();
std::fs::write(dir.path().join("a.rs"), src).unwrap();
Dataflow::build(dir.path()).unwrap()
}
#[test]
fn tracks_transitive_dependence() {
let flow = build(
"\
fn f(a: i32) -> i32 {
let b = a + 1;
let c = b * 2;
c
}
",
);
assert!(flow.has_function("f"));
let deps = flow.flow("f", "c", FlowDir::DependsOn, 5);
let names: Vec<&str> = deps.iter().map(|s| s.name.as_str()).collect();
assert!(names.contains(&"b"));
assert!(names.contains(&"a"));
}
#[test]
fn tracks_forward_flow() {
let flow = build(
"\
fn f(a: i32) -> i32 {
let b = a + 1;
let c = b * 2;
c
}
",
);
let into = flow.flow("f", "a", FlowDir::FlowsInto, 5);
let names: Vec<&str> = into.iter().map(|s| s.name.as_str()).collect();
assert!(names.contains(&"b"));
assert!(names.contains(&"c"));
}
#[test]
fn non_locals_are_filtered() {
let flow = build("fn f() { let x = helper(); }");
assert!(flow.flow("f", "x", FlowDir::DependsOn, 5).is_empty());
}
}