tessellate-core 0.3.0

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

use crate::ast::{Effect, Expr, ExprKind, RuleDecl};
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 = 3;

/// Version of the serialized policy graph impact-diff schema.
pub const POLICY_GRAPH_DIFF_SCHEMA_VERSION: u32 = 2;

/// 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 fragment nodes carry fragment metadata.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub fragment: Option<PolicyFragmentMetadata>,
}

/// 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,
    Function,
    Fragment,
}

/// Native-document metadata retained for a fragment.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyFragmentMetadata {
    pub locator: String,
    pub text: String,
}

/// 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 or function is based on a document fragment.
    BasedOn,
    /// A rule or function calls a pure function.
    Calls,
    /// A document fragment explicitly references another fragment.
    References,
}

impl PolicyEdgeKind {
    const fn as_str(self) -> &'static str {
        match self {
            Self::Proposes => "proposes",
            Self::Overrides => "overrides",
            Self::BasedOn => "based_on",
            Self::Calls => "calls",
            Self::References => "references",
        }
    }
}

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

/// A stable comparison between a recorded policy graph and the current graph.
///
/// Fragment changes are reported as review triggers, not as an assertion that
/// every connected declaration is stale. Reverse `references`, `based_on`,
/// `calls`, `overrides`, and `proposes` relationships narrow the functions,
/// rules, and decisions that need human review.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyGraphDiff {
    pub schema_version: u32,
    pub module: String,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub decision: Option<String>,
    pub fragments: Vec<PolicyFragmentChange>,
    pub review_functions: Vec<PolicyFunctionReview>,
    pub review_rules: Vec<PolicyRuleReview>,
    pub review_decisions: Vec<PolicyDecisionReview>,
    pub added_nodes: Vec<PolicyNodeSummary>,
    pub removed_nodes: Vec<PolicyNodeSummary>,
    pub added_edges: Vec<PolicyEdge>,
    pub removed_edges: Vec<PolicyEdge>,
}

/// One fragment whose identity, locator, or raw source changed.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyFragmentChange {
    pub id: String,
    pub name: String,
    pub kind: PolicyFragmentChangeKind,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub before: Option<PolicyFragmentMetadata>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub after: Option<PolicyFragmentMetadata>,
}

/// The observable kind of a fragment change.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum PolicyFragmentChangeKind {
    Added,
    Removed,
    Text,
    Locator,
    TextAndLocator,
}

/// A rule connected to one or more changed fragments.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyRuleReview {
    pub id: String,
    pub name: String,
    pub fragments: Vec<String>,
}

/// A function connected to one or more changed fragments.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyFunctionReview {
    pub id: String,
    pub name: String,
    pub fragments: Vec<String>,
}

/// A decision that can receive a candidate from a review rule.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyDecisionReview {
    pub id: String,
    pub name: String,
    pub rules: Vec<String>,
}

/// Stable identity for an added or removed graph node.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PolicyNodeSummary {
    pub id: String,
    pub kind: PolicyNodeKind,
    pub name: String,
}

/// A recorded graph cannot be compared with the selected current graph.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum PolicyGraphDiffError {
    UnsupportedSchema {
        side: &'static str,
        found: u32,
        expected: u32,
    },
    ModuleMismatch {
        baseline: String,
        current: String,
    },
    DecisionMismatch {
        baseline: Option<String>,
        current: Option<String>,
    },
    MalformedFragment {
        side: &'static str,
        id: 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 {}

impl fmt::Display for PolicyGraphDiffError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::UnsupportedSchema {
                side,
                found,
                expected,
            } => write!(
                formatter,
                "unsupported {side} policy graph schema `{found}`; expected `{expected}`"
            ),
            Self::ModuleMismatch { baseline, current } => write!(
                formatter,
                "policy graph module mismatch: baseline `{baseline}`, current `{current}`"
            ),
            Self::DecisionMismatch { baseline, current } => write!(
                formatter,
                "policy graph decision filter mismatch: baseline `{}`, current `{}`",
                baseline.as_deref().unwrap_or("<all>"),
                current.as_deref().unwrap_or("<all>")
            ),
            Self::MalformedFragment { side, id } => write!(
                formatter,
                "{side} policy graph fragment `{id}` is missing its locator/text metadata"
            ),
        }
    }
}

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

