arbor_graph/

impact.rs

//! Impact analysis for code changes.
//!
//! This module provides bidirectional BFS traversal to find all nodes
//! affected by a change to a target node. It answers the question:
//! "What breaks if I change this?"

use crate::edge::EdgeKind;
use crate::graph::{ArborGraph, NodeId};
use crate::query::NodeInfo;
use petgraph::visit::EdgeRef;
use petgraph::Direction;
use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet, VecDeque};
use std::time::Instant;

/// Severity of impact based on hop distance from target.
///
/// Never construct directly — always use `from_hops()`.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub enum ImpactSeverity {
    /// 1 hop - immediate callers/callees
    Direct = 0,
    /// 2-3 hops - transitively connected
    Transitive = 1,
    /// 4+ hops - distantly connected
    Distant = 2,
}

impl ImpactSeverity {
    /// Derives severity from hop distance.
    ///
    /// This is the ONLY way to create an ImpactSeverity.
    /// Thresholds: 1 hop = Direct, 2-3 = Transitive, 4+ = Distant
    pub fn from_hops(hops: usize) -> Self {
        match hops {
            0 | 1 => ImpactSeverity::Direct,
            2 | 3 => ImpactSeverity::Transitive,
            _ => ImpactSeverity::Distant,
        }
    }

    /// Returns a human-readable description.
    pub fn as_str(&self) -> &'static str {
        match self {
            ImpactSeverity::Direct => "direct",
            ImpactSeverity::Transitive => "transitive",
            ImpactSeverity::Distant => "distant",
        }
    }
}

impl std::fmt::Display for ImpactSeverity {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.as_str())
    }
}

/// Direction of impact from the target node.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum ImpactDirection {
    /// Nodes that depend on the target (incoming edges).
    /// These break if the target's interface changes.
    Upstream,
    /// Nodes the target depends on (outgoing edges).
    /// Changes here may require updating the target.
    Downstream,
}

impl std::fmt::Display for ImpactDirection {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            ImpactDirection::Upstream => write!(f, "upstream"),
            ImpactDirection::Downstream => write!(f, "downstream"),
        }
    }
}

/// A node affected by a change to the target.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct AffectedNode {
    /// The node's graph index.
    pub node_id: NodeId,
    /// Full node information.
    pub node_info: NodeInfo,
    /// Severity derived from hop distance.
    pub severity: ImpactSeverity,
    /// Number of edges from target to this node.
    pub hop_distance: usize,
    /// The edge kind of the first hop that led to this node.
    /// This explains why this node is in the impact set.
    pub entry_edge: EdgeKind,
    /// Whether this node is upstream or downstream of target.
    pub direction: ImpactDirection,
}

/// Complete impact analysis result.
#[derive(Debug, Serialize, Deserialize)]
pub struct ImpactAnalysis {
    /// The target node being analyzed.
    pub target: NodeInfo,
    /// Nodes that depend on the target (callers, importers, etc.)
    pub upstream: Vec<AffectedNode>,
    /// Nodes the target depends on (callees, imports, etc.)
    pub downstream: Vec<AffectedNode>,
    /// Total count of affected nodes.
    pub total_affected: usize,
    /// Maximum depth searched.
    pub max_depth: usize,
    /// Time taken in milliseconds.
    pub query_time_ms: u64,
}

impl ImpactAnalysis {
    /// Returns all affected nodes (upstream + downstream) sorted by severity.
    pub fn all_affected(&self) -> Vec<&AffectedNode> {
        let mut all: Vec<&AffectedNode> =
            self.upstream.iter().chain(self.downstream.iter()).collect();

        // Stable sort: severity → hop_distance → node_id
        all.sort_by(|a, b| {
            a.severity
                .cmp(&b.severity)
                .then_with(|| a.hop_distance.cmp(&b.hop_distance))
                .then_with(|| a.node_info.id.cmp(&b.node_info.id))
        });

        all
    }

    /// Returns only direct (1-hop) affected nodes.
    pub fn direct_only(&self) -> Vec<&AffectedNode> {
        self.all_affected()
            .into_iter()
            .filter(|n| n.severity == ImpactSeverity::Direct)
            .collect()
    }

