tessellate-core 0.1.0

//! Deterministic structural views of decisions, rules, overrides, and sources.
//!
//! A policy graph is intentionally descriptive rather than executable. It is
//! built from an already compiled program, so every referenced decision, rule,
//! and named source has passed normal Tess name and type checking.

use crate::ast::{Effect, SourceRef};
use crate::compiler::{CompiledProgram, display_symbol_name, normalize_name};
use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet};
use std::fmt::{self, Write};

/// Version of the serialized policy graph schema.
pub const POLICY_GRAPH_SCHEMA_VERSION: u32 = 1;

/// A stable, deterministically ordered policy graph.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyGraph {
    pub schema_version: u32,
    pub module: String,
    /// Present when the graph was restricted to one decision.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub decision: Option<String>,
    pub nodes: Vec<PolicyNode>,
    pub edges: Vec<PolicyEdge>,
}

/// A graph node with a kind-qualified, stable identifier.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyNode {
    pub id: String,
    pub kind: PolicyNodeKind,
    pub name: String,
    /// Only source nodes carry source metadata.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub source: Option<PolicySourceMetadata>,
}

/// The declaration represented by a graph node.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum PolicyNodeKind {
    Decision,
    Rule,
    Source,
}

/// Metadata retained for a named or legacy inline source reference.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicySourceMetadata {
    pub title: String,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub section: Option<String>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub version: Option<String>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub uri: Option<String>,
    /// `true` for a legacy `source "..."` reference without a declaration.
    pub inline: bool,
}

/// A directed relationship between two policy nodes.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct PolicyEdge {
    pub from: String,
    pub to: String,
    pub kind: PolicyEdgeKind,
}

/// The meaning of a directed policy graph edge.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum PolicyEdgeKind {
    /// A rule contributes a candidate to a decision.
    Proposes,
    /// A rule explicitly overrides another rule.
    Overrides,
    /// A rule cites a named or legacy inline source.
    Cites,
}

impl PolicyEdgeKind {
    const fn as_str(self) -> &'static str {
        match self {
            Self::Proposes => "proposes",
            Self::Overrides => "overrides",
            Self::Cites => "cites",
        }
    }
}

/// Failure to select a requested graph root.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum PolicyGraphError {
    UnknownDecision {
        name: String,
        available: Vec<String>,
    },
}

impl fmt::Display for PolicyGraphError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::UnknownDecision { name, available } if available.is_empty() => {
                write!(
                    formatter,
                    "decision `{name}` was not found; this target declares no decisions"
                )
            }
            Self::UnknownDecision { name, available } => write!(
                formatter,
                "decision `{name}` was not found; available decisions: {}",
                available.join(", ")
            ),
        }
    }
}

impl std::error::Error for PolicyGraphError {}

