geographdb_core/algorithms/

complexity.rs

//! Cyclomatic Complexity Calculation from Branch Counts
//!
//! This module calculates cyclomatic complexity using the Z-coordinate
//! (branch_count) from the 3D spatial representation of CFG blocks.
//!
//! # Formula
//!
//! Cyclomatic Complexity M = E - N + 2P where:
//! - E = number of edges
//! - N = number of nodes
//! - P = number of connected components (usually 1 for a function)
//!
//! Using spatial coordinates:
//! M = 1 + sum(branch_count) for all blocks
//!
//! # Complexity
//!
//! - Time: O(n) single pass through blocks
//! - Space: O(1) constant space
//!
//! # Example
//!
//! ```rust
//! use geographdb_core::algorithms::complexity::{calculate_cyclomatic_complexity, ComplexityBlock};
//!
//! let blocks = vec![
//!     ComplexityBlock { id: 0, z: 0.0 },  // Entry (no branches)
//!     ComplexityBlock { id: 1, z: 1.0 },  // If statement (1 branch)
//!     ComplexityBlock { id: 2, z: 0.0 },  // Sequential
//!     ComplexityBlock { id: 3, z: 1.0 },  // Another if (1 branch)
//! ];
//!
//! let result = calculate_cyclomatic_complexity(&blocks);
//! assert_eq!(result.cyclomatic_complexity, 3);  // 1 + 1 + 1 = 3
//! ```

/// A block for complexity calculation
#[derive(Debug, Clone)]
pub struct ComplexityBlock {
    pub id: u64,
    pub z: f32, // branch_count
}

/// Result of complexity analysis
#[derive(Debug, Clone)]
pub struct ComplexityResult {
    /// Cyclomatic complexity (McCabe number)
    pub cyclomatic_complexity: u32,
    /// Number of blocks analyzed
    pub block_count: usize,
    /// Total branch count
    pub total_branches: u32,
    /// Average branches per block
    pub avg_branches_per_block: f32,
    /// Complexity rating (Low/Medium/High/VeryHigh)
    pub rating: ComplexityRating,
}

/// Complexity rating based on McCabe number
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ComplexityRating {
    /// 1-10: Simple, well-structured code
    Low,
    /// 11-20: Moderate complexity
    Medium,
    /// 21-50: Complex, difficult to test
    High,
    /// 51+: Very complex, should be refactored
    VeryHigh,
}

impl ComplexityRating {
    pub fn as_str(&self) -> &'static str {
        match self {
            ComplexityRating::Low => "Low (1-10)",
            ComplexityRating::Medium => "Medium (11-20)",
            ComplexityRating::High => "High (21-50)",
            ComplexityRating::VeryHigh => "Very High (51+)",
        }
    }

    pub fn from_complexity(complexity: u32) -> Self {
        match complexity {
            0..=10 => ComplexityRating::Low,
            11..=20 => ComplexityRating::Medium,
            21..=50 => ComplexityRating::High,
            _ => ComplexityRating::VeryHigh,
        }
    }
}

/// Calculate cyclomatic complexity from CFG blocks
///
/// Uses the formula: M = 1 + sum(branch_count)
/// This is equivalent to the traditional formula M = E - N + 2P
/// when branch_count represents the number of decision points.
pub fn calculate_cyclomatic_complexity(blocks: &[ComplexityBlock]) -> ComplexityResult {
    let block_count = blocks.len();
    let total_branches: u32 = blocks.iter().map(|b| b.z as u32).sum();

    // Cyclomatic complexity = 1 + number of decision points
    let cyclomatic_complexity = 1 + total_branches;

    let avg_branches = if block_count > 0 {
        total_branches as f32 / block_count as f32
    } else {
        0.0
    };

    let rating = ComplexityRating::from_complexity(cyclomatic_complexity);

    ComplexityResult {
        cyclomatic_complexity,
        block_count,
        total_branches,
        avg_branches_per_block: avg_branches,
        rating,
    }
}