    /// Returns a summary suitable for CLI output.
    pub fn summary(&self) -> String {
        let direct = self
            .all_affected()
            .iter()
            .filter(|n| n.severity == ImpactSeverity::Direct)
            .count();
        let transitive = self
            .all_affected()
            .iter()
            .filter(|n| n.severity == ImpactSeverity::Transitive)
            .count();
        let distant = self
            .all_affected()
            .iter()
            .filter(|n| n.severity == ImpactSeverity::Distant)
            .count();

        format!(
            "Blast Radius: {} nodes (direct: {}, transitive: {}, distant: {})",
            self.total_affected, direct, transitive, distant
        )
    }
}

impl ArborGraph {
    /// Analyzes the impact of changing a node.
    ///
    /// Performs bidirectional BFS from the target:
    /// - Upstream: nodes that depend on target (would break if target changes)
    /// - Downstream: nodes target depends on (may require target updates)
    ///
    /// # Arguments
    /// * `target` - The node to analyze
    /// * `max_depth` - Maximum hop distance to traverse (0 = unlimited)
    ///
    /// # Returns
    /// Complete impact analysis with affected nodes sorted by severity.
    pub fn analyze_impact(&self, target: NodeId, max_depth: usize) -> ImpactAnalysis {
        let start = Instant::now();

        let target_node = match self.get(target) {
            Some(node) => NodeInfo::from(node),
            None => {
                return ImpactAnalysis {
                    target: NodeInfo {
                        id: String::new(),
                        name: String::new(),
                        qualified_name: String::new(),
                        kind: String::new(),
                        file: String::new(),
                        line_start: 0,
                        line_end: 0,
                        signature: None,
                        centrality: 0.0,
                    },
                    upstream: Vec::new(),
                    downstream: Vec::new(),
                    total_affected: 0,
                    max_depth,
                    query_time_ms: 0,
                };
            }
        };

        let effective_depth = if max_depth == 0 {
            usize::MAX
        } else {
            max_depth
        };

        let upstream = self.bfs_impact(target, Direction::Incoming, effective_depth);
        let downstream = self.bfs_impact(target, Direction::Outgoing, effective_depth);

        let total = upstream.len() + downstream.len();
        let elapsed = start.elapsed().as_millis() as u64;

        ImpactAnalysis {
            target: target_node,
            upstream,
            downstream,
            total_affected: total,
            max_depth,
            query_time_ms: elapsed,
        }
    }