/// Build a complete graph, or the subgraph that can directly affect one decision.
///
/// A decision-filtered graph contains rules that propose that decision, rules
/// that directly override one of those proposing rules, and the sources cited
/// by the included rules. Unrelated effects on a multi-effect rule are omitted.
///
/// # Errors
///
/// Returns [`PolicyGraphError::UnknownDecision`] when `decision` does not name
/// a declared decision.
pub fn build_policy_graph(
    program: &CompiledProgram,
    decision: Option<&str>,
) -> Result<PolicyGraph, PolicyGraphError> {
    let selected = decision.map(normalize_name);
    let selected_declaration = if let (Some(selected), Some(requested)) = (&selected, decision) {
        Some(program.decisions().get(selected).ok_or_else(|| {
            PolicyGraphError::UnknownDecision {
                name: requested.to_owned(),
                available: program
                    .decisions()
                    .values()
                    .map(|declaration| display_symbol_name(&declaration.name.value))
                    .collect(),
            }
        })?)
    } else {
        None
    };

    let relevant_rules = relevant_rules(program, selected.as_deref());
    let mut nodes = BTreeMap::<String, PolicyNode>::new();
    let mut edges = BTreeSet::<PolicyEdge>::new();

    if let Some((selected, declaration)) = selected.as_ref().zip(selected_declaration) {
        insert_node(
            &mut nodes,
            PolicyNode {
                id: decision_id(selected),
                kind: PolicyNodeKind::Decision,
                name: display_symbol_name(&declaration.name.value),
                source: None,
            },
        );
    } else {
        for (name, declaration) in program.decisions() {
            insert_node(
                &mut nodes,
                PolicyNode {
                    id: decision_id(name),
                    kind: PolicyNodeKind::Decision,
                    name: display_symbol_name(&declaration.name.value),
                    source: None,
                },
            );
        }
        for (name, declaration) in program.sources() {
            insert_named_source(&mut nodes, name, declaration);
        }
    }

    for rule_name in &relevant_rules {
        let rule = &program.rules()[rule_name];
        insert_node(
            &mut nodes,
            PolicyNode {
                id: rule_id(rule_name),
                kind: PolicyNodeKind::Rule,
                name: display_symbol_name(&rule.name.value),
                source: None,
            },
        );

        for effect in &rule.effects {
            match effect {
                Effect::Decide { decision, .. } => {
                    let target = normalize_name(&decision.value);
                    if selected.as_ref().is_none_or(|selected| selected == &target) {
                        edges.insert(PolicyEdge {
                            from: rule_id(rule_name),
                            to: decision_id(&target),
                            kind: PolicyEdgeKind::Proposes,
                        });
                    }
                }
                Effect::Override { rule: target, .. } => {
                    let target = normalize_name(&target.value);
                    if relevant_rules.contains(&target) {
                        edges.insert(PolicyEdge {
                            from: rule_id(rule_name),
                            to: rule_id(&target),
                            kind: PolicyEdgeKind::Overrides,
                        });
                    }
                }
            }
        }

        for source in &rule.sources {
            let target = match source {
                SourceRef::Named(name) => {
                    let name = normalize_name(&name.value);
                    if let Some(declaration) = program.sources().get(&name) {
                        insert_named_source(&mut nodes, &name, declaration);
                    }
                    named_source_id(&name)
                }
                SourceRef::Inline(value) => {
                    let id = inline_source_id(&value.value);
                    insert_node(
                        &mut nodes,
                        PolicyNode {
                            id: id.clone(),
                            kind: PolicyNodeKind::Source,
                            name: value.value.clone(),
                            source: Some(PolicySourceMetadata {
                                title: value.value.clone(),
                                section: None,
                                version: None,
                                uri: None,
                                inline: true,
                            }),
                        },
                    );
                    id
                }
            };
            edges.insert(PolicyEdge {
                from: rule_id(rule_name),
                to: target,
                kind: PolicyEdgeKind::Cites,
            });
        }
    }

    Ok(PolicyGraph {
        schema_version: POLICY_GRAPH_SCHEMA_VERSION,
        module: program.ast().module.value.clone(),
        decision: selected_declaration
            .map(|declaration| display_symbol_name(&declaration.name.value)),
        nodes: nodes.into_values().collect(),
        edges: edges.into_iter().collect(),
    })
}

impl PolicyGraph {
    /// Render a canonical Graphviz DOT document.
    #[must_use]
    pub fn render_dot(&self) -> String {
        let mut output = String::from("digraph policy {\n  rankdir=LR;\n");
        for node in &self.nodes {
            let shape = match node.kind {
                PolicyNodeKind::Decision => "box",
                PolicyNodeKind::Rule => "ellipse",
                PolicyNodeKind::Source => "note",
            };
            let kind = match node.kind {
                PolicyNodeKind::Decision => "decision",
                PolicyNodeKind::Rule => "rule",
                PolicyNodeKind::Source => "source",
            };
            let mut label = format!("{kind}\n{}", node.name);
            if let Some(source) = node
                .source
                .as_ref()
                .filter(|source| source.title != node.name)
            {
                label.push('\n');
                label.push_str(&source.title);
            }
            let _ = writeln!(
                output,
                "  \"{}\" [label=\"{}\", shape={}];",
                dot_escape(&node.id),
                dot_escape(&label),
                shape
            );
        }
        for edge in &self.edges {
            let _ = writeln!(
                output,
                "  \"{}\" -> \"{}\" [label=\"{}\"];",
                dot_escape(&edge.from),
                dot_escape(&edge.to),
                edge.kind.as_str()
            );
        }
        output.push_str("}\n");
        output
    }
}

