dhive-core 0.1.0

//! 相似度与哈希 — LCS 最长公共子串 + canonicalHash
//!
//! LCS: 用于冲突检测和 merge 候选发现
//! canonicalHash: SHA-256 用于精确去重

use sha2::{Sha256, Digest};

/// 计算两个字符串的最长公共子串 (Longest Common Substring) 长度
///
/// 动态规划算法，时间复杂度 O(m×n)，空间复杂度 O(m×n)。
/// 对于记忆文本 (<5000 字符)，实际执行时间 <10ms。
pub fn longest_common_substring(a: &str, b: &str) -> usize {
    let a_chars: Vec<char> = a.chars().collect();
    let b_chars: Vec<char> = b.chars().collect();
    let m = a_chars.len();
    let n = b_chars.len();

    if m == 0 || n == 0 {
        return 0;
    }

    // 使用两行优化空间: O(min(m, n)) 而非 O(m×n)
    let mut prev = vec![0u32; n + 1];
    let mut curr = vec![0u32; n + 1];
    let mut max_len: u32 = 0;

    for i in 1..=m {
        for j in 1..=n {
            if a_chars[i - 1] == b_chars[j - 1] {
                curr[j] = prev[j - 1] + 1;
                max_len = max_len.max(curr[j]);
            } else {
                curr[j] = 0;
            }
        }
        std::mem::swap(&mut prev, &mut curr);
    }

    max_len as usize
}

/// 计算 LCS 相似度 (0.0–1.0)
///
/// `similarity = LCS(a, b) / max(len(a), len(b))`
pub fn lcs_similarity(a: &str, b: &str) -> f64 {
    let max_len = a.chars().count().max(b.chars().count());
    if max_len == 0 {
        return 0.0;
    }
    longest_common_substring(a, b) as f64 / max_len as f64
}

/// 冲突分类
#[derive(Debug, PartialEq, Eq)]
pub enum ConflictCategory {
    /// 几乎相同 (similarity ≥ 0.90)
    Exact,
    /// 高度相似 (0.70–0.89)
    Similar,
    /// 相关但不同 (0.40–0.69)
    Related,
    /// 无关 (< 0.40)
    Unrelated,
}

impl ConflictCategory {
    pub fn from_similarity(sim: f64) -> Self {
        if sim >= 0.90 {
            ConflictCategory::Exact
        } else if sim >= 0.70 {
            ConflictCategory::Similar
        } else if sim >= 0.40 {
            ConflictCategory::Related
        } else {
            ConflictCategory::Unrelated
        }
    }
}

/// 计算 canonicalHash (SHA-256 前 16 个 hex 字符)
///
/// `canonicalHash = SHA-256(content.trim().to_lowercase()).hex()[0..16]`
pub fn canonical_hash(content: &str) -> String {
    let normalized = content.trim().to_lowercase();
    let mut hasher = Sha256::new();
    hasher.update(normalized.as_bytes());
    let result = hasher.finalize();
    hex::encode(&result[..8]) // 前 8 字节 = 16 hex 字符
}

/// hex 编码辅助
mod hex {
    pub fn encode(bytes: &[u8]) -> String {
        bytes.iter().map(|b| format!("{:02x}", b)).collect()
    }
}

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

    #[test]
    fn test_lcs_identical() {
        assert_eq!(lcs_similarity("Hello World", "Hello World"), 1.0);
    }

    #[test]
    fn test_lcs_completely_different() {
        assert_eq!(lcs_similarity("abc", "xyz"), 0.0);
    }

    #[test]
    fn test_lcs_partial_overlap() {
        let sim = lcs_similarity("使用 pnpm 作为包管理器", "建议使用 pnpm 管理依赖");
        assert!(sim > 0.3 && sim < 0.9, "similarity = {}", sim);
    }

    #[test]
    fn test_lcs_empty_strings() {
        assert_eq!(lcs_similarity("", "Hello"), 0.0);
        assert_eq!(lcs_similarity("Hello", ""), 0.0);
        assert_eq!(lcs_similarity("", ""), 0.0);
    }

    #[test]
    fn test_conflict_category() {
        assert_eq!(ConflictCategory::from_similarity(0.95), ConflictCategory::Exact);
        assert_eq!(ConflictCategory::from_similarity(0.80), ConflictCategory::Similar);
        assert_eq!(ConflictCategory::from_similarity(0.50), ConflictCategory::Related);
        assert_eq!(ConflictCategory::from_similarity(0.10), ConflictCategory::Unrelated);
    }

    #[test]
    fn test_canonical_hash_deterministic() {
        let h1 = canonical_hash("Hello World");
        let h2 = canonical_hash("Hello World");
        assert_eq!(h1, h2);
    }

    #[test]
    fn test_canonical_hash_case_insensitive() {
        let h1 = canonical_hash("HELLO WORLD");
        let h2 = canonical_hash("hello world");
        assert_eq!(h1, h2);
    }

    #[test]
    fn test_canonical_hash_trim() {
        let h1 = canonical_hash("  test  ");
        let h2 = canonical_hash("test");
        assert_eq!(h1, h2);
    }

    #[test]
    fn test_canonical_hash_length() {
        let h = canonical_hash("test");
        assert_eq!(h.len(), 16);
    }

    #[test]
    fn test_canonical_hash_different() {
        let h1 = canonical_hash("内容A");
        let h2 = canonical_hash("内容B");
        assert_ne!(h1, h2);
    }
}