tessellate-core 0.3.0

use crate::ast::{
    BinaryOp, Cardinality, CaseDecl, Effect, Expr, ExprKind, Literal, NumericLiteral, RuleDecl,
    TypeRef, UnaryOp,
};
use crate::compiler::{CompiledProgram, ValueType, display_symbol_name, normalize_name};
use crate::diagnostic::Diagnostic;
use crate::provenance::{
    ProvenanceEdgeKind, ProvenanceEvaluation, ProvenanceNodeKind, ProvenanceObservation,
    ProvenanceRecorder, ProvenanceStatus,
};
use crate::source::Span;
use crate::value::{
    TruthValue, Value, checked_decimal_add, checked_decimal_div, checked_decimal_mul,
    checked_decimal_sub, parse_decimal,
};
use chrono::NaiveDate;
use rust_decimal::Decimal;
use serde::{Deserialize, Serialize};
use std::cell::RefCell;
use std::collections::{BTreeMap, BTreeSet};
use std::fmt::Write;
use std::rc::Rc;
use std::time::Instant;

/// A named record instance supplied to the evaluator.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct EntityInput {
    pub entity: String,
    pub fields: BTreeMap<String, Value>,
}

/// All record bindings available to one evaluation.
#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct Input {
    pub bindings: BTreeMap<String, EntityInput>,
}

impl Input {
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    pub fn insert(
        &mut self,
        name: impl Into<String>,
        entity: impl Into<String>,
        fields: BTreeMap<String, Value>,
    ) {
        let fields = fields
            .into_iter()
            .map(|(name, value)| (normalize_name(&name), normalized_value(value)))
            .collect();
        self.bindings.insert(
            normalize_name(&name.into()),
            EntityInput {
                entity: normalize_name(&entity.into()),
                fields,
            },
        );
    }

    /// Validate every provided field against the compiled record schema.
    ///
    /// Missing fields are intentionally accepted as partial, open-world input.
    /// A missing value becomes `unknown` only when evaluation needs it.
    #[must_use]
    pub fn validate(&self, program: &CompiledProgram) -> Vec<Diagnostic> {
        let mut diagnostics = Vec::new();
        for (binding_name, binding) in &self.bindings {
            let Some(entity) = find_entity(program, &binding.entity) else {
                diagnostics.push(Diagnostic::error(
                    "E1211",
                    format!(
                        "input binding `{binding_name}` has unknown record type `{}`",
                        binding.entity
                    ),
                    Span::default(),
                ));
                continue;
            };
            for (field_name, value) in &binding.fields {
                let Some(field) = entity
                    .fields
                    .iter()
                    .find(|field| normalize_name(&field.name.value) == normalize_name(field_name))
                else {
                    diagnostics.push(Diagnostic::error(
                        "E1212",
                        format!("input binding `{binding_name}` has unknown field `{field_name}`"),
                        Span::default(),
                    ));
                    continue;
                };
                if let Err(message) = validate_field_value(program, field, value) {
                    diagnostics.push(Diagnostic::error(
                        "E1213",
                        format!("invalid `{binding_name}.{field_name}`: {message}"),
                        Span::default(),
                    ));
                }
            }
        }
        diagnostics
            .sort_by(|left, right| (&left.code, &left.message).cmp(&(&right.code, &right.message)));
        diagnostics
    }

    /// Build runtime input from a declared `test`.
    ///
    /// # Errors
    ///
    /// Returns source diagnostics when the test references an unknown record or
    /// field, or when a field initializer is not a valid constant value.
    pub fn from_case(program: &CompiledProgram, case: &CaseDecl) -> Result<Self, Vec<Diagnostic>> {
        let mut input = Self::new();
        let mut diagnostics = Vec::new();

        for binding in &case.bindings {
            let Some(entity) = find_entity(program, &binding.entity.value) else {
                diagnostics.push(Diagnostic::error(
                    "E1201",
                    format!("unknown record `{}`", binding.entity.value),
                    binding.entity.span,
                ));
                continue;
            };
            let mut fields = BTreeMap::new();
            for field_value in &binding.fields {
                let Some(field) = entity
                    .fields
                    .iter()
                    .find(|field| field.name.value == field_value.name.value)
                else {
                    diagnostics.push(Diagnostic::error(
                        "E1202",
                        format!("unknown field `{}`", field_value.name.value),
                        field_value.name.span,
                    ));
                    continue;
                };
                if matches!(field_value.value.kind, ExprKind::Literal(Literal::Unknown)) {
                    continue;
                }
                match constant_value(program, &field_value.value, Some(&field.ty)) {
                    Ok(value) => {
                        fields.insert(field.name.value.clone(), value);
                    }
                    Err(message) => diagnostics.push(Diagnostic::error(
                        "E1203",
                        message,
                        field_value.value.span,
                    )),
                }
            }
            input.insert(
                binding.name.value.clone(),
                binding.entity.value.clone(),
                fields,
            );
        }

        if diagnostics.is_empty() {
            Ok(input)
        } else {
            Err(diagnostics)
        }
    }

    /// Decode either a single-record object or an object keyed by query argument.
    ///
    /// # Errors
    ///
    /// Returns diagnostics when the JSON shape or a value does not match the
    /// record schema required by the query.
    pub fn from_json(
        program: &CompiledProgram,
        query: &Query,
        json: &serde_json::Value,
    ) -> Result<Self, Vec<Diagnostic>> {
        let Some(decision) = find_decision(program, &query.decision) else {
            return Err(vec![Diagnostic::error(
                "E1204",
                format!("unknown decision `{}`", query.decision),
                Span::default(),
            )]);
        };
        if decision.parameters.len() != query.arguments.len() {
            return Err(vec![Diagnostic::error(
                "E1205",
                format!(
                    "decision `{}` expects {} argument(s), but {} were supplied",
                    query.decision,
                    decision.parameters.len(),
                    query.arguments.len()
                ),
                Span::default(),
            )]);
        }
        let Some(root) = json.as_object() else {
            return Err(vec![Diagnostic::error(
                "E1206",
                "JSON input must be an object",
                Span::default(),
            )]);
        };

        let nested = query.arguments.len() > 1
            || query.arguments.first().is_some_and(|argument| {
                root.iter()
                    .any(|(name, value)| normalize_name(name) == *argument && value.is_object())
            });
        let mut input = Self::new();
        let mut diagnostics = Vec::new();

        for (index, (argument, parameter)) in
            query.arguments.iter().zip(&decision.parameters).enumerate()
        {
            let object = if nested {
                root.iter()
                    .find(|(name, _)| normalize_name(name) == *argument)
                    .and_then(|(_, value)| value.as_object())
            } else if index == 0 {
                Some(root)
            } else {
                None
            };
            let Some(object) = object else {
                diagnostics.push(Diagnostic::error(
                    "E1207",
                    format!("missing JSON object for query argument `{argument}`"),
                    Span::default(),
                ));
                continue;
            };
            let entity_name = &parameter.ty.value;
            let Some(entity) = find_entity(program, entity_name) else {
                diagnostics.push(Diagnostic::error(
                    "E1208",
                    format!("`{entity_name}` is not a record type"),
                    parameter.ty.span,
                ));
                continue;
            };
            let mut fields = BTreeMap::new();
            for (name, value) in object {
                if name == "$type" {
                    continue;
                }
                let normalized_name = normalize_name(name);
                let Some(field) = entity
                    .fields
                    .iter()
                    .find(|field| normalize_name(&field.name.value) == normalized_name)
                else {
                    diagnostics.push(Diagnostic::error(
                        "E1209",
                        format!("unknown field `{name}` on record `{entity_name}`"),
                        Span::default(),
                    ));
                    continue;
                };
                match json_value(program, value, &field.ty)
                    .and_then(|value| validate_field_value(program, field, &value).map(|()| value))
                {
                    Ok(value) => {
                        fields.insert(field.name.value.clone(), value);
                    }
                    Err(message) => diagnostics.push(Diagnostic::error(
                        "E1210",
                        format!("invalid value for `{name}`: {message}"),
                        Span::default(),
                    )),
                }
            }
            input.insert(argument.clone(), entity_name.clone(), fields);
        }

        if diagnostics.is_empty() {
            Ok(input)
        } else {
            Err(diagnostics)
        }
    }
}

/// A parsed decision query such as `최종등급(s)`.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Query {
    pub decision: String,
    pub arguments: Vec<String>,
}

impl Query {
    /// Parse a textual decision query.
    ///
    /// # Errors
    ///
    /// Returns a message when the query is not in `decision(binding, ...)` form.
    pub fn parse(text: &str) -> Result<Self, String> {
        let text = text.trim();
        let Some(open) = text.find('(') else {
            return Err("a query must have the form decision(binding)".into());
        };
        let Some(close) = text.rfind(')') else {
            return Err("a query is missing `)`".into());
        };
        if close != text.len() - 1 {
            return Err("unexpected text after query `)`".into());
        }
        let decision = text[..open].trim();
        if decision.is_empty() {
            return Err("a query is missing its decision name".into());
        }
        let body = &text[open + 1..close];
        let arguments = if body.trim().is_empty() {
            Vec::new()
        } else {
            body.split(',')
                .map(str::trim)
                .map(|value| {
                    if value.is_empty() {
                        Err("a query contains an empty argument".to_owned())
                    } else {
                        Ok(normalize_name(value))
                    }
                })
                .collect::<Result<Vec<_>, _>>()?
        };
        Ok(Self {
            decision: normalize_name(decision),
            arguments,
        })
    }

    #[must_use]
    pub fn render(&self) -> String {
        format!("{}({})", self.decision, self.arguments.join(", "))
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(tag = "status", rename_all = "snake_case")]
pub enum DecisionStatus {
    Resolved {
        values: Vec<Value>,
    },
    Undefined,
    Unknown {
        missing: Vec<String>,
    },
    Conflict {
        values: Vec<Value>,
        reasons: Vec<String>,
    },
}

impl DecisionStatus {
    #[must_use]
    pub fn single_value(&self) -> Option<&Value> {
        match self {
            Self::Resolved { values } if values.len() == 1 => values.first(),
            _ => None,
        }
    }

