use crate::types::{FunctionGraph, FunctionNode, FunctionEdge};
use jsxbin_parser::types::Token;
use log::{debug, trace};
use std::collections::HashMap;
pub struct GraphBuilder {
functions: HashMap<String, usize>,
next_id: usize,
}
impl GraphBuilder {
pub fn new() -> Self {
GraphBuilder {
functions: HashMap::new(),
next_id: 0,
}
}
pub fn build_graph(&mut self, tokens: &[Token]) -> FunctionGraph {
debug!("Building function call graph from {} tokens", tokens.len());
let mut nodes = Vec::new();
let mut edges = Vec::new();
let mut call_counts: HashMap<(usize, usize), usize> = HashMap::new();
self.collect_functions(tokens, &mut nodes);
self.collect_calls(tokens, &mut nodes, &mut call_counts);
for ((from, to), count) in call_counts {
edges.push(FunctionEdge { from, to, count });
}
debug!("Built graph with {} nodes and {} edges", nodes.len(), edges.len());
FunctionGraph { nodes, edges }
}
fn collect_functions(&mut self, tokens: &[Token], nodes: &mut Vec<FunctionNode>) {
for token in tokens {
match token {
Token::Function { name, params, .. } => {
let id = self.next_id;
self.next_id += 1;
trace!("Found function: {} with {} params", name, params.len());
self.functions.insert(name.clone(), id);
nodes.push(FunctionNode {
id,
name: name.clone(),
params: params.len(),
calls_count: 0,
is_exported: false,
});
}
Token::Block(block) => {
self.collect_functions(&block.statements, nodes);
}
_ => {}
}
}
}
fn collect_calls(
&self,
tokens: &[Token],
nodes: &mut [FunctionNode],
calls: &mut HashMap<(usize, usize), usize>,
) {
for token in tokens {
match token {
Token::FunctionCall { callee, .. } => {
if let Token::Identifier(func_name) = &*callee.token {
if let Some(&called_id) = self.functions.get(func_name) {
trace!("Found function call: {}", func_name);
if let Some(node) = nodes.iter_mut().find(|n| n.id == called_id) {
node.calls_count += 1;
}
}
}
}
Token::Block(block) => {
self.collect_calls(&block.statements, nodes, calls);
}
_ => {}
}
}
}
pub fn find_entry_points(graph: &FunctionGraph) -> Vec<usize> {
let defined: std::collections::HashSet<_> = graph.nodes.iter().map(|n| n.id).collect();
let called: std::collections::HashSet<_> = graph.edges.iter().map(|e| e.to).collect();
called.difference(&defined).copied().collect()
}
pub fn calculate_complexity(graph: &FunctionGraph) -> f64 {
if graph.nodes.is_empty() {
return 0.0;
}
let num_nodes = graph.nodes.len() as f64;
let num_edges = graph.edges.len() as f64;
let num_components = 1.0;
num_edges - num_nodes + 2.0 * num_components
}
pub fn find_cycles(graph: &FunctionGraph) -> Vec<Vec<usize>> {
let mut cycles = Vec::new();
let mut visited = vec![false; graph.nodes.len()];
let mut rec_stack = vec![false; graph.nodes.len()];
let mut path = Vec::new();
for i in 0..graph.nodes.len() {
if !visited[i] {
Self::find_cycles_dfs(
i,
graph,
&mut visited,
&mut rec_stack,
&mut path,
&mut cycles,
);
}
}
cycles
}
fn find_cycles_dfs(
node: usize,
graph: &FunctionGraph,
visited: &mut [bool],
rec_stack: &mut [bool],
path: &mut Vec<usize>,
cycles: &mut Vec<Vec<usize>>,
) {
visited[node] = true;
rec_stack[node] = true;
path.push(node);
for edge in graph.edges.iter().filter(|e| e.from == node) {
let next = edge.to;
if !visited[next] {
Self::find_cycles_dfs(next, graph, visited, rec_stack, path, cycles);
} else if rec_stack[next] {
if let Some(pos) = path.iter().position(|&n| n == next) {
cycles.push(path[pos..].to_vec());
}
}
}
path.pop();
rec_stack[node] = false;
}
}
impl Default for GraphBuilder {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_build_empty_graph() {
let mut builder = GraphBuilder::new();
let tokens = vec![];
let graph = builder.build_graph(&tokens);
assert_eq!(graph.nodes.len(), 0);
assert_eq!(graph.edges.len(), 0);
}
#[test]
fn test_collect_functions() {
let mut builder = GraphBuilder::new();
let tokens = vec![
Token::Function {
name: "foo".to_string(),
params: vec!["x".to_string()],
body: Box::new(jsxbin_parser::types::Block {
statements: Vec::new(),
}),
},
Token::Function {
name: "bar".to_string(),
params: vec![],
body: Box::new(jsxbin_parser::types::Block {
statements: Vec::new(),
}),
},
];
let graph = builder.build_graph(&tokens);
assert_eq!(graph.nodes.len(), 2);
}
#[test]
fn test_complexity_calculation() {
let graph = FunctionGraph {
nodes: vec![
FunctionNode {
id: 0,
name: "main".to_string(),
params: 0,
calls_count: 2,
is_exported: true,
},
FunctionNode {
id: 1,
name: "helper".to_string(),
params: 1,
calls_count: 1,
is_exported: false,
},
],
edges: vec![FunctionEdge {
from: 0,
to: 1,
count: 1,
}],
};
let complexity = GraphBuilder::calculate_complexity(&graph);
assert!(complexity >= 0.0);
}
}