/// Compare a recorded policy graph with a current graph and identify the
/// functions, rules, and decisions connected to changed source fragments.
///
/// Both graphs must use the current graph schema and the same module and
/// optional decision filter. Relationships from both sides participate in the
/// impact closure so removed basis, reference, call, or override edges do not
/// hide review work.
///
/// # Errors
///
/// Returns [`PolicyGraphDiffError`] for incompatible schemas, modules, or
/// decision-filtered graph scopes.
pub fn diff_policy_graphs(
    baseline: &PolicyGraph,
    current: &PolicyGraph,
) -> Result<PolicyGraphDiff, PolicyGraphDiffError> {
    for (side, graph) in [("baseline", baseline), ("current", current)] {
        if graph.schema_version != POLICY_GRAPH_SCHEMA_VERSION {
            return Err(PolicyGraphDiffError::UnsupportedSchema {
                side,
                found: graph.schema_version,
                expected: POLICY_GRAPH_SCHEMA_VERSION,
            });
        }
    }
    if baseline.module != current.module {
        return Err(PolicyGraphDiffError::ModuleMismatch {
            baseline: baseline.module.clone(),
            current: current.module.clone(),
        });
    }
    if baseline.decision != current.decision {
        return Err(PolicyGraphDiffError::DecisionMismatch {
            baseline: baseline.decision.clone(),
            current: current.decision.clone(),
        });
    }

    let baseline_nodes = baseline
        .nodes
        .iter()
        .map(|node| (node.id.clone(), node))
        .collect::<BTreeMap<_, _>>();
    let current_nodes = current
        .nodes
        .iter()
        .map(|node| (node.id.clone(), node))
        .collect::<BTreeMap<_, _>>();
    let node_ids = baseline_nodes
        .keys()
        .chain(current_nodes.keys())
        .cloned()
        .collect::<BTreeSet<_>>();

    let mut fragments = Vec::new();
    for id in &node_ids {
        let before = baseline_nodes
            .get(id)
            .filter(|node| node.kind == PolicyNodeKind::Fragment);
        let after = current_nodes
            .get(id)
            .filter(|node| node.kind == PolicyNodeKind::Fragment);
        let (name, kind, before_metadata, after_metadata) = match (before, after) {
            (None, None) => continue,
            (None, Some(after)) => (
                after.name.clone(),
                PolicyFragmentChangeKind::Added,
                None,
                Some(required_fragment_metadata(after, "current")?.clone()),
            ),
            (Some(before), None) => (
                before.name.clone(),
                PolicyFragmentChangeKind::Removed,
                Some(required_fragment_metadata(before, "baseline")?.clone()),
                None,
            ),
            (Some(before), Some(after)) => {
                let before_metadata = required_fragment_metadata(before, "baseline")?;
                let after_metadata = required_fragment_metadata(after, "current")?;
                let text = before_metadata.text != after_metadata.text;
                let locator = before_metadata.locator != after_metadata.locator;
                let kind = match (text, locator) {
                    (false, false) => continue,
                    (true, false) => PolicyFragmentChangeKind::Text,
                    (false, true) => PolicyFragmentChangeKind::Locator,
                    (true, true) => PolicyFragmentChangeKind::TextAndLocator,
                };
                (
                    after.name.clone(),
                    kind,
                    Some(before_metadata.clone()),
                    Some(after_metadata.clone()),
                )
            }
        };
        fragments.push(PolicyFragmentChange {
            id: id.clone(),
            name,
            kind,
            before: before_metadata,
            after: after_metadata,
        });
    }

    let added_nodes = current_nodes
        .iter()
        .filter(|(id, _)| !baseline_nodes.contains_key(*id))
        .map(|(_, node)| node_summary(node))
        .collect();
    let removed_nodes = baseline_nodes
        .iter()
        .filter(|(id, _)| !current_nodes.contains_key(*id))
        .map(|(_, node)| node_summary(node))
        .collect();
    let baseline_edges = baseline.edges.iter().cloned().collect::<BTreeSet<_>>();
    let current_edges = current.edges.iter().cloned().collect::<BTreeSet<_>>();
    let added_edges = current_edges.difference(&baseline_edges).cloned().collect();
    let removed_edges = baseline_edges.difference(&current_edges).cloned().collect();
    let combined_edges = baseline_edges
        .union(&current_edges)
        .cloned()
        .collect::<BTreeSet<_>>();

    let all_nodes = current_nodes.iter().chain(baseline_nodes.iter()).fold(
        BTreeMap::new(),
        |mut nodes, (id, node)| {
            nodes.entry(id.clone()).or_insert(*node);
            nodes
        },
    );
    let mut fragment_causes = fragments
        .iter()
        .map(|fragment| (fragment.id.clone(), BTreeSet::from([fragment.id.clone()])))
        .collect::<BTreeMap<_, _>>();
    loop {
        let mut changed = false;
        for edge in &combined_edges {
            if edge.kind != PolicyEdgeKind::References {
                continue;
            }
            let Some(causes) = fragment_causes.get(&edge.to).cloned() else {
                continue;
            };
            let entry = fragment_causes.entry(edge.from.clone()).or_default();
            let before = entry.len();
            entry.extend(causes);
            changed |= entry.len() != before;
        }
        if !changed {
            break;
        }
    }

    let mut policy_causes = BTreeMap::<String, BTreeSet<String>>::new();
    for edge in &combined_edges {
        if edge.kind == PolicyEdgeKind::BasedOn {
            if let Some(causes) = fragment_causes.get(&edge.to) {
                policy_causes
                    .entry(edge.from.clone())
                    .or_default()
                    .extend(causes.iter().cloned());
            }
        }
    }
    loop {
        let mut changed = false;
        for edge in &combined_edges {
            match edge.kind {
                PolicyEdgeKind::Calls => {
                    let Some(causes) = policy_causes.get(&edge.to).cloned() else {
                        continue;
                    };
                    let entry = policy_causes.entry(edge.from.clone()).or_default();
                    let before = entry.len();
                    entry.extend(causes);
                    changed |= entry.len() != before;
                }
                PolicyEdgeKind::Overrides => {
                    let mut causes = policy_causes.get(&edge.from).cloned().unwrap_or_default();
                    causes.extend(policy_causes.get(&edge.to).into_iter().flatten().cloned());
                    if causes.is_empty() {
                        continue;
                    }
                    for id in [&edge.from, &edge.to] {
                        let entry = policy_causes.entry(id.clone()).or_default();
                        let before = entry.len();
                        entry.extend(causes.iter().cloned());
                        changed |= entry.len() != before;
                    }
                }
                PolicyEdgeKind::Proposes | PolicyEdgeKind::BasedOn | PolicyEdgeKind::References => {
                }
            }
        }
        if !changed {
            break;
        }
    }

    let reviews = |kind| {
        policy_causes
            .iter()
            .filter_map(|(id, causes)| {
                let node = all_nodes.get(id)?;
                (node.kind == kind).then(|| {
                    (
                        id.clone(),
                        node.name.clone(),
                        causes
                            .iter()
                            .filter_map(|fragment| {
                                all_nodes.get(fragment).map(|node| node.name.clone())
                            })
                            .collect::<Vec<_>>(),
                    )
                })
            })
            .collect::<Vec<_>>()
    };
    let review_functions = reviews(PolicyNodeKind::Function)
        .into_iter()
        .map(|(id, name, fragments)| PolicyFunctionReview {
            id,
            name,
            fragments,
        })
        .collect::<Vec<_>>();
    let review_rules = reviews(PolicyNodeKind::Rule)
        .iter()
        .map(|(id, name, fragments)| PolicyRuleReview {
            id: id.clone(),
            name: name.clone(),
            fragments: fragments.clone(),
        })
        .collect::<Vec<_>>();
    let review_rule_ids = review_rules
        .iter()
        .map(|rule| rule.id.clone())
        .collect::<BTreeSet<_>>();
    let mut decision_rules = BTreeMap::<String, BTreeSet<String>>::new();
    for edge in &combined_edges {
        if edge.kind == PolicyEdgeKind::Proposes && review_rule_ids.contains(&edge.from) {
            decision_rules
                .entry(edge.to.clone())
                .or_default()
                .insert(edge.from.clone());
        }
    }
    let review_decisions = decision_rules
        .into_iter()
        .filter_map(|(id, rules)| {
            let node = all_nodes.get(&id)?;
            Some(PolicyDecisionReview {
                id,
                name: node.name.clone(),
                rules: rules
                    .iter()
                    .filter_map(|rule| all_nodes.get(rule).map(|node| node.name.clone()))
                    .collect(),
            })
        })
        .collect();

    Ok(PolicyGraphDiff {
        schema_version: POLICY_GRAPH_DIFF_SCHEMA_VERSION,
        module: current.module.clone(),
        decision: current.decision.clone(),
        fragments,
        review_functions,
        review_rules,
        review_decisions,
        added_nodes,
        removed_nodes,
        added_edges,
        removed_edges,
    })
}