fn relevant_rules(program: &CompiledProgram, selected: Option<&str>) -> BTreeSet<String> {
    let Some(selected) = selected else {
        return program.rules().keys().cloned().collect();
    };
    let proposing = program
        .rules()
        .iter()
        .filter(|(_, rule)| {
            rule.effects.iter().any(|effect| {
                matches!(effect, Effect::Decide { decision, .. }
                    if normalize_name(&decision.value) == selected)
            })
        })
        .map(|(name, _)| name.clone())
        .collect::<BTreeSet<_>>();
    let mut relevant = proposing.clone();
    for (name, rule) in program.rules() {
        if rule.effects.iter().any(|effect| {
            matches!(effect, Effect::Override { rule, .. }
                if proposing.contains(&normalize_name(&rule.value)))
        }) {
            relevant.insert(name.clone());
        }
    }
    relevant
}

fn insert_node(nodes: &mut BTreeMap<String, PolicyNode>, node: PolicyNode) {
    nodes.entry(node.id.clone()).or_insert(node);
}

fn insert_named_source(
    nodes: &mut BTreeMap<String, PolicyNode>,
    name: &str,
    declaration: &crate::ast::SourceDecl,
) {
    insert_node(
        nodes,
        PolicyNode {
            id: named_source_id(name),
            kind: PolicyNodeKind::Source,
            name: display_symbol_name(&declaration.name.value),
            source: Some(PolicySourceMetadata {
                title: declaration.title.value.clone(),
                section: declaration
                    .section
                    .as_ref()
                    .map(|value| value.value.clone()),
                version: declaration
                    .version
                    .as_ref()
                    .map(|value| value.value.clone()),
                uri: declaration.uri.as_ref().map(|value| value.value.clone()),
                inline: false,
            }),
        },
    );
}

fn decision_id(name: &str) -> String {
    format!("decision:{}", display_symbol_name(name))
}

fn rule_id(name: &str) -> String {
    format!("rule:{}", display_symbol_name(name))
}

fn named_source_id(name: &str) -> String {
    format!("source:named:{}", display_symbol_name(name))
}

fn inline_source_id(value: &str) -> String {
    format!("source:inline:{value}")
}