/// Calculate complexity for each block individually
pub fn calculate_per_block_complexity(blocks: &[ComplexityBlock]) -> Vec<BlockComplexity> {
    blocks
        .iter()
        .map(|b| {
            BlockComplexity {
                block_id: b.id,
                branch_count: b.z as u32,
                // Individual block complexity is 1 + branches at that block
                local_complexity: 1 + b.z as u32,
            }
        })
        .collect()
}

/// Complexity metrics for a single block
#[derive(Debug, Clone)]
pub struct BlockComplexity {
    pub block_id: u64,
    pub branch_count: u32,
    pub local_complexity: u32,
}

/// Identify the most complex blocks (top N by branch count)
pub fn find_most_complex_blocks(blocks: &[ComplexityBlock], n: usize) -> Vec<BlockComplexity> {
    let mut complexities: Vec<BlockComplexity> = calculate_per_block_complexity(blocks);

    // Sort by local complexity descending
    complexities.sort_by_key(|block| std::cmp::Reverse(block.local_complexity));

    // Take top N
    complexities.into_iter().take(n).collect()
}

/// Check if complexity is within acceptable limits
pub fn is_complexity_acceptable(complexity: u32, threshold: u32) -> bool {
    complexity <= threshold
}

/// Get complexity trend description
pub fn get_complexity_trend(complexity: u32) -> &'static str {
    match complexity {
        0..=5 => "Very simple - easy to understand and test",
        6..=10 => "Simple - well-structured code",
        11..=15 => "Moderate - consider adding comments",
        16..=20 => "Complex - consider refactoring",
        21..=30 => "Very complex - should be refactored",
        _ => "Extremely complex - immediate refactoring recommended",
    }
}

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

    #[test]
    fn test_cyclomatic_complexity_simple() {
        // Simple function with no branches
        let blocks = vec![
            ComplexityBlock { id: 0, z: 0.0 },
            ComplexityBlock { id: 1, z: 0.0 },
            ComplexityBlock { id: 2, z: 0.0 },
        ];

        let result = calculate_cyclomatic_complexity(&blocks);

        assert_eq!(
            result.cyclomatic_complexity, 1,
            "Simple function should have complexity 1"
        );
        assert_eq!(result.block_count, 3);
        assert_eq!(result.total_branches, 0);
        assert_eq!(result.rating, ComplexityRating::Low);
    }

    #[test]
    fn test_cyclomatic_complexity_single_if() {
        // Function with single if statement
        let blocks = vec![
            ComplexityBlock { id: 0, z: 0.0 }, // Entry
            ComplexityBlock { id: 1, z: 1.0 }, // If (1 branch)
            ComplexityBlock { id: 2, z: 0.0 }, // Then
            ComplexityBlock { id: 3, z: 0.0 }, // Exit
        ];

        let result = calculate_cyclomatic_complexity(&blocks);

        assert_eq!(
            result.cyclomatic_complexity, 2,
            "Single if should have complexity 2"
        );
        assert_eq!(result.total_branches, 1);
    }

    #[test]
    fn test_cyclomatic_complexity_nested_if() {
        // Function with nested if statements
        let blocks = vec![
            ComplexityBlock { id: 0, z: 0.0 }, // Entry
            ComplexityBlock { id: 1, z: 1.0 }, // Outer if
            ComplexityBlock { id: 2, z: 1.0 }, // Inner if
            ComplexityBlock { id: 3, z: 0.0 }, // Then
            ComplexityBlock { id: 4, z: 0.0 }, // Exit
        ];

        let result = calculate_cyclomatic_complexity(&blocks);

        assert_eq!(
            result.cyclomatic_complexity, 3,
            "Nested if should have complexity 3"
        );
        assert_eq!(result.total_branches, 2);
    }

    #[test]
    fn test_cyclomatic_complexity_multiple_branches() {
        // Function with multiple decision points
        let blocks = vec![
            ComplexityBlock { id: 0, z: 0.0 }, // Entry
            ComplexityBlock { id: 1, z: 1.0 }, // If 1
            ComplexityBlock { id: 2, z: 1.0 }, // If 2
            ComplexityBlock { id: 3, z: 1.0 }, // If 3
            ComplexityBlock { id: 4, z: 0.0 }, // Exit
        ];

        let result = calculate_cyclomatic_complexity(&blocks);

        assert_eq!(
            result.cyclomatic_complexity, 4,
            "Three ifs should have complexity 4"
        );
    }

    #[test]
    fn test_complexity_rating_low() {
        let blocks: Vec<ComplexityBlock> =
            (0..10).map(|i| ComplexityBlock { id: i, z: 0.0 }).collect();
        let result = calculate_cyclomatic_complexity(&blocks);
        assert_eq!(result.rating, ComplexityRating::Low);
    }

    #[test]
    fn test_complexity_rating_medium() {
        // Create blocks with 15 branches (complexity = 16)
        let blocks: Vec<ComplexityBlock> =
            (0..15).map(|i| ComplexityBlock { id: i, z: 1.0 }).collect();
        let result = calculate_cyclomatic_complexity(&blocks);
        assert_eq!(result.rating, ComplexityRating::Medium);
    }

    #[test]
    fn test_complexity_rating_high() {
        // Create blocks with 30 branches (complexity = 31)
        let blocks: Vec<ComplexityBlock> =
            (0..30).map(|i| ComplexityBlock { id: i, z: 1.0 }).collect();
        let result = calculate_cyclomatic_complexity(&blocks);
        assert_eq!(result.rating, ComplexityRating::High);
    }

    #[test]
    fn test_complexity_rating_very_high() {
        // Create blocks with 60 branches (complexity = 61)
        let blocks: Vec<ComplexityBlock> =
            (0..60).map(|i| ComplexityBlock { id: i, z: 1.0 }).collect();
        let result = calculate_cyclomatic_complexity(&blocks);
        assert_eq!(result.rating, ComplexityRating::VeryHigh);
    }

    #[test]
    fn test_per_block_complexity() {
        let blocks = vec![
            ComplexityBlock { id: 0, z: 0.0 },
            ComplexityBlock { id: 1, z: 2.0 }, // Switch with 2 cases
            ComplexityBlock { id: 2, z: 0.0 },
        ];

        let complexities = calculate_per_block_complexity(&blocks);

        assert_eq!(complexities.len(), 3);
        assert_eq!(complexities[1].local_complexity, 3); // 1 + 2 branches
    }

    #[test]
    fn test_find_most_complex_blocks() {
        let blocks = vec![
            ComplexityBlock { id: 0, z: 0.0 },
            ComplexityBlock { id: 1, z: 3.0 }, // Most complex
            ComplexityBlock { id: 2, z: 1.0 },
            ComplexityBlock { id: 3, z: 2.0 }, // Second most
            ComplexityBlock { id: 4, z: 0.0 },
        ];

        let top = find_most_complex_blocks(&blocks, 2);

        assert_eq!(top.len(), 2);
        assert_eq!(top[0].block_id, 1); // Most complex first
        assert_eq!(top[1].block_id, 3); // Second most complex
    }

    #[test]
    fn test_is_complexity_acceptable() {
        assert!(
            is_complexity_acceptable(5, 10),
            "5 should be acceptable with threshold 10"
        );
        assert!(
            !is_complexity_acceptable(15, 10),
            "15 should not be acceptable with threshold 10"
        );
        assert!(
            is_complexity_acceptable(10, 10),
            "10 should be acceptable with threshold 10"
        );
    }

    #[test]
    fn test_get_complexity_trend() {
        assert!(get_complexity_trend(3).contains("simple"));
        assert!(get_complexity_trend(25).contains("complex"));
        assert!(get_complexity_trend(60).contains("refactoring"));
    }

    #[test]
    fn test_avg_branches_per_block() {
        let blocks = vec![
            ComplexityBlock { id: 0, z: 0.0 },
            ComplexityBlock { id: 1, z: 2.0 },
            ComplexityBlock { id: 2, z: 4.0 },
        ];

        let result = calculate_cyclomatic_complexity(&blocks);

        // Total branches = 6, blocks = 3, avg = 2.0
        assert!((result.avg_branches_per_block - 2.0).abs() < 0.001);
    }
}