/// 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, their transitively
/// called functions, the fragments used as basis by those declarations, and
/// the fragments' transitive `ref` closure.
///
/// # 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 relevant_functions = relevant_functions(program, &relevant_rules, selected.is_some());
    let relevant_fragments = relevant_fragments(
        program,
        &relevant_rules,
        &relevant_functions,
        selected.is_some(),
    );
    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),
                fragment: 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),
                    fragment: None,
                },
            );
        }
    }

    for id in &relevant_fragments {
        if let Some(declaration) = program.fragments().get(id) {
            insert_fragment(&mut nodes, id, declaration);
        }
    }
    for id in &relevant_fragments {
        let Some(declaration) = program.fragments().get(id) else {
            continue;
        };
        for reference in &declaration.refs {
            let target = normalize_name(&reference.id.value);
            if relevant_fragments.contains(&target) && program.fragments().contains_key(&target) {
                edges.insert(PolicyEdge {
                    from: fragment_id(id),
                    to: fragment_id(&target),
                    kind: PolicyEdgeKind::References,
                });
            }
        }
    }

    for function_name in &relevant_functions {
        let function = &program.derives()[function_name];
        insert_node(
            &mut nodes,
            PolicyNode {
                id: function_id(function_name),
                kind: PolicyNodeKind::Function,
                name: display_symbol_name(&function.name.value),
                fragment: None,
            },
        );
        for callee in expression_derives(program, &function.expression) {
            if relevant_functions.contains(&callee) {
                edges.insert(PolicyEdge {
                    from: function_id(function_name),
                    to: function_id(&callee),
                    kind: PolicyEdgeKind::Calls,
                });
            }
        }
        for basis in &function.basis {
            let id = normalize_name(&basis.id.value);
            if relevant_fragments.contains(&id) && program.fragments().contains_key(&id) {
                edges.insert(PolicyEdge {
                    from: function_id(function_name),
                    to: fragment_id(&id),
                    kind: PolicyEdgeKind::BasedOn,
                });
            }
        }
    }

    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),
                fragment: None,
            },
        );

        match &rule.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,
                    });
                }
            }
            Effect::Invalid { .. } => {}
        }

        for basis in &rule.basis {
            let id = normalize_name(&basis.id.value);
            if relevant_fragments.contains(&id) && program.fragments().contains_key(&id) {
                edges.insert(PolicyEdge {
                    from: rule_id(rule_name),
                    to: fragment_id(&id),
                    kind: PolicyEdgeKind::BasedOn,
                });
            }
        }
        for callee in rule_derives(program, rule) {
            if relevant_functions.contains(&callee) {
                edges.insert(PolicyEdge {
                    from: rule_id(rule_name),
                    to: function_id(&callee),
                    kind: PolicyEdgeKind::Calls,
                });
            }
        }
    }

    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::Function => "component",
                PolicyNodeKind::Fragment => "note",
            };
            let kind = match node.kind {
                PolicyNodeKind::Decision => "decision",
                PolicyNodeKind::Rule => "rule",
                PolicyNodeKind::Function => "function",
                PolicyNodeKind::Fragment => "fragment",
            };
            let label = node.fragment.as_ref().map_or_else(
                || format!("{kind}\n{}", node.name),
                |fragment| {
                    if fragment.locator == node.name {
                        format!("{kind}\n{}", node.name)
                    } else {
                        format!("{kind}\n{}\n@ {}", node.name, fragment.locator)
                    }
                },
            );
            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
    }
}

