corpora_core/

graph.rs

//! The immutable, queryable graph rules and adapters consume. `build` is pure:
//! `records -> (Graph, Vec<Diagnostic>)`, resolving supersession into three views —
//! **raw** (declared edges), **effective** (adopted successor, chased to the terminal),
//! and **pending** (a proposed/open replacement not yet adopted) — and flagging
//! duplicate ids, kind mismatches, multiple adopted successors, and cycles.

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

use crate::diagnostic::Diagnostic;
use crate::model::{DocPath, Facet, Id, Lifecycle, Record, Status};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Relation {
    DependsOn,
    Supports,
    Related,
    Link,
}

/// A typed (structured) citation from one record to another.
#[derive(Clone, Debug)]
pub struct Cite {
    pub target: Id,
    pub relation: Relation,
}

pub struct Graph {
    records: Vec<Arc<Record>>,
    by_id: BTreeMap<Id, usize>,
    /// `X -> Y`: Y is the (single) **adopted** successor that supersedes X.
    adopted_successor: BTreeMap<Id, Id>,
    /// `X -> [Y…]`: proposed/open records that supersede X but aren't adopted yet.
    pending: BTreeMap<Id, Vec<Id>>,
    /// Targets with more than one adopted successor: superseded, but with no resolvable
    /// terminal. Tracked explicitly because map-absence can't tell "genuinely terminal"
    /// from "removed because ambiguous".
    ambiguous: BTreeSet<Id>,
}

/// Has this record reached an adopted state? Decisions go by their adoption `status`;
/// other kinds are adopted once they leave `Draft`.
fn record_is_adopted(r: &Record) -> bool {
    match &r.facet {
        Facet::Decision(d) => matches!(
            d.status,
            Status::Accepted | Status::Superseded | Status::Deprecated
        ),
        _ => r.lifecycle != Lifecycle::Draft,
    }
}

impl Graph {
    pub fn build(records: Vec<Arc<Record>>) -> (Graph, Vec<Diagnostic>) {
        let mut by_id = BTreeMap::new();
        let mut adopted_successor: BTreeMap<Id, Id> = BTreeMap::new();
        let mut pending: BTreeMap<Id, Vec<Id>> = BTreeMap::new();
        let mut ambiguous: BTreeSet<Id> = BTreeSet::new();
        let mut diags = Vec::new();

        // Pass 1: index ids, flag duplicates.
        for (i, r) in records.iter().enumerate() {
            if let Some(id) = &r.id {
                if by_id.insert(id.clone(), i).is_some() {
                    diags.push(Diagnostic::error(
                        "DUP",
                        &r.path,
                        format!("duplicate id {}", id.0),
                    ));
                }
            }
        }

        // Pass 2: classify supersession edges. An edge with a dangling target or a kind
        // mismatch is diagnosed and *dropped* — it must not reach the resolved maps, or an
        // unknown id would look superseded and a cross-kind atom could become a migration
        // target. Adopted successors are collected per target so arity is known before any
        // edge becomes "effective".
        let mut adopted_cands: BTreeMap<Id, Vec<Id>> = BTreeMap::new();
        for r in records.iter() {
            let Some(src) = &r.id else { continue };
            let adopted = record_is_adopted(r);
            for tgt in &r.edges.supersedes {
                let valid = match by_id.get(tgt) {
                    None => {
                        diags.push(Diagnostic::warn(
                            "SUPERSEDE",
                            &r.path,
                            format!("{} supersedes unknown id {}", src.0, tgt.0),
                        ));
                        false
                    }
                    Some(&ti) => {
                        let tkind = records[ti].kind;
                        if tkind != r.kind {
                            diags.push(Diagnostic::error(
                                "KIND",
                                &r.path,
                                format!(
                                    "{} ({:?}) supersedes {} of different kind ({:?})",
                                    src.0, r.kind, tgt.0, tkind
                                ),
                            ));
                            false
                        } else {
                            true
                        }
                    }
                };
                if !valid {
                    continue;
                }

                if adopted {
                    let v = adopted_cands.entry(tgt.clone()).or_default();
                    if !v.contains(src) {
                        v.push(src.clone());
                    }
                } else {
                    let v = pending.entry(tgt.clone()).or_default();
                    if !v.contains(src) {
                        v.push(src.clone());
                    }
                }
            }
        }

        // Resolve adopted candidates: exactly one => the effective successor; more than one
        // => ambiguous, so the target gets NO effective successor (the result is then
        // independent of input ordering). The error is anchored on the contested target.
        for (tgt, srcs) in &adopted_cands {
            if srcs.len() == 1 {
                adopted_successor.insert(tgt.clone(), srcs[0].clone());
            } else {
                ambiguous.insert(tgt.clone());
                let mut names: Vec<&str> = srcs.iter().map(|i| i.0.as_str()).collect();
                names.sort_unstable();
                let path = by_id
                    .get(tgt)
                    .map(|&i| records[i].path.clone())
                    .unwrap_or_else(|| DocPath(tgt.0.clone()));
                diags.push(Diagnostic::error(
                    "SUPERSEDE",
                    &path,
                    format!("{} has multiple adopted successors: {}", tgt.0, names.join(", ")),
                ));
            }
        }

        // Pass 3: cycle detection over the adopted-successor chain (report each cycle once).
        let mut cyclic: BTreeSet<Id> = BTreeSet::new();
        for start in adopted_successor.keys() {
            if cyclic.contains(start) {
                continue;
            }
            let mut seen: Vec<Id> = Vec::new();
            let mut cur = start.clone();
            loop {
                if cyclic.contains(&cur) {
                    break; // this chain feeds a cycle that was already reported
                }
                if let Some(pos) = seen.iter().position(|x| *x == cur) {
                    for id in &seen[pos..] {
                        cyclic.insert(id.clone());
                    }
                    let mut chain: Vec<String> =
                        seen[pos..].iter().map(|i| i.0.clone()).collect();
                    chain.push(cur.0.clone());
                    let path = by_id
                        .get(&cur)
                        .map(|&i| records[i].path.clone())
                        .unwrap_or_else(|| DocPath(cur.0.clone()));
                    diags.push(Diagnostic::error(
                        "CYCLE",
                        &path,
                        format!("supersession cycle: {}", chain.join(" → ")),
                    ));
                    break;
                }
                seen.push(cur.clone());
                match adopted_successor.get(&cur) {
                    Some(next) => cur = next.clone(),
                    None => break,
                }
            }
        }

        (
            Graph {
                records,
                by_id,
                adopted_successor,
                pending,
                ambiguous,
            },
            diags,
        )
    }