fn dot_escape(value: &str) -> String {
    let mut escaped = String::with_capacity(value.len());
    for character in value.chars() {
        match character {
            '\\' => escaped.push_str("\\\\"),
            '"' => escaped.push_str("\\\""),
            '\n' => escaped.push_str("\\n"),
            '\r' => escaped.push_str("\\r"),
            '\t' => escaped.push_str("\\t"),
            control if control.is_control() => {
                let _ = write!(escaped, "\\\\u{{{:x}}}", u32::from(control));
            }
            value => escaped.push(value),
        }
    }
    escaped
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{SourceFile, compile_source};

    const GRAPH_SOURCE: &str = r#"module graph

enum Result { Yes, No }
entity Request { enabled: Bool }

decision eligibility(Request r) -> Result
decision audit(Request r) -> Bool many

source Statute {
  title: "Policy \"A\"",
  section: "4.2",
}
source Unused { title: "Unused" }

rule base(Request r):
  when r.enabled
  then eligibility(r) = Yes
  source Statute

rule exception(Request r):
  when not r.enabled
  then eligibility(r) = No
  then override base
  source "Legacy\nMemo"

rule audit_rule(Request r):
  when r.enabled
  then audit(r) = true
"#;

    fn compiled(text: &str) -> CompiledProgram {
        let output = compile_source(SourceFile::new("graph.tes", text));
        assert!(!output.has_errors(), "{:?}", output.diagnostics);
        output.program.expect("valid graph fixture")
    }

    #[test]
    fn full_graph_has_stable_nodes_edges_and_source_metadata() {
        let graph = build_policy_graph(&compiled(GRAPH_SOURCE), None).unwrap();
        assert_eq!(graph.schema_version, 1);
        assert_eq!(graph.module, "graph");
        assert_eq!(graph.nodes.len(), 8);
        assert_eq!(graph.edges.len(), 6);
        assert!(graph.nodes.windows(2).all(|pair| pair[0].id < pair[1].id));
        assert!(graph.edges.windows(2).all(|pair| pair[0] < pair[1]));
        let statute = graph
            .nodes
            .iter()
            .find(|node| node.id == "source:named:Statute")
            .unwrap();
        assert_eq!(
            statute.source.as_ref().unwrap().section.as_deref(),
            Some("4.2")
        );
        assert!(!statute.source.as_ref().unwrap().inline);
        assert!(graph.nodes.iter().any(|node| {
            node.id == "source:inline:Legacy\nMemo"
                && node.source.as_ref().is_some_and(|source| source.inline)
        }));
    }

    #[test]
    fn decision_filter_keeps_proposers_direct_overriders_and_their_sources() {
        let program = compiled(GRAPH_SOURCE);
        let graph = build_policy_graph(&program, Some("eligibility")).unwrap();
        assert_eq!(graph.decision.as_deref(), Some("eligibility"));
        assert_eq!(
            graph
                .nodes
                .iter()
                .map(|node| node.id.as_str())
                .collect::<Vec<_>>(),
            [
                "decision:eligibility",
                "rule:base",
                "rule:exception",
                "source:inline:Legacy\nMemo",
                "source:named:Statute",
            ]
        );
        assert_eq!(graph.edges.len(), 5);
        assert!(
            !graph
                .nodes
                .iter()
                .any(|node| node.id == "decision:audit" || node.id == "source:named:Unused")
        );
    }

    #[test]
    fn declaration_order_does_not_change_the_graph() {
        let first = build_policy_graph(&compiled(GRAPH_SOURCE), None).unwrap();
        let reordered = GRAPH_SOURCE.replace(
            "decision eligibility(Request r) -> Result\ndecision audit(Request r) -> Bool many",
            "decision audit(Request r) -> Bool many\ndecision eligibility(Request r) -> Result",
        );
        let second = build_policy_graph(&compiled(&reordered), None).unwrap();
        assert_eq!(first, second);
        let encoded = serde_json::to_string(&first).unwrap();
        assert_eq!(
            serde_json::from_str::<PolicyGraph>(&encoded).unwrap(),
            first
        );
    }

    #[test]
    fn dot_output_escapes_quotes_newlines_and_backslashes() {
        let graph = build_policy_graph(&compiled(GRAPH_SOURCE), Some("eligibility")).unwrap();
        let dot = graph.render_dot();
        assert!(dot.starts_with("digraph policy {\n  rankdir=LR;\n"));
        assert!(dot.contains("Policy \\\"A\\\""));
        assert!(dot.contains("Legacy\\nMemo"));
        assert!(dot.contains("[label=\"overrides\"]"));
        assert!(dot.ends_with("}\n"));
    }

    #[test]
    fn unknown_decision_lists_stable_available_names() {
        let error = build_policy_graph(&compiled(GRAPH_SOURCE), Some("missing")).unwrap_err();
        assert_eq!(
            error,
            PolicyGraphError::UnknownDecision {
                name: "missing".into(),
                available: vec!["audit".into(), "eligibility".into()],
            }
        );
        assert_eq!(
            error.to_string(),
            "decision `missing` was not found; available decisions: audit, eligibility"
        );
    }
}