impl PolicyGraphDiff {
    /// Whether the recorded and current graphs have no observable change.
    #[must_use]
    pub fn matches(&self) -> bool {
        self.fragments.is_empty()
            && self.added_nodes.is_empty()
            && self.removed_nodes.is_empty()
            && self.added_edges.is_empty()
            && self.removed_edges.is_empty()
    }

    /// Render a concise human review report without raw source or file paths.
    #[must_use]
    pub fn render_text(&self) -> String {
        if self.matches() {
            return "policy graph matches baseline\n".to_owned();
        }
        let mut output = String::from("policy impact review\n");
        if !self.fragments.is_empty() {
            output.push_str("\nchanged fragments\n");
            for fragment in &self.fragments {
                let label = match fragment.kind {
                    PolicyFragmentChangeKind::Added => "added",
                    PolicyFragmentChangeKind::Removed => "removed",
                    PolicyFragmentChangeKind::Text => "text",
                    PolicyFragmentChangeKind::Locator => "locator",
                    PolicyFragmentChangeKind::TextAndLocator => "text + locator",
                };
                let _ = writeln!(output, "  {label}: {}", fragment.name);
                if matches!(
                    fragment.kind,
                    PolicyFragmentChangeKind::Locator | PolicyFragmentChangeKind::TextAndLocator
                ) {
                    let before = fragment
                        .before
                        .as_ref()
                        .map_or("<none>", |metadata| metadata.locator.as_str());
                    let after = fragment
                        .after
                        .as_ref()
                        .map_or("<none>", |metadata| metadata.locator.as_str());
                    let _ = writeln!(output, "    {before} -> {after}");
                }
            }
        }
        if !self.review_functions.is_empty() {
            output.push_str("\nreview functions\n");
            for function in &self.review_functions {
                let _ = writeln!(
                    output,
                    "  {} <- {}",
                    function.name,
                    function.fragments.join(", ")
                );
            }
        }
        if !self.review_rules.is_empty() {
            output.push_str("\nreview rules\n");
            for rule in &self.review_rules {
                let _ = writeln!(output, "  {} <- {}", rule.name, rule.fragments.join(", "));
            }
        }
        if !self.review_decisions.is_empty() {
            output.push_str("\nreview decisions\n");
            for decision in &self.review_decisions {
                let _ = writeln!(output, "  {}", decision.name);
            }
        }
        if !self.added_nodes.is_empty()
            || !self.removed_nodes.is_empty()
            || !self.added_edges.is_empty()
            || !self.removed_edges.is_empty()
        {
            output.push_str("\nstructural changes\n");
            for node in &self.added_nodes {
                let _ = writeln!(output, "  + {} {}", node_kind_label(node.kind), node.name);
            }
            for node in &self.removed_nodes {
                let _ = writeln!(output, "  - {} {}", node_kind_label(node.kind), node.name);
            }
            for edge in &self.added_edges {
                let _ = writeln!(
                    output,
                    "  + {} {} -> {}",
                    edge.kind.as_str(),
                    edge.from,
                    edge.to
                );
            }
            for edge in &self.removed_edges {
                let _ = writeln!(
                    output,
                    "  - {} {} -> {}",
                    edge.kind.as_str(),
                    edge.from,
                    edge.to
                );
            }
        }
        output
    }
}

