tessellate-core 0.5.0

//! Versioned, deterministic runtime provenance for one decision evaluation.
//!
//! Unlike [`crate::policy_graph`], which describes declarations and their
//! structural relationships, this module records the concrete data flow of a
//! single evaluation.  Existing [`crate::engine::Evaluation`] JSON remains
//! unchanged; callers opt into this richer payload with
//! [`crate::engine::evaluate_with_provenance`].

use crate::engine::Evaluation;
use crate::source::{SourceFile, Span};
use crate::value::Value;
use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet};

/// Version of the serialized runtime provenance schema.
pub const PROVENANCE_SCHEMA_VERSION: u32 = 1;

/// A normal decision evaluation paired with its concrete provenance DAG.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct ProvenanceEvaluation {
    pub evaluation: Evaluation,
    pub provenance: ProvenanceGraph,
}

/// A stable, deterministically ordered directed acyclic graph.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct ProvenanceGraph {
    pub schema_version: u32,
    pub module: String,
    pub query: String,
    /// Identifier of the unique final [`ProvenanceNodeKind::DecisionResult`]
    /// node.
    pub result_node: String,
    pub nodes: Vec<ProvenanceNode>,
    pub edges: Vec<ProvenanceEdge>,
}

impl ProvenanceGraph {
    /// Look up a node by its stable identifier.
    #[must_use]
    pub fn node(&self, id: &str) -> Option<&ProvenanceNode> {
        self.nodes.iter().find(|node| node.id == id)
    }

    /// Iterate over direct causes of `id` in deterministic edge order.
    pub fn incoming<'a>(&'a self, id: &'a str) -> impl Iterator<Item = &'a ProvenanceEdge> + 'a {
        self.edges.iter().filter(move |edge| edge.to == id)
    }

    /// Iterate over direct consumers of `id` in deterministic edge order.
    pub fn outgoing<'a>(&'a self, id: &'a str) -> impl Iterator<Item = &'a ProvenanceEdge> + 'a {
        self.edges.iter().filter(move |edge| edge.from == id)
    }
}

/// One observed value or semantic step in an evaluation.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct ProvenanceNode {
    /// A kind-qualified identifier stable for the same program, input binding
    /// names, and query.
    pub id: String,
    pub kind: ProvenanceNodeKind,
    pub label: String,
    pub status: ProvenanceStatus,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub values: Vec<Value>,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub missing: Vec<String>,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub reasons: Vec<String>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub location: Option<ProvenanceLocation>,
}

/// The runtime construct represented by a provenance node.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum ProvenanceNodeKind {
    InputField,
    Literal,
    Name,
    FieldAccess,
    DeriveCall,
    BuiltinCall,
    UnaryOperation,
    BinaryOperation,
    RuleCondition,
    DecisionCandidate,
    Override,
    Suppression,
    DecisionResult,
}

/// The observed state of a node.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum ProvenanceStatus {
    Known,
    Entity,
    True,
    False,
    Unknown,
    Conflict,
    Applied,
    Blocked,
    Suppressed,
    Resolved,
    Undefined,
}

/// A directed data or semantic dependency. Edges point from cause to consumer.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct ProvenanceEdge {
    pub from: String,
    pub to: String,
    pub kind: ProvenanceEdgeKind,
}

/// Meaning of a provenance dependency.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum ProvenanceEdgeKind {
    /// A nested expression is an operand of another expression.
    Operand,
    /// A field access reads a concrete or missing input field.
    Reads,
    /// A function parameter receives the value of a call argument.
    Argument,
    /// An expression establishes a rule condition or candidate value.
    Evaluates,
    /// A true rule condition enables a candidate or override.
    Enables,
    /// A rule produces a decision candidate.
    Produces,
    /// An active override removes a candidate.
    Suppresses,
    /// A candidate, blocker, or suppression contributes to the result.
    Contributes,
}

/// Original source coordinates for an evaluated expression.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct ProvenanceLocation {
    pub file: String,
    pub line: usize,
    pub column: usize,
    pub end_line: usize,
    pub end_column: usize,
    pub expression: String,
}

#[derive(Clone, Debug)]
pub(crate) struct ProvenanceObservation {
    pub(crate) status: ProvenanceStatus,
    pub(crate) values: Vec<Value>,
    pub(crate) missing: Vec<String>,
    pub(crate) reasons: Vec<String>,
}

impl ProvenanceObservation {
    pub(crate) fn status(status: ProvenanceStatus) -> Self {
        Self {
            status,
            values: Vec::new(),
            missing: Vec::new(),
            reasons: Vec::new(),
        }
    }

    pub(crate) fn value(status: ProvenanceStatus, value: Value) -> Self {
        Self {
            status,
            values: vec![value],
            missing: Vec::new(),
            reasons: Vec::new(),
        }
    }
}

#[derive(Clone, Debug)]
struct ExpressionFrame {
    id: String,
    kind: ProvenanceNodeKind,
    label: String,
    span: Span,
    next_child: usize,
    dependencies: BTreeSet<(String, ProvenanceEdgeKind)>,
}

/// Internal recorder shared by nested function evaluation contexts.
#[derive(Clone, Debug)]
pub(crate) struct ProvenanceRecorder {
    source: SourceFile,
    module: String,
    query: String,
    scope: String,
    next_root: usize,
    frames: Vec<ExpressionFrame>,
    nodes: BTreeMap<String, ProvenanceNode>,
    edges: BTreeSet<ProvenanceEdge>,
    last_completed: Option<String>,
}