    /// BFS traversal in one direction from target.
    fn bfs_impact(
        &self,
        target: NodeId,
        direction: Direction,
        max_depth: usize,
    ) -> Vec<AffectedNode> {
        let mut result = Vec::new();
        let mut visited: HashSet<NodeId> = HashSet::new();
        let mut queue: VecDeque<(NodeId, usize, EdgeKind)> = VecDeque::new();

        // Track entry edges for each node (first edge that reaches it)
        let mut entry_edges: HashMap<NodeId, EdgeKind> = HashMap::new();

        visited.insert(target);

        // Seed queue with immediate neighbors
        for edge_ref in self.graph.edges_directed(target, direction) {
            let neighbor = match direction {
                Direction::Incoming => edge_ref.source(),
                Direction::Outgoing => edge_ref.target(),
            };

            if !visited.contains(&neighbor) {
                let edge_kind = edge_ref.weight().kind;
                queue.push_back((neighbor, 1, edge_kind));
                entry_edges.insert(neighbor, edge_kind);
            }
        }

        while let Some((current, depth, entry_edge)) = queue.pop_front() {
            if depth > max_depth || visited.contains(&current) {
                continue;
            }

            visited.insert(current);

            if let Some(node) = self.get(current) {
                let mut node_info = NodeInfo::from(node);
                node_info.centrality = self.centrality(current);

                let impact_direction = match direction {
                    Direction::Incoming => ImpactDirection::Upstream,
                    Direction::Outgoing => ImpactDirection::Downstream,
                };

                result.push(AffectedNode {
                    node_id: current,
                    node_info,
                    severity: ImpactSeverity::from_hops(depth),
                    hop_distance: depth,
                    entry_edge,
                    direction: impact_direction,
                });
            }

            // Continue BFS if not at max depth
            if depth < max_depth {
                for edge_ref in self.graph.edges_directed(current, direction) {
                    let neighbor = match direction {
                        Direction::Incoming => edge_ref.source(),
                        Direction::Outgoing => edge_ref.target(),
                    };

                    if !visited.contains(&neighbor) {
                        let next_entry = *entry_edges.get(&neighbor).unwrap_or(&entry_edge);
                        queue.push_back((neighbor, depth + 1, next_entry));

                        // Store entry edge for first arrival
                        entry_edges
                            .entry(neighbor)
                            .or_insert(edge_ref.weight().kind);
                    }
                }
            }
        }

        // Sort by severity → hop_distance → id for stable ordering
        result.sort_by(|a, b| {
            a.severity
                .cmp(&b.severity)
                .then_with(|| a.hop_distance.cmp(&b.hop_distance))
                .then_with(|| a.node_info.id.cmp(&b.node_info.id))
        });

        result
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::edge::Edge;
    use arbor_core::{CodeNode, NodeKind};

    fn make_node(name: &str) -> CodeNode {
        CodeNode::new(name, name, NodeKind::Function, "test.rs")
    }

    #[test]
    fn test_severity_from_hops() {
        assert_eq!(ImpactSeverity::from_hops(0), ImpactSeverity::Direct);
        assert_eq!(ImpactSeverity::from_hops(1), ImpactSeverity::Direct);
        assert_eq!(ImpactSeverity::from_hops(2), ImpactSeverity::Transitive);
        assert_eq!(ImpactSeverity::from_hops(3), ImpactSeverity::Transitive);
        assert_eq!(ImpactSeverity::from_hops(4), ImpactSeverity::Distant);
        assert_eq!(ImpactSeverity::from_hops(100), ImpactSeverity::Distant);
    }

    #[test]
    fn test_empty_graph() {
        let graph = ArborGraph::new();
        let result = graph.analyze_impact(NodeId::new(0), 5);
        assert_eq!(result.total_affected, 0);
        assert!(result.upstream.is_empty());
        assert!(result.downstream.is_empty());
    }

    #[test]
    fn test_single_node() {
        let mut graph = ArborGraph::new();
        let id = graph.add_node(make_node("lonely"));
        let result = graph.analyze_impact(id, 5);
        assert_eq!(result.total_affected, 0);
        assert_eq!(result.target.name, "lonely");
    }

    #[test]
    fn test_linear_chain() {
        // A → B → C
        let mut graph = ArborGraph::new();
        let a = graph.add_node(make_node("a"));
        let b = graph.add_node(make_node("b"));
        let c = graph.add_node(make_node("c"));

        graph.add_edge(a, b, Edge::new(EdgeKind::Calls));
        graph.add_edge(b, c, Edge::new(EdgeKind::Calls));

        // Impact of B
        let result = graph.analyze_impact(b, 5);

        // Upstream: A calls B
        assert_eq!(result.upstream.len(), 1);
        assert_eq!(result.upstream[0].node_info.name, "a");
        assert_eq!(result.upstream[0].hop_distance, 1);
        assert_eq!(result.upstream[0].severity, ImpactSeverity::Direct);

        // Downstream: B calls C
        assert_eq!(result.downstream.len(), 1);
        assert_eq!(result.downstream[0].node_info.name, "c");
        assert_eq!(result.downstream[0].hop_distance, 1);
    }

    #[test]
    fn test_diamond_pattern() {
        //     A
        //    / \
        //   B   C
        //    \ /
        //     D
        let mut graph = ArborGraph::new();
        let a = graph.add_node(make_node("a"));
        let b = graph.add_node(make_node("b"));
        let c = graph.add_node(make_node("c"));
        let d = graph.add_node(make_node("d"));

        graph.add_edge(a, b, Edge::new(EdgeKind::Calls));
        graph.add_edge(a, c, Edge::new(EdgeKind::Calls));
        graph.add_edge(b, d, Edge::new(EdgeKind::Calls));
        graph.add_edge(c, d, Edge::new(EdgeKind::Calls));

        // Impact of A
        let result = graph.analyze_impact(a, 5);

        // Downstream should have B, C (depth 1) and D (depth 2)
        assert_eq!(result.downstream.len(), 3);

        let names: Vec<&str> = result
            .downstream
            .iter()
            .map(|n| n.node_info.name.as_str())
            .collect();
        assert!(names.contains(&"b"));
        assert!(names.contains(&"c"));
        assert!(names.contains(&"d"));

        // D should be transitive
        let d_node = result
            .downstream
            .iter()
            .find(|n| n.node_info.name == "d")
            .unwrap();
        assert_eq!(d_node.hop_distance, 2);
        assert_eq!(d_node.severity, ImpactSeverity::Transitive);
    }

    #[test]
    fn test_cycle_no_infinite_loop() {
        // A → B → C → A (cycle)
        let mut graph = ArborGraph::new();
        let a = graph.add_node(make_node("a"));
        let b = graph.add_node(make_node("b"));
        let c = graph.add_node(make_node("c"));

        graph.add_edge(a, b, Edge::new(EdgeKind::Calls));
        graph.add_edge(b, c, Edge::new(EdgeKind::Calls));
        graph.add_edge(c, a, Edge::new(EdgeKind::Calls)); // Cycle back

        // Should not hang
        let result = graph.analyze_impact(a, 10);

        // Should find B and C downstream
        assert_eq!(result.downstream.len(), 2);

        // Upstream: C → A (depth 1), and B → C means B is also reachable at depth 2
        assert_eq!(result.upstream.len(), 2);
        let upstream_names: Vec<&str> = result
            .upstream
            .iter()
            .map(|n| n.node_info.name.as_str())
            .collect();
        assert!(upstream_names.contains(&"c"));
        assert!(upstream_names.contains(&"b"));
    }

    #[test]
    fn test_max_depth_limit() {
        // A → B → C → D → E
        let mut graph = ArborGraph::new();
        let a = graph.add_node(make_node("a"));
        let b = graph.add_node(make_node("b"));
        let c = graph.add_node(make_node("c"));
        let d = graph.add_node(make_node("d"));
        let e = graph.add_node(make_node("e"));

        graph.add_edge(a, b, Edge::new(EdgeKind::Calls));
        graph.add_edge(b, c, Edge::new(EdgeKind::Calls));
        graph.add_edge(c, d, Edge::new(EdgeKind::Calls));
        graph.add_edge(d, e, Edge::new(EdgeKind::Calls));

        // Impact of A with max_depth = 2
        let result = graph.analyze_impact(a, 2);

        // Should only find B (depth 1) and C (depth 2), not D or E
        assert_eq!(result.downstream.len(), 2);

        let names: Vec<&str> = result
            .downstream
            .iter()
            .map(|n| n.node_info.name.as_str())
            .collect();
        assert!(names.contains(&"b"));
        assert!(names.contains(&"c"));
        assert!(!names.contains(&"d"));
        assert!(!names.contains(&"e"));
    }

    #[test]
    fn test_stable_ordering() {
        // Verify that results are deterministically ordered
        let mut graph = ArborGraph::new();
        let target = graph.add_node(make_node("target"));
        let z = graph.add_node(make_node("z_caller"));
        let a = graph.add_node(make_node("a_caller"));
        let m = graph.add_node(make_node("m_caller"));

        graph.add_edge(z, target, Edge::new(EdgeKind::Calls));
        graph.add_edge(a, target, Edge::new(EdgeKind::Calls));
        graph.add_edge(m, target, Edge::new(EdgeKind::Calls));

        let result = graph.analyze_impact(target, 5);

        // All are depth 1 (Direct), so should be sorted by name (which equals ID here)
        let names: Vec<&str> = result
            .upstream
            .iter()
            .map(|n| n.node_info.name.as_str())
            .collect();
        // Sorted alphabetically by node_info.id
        assert_eq!(names.len(), 3);
        assert!(names.contains(&"a_caller"));
        assert!(names.contains(&"m_caller"));
        assert!(names.contains(&"z_caller"));
    }
}