const fn node_kind_label(kind: PolicyNodeKind) -> &'static str {
    match kind {
        PolicyNodeKind::Decision => "decision",
        PolicyNodeKind::Rule => "rule",
        PolicyNodeKind::Function => "function",
        PolicyNodeKind::Fragment => "fragment",
    }
}

fn node_summary(node: &PolicyNode) -> PolicyNodeSummary {
    PolicyNodeSummary {
        id: node.id.clone(),
        kind: node.kind,
        name: node.name.clone(),
    }
}

fn required_fragment_metadata<'a>(
    node: &'a PolicyNode,
    side: &'static str,
) -> Result<&'a PolicyFragmentMetadata, PolicyGraphDiffError> {
    node.fragment
        .as_ref()
        .ok_or_else(|| PolicyGraphDiffError::MalformedFragment {
            side,
            id: node.id.clone(),
        })
}

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)| {
            matches!(&rule.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 matches!(&rule.effect, Effect::Override { rule, .. }
                if proposing.contains(&normalize_name(&rule.value)))
        {
            relevant.insert(name.clone());
        }
    }
    relevant
}

fn relevant_functions(
    program: &CompiledProgram,
    rules: &BTreeSet<String>,
    filtered: bool,
) -> BTreeSet<String> {
    if !filtered {
        return program.derives().keys().cloned().collect();
    }
    let mut relevant = rules
        .iter()
        .flat_map(|rule| rule_derives(program, &program.rules()[rule]))
        .collect::<BTreeSet<_>>();
    let mut pending = relevant.iter().cloned().collect::<Vec<_>>();
    while let Some(name) = pending.pop() {
        let Some(function) = program.derives().get(&name) else {
            continue;
        };
        for callee in expression_derives(program, &function.expression) {
            if relevant.insert(callee.clone()) {
                pending.push(callee);
            }
        }
    }
    relevant
}

