artifactize_core/

graph.rs

//! Dependency edges, strongly connected components, gates, and obligations.

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

use petgraph::{algo::kosaraju_scc, graph::DiGraph};
use thiserror::Error;

use crate::{
    config::{ArtifactName, EvalId, RepoConfig},
    runtime::Verdict,
};

#[derive(Debug, Error)]
#[error("{0}")]
pub struct GraphError(pub String);

/// A strongly-connected component's position in `Graph::components`, guarding it from
/// arbitrary `usize` arithmetic: dependency-first, so a lower id is never a later
/// component's dependency.
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize, serde::Deserialize,
)]
#[serde(transparent)]
pub struct ComponentId(usize);

impl ComponentId {
    /// Live graph and legacy saved components derive their identity from a list position.
    /// Saved explicit IDs deserialize as the same unsigned integer, never arithmetic indices.
    pub(crate) fn from_position(index: usize) -> Self {
        Self(index)
    }

    pub(crate) fn index(self) -> usize {
        self.0
    }
}

impl std::fmt::Display for ComponentId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.0.fmt(f)
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArtifactNode<'a> {
    pub basis: bool,
    pub evals: Vec<&'a EvalId>,
    /// The Artifacts it is directly composed of, by name.
    pub parts: Vec<&'a ArtifactName>,
    pub component: ComponentId,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Component<'a> {
    pub artifacts: Vec<&'a ArtifactName>,
    /// Direct condensation dependencies, always earlier in the component list.
    pub dependencies: Vec<ComponentId>,
    /// Aggregate external obligations for the material projection, not execution gates.
    /// Each Eval’s actual gates come from the Eval-level schedule.
    pub gates: Vec<&'a EvalId>,
}

#[derive(Debug)]
pub struct Graph<'a> {
    artifacts: BTreeMap<ArtifactName, ArtifactNode<'a>>,
    evals: BTreeMap<EvalId, &'a ArtifactName>,
    components: Vec<Component<'a>>,
    schedule: schedule::Schedule<'a>,
}

impl<'a> Graph<'a> {
    /// Build from scope's resolved relations without reading files or running code.
    pub fn new(config: &'a RepoConfig) -> Result<Self, GraphError> {
        let mut graph = DiGraph::<&ArtifactName, ()>::new();
        let nodes: BTreeMap<_, _> = config
            .artifacts
            .keys()
            .map(|id| (id, graph.add_node(id)))
            .collect();
        let mut artifacts: BTreeMap<_, _> = config
            .artifacts
            .iter()
            .map(|(id, artifact)| {
                (
                    id.clone(),
                    ArtifactNode {
                        basis: artifact.basis == Some(true),
                        evals: Vec::new(),
                        parts: Vec::new(),
                        component: ComponentId(0),
                    },
                )
            })
            .collect();
        let mut evals = BTreeMap::new();
        for eval in &config.evals {
            let artifact = artifacts
                .get_mut(&eval.target)
                .ok_or_else(|| GraphError(format!("Unknown Eval target: {}", eval.target)))?;
            if artifact.basis {
                return Err(GraphError(format!(
                    "Basis Artifact {} cannot own Evals.",
                    eval.target
                )));
            }
            if evals.insert(eval.id.clone(), &eval.target).is_some() {
                return Err(GraphError(format!("Duplicate Eval: {}", eval.id)));
            }
            artifact.evals.push(&eval.id);
        }
        for artifact in artifacts.values_mut() {
            artifact.evals.sort_unstable();
        }
        let mut edges = BTreeSet::new();
        for relation in &config.relations {
            for id in [&relation.source, &relation.target] {
                if !nodes.contains_key(id) {
                    return Err(GraphError(format!("Unknown relation Artifact: {id}")));
                }
            }
            // A parent needs its parts as a consumer needs its inputs, for obligations
            // only: execution gates come from references alone.
            edges.insert((&relation.target, &relation.source));
            if relation.kind == crate::scope::RelationKind::Part {
                artifacts
                    .get_mut(&relation.target)
                    .unwrap()
                    .parts
                    .push(&relation.source);
            }
        }
        // Consumer -> input makes iterative SCC traversal dependency-first.
        for &(consumer, dependency) in &edges {
            graph.add_edge(nodes[consumer], nodes[dependency], ());
        }
        let mut components: Vec<_> = kosaraju_scc(&graph)
            .into_iter()
            .map(|members| {
                let mut artifacts: Vec<_> = members.into_iter().map(|node| graph[node]).collect();
                artifacts.sort_unstable();
                Component {
                    artifacts,
                    dependencies: Vec::new(),
                    gates: Vec::new(),
                }
            })
            .collect();
        for (index, component) in components.iter().enumerate() {
            for id in &component.artifacts {
                artifacts.get_mut(id.as_str()).unwrap().component = ComponentId(index);
            }
        }
        let mut dependencies = vec![BTreeSet::new(); components.len()];
        for (consumer, dependency) in edges {
            let consumer = artifacts[consumer.as_str()].component;
            let dependency = artifacts[dependency.as_str()].component;
            if consumer != dependency {
                debug_assert!(dependency < consumer);
                dependencies[consumer.index()].insert(dependency);
            }
        }
        for (index, dependencies) in dependencies.into_iter().enumerate() {
            let mut gates: Vec<_> = dependencies
                .iter()
                .flat_map(|&dependency| &components[dependency.index()].artifacts)
                .flat_map(|id| &artifacts[id.as_str()].evals)
                .copied()
                .collect();
            gates.sort_unstable();
            components[index].dependencies = dependencies.into_iter().collect();
            components[index].gates = gates;
        }
        let schedule = schedule::Schedule::new(config.evals.iter().map(|eval| schedule::Input {
            id: &eval.id,
            target: &eval.target,
            deps: eval.deps.iter().collect(),
            human: eval.declaration.profile().kind() == crate::config::ProfileKind::Human,
        }));
        Ok(Self {
            artifacts,
            evals,
            components,
            schedule,
        })
    }

    pub fn artifacts(&self) -> &BTreeMap<ArtifactName, ArtifactNode<'a>> {
        &self.artifacts
    }

    /// Components are dependency-first; members and gates are lexically ordered.
    pub fn components(&self) -> &[Component<'a>] {
        &self.components
    }

    /// Required material and verification, including roots and all cycle peers.
    pub fn dependency_closure(
        &self,
        roots: &[&ArtifactName],
    ) -> Result<Vec<&'a ArtifactName>, GraphError> {
        let mut pending = Vec::new();
        for root in roots {
            let artifact = self
                .artifacts
                .get(*root)
                .ok_or_else(|| GraphError(format!("Unknown Artifact: {root}")))?;
            pending.push(artifact.component);
        }
        let mut visited = BTreeSet::new();
        let mut required = BTreeSet::new();
        while let Some(index) = pending.pop() {
            if !visited.insert(index) {
                continue;
            }
            let component = &self.components[index.index()];
            required.extend(component.artifacts.iter().copied());
            pending.extend(&component.dependencies);
        }
        Ok(required.into_iter().collect())
    }

    /// The roots and every Artifact sharing a cycle with one of them, lexically ordered.
    pub fn cycle_members(
        &self,
        roots: &[&ArtifactName],
    ) -> Result<Vec<&'a ArtifactName>, GraphError> {
        let components = roots
            .iter()
            .map(|root| {
                self.artifacts
                    .get(*root)
                    .map(|artifact| artifact.component)
                    .ok_or_else(|| GraphError(format!("Unknown Artifact: {root}")))
            })
            .collect::<Result<BTreeSet<_>, _>>()?;
        Ok(components
            .into_iter()
            .flat_map(|component| self.components[component.index()].artifacts.iter().copied())
            .collect::<BTreeSet<_>>()
            .into_iter()
            .collect())
    }

    /// Evaluate the whole graph. Evidence freshness is supplied by the caller;
    /// absent entries are unreviewed, and unrelated entries are ignored.
    pub fn evaluate(&self, evidence: &BTreeMap<EvalId, Evidence>) -> Evaluation<'_> {
        self.evaluate_for_run(evidence, false)
    }

    /// Speculation turns operational failures into immediate blockers, without changing
    /// the default read/verification policy of waiting for replacement GREEN evidence.
    pub(crate) fn evaluate_for_run(
        &self,
        evidence: &BTreeMap<EvalId, Evidence>,
        errors_block: bool,
    ) -> Evaluation<'_> {
        let mut evals: BTreeMap<EvalId, EvalEvaluation<'_>> = BTreeMap::new();
        for &id in &self.schedule.order {
            let gates = &self.schedule.gates[id];
            let unmet_gates: Vec<_> = gates
                .iter()
                .copied()
                .filter(|id| !evals[id.as_str()].status.passes_gate())
                .collect();
            // Only a Human eval's sibling machine evals share its Artifact; their ERROR blocks
            // it too, since a person signs off only on passing machine evals.
            let target = self.evals[id.as_str()];
            // A BLOCKED gate passes on its own causes: the root is always a RED upstream.
            let causes: Vec<_> = unmet_gates
                .iter()
                .flat_map(|&gate| {
                    let eval = &evals[gate.as_str()];
                    let sibling = self.evals[gate.as_str()] == target;
                    match eval.status {
                        EvalStatus::Red if sibling => vec![Cause::SiblingRed(gate)],
                        EvalStatus::Red => vec![Cause::Red(gate)],
                        EvalStatus::Error if sibling => vec![Cause::SiblingError(gate)],
                        EvalStatus::Error if errors_block => vec![Cause::Error(gate)],
                        EvalStatus::Blocked => {
                            eval.causes.iter().map(|cause| cause.upstream()).collect()
                        }
                        _ => Vec::new(),
                    }
                })
                .collect::<BTreeSet<_>>()
                .into_iter()
                .collect();
            let readiness = if !causes.is_empty() {
                Readiness::Blocked
            } else if unmet_gates.is_empty() {
                Readiness::Ready
            } else {
                Readiness::Wait
            };
            let provisional = gates.iter().any(|id| {
                matches!(
                    evals[id.as_str()].status,
                    EvalStatus::Deferred | EvalStatus::Provisional
                )
            });
            let evidence = evidence.get(id.as_str()).copied();
            let status = match readiness {
                Readiness::Blocked => EvalStatus::Blocked,
                Readiness::Wait => match evidence {
                    Some(Evidence::Current(Verdict::Red)) if errors_block => EvalStatus::Red,
                    Some(Evidence::OperationalError) if errors_block => EvalStatus::Error,
                    _ => EvalStatus::Wait,
                },
                Readiness::Ready => match evidence {
                    Some(Evidence::Deferred) => EvalStatus::Deferred,
                    Some(Evidence::Current(Verdict::Green)) if provisional => {
                        EvalStatus::Provisional
                    }
                    Some(Evidence::Current(Verdict::Green)) => EvalStatus::Green,
                    Some(Evidence::Current(Verdict::Red)) => EvalStatus::Red,
                    Some(Evidence::OperationalError) => EvalStatus::Error,
                    Some(Evidence::Stale) => EvalStatus::Stale,
                    None => EvalStatus::Unreviewed,
                },
            };
            let blocked_by = if causes.is_empty() {
                unmet_gates
                    .iter()
                    .copied()
                    .map(BlockedReference::Eval)
                    .collect()
            } else {
                causes
                    .iter()
                    .map(|cause| BlockedReference::Eval(cause.eval()))
                    .collect()
            };
            evals.insert(
                id.clone(),
                EvalEvaluation {
                    readiness,
                    status,
                    evidence,
                    unmet_gates,
                    blocked_by,
                    causes,
                },
            );
        }
        let own_satisfied: BTreeMap<_, _> = self
            .artifacts
            .iter()
            .map(|(id, artifact)| {
                // An Artifact without evals that is composed of others takes its verdict from
                // them, which the components below require.
                let satisfied = artifact.basis
                    || (artifact.evals.is_empty() && !artifact.parts.is_empty())
                    || (!artifact.evals.is_empty()
                        && artifact
                            .evals
                            .iter()
                            .all(|id| evals[id.as_str()].status == EvalStatus::Green));
                (id, satisfied)
            })
            .collect();
        let mut satisfied = vec![false; self.components.len()];
        for (index, component) in self.components.iter().enumerate() {
            satisfied[index] = component.artifacts.iter().all(|id| own_satisfied[id])
                && component
                    .dependencies
                    .iter()
                    .all(|&dependency| satisfied[dependency.index()]);
        }
        // A part's status is part of its parent's, so parts go first; parts never form a cycle.
        let mut order = Vec::with_capacity(self.artifacts.len());
        let mut placed = BTreeSet::new();
        for root in self.artifacts.keys() {
            let mut pending = vec![(root, false)];
            while let Some((id, expanded)) = pending.pop() {
                if expanded {
                    order.push((id, &self.artifacts[id]));
                } else if placed.insert(id) {
                    pending.push((id, true));
                    pending.extend(self.artifacts[id].parts.iter().map(|part| (*part, false)));
                }
            }
        }
        let mut artifacts: BTreeMap<ArtifactName, ArtifactEvaluation> = BTreeMap::new();
        for (id, artifact) in order {
            let satisfied = satisfied[artifact.component.index()];
            let status = if satisfied {
                if artifact.basis {
                    ArtifactStatus::Basis
                } else {
                    ArtifactStatus::Green
                }
            } else {
                [
                    (EvalStatus::Error, ArtifactStatus::Error),
                    (EvalStatus::Red, ArtifactStatus::Red),
                    (EvalStatus::Blocked, ArtifactStatus::Blocked),
                    (EvalStatus::Wait, ArtifactStatus::Wait),
                    (EvalStatus::Deferred, ArtifactStatus::Deferred),
                    (EvalStatus::Provisional, ArtifactStatus::Provisional),
                    (EvalStatus::Stale, ArtifactStatus::Stale),
                    (EvalStatus::Unreviewed, ArtifactStatus::Unreviewed),
                ]
                .into_iter()
                .find_map(|(eval_status, artifact_status)| {
                    (artifact
                        .evals
                        .iter()
                        .any(|id| evals[id.as_str()].status == eval_status)
                        || artifact
                            .parts
                            .iter()
                            .any(|id| artifacts[id.as_str()].status == artifact_status))
                    .then_some(artifact_status)
                })
                .unwrap_or(if own_satisfied[id] {
                    ArtifactStatus::Incomplete
                } else {
                    ArtifactStatus::Unreviewed
                })
            };
            artifacts.insert(
                id.clone(),
                ArtifactEvaluation {
                    status,
                    own_satisfied: own_satisfied[id],
                    satisfied,
                    passed: artifact
                        .evals
                        .iter()
                        .filter(|id| evals[id.as_str()].status == EvalStatus::Green)
                        .count(),
                    total: artifact.evals.len(),
                },
            );
        }
        let obligations: Vec<_> = own_satisfied
            .into_iter()
            .filter_map(|(id, satisfied)| (!satisfied).then_some(id))
            .collect();
        let status = if evals.values().any(|c| c.status == EvalStatus::Error) {
            FinalStatus::Error
        } else if evals.values().any(|c| c.status == EvalStatus::Red) {
            FinalStatus::Red
        } else if obligations.is_empty() {
            FinalStatus::Green
        } else {
            FinalStatus::Incomplete
        };
        Evaluation {
            evals,
            artifacts,
            obligations,
            status,
        }
    }

    pub(crate) fn gates(&self, id: &EvalId) -> Vec<&'a EvalId> {
        self.schedule.gates[id].clone()
    }

    pub fn eval_target(&self, id: &str) -> Option<&'a ArtifactName> {
        self.evals.get(id).copied()
    }
}

/// Current means usable for this input/run, not merely the latest stored result.
/// Stale evidence carries no current verdict; operational failure is not RED.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Evidence {
    Current(Verdict),
    Deferred,
    OperationalError,
    Stale,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Readiness {
    Ready,
    Wait,
    Blocked,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EvalStatus {
    Deferred,
    Provisional,
    Green,
    Red,
    Error,
    Stale,
    Unreviewed,
    Wait,
    Blocked,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EvalEvaluation<'a> {
    /// Gate readiness only; READY never requests re-execution of existing evidence.
    pub readiness: Readiness,
    pub status: EvalStatus,
    /// Retained for audit even when gates mask its effective status.
    pub evidence: Option<Evidence>,
    pub unmet_gates: Vec<&'a EvalId>,
    /// BLOCKED: the root causes; otherwise the unmet gates it waits for.
    pub blocked_by: Vec<BlockedReference<'a>>,
    /// Why the eval is BLOCKED, followed through BLOCKED gates to the failed evals upstream;
    /// empty unless BLOCKED.
    pub causes: Vec<Cause<'a>>,
}

/// The failed eval at the root of a block: a RED verdict, or in a Run that treats
/// operational failures as blockers (`--speculate`), an ERROR. A Human eval is also blocked
/// by a RED or ERROR machine eval of its own Artifact, its sibling.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Cause<'a> {
    Red(&'a EvalId),
    Error(&'a EvalId),
    SiblingRed(&'a EvalId),
    SiblingError(&'a EvalId),
}

impl<'a> Cause<'a> {
    pub fn eval(self) -> &'a EvalId {
        match self {
            Self::Red(id) | Self::Error(id) | Self::SiblingRed(id) | Self::SiblingError(id) => id,
        }
    }

    /// The same failure as seen from downstream, where it is an upstream dependency.
    fn upstream(self) -> Self {
        match self {
            Self::SiblingRed(id) => Self::Red(id),
            Self::SiblingError(id) => Self::Error(id),
            cause => cause,
        }
    }
}

/// A blocked dependency names either material or an Eval, never an unclassified string.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BlockedReference<'a> {
    Artifact(&'a ArtifactName),
    Eval(&'a EvalId),
}
impl BlockedReference<'_> {
    pub fn as_str(&self) -> &str {
        match self {
            Self::Artifact(id) => id.as_str(),
            Self::Eval(id) => id.as_str(),
        }
    }
}
impl std::fmt::Display for BlockedReference<'_> {
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        formatter.write_str(self.as_str())
    }
}

impl EvalStatus {
    pub fn passes_gate(self) -> bool {
        matches!(self, Self::Green | Self::Deferred | Self::Provisional)
    }
}

impl EvalEvaluation<'_> {
    /// Operational errors require an explicit retry, not automatic redispatch.
    pub fn can_execute(&self) -> bool {
        self.readiness == Readiness::Ready && matches!(self.evidence, None | Some(Evidence::Stale))
    }

    /// Names the failed evals that block this one, RED verdicts first; `None` unless BLOCKED.
    /// Each cause is final within a Run, but more can follow, so settlement saves it again.
    pub fn blocked_reason(&self) -> Option<String> {
        let names = |kind: fn(&Cause<'_>) -> bool| {
            self.causes
                .iter()
                .filter(|cause| kind(cause))
                .map(|cause| cause.eval().as_str())
                .collect::<Vec<_>>()
                .join(", ")
        };
        let parts: Vec<_> = [
            (
                "Sibling machine eval RED",
                names(|cause| matches!(cause, Cause::SiblingRed(_))),
            ),
            (
                "Sibling machine eval ERROR",
                names(|cause| matches!(cause, Cause::SiblingError(_))),
            ),
            (
                "Dependency verdict RED",
                names(|cause| matches!(cause, Cause::Red(_))),
            ),
            (
                "Dependency ERROR",
                names(|cause| matches!(cause, Cause::Error(_))),
            ),
        ]
        .into_iter()
        .filter(|(_, names)| !names.is_empty())
        .map(|(label, names)| format!("{label}: {names}"))
        .collect();
        (!parts.is_empty()).then(|| parts.join("; "))
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ArtifactStatus {
    Deferred,
    Provisional,
    Basis,
    Green,
    Incomplete,
    Error,
    Red,
    Blocked,
    Wait,
    Stale,
    Unreviewed,
}

impl From<ArtifactStatus> for crate::types::ArtifactValidationStatus {
    fn from(status: ArtifactStatus) -> Self {
        match status {
            ArtifactStatus::Deferred => Self::Deferred,
            ArtifactStatus::Provisional => Self::Provisional,
            ArtifactStatus::Basis => Self::Basis,
            ArtifactStatus::Green => Self::Green,
            ArtifactStatus::Incomplete => Self::Incomplete,
            ArtifactStatus::Error => Self::Error,
            ArtifactStatus::Red => Self::Red,
            ArtifactStatus::Blocked => Self::Blocked,
            ArtifactStatus::Wait => Self::Wait,
            ArtifactStatus::Stale => Self::Stale,
            ArtifactStatus::Unreviewed => Self::Unreviewed,
        }
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArtifactEvaluation {
    pub status: ArtifactStatus,
    pub own_satisfied: bool,
    /// Includes all required dependencies and SCC peers, even without Evals.
    pub satisfied: bool,
    pub passed: usize,
    pub total: usize,
}

/// Aggregate validation status, never a fabricated Eval verdict.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum FinalStatus {
    Green,
    Red,
    Error,
    Incomplete,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Evaluation<'a> {
    pub evals: BTreeMap<EvalId, EvalEvaluation<'a>>,
    pub artifacts: BTreeMap<ArtifactName, ArtifactEvaluation>,
    /// Artifacts whose own obligations are unmet, not execution gates.
    pub obligations: Vec<&'a ArtifactName>,
    pub status: FinalStatus,
}

#[cfg(test)]
mod tests;

impl serde::Serialize for BlockedReference<'_> {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        serializer.serialize_str(self.as_str())
    }
}

impl From<BlockedReference<'_>> for crate::store::Blocker {
    fn from(reference: BlockedReference<'_>) -> Self {
        match reference {
            BlockedReference::Artifact(id) => Self::Artifact(id.clone()),
            BlockedReference::Eval(id) => Self::Eval(id.clone()),
        }
    }
}

pub(crate) mod schedule;