geographdb_core/algorithms/

slicing.rs

//! Program Slicing - Backward and Forward Slicing
//!
//! Program slicing extracts all statements that affect or are affected by
//! a particular program point (the slicing criterion).
//!
//! # Types
//!
//! - **Backward Slice**: All statements that affect the criterion
//! - **Forward Slice**: All statements affected by the criterion
//! - **Full Slice**: Union of backward and forward slices
//!
//! # Applications
//!
//! - Impact analysis (what breaks if I change this?)
//! - Debugging (what code affects this variable?)
//! - Dead code detection (unreachable from entry)
//! - Optimization (remove unused code)

use crate::algorithms::astar::CfgGraphNode;
use std::collections::{HashMap, HashSet, VecDeque};

/// Result of program slicing
#[derive(Debug, Clone)]
pub struct SliceResult {
    /// Nodes in the slice
    pub nodes: HashSet<u64>,
    /// Edges within the slice (source, target)
    pub edges: Vec<(u64, u64)>,
    /// Slice direction
    pub direction: SliceDirection,
    /// Slicing criterion (target node)
    pub criterion: u64,
}

/// Direction of program slice
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SliceDirection {
    /// Backward slice (what affects criterion)
    Backward,
    /// Forward slice (what is affected by criterion)
    Forward,
}

/// Compute backward slice from a criterion node
///
/// The backward slice contains all nodes that can reach the criterion.
/// This answers: "What code affects this point?"
///
/// # Arguments
/// * `nodes` - CFG nodes
/// * `criterion` - Slicing criterion (target node)
///
/// # Returns
/// SliceResult with all nodes and edges in the backward slice
pub fn backward_slice(nodes: &[CfgGraphNode], criterion: u64) -> SliceResult {
    // Build predecessor map
    let mut predecessors: HashMap<u64, Vec<u64>> = HashMap::new();
    let mut all_nodes: HashSet<u64> = HashSet::new();

    for node in nodes {
        all_nodes.insert(node.id);
        for &succ in &node.successors {
            predecessors.entry(succ).or_default().push(node.id);
        }
    }

    // BFS backward from criterion
    let mut slice_nodes: HashSet<u64> = HashSet::new();
    let mut worklist: VecDeque<u64> = VecDeque::new();

    if all_nodes.contains(&criterion) {
        slice_nodes.insert(criterion);
        worklist.push_back(criterion);
    }

    while let Some(node_id) = worklist.pop_front() {
        if let Some(preds) = predecessors.get(&node_id) {
            for &pred in preds {
                if !slice_nodes.contains(&pred) {
                    slice_nodes.insert(pred);
                    worklist.push_back(pred);
                }
            }
        }
    }

    // Collect edges within slice
    let mut edges = Vec::new();
    for node in nodes {
        if slice_nodes.contains(&node.id) {
            for &succ in &node.successors {
                if slice_nodes.contains(&succ) {
                    edges.push((node.id, succ));
                }
            }
        }
    }

    SliceResult {
        nodes: slice_nodes,
        edges,
        direction: SliceDirection::Backward,
        criterion,
    }
}

/// Compute forward slice from a criterion node
///
/// The forward slice contains all nodes reachable from the criterion.
/// This answers: "What code is affected by this point?"
///
/// # Arguments
/// * `nodes` - CFG nodes
/// * `criterion` - Slicing criterion (source node)
///
/// # Returns
/// SliceResult with all nodes and edges in the forward slice
pub fn forward_slice(nodes: &[CfgGraphNode], criterion: u64) -> SliceResult {
    let node_map: HashMap<u64, &CfgGraphNode> = nodes.iter().map(|n| (n.id, n)).collect();

    // BFS forward from criterion
    let mut slice_nodes: HashSet<u64> = HashSet::new();
    let mut worklist: VecDeque<u64> = VecDeque::new();

    if node_map.contains_key(&criterion) {
        slice_nodes.insert(criterion);
        worklist.push_back(criterion);
    }

    while let Some(node_id) = worklist.pop_front() {
        if let Some(node) = node_map.get(&node_id) {
            for &succ in &node.successors {
                if !slice_nodes.contains(&succ) {
                    slice_nodes.insert(succ);
                    worklist.push_back(succ);
                }
            }
        }
    }

    // Collect edges within slice
    let mut edges = Vec::new();
    for node in nodes {
        if slice_nodes.contains(&node.id) {
            for &succ in &node.successors {
                if slice_nodes.contains(&succ) {
                    edges.push((node.id, succ));
                }
            }
        }
    }

    SliceResult {
        nodes: slice_nodes,
        edges,
        direction: SliceDirection::Forward,
        criterion,
    }
}

/// Compute full slice (backward + forward) from a criterion
pub fn full_slice(nodes: &[CfgGraphNode], criterion: u64) -> SliceResult {
    let backward = backward_slice(nodes, criterion);
    let forward = forward_slice(nodes, criterion);

    let mut nodes = backward.nodes;
    nodes.extend(forward.nodes);

    let mut edges = backward.edges;
    edges.extend(forward.edges);

    SliceResult {
        nodes,
        edges,
        direction: SliceDirection::Backward, // Default
        criterion,
    }
}

