memlay 0.1.5

//! Derived current state: key aliases, current heads, and semantic conflicts
//! (PRD §10.1). Aliases are derived first, then ordinary record heads are
//! computed over canonical keys. Nothing here is ever resolved by timestamp,
//! lexical order, confidence, or author.

use crate::records::store::LoadedRecord;
use crate::records::{Kind, Op, Record};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use uuid::Uuid;

#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
pub struct GraphIssue {
    /// Record the issue is attached to, when applicable.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub record_id: Option<Uuid>,
    /// Logical key the issue concerns, when applicable.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub key: Option<String>,
    pub code: IssueCode,
    pub message: String,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
#[serde(rename_all = "kebab-case")]
pub enum IssueCode {
    MissingSupersededId,
    CrossKeySupersession,
    SupersessionCycle,
    AliasConflict,
    AliasCycle,
    NoCurrentHead,
}

#[derive(Debug, Clone, serde::Serialize)]
pub struct KeyState {
    pub canonical_key: String,
    pub kind: Kind,
    /// IDs of current heads, sorted. One head is normal; more is a conflict.
    pub head_ids: Vec<Uuid>,
    /// True when the single head is an assert (key has an active value).
    pub active: bool,
    pub conflicted: bool,
    /// Literal keys that contributed records (differs from canonical when
    /// aliases fused historically divergent keys).
    pub literal_keys: BTreeSet<String>,
}

#[derive(Debug, Clone, serde::Serialize)]
pub struct Conflict {
    pub canonical_key: String,
    pub kind: Kind,
    pub head_ids: Vec<Uuid>,
    /// True when the conflicting heads entered under different literal keys
    /// and were fused by an alias (PRD §10.4 alias impact).
    pub alias_induced: bool,
}

#[derive(Debug, Default, serde::Serialize)]
pub struct MemoryGraph {
    /// Direct alias mappings (alias key -> canonical key) from active heads.
    pub alias_map: BTreeMap<String, String>,
    /// Derived state per canonical key (excludes key-alias records).
    pub keys: BTreeMap<String, KeyState>,
    pub conflicts: Vec<Conflict>,
    pub issues: Vec<GraphIssue>,
}

impl MemoryGraph {
    /// Resolve a literal key to its canonical key by following active alias
    /// mappings transitively. Cycles were already rejected during build; an
    /// unknown key resolves to itself.
    pub fn resolve_key(&self, key: &str) -> String {
        let mut current = key.to_string();
        let mut visited = HashSet::new();
        while let Some(next) = self.alias_map.get(&current) {
            if !visited.insert(current.clone()) {
                return key.to_string(); // defensive: cycle
            }
            current = next.clone();
        }
        current
    }
}

/// Derive heads within a set of records that share one identity: a record is
/// a head when no other record in the set supersedes it.
fn heads_within<'a>(group: &[&'a Record]) -> Vec<&'a Record> {
    let ids: HashSet<Uuid> = group.iter().map(|r| r.id).collect();
    let mut superseded: HashSet<Uuid> = HashSet::new();
    for r in group {
        for target in &r.supersedes {
            if ids.contains(target) && *target != r.id {
                superseded.insert(*target);
            }
        }
    }
    let mut heads: Vec<&Record> = group
        .iter()
        .copied()
        .filter(|r| !superseded.contains(&r.id))
        .collect();
    heads.sort_by_key(|r| r.id);
    heads
}

