codehelion_core/engine/

group.rs

//! Clone-pair grouping and noise scoring.
//!
//! Pairs whose matched content has the same collision-resistant identity form
//! one clone group; instances are deduplicated and the canonical instance is
//! chosen by a deterministic tie-break. Exact-content equivalence classes
//! trivially satisfy the constraint that every member match the canonical
//! instance, so this interface can later be re-implemented with medoid-based
//! grouping for near-match clones without changing callers.
//!
//! Each group carries two noise signals instead of being silently dropped:
//! low content entropy (degenerate repetition such as long literal tables) and
//! high instance degree (idiomatic boilerplate that recurs all over a
//! codebase). Thresholds only set a suppression marker; reporting stays
//! honest about what was found.

use std::collections::{BTreeMap, BTreeSet};

use super::fingerprint::{ContentDigest, norm_token_hash};
use super::normalize::normalize;
use super::{
    CloneClass, CloneGroup, ClonePair, EngineConfig, InputFile, Instance, LiteralNorm,
    SuppressReason,
};
use crate::frontend::Token;

/// Shannon entropy, in bits, of a token slice's normalized-token
/// distribution.
///
/// Low entropy marks degenerate repetition — a long literal table, a run of
/// near-identical accessors — which is a noise signal rather than a finding.
/// Any mode that reports clone groups scores its content the same way, so the
/// signal means the same thing across modes.
#[must_use]
#[allow(clippy::cast_precision_loss)] // token counts are far below 2^52
pub fn content_entropy_bits(tokens: &[Token], literals: LiteralNorm) -> f64 {
    let normalized = normalize(tokens, literals);
    let mut counts: BTreeMap<u64, usize> = BTreeMap::new();
    for token in &normalized {
        *counts.entry(norm_token_hash(token)).or_insert(0) += 1;
    }
    let total = normalized.len();
    if total == 0 {
        return 0.0;
    }
    counts
        .values()
        .map(|&c| {
            let p = c as f64 / total as f64;
            -p * p.log2()
        })
        .sum()
}

/// Entropy as a share of the largest value a token sequence of this length
/// could have.
///
/// Absolute entropy grows simply because there are more positions to fill.
/// Dividing by `log2(token_count)` makes the suppression floor describe
/// diversity rather than clone length. Empty and one-token sequences carry no
/// diversity evidence and return `0.0`.
#[must_use]
#[allow(clippy::cast_precision_loss)] // token counts are far below 2^52
pub fn entropy_ratio(entropy_bits: f64, token_count: usize) -> f64 {
    if token_count <= 1 {
        0.0
    } else {
        entropy_bits / (token_count as f64).log2()
    }
}