/// Get slice size (number of nodes)
pub fn slice_size(slice: &SliceResult) -> usize {
    slice.nodes.len()
}

/// Check if a node is in the slice
pub fn node_in_slice(node_id: u64, slice: &SliceResult) -> bool {
    slice.nodes.contains(&node_id)
}

/// Compute slice coverage (percentage of nodes in slice)
pub fn slice_coverage(slice: &SliceResult, total_nodes: usize) -> f32 {
    if total_nodes == 0 {
        return 0.0;
    }
    (slice.nodes.len() as f32) / (total_nodes as f32) * 100.0
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_backward_slice_linear() {
        // Linear: 0 -> 1 -> 2 -> 3
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![2],
            },
            CfgGraphNode {
                id: 2,
                x: 2.0,
                y: 0.0,
                z: 0.0,
                successors: vec![3],
            },
            CfgGraphNode {
                id: 3,
                x: 3.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        // Backward slice from node 3 should include all nodes
        let slice = backward_slice(&nodes, 3);
        assert_eq!(slice.nodes.len(), 4);
        assert!(slice.nodes.contains(&0));
        assert!(slice.nodes.contains(&3));
        assert_eq!(slice.direction, SliceDirection::Backward);
    }

    #[test]
    fn test_backward_slice_partial() {
        // Linear: 0 -> 1 -> 2 -> 3
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![2],
            },
            CfgGraphNode {
                id: 2,
                x: 2.0,
                y: 0.0,
                z: 0.0,
                successors: vec![3],
            },
            CfgGraphNode {
                id: 3,
                x: 3.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        // Backward slice from node 1 should include 0 and 1
        let slice = backward_slice(&nodes, 1);
        assert_eq!(slice.nodes.len(), 2);
        assert!(slice.nodes.contains(&0));
        assert!(slice.nodes.contains(&1));
    }

    #[test]
    fn test_forward_slice_linear() {
        // Linear: 0 -> 1 -> 2 -> 3
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![2],
            },
            CfgGraphNode {
                id: 2,
                x: 2.0,
                y: 0.0,
                z: 0.0,
                successors: vec![3],
            },
            CfgGraphNode {
                id: 3,
                x: 3.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        // Forward slice from node 0 should include all nodes
        let slice = forward_slice(&nodes, 0);
        assert_eq!(slice.nodes.len(), 4);
        assert!(slice.nodes.contains(&0));
        assert!(slice.nodes.contains(&3));
        assert_eq!(slice.direction, SliceDirection::Forward);
    }

    #[test]
    fn test_forward_slice_partial() {
        // Linear: 0 -> 1 -> 2 -> 3
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![2],
            },
            CfgGraphNode {
                id: 2,
                x: 2.0,
                y: 0.0,
                z: 0.0,
                successors: vec![3],
            },
            CfgGraphNode {
                id: 3,
                x: 3.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        // Forward slice from node 2 should include 2 and 3
        let slice = forward_slice(&nodes, 2);
        assert_eq!(slice.nodes.len(), 2);
        assert!(slice.nodes.contains(&2));
        assert!(slice.nodes.contains(&3));
    }

    #[test]
    fn test_slice_coverage() {
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        let slice = backward_slice(&nodes, 1);
        let coverage = slice_coverage(&slice, 2);
        assert!((coverage - 100.0).abs() < 0.001);
    }

    #[test]
    fn test_node_in_slice() {
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        let slice = backward_slice(&nodes, 1);
        assert!(node_in_slice(0, &slice));
        assert!(node_in_slice(1, &slice));
    }

    #[test]
    fn test_backward_slice_branching() {
        // Diamond: 0 -> 1 -> 3, 0 -> 2 -> 3
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1, 2],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![3],
            },
            CfgGraphNode {
                id: 2,
                x: 2.0,
                y: 0.0,
                z: 0.0,
                successors: vec![3],
            },
            CfgGraphNode {
                id: 3,
                x: 3.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        // Backward slice from node 3 should include all nodes
        let slice = backward_slice(&nodes, 3);
        assert_eq!(slice.nodes.len(), 4);
    }

    #[test]
    fn test_slice_edges() {
        let nodes = vec![
            CfgGraphNode {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
                successors: vec![1],
            },
            CfgGraphNode {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 0.0,
                successors: vec![2],
            },
            CfgGraphNode {
                id: 2,
                x: 2.0,
                y: 0.0,
                z: 0.0,
                successors: vec![],
            },
        ];

        let slice = backward_slice(&nodes, 2);
        assert_eq!(slice.edges.len(), 2);
        assert!(slice.edges.contains(&(0, 1)));
        assert!(slice.edges.contains(&(1, 2)));
    }
}