/// Build the derived memory graph from the currently visible valid records.
pub fn build(records: &[LoadedRecord]) -> MemoryGraph {
    let mut graph = MemoryGraph::default();
    let valid: Vec<&LoadedRecord> = records.iter().filter(|r| r.is_valid()).collect();
    let by_id: HashMap<Uuid, &LoadedRecord> = valid.iter().map(|r| (r.record.id, *r)).collect();

    // --- Step 1: alias heads, per alias identity, no alias application. ---
    let mut alias_groups: BTreeMap<String, Vec<&Record>> = BTreeMap::new();
    for lr in &valid {
        if lr.record.kind == Kind::KeyAlias {
            alias_groups
                .entry(lr.record.key.clone())
                .or_default()
                .push(&lr.record);
        }
    }

    let mut proposed: BTreeMap<String, (String, Uuid)> = BTreeMap::new(); // alias -> (canonical, head id)
    for (literal_key, group) in &alias_groups {
        let heads = heads_within(group);
        match heads.len() {
            0 => graph.issues.push(GraphIssue {
                record_id: None,
                key: Some(literal_key.clone()),
                code: IssueCode::SupersessionCycle,
                message: format!(
                    "alias identity '{literal_key}' has no current head (supersession cycle)"
                ),
            }),
            1 => {
                let head = heads[0];
                if head.op == Op::Assert {
                    if let (Some(alias), Some(canonical)) = (&head.alias_key, &head.canonical_key) {
                        proposed.insert(alias.clone(), (canonical.clone(), head.id));
                    }
                }
                // A retract head deactivates the alias: no mapping.
            }
            _ => {
                let ids: Vec<Uuid> = heads.iter().map(|r| r.id).collect();
                graph.issues.push(GraphIssue {
                    record_id: None,
                    key: Some(literal_key.clone()),
                    code: IssueCode::AliasConflict,
                    message: format!(
                        "alias identity '{literal_key}' has {} competing heads; resolve before the mapping can apply",
                        heads.len()
                    ),
                });
                graph.conflicts.push(Conflict {
                    canonical_key: literal_key.clone(),
                    kind: Kind::KeyAlias,
                    head_ids: ids,
                    alias_induced: false,
                });
            }
        }
    }

    // --- Step 2: reject cycles; accepted mappings become the alias map. ---
    for (alias, (canonical, head_id)) in &proposed {
        // Follow the chain from `canonical`; if it reaches back to `alias`, reject.
        let mut current = canonical.clone();
        let mut visited: HashSet<String> = HashSet::from([alias.clone()]);
        let mut cyclic = false;
        while let Some((next, _)) = proposed.get(&current) {
            if !visited.insert(current.clone()) {
                cyclic = true;
                break;
            }
            current = next.clone();
        }
        if cyclic || visited.contains(&current) && current == *alias {
            graph.issues.push(GraphIssue {
                record_id: Some(*head_id),
                key: Some(alias.clone()),
                code: IssueCode::AliasCycle,
                message: format!(
                    "alias '{alias}' -> '{canonical}' participates in a cycle; mapping rejected"
                ),
            });
        } else {
            graph.alias_map.insert(alias.clone(), canonical.clone());
        }
    }

    // --- Step 3: group non-alias records by canonical key. ---
    let mut groups: BTreeMap<String, Vec<&LoadedRecord>> = BTreeMap::new();
    for lr in &valid {
        if lr.record.kind == Kind::KeyAlias {
            continue;
        }
        let canonical = graph.resolve_key(&lr.record.key);
        groups.entry(canonical).or_default().push(lr);
    }

    // --- Step 4: validate supersession edges and derive heads per key. ---
    for (canonical, group) in &groups {
        let group_ids: HashSet<Uuid> = group.iter().map(|r| r.record.id).collect();
        let mut superseded: HashSet<Uuid> = HashSet::new();
        for lr in group {
            for target in &lr.record.supersedes {
                if group_ids.contains(target) {
                    superseded.insert(*target);
                } else if let Some(other) = by_id.get(target) {
                    let other_canonical = graph.resolve_key(&other.record.key);
                    graph.issues.push(GraphIssue {
                        record_id: Some(lr.record.id),
                        key: Some(canonical.clone()),
                        code: IssueCode::CrossKeySupersession,
                        message: format!(
                            "record {} (key '{}') supersedes {} which resolves to different canonical key '{}'; edge ignored",
                            lr.record.id, lr.record.key, target, other_canonical
                        ),
                    });
                } else {
                    graph.issues.push(GraphIssue {
                        record_id: Some(lr.record.id),
                        key: Some(canonical.clone()),
                        code: IssueCode::MissingSupersededId,
                        message: format!(
                            "record {} supersedes unknown record {target}; edge ignored",
                            lr.record.id
                        ),
                    });
                }
            }
        }

        let mut heads: Vec<&LoadedRecord> = group
            .iter()
            .copied()
            .filter(|r| !superseded.contains(&r.record.id))
            .collect();
        heads.sort_by_key(|r| r.record.id);

        let kind = heads
            .first()
            .map(|r| r.record.kind)
            .unwrap_or_else(|| group[0].record.kind);
        let literal_keys: BTreeSet<String> = group.iter().map(|r| r.record.key.clone()).collect();

        if heads.is_empty() {
            graph.issues.push(GraphIssue {
                record_id: None,
                key: Some(canonical.clone()),
                code: IssueCode::NoCurrentHead,
                message: format!(
                    "key '{canonical}' has records but no current head; the supersession graph contains a cycle"
                ),
            });
            graph.keys.insert(
                canonical.clone(),
                KeyState {
                    canonical_key: canonical.clone(),
                    kind,
                    head_ids: vec![],
                    active: false,
                    conflicted: false,
                    literal_keys,
                },
            );
            continue;
        }

        let conflicted = heads.len() > 1;
        if conflicted {
            let head_literal_keys: BTreeSet<&str> =
                heads.iter().map(|r| r.record.key.as_str()).collect();
            graph.conflicts.push(Conflict {
                canonical_key: canonical.clone(),
                kind,
                head_ids: heads.iter().map(|r| r.record.id).collect(),
                alias_induced: head_literal_keys.len() > 1,
            });
        }
        let active = !conflicted && heads[0].record.op == Op::Assert;
        graph.keys.insert(
            canonical.clone(),
            KeyState {
                canonical_key: canonical.clone(),
                kind,
                head_ids: heads.iter().map(|r| r.record.id).collect(),
                active,
                conflicted,
                literal_keys,
            },
        );
    }

    graph
        .conflicts
        .sort_by(|a, b| a.canonical_key.cmp(&b.canonical_key));
    graph
}

