minutes-core 0.25.1

//! Person entity-resolution clustering — issue #385, class 3 (name-variant
//! fragmentation, e.g. `junrei` / `jun-rei` / `junlei` / `junwei`).
//!
//! This is **suggestion-only**. It groups people whose names are plausibly the
//! same person so the graph can surface them as candidates for a human to
//! confirm. It NEVER merges or writes anything. Per the entity-resolution plan
//! (`docs/plans/person-entity-resolution-2026-06-26.md`) a wrong merge is worse
//! than a split, so the merge action is a confirm-gated follow-up. Because
//! nothing is written, an over-eager suggestion costs precision, not data.
//!
//! Two link tiers, both conservative:
//! - **Separator variant** — identical characters modulo separators and case
//!   (`Mo-Han` ~ `mohan`, `jun-rei` ~ `junrei`). Guarded by a minimum length.
//! - **Spelling edit** — single-token, ASCII names that share a first letter and
//!   are within a length-scaled edit budget (`geert` ~ `gert`, `junrei` ~
//!   `junlei`). ASCII-only because same-first + bounded edit is a Latin
//!   heuristic; a single edit between distinct non-ASCII names (李雷/李蕾) is not
//!   a same-person signal. Reuses the exact edit-distance matcher from
//!   `name_correction`.

use crate::name_correction::normalize_name;

/// Why two names were linked. Kept for tests/scoring; the graph display collapses
/// clusters and does not surface the per-edge reason.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum MatchReason {
    /// Same characters modulo separators/case (`jun-rei` ~ `junrei`).
    SeparatorVariant,
    /// Same first letter, within edit budget (`geert` ~ `gert`).
    PhoneticEdit,
}

/// Minimum compact length for a separator-variant match, so short initials
/// (`d-p`, `c-s`) don't collapse to one entity.
const MIN_COMPACT_LEN: usize = 3;
const MAX_MATCH_NAME_BYTES: usize = 4 * 1024;

fn bounded_ascii_levenshtein(a: &[u8], b: &[u8], limit: usize) -> bool {
    if a.len().abs_diff(b.len()) > limit {
        return false;
    }
    let unreachable = limit + 1;
    let mut previous = vec![unreachable; b.len() + 1];
    let mut current = vec![unreachable; b.len() + 1];
    for (index, value) in previous.iter_mut().enumerate().take(limit + 1) {
        *value = index;
    }
    for (i, &left) in a.iter().enumerate() {
        current.fill(unreachable);
        let row = i + 1;
        if row <= limit {
            current[0] = row;
        }
        let start = row.saturating_sub(limit).max(1);
        let end = b.len().min(row.saturating_add(limit));
        let mut row_min = current[0];
        for column in start..=end {
            let substitution = previous[column - 1] + usize::from(left != b[column - 1]);
            current[column] = (previous[column] + 1)
                .min(current[column - 1] + 1)
                .min(substitution);
            row_min = row_min.min(current[column]);
        }
        if row_min > limit {
            return false;
        }
        std::mem::swap(&mut previous, &mut current);
    }
    previous[b.len()] <= limit
}

/// Compact key: normalized (lowercase + accent-folded) with every non-alphanumeric
/// character removed, so pure separator/case variants share a key
/// (`Mo-Han` -> `mohan`, `jun-rei` -> `junrei`, `José` -> `jose`).
pub(crate) fn compact_key(name: &str) -> String {
    normalize_name(name)
        .chars()
        .filter(|c| c.is_alphanumeric())
        .collect()
}

/// Edit budget for a normalized token: 1 edit for short names, 2 for longer.
/// Mirrors `name_correction::distance_budget`.
fn distance_budget(len: usize) -> usize {
    if len >= 6 {
        2
    } else {
        1
    }
}

fn is_single_token(name: &str) -> bool {
    normalize_name(name).split_whitespace().count() == 1
}

/// Are these two names plausibly the same person? Returns the reason when yes.
///
/// SUGGESTION strength only — this decides whether to *propose* a link, never to
/// merge. It is deliberately recall-oriented in the ambiguous short-name band
/// (`sam`/`sami`, `an`/`ann`): those become suggestions a human resolves. It
/// stays confidently negative for dissimilar names (different first letter,
/// different phonetics, out of edit budget).
pub(crate) fn names_plausibly_same_person(a: &str, b: &str) -> Option<MatchReason> {
    if a.len() > MAX_MATCH_NAME_BYTES || b.len() > MAX_MATCH_NAME_BYTES {
        return None;
    }
    let ca = compact_key(a);
    let cb = compact_key(b);
    if ca.is_empty() || cb.is_empty() {
        return None;
    }

    // Tier 1: identical compact key => separator/case variant.
    if ca == cb {
        if ca.chars().count() >= MIN_COMPACT_LEN {
            return Some(MatchReason::SeparatorVariant);
        }
        return None;
    }

    // Tier 2: single-edit spelling drift, single-token names only. Multi-token
    // names are the existing `names_likely_same` (prefix/last-name) territory,
    // and edit distance over full multi-word strings is too noisy to trust.
    if !is_single_token(a) || !is_single_token(b) {
        return None;
    }
    let na = normalize_name(a);
    let nb = normalize_name(b);
    // ASCII-only. Same-first-letter + bounded edit is an English/Latin heuristic;
    // for non-ASCII scripts (e.g. CJK) a single edit between DISTINCT names
    // (李雷 vs 李蕾) is common and must not be suggested as the same person.
    // Accent-folded Latin names (José -> jose) are ASCII here, so they still match.
    if !na.is_ascii() || !nb.is_ascii() {
        return None;
    }
    // Require the same first letter: a coincidental single edit across different
    // initials is too weak a signal to even suggest.
    if na.as_bytes().first() != nb.as_bytes().first() {
        return None;
    }
    let budget = distance_budget(na.chars().count().min(nb.chars().count()));
    if bounded_ascii_levenshtein(na.as_bytes(), nb.as_bytes(), budget) {
        Some(MatchReason::PhoneticEdit)
    } else {
        None
    }
}