    #[must_use]
    pub const fn is_resolved(&self) -> bool {
        matches!(self, Self::Resolved { .. })
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
/// One ordered fragment basis item carried into runtime explanations.
pub struct FragmentEvidence {
    /// Stable Tess fragment ID.
    pub id: String,
    /// Opaque native-document locator.
    pub locator: String,
    /// Exact fragment source text.
    pub text: String,
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Candidate {
    pub rule: String,
    pub value: Value,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub basis: Vec<FragmentEvidence>,
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum SuppressionReason {
    ExplicitOverride { by: String },
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct SuppressedCandidate {
    pub candidate: Candidate,
    pub reason: SuppressionReason,
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum RuleOutcome {
    Applied,
    Skipped,
    Blocked,
    Conflicted,
    OverrideApplied,
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct RuleTrace {
    pub rule: String,
    pub condition_expression: String,
    pub condition: TruthValue,
    pub outcome: RuleOutcome,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub missing: Vec<String>,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub basis: Vec<FragmentEvidence>,
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct DecisionResult {
    pub decision: String,
    pub cardinality: Cardinality,
    pub status: DecisionStatus,
    pub candidates: Vec<Candidate>,
    pub suppressed: Vec<SuppressedCandidate>,
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Evaluation {
    pub query: String,
    pub result: DecisionResult,
    pub rules: Vec<RuleTrace>,
}

impl Evaluation {
    #[must_use]
    pub fn render_text(&self) -> String {
        let mut out = String::new();
        match &self.result.status {
            DecisionStatus::Resolved { values } => {
                let rendered = values
                    .iter()
                    .map(ToString::to_string)
                    .collect::<Vec<_>>()
                    .join(", ");
                let _ = writeln!(out, "{} = {rendered}", self.query);
            }
            DecisionStatus::Undefined => {
                let _ = writeln!(out, "{} = undefined", self.query);
            }
            DecisionStatus::Unknown { missing } => {
                let _ = writeln!(out, "{} = unknown", self.query);
                if !missing.is_empty() {
                    let _ = writeln!(out, "missing: {}", missing.join(", "));
                }
            }
            DecisionStatus::Conflict { values, reasons } => {
                let rendered = values
                    .iter()
                    .map(ToString::to_string)
                    .collect::<Vec<_>>()
                    .join(", ");
                let _ = writeln!(out, "{} = conflict [{rendered}]", self.query);
                for reason in reasons {
                    let _ = writeln!(out, "  reason: {reason}");
                }
            }
        }
        out
    }

    #[must_use]
    pub fn explain_text(&self) -> String {
        let mut out = self.render_text();
        out.push_str("\nrules:\n");
        for trace in &self.rules {
            let basis = if trace.basis.is_empty() {
                String::new()
            } else {
                format!(" [{}]", render_basis_text(&trace.basis))
            };
            let outcome = match &trace.outcome {
                RuleOutcome::Applied => "applied",
                RuleOutcome::Skipped => "skipped",
                RuleOutcome::Blocked => "blocked",
                RuleOutcome::Conflicted => "conflicted",
                RuleOutcome::OverrideApplied => "override_applied",
            };
            let _ = writeln!(
                out,
                "  - {}: {} -> {}{}",
                trace.rule, trace.condition, outcome, basis
            );
            if !trace.missing.is_empty() {
                let _ = writeln!(out, "    missing: {}", trace.missing.join(", "));
            }
            if trace.condition != TruthValue::True {
                let _ = writeln!(out, "    condition: {}", trace.condition_expression);
            }
        }
        if !self.result.candidates.is_empty() {
            out.push_str("candidates:\n");
            for candidate in &self.result.candidates {
                let _ = writeln!(
                    out,
                    "  - {} = {} by {}",
                    self.result.decision, candidate.value, candidate.rule
                );
            }
            let mut by_value: BTreeMap<&Value, Vec<&str>> = BTreeMap::new();
            for candidate in &self.result.candidates {
                by_value
                    .entry(&candidate.value)
                    .or_default()
                    .push(&candidate.rule);
            }
            for (value, rules) in by_value {
                if rules.len() > 1 {
                    let _ = writeln!(out, "  merged {value}: {}", rules.join(", "));
                }
            }
        }
        if !self.result.suppressed.is_empty() {
            out.push_str("suppressed:\n");
            for suppressed in &self.result.suppressed {
                let reason = match &suppressed.reason {
                    SuppressionReason::ExplicitOverride { by } => {
                        format!("explicitly overridden by {by}")
                    }
                };
                let _ = writeln!(
                    out,
                    "  - {} from {}: {reason}",
                    suppressed.candidate.value, suppressed.candidate.rule
                );
            }
        }
        out
    }
}

/// Selects the human or machine explanation representation.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ExplainFormat {
    Text,
    Json,
}

#[derive(Clone, Debug)]
enum RuntimeValue {
    Known(Value),
    Entity(String),
    Unknown(BTreeSet<String>),
    Conflict(Vec<String>),
}

impl RuntimeValue {
    fn missing(path: impl Into<String>) -> Self {
        Self::Unknown(BTreeSet::from([path.into()]))
    }

    fn truth(&self) -> RuntimeTruth {
        match self {
            Self::Known(Value::Bool(true)) => RuntimeTruth::True,
            Self::Known(Value::Bool(false)) => RuntimeTruth::False,
            Self::Known(_) | Self::Entity(_) => {
                RuntimeTruth::Conflict(vec!["condition did not evaluate to Bool".into()])
            }
            Self::Unknown(missing) => RuntimeTruth::Unknown(missing.clone()),
            Self::Conflict(reasons) => RuntimeTruth::Conflict(reasons.clone()),
        }
    }
}

#[derive(Clone, Debug)]
enum RuntimeTruth {
    True,
    False,
    Unknown(BTreeSet<String>),
    Conflict(Vec<String>),
}

impl RuntimeTruth {
    fn into_value(self) -> RuntimeValue {
        match self {
            Self::True => RuntimeValue::Known(Value::Bool(true)),
            Self::False => RuntimeValue::Known(Value::Bool(false)),
            Self::Unknown(missing) => RuntimeValue::Unknown(missing),
            Self::Conflict(reasons) => RuntimeValue::Conflict(reasons),
        }
    }
}

struct EvalContext<'a> {
    program: &'a CompiledProgram,
    input: &'a Input,
    variables: BTreeMap<String, RuntimeValue>,
    variable_origins: BTreeMap<String, String>,
    derive_stack: Vec<String>,
    provenance: Option<Rc<RefCell<ProvenanceRecorder>>>,
}

impl EvalContext<'_> {
    fn child(&self) -> Self {
        Self {
            program: self.program,
            input: self.input,
            variables: self.variables.clone(),
            variable_origins: self.variable_origins.clone(),
            derive_stack: self.derive_stack.clone(),
            provenance: self.provenance.clone(),
        }
    }

    fn eval(&mut self, expression: &Expr, expected: Option<&TypeRef>) -> RuntimeValue {
        if let Some(provenance) = &self.provenance {
            let (kind, label) = provenance_expression(self.program, expression);
            provenance
                .borrow_mut()
                .begin_expression(kind, label, expression.span);
        }
        let inferred = expected.cloned().or_else(|| {
            self.program
                .type_of_span(expression.span)
                .and_then(type_ref_from_value_type)
        });
        let expected = inferred.as_ref();
        let result = match &expression.kind {
            ExprKind::Literal(literal) => match literal {
                Literal::Bool(value) => RuntimeValue::Known(Value::Bool(*value)),
                Literal::Number(NumericLiteral::Int(value)) => {
                    if matches!(expected, Some(TypeRef::Decimal)) {
                        RuntimeValue::Known(Value::decimal(Decimal::from(*value)))
                    } else {
                        RuntimeValue::Known(Value::Int(*value))
                    }
                }
                Literal::Number(NumericLiteral::Decimal(value)) => {
                    parse_decimal(value).map(Value::decimal).map_or_else(
                        |error| RuntimeValue::Conflict(vec![error.to_string()]),
                        RuntimeValue::Known,
                    )
                }
                Literal::String(value) => RuntimeValue::Known(Value::String(value.clone())),
                Literal::Unknown => RuntimeValue::missing("explicit unknown"),
            },
            ExprKind::Name(name) => self.eval_name(name, expected),
            ExprKind::Field { receiver, field } => match self.eval(receiver, None) {
                RuntimeValue::Entity(binding) => {
                    let result = self
                        .input
                        .bindings
                        .get(&binding)
                        .and_then(|entity| entity.fields.get(&field.value))
                        .cloned()
                        .map_or_else(
                            || RuntimeValue::missing(format!("{binding}.{}", field.value)),
                            RuntimeValue::Known,
                        );
                    if let Some(provenance) = &self.provenance {
                        provenance.borrow_mut().record_input(
                            &binding,
                            &field.value,
                            provenance_observation(&result),
                        );
                    }
                    result
                }
                RuntimeValue::Unknown(missing) => RuntimeValue::Unknown(missing),
                RuntimeValue::Conflict(reasons) => RuntimeValue::Conflict(reasons),
                RuntimeValue::Known(_) => RuntimeValue::Conflict(vec![format!(
                    "field `{}` was accessed on a non-record value",
                    field.value
                )]),
            },
            ExprKind::Call { callee, arguments } => {
                self.eval_call(&callee.value, arguments, expected)
            }
            ExprKind::Unary { operator, operand } => {
                let value = self.eval(operand, None);
                match operator {
                    UnaryOp::Not => match value.truth() {
                        RuntimeTruth::True => RuntimeTruth::False.into_value(),
                        RuntimeTruth::False => RuntimeTruth::True.into_value(),
                        RuntimeTruth::Unknown(missing) => RuntimeValue::Unknown(missing),
                        RuntimeTruth::Conflict(reasons) => RuntimeValue::Conflict(reasons),
                    },
                    UnaryOp::Negate => negate(value),
                }
            }
            ExprKind::Binary {
                left,
                operator,
                right,
            } => self.eval_binary(left, *operator, right),
        };
        let result = coerce_runtime_value(result, expected);
        if let Some(provenance) = &self.provenance {
            provenance
                .borrow_mut()
                .finish_expression(provenance_observation(&result));
        }
        result
    }

    fn eval_name(&self, name: &str, expected: Option<&TypeRef>) -> RuntimeValue {
        if let Some(value) = self.variables.get(name) {
            if let (Some(provenance), Some(origin)) =
                (&self.provenance, self.variable_origins.get(name))
            {
                provenance
                    .borrow_mut()
                    .record_dependency(origin.clone(), ProvenanceEdgeKind::Argument);
            }
            return value.clone();
        }
        if matches!(expected, Some(TypeRef::Bool)) {
            if name == "true" {
                return RuntimeValue::Known(Value::Bool(true));
            }
            if name == "false" {
                return RuntimeValue::Known(Value::Bool(false));
            }
        }
        if let Some(TypeRef::Named(enum_name)) = expected {
            if enum_contains(self.program, enum_name, name) {
                return RuntimeValue::Known(Value::Enum {
                    type_name: enum_name.clone(),
                    variant: name.to_owned(),
                });
            }
        }
        let matching = enum_variants(self.program, name);
        if matching.len() == 1 {
            return RuntimeValue::Known(Value::Enum {
                type_name: matching[0].clone(),
                variant: name.to_owned(),
            });
        }
        RuntimeValue::Conflict(vec![format!("unresolved name `{name}`")])
    }

    fn eval_call(
        &mut self,
        callee: &str,
        arguments: &[Expr],
        expected: Option<&TypeRef>,
    ) -> RuntimeValue {
        match callee {
            "max" | "min" => {
                if arguments.len() != 2 {
                    return RuntimeValue::Conflict(vec![format!(
                        "`{callee}` expects two arguments"
                    )]);
                }
                let left = self.eval(&arguments[0], expected);
                let right = self.eval(&arguments[1], expected);
                min_max(left, right, callee == "max")
            }
            "abs" => {
                if arguments.len() != 1 {
                    return RuntimeValue::Conflict(vec!["`abs` expects one argument".into()]);
                }
                absolute(self.eval(&arguments[0], expected))
            }
            "date" => {
                if arguments.len() != 1 {
                    return RuntimeValue::Conflict(vec!["`date` expects one argument".into()]);
                }
                match self.eval(&arguments[0], Some(&TypeRef::String)) {
                    RuntimeValue::Known(Value::String(value)) => {
                        match NaiveDate::parse_from_str(&value, "%Y-%m-%d") {
                            Ok(value) => RuntimeValue::Known(Value::Date(value)),
                            Err(error) => RuntimeValue::Conflict(vec![error.to_string()]),
                        }
                    }
                    value => propagate_or_conflict(value, "`date` expects a String"),
                }
            }
            "days" | "hours" | "minutes" => {
                if arguments.len() != 1 {
                    return RuntimeValue::Conflict(vec![format!(
                        "`{callee}` expects one argument"
                    )]);
                }
                match self.eval(&arguments[0], Some(&TypeRef::Int)) {
                    RuntimeValue::Known(Value::Int(value)) => {
                        let factor = match callee {
                            "days" => 86_400,
                            "hours" => 3_600,
                            _ => 60,
                        };
                        value.checked_mul(factor).map_or_else(
                            || RuntimeValue::Conflict(vec!["duration overflow".into()]),
                            |seconds| RuntimeValue::Known(Value::Duration(seconds)),
                        )
                    }
                    value => propagate_or_conflict(value, "duration constructor expects an Int"),
                }
            }
            _ => {
                let Some(derive) = find_derive(self.program, callee) else {
                    return RuntimeValue::Conflict(vec![format!("unknown function `{callee}`")]);
                };
                if self.derive_stack.iter().any(|name| name == callee) {
                    return RuntimeValue::Conflict(vec![format!(
                        "cyclic fn evaluation involving `{callee}`"
                    )]);
                }
                if derive.parameters.len() != arguments.len() {
                    return RuntimeValue::Conflict(vec![format!(
                        "fn `{callee}` expects {} argument(s)",
                        derive.parameters.len()
                    )]);
                }
                let mut child = self.child();
                child.derive_stack.push(callee.to_owned());
                for (parameter, argument) in derive.parameters.iter().zip(arguments) {
                    let value = self.eval(argument, None);
                    if let Some(origin) = self
                        .provenance
                        .as_ref()
                        .and_then(|provenance| provenance.borrow().last_completed())
                    {
                        child
                            .variable_origins
                            .insert(parameter.name.value.clone(), origin);
                    }
                    match value {
                        RuntimeValue::Entity(binding) => {
                            child.variables.insert(
                                parameter.name.value.clone(),
                                RuntimeValue::Entity(binding),
                            );
                        }
                        RuntimeValue::Known(value) => {
                            child
                                .variables
                                .insert(parameter.name.value.clone(), RuntimeValue::Known(value));
                        }
                        RuntimeValue::Unknown(missing) => return RuntimeValue::Unknown(missing),
                        RuntimeValue::Conflict(reasons) => return RuntimeValue::Conflict(reasons),
                    }
                }
                child.eval(&derive.expression, Some(&derive.return_type.value))
            }
        }
    }

    fn eval_binary(&mut self, left: &Expr, operator: BinaryOp, right: &Expr) -> RuntimeValue {
        if operator == BinaryOp::And {
            let left = self.eval(left, Some(&TypeRef::Bool)).truth();
            if matches!(left, RuntimeTruth::False) {
                return RuntimeValue::Known(Value::Bool(false));
            }
            let right = self.eval(right, Some(&TypeRef::Bool)).truth();
            return truth_and(left, right).into_value();
        }
        if operator == BinaryOp::Or {
            let left = self.eval(left, Some(&TypeRef::Bool)).truth();
            if matches!(left, RuntimeTruth::True) {
                return RuntimeValue::Known(Value::Bool(true));
            }
            let right = self.eval(right, Some(&TypeRef::Bool)).truth();
            return truth_or(left, right).into_value();
        }
        let left = self.eval(left, None);
        let right = self.eval(right, None);
        match operator {
            BinaryOp::Equal
            | BinaryOp::NotEqual
            | BinaryOp::Greater
            | BinaryOp::GreaterEqual
            | BinaryOp::Less
            | BinaryOp::LessEqual => compare(left, right, operator),
            BinaryOp::Add | BinaryOp::Subtract | BinaryOp::Multiply | BinaryOp::Divide => {
                arithmetic(left, right, operator)
            }
            BinaryOp::And | BinaryOp::Or => unreachable!("logical operators handled above"),
        }
    }
}

fn provenance_expression(
    program: &CompiledProgram,
    expression: &Expr,
) -> (ProvenanceNodeKind, String) {
    match &expression.kind {
        ExprKind::Literal(_) => (ProvenanceNodeKind::Literal, "literal".into()),
        ExprKind::Name(name) => (ProvenanceNodeKind::Name, name.clone()),
        ExprKind::Field { field, .. } => {
            (ProvenanceNodeKind::FieldAccess, format!(".{}", field.value))
        }
        ExprKind::Call { callee, .. } => (
            if program.derive(&callee.value).is_some() {
                ProvenanceNodeKind::DeriveCall
            } else {
                ProvenanceNodeKind::BuiltinCall
            },
            callee.value.clone(),
        ),
        ExprKind::Unary { operator, .. } => (
            ProvenanceNodeKind::UnaryOperation,
            match operator {
                UnaryOp::Not => "not",
                UnaryOp::Negate => "-",
            }
            .into(),
        ),
        ExprKind::Binary { operator, .. } => (
            ProvenanceNodeKind::BinaryOperation,
            match operator {
                BinaryOp::Or => "or",
                BinaryOp::And => "and",
                BinaryOp::Equal => "==",
                BinaryOp::NotEqual => "!=",
                BinaryOp::Greater => ">",
                BinaryOp::GreaterEqual => ">=",
                BinaryOp::Less => "<",
                BinaryOp::LessEqual => "<=",
                BinaryOp::Add => "+",
                BinaryOp::Subtract => "-",
                BinaryOp::Multiply => "*",
                BinaryOp::Divide => "/",
            }
            .into(),
        ),
    }
}

fn provenance_observation(value: &RuntimeValue) -> ProvenanceObservation {
    match value {
        RuntimeValue::Known(value) => {
            ProvenanceObservation::value(ProvenanceStatus::Known, value.clone())
        }
        RuntimeValue::Entity(_) => ProvenanceObservation::status(ProvenanceStatus::Entity),
        RuntimeValue::Unknown(missing) => ProvenanceObservation {
            status: ProvenanceStatus::Unknown,
            values: Vec::new(),
            missing: missing.iter().cloned().collect(),
            reasons: Vec::new(),
        },
        RuntimeValue::Conflict(reasons) => ProvenanceObservation {
            status: ProvenanceStatus::Conflict,
            values: Vec::new(),
            missing: Vec::new(),
            reasons: reasons.clone(),
        },
    }
}

fn provenance_truth_observation(value: &RuntimeTruth) -> ProvenanceObservation {
    match value {
        RuntimeTruth::True => {
            ProvenanceObservation::value(ProvenanceStatus::True, Value::Bool(true))
        }
        RuntimeTruth::False => {
            ProvenanceObservation::value(ProvenanceStatus::False, Value::Bool(false))
        }
        RuntimeTruth::Unknown(missing) => ProvenanceObservation {
            status: ProvenanceStatus::Unknown,
            values: Vec::new(),
            missing: missing.iter().cloned().collect(),
            reasons: Vec::new(),
        },
        RuntimeTruth::Conflict(reasons) => ProvenanceObservation {
            status: ProvenanceStatus::Conflict,
            values: Vec::new(),
            missing: Vec::new(),
            reasons: reasons.clone(),
        },
    }
}

fn provenance_decision_observation(status: &DecisionStatus) -> ProvenanceObservation {
    match status {
        DecisionStatus::Resolved { values } => ProvenanceObservation {
            status: ProvenanceStatus::Resolved,
            values: values.clone(),
            missing: Vec::new(),
            reasons: Vec::new(),
        },
        DecisionStatus::Undefined => ProvenanceObservation::status(ProvenanceStatus::Undefined),
        DecisionStatus::Unknown { missing } => ProvenanceObservation {
            status: ProvenanceStatus::Unknown,
            values: Vec::new(),
            missing: missing.clone(),
            reasons: Vec::new(),
        },
        DecisionStatus::Conflict { values, reasons } => ProvenanceObservation {
            status: ProvenanceStatus::Conflict,
            values: values.clone(),
            missing: Vec::new(),
            reasons: reasons.clone(),
        },
    }
}

fn provenance_candidate_id(rule: &str, value_start: usize) -> String {
    format!("candidate:{}:{value_start}", display_symbol_name(rule))
}

fn provenance_override_id(rule: &str, target: &str) -> String {
    format!(
        "override:{}:{}",
        display_symbol_name(rule),
        display_symbol_name(target)
    )
}

fn provenance_result_id(query: &Query) -> String {
    format!("decision:{}", query.render())
}

#[derive(Clone, Debug)]
struct PendingCandidate {
    candidate: Candidate,
    provenance: Vec<String>,
}

#[derive(Clone, Debug)]
struct Blocker {
    rule: String,
    missing: BTreeSet<String>,
    reasons: Vec<String>,
    conflict: bool,
    provenance: Option<String>,
}

#[derive(Clone, Debug)]
struct UncertainOverride {
    rule: String,
    targets: BTreeSet<String>,
    missing: BTreeSet<String>,
    provenance: Option<String>,
}

fn collect_fragment_evidence(
    program: &CompiledProgram,
    basis: &[crate::ast::FragmentRef],
) -> Vec<FragmentEvidence> {
    basis
        .iter()
        .filter_map(|reference| program.fragment(&reference.id.value))
        .map(|fragment| FragmentEvidence {
            id: display_symbol_name(&fragment.id.value),
            locator: fragment.locator.value.clone(),
            text: fragment.text.value.clone(),
        })
        .collect()
}

#[must_use]
pub fn render_basis_text(basis: &[FragmentEvidence]) -> String {
    basis
        .iter()
        .map(|fragment| fragment.text.trim_end_matches('\n'))
        .collect::<Vec<_>>()
        .join("\n\n")
}

/// Evaluate one decision query against concrete input.
///
/// # Errors
///
/// Returns a diagnostic when the textual query is malformed or cannot be
/// resolved against the compiled program and input bindings.
pub fn evaluate(
    program: &CompiledProgram,
    input: &Input,
    query_text: &str,
) -> Result<Evaluation, Diagnostic> {
    let query = Query::parse(query_text)
        .map_err(|message| Diagnostic::error("E1301", message, Span::default()))?;
    evaluate_query(program, input, &query)
}

/// Evaluate one textual decision query and retain its complete runtime
/// provenance DAG.
///
/// Runtime fragment evidence remains on [`Evaluation`]; provenance is an
/// opt-in, versioned companion payload.
///
/// # Errors
///
/// Returns the same parse, binding, and input diagnostics as [`evaluate`].
pub fn evaluate_with_provenance(
    program: &CompiledProgram,
    input: &Input,
    query_text: &str,
) -> Result<ProvenanceEvaluation, Diagnostic> {
    let query = Query::parse(query_text)
        .map_err(|message| Diagnostic::error("E1301", message, Span::default()))?;
    evaluate_query_with_provenance(program, input, &query)
}

/// Evaluate an already parsed decision query.
///
/// # Errors
///
/// Returns a diagnostic for an unknown decision, arity mismatch, missing
/// binding, or incompatible record argument.
pub fn evaluate_query(
    program: &CompiledProgram,
    input: &Input,
    query: &Query,
) -> Result<Evaluation, Diagnostic> {
    evaluate_query_internal(program, input, query, None)
}

/// Evaluate an already parsed query and retain its complete runtime provenance
/// DAG.
///
/// # Errors
///
/// Returns the same query, binding, and input diagnostics as
/// [`evaluate_query`].
pub fn evaluate_query_with_provenance(
    program: &CompiledProgram,
    input: &Input,
    query: &Query,
) -> Result<ProvenanceEvaluation, Diagnostic> {
    let recorder = Rc::new(RefCell::new(ProvenanceRecorder::new(
        program.source().clone(),
        program.ast().module.value.clone(),
        query.render(),
    )));
    let evaluation = evaluate_query_internal(program, input, query, Some(recorder.clone()))?;
    let provenance = recorder
        .borrow()
        .clone()
        .finish(provenance_result_id(query));
    Ok(ProvenanceEvaluation {
        evaluation,
        provenance,
    })
}

fn evaluate_query_internal(
    program: &CompiledProgram,
    input: &Input,
    query: &Query,
    provenance: Option<Rc<RefCell<ProvenanceRecorder>>>,
) -> Result<Evaluation, Diagnostic> {
    if let Some(diagnostic) = input.validate(program).into_iter().next() {
        return Err(diagnostic);
    }
    let decision = find_decision(program, &query.decision).ok_or_else(|| {
        Diagnostic::error(
            "E1302",
            format!("unknown decision `{}`", query.decision),
            Span::default(),
        )
    })?;
    if decision.parameters.len() != query.arguments.len() {
        return Err(Diagnostic::error(
            "E1303",
            format!(
                "decision `{}` expects {} argument(s), but {} were supplied",
                query.decision,
                decision.parameters.len(),
                query.arguments.len()
            ),
            Span::default(),
        ));
    }
    for (argument, parameter) in query.arguments.iter().zip(&decision.parameters) {
        let Some(binding) = input.bindings.get(argument) else {
            return Err(Diagnostic::error(
                "E1304",
                format!("query argument `{argument}` has no input binding"),
                Span::default(),
            ));
        };
        if binding.entity != parameter.ty.value {
            return Err(Diagnostic::error(
                "E1305",
                format!(
                    "query argument `{argument}` has record type `{}`, expected `{}`",
                    binding.entity, parameter.ty.value
                ),
                Span::default(),
            ));
        }
    }
    let binding_entities = input
        .bindings
        .iter()
        .map(|(name, binding)| (name.clone(), binding.entity.clone()))
        .collect::<BTreeMap<_, _>>();

    let rules = all_rules(program);
    let mut traces = Vec::new();
    let mut pending = Vec::new();
    let mut active_overrides: BTreeMap<String, String> = BTreeMap::new();
    let mut uncertain_overrides = Vec::new();
    let mut blockers = Vec::new();
    let mut provenance_contributors = BTreeSet::new();

    for rule in rules {
        let Ok(variables) = resolve_rule_bindings(rule, decision, query, &binding_entities) else {
            continue;
        };
        let affects_decision = matches!(
            &rule.effect,
            Effect::Decide {
                decision: target,
                ..
            } if target.value == query.decision
        );
        let override_targets = match &rule.effect {
            Effect::Override { rule, .. }
                if program.rule(&rule.value).is_some_and(|target_rule| {
                    matches!(
                        &target_rule.effect,
                        Effect::Decide { decision, .. }
                            if normalize_name(&decision.value) == query.decision
                    )
                }) =>
            {
                BTreeSet::from([rule.value.clone()])
            }
            Effect::Decide { .. } | Effect::Override { .. } | Effect::Invalid { .. } => {
                BTreeSet::new()
            }
        };
        if !affects_decision && override_targets.is_empty() {
            continue;
        }

        let mut context = EvalContext {
            program,
            input,
            variables: variables
                .into_iter()
                .map(|(parameter, binding)| (parameter, RuntimeValue::Entity(binding)))
                .collect(),
            variable_origins: BTreeMap::new(),
            derive_stack: Vec::new(),
            provenance: provenance.clone(),
        };
        if let Some(provenance) = &provenance {
            provenance.borrow_mut().set_scope(format!(
                "rule:{}:condition",
                display_symbol_name(&rule.name.value)
            ));
        }
        let condition = context.eval(&rule.condition, Some(&TypeRef::Bool)).truth();
        let condition_node = provenance.as_ref().map(|provenance| {
            let mut provenance = provenance.borrow_mut();
            let expression = provenance
                .last_completed()
                .expect("a recorded condition must have an expression root");
            let id = format!("condition:{}", display_symbol_name(&rule.name.value));
            provenance.record_node(
                id.clone(),
                ProvenanceNodeKind::RuleCondition,
                display_symbol_name(&rule.name.value),
                provenance_truth_observation(&condition),
            );
            provenance.connect(expression, id.clone(), ProvenanceEdgeKind::Evaluates);
            id
        });
        let condition_expression = program
            .source()
            .text
            .get(rule.condition.span.start..rule.condition.span.end)
            .unwrap_or("<condition>")
            .trim()
            .to_owned();
        let basis = collect_fragment_evidence(program, &rule.basis);
        match condition {
            RuntimeTruth::False => {
                if let Some(condition_node) = &condition_node {
                    provenance_contributors.insert(condition_node.clone());
                }
                traces.push(RuleTrace {
                    rule: display_symbol_name(&rule.name.value),
                    condition_expression: condition_expression.clone(),
                    condition: TruthValue::False,
                    outcome: RuleOutcome::Skipped,
                    missing: Vec::new(),
                    basis,
                });
            }
            RuntimeTruth::Unknown(missing) => {
                if affects_decision {
                    blockers.push(Blocker {
                        rule: rule.name.value.clone(),
                        missing: missing.clone(),
                        reasons: Vec::new(),
                        conflict: false,
                        provenance: condition_node.clone(),
                    });
                }
                if !override_targets.is_empty() {
                    uncertain_overrides.push(UncertainOverride {
                        rule: rule.name.value.clone(),
                        targets: override_targets,
                        missing: missing.clone(),
                        provenance: condition_node.clone(),
                    });
                }
                traces.push(RuleTrace {
                    rule: display_symbol_name(&rule.name.value),
                    condition_expression: condition_expression.clone(),
                    condition: TruthValue::Unknown,
                    outcome: RuleOutcome::Blocked,
                    missing: missing.into_iter().collect(),
                    basis,
                });
            }
            RuntimeTruth::Conflict(reasons) => {
                if affects_decision || !override_targets.is_empty() {
                    blockers.push(Blocker {
                        rule: rule.name.value.clone(),
                        missing: BTreeSet::new(),
                        reasons: reasons.clone(),
                        conflict: true,
                        provenance: condition_node.clone(),
                    });
                }
                if !override_targets.is_empty() {
                    uncertain_overrides.push(UncertainOverride {
                        rule: rule.name.value.clone(),
                        targets: override_targets,
                        missing: BTreeSet::new(),
                        provenance: condition_node.clone(),
                    });
                }
                traces.push(RuleTrace {
                    rule: display_symbol_name(&rule.name.value),
                    condition_expression: condition_expression.clone(),
                    condition: TruthValue::Conflict,
                    outcome: RuleOutcome::Conflicted,
                    missing: Vec::new(),
                    basis,
                });
            }
            RuntimeTruth::True => {
                let applied_override = !override_targets.is_empty();
                for target in override_targets {
                    if let Some(provenance) = &provenance {
                        let id = provenance_override_id(&rule.name.value, &target);
                        let mut provenance = provenance.borrow_mut();
                        provenance.record_node(
                            id.clone(),
                            ProvenanceNodeKind::Override,
                            format!(
                                "{} overrides {}",
                                display_symbol_name(&rule.name.value),
                                display_symbol_name(&target)
                            ),
                            ProvenanceObservation::status(ProvenanceStatus::Applied),
                        );
                        if let Some(condition_node) = &condition_node {
                            provenance.connect(
                                condition_node.clone(),
                                id.clone(),
                                ProvenanceEdgeKind::Enables,
                            );
                        }
                    }
                    active_overrides
                        .entry(target)
                        .and_modify(|current| {
                            if rule.name.value < *current {
                                current.clone_from(&rule.name.value);
                            }
                        })
                        .or_insert_with(|| rule.name.value.clone());
                }
                let mut added_candidate = false;
                let mut effect_missing = BTreeSet::new();
                let mut effect_conflicted = false;
                if let Effect::Decide {
                    decision: target,
                    arguments,
                    value,
                    ..
                } = &rule.effect
                {
                    let saved_provenance = context.provenance.take();
                    let matches_query = effect_matches_query(&mut context, arguments, query);
                    context.provenance = saved_provenance;
                    if matches_query {
                        if let Some(provenance) = &provenance {
                            provenance.borrow_mut().set_scope(format!(
                                "rule:{}:candidate:{}",
                                display_symbol_name(&rule.name.value),
                                value.span.start
                            ));
                        }
                        let candidate_value =
                            context.eval(value, Some(&decision.return_type.value));
                        let candidate_node = provenance.as_ref().map(|provenance| {
                            let mut provenance = provenance.borrow_mut();
                            let expression = provenance
                                .last_completed()
                                .expect("a recorded candidate must have an expression root");
                            let id = provenance_candidate_id(&rule.name.value, value.span.start);
                            let observation = match &candidate_value {
                                RuntimeValue::Known(value) => ProvenanceObservation::value(
                                    ProvenanceStatus::Applied,
                                    value.clone(),
                                ),
                                RuntimeValue::Unknown(missing) => ProvenanceObservation {
                                    status: ProvenanceStatus::Blocked,
                                    values: Vec::new(),
                                    missing: missing.iter().cloned().collect(),
                                    reasons: Vec::new(),
                                },
                                RuntimeValue::Conflict(reasons) => ProvenanceObservation {
                                    status: ProvenanceStatus::Conflict,
                                    values: Vec::new(),
                                    missing: Vec::new(),
                                    reasons: reasons.clone(),
                                },
                                RuntimeValue::Entity(binding) => ProvenanceObservation {
                                    status: ProvenanceStatus::Conflict,
                                    values: Vec::new(),
                                    missing: Vec::new(),
                                    reasons: vec![format!(
                                        "decision value evaluated to record reference `{binding}`"
                                    )],
                                },
                            };
                            provenance.record_node(
                                id.clone(),
                                ProvenanceNodeKind::DecisionCandidate,
                                format!(
                                    "{} by {}",
                                    target.value,
                                    display_symbol_name(&rule.name.value)
                                ),
                                observation,
                            );
                            provenance.connect(
                                expression,
                                id.clone(),
                                ProvenanceEdgeKind::Produces,
                            );
                            if let Some(condition_node) = &condition_node {
                                provenance.connect(
                                    condition_node.clone(),
                                    id.clone(),
                                    ProvenanceEdgeKind::Enables,
                                );
                            }
                            id
                        });
                        match candidate_value {
                            RuntimeValue::Known(value) => {
                                pending.push(PendingCandidate {
                                    candidate: Candidate {
                                        rule: rule.name.value.clone(),
                                        value,
                                        basis: basis.clone(),
                                    },
                                    provenance: candidate_node.into_iter().collect(),
                                });
                                added_candidate = true;
                            }
                            RuntimeValue::Unknown(missing) => {
                                effect_missing.extend(missing.iter().cloned());
                                blockers.push(Blocker {
                                    rule: rule.name.value.clone(),
                                    missing,
                                    reasons: Vec::new(),
                                    conflict: false,
                                    provenance: candidate_node,
                                });
                            }
                            RuntimeValue::Conflict(reasons) => {
                                effect_conflicted = true;
                                blockers.push(Blocker {
                                    rule: rule.name.value.clone(),
                                    missing: BTreeSet::new(),
                                    reasons,
                                    conflict: true,
                                    provenance: candidate_node,
                                });
                            }
                            RuntimeValue::Entity(_) => {
                                effect_conflicted = true;
                                blockers.push(Blocker {
                                    rule: rule.name.value.clone(),
                                    missing: BTreeSet::new(),
                                    reasons: vec![
                                        "decision value evaluated to a record reference".into(),
                                    ],
                                    conflict: true,
                                    provenance: candidate_node,
                                });
                            }
                        }
                    }
                }
                traces.push(RuleTrace {
                    rule: display_symbol_name(&rule.name.value),
                    condition_expression,
                    condition: TruthValue::True,
                    outcome: if effect_conflicted {
                        RuleOutcome::Conflicted
                    } else if !effect_missing.is_empty() {
                        RuleOutcome::Blocked
                    } else if added_candidate {
                        RuleOutcome::Applied
                    } else if applied_override {
                        RuleOutcome::OverrideApplied
                    } else {
                        // The rule evaluated successfully, but its effect did
                        // not contribute a candidate for this decision.
                        RuleOutcome::Applied
                    },
                    missing: effect_missing.into_iter().collect(),
                    basis,
                });
            }
        }
    }

    traces.sort_by(|left, right| left.rule.cmp(&right.rule));
    pending.sort_by(|left, right| {
        (&left.candidate.rule, &left.candidate.value)
            .cmp(&(&right.candidate.rule, &right.candidate.value))
    });
    let mut deduplicated: Vec<PendingCandidate> = Vec::new();
    for mut pending in pending {
        if let Some(existing) = deduplicated
            .last_mut()
            .filter(|existing| existing.candidate == pending.candidate)
        {
            existing.provenance.append(&mut pending.provenance);
        } else {
            deduplicated.push(pending);
        }
    }

    let mut suppressed = Vec::new();
    let mut candidates = Vec::new();
    for pending in deduplicated {
        if let Some(by) = active_overrides.get(&pending.candidate.rule) {
            if let (Some(provenance), Some(first_candidate)) =
                (&provenance, pending.provenance.first())
            {
                let suppression_id = format!(
                    "suppression:{first_candidate}:by:{}",
                    display_symbol_name(by)
                );
                let mut provenance = provenance.borrow_mut();
                provenance.record_node(
                    suppression_id.clone(),
                    ProvenanceNodeKind::Suppression,
                    format!(
                        "{} suppressed by {}",
                        display_symbol_name(&pending.candidate.rule),
                        display_symbol_name(by)
                    ),
                    ProvenanceObservation::value(
                        ProvenanceStatus::Suppressed,
                        pending.candidate.value.clone(),
                    ),
                );
                for candidate_node in &pending.provenance {
                    provenance.connect(
                        candidate_node.clone(),
                        suppression_id.clone(),
                        ProvenanceEdgeKind::Contributes,
                    );
                }
                provenance.connect(
                    provenance_override_id(by, &pending.candidate.rule),
                    suppression_id.clone(),
                    ProvenanceEdgeKind::Suppresses,
                );
                provenance_contributors.insert(suppression_id);
            }
            suppressed.push(SuppressedCandidate {
                candidate: pending.candidate,
                reason: SuppressionReason::ExplicitOverride { by: by.clone() },
            });
        } else {
            provenance_contributors.extend(pending.provenance);
            candidates.push(pending.candidate);
        }
    }
    blockers.retain(|blocker| blocker.conflict || !active_overrides.contains_key(&blocker.rule));
    provenance_contributors.extend(
        blockers
            .iter()
            .filter_map(|blocker| blocker.provenance.clone()),
    );
    provenance_contributors.extend(uncertain_overrides.iter().filter_map(|uncertain| {
        candidates
            .iter()
            .any(|candidate| uncertain.targets.contains(&candidate.rule))
            .then(|| uncertain.provenance.clone())
            .flatten()
    }));

    suppressed.sort_by(|left, right| {
        (&left.candidate.rule, &left.candidate.value)
            .cmp(&(&right.candidate.rule, &right.candidate.value))
    });

    let status = resolve_status(
        decision.cardinality,
        &candidates,
        &blockers,
        &uncertain_overrides,
    );

    if let Some(provenance) = &provenance {
        let result_node = provenance_result_id(query);
        let mut provenance = provenance.borrow_mut();
        provenance.record_node(
            result_node.clone(),
            ProvenanceNodeKind::DecisionResult,
            query.render(),
            provenance_decision_observation(&status),
        );
        for contributor in provenance_contributors {
            provenance.connect(
                contributor,
                result_node.clone(),
                ProvenanceEdgeKind::Contributes,
            );
        }
    }

    for candidate in &mut candidates {
        candidate.rule = display_symbol_name(&candidate.rule);
    }
    for suppressed_candidate in &mut suppressed {
        suppressed_candidate.candidate.rule =
            display_symbol_name(&suppressed_candidate.candidate.rule);
        let SuppressionReason::ExplicitOverride { by } = &mut suppressed_candidate.reason;
        *by = display_symbol_name(by);
    }
    candidates.sort_by(|left, right| (&left.rule, &left.value).cmp(&(&right.rule, &right.value)));
    suppressed.sort_by(|left, right| {
        (&left.candidate.rule, &left.candidate.value)
            .cmp(&(&right.candidate.rule, &right.candidate.value))
    });

    Ok(Evaluation {
        query: query.render(),
        result: DecisionResult {
            decision: query.decision.clone(),
            cardinality: decision.cardinality,
            status,
            candidates,
            suppressed,
        },
        rules: traces,
    })
}

fn resolve_status(
    cardinality: Cardinality,
    candidates: &[Candidate],
    blockers: &[Blocker],
    uncertain_overrides: &[UncertainOverride],
) -> DecisionStatus {
    let mut missing = BTreeSet::new();
    let mut conflict_reasons = Vec::new();
    for blocker in blockers {
        missing.extend(blocker.missing.iter().cloned());
        if blocker.conflict {
            if blocker.reasons.is_empty() {
                conflict_reasons.push(format!(
                    "rule `{}` has conflicting premises",
                    display_symbol_name(&blocker.rule)
                ));
            } else {
                conflict_reasons.extend(blocker.reasons.iter().map(|reason| {
                    format!("rule `{}`: {reason}", display_symbol_name(&blocker.rule))
                }));
            }
        }
    }
    for uncertain in uncertain_overrides {
        if candidates
            .iter()
            .any(|candidate| uncertain.targets.contains(&candidate.rule))
        {
            missing.extend(uncertain.missing.iter().cloned());
            if uncertain.missing.is_empty() {
                conflict_reasons.push(format!(
                    "override rule `{}` has conflicting premises",
                    display_symbol_name(&uncertain.rule)
                ));
            }
        }
    }

    let mut values = candidates
        .iter()
        .map(|candidate| candidate.value.clone())
        .collect::<Vec<_>>();
    values.sort();
    values.dedup();

    if !conflict_reasons.is_empty() {
        conflict_reasons.sort();
        conflict_reasons.dedup();
        return DecisionStatus::Conflict {
            values,
            reasons: conflict_reasons,
        };
    }
    if !missing.is_empty() {
        return DecisionStatus::Unknown {
            missing: missing.into_iter().collect(),
        };
    }
    if values.is_empty() {
        return if cardinality == Cardinality::ExactlyOne {
            DecisionStatus::Undefined
        } else {
            DecisionStatus::Resolved { values }
        };
    }
    if cardinality != Cardinality::Many && values.len() > 1 {
        return DecisionStatus::Conflict {
            values,
            reasons: vec!["different values remain after explicit overrides".into()],
        };
    }
    DecisionStatus::Resolved { values }
}

/// Resolve rule parameters onto concrete query bindings.
///
/// Runtime evaluation and exact static partitioning intentionally share this
/// function: changing positional, repeated-argument, or ambiguity semantics in
/// one caller without the other could otherwise turn an analyzer proof unsound.
pub(crate) fn resolve_rule_bindings(
    rule: &RuleDecl,
    decision: &crate::ast::DecisionDecl,
    query: &Query,
    binding_entities: &BTreeMap<String, String>,
) -> Result<BTreeMap<String, String>, String> {
    let mut variables = BTreeMap::new();
    let parameter_types = rule
        .parameters
        .iter()
        .map(|parameter| {
            (
                normalize_name(&parameter.name.value),
                normalize_name(&parameter.ty.value),
            )
        })
        .collect::<BTreeMap<_, _>>();

    if let Effect::Decide {
        decision: target,
        arguments,
        ..
    } = &rule.effect
    {
        if normalize_name(&target.value) == query.decision
            && arguments.len() == query.arguments.len()
        {
            for (argument, query_argument) in arguments.iter().zip(&query.arguments) {
                let ExprKind::Name(parameter_name) = &argument.kind else {
                    continue;
                };
                let parameter_name = normalize_name(parameter_name);
                if !parameter_types.contains_key(&parameter_name) {
                    continue;
                }
                let query_argument = normalize_name(query_argument);
                if variables
                    .insert(parameter_name.clone(), query_argument.clone())
                    .is_some_and(|previous| previous != query_argument)
                {
                    return Err(format!(
                        "parameter `{parameter_name}` cannot bind consistently to this query"
                    ));
                }
            }
        }
    }

    for (index, parameter) in rule.parameters.iter().enumerate() {
        let parameter_name = normalize_name(&parameter.name.value);
        let parameter_type = normalize_name(&parameter.ty.value);
        if let Some(binding_name) = variables.get(&parameter_name) {
            if binding_entities.get(binding_name) != Some(&parameter_type) {
                return Err(format!(
                    "parameter `{parameter_name}` binds to an incompatible record"
                ));
            }
            continue;
        }
        if binding_entities.get(&parameter_name) == Some(&parameter_type) {
            variables.insert(parameter_name.clone(), parameter_name);
            continue;
        }
        if rule.parameters.len() == decision.parameters.len()
            && rule
                .parameters
                .iter()
                .zip(&decision.parameters)
                .all(|(left, right)| {
                    normalize_name(&left.ty.value) == normalize_name(&right.ty.value)
                })
        {
            let Some(binding_name) = query.arguments.get(index).map(|name| normalize_name(name))
            else {
                return Err(format!(
                    "parameter `{parameter_name}` has no positional query binding"
                ));
            };
            if binding_entities.get(&binding_name) != Some(&parameter_type) {
                return Err(format!(
                    "parameter `{parameter_name}` binds to an incompatible record"
                ));
            }
            variables.insert(parameter_name, binding_name);
            continue;
        }
        let mut matches = decision
            .parameters
            .iter()
            .zip(&query.arguments)
            .filter(|(decision_parameter, _)| {
                normalize_name(&decision_parameter.ty.value) == parameter_type
            })
            .map(|(_, argument)| normalize_name(argument))
            .collect::<Vec<_>>();
        if matches.is_empty() {
            matches = binding_entities
                .iter()
                .filter(|(_, entity)| **entity == parameter_type)
                .map(|(name, _)| name.clone())
                .collect();
        }
        matches.sort();
        matches.dedup();
        if matches.len() != 1 {
            return Err(format!(
                "parameter `{parameter_name}` has an ambiguous quantified binding"
            ));
        }
        variables.insert(parameter_name, matches.remove(0));
    }
    Ok(variables)
}

fn effect_matches_query(context: &mut EvalContext<'_>, arguments: &[Expr], query: &Query) -> bool {
    if arguments.len() != query.arguments.len() {
        return false;
    }
    arguments
        .iter()
        .zip(&query.arguments)
        .all(|(argument, query_argument)| {
            matches!(context.eval(argument, None), RuntimeValue::Entity(binding) if binding == *query_argument)
        })
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum TestStatus {
    Passed,
    Failed,
    Unresolved,
    Error,
}

const fn combine_test_status(current: TestStatus, next: TestStatus) -> TestStatus {
    const fn rank(status: TestStatus) -> u8 {
        match status {
            TestStatus::Passed => 0,
            TestStatus::Unresolved => 1,
            TestStatus::Failed => 2,
            TestStatus::Error => 3,
        }
    }
    if rank(next) > rank(current) {
        next
    } else {
        current
    }
}

/// Version of the standalone test-report payload serialized by [`TestReport`].
///
/// Every non-optional field is required. Any payload-shape change must advance
/// this schema version.
pub const TEST_REPORT_SCHEMA_VERSION: &str = "tess.test-report/v2";

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct TestAssertion {
    pub query: String,
    pub operator: String,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub expected: Option<Value>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub actual: Option<DecisionStatus>,
    pub status: TestStatus,
    pub message: String,
    pub duration_ms: u64,
}

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct TestOutcome {
    pub case: String,
    pub status: TestStatus,
    pub expectations: usize,
    pub message: String,
    pub assertions: Vec<TestAssertion>,
    pub duration_ms: u64,
}

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct TestReport {
    pub schema_version: String,
    pub module: String,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub selected_case: Option<String>,
    pub outcomes: Vec<TestOutcome>,
    pub passed: usize,
    pub failed: usize,
    pub unresolved: usize,
    pub errors: usize,
    pub duration_ms: u64,
}

impl Default for TestReport {
    fn default() -> Self {
        Self {
            schema_version: TEST_REPORT_SCHEMA_VERSION.to_owned(),
            module: String::new(),
            selected_case: None,
            outcomes: Vec::new(),
            passed: 0,
            failed: 0,
            unresolved: 0,
            errors: 0,
            duration_ms: 0,
        }
    }
}

impl TestReport {
    #[must_use]
    pub const fn success(&self) -> bool {
        self.failed == 0 && self.unresolved == 0 && self.errors == 0
    }

    #[must_use]
    pub const fn total(&self) -> usize {
        self.passed + self.failed + self.unresolved + self.errors
    }

    #[must_use]
    pub fn render_text(&self) -> String {
        let mut out = String::new();
        for outcome in &self.outcomes {
            let label = match outcome.status {
                TestStatus::Passed => "PASS",
                TestStatus::Failed => "FAIL",
                TestStatus::Unresolved => "UNRESOLVED",
                TestStatus::Error => "ERROR",
            };
            let _ = writeln!(out, "{label:10} {} — {}", outcome.case, outcome.message);
        }
        let _ = writeln!(
            out,
            "\n{} passed; {} failed; {} unresolved; {} errors",
            self.passed, self.failed, self.unresolved, self.errors
        );
        out
    }

    /// Render this report as a self-contained `JUnit XML` test suite.
    #[must_use]
    pub fn render_junit_xml(&self) -> String {
        let mut out = String::new();
        let suite_name = if self.module.is_empty() {
            "tess"
        } else {
            &self.module
        };
        let skipped = self.unresolved;
        let _ = writeln!(out, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>");
        let _ = writeln!(
            out,
            "<testsuite name=\"{}\" tests=\"{}\" failures=\"{}\" errors=\"{}\" skipped=\"{}\" time=\"{}\">",
            escape_xml_attribute(suite_name),
            self.total(),
            self.failed,
            self.errors,
            skipped,
            render_junit_seconds(self.duration_ms),
        );
        for outcome in &self.outcomes {
            let _ = writeln!(
                out,
                "  <testcase classname=\"{}\" name=\"{}\" assertions=\"{}\" time=\"{}\">",
                escape_xml_attribute(suite_name),
                escape_xml_attribute(&outcome.case),
                outcome.expectations,
                render_junit_seconds(outcome.duration_ms),
            );
            let element = match outcome.status {
                TestStatus::Passed => None,
                TestStatus::Failed => Some("failure"),
                TestStatus::Unresolved => Some("skipped"),
                TestStatus::Error => Some("error"),
            };
            if let Some(element) = element {
                let _ = writeln!(
                    out,
                    "    <{element} message=\"{}\">{}</{element}>",
                    escape_xml_attribute(&outcome.message),
                    escape_xml_text(&outcome.message),
                );
            }
            out.push_str("  </testcase>\n");
        }
        out.push_str("</testsuite>\n");
        out
    }
}

fn elapsed_millis(started: Instant) -> u64 {
    u64::try_from(started.elapsed().as_millis()).unwrap_or(u64::MAX)
}

fn render_junit_seconds(milliseconds: u64) -> String {
    format!("{}.{:03}", milliseconds / 1_000, milliseconds % 1_000)
}

fn escape_xml_attribute(value: &str) -> String {
    value
        .replace('&', "&amp;")
        .replace('<', "&lt;")
        .replace('>', "&gt;")
        .replace('"', "&quot;")
        .replace('\'', "&apos;")
}

fn escape_xml_text(value: &str) -> String {
    value
        .replace('&', "&amp;")
        .replace('<', "&lt;")
        .replace('>', "&gt;")
}

/// Execute all declared tests, optionally selecting one by name.
#[must_use]
pub fn run_tests(program: &CompiledProgram, filter: Option<&str>) -> TestReport {
    let report_started = Instant::now();
    let mut report = TestReport {
        module: program.ast().module.value.clone(),
        selected_case: filter.map(ToOwned::to_owned),
        ..TestReport::default()
    };
    for case in all_cases(program) {
        if filter.is_some_and(|filter| case.name.value != filter) {
            continue;
        }
        let case_started = Instant::now();
        if case.expectations.is_empty() {
            report.errors += 1;
            report.outcomes.push(TestOutcome {
                case: case.name.value.clone(),
                status: TestStatus::Error,
                expectations: 0,
                message: "test has no expectations".into(),
                assertions: Vec::new(),
                duration_ms: elapsed_millis(case_started),
            });
            continue;
        }
        let input = match Input::from_case(program, case) {
            Ok(input) => input,
            Err(diagnostics) => {
                report.errors += 1;
                report.outcomes.push(TestOutcome {
                    case: case.name.value.clone(),
                    status: TestStatus::Error,
                    expectations: case.expectations.len(),
                    message: diagnostics
                        .iter()
                        .map(|diagnostic| diagnostic.message.clone())
                        .collect::<Vec<_>>()
                        .join("; "),
                    assertions: Vec::new(),
                    duration_ms: elapsed_millis(case_started),
                });
                continue;
            }
        };
        let mut status = TestStatus::Passed;
        let mut messages = Vec::new();
        let mut assertions = Vec::with_capacity(case.expectations.len());
        for expectation in &case.expectations {
            let assertion_started = Instant::now();
            let arguments = expectation
                .arguments
                .iter()
                .filter_map(|argument| match &argument.kind {
                    ExprKind::Name(name) => Some(name.clone()),
                    _ => None,
                })
                .collect::<Vec<_>>();
            let query = Query {
                decision: expectation.decision.value.clone(),
                arguments,
            };
            let evaluation = match evaluate_query(program, &input, &query) {
                Ok(evaluation) => evaluation,
                Err(error) => {
                    status = combine_test_status(status, TestStatus::Error);
                    messages.push(error.message.clone());
                    assertions.push(TestAssertion {
                        query: query.render(),
                        operator: render_test_operator(expectation.operator).to_owned(),
                        expected: None,
                        actual: None,
                        status: TestStatus::Error,
                        message: error.message,
                        duration_ms: elapsed_millis(assertion_started),
                    });
                    continue;
                }
            };
            let expected_type = find_decision(program, &expectation.decision.value)
                .map(|decision| &decision.return_type.value);
            let expected = constant_value(program, &expectation.value, expected_type);
            let Ok(expected) = expected else {
                status = combine_test_status(status, TestStatus::Error);
                let message = expected.unwrap_err();
                messages.push(message.clone());
                assertions.push(TestAssertion {
                    query: query.render(),
                    operator: render_test_operator(expectation.operator).to_owned(),
                    expected: None,
                    actual: Some(evaluation.result.status.clone()),
                    status: TestStatus::Error,
                    message,
                    duration_ms: elapsed_millis(assertion_started),
                });
                continue;
            };
            let mut assertion_status = TestStatus::Passed;
            let mut assertion_message = "expectation satisfied".to_owned();
            match &evaluation.result.status {
                DecisionStatus::Resolved { values } => {
                    let equal = values.contains(&expected);
                    let satisfied = match expectation.operator {
                        crate::ast::CompareOp::Equal => equal,
                        crate::ast::CompareOp::NotEqual => !equal,
                    };
                    if !satisfied {
                        status = combine_test_status(status, TestStatus::Failed);
                        assertion_status = TestStatus::Failed;
                        assertion_message = format!(
                            "expected {} {} {}, got {}",
                            query.render(),
                            if expectation.operator == crate::ast::CompareOp::Equal {
                                "="
                            } else {
                                "!="
                            },
                            expected,
                            values
                                .iter()
                                .map(ToString::to_string)
                                .collect::<Vec<_>>()
                                .join(", ")
                        );
                        messages.push(assertion_message.clone());
                    }
                }
                DecisionStatus::Undefined => {
                    status = combine_test_status(status, TestStatus::Unresolved);
                    assertion_status = TestStatus::Unresolved;
                    assertion_message = format!("{} was undefined", query.render());
                    messages.push(assertion_message.clone());
                }
                DecisionStatus::Unknown { missing } => {
                    status = combine_test_status(status, TestStatus::Unresolved);
                    assertion_status = TestStatus::Unresolved;
                    assertion_message = format!(
                        "{} was unknown (missing {})",
                        query.render(),
                        missing.join(", ")
                    );
                    messages.push(assertion_message.clone());
                }
                DecisionStatus::Conflict { values, .. } => {
                    status = combine_test_status(status, TestStatus::Failed);
                    assertion_status = TestStatus::Failed;
                    assertion_message = format!(
                        "{} conflicted: {}",
                        query.render(),
                        values
                            .iter()
                            .map(ToString::to_string)
                            .collect::<Vec<_>>()
                            .join(", ")
                    );
                    messages.push(assertion_message.clone());
                }
            }
            assertions.push(TestAssertion {
                query: query.render(),
                operator: render_test_operator(expectation.operator).to_owned(),
                expected: Some(expected),
                actual: Some(evaluation.result.status),
                status: assertion_status,
                message: assertion_message,
                duration_ms: elapsed_millis(assertion_started),
            });
        }
        if messages.is_empty() {
            messages.push(format!(
                "{} expectation(s) satisfied",
                case.expectations.len()
            ));
        }
        match status {
            TestStatus::Passed => report.passed += 1,
            TestStatus::Failed => report.failed += 1,
            TestStatus::Unresolved => report.unresolved += 1,
            TestStatus::Error => report.errors += 1,
        }
        report.outcomes.push(TestOutcome {
            case: case.name.value.clone(),
            status,
            expectations: case.expectations.len(),
            message: messages.join("; "),
            assertions,
            duration_ms: elapsed_millis(case_started),
        });
    }
    report.duration_ms = elapsed_millis(report_started);
    report
}

const fn render_test_operator(operator: crate::ast::CompareOp) -> &'static str {
    match operator {
        crate::ast::CompareOp::Equal => "equal",
        crate::ast::CompareOp::NotEqual => "not_equal",
    }
}

pub(crate) fn constant_value(
    program: &CompiledProgram,
    expression: &Expr,
    expected: Option<&TypeRef>,
) -> Result<Value, String> {
    let input = Input::new();
    let mut context = EvalContext {
        program,
        input: &input,
        variables: BTreeMap::new(),
        variable_origins: BTreeMap::new(),
        derive_stack: Vec::new(),
        provenance: None,
    };
    match context.eval(expression, expected) {
        RuntimeValue::Known(value) => Ok(value),
        RuntimeValue::Unknown(missing) => Err(format!(
            "constant value is unknown: {}",
            missing.into_iter().collect::<Vec<_>>().join(", ")
        )),
        RuntimeValue::Conflict(reasons) => Err(reasons.join("; ")),
        RuntimeValue::Entity(_) => Err("constant value cannot be a record reference".into()),
    }
}

#[derive(Clone, Debug)]
pub(crate) struct ConditionEvaluation {
    pub truth: TruthValue,
    pub missing: Vec<String>,
    pub reasons: Vec<String>,
}

#[derive(Clone, Debug)]
pub(crate) enum ValueEvaluation {
    Known(Value),
    Unknown(Vec<String>),
    Conflict(Vec<String>),
}

pub(crate) fn evaluate_condition(
    program: &CompiledProgram,
    input: &Input,
    variables: BTreeMap<String, String>,
    expression: &Expr,
) -> ConditionEvaluation {
    let mut context = EvalContext {
        program,
        input,
        variables: variables
            .into_iter()
            .map(|(parameter, binding)| (parameter, RuntimeValue::Entity(binding)))
            .collect(),
        variable_origins: BTreeMap::new(),
        derive_stack: Vec::new(),
        provenance: None,
    };
    match context.eval(expression, Some(&TypeRef::Bool)).truth() {
        RuntimeTruth::True => ConditionEvaluation {
            truth: TruthValue::True,
            missing: Vec::new(),
            reasons: Vec::new(),
        },
        RuntimeTruth::False => ConditionEvaluation {
            truth: TruthValue::False,
            missing: Vec::new(),
            reasons: Vec::new(),
        },
        RuntimeTruth::Unknown(missing) => ConditionEvaluation {
            truth: TruthValue::Unknown,
            missing: missing.into_iter().collect(),
            reasons: Vec::new(),
        },
        RuntimeTruth::Conflict(reasons) => ConditionEvaluation {
            truth: TruthValue::Conflict,
            missing: Vec::new(),
            reasons,
        },
    }
}

pub(crate) fn evaluate_value(
    program: &CompiledProgram,
    input: &Input,
    variables: BTreeMap<String, String>,
    expression: &Expr,
    expected: Option<&TypeRef>,
) -> ValueEvaluation {
    let mut context = EvalContext {
        program,
        input,
        variables: variables
            .into_iter()
            .map(|(parameter, binding)| (parameter, RuntimeValue::Entity(binding)))
            .collect(),
        variable_origins: BTreeMap::new(),
        derive_stack: Vec::new(),
        provenance: None,
    };
    match context.eval(expression, expected) {
        RuntimeValue::Known(value) => ValueEvaluation::Known(value),
        RuntimeValue::Unknown(missing) => ValueEvaluation::Unknown(missing.into_iter().collect()),
        RuntimeValue::Conflict(reasons) => ValueEvaluation::Conflict(reasons),
        RuntimeValue::Entity(binding) => ValueEvaluation::Conflict(vec![format!(
            "expression produced state/record reference `{binding}` instead of a scalar value"
        )]),
    }
}

fn json_value(
    program: &CompiledProgram,
    value: &serde_json::Value,
    expected: &TypeRef,
) -> Result<Value, String> {
    match expected {
        TypeRef::Bool => value
            .as_bool()
            .map(Value::Bool)
            .ok_or_else(|| "expected Bool".into()),
        TypeRef::Int => value
            .as_i64()
            .map(Value::Int)
            .ok_or_else(|| "expected an integer".into()),
        TypeRef::Decimal => {
            let text = match value {
                serde_json::Value::Number(number) => number.to_string(),
                serde_json::Value::String(text) => text.clone(),
                _ => return Err("expected a JSON number or decimal string".into()),
            };
            parse_decimal(&text)
                .map(Value::decimal)
                .map_err(|error| error.to_string())
        }
        TypeRef::String => value
            .as_str()
            .map(|value| Value::String(value.to_owned()))
            .ok_or_else(|| "expected String".into()),
        TypeRef::Date => value
            .as_str()
            .ok_or_else(|| "expected an ISO date string".to_owned())
            .and_then(|value| {
                NaiveDate::parse_from_str(value, "%Y-%m-%d")
                    .map(Value::Date)
                    .map_err(|error| error.to_string())
            }),
        TypeRef::Duration => value
            .as_i64()
            .map(Value::Duration)
            .ok_or_else(|| "expected duration seconds as an integer".into()),
        TypeRef::Named(name) if find_enum(program, name).is_some() => {
            let variant = value
                .as_str()
                .ok_or_else(|| format!("expected a variant name from enum `{name}`"))?;
            if enum_contains(program, name, variant) {
                Ok(Value::Enum {
                    type_name: name.clone(),
                    variant: variant.to_owned(),
                })
            } else {
                Err(format!("`{variant}` is not a variant of enum `{name}`"))
            }
        }
        TypeRef::Named(name) => Err(format!("nested record `{name}` is not a scalar field")),
        TypeRef::Unknown => Err("cannot decode a value with unknown type".into()),
    }
}

pub(crate) fn validate_field_value(
    program: &CompiledProgram,
    field: &crate::ast::FieldDecl,
    value: &Value,
) -> Result<(), String> {
    let type_matches = match (&field.ty, value) {
        (TypeRef::Bool, Value::Bool(_))
        | (TypeRef::Int, Value::Int(_))
        | (TypeRef::Decimal, Value::Decimal(_) | Value::Int(_))
        | (TypeRef::String, Value::String(_))
        | (TypeRef::Date, Value::Date(_))
        | (TypeRef::Duration, Value::Duration(_))
        | (TypeRef::Unknown, _) => true,
        (TypeRef::Named(expected), Value::Enum { type_name, variant }) => {
            expected == type_name && enum_contains(program, expected, variant)
        }
        (TypeRef::Named(expected), Value::EntityRef { type_name, .. }) => {
            expected == type_name && program.entity(expected).is_some()
        }
        _ => false,
    };
    if !type_matches {
        return Err(format!(
            "expected {}, found {}",
            type_name(&field.ty),
            value.kind_name()
        ));
    }
    if let Some(domain) = &field.domain {
        let mut allowed = Vec::new();
        let mut matches = false;
        for expression in &domain.values {
            let candidate = constant_value(program, expression, Some(&field.ty))?;
            matches |= if field.ty == TypeRef::Decimal {
                numeric_compare(&candidate, value).is_some_and(std::cmp::Ordering::is_eq)
            } else {
                candidate == *value
            };
            allowed.push(candidate.to_string());
        }
        if !matches {
            return Err(format!(
                "value {value} is outside the declared domain {{{}}}",
                allowed.join(", ")
            ));
        }
    }
    let Some(range) = &field.range else {
        return Ok(());
    };
    let Some(actual) = as_decimal(value) else {
        return Err("a range constraint requires a numeric value".into());
    };
    let start = numeric_literal_decimal(&range.start)?;
    let end = numeric_literal_decimal(&range.end)?;
    if actual < start || actual > end {
        let start = Value::decimal(start);
        let end = Value::decimal(end);
        return Err(format!(
            "value {value} is outside the inclusive range {start}..{end}"
        ));
    }
    Ok(())
}

fn numeric_literal_decimal(literal: &NumericLiteral) -> Result<Decimal, String> {
    match literal {
        NumericLiteral::Int(value) => Ok(Decimal::from(*value)),
        NumericLiteral::Decimal(value) => parse_decimal(value).map_err(|error| error.to_string()),
    }
}

fn type_name(ty: &TypeRef) -> &str {
    match ty {
        TypeRef::Bool => "Bool",
        TypeRef::Int => "Int",
        TypeRef::Decimal => "Decimal",
        TypeRef::String => "String",
        TypeRef::Date => "Date",
        TypeRef::Duration => "Duration",
        TypeRef::Named(name) => name,
        TypeRef::Unknown => "unknown",
    }
}

fn normalized_value(value: Value) -> Value {
    match value {
        Value::Decimal(value) => Value::decimal(value),
        Value::Enum { type_name, variant } => Value::Enum {
            type_name: normalize_name(&type_name),
            variant: normalize_name(&variant),
        },
        Value::EntityRef { type_name, id } => Value::EntityRef {
            type_name: normalize_name(&type_name),
            id: normalize_name(&id),
        },
        value => value,
    }
}

fn type_ref_from_value_type(value: &ValueType) -> Option<TypeRef> {
    match value {
        ValueType::Bool => Some(TypeRef::Bool),
        ValueType::Int => Some(TypeRef::Int),
        ValueType::Decimal => Some(TypeRef::Decimal),
        ValueType::String => Some(TypeRef::String),
        ValueType::Date => Some(TypeRef::Date),
        ValueType::Duration => Some(TypeRef::Duration),
        ValueType::Enum(name) | ValueType::Entity(name) | ValueType::State(name) => {
            Some(TypeRef::Named(name.clone()))
        }
        ValueType::Unknown => Some(TypeRef::Unknown),
        ValueType::Error => None,
    }
}

fn coerce_runtime_value(value: RuntimeValue, expected: Option<&TypeRef>) -> RuntimeValue {
    match (value, expected) {
        (RuntimeValue::Known(Value::Int(value)), Some(TypeRef::Decimal)) => {
            RuntimeValue::Known(Value::decimal(Decimal::from(value)))
        }
        (RuntimeValue::Known(Value::Decimal(value)), _) => {
            RuntimeValue::Known(Value::decimal(value))
        }
        (value, _) => value,
    }
}

fn negate(value: RuntimeValue) -> RuntimeValue {
    match value {
        RuntimeValue::Known(Value::Int(value)) => value.checked_neg().map_or_else(
            || RuntimeValue::Conflict(vec!["integer overflow".into()]),
            |value| RuntimeValue::Known(Value::Int(value)),
        ),
        RuntimeValue::Known(Value::Decimal(value)) => RuntimeValue::Known(Value::Decimal(-value)),
        value @ (RuntimeValue::Unknown(_) | RuntimeValue::Conflict(_)) => value,
        RuntimeValue::Known(_) | RuntimeValue::Entity(_) => {
            RuntimeValue::Conflict(vec!["unary `-` expects a number".into()])
        }
    }
}

fn absolute(value: RuntimeValue) -> RuntimeValue {
    match value {
        RuntimeValue::Known(Value::Int(value)) => value.checked_abs().map_or_else(
            || RuntimeValue::Conflict(vec!["integer overflow".into()]),
            |value| RuntimeValue::Known(Value::Int(value)),
        ),
        RuntimeValue::Known(Value::Decimal(value)) => {
            RuntimeValue::Known(Value::Decimal(value.abs()))
        }
        value @ (RuntimeValue::Unknown(_) | RuntimeValue::Conflict(_)) => value,
        RuntimeValue::Known(_) | RuntimeValue::Entity(_) => {
            RuntimeValue::Conflict(vec!["`abs` expects a number".into()])
        }
    }
}

fn min_max(left: RuntimeValue, right: RuntimeValue, max: bool) -> RuntimeValue {
    let (left, right) = match known_pair(left, right) {
        Ok(values) => values,
        Err(value) => return value,
    };
    match numeric_compare(&left, &right) {
        Some(ordering) => {
            if (max && ordering.is_ge()) || (!max && ordering.is_le()) {
                RuntimeValue::Known(left)
            } else {
                RuntimeValue::Known(right)
            }
        }
        None => RuntimeValue::Conflict(vec!["`min`/`max` expect comparable numbers".into()]),
    }
}

fn arithmetic(left: RuntimeValue, right: RuntimeValue, operator: BinaryOp) -> RuntimeValue {
    let (left, right) = match known_pair(left, right) {
        Ok(values) => values,
        Err(value) => return value,
    };
    if let (Value::Int(left), Value::Int(right)) = (&left, &right) {
        if operator != BinaryOp::Divide {
            let value = match operator {
                BinaryOp::Add => left.checked_add(*right),
                BinaryOp::Subtract => left.checked_sub(*right),
                BinaryOp::Multiply => left.checked_mul(*right),
                _ => None,
            };
            return value.map_or_else(
                || RuntimeValue::Conflict(vec!["integer arithmetic overflow".into()]),
                |value| RuntimeValue::Known(Value::Int(value)),
            );
        }
    }
    let Some(left) = as_decimal(&left) else {
        return RuntimeValue::Conflict(vec!["arithmetic expects numbers".into()]);
    };
    let Some(right) = as_decimal(&right) else {
        return RuntimeValue::Conflict(vec!["arithmetic expects numbers".into()]);
    };
    let result = match operator {
        BinaryOp::Add => checked_decimal_add(left, right),
        BinaryOp::Subtract => checked_decimal_sub(left, right),
        BinaryOp::Multiply => checked_decimal_mul(left, right),
        BinaryOp::Divide => checked_decimal_div(left, right),
        _ => unreachable!("non-arithmetic operator"),
    };
    result.map_or_else(
        |error| RuntimeValue::Conflict(vec![error.to_string()]),
        |value| RuntimeValue::Known(Value::Decimal(value)),
    )
}

fn compare(left: RuntimeValue, right: RuntimeValue, operator: BinaryOp) -> RuntimeValue {
    if let (RuntimeValue::Entity(left), RuntimeValue::Entity(right)) = (&left, &right) {
        return match operator {
            BinaryOp::Equal => RuntimeValue::Known(Value::Bool(left == right)),
            BinaryOp::NotEqual => RuntimeValue::Known(Value::Bool(left != right)),
            _ => RuntimeValue::Conflict(vec!["record values are only equality-comparable".into()]),
        };
    }
    let (left, right) = match known_pair(left, right) {
        Ok(values) => values,
        Err(value) => return value,
    };
    let ordering = if let Some(ordering) = numeric_compare(&left, &right) {
        Some(ordering)
    } else {
        match (&left, &right) {
            (Value::Bool(left), Value::Bool(right)) => Some(left.cmp(right)),
            (Value::String(left), Value::String(right)) => Some(left.cmp(right)),
            (Value::Date(left), Value::Date(right)) => Some(left.cmp(right)),
            (Value::Duration(left), Value::Duration(right)) => Some(left.cmp(right)),
            (
                Value::Enum {
                    type_name: left_type,
                    variant: left,
                },
                Value::Enum {
                    type_name: right_type,
                    variant: right,
                },
            ) if left_type == right_type => Some(left.cmp(right)),
            _ => None,
        }
    };
    let Some(ordering) = ordering else {
        return RuntimeValue::Conflict(vec!["values are not comparable".into()]);
    };
    let value = match operator {
        BinaryOp::Equal => ordering.is_eq(),
        BinaryOp::NotEqual => ordering.is_ne(),
        BinaryOp::Greater => ordering.is_gt(),
        BinaryOp::GreaterEqual => ordering.is_ge(),
        BinaryOp::Less => ordering.is_lt(),
        BinaryOp::LessEqual => ordering.is_le(),
        _ => unreachable!("non-comparison operator"),
    };
    RuntimeValue::Known(Value::Bool(value))
}

fn known_pair(left: RuntimeValue, right: RuntimeValue) -> Result<(Value, Value), RuntimeValue> {
    match (left, right) {
        (RuntimeValue::Known(left), RuntimeValue::Known(right)) => Ok((left, right)),
        (RuntimeValue::Conflict(mut left), RuntimeValue::Conflict(right)) => {
            left.extend(right);
            Err(RuntimeValue::Conflict(left))
        }
        (RuntimeValue::Conflict(reasons), _) | (_, RuntimeValue::Conflict(reasons)) => {
            Err(RuntimeValue::Conflict(reasons))
        }
        (RuntimeValue::Unknown(mut left), RuntimeValue::Unknown(right)) => {
            left.extend(right);
            Err(RuntimeValue::Unknown(left))
        }
        (RuntimeValue::Unknown(missing), _) | (_, RuntimeValue::Unknown(missing)) => {
            Err(RuntimeValue::Unknown(missing))
        }
        (RuntimeValue::Entity(_), _) | (_, RuntimeValue::Entity(_)) => {
            Err(RuntimeValue::Conflict(vec![
                "record values cannot be used here".into(),
            ]))
        }
    }
}

fn as_decimal(value: &Value) -> Option<Decimal> {
    match value {
        Value::Int(value) => Some(Decimal::from(*value)),
        Value::Decimal(value) => Some(*value),
        _ => None,
    }
}

fn numeric_compare(left: &Value, right: &Value) -> Option<std::cmp::Ordering> {
    Some(as_decimal(left)?.cmp(&as_decimal(right)?))
}

fn propagate_or_conflict(value: RuntimeValue, message: &str) -> RuntimeValue {
    match value {
        value @ (RuntimeValue::Unknown(_) | RuntimeValue::Conflict(_)) => value,
        RuntimeValue::Known(_) | RuntimeValue::Entity(_) => {
            RuntimeValue::Conflict(vec![message.into()])
        }
    }
}

fn truth_and(left: RuntimeTruth, right: RuntimeTruth) -> RuntimeTruth {
    match (left, right) {
        (RuntimeTruth::False, _) | (_, RuntimeTruth::False) => RuntimeTruth::False,
        (RuntimeTruth::True, RuntimeTruth::True) => RuntimeTruth::True,
        (RuntimeTruth::Conflict(mut left), RuntimeTruth::Conflict(right)) => {
            left.extend(right);
            RuntimeTruth::Conflict(left)
        }
        (RuntimeTruth::Conflict(reasons), _) | (_, RuntimeTruth::Conflict(reasons)) => {
            RuntimeTruth::Conflict(reasons)
        }
        (RuntimeTruth::Unknown(mut left), RuntimeTruth::Unknown(right)) => {
            left.extend(right);
            RuntimeTruth::Unknown(left)
        }
        (RuntimeTruth::Unknown(missing), _) | (_, RuntimeTruth::Unknown(missing)) => {
            RuntimeTruth::Unknown(missing)
        }
    }
}

fn truth_or(left: RuntimeTruth, right: RuntimeTruth) -> RuntimeTruth {
    match (left, right) {
        (RuntimeTruth::True, _) | (_, RuntimeTruth::True) => RuntimeTruth::True,
        (RuntimeTruth::False, RuntimeTruth::False) => RuntimeTruth::False,
        (RuntimeTruth::Conflict(mut left), RuntimeTruth::Conflict(right)) => {
            left.extend(right);
            RuntimeTruth::Conflict(left)
        }
        (RuntimeTruth::Conflict(reasons), _) | (_, RuntimeTruth::Conflict(reasons)) => {
            RuntimeTruth::Conflict(reasons)
        }
        (RuntimeTruth::Unknown(mut left), RuntimeTruth::Unknown(right)) => {
            left.extend(right);
            RuntimeTruth::Unknown(left)
        }
        (RuntimeTruth::Unknown(missing), _) | (_, RuntimeTruth::Unknown(missing)) => {
            RuntimeTruth::Unknown(missing)
        }
    }
}

fn find_entity<'a>(program: &'a CompiledProgram, name: &str) -> Option<&'a crate::ast::EntityDecl> {
    program.entity(name)
}

fn find_enum<'a>(program: &'a CompiledProgram, name: &str) -> Option<&'a crate::ast::EnumDecl> {
    program.enum_decl(name)
}

fn find_derive<'a>(program: &'a CompiledProgram, name: &str) -> Option<&'a crate::ast::DeriveDecl> {
    program.derive(name)
}

fn find_decision<'a>(
    program: &'a CompiledProgram,
    name: &str,
) -> Option<&'a crate::ast::DecisionDecl> {
    program.decision(name)
}