fn rule_derives(program: &CompiledProgram, rule: &RuleDecl) -> BTreeSet<String> {
    let mut derives = expression_derives(program, &rule.condition);
    if let Effect::Decide {
        arguments, value, ..
    } = &rule.effect
    {
        for argument in arguments {
            derives.extend(expression_derives(program, argument));
        }
        derives.extend(expression_derives(program, value));
    }
    derives
}

fn expression_derives(program: &CompiledProgram, expression: &Expr) -> BTreeSet<String> {
    let mut derives = BTreeSet::new();
    collect_expression_derives(program, expression, &mut derives);
    derives
}

fn collect_expression_derives(
    program: &CompiledProgram,
    expression: &Expr,
    derives: &mut BTreeSet<String>,
) {
    match &expression.kind {
        ExprKind::Literal(_) | ExprKind::Name(_) => {}
        ExprKind::Field { receiver, .. } => {
            collect_expression_derives(program, receiver, derives);
        }
        ExprKind::Call { callee, arguments } => {
            let name = normalize_name(&callee.value);
            if program.derives().contains_key(&name) {
                derives.insert(name);
            }
            for argument in arguments {
                collect_expression_derives(program, argument, derives);
            }
        }
        ExprKind::Unary { operand, .. } => {
            collect_expression_derives(program, operand, derives);
        }
        ExprKind::Binary { left, right, .. } => {
            collect_expression_derives(program, left, derives);
            collect_expression_derives(program, right, derives);
        }
    }
}

fn relevant_fragments(
    program: &CompiledProgram,
    rules: &BTreeSet<String>,
    functions: &BTreeSet<String>,
    filtered: bool,
) -> BTreeSet<String> {
    if !filtered {
        return program.fragments().keys().cloned().collect();
    }
    let mut relevant = rules
        .iter()
        .flat_map(|rule| program.rules()[rule].basis.iter())
        .chain(
            functions
                .iter()
                .flat_map(|function| program.derives()[function].basis.iter()),
        )
        .map(|basis| normalize_name(&basis.id.value))
        .collect::<BTreeSet<_>>();
    let mut pending = relevant.iter().cloned().collect::<Vec<_>>();
    while let Some(id) = pending.pop() {
        let Some(fragment) = program.fragments().get(&id) else {
            continue;
        };
        for reference in &fragment.refs {
            let target = normalize_name(&reference.id.value);
            if relevant.insert(target.clone()) {
                pending.push(target);
            }
        }
    }
    relevant
}

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

fn insert_fragment(
    nodes: &mut BTreeMap<String, PolicyNode>,
    id: &str,
    declaration: &crate::ast::FragmentDecl,
) {
    insert_node(
        nodes,
        PolicyNode {
            id: fragment_id(id),
            kind: PolicyNodeKind::Fragment,
            name: display_symbol_name(&declaration.id.value),
            fragment: Some(PolicyFragmentMetadata {
                locator: declaration.locator.value.clone(),
                text: declaration.text.value.clone(),
            }),
        },
    );
}

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 function_id(name: &str) -> String {
    format!("function:{}", display_symbol_name(name))
}

fn fragment_id(id: &str) -> String {
    format!("fragment:{}", display_symbol_name(id))
}

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#"mod graph

enum Result:
    Yes
    No

record Request:
    enabled: Bool

dec eligibility(r Request) -> Result
dec audit(r Request) -> Bool

law::definitions @Definitions:
    Defined terms.

law::statute @Statute:
    Policy "A"

    ref law::definitions
    rule base(r Request):
        r.enabled => eligibility(r) = Yes

law::memo @Supporting Memo:
    Supporting
    Memo

    rule exception(r Request):
        not r.enabled => eligibility(r) = No

    rule exception_override(r Request):
        not r.enabled => override law::statute::base