/// Cluster an explicit edge list into CLIQUES (groups where every pair is a
/// direct edge), not mere connected components. This is what prevents fuzzy-match
/// drift CHAINS from bridging distinct people: `jon`~`jan`~`jana` form one
/// connected component, but `jon`/`jana` are not directly linked, so they must
/// never share a cluster. Real drift groups (`junrei`/`junlei`/`junwei`/`jun-rei`)
/// are fully connected and survive as one cluster.
///
/// A connected component that is already a clique is emitted whole. A non-clique
/// component is decomposed into its direct-edge pairs (2-member clusters), so
/// every real pairwise link is still surfaced without the spurious transitive
/// pair. Output is deterministic: members sorted, clusters ordered lexically.
#[cfg(test)]
pub(crate) fn cluster_indices(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
    cluster_indices_with_check(n, edges, || true).unwrap_or_default()
}

pub(crate) fn cluster_indices_with_check(
    n: usize,
    edges: &[(usize, usize)],
    mut check: impl FnMut() -> bool,
) -> Option<Vec<Vec<usize>>> {
    use std::collections::{BTreeMap, BTreeSet};

    // Normalize edges to (min, max) and dedup.
    let mut edge_set: BTreeSet<(usize, usize)> = BTreeSet::new();
    for &(a, b) in edges {
        if !check() {
            return None;
        }
        if a >= n || b >= n || a == b {
            continue;
        }
        edge_set.insert((a.min(b), a.max(b)));
    }

    let mut parent: Vec<usize> = (0..n).collect();
    fn find(parent: &mut [usize], x: usize) -> usize {
        let mut root = x;
        while parent[root] != root {
            root = parent[root];
        }
        let mut cur = x;
        while parent[cur] != root {
            let next = parent[cur];
            parent[cur] = root;
            cur = next;
        }
        root
    }
    for &(a, b) in &edge_set {
        if !check() {
            return None;
        }
        let ra = find(&mut parent, a);
        let rb = find(&mut parent, b);
        if ra != rb {
            if ra < rb {
                parent[rb] = ra;
            } else {
                parent[ra] = rb;
            }
        }
    }

    let mut components: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
    for i in 0..n {
        if !check() {
            return None;
        }
        let root = find(&mut parent, i);
        components.entry(root).or_default().push(i);
    }

    let is_edge = |a: usize, b: usize| edge_set.contains(&(a.min(b), a.max(b)));
    let mut clusters: Vec<Vec<usize>> = Vec::new();
    for members in components.into_values() {
        if !check() {
            return None;
        }
        if members.len() < 2 {
            continue;
        }
        // Clique? every pair within the component must be a direct edge.
        let mut is_clique = true;
        'clique: for (i, &a) in members.iter().enumerate() {
            for &b in &members[i + 1..] {
                if !check() {
                    return None;
                }
                if !is_edge(a, b) {
                    is_clique = false;
                    break 'clique;
                }
            }
        }
        if is_clique {
            clusters.push(members); // already ascending (built from 0..n)
        } else {
            // Decompose into direct-edge pairs so distinct chain endpoints
            // (jon/jana) never share a cluster.
            for i in 0..members.len() {
                for j in (i + 1)..members.len() {
                    if !check() {
                        return None;
                    }
                    if is_edge(members[i], members[j]) {
                        clusters.push(vec![members[i], members[j]]);
                    }
                }
            }
        }
    }
    clusters.sort();
    Some(clusters)
}