    pub fn records(&self) -> impl Iterator<Item = &Record> {
        self.records.iter().map(|a| a.as_ref())
    }

    pub fn get(&self, id: &Id) -> Option<&Record> {
        self.by_id.get(id).map(|&i| self.records[i].as_ref())
    }

    /// True iff `id` has been superseded — it carries at least one adopted successor edge,
    /// whether or not that resolves to a single live atom. Direct-edge semantics only;
    /// whether a *safe* terminal migration exists is [`effective_successor`]'s question.
    ///
    /// [`effective_successor`]: Graph::effective_successor
    pub fn is_superseded(&self, id: &Id) -> bool {
        self.adopted_successor.contains_key(id) || self.ambiguous.contains(id)
    }

    /// The terminal adopted successor of `id` — the live atom a stale citation should
    /// migrate to — chasing multi-hop chains. Returns `None` when no *safe* terminal
    /// exists: the chain enters a cycle, or it runs through an ambiguous node (one with
    /// multiple adopted successors), which is itself unresolved. Downstream rules must not
    /// recommend a migration target in those cases.
    pub fn effective_successor(&self, id: &Id) -> Option<&Id> {
        if self.ambiguous.contains(id) {
            return None;
        }
        let mut seen: BTreeSet<Id> = BTreeSet::new();
        seen.insert(id.clone());
        let mut cur = self.adopted_successor.get(id)?;
        loop {
            if !seen.insert(cur.clone()) {
                return None; // cycle: no well-defined terminal successor
            }
            if self.ambiguous.contains(cur) {
                return None; // path runs through an unresolved (multiply-superseded) node
            }
            match self.adopted_successor.get(cur) {
                Some(next) => cur = next,
                None => return Some(cur),
            }
        }
    }

    /// Proposed/open records superseding `id` that haven't been adopted — the
    /// pending-supersession view (e.g. open forks).
    pub fn pending_successors(&self, id: &Id) -> &[Id] {
        self.pending.get(id).map(|v| v.as_slice()).unwrap_or(&[])
    }

