srcgraph_metrics/

cyclomatic.rs

//! Per-method cyclomatic complexity + bimodality detection.
//!
//! Reads the `cyclomaticComplexity` JSON blob already attached to each class
//! node by the visiting-tool extractor (shape: `{"methods": [{"name": str,
//! "complexity": int}, …]}`) and rolls it up into per-class distribution
//! statistics plus a heuristic bimodality test that flags classes whose
//! complexity distribution suggests they should be split.
//!
//! The bimodality heuristic mirrors the Python reference at
//! `visiting/graph-theory-code-analysis-tool/analysis/cyclomatic.py`: sort the
//! values, find the largest consecutive gap, and call the distribution bimodal
//! when that gap is ≥ `max(3, 3 × median_gap)` and there are at least 2 values
//! on each side. This is not the full Hartigan dip test (which needs a
//! resampling-based critical value); the field is named `dip_score` for
//! continuity with the Python panel but is a normalized gap ratio in [0, 1].
//!
//! See `DESIGN.md` (Phase 2) at the workspace root.

use petgraph::Graph;
use serde::{Deserialize, Serialize};

use srcgraph_core::{ClassNode, EdgeKind};

/// One row of the `cyclomaticComplexity.methods` array.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct MethodCc {
    #[serde(default)]
    pub name: String,
    /// Defaults to 1 (a method with no branches has CC = 1).
    #[serde(default = "one")]
    pub complexity: u32,
}

fn one() -> u32 {
    1
}

/// Distribution stats over a class's per-method CC values.
#[derive(Debug, Clone, Serialize, Deserialize, Default)]
pub struct CcStats {
    pub mean: f64,
    pub median: u32,
    pub min: u32,
    pub max: u32,
    pub std: f64,
    /// Number of methods (`values.len()`).
    pub total: usize,
}

/// Bimodality verdict over a class's per-method CC values.
#[derive(Debug, Clone, Serialize, Deserialize, Default)]
pub struct Bimodality {
    pub is_bimodal: bool,
    /// 1 or 2.
    pub num_modes: u8,
    /// Normalized gap ratio in [0, 1]; higher = more bimodal. Named for
    /// continuity with the Python `dip_score` field — not the true Hartigan
    /// dip statistic.
    pub dip_score: f64,
    /// Complexity value at which the split occurs, when `is_bimodal` is true.
    pub split_point: Option<u32>,
}

/// Full cyclomatic readout for one class.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CyclomaticReport {
    pub class_id: String,
    /// `None` when the node has no `cyclomaticComplexity` blob (syntax-only
    /// extraction) or the blob fails to parse.
    pub methods: Option<Vec<MethodCc>>,
    pub stats: Option<CcStats>,
    pub bimodality: Option<Bimodality>,
}

/// Parse a `cyclomaticComplexity` blob, returning the `methods` array.
pub fn parse_methods(blob: &serde_json::Value) -> Option<Vec<MethodCc>> {
    let arr = blob.get("methods")?.as_array()?;
    let mut out = Vec::with_capacity(arr.len());
    for v in arr {
        let m: MethodCc = serde_json::from_value(v.clone()).ok()?;
        out.push(m);
    }
    Some(out)
}

/// Mean / median / min / max / std / total over a complexity series.
///
/// Returns the default (all zeros, total = 0) for an empty input.
pub fn compute_stats(values: &[u32]) -> CcStats {
    let n = values.len();
    if n == 0 {
        return CcStats::default();
    }
    let sum: u64 = values.iter().map(|v| *v as u64).sum();
    let mean = sum as f64 / n as f64;
    let mut sorted: Vec<u32> = values.to_vec();
    sorted.sort_unstable();
    let median = sorted[n / 2];
    let max = *sorted.last().unwrap();
    let min = sorted[0];
    let variance: f64 = values
        .iter()
        .map(|v| {
            let d = *v as f64 - mean;
            d * d
        })
        .sum::<f64>()
        / n as f64;
    CcStats {
        mean,
        median,
        min,
        max,
        std: variance.sqrt(),
        total: n,
    }
}