/// Convenience: cluster a flat list of names using [`names_plausibly_same_person`]
/// as the edge source, then [`cluster_indices`]. This is the same predicate the
/// graph layer uses for `alias_clusters`, so the eval mirrors production.
#[cfg(test)]
pub(crate) fn cluster_names(names: &[String]) -> Vec<Vec<usize>> {
    let mut edges = Vec::new();
    for i in 0..names.len() {
        for j in (i + 1)..names.len() {
            if names_plausibly_same_person(&names[i], &names[j]).is_some() {
                edges.push((i, j));
            }
        }
    }
    cluster_indices(names.len(), &edges)
}

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

    #[test]
    fn compact_key_folds_separators_case_and_accents() {
        assert_eq!(compact_key("Mo-Han"), "mohan");
        assert_eq!(compact_key("jun-rei"), "junrei");
        assert_eq!(compact_key("José"), "jose");
    }

    #[test]
    fn separator_variants_link() {
        assert_eq!(
            names_plausibly_same_person("jun-rei", "junrei"),
            Some(MatchReason::SeparatorVariant)
        );
    }

    #[test]
    fn short_separator_keys_do_not_link() {
        // "d-p" / "dp" compact to "dp" (len 2) < MIN_COMPACT_LEN.
        assert_eq!(names_plausibly_same_person("d-p", "dp"), None);
    }

    #[test]
    fn spelling_edit_drift_links() {
        assert_eq!(
            names_plausibly_same_person("geert", "gert"),
            Some(MatchReason::PhoneticEdit)
        );
        // r/l and r/w drift, same first letter, within budget.
        assert!(names_plausibly_same_person("junrei", "junlei").is_some());
        assert!(names_plausibly_same_person("junrei", "junwei").is_some());
    }

    #[test]
    fn oversized_names_are_rejected_before_normalization_or_edit_distance() {
        let oversized = format!("a{}", "x".repeat(MAX_MATCH_NAME_BYTES));
        assert_eq!(names_plausibly_same_person(&oversized, &oversized), None);
        assert!(!bounded_ascii_levenshtein(b"aaaaaaaa", b"azzzzzzz", 2));
    }

    #[test]
    fn bounded_edit_distance_matches_reference_inside_the_supported_thresholds() {
        let values = [
            "", "a", "b", "aa", "ab", "ba", "bb", "aaa", "aab", "abb", "bbb",
        ];
        for left in values {
            for right in values {
                for limit in 0..=2 {
                    assert_eq!(
                        bounded_ascii_levenshtein(left.as_bytes(), right.as_bytes(), limit),
                        crate::name_correction::levenshtein(left, right) <= limit,
                        "left={left:?} right={right:?} limit={limit}",
                    );
                }
            }
        }
    }

    #[test]
    fn checked_clustering_honors_the_operation_deadline_hook() {
        let mut checks = 0usize;
        let result = cluster_indices_with_check(3, &[(0, 1), (1, 2)], || {
            checks += 1;
            checks < 2
        });
        assert!(result.is_none());
    }

    #[test]
    fn dissimilar_names_do_not_link() {
        // Different first letter is not a signal, even for a single edit (c/k).
        assert_eq!(names_plausibly_same_person("carl", "karl"), None);
        assert_eq!(names_plausibly_same_person("carl", "deepak"), None);
        assert_eq!(names_plausibly_same_person("sarah", "sam"), None);
        assert_eq!(names_plausibly_same_person("bright", "liam"), None);
    }

    #[test]
    fn non_ascii_near_miss_does_not_link() {
        // Distinct CJK names one codepoint apart must NOT be suggested (no ASCII
        // phonetic/edit corroboration applies).
        assert_eq!(names_plausibly_same_person("李雷", "李蕾"), None);
    }

    #[test]
    fn multi_token_names_use_separator_tier_only() {
        // "Alex Chen" vs "Alex Kim": different compact, multi-token -> no phonetic tier.
        assert_eq!(names_plausibly_same_person("Alex Chen", "Alex Kim"), None);
    }

    #[test]
    fn clique_clustering_groups_a_drift_set() {
        // The jun* fragments are mutually linked (a clique), so they collapse to
        // one cluster; `bright` is unrelated and excluded.
        let names: Vec<String> = ["jun-rei", "junrei", "junlei", "junwei", "bright"]
            .iter()
            .map(|s| s.to_string())
            .collect();
        let clusters = cluster_names(&names);
        assert_eq!(clusters.len(), 1, "one cluster, bright excluded");
        // Indices 0..=3 are the jun* set.
        assert_eq!(clusters[0], vec![0, 1, 2, 3]);
    }

    #[test]
    fn drift_chain_does_not_bridge_endpoints() {
        // `jon`~`jan` and `jan`~`jana` are edges, but `jon`~`jana` is not (dist 2).
        // Clique emission must NOT put the chain endpoints in one cluster.
        let names: Vec<String> = ["jon", "jan", "jana"]
            .iter()
            .map(|s| s.to_string())
            .collect();
        let clusters = cluster_names(&names);
        for c in &clusters {
            assert!(
                !(c.contains(&0) && c.contains(&2)),
                "drift-chain endpoints jon/jana were bridged: {c:?}"
            );
        }
    }

    #[test]
    fn clustering_is_deterministic_and_excludes_singletons() {
        let names: Vec<String> = ["zeta", "gert", "geert"]
            .iter()
            .map(|s| s.to_string())
            .collect();
        let clusters = cluster_names(&names);
        // gert(1) ~ geert(2); zeta(0) is a singleton and excluded.
        assert_eq!(clusters, vec![vec![1, 2]]);
    }
}