    /// Typed edges out of `from` (depends_on / supports / related) — the E3 *error* path.
    pub fn structured_citations(&self, from: &Id) -> Vec<Cite> {
        let Some(r) = self.get(from) else {
            return Vec::new();
        };
        let mut v = Vec::new();
        for t in &r.edges.depends_on {
            v.push(Cite {
                target: t.clone(),
                relation: Relation::DependsOn,
            });
        }
        for t in &r.edges.supports {
            v.push(Cite {
                target: t.clone(),
                relation: Relation::Supports,
            });
        }
        for t in &r.edges.related {
            v.push(Cite {
                target: t.clone(),
                relation: Relation::Related,
            });
        }
        for t in &r.body.link_refs {
            v.push(Cite {
                target: t.clone(),
                relation: Relation::Link,
            });
        }
        v
    }

    /// Bare prose mentions out of `from` — the E3 *warning* path.
    pub fn bare_mentions(&self, from: &Id) -> Vec<Id> {
        self.get(from)
            .map(|r| r.body.bare_mentions.clone())
            .unwrap_or_default()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::diagnostic::Severity;
    use crate::model::*;

    fn id(s: &str) -> Id {
        Id(s.into())
    }

    /// A decision record with the given adoption status and `supersedes` targets.
    fn decision(name: &str, status: Status, supersedes: &[&str]) -> Record {
        let mut r = Record::minimal(
            Some(id(name)),
            DocPath(format!("{name}.md")),
            Kind::Decision,
            Lifecycle::Current,
            Authority::Normative,
            Facet::Decision(DecisionFacet {
                status,
                date: Date("2026-06-21".into()),
                implementation: None,
                fork: None,
                realized_by: vec![],
            }),
        );
        r.edges.supersedes = supersedes.iter().map(|s| id(s)).collect();
        r
    }

    fn build(records: Vec<Record>) -> (Graph, Vec<Diagnostic>) {
        Graph::build(records.into_iter().map(Arc::new).collect())
    }

    fn codes(diags: &[Diagnostic]) -> Vec<&str> {
        diags.iter().map(|d| d.code.as_str()).collect()
    }

    #[test]
    fn supersession_resolves() {
        let d1 = decision("D1", Status::Superseded, &[]);
        let d2 = decision("D2", Status::Accepted, &["D1"]);
        let (g, diags) = build(vec![d1, d2]);
        assert!(diags.is_empty(), "{diags:?}");
        assert!(g.is_superseded(&id("D1")));
        assert_eq!(g.effective_successor(&id("D1")), Some(&id("D2")));
        assert!(!g.is_superseded(&id("D2")));
    }

    #[test]
    fn effective_successor_chases_to_terminal() {
        let d1 = decision("D1", Status::Superseded, &[]);
        let d2 = decision("D2", Status::Superseded, &["D1"]);
        let d3 = decision("D3", Status::Accepted, &["D2"]);
        let (g, diags) = build(vec![d1, d2, d3]);
        assert!(diags.is_empty(), "{diags:?}");
        assert_eq!(g.effective_successor(&id("D1")), Some(&id("D3")));
        assert_eq!(g.effective_successor(&id("D2")), Some(&id("D3")));
    }

    #[test]
    fn proposed_successor_is_pending_not_effective() {
        let d1 = decision("D1", Status::Accepted, &[]);
        let d2 = decision("D2", Status::Proposed, &["D1"]); // not yet adopted
        let (g, diags) = build(vec![d1, d2]);
        assert!(diags.is_empty(), "{diags:?}");
        assert!(!g.is_superseded(&id("D1")));
        assert_eq!(g.effective_successor(&id("D1")), None);
        assert_eq!(g.pending_successors(&id("D1")), &[id("D2")]);
    }

    #[test]
    fn two_adopted_successors_conflict() {
        let d1 = decision("D1", Status::Superseded, &[]);
        let d2 = decision("D2", Status::Accepted, &["D1"]);
        let d3 = decision("D3", Status::Accepted, &["D1"]);
        let (g, diags) = build(vec![d1, d2, d3]);
        assert!(codes(&diags).contains(&"SUPERSEDE"), "{diags:?}");
        // Ambiguous target => superseded (direct edges exist) but NO safe terminal.
        assert!(g.is_superseded(&id("D1")));
        assert_eq!(g.effective_successor(&id("D1")), None);
    }

    #[test]
    fn ambiguity_is_order_independent() {
        // Same three records, reversed input order: the verdict must not change.
        let d1 = decision("D1", Status::Superseded, &[]);
        let d2 = decision("D2", Status::Accepted, &["D1"]);
        let d3 = decision("D3", Status::Accepted, &["D1"]);
        let (g, _) = build(vec![d3, d2, d1]);
        assert_eq!(g.effective_successor(&id("D1")), None);
    }

    #[test]
    fn ambiguity_is_not_transitively_resolvable() {
        // B supersedes A; C and D both supersede B. A has a single successor (B), but B is
        // ambiguous, so A has no *safe* terminal even though it is superseded.
        let a = decision("A", Status::Superseded, &[]);
        let b = decision("B", Status::Superseded, &["A"]);
        let c = decision("C", Status::Accepted, &["B"]);
        let d = decision("D", Status::Accepted, &["B"]);
        let (g, diags) = build(vec![a, b, c, d]);

        assert!(g.is_superseded(&id("A")), "A is superseded by B");
        assert_eq!(
            g.effective_successor(&id("A")),
            None,
            "A's chain runs through the ambiguous B, so no terminal is safe"
        );
        // The ambiguity error is anchored on the contested target, B.
        let sup = diags
            .iter()
            .find(|x| x.code == "SUPERSEDE")
            .expect("ambiguity should be reported");
        assert_eq!(sup.path, DocPath("B.md".into()));
    }

    #[test]
    fn kind_must_be_preserved() {
        let d1 = decision("D1", Status::Superseded, &[]);
        let mut a1 = Record::minimal(
            Some(id("A1")),
            DocPath("a1.md".into()),
            Kind::Axiom,
            Lifecycle::Current,
            Authority::Axiomatic,
            Facet::Axiom,
        );
        a1.edges.supersedes = vec![id("D1")];
        let (g, diags) = build(vec![d1, a1]);
        assert!(codes(&diags).contains(&"KIND"), "{diags:?}");
        // The kind-mismatched edge is dropped: the target is not superseded.
        assert!(!g.is_superseded(&id("D1")));
        assert_eq!(g.effective_successor(&id("D1")), None);
    }

    #[test]
    fn supersession_cycle_detected() {
        let d1 = decision("D1", Status::Accepted, &["D2"]);
        let d2 = decision("D2", Status::Accepted, &["D1"]);
        let (g, diags) = build(vec![d1, d2]);
        let cycle: Vec<_> = diags.iter().filter(|d| d.code == "CYCLE").collect();
        assert_eq!(cycle.len(), 1, "exactly one cycle report: {diags:?}");
        // A cycle has no well-defined terminal, so no migration target is offered.
        assert_eq!(g.effective_successor(&id("D1")), None);
        assert_eq!(g.effective_successor(&id("D2")), None);
    }

    #[test]
    fn cycle_reported_once_through_tails() {
        // Cycle B<->C, with tails A→B and E→C feeding into it. Report it exactly once,
        // even though a tail that starts after detection still walks into the cycle.
        let a = decision("A", Status::Accepted, &[]);
        let b = decision("B", Status::Accepted, &["A", "C"]);
        let c = decision("C", Status::Accepted, &["B", "E"]);
        let e = decision("E", Status::Accepted, &[]);
        let (_g, diags) = build(vec![a, b, c, e]);
        let cycle: Vec<_> = diags.iter().filter(|d| d.code == "CYCLE").collect();
        assert_eq!(cycle.len(), 1, "one report despite multiple tails: {diags:?}");
    }

    #[test]
    fn dangling_supersedes_warns_and_drops_edge() {
        let d2 = decision("D2", Status::Accepted, &["D1"]); // D1 absent
        let (g, diags) = build(vec![d2]);
        assert!(codes(&diags).contains(&"SUPERSEDE"), "{diags:?}");
        assert_eq!(diags[0].severity, Severity::Warning);
        // The unknown id must not appear superseded.
        assert!(!g.is_superseded(&id("D1")));
    }

    #[test]
    fn duplicate_id_flagged() {
        let a = decision("D1", Status::Accepted, &[]);
        let mut b = decision("D1", Status::Accepted, &[]);
        b.path = DocPath("b.md".into());
        let (_g, diags) = build(vec![a, b]);
        assert_eq!(codes(&diags), vec!["DUP"]);
    }
}