law::unused @Unused:
    Unused

law::audit @Audit Policy:
    Audit policy

    rule audit_rule(r Request):
        r.enabled => 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_fragment_metadata() {
        let graph = build_policy_graph(&compiled(GRAPH_SOURCE), None).unwrap();
        assert_eq!(graph.schema_version, POLICY_GRAPH_SCHEMA_VERSION);
        assert_eq!(graph.module, "graph");
        assert_eq!(graph.nodes.len(), 11);
        assert_eq!(graph.edges.len(), 9);
        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 == "fragment:law::statute")
            .unwrap();
        assert_eq!(statute.fragment.as_ref().unwrap().locator, "Statute");
        assert_eq!(statute.fragment.as_ref().unwrap().text, "Policy \"A\"\n");
        assert!(graph.nodes.iter().any(|node| {
            node.id == "fragment:law::memo"
                && node
                    .fragment
                    .as_ref()
                    .is_some_and(|fragment| fragment.text == "Supporting\nMemo\n")
        }));
        let encoded = serde_json::to_string(&graph).unwrap();
        assert!(encoded.contains("\"kind\":\"fragment\""));
        assert!(encoded.contains("\"kind\":\"based_on\""));
        assert!(encoded.contains("\"kind\":\"references\""));
        assert!(!encoded.contains("\"source\""));
        assert!(!encoded.contains("\"cites\""));
    }

    #[test]
    fn decision_filter_keeps_proposers_direct_overriders_and_their_basis() {
        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",
                "fragment:law::definitions",
                "fragment:law::memo",
                "fragment:law::statute",
                "rule:law::memo::exception",
                "rule:law::memo::exception_override",
                "rule:law::statute::base",
            ]
        );
        assert_eq!(graph.edges.len(), 7);
        assert!(!graph.nodes.iter().any(|node| {
            node.id == "decision:audit"
                || node.id == "fragment:law::audit"
                || node.id == "fragment:law::unused"
        }));
    }

    #[test]
    fn fragment_function_calls_are_graph_nodes_and_propagate_impact() {
        let source = r"mod graph

record Request:
    score: Decimal

dec eligibility(request Request) -> Bool

law::definitions:
    The base score is defined here.

law::formula:
    Eligibility uses seventy percent of the score.

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

    fn qualifies(request Request) -> Bool:
        adjusted(request) >= 70

    rule eligible(request Request):
        qualifies(request) => eligibility(request) = true
";
        let baseline = build_policy_graph(&compiled(source), Some("eligibility")).unwrap();
        assert!(baseline.nodes.iter().any(|node| {
            node.id == "function:law::formula::adjusted" && node.kind == PolicyNodeKind::Function
        }));
        assert!(baseline.edges.contains(&PolicyEdge {
            from: "rule:law::formula::eligible".into(),
            to: "function:law::formula::qualifies".into(),
            kind: PolicyEdgeKind::Calls,
        }));
        assert!(baseline.edges.contains(&PolicyEdge {
            from: "function:law::formula::adjusted".into(),
            to: "fragment:law::definitions".into(),
            kind: PolicyEdgeKind::BasedOn,
        }));

        let current = build_policy_graph(
            &compiled(&source.replace(
                "The base score is defined here.",
                "The revised base score is defined here.",
            )),
            Some("eligibility"),
        )
        .unwrap();
        let diff = diff_policy_graphs(&baseline, &current).unwrap();
        assert_eq!(
            diff.review_functions
                .iter()
                .map(|function| function.name.as_str())
                .collect::<Vec<_>>(),
            ["law::formula::adjusted", "law::formula::qualifies"]
        );
        assert_eq!(
            diff.review_rules
                .iter()
                .map(|rule| rule.name.as_str())
                .collect::<Vec<_>>(),
            ["law::formula::eligible"]
        );
        assert!(diff.render_text().contains("review functions"));
    }

    #[test]
    fn fragment_text_diff_follows_reverse_references_basis_and_overrides() {
        let baseline = build_policy_graph(&compiled(GRAPH_SOURCE), None).unwrap();
        let current_source = GRAPH_SOURCE.replace("Defined terms.", "Updated defined terms.");
        let current = build_policy_graph(&compiled(&current_source), None).unwrap();
        let diff = diff_policy_graphs(&baseline, &current).unwrap();

        assert_eq!(diff.schema_version, POLICY_GRAPH_DIFF_SCHEMA_VERSION);
        assert_eq!(diff.fragments.len(), 1);
        assert_eq!(diff.fragments[0].name, "law::definitions");
        assert_eq!(diff.fragments[0].kind, PolicyFragmentChangeKind::Text);
        assert_eq!(
            diff.review_rules
                .iter()
                .map(|rule| rule.name.as_str())
                .collect::<Vec<_>>(),
            ["law::memo::exception_override", "law::statute::base"]
        );
        assert!(
            diff.review_rules
                .iter()
                .all(|rule| { rule.fragments == ["law::definitions"] })
        );
        assert_eq!(diff.review_decisions.len(), 1);
        assert_eq!(diff.review_decisions[0].name, "eligibility");
        assert!(!diff.matches());
        let rendered = diff.render_text();
        assert!(rendered.contains("text: law::definitions"), "{rendered}");
        assert!(rendered.contains("review rules"), "{rendered}");
        assert!(!rendered.contains("Updated defined terms"), "{rendered}");
    }

    #[test]
    fn fragment_locator_diff_is_reviewable_without_calling_rules_stale() {
        let baseline = build_policy_graph(&compiled(GRAPH_SOURCE), Some("eligibility")).unwrap();
        let current_source = GRAPH_SOURCE.replace("@Statute:", "@Statute / paragraph 2:");
        let current = build_policy_graph(&compiled(&current_source), Some("eligibility")).unwrap();
        let diff = diff_policy_graphs(&baseline, &current).unwrap();

        assert_eq!(diff.fragments[0].kind, PolicyFragmentChangeKind::Locator);
        assert_eq!(
            diff.fragments[0].before.as_ref().unwrap().locator,
            "Statute"
        );
        assert_eq!(
            diff.fragments[0].after.as_ref().unwrap().locator,
            "Statute / paragraph 2"
        );
        assert!(diff.render_text().contains("policy impact review"));
        assert!(!diff.render_text().contains("stale"));
    }

    #[test]
    fn identical_policy_graphs_match_and_incompatible_scopes_are_rejected() {
        let graph = build_policy_graph(&compiled(GRAPH_SOURCE), None).unwrap();
        let diff = diff_policy_graphs(&graph, &graph).unwrap();
        assert!(diff.matches());
        assert_eq!(diff.render_text(), "policy graph matches baseline\n");

        let filtered = build_policy_graph(&compiled(GRAPH_SOURCE), Some("eligibility")).unwrap();
        assert!(matches!(
            diff_policy_graphs(&graph, &filtered),
            Err(PolicyGraphDiffError::DecisionMismatch { .. })
        ));

        let mut malformed = graph.clone();
        malformed
            .nodes
            .iter_mut()
            .find(|node| node.kind == PolicyNodeKind::Fragment)
            .unwrap()
            .fragment = None;
        assert!(matches!(
            diff_policy_graphs(&malformed, &graph),
            Err(PolicyGraphDiffError::MalformedFragment {
                side: "baseline",
                ..
            })
        ));
    }

    #[test]
    fn declaration_order_does_not_change_the_graph() {
        let first = build_policy_graph(&compiled(GRAPH_SOURCE), None).unwrap();
        let reordered = GRAPH_SOURCE.replace(
            "dec eligibility(r Request) -> Result\ndec audit(r Request) -> Bool",
            "dec audit(r Request) -> Bool\ndec eligibility(r Request) -> 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 mut graph = build_policy_graph(&compiled(GRAPH_SOURCE), Some("eligibility")).unwrap();
        graph
            .nodes
            .iter_mut()
            .find(|node| node.kind == PolicyNodeKind::Fragment)
            .unwrap()
            .name = "Policy \"A\"\nC:\\rules".into();
        let dot = graph.render_dot();
        assert!(dot.starts_with("digraph policy {\n  rankdir=LR;\n"));
        assert!(dot.contains("Policy \\\"A\\\""));
        assert!(dot.contains("C:\\\\rules"));
        assert!(dot.contains("Policy \\\"A\\\"\\nC:"));
        assert!(dot.contains("[label=\"overrides\"]"));
        assert!(dot.contains("[label=\"based_on\"]"));
        assert!(dot.contains("@ Statute"));
        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"
        );
    }
}