/// Heuristic bimodality test. Mirrors the Python reference: sort, find the
/// largest consecutive gap, declare the distribution bimodal when that gap is
/// at least `max(3, 3 × median_gap)` with ≥ 2 values on either side.
pub fn detect_bimodality(values: &[u32]) -> Bimodality {
    if values.len() < 4 {
        return Bimodality {
            is_bimodal: false,
            num_modes: 1,
            dip_score: 0.0,
            split_point: None,
        };
    }
    let mut sorted: Vec<u32> = values.to_vec();
    sorted.sort_unstable();
    let gaps: Vec<u32> = sorted.windows(2).map(|w| w[1] - w[0]).collect();

    let max_gap = *gaps.iter().max().unwrap_or(&0);
    if max_gap == 0 {
        return Bimodality {
            is_bimodal: false,
            num_modes: 1,
            dip_score: 0.0,
            split_point: None,
        };
    }
    let max_gap_idx = gaps.iter().position(|g| *g == max_gap).unwrap();

    let mut gaps_sorted = gaps.clone();
    gaps_sorted.sort_unstable();
    let median_gap = gaps_sorted[gaps_sorted.len() / 2];

    let mean_gap = gaps.iter().map(|g| *g as f64).sum::<f64>() / gaps.len() as f64;
    let dip_score = if mean_gap > 0.0 {
        ((max_gap as f64 / (mean_gap + 0.01)) / 5.0).min(1.0)
    } else {
        0.0
    };

    let left_count = max_gap_idx + 1;
    let right_count = sorted.len() - left_count;
    let threshold = std::cmp::max(3, median_gap.saturating_mul(3));
    let is_bimodal = max_gap >= threshold && left_count >= 2 && right_count >= 2;

    Bimodality {
        is_bimodal,
        num_modes: if is_bimodal { 2 } else { 1 },
        // Round to 4 decimals to match the Python output exactly.
        dip_score: (dip_score * 10_000.0).round() / 10_000.0,
        split_point: if is_bimodal {
            Some(sorted[max_gap_idx])
        } else {
            None
        },
    }
}

/// Compute the full per-class cyclomatic readout for every node in `graph`.
///
/// Pulls the `cyclomaticComplexity` JSON blob via `Self::cyclomatic_complexity`
/// (added to the `ClassNode` trait). Nodes without a blob yield a report with
/// all `Option` fields set to `None`.
pub fn compute_cyclomatic<N, E>(graph: &Graph<N, E>) -> Vec<CyclomaticReport>
where
    N: ClassNode,
    E: EdgeKind,
{
    graph
        .node_indices()
        .map(|nx| {
            let node = &graph[nx];
            let class_id = node.id().to_owned();
            let Some(blob) = node.cyclomatic_complexity() else {
                return CyclomaticReport {
                    class_id,
                    methods: None,
                    stats: None,
                    bimodality: None,
                };
            };
            let Some(methods) = parse_methods(blob) else {
                return CyclomaticReport {
                    class_id,
                    methods: None,
                    stats: None,
                    bimodality: None,
                };
            };
            let values: Vec<u32> = methods.iter().map(|m| m.complexity).collect();
            let stats = compute_stats(&values);
            let bimodality = detect_bimodality(&values);
            CyclomaticReport {
                class_id,
                methods: Some(methods),
                stats: Some(stats),
                bimodality: Some(bimodality),
            }
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use srcgraph_core::{EdgeType, OwnedClassNode, OwnedGraph};
    use petgraph::Graph;
    use serde_json::json;

    fn class(id: &str, cc: Option<serde_json::Value>) -> OwnedClassNode {
        OwnedClassNode {
            id: id.to_owned(),
            name: id.to_owned(),
            namespace: "test".to_owned(),
            line_count: 10,
            method_count: 1,
            halstead_eta1: 0,
            halstead_eta2: 0,
            halstead_n1: 0,
            halstead_n2: 0,
            method_connectivity: None,
            method_fingerprints: None,
            method_tokens: None,
            call_sequences: None,
            cyclomatic_complexity: cc,
            path_conditions: None,
            invariants: None,
            error_messages: None,
            magic_numbers: None,
            dead_code: None,
            tenant_branches: None,
            state_transitions: None,
        }
    }

    #[test]
    fn parse_methods_extracts_array() {
        let blob = json!({"methods": [
            {"name": "foo", "complexity": 1},
            {"name": "bar", "complexity": 7}
        ]});
        let m = parse_methods(&blob).unwrap();
        assert_eq!(m.len(), 2);
        assert_eq!(m[0].name, "foo");
        assert_eq!(m[1].complexity, 7);
    }

    #[test]
    fn parse_methods_defaults_missing_complexity_to_one() {
        let blob = json!({"methods": [{"name": "ctor"}]});
        let m = parse_methods(&blob).unwrap();
        assert_eq!(m[0].complexity, 1);
    }

    #[test]
    fn compute_stats_empty_is_zeros() {
        let s = compute_stats(&[]);
        assert_eq!(s.total, 0);
        assert_eq!(s.mean, 0.0);
    }

    #[test]
    fn compute_stats_basic_distribution() {
        // [1, 2, 3, 4, 5] — mean 3, median 3, min 1, max 5, var = 2, std ≈ 1.4142
        let s = compute_stats(&[1, 2, 3, 4, 5]);
        assert_eq!(s.total, 5);
        assert!((s.mean - 3.0).abs() < 1e-12);
        assert_eq!(s.median, 3);
        assert_eq!(s.min, 1);
        assert_eq!(s.max, 5);
        assert!((s.std - 2_f64.sqrt()).abs() < 1e-12);
    }

    #[test]
    fn bimodality_short_input_is_unimodal() {
        // Fewer than 4 values → unimodal.
        let b = detect_bimodality(&[1, 20, 3]);
        assert!(!b.is_bimodal);
        assert_eq!(b.num_modes, 1);
        assert_eq!(b.split_point, None);
    }

    #[test]
    fn bimodality_flat_distribution_is_unimodal() {
        // All identical — every gap is 0.
        let b = detect_bimodality(&[5, 5, 5, 5, 5]);
        assert!(!b.is_bimodal);
        assert_eq!(b.dip_score, 0.0);
    }

    #[test]
    fn bimodality_two_clusters_detected() {
        // Two clear clusters: {1,2,2,3} and {20,21,22,23}. Median gap is ~1,
        // max gap is 17 — well above the `max(3, 3×median_gap)` threshold.
        let b = detect_bimodality(&[1, 2, 2, 3, 20, 21, 22, 23]);
        assert!(b.is_bimodal);
        assert_eq!(b.num_modes, 2);
        assert_eq!(b.split_point, Some(3));
        assert!(b.dip_score > 0.0);
    }

    #[test]
    fn bimodality_unbalanced_split_rejected() {
        // The split lies one-in-from-the-edge (only one value on the right) —
        // the Python heuristic requires ≥ 2 on each side, so we reject.
        let b = detect_bimodality(&[1, 2, 3, 4, 50]);
        assert!(!b.is_bimodal);
    }

    #[test]
    fn compute_cyclomatic_walks_graph_and_handles_missing_blob() {
        let mut g: OwnedGraph = Graph::new();
        let a = g.add_node(class(
            "A",
            Some(json!({"methods": [
                {"name": "m1", "complexity": 1},
                {"name": "m2", "complexity": 2},
                {"name": "m3", "complexity": 2},
                {"name": "m4", "complexity": 30}
            ]})),
        ));
        let b = g.add_node(class("B", None));
        g.add_edge(a, b, EdgeType::MethodCall);

        let reports = compute_cyclomatic(&g);
        assert_eq!(reports.len(), 2);

        let r_a = reports.iter().find(|r| r.class_id == "A").unwrap();
        let stats_a = r_a.stats.as_ref().unwrap();
        assert_eq!(stats_a.total, 4);
        assert_eq!(stats_a.max, 30);
        // A's distribution is heavily bimodal: {1,2,2} and {30}. Only one on
        // the right, so the heuristic does *not* call it bimodal — left/right
        // count guard is doing its job.
        assert!(!r_a.bimodality.as_ref().unwrap().is_bimodal);

        let r_b = reports.iter().find(|r| r.class_id == "B").unwrap();
        assert!(r_b.methods.is_none());
        assert!(r_b.stats.is_none());
        assert!(r_b.bimodality.is_none());
    }
}