fn all_rules(program: &CompiledProgram) -> Vec<&RuleDecl> {
    let mut rules = program.rules().values().collect::<Vec<_>>();
    rules.sort_by(|left, right| left.name.value.cmp(&right.name.value));
    rules
}

fn all_cases(program: &CompiledProgram) -> Vec<&CaseDecl> {
    let mut cases = program.cases().values().collect::<Vec<_>>();
    cases.sort_by(|left, right| left.name.value.cmp(&right.name.value));
    cases
}

fn enum_contains(program: &CompiledProgram, enum_name: &str, variant: &str) -> bool {
    let variant = normalize_name(variant);
    find_enum(program, enum_name).is_some_and(|value| {
        value
            .variants
            .iter()
            .any(|candidate| normalize_name(&candidate.value) == variant)
    })
}

fn enum_variants(program: &CompiledProgram, variant: &str) -> Vec<String> {
    let variant = normalize_name(variant);
    let mut values = program
        .enums()
        .values()
        .filter(|value| {
            value
                .variants
                .iter()
                .any(|candidate| normalize_name(&candidate.value) == variant)
        })
        .map(|value| value.name.value.clone())
        .collect::<Vec<_>>();
    values.sort();
    values
}

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

    #[test]
    fn fragment_function_basis_reaches_runtime_rule_evidence() {
        let output = crate::compile_source(crate::SourceFile::new(
            "evidence.tes",
            r"record Request:
    value: Decimal

dec result(request Request) -> Bool

law::definitions:
    Definitions.

law::formula:
    The adjusted amount is seventy percent of the stated value.

    fn adjusted(request Request) -> Decimal:
        basis law::definitions
        request.value * 0.7

    fn eligible(request Request) -> Bool:
        adjusted(request) >= 10

rule applies(request Request):
    law::formula::eligible(request) => result(request) = true
",
        ));
        assert!(!output.has_errors(), "{:?}", output.diagnostics);
        let program = output.program.unwrap();
        let mut input = Input::new();
        input.insert(
            "request",
            "Request",
            BTreeMap::from([("value".into(), Value::decimal(Decimal::new(200, 1)))]),
        );
        let evaluation = evaluate(&program, &input, "result(request)").unwrap();
        assert_eq!(
            evaluation.rules[0]
                .basis
                .iter()
                .map(|basis| basis.id.as_str())
                .collect::<Vec<_>>(),
            ["law::formula", "law::definitions"]
        );
        assert!(
            evaluation
                .explain_text()
                .contains("The adjusted amount is seventy percent")
        );
        assert!(evaluation.explain_text().contains("Definitions."));
    }

    #[test]
    fn parses_query() {
        let query = Query::parse("최종등급(s)").unwrap();
        assert_eq!(query.decision, "최종등급");
        assert_eq!(query.arguments, ["s"]);
    }

    #[test]
    fn rejects_malformed_query() {
        assert!(Query::parse("grade").is_err());
        assert!(Query::parse("(s)").is_err());
        assert!(Query::parse("grade(s) trailing").is_err());
    }

    #[test]
    fn false_dominates_unknown_for_and() {
        assert!(matches!(
            truth_and(
                RuntimeTruth::False,
                RuntimeTruth::Unknown(BTreeSet::from(["x".into()]))
            ),
            RuntimeTruth::False
        ));
    }

    #[test]
    fn true_dominates_unknown_for_or() {
        assert!(matches!(
            truth_or(
                RuntimeTruth::True,
                RuntimeTruth::Unknown(BTreeSet::from(["x".into()]))
            ),
            RuntimeTruth::True
        ));
    }

    #[test]
    fn decimal_arithmetic_is_exact() {
        let result = arithmetic(
            RuntimeValue::Known(Value::Decimal(Decimal::new(1, 1))),
            RuntimeValue::Known(Value::Decimal(Decimal::new(2, 1))),
            BinaryOp::Add,
        );
        assert!(
            matches!(result, RuntimeValue::Known(Value::Decimal(value)) if value == Decimal::new(3, 1))
        );
    }

    #[test]
    fn division_by_zero_conflicts() {
        let result = arithmetic(
            RuntimeValue::Known(Value::Int(1)),
            RuntimeValue::Known(Value::Int(0)),
            BinaryOp::Divide,
        );
        assert!(matches!(result, RuntimeValue::Conflict(_)));
    }

    #[test]
    fn duplicate_candidate_values_are_merged_for_status() {
        let candidates = vec![
            Candidate {
                rule: "a".into(),
                value: Value::Int(1),
                basis: Vec::new(),
            },
            Candidate {
                rule: "b".into(),
                value: Value::Int(1),
                basis: Vec::new(),
            },
        ];
        let status = resolve_status(Cardinality::ExactlyOne, &candidates, &[], &[]);
        assert!(matches!(status, DecisionStatus::Resolved { values } if values == [Value::Int(1)]));
    }

    #[test]
    fn distinct_candidate_values_conflict() {
        let candidates = vec![
            Candidate {
                rule: "a".into(),
                value: Value::Int(1),
                basis: Vec::new(),
            },
            Candidate {
                rule: "b".into(),
                value: Value::Int(2),
                basis: Vec::new(),
            },
        ];
        assert!(matches!(
            resolve_status(Cardinality::ExactlyOne, &candidates, &[], &[]),
            DecisionStatus::Conflict { .. }
        ));
    }

    #[test]
    fn known_candidate_does_not_hide_an_unknown_rule() {
        let candidates = vec![Candidate {
            rule: "known".into(),
            value: Value::Int(1),
            basis: Vec::new(),
        }];
        let blockers = vec![Blocker {
            rule: "maybe".into(),
            missing: BTreeSet::from(["s.x".into()]),
            reasons: Vec::new(),
            conflict: false,
            provenance: None,
        }];
        assert!(matches!(
            resolve_status(Cardinality::ExactlyOne, &candidates, &blockers, &[]),
            DecisionStatus::Unknown { .. }
        ));
    }

    #[test]
    fn junit_report_escapes_names_and_failure_messages() {
        let report = TestReport {
            module: "rules & policy".to_owned(),
            outcomes: vec![TestOutcome {
                case: "a < b".to_owned(),
                status: TestStatus::Failed,
                expectations: 1,
                message: "expected \"yes\" & got <none>".to_owned(),
                assertions: Vec::new(),
                duration_ms: 12,
            }],
            failed: 1,
            duration_ms: 12,
            ..TestReport::default()
        };
        let xml = report.render_junit_xml();
        assert!(xml.contains("name=\"rules &amp; policy\""));
        assert!(xml.contains("name=\"a &lt; b\""));
        assert!(xml.contains("message=\"expected &quot;yes&quot; &amp; got &lt;none&gt;\""));
        assert!(xml.contains("expected \"yes\" &amp; got &lt;none&gt;"));
    }

    #[test]
    fn test_report_requires_versioned_metadata() {
        let report = serde_json::from_value::<TestReport>(serde_json::json!({
            "outcomes": [{
                "case": "example",
                "status": "passed",
                "expectations": 1,
                "message": "1 expectation(s) satisfied"
            }],
            "passed": 1,
            "failed": 0,
            "unresolved": 0,
            "errors": 0
        }));
        assert!(report.is_err());
    }
}