/// Alias impact simulation (PRD §10.4): before/after head counts and any
/// newly introduced semantic conflicts if `alias -> canonical` were applied.
#[derive(Debug, serde::Serialize)]
pub struct AliasImpact {
    pub alias_key: String,
    pub canonical_key: String,
    pub before_alias_heads: usize,
    pub before_canonical_heads: usize,
    pub after_heads: usize,
    pub introduces_conflict: bool,
}

pub fn simulate_alias(
    records: &[LoadedRecord],
    alias_key: &str,
    canonical_key: &str,
) -> AliasImpact {
    let before = build(records);
    let alias_resolved = before.resolve_key(alias_key);
    let canonical_resolved = before.resolve_key(canonical_key);
    let count = |g: &MemoryGraph, k: &str| g.keys.get(k).map(|s| s.head_ids.len()).unwrap_or(0);

    // Simulate by re-grouping: everything that resolved to the alias now
    // resolves to the canonical target.
    let mut merged_heads: BTreeSet<Uuid> = BTreeSet::new();
    for k in [&alias_resolved, &canonical_resolved] {
        if let Some(s) = before.keys.get(k.as_str()) {
            merged_heads.extend(s.head_ids.iter().copied());
        }
    }
    // Heads may collapse if a record in one group supersedes a record in the
    // other (previously a cross-key edge, valid after fusion).
    let by_id: HashMap<Uuid, &LoadedRecord> = records.iter().map(|r| (r.record.id, r)).collect();
    let mut both: Vec<&Record> = Vec::new();
    for lr in records.iter().filter(|r| r.is_valid()) {
        let rk = before.resolve_key(&lr.record.key);
        if rk == alias_resolved || rk == canonical_resolved {
            both.push(&lr.record);
        }
    }
    let after_heads = heads_within(&both).len();
    let _ = by_id;

    AliasImpact {
        alias_key: alias_key.to_string(),
        canonical_key: canonical_key.to_string(),
        before_alias_heads: count(&before, &alias_resolved),
        before_canonical_heads: count(&before, &canonical_resolved),
        after_heads,
        // A conflict is introduced (or worsened) whenever the fused key ends
        // up with more competing heads than the canonical key already had.
        introduces_conflict: after_heads > 1 && after_heads > count(&before, &canonical_resolved),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::records::{Confidence, Record};
    use chrono::TimeZone;
    use chrono::Utc;

    fn rec(key: &str, kind: Kind, op: Op, supersedes: Vec<Uuid>) -> LoadedRecord {
        let record = Record {
            id: Uuid::now_v7(),
            key: key.into(),
            kind,
            op,
            summary: "S.".into(),
            rationale: Some("R.".into()),
            confidence: Confidence::Verified,
            created_at: Utc.with_ymd_and_hms(2026, 7, 27, 0, 0, 0).unwrap(),
            writer: "w".into(),
            human: None,
            agent: None,
            session: None,
            pr: None,
            issue: None,
            alias_key: None,
            canonical_key: None,
            details: vec![],
            alternatives: vec![],
            consequences: vec![],
            paths: vec![],
            symbols: vec![],
            tags: vec!["t".into()],
            evidence: vec![],
            supersedes,
            related: vec![],
            extensions: vec![],
        };
        LoadedRecord {
            rel_path: record.relative_path(),
            record,
            issues: vec![],
        }
    }

    fn alias(alias_key: &str, canonical: &str, supersedes: Vec<Uuid>) -> LoadedRecord {
        let mut lr = rec(
            &format!("key-alias.{alias_key}"),
            Kind::KeyAlias,
            Op::Assert,
            supersedes,
        );
        lr.record.alias_key = Some(alias_key.into());
        lr.record.canonical_key = Some(canonical.into());
        lr
    }

    #[test]
    fn single_head_is_active() {
        let a = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let g = build(std::slice::from_ref(&a));
        let s = &g.keys["k.a"];
        assert_eq!(s.head_ids, vec![a.record.id]);
        assert!(s.active);
        assert!(!s.conflicted);
    }

    #[test]
    fn supersession_moves_head() {
        let a = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let b = rec("k.a", Kind::Decision, Op::Assert, vec![a.record.id]);
        let g = build(&[a.clone(), b.clone()]);
        assert_eq!(g.keys["k.a"].head_ids, vec![b.record.id]);
        assert!(g.conflicts.is_empty());
    }

    #[test]
    fn two_heads_conflict_and_never_auto_resolve() {
        let a = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let b = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let g = build(&[a, b]);
        assert!(g.keys["k.a"].conflicted);
        assert!(!g.keys["k.a"].active);
        assert_eq!(g.conflicts.len(), 1);
        assert_eq!(g.conflicts[0].head_ids.len(), 2);
    }

    #[test]
    fn resolve_supersedes_both_heads() {
        let a = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let b = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let c = rec(
            "k.a",
            Kind::Decision,
            Op::Assert,
            vec![a.record.id, b.record.id],
        );
        let g = build(&[a, b, c.clone()]);
        assert_eq!(g.keys["k.a"].head_ids, vec![c.record.id]);
        assert!(g.conflicts.is_empty());
    }

    #[test]
    fn retract_deactivates() {
        let a = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let b = rec("k.a", Kind::Decision, Op::Retract, vec![a.record.id]);
        let g = build(&[a, b]);
        assert!(!g.keys["k.a"].active);
        assert!(!g.keys["k.a"].conflicted);
    }

    #[test]
    fn cycle_reported_no_head() {
        let mut a = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let mut b = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        a.record.supersedes = vec![b.record.id];
        b.record.supersedes = vec![a.record.id];
        let g = build(&[a, b]);
        assert!(g.keys["k.a"].head_ids.is_empty());
        assert!(g.issues.iter().any(|i| i.code == IssueCode::NoCurrentHead));
    }

    #[test]
    fn cross_key_supersession_ignored_and_reported() {
        let a = rec("k.a", Kind::Decision, Op::Assert, vec![]);
        let b = rec("k.b", Kind::Decision, Op::Assert, vec![a.record.id]);
        let g = build(&[a.clone(), b]);
        assert_eq!(g.keys["k.a"].head_ids, vec![a.record.id]);
        assert!(g
            .issues
            .iter()
            .any(|i| i.code == IssueCode::CrossKeySupersession));
    }

    #[test]
    fn alias_fuses_keys_and_flags_alias_induced_conflict() {
        let a = rec("auth.tokens", Kind::Decision, Op::Assert, vec![]);
        let b = rec("auth.token-storage", Kind::Decision, Op::Assert, vec![]);
        let m = alias("auth.tokens", "auth.token-storage", vec![]);
        let g = build(&[a, b, m]);
        let s = &g.keys["auth.token-storage"];
        assert!(s.conflicted);
        assert_eq!(g.conflicts.len(), 1);
        assert!(g.conflicts[0].alias_induced);
    }

    #[test]
    fn alias_cycle_rejected() {
        let m1 = alias("a.one", "a.two", vec![]);
        let m2 = alias("a.two", "a.one", vec![]);
        let g = build(&[m1, m2]);
        assert!(g.issues.iter().any(|i| i.code == IssueCode::AliasCycle));
        // Neither mapping may silently win.
        assert!(g.alias_map.is_empty() || g.alias_map.len() < 2);
    }

    #[test]
    fn alias_supersession_updates_mapping() {
        let m1 = alias("a.old", "a.first", vec![]);
        let m2 = alias("a.old", "a.second", vec![m1.record.id]);
        let g = build(&[m1, m2]);
        assert_eq!(g.alias_map.get("a.old"), Some(&"a.second".to_string()));
    }

    #[test]
    fn event_keys_do_not_conflict_across_distinct_events() {
        let a = rec(
            &format!("change.{}", Uuid::now_v7()),
            Kind::Change,
            Op::Assert,
            vec![],
        );
        let b = rec(
            &format!("change.{}", Uuid::now_v7()),
            Kind::Change,
            Op::Assert,
            vec![],
        );
        let g = build(&[a, b]);
        assert!(g.conflicts.is_empty());
    }

    #[test]
    fn simulate_alias_predicts_conflict() {
        let a = rec("auth.tokens", Kind::Decision, Op::Assert, vec![]);
        let b = rec("auth.token-storage", Kind::Decision, Op::Assert, vec![]);
        let impact = simulate_alias(&[a, b], "auth.tokens", "auth.token-storage");
        assert_eq!(impact.before_alias_heads, 1);
        assert_eq!(impact.before_canonical_heads, 1);
        assert_eq!(impact.after_heads, 2);
        assert!(impact.introduces_conflict);
    }
}