/// Entropy of one instance's matched content, under the run's literal
/// strategy.
fn entropy_bits(files: &[InputFile<'_>], instance: &Instance, config: &EngineConfig) -> f64 {
    let slice = &files[instance.file].tokens[instance.token_start..instance.token_end];
    content_entropy_bits(slice, config.literals)
}

/// Group clone pairs into clone groups by matched content.
///
/// Instances are deduplicated across pairs, members are sorted, and the
/// canonical instance is the first member under `(file, token range)` order.
/// Groups come back sorted by their canonical instance, so output order does
/// not depend on input order.
#[must_use]
pub fn group_pairs(
    pairs: &[ClonePair],
    files: &[InputFile<'_>],
    config: &EngineConfig,
) -> Vec<CloneGroup> {
    let mut by_key: BTreeMap<(u64, ContentDigest), Vec<&ClonePair>> = BTreeMap::new();
    for pair in pairs {
        by_key
            .entry((pair.content_key, pair.content_digest))
            .or_default()
            .push(pair);
    }

    let mut groups: Vec<CloneGroup> = by_key
        .into_iter()
        .map(|((content_key, _), pairs)| {
            let mut members: Vec<Instance> = Vec::new();
            let mut seen: BTreeSet<(usize, usize, usize)> = BTreeSet::new();
            for pair in &pairs {
                for candidate in [&pair.a, &pair.b] {
                    if seen.insert((candidate.file, candidate.token_start, candidate.token_end)) {
                        members.push(candidate.clone());
                    }
                }
            }
            members.sort_by_key(|m| (m.file, m.token_start, m.token_end));

            let clone_type = if pairs.iter().any(|p| p.clone_type == CloneClass::Type2) {
                CloneClass::Type2
            } else {
                CloneClass::Type1
            };
            let score = pairs.iter().map(|p| p.score).fold(f64::INFINITY, f64::min);
            let entropy = entropy_bits(files, &members[0], config);
            let token_count = members[0].token_end - members[0].token_start;
            let entropy_ratio = entropy_ratio(entropy, token_count);
            let degree = members.len();
            let suppressed = if degree > config.degree_cap {
                Some(SuppressReason::HighFrequency)
            } else if entropy_ratio < config.entropy_ratio_floor {
                Some(SuppressReason::LowEntropy)
            } else {
                None
            };
            CloneGroup {
                content_key,
                clone_type,
                score,
                members,
                entropy_bits: entropy,
                suppressed,
            }
        })
        .collect();

    groups.sort_by_key(|g| {
        let c = &g.members[0];
        (c.file, c.token_start, c.token_end, g.content_key)
    });
    groups
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
    use super::*;
    use crate::engine::fingerprint::raw_sequence_digest;
    use crate::frontend::{Lexeme, SourceSpan, TokenKind};

    fn tokens(texts: &[&str]) -> Vec<Token> {
        texts
            .iter()
            .enumerate()
            .map(|(index, text)| Token {
                kind: TokenKind::Identifier,
                text: Lexeme::from(*text),
                span: SourceSpan {
                    start_byte: index,
                    end_byte: index + text.len(),
                    start_line: 1,
                    start_column: 1,
                },
            })
            .collect()
    }

    fn instance(file: usize) -> Instance {
        Instance {
            file,
            token_start: 0,
            token_end: 2,
            start_line: 1,
            end_line: 1,
            unit: None,
        }
    }

    #[test]
    fn a_shared_64_bit_key_cannot_merge_distinct_verified_content() {
        // Model an attacker-controlled FNV collision without relying on a
        // particular construction: candidate keys are intentionally small,
        // but the grouping relation must use the independent BLAKE3 digest.
        let first = tokens(&["first", "content"]);
        let second = tokens(&["first", "content"]);
        let third = tokens(&["other", "tokens"]);
        let fourth = tokens(&["other", "tokens"]);
        let files = [
            InputFile {
                tokens: &first,
                units: &[],
            },
            InputFile {
                tokens: &second,
                units: &[],
            },
            InputFile {
                tokens: &third,
                units: &[],
            },
            InputFile {
                tokens: &fourth,
                units: &[],
            },
        ];
        let shared_candidate_key = 0x4b1d_fa11_u64;
        let pairs = [
            ClonePair {
                content_key: shared_candidate_key,
                content_digest: raw_sequence_digest(&first),
                clone_type: CloneClass::Type1,
                score: 1.0,
                a: instance(0),
                b: instance(1),
            },
            ClonePair {
                content_key: shared_candidate_key,
                content_digest: raw_sequence_digest(&third),
                clone_type: CloneClass::Type1,
                score: 1.0,
                a: instance(2),
                b: instance(3),
            },
        ];

        let groups = group_pairs(&pairs, &files, &EngineConfig::default());

        assert_eq!(groups.len(), 2);
        assert!(groups.iter().all(|group| group.members.len() == 2));
        assert!(
            groups
                .iter()
                .all(|group| group.content_key == shared_candidate_key)
        );
    }

    #[test]
    fn entropy_separates_repetition_from_variety() {
        let empty = content_entropy_bits(&[], LiteralNorm::Full);
        assert!(empty.abs() < 1e-12);

        // Identifiers normalize scope-locally, so repetition shows up as a
        // single symbol: no information, zero bits.
        let repeated = content_entropy_bits(&tokens(&["a", "a", "a", "a"]), LiteralNorm::Full);
        assert!(repeated.abs() < 1e-12);

        // Four equally frequent distinct symbols carry exactly two bits.
        let varied = content_entropy_bits(&tokens(&["a", "b", "c", "d"]), LiteralNorm::Full);
        assert!(varied > repeated);
        assert!((varied - 2.0).abs() < 1e-9, "expected 2 bits, got {varied}");

        assert!(entropy_ratio(repeated, 4).abs() < 1e-12);
        assert!((entropy_ratio(varied, 4) - 1.0).abs() < 1e-12);
    }

    #[test]
    fn entropy_ratio_is_not_an_absolute_clone_length_floor() {
        // Both slices are maximally diverse at their own length. Their bits
        // differ because one is longer, but their normalized evidence is the
        // same and neither can be hidden by a ratio floor below one.
        let short = tokens(&["a", "b", "c", "d"]);
        let long = tokens(&["a", "b", "c", "d", "e", "f", "g", "h"]);
        let short_bits = content_entropy_bits(&short, LiteralNorm::Full);
        let long_bits = content_entropy_bits(&long, LiteralNorm::Full);
        assert!(long_bits > short_bits);
        assert!((entropy_ratio(short_bits, short.len()) - 1.0).abs() < 1e-12);
        assert!((entropy_ratio(long_bits, long.len()) - 1.0).abs() < 1e-12);
    }
}