impl ProvenanceRecorder {
    pub(crate) fn new(source: SourceFile, module: String, query: String) -> Self {
        Self {
            source,
            module,
            query,
            scope: String::new(),
            next_root: 0,
            frames: Vec::new(),
            nodes: BTreeMap::new(),
            edges: BTreeSet::new(),
            last_completed: None,
        }
    }

    pub(crate) fn set_scope(&mut self, scope: impl Into<String>) {
        debug_assert!(self.frames.is_empty());
        self.scope = scope.into();
        self.next_root = 0;
        self.last_completed = None;
    }

    pub(crate) fn begin_expression(&mut self, kind: ProvenanceNodeKind, label: String, span: Span) {
        let id = if let Some(parent) = self.frames.last_mut() {
            let child = parent.next_child;
            parent.next_child += 1;
            format!("{}/expression:{child}", parent.id)
        } else {
            let root = self.next_root;
            self.next_root += 1;
            if root == 0 {
                format!("expression:{}", self.scope)
            } else {
                format!("expression:{}/root:{root}", self.scope)
            }
        };
        self.frames.push(ExpressionFrame {
            id,
            kind,
            label,
            span,
            next_child: 0,
            dependencies: BTreeSet::new(),
        });
    }

    pub(crate) fn finish_expression(&mut self, observation: ProvenanceObservation) {
        let frame = self
            .frames
            .pop()
            .expect("a provenance expression frame must be active");
        let id = frame.id.clone();
        self.insert_node(ProvenanceNode {
            id: id.clone(),
            kind: frame.kind,
            label: frame.label,
            status: observation.status,
            values: observation.values,
            missing: sorted_unique(observation.missing),
            reasons: sorted_unique(observation.reasons),
            location: Some(self.location(frame.span)),
        });
        for (dependency, kind) in frame.dependencies {
            self.connect(dependency, id.clone(), kind);
        }
        if let Some(parent) = self.frames.last_mut() {
            parent
                .dependencies
                .insert((id.clone(), ProvenanceEdgeKind::Operand));
        }
        self.last_completed = Some(id);
    }

    pub(crate) fn record_dependency(&mut self, from: String, kind: ProvenanceEdgeKind) {
        if let Some(frame) = self.frames.last_mut() {
            frame.dependencies.insert((from, kind));
        }
    }

    pub(crate) fn record_input(
        &mut self,
        binding: &str,
        field: &str,
        observation: ProvenanceObservation,
    ) -> String {
        let path = format!("{binding}.{field}");
        let id = format!("input:{path}");
        self.insert_node(ProvenanceNode {
            id: id.clone(),
            kind: ProvenanceNodeKind::InputField,
            label: path,
            status: observation.status,
            values: observation.values,
            missing: sorted_unique(observation.missing),
            reasons: sorted_unique(observation.reasons),
            location: None,
        });
        self.record_dependency(id.clone(), ProvenanceEdgeKind::Reads);
        id
    }

    pub(crate) fn record_node(
        &mut self,
        id: impl Into<String>,
        kind: ProvenanceNodeKind,
        label: impl Into<String>,
        observation: ProvenanceObservation,
    ) -> String {
        let id = id.into();
        self.insert_node(ProvenanceNode {
            id: id.clone(),
            kind,
            label: label.into(),
            status: observation.status,
            values: observation.values,
            missing: sorted_unique(observation.missing),
            reasons: sorted_unique(observation.reasons),
            location: None,
        });
        id
    }

    pub(crate) fn connect(
        &mut self,
        from: impl Into<String>,
        to: impl Into<String>,
        kind: ProvenanceEdgeKind,
    ) {
        self.edges.insert(ProvenanceEdge {
            from: from.into(),
            to: to.into(),
            kind,
        });
    }

    pub(crate) fn last_completed(&self) -> Option<String> {
        self.last_completed.clone()
    }

    pub(crate) fn finish(self, result_node: String) -> ProvenanceGraph {
        debug_assert!(self.frames.is_empty());
        ProvenanceGraph {
            schema_version: PROVENANCE_SCHEMA_VERSION,
            module: self.module,
            query: self.query,
            result_node,
            nodes: self.nodes.into_values().collect(),
            edges: self.edges.into_iter().collect(),
        }
    }

    fn insert_node(&mut self, node: ProvenanceNode) {
        match self.nodes.get(&node.id) {
            Some(existing) => debug_assert_eq!(existing, &node),
            None => {
                self.nodes.insert(node.id.clone(), node);
            }
        }
    }

    fn location(&self, span: Span) -> ProvenanceLocation {
        let (line, column) = self.source.line_col(span.start);
        let (end_line, end_column) = self.source.line_col(span.end);
        ProvenanceLocation {
            file: self.source.name_at(span.start).to_owned(),
            line,
            column,
            end_line,
            end_column,
            expression: self
                .source
                .text
                .get(span.start..span.end)
                .unwrap_or_default()
                .trim()
                .to_owned(),
        }
    }
}

fn sorted_unique(values: Vec<String>) -> Vec<String> {
    values
        .into_iter()
        .collect::<BTreeSet<_>>()
        .into_iter()
        .collect()
}