geographdb_core/algorithms/

loop_detection.rs

//! Loop Detection via Y-Coordinate Clustering
//!
//! This module implements loop detection for Control Flow Graphs using
//! 3D spatial coordinates, specifically the Y-coordinate (loop_nesting level).
//!
//! # Algorithm
//!
//! Blocks with Y > 0 are inside at least one loop. Blocks with the same
//! Y coordinate at non-zero levels belong to the same loop nesting depth.
//!
//! # Complexity
//!
//! - Time: O(n) single pass through blocks
//! - Space: O(l) where l is number of unique loop levels
//!
//! # Example
//!
//! ```rust
//! use geographdb_core::algorithms::loop_detection::{detect_loops, LoopBlock};
//!
//! let blocks = vec![
//!     LoopBlock { id: 0, x: 0.0, y: 0.0, z: 0.0 },  // Entry (not in loop)
//!     LoopBlock { id: 1, x: 1.0, y: 0.0, z: 1.0 },  // Branch (not in loop)
//!     LoopBlock { id: 2, x: 2.0, y: 1.0, z: 0.0 },  // Inside loop (depth 1)
//!     LoopBlock { id: 3, x: 3.0, y: 1.0, z: 0.0 },  // Inside loop (depth 1)
//!     LoopBlock { id: 4, x: 4.0, y: 2.0, z: 0.0 },  // Inside nested loop (depth 2)
//! ];
//!
//! let loops = detect_loops(&blocks);
//! assert_eq!(loops.len(), 2);  // Two loop levels detected
//! ```

use std::collections::HashMap;

/// A block in the CFG for loop detection
#[derive(Debug, Clone)]
pub struct LoopBlock {
    pub id: u64,
    pub x: f32, // dominator_depth
    pub y: f32, // loop_nesting
    pub z: f32, // branch_count
}

/// Information about a detected loop
#[derive(Debug, Clone)]
pub struct LoopInfo {
    /// Loop nesting level (1 = outermost loop)
    pub level: u32,
    /// Block IDs that belong to this loop
    pub block_ids: Vec<u64>,
    /// Entry block ID (block with minimum X at this level)
    pub entry_block: u64,
    /// Whether this loop contains nested loops
    pub has_nested_loops: bool,
}

/// Result of loop detection analysis
#[derive(Debug, Clone)]
pub struct LoopAnalysisResult {
    /// All detected loops, ordered by nesting level
    pub loops: Vec<LoopInfo>,
    /// Maximum loop nesting depth found
    pub max_depth: u32,
    /// Total number of blocks inside loops
    pub blocks_in_loops: usize,
    /// Total number of blocks outside loops
    pub blocks_outside_loops: usize,
}

/// Detect loops in a CFG using Y-coordinate clustering
///
/// Blocks with Y > 0 are inside loops. Blocks with the same Y value
/// at non-zero levels are grouped together as belonging to the same
/// loop nesting depth.
///
/// # Arguments
/// * `blocks` - Slice of CFG blocks with spatial coordinates
///
/// # Returns
/// Vector of LoopInfo for each detected loop level
pub fn detect_loops(blocks: &[LoopBlock]) -> Vec<LoopInfo> {
    // Group blocks by Y coordinate (loop nesting level)
    let mut level_blocks: HashMap<u32, Vec<&LoopBlock>> = HashMap::new();

    for block in blocks {
        let level = block.y as u32;
        if level > 0 {
            level_blocks.entry(level).or_default().push(block);
        }
    }

    // Convert to LoopInfo structures
    let mut loops: Vec<LoopInfo> = level_blocks
        .into_iter()
        .map(|(level, blocks_at_level)| {
            let block_ids: Vec<u64> = blocks_at_level.iter().map(|b| b.id).collect();

            // Entry block is the one with minimum X (dominator depth)
            let entry_block = blocks_at_level
                .iter()
                .min_by(|a, b| a.x.partial_cmp(&b.x).unwrap_or(std::cmp::Ordering::Equal))
                .map(|b| b.id)
                .unwrap_or(0);

            // Check for nested loops (higher levels exist)
            let has_nested_loops = false; // Will be set in analyze_loops

            LoopInfo {
                level,
                block_ids,
                entry_block,
                has_nested_loops,
            }
        })
        .collect();

    // Sort by level (outermost first)
    loops.sort_by_key(|l| l.level);

    // Mark loops that have nested loops
    let max_level = loops.iter().map(|l| l.level).max().unwrap_or(0);
    for loop_info in &mut loops {
        loop_info.has_nested_loops = loop_info.level < max_level;
    }

    loops
}

/// Analyze loop structure of a CFG
///
/// Provides comprehensive statistics about loop nesting and distribution.
pub fn analyze_loops(blocks: &[LoopBlock]) -> LoopAnalysisResult {
    let loops = detect_loops(blocks);

    let max_depth = loops.iter().map(|l| l.level).max().unwrap_or(0);
    let blocks_in_loops: usize = loops.iter().map(|l| l.block_ids.len()).sum();
    let blocks_outside_loops = blocks.len() - blocks_in_loops;

    LoopAnalysisResult {
        loops,
        max_depth,
        blocks_in_loops,
        blocks_outside_loops,
    }
}

/// Find the innermost loop containing a specific block
///
/// Returns the LoopInfo for the deepest loop that contains the given block.
pub fn find_innermost_loop_for_block(block_id: u64, loops: &[LoopInfo]) -> Option<&LoopInfo> {
    loops
        .iter()
        .filter(|l| l.block_ids.contains(&block_id))
        .max_by_key(|l| l.level)
}

/// Check if a block is inside any loop
#[inline]
pub fn is_in_loop(block: &LoopBlock) -> bool {
    block.y > 0.0
}

/// Get the loop nesting depth for a block
#[inline]
pub fn get_loop_depth(block: &LoopBlock) -> u32 {
    block.y as u32
}

/// Find all blocks at a specific loop nesting level
pub fn get_blocks_at_level(blocks: &[LoopBlock], level: u32) -> Vec<&LoopBlock> {
    blocks.iter().filter(|b| (b.y as u32) == level).collect()
}

/// Calculate loop complexity score
///
/// Higher scores indicate more complex loop structures.
/// Score = sum of (level * block_count) for all loops
pub fn calculate_loop_complexity(loops: &[LoopInfo]) -> u32 {
    loops
        .iter()
        .map(|l| l.level * l.block_ids.len() as u32)
        .sum()
}

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

    #[test]
    fn test_detect_loops_simple() {
        // Simple loop: entry -> header -> body -> exit
        let blocks = vec![
            LoopBlock {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
            }, // Entry (not in loop)
            LoopBlock {
                id: 1,
                x: 1.0,
                y: 1.0,
                z: 1.0,
            }, // Loop header
            LoopBlock {
                id: 2,
                x: 2.0,
                y: 1.0,
                z: 0.0,
            }, // Loop body
            LoopBlock {
                id: 3,
                x: 3.0,
                y: 0.0,
                z: 0.0,
            }, // Exit (not in loop)
        ];

        let loops = detect_loops(&blocks);

        assert_eq!(loops.len(), 1, "Should detect 1 loop");
        assert_eq!(loops[0].level, 1, "Loop should be at level 1");
        assert_eq!(loops[0].block_ids.len(), 2, "Loop should have 2 blocks");
        assert!(loops[0].block_ids.contains(&1), "Should contain header");
        assert!(loops[0].block_ids.contains(&2), "Should contain body");
    }

    #[test]
    fn test_detect_loops_nested() {
        // Nested loops: outer loop (level 1) containing inner loop (level 2)
        let blocks = vec![
            LoopBlock {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
            }, // Entry
            LoopBlock {
                id: 1,
                x: 1.0,
                y: 1.0,
                z: 1.0,
            }, // Outer loop header
            LoopBlock {
                id: 2,
                x: 2.0,
                y: 1.0,
                z: 0.0,
            }, // Outer loop body
            LoopBlock {
                id: 3,
                x: 3.0,
                y: 2.0,
                z: 1.0,
            }, // Inner loop header
            LoopBlock {
                id: 4,
                x: 4.0,
                y: 2.0,
                z: 0.0,
            }, // Inner loop body
            LoopBlock {
                id: 5,
                x: 5.0,
                y: 0.0,
                z: 0.0,
            }, // Exit
        ];

        let loops = detect_loops(&blocks);

        assert_eq!(loops.len(), 2, "Should detect 2 loops");
        assert_eq!(loops[0].level, 1, "First loop at level 1");
        assert_eq!(loops[1].level, 2, "Second loop at level 2");
        assert!(
            loops[0].has_nested_loops,
            "Outer loop should have nested loops"
        );
        assert!(
            !loops[1].has_nested_loops,
            "Inner loop should not have nested loops"
        );
    }

    #[test]
    fn test_detect_loops_multiple_at_same_level() {
        // Multiple separate loops at same nesting level
        let blocks = vec![
            LoopBlock {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
            }, // Entry
            LoopBlock {
                id: 1,
                x: 1.0,
                y: 1.0,
                z: 1.0,
            }, // Loop 1 header
            LoopBlock {
                id: 2,
                x: 2.0,
                y: 1.0,
                z: 0.0,
            }, // Loop 1 body
            LoopBlock {
                id: 3,
                x: 3.0,
                y: 0.0,
                z: 0.0,
            }, // Between loops
            LoopBlock {
                id: 4,
                x: 4.0,
                y: 1.0,
                z: 1.0,
            }, // Loop 2 header
            LoopBlock {
                id: 5,
                x: 5.0,
                y: 1.0,
                z: 0.0,
            }, // Loop 2 body
        ];

        let loops = detect_loops(&blocks);

        // Note: Current implementation groups by level, not by separate loops
        assert_eq!(loops.len(), 1, "Should detect 1 loop level");
        assert_eq!(loops[0].block_ids.len(), 4, "All level-1 blocks grouped");
    }

    #[test]
    fn test_detect_loops_no_loops() {
        // No loops - all blocks at level 0
        let blocks = vec![
            LoopBlock {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
            },
            LoopBlock {
                id: 1,
                x: 1.0,
                y: 0.0,
                z: 1.0,
            },
            LoopBlock {
                id: 2,
                x: 2.0,
                y: 0.0,
                z: 0.0,
            },
        ];

        let loops = detect_loops(&blocks);

        assert_eq!(loops.len(), 0, "Should detect no loops");
    }

    #[test]
    fn test_analyze_loops() {
        let blocks = vec![
            LoopBlock {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
            }, // Outside
            LoopBlock {
                id: 1,
                x: 1.0,
                y: 1.0,
                z: 1.0,
            }, // In loop
            LoopBlock {
                id: 2,
                x: 2.0,
                y: 1.0,
                z: 0.0,
            }, // In loop
            LoopBlock {
                id: 3,
                x: 3.0,
                y: 2.0,
                z: 0.0,
            }, // In nested loop
            LoopBlock {
                id: 4,
                x: 4.0,
                y: 0.0,
                z: 0.0,
            }, // Outside
        ];

        let result = analyze_loops(&blocks);

        assert_eq!(result.max_depth, 2, "Max depth should be 2");
        assert_eq!(result.blocks_in_loops, 3, "3 blocks in loops");
        assert_eq!(result.blocks_outside_loops, 2, "2 blocks outside loops");
        assert_eq!(result.loops.len(), 2, "2 loop levels");
    }

    #[test]
    fn test_is_in_loop() {
        let in_loop = LoopBlock {
            id: 0,
            x: 1.0,
            y: 1.0,
            z: 0.0,
        };
        let not_in_loop = LoopBlock {
            id: 1,
            x: 0.0,
            y: 0.0,
            z: 0.0,
        };

        assert!(is_in_loop(&in_loop), "Block with y>0 should be in loop");
        assert!(
            !is_in_loop(&not_in_loop),
            "Block with y=0 should not be in loop"
        );
    }

    #[test]
    fn test_get_loop_depth() {
        let block = LoopBlock {
            id: 0,
            x: 0.0,
            y: 3.0,
            z: 0.0,
        };
        assert_eq!(get_loop_depth(&block), 3, "Loop depth should be 3");
    }

    #[test]
    fn test_find_innermost_loop_for_block() {
        let loops = vec![
            LoopInfo {
                level: 1,
                block_ids: vec![1, 2, 3],
                entry_block: 1,
                has_nested_loops: true,
            },
            LoopInfo {
                level: 2,
                block_ids: vec![2, 3],
                entry_block: 2,
                has_nested_loops: false,
            },
        ];

        let innermost = find_innermost_loop_for_block(2, &loops);
        assert!(innermost.is_some(), "Should find loop for block 2");
        assert_eq!(innermost.unwrap().level, 2, "Should return innermost loop");
    }

    #[test]
    fn test_get_blocks_at_level() {
        let blocks = vec![
            LoopBlock {
                id: 0,
                x: 0.0,
                y: 0.0,
                z: 0.0,
            },
            LoopBlock {
                id: 1,
                x: 1.0,
                y: 1.0,
                z: 0.0,
            },
            LoopBlock {
                id: 2,
                x: 2.0,
                y: 1.0,
                z: 0.0,
            },
            LoopBlock {
                id: 3,
                x: 3.0,
                y: 2.0,
                z: 0.0,
            },
        ];

        let level_1 = get_blocks_at_level(&blocks, 1);
        assert_eq!(level_1.len(), 2, "Should have 2 blocks at level 1");

        let level_2 = get_blocks_at_level(&blocks, 2);
        assert_eq!(level_2.len(), 1, "Should have 1 block at level 2");
    }

    #[test]
    fn test_loop_complexity() {
        let loops = vec![
            LoopInfo {
                level: 1,
                block_ids: vec![1, 2, 3],
                entry_block: 1,
                has_nested_loops: true,
            },
            LoopInfo {
                level: 2,
                block_ids: vec![2, 3],
                entry_block: 2,
                has_nested_loops: false,
            },
        ];

        // Complexity = 1*3 + 2*2 = 3 + 4 = 7
        let complexity = calculate_loop_complexity(&loops);
        assert_eq!(complexity, 7, "Loop complexity should be 7");
    }

    #[test]
    fn test_loop_entry_block() {
        // Entry block should be the one with minimum X
        let blocks = vec![
            LoopBlock {
                id: 0,
                x: 5.0,
                y: 1.0,
                z: 0.0,
            },
            LoopBlock {
                id: 1,
                x: 2.0,
                y: 1.0,
                z: 0.0,
            }, // Entry (min X)
            LoopBlock {
                id: 2,
                x: 8.0,
                y: 1.0,
                z: 0.0,
            },
        ];

        let loops = detect_loops(&blocks);
        assert_eq!(loops[0].entry_block, 1, "Entry should be block with min X");
    }
}