silk/

ontology.rs

use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, HashSet};

use crate::entry::Value;

/// Every constraint name the validator enforces. Single source of truth:
/// `validate_constraints` dispatches on it, `fingerprint` emits a fact for
/// each, and `validate_self` rejects any other name. Adding a constraint
/// means adding it here, which makes the other two fail until they cover it.
pub const ENFORCED_CONSTRAINTS: [&str; 8] = [
    "enum",
    "min",
    "max",
    "min_exclusive",
    "max_exclusive",
    "min_length",
    "max_length",
    "pattern",
];

/// Prefix reserved for constraints this validator does not enforce. Declaring
/// one is an explicit statement that nothing will check it (S3); any other
/// unknown name is a typo and is rejected.
pub const UNENFORCED_CONSTRAINT_PREFIX: &str = "x_";

/// Version of the fingerprint formula. Bumped whenever the emitter changes
/// what facts it produces, so that an emitter upgrade is a nameable condition
/// rather than a false fork (S10). v1 emitted a fact for `enum` only.
pub const FINGERPRINT_VERSION: u32 = 2;

/// What a materialization pass enforces.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ValidationMode {
    /// Everything: required properties, declared types, constraints, endpoints.
    Full,
    /// Everything except required-property presence. Used only for a
    /// checkpoint's synthetic inner ops, whose `AddNode` carries an empty
    /// property map by design (EXP-02) with the values arriving as separate
    /// `UpdateProperty` ops. Narrower than the old blanket bypass (S2):
    /// declared types, constraints and edge endpoints are still enforced.
    SkipRequired,
}

/// The type of a property value.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum ValueType {
    String,
    Int,
    Float,
    Bool,
    List,
    Map,
    /// Accept any Value variant.
    Any,
}

/// Definition of a single property on a node or edge type.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct PropertyDef {
    pub value_type: ValueType,
    #[serde(default)]
    pub required: bool,
    #[serde(default)]
    pub description: Option<String>,
    /// Extensible constraints — validated at write time.
    /// Built-in: "enum" (list of allowed values), "min"/"max" (numeric range).
    /// Community contributions welcome for additional constraint types.
    #[serde(default)]
    pub constraints: Option<BTreeMap<String, serde_json::Value>>,
}

/// Definition of a subtype within a node type (D-024).
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct SubtypeDef {
    #[serde(default)]
    pub description: Option<String>,
    #[serde(default)]
    pub properties: BTreeMap<String, PropertyDef>,
}

/// Definition of a node type in the ontology.
///
/// If `subtypes` is `Some`, then `add_node` requires a `subtype` parameter
/// and properties are validated against the subtype's definition.
/// If `subtypes` is `None`, the type works as before (D-024 backward compat).
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NodeTypeDef {
    #[serde(default)]
    pub description: Option<String>,
    #[serde(default)]
    pub properties: BTreeMap<String, PropertyDef>,
    /// Optional subtype definitions. When present, `add_node` must specify
    /// a subtype and properties are validated per-subtype (D-024).
    #[serde(default)]
    pub subtypes: Option<BTreeMap<String, SubtypeDef>>,
    /// RDFS-level class hierarchy (Step 2). If set, this type is a subclass
    /// of `parent_type`. Queries for the parent type include this type.
    /// Edge constraints accepting the parent type also accept this type.
    /// Properties are inherited from the parent (child overrides on conflict).
    #[serde(default)]
    pub parent_type: Option<String>,
}

/// Definition of an edge type in the ontology.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct EdgeTypeDef {
    #[serde(default)]
    pub description: Option<String>,
    /// Which node types can be the source of this edge.
    pub source_types: Vec<String>,
    /// Which node types can be the target of this edge.
    pub target_types: Vec<String>,
    #[serde(default)]
    pub properties: BTreeMap<String, PropertyDef>,
}

/// Immutable ontology — the vocabulary and rules of a Silk graph.
///
/// Defined once at genesis, locked forever. Every operation is validated
/// against this ontology before being appended to the DAG.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct Ontology {
    pub node_types: BTreeMap<String, NodeTypeDef>,
    pub edge_types: BTreeMap<String, EdgeTypeDef>,
}

/// Result of comparing two ontologies for sync compatibility.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Compatibility {
    /// Same resolved ontology (identical hash).
    Identical,
    /// Local contains everything remote has, plus more, and nothing the
    /// remote already holds stops validating. Safe to merge.
    Superset,
    /// Local is a superset on the declarations, but the extra facts include a
    /// requirement the remote's data was never held to. Adopting this ontology
    /// would quarantine entries the remote considers valid.
    ///
    /// This is reported instead of `Superset` so a consumer that gates an
    /// automatic migration on `"superset"` falls through to its refuse branch
    /// rather than migrating into data loss.
    DestructiveSuperset,
    /// Remote has types/properties local doesn't have yet. ExtendOntology
    /// entries in the sync payload will resolve the gap.
    Subset,
    /// Neither is a superset. Incompatible fork, cannot be resolved
    /// by additive evolution alone.
    Divergent,
}

impl Ontology {
    /// BLAKE3 hash of the canonical JSON representation.
    ///
    /// Two ontologies with identical resolved state produce the same hash,
    /// regardless of how they got there (genesis path, extension order).
    /// BTreeMap gives deterministic key ordering.
    pub fn content_hash(&self) -> [u8; 32] {
        let json = serde_json::to_string(self).expect("ontology serialization should not fail");
        *blake3::hash(json.as_bytes()).as_bytes()
    }

    /// Set of atomic facts about this ontology's structure.
    ///
    /// Each fact is a string: "type:Animal", "prop:Animal:name:string:required",
    /// "edge:LIVES_AT", "edge:LIVES_AT:src:Animal", "subtype:Entity:Project", etc.
    ///
    /// Under additive-only evolution, a newer ontology's fingerprint is a strict
    /// superset of an older one's. Set comparison gives the compatibility verdict.
    pub fn fingerprint(&self) -> HashSet<String> {
        let mut facts = HashSet::new();

        // S10: identify the emitter's formula, so an upgrade is distinguishable
        // from a real fork.
        facts.insert(format!("fingerprint_version:{FINGERPRINT_VERSION}"));

        for (type_name, type_def) in &self.node_types {
            facts.insert(format!("type:{type_name}"));

            if let Some(parent) = &type_def.parent_type {
                facts.insert(format!("type:{type_name}:parent:{parent}"));
            }

            // H3: emit membership from the RESOLVED table, not the declaration
            // syntax, so a slot attached by any route (own, parent chain) is a
            // fact on the type that actually carries it.
            for (prop_name, prop_def) in &self.effective_properties(type_name) {
                let req = if prop_def.required {
                    "required"
                } else {
                    "optional"
                };
                let vt = format!("{:?}", prop_def.value_type).to_lowercase();
                facts.insert(format!("prop:{type_name}:{prop_name}:{vt}:{req}"));
                Self::fingerprint_constraints(&mut facts, type_name, prop_name, prop_def);
            }

            // Subtypes
            if let Some(subtypes) = &type_def.subtypes {
                for (sub_name, sub_def) in subtypes {
                    facts.insert(format!("subtype:{type_name}:{sub_name}"));
                    for (prop_name, prop_def) in &sub_def.properties {
                        let req = if prop_def.required {
                            "required"
                        } else {
                            "optional"
                        };
                        let vt = format!("{:?}", prop_def.value_type).to_lowercase();
                        facts.insert(format!(
                            "subprop:{type_name}:{sub_name}:{prop_name}:{vt}:{req}"
                        ));
                        Self::fingerprint_constraints(
                            &mut facts,
                            &format!("{type_name}:{sub_name}"),
                            prop_name,
                            prop_def,
                        );
                    }
                }
            }
        }

        for (edge_name, edge_def) in &self.edge_types {
            facts.insert(format!("edge:{edge_name}"));
            for src in &edge_def.source_types {
                facts.insert(format!("edge:{edge_name}:src:{src}"));
            }
            for tgt in &edge_def.target_types {
                facts.insert(format!("edge:{edge_name}:tgt:{tgt}"));
            }
            // H3: edge properties are validated (validate_edge ->
            // validate_properties) and so must be fingerprinted.
            for (prop_name, prop_def) in &edge_def.properties {
                let req = if prop_def.required {
                    "required"
                } else {
                    "optional"
                };
                let vt = format!("{:?}", prop_def.value_type).to_lowercase();
                facts.insert(format!("edgeprop:{edge_name}:{prop_name}:{vt}:{req}"));
                Self::fingerprint_constraints(
                    &mut facts,
                    &format!("edge:{edge_name}"),
                    prop_name,
                    prop_def,
                );
            }
        }

        facts
    }

    /// Facts held here that would invalidate data the foreign peer considers
    /// valid, as human-readable lines.
    ///
    /// Works on fingerprints alone, so it needs no access to the peer's oplog.
    /// That is also its limit: a change whose destructiveness depends on
    /// values rather than declarations is invisible here. Declaring a property
    /// that existing nodes already carry as an undeclared extra, under a type
    /// that does not match, is the known case. `preview_extension` sees that
    /// one because it replays.
    pub fn destructive_changes(&self, foreign_fingerprint: &HashSet<String>) -> Vec<String> {
        Self::destructive_facts(&self.fingerprint(), foreign_fingerprint)
    }

    /// Shared by `check_compatibility` and `destructive_changes`.
    ///
    /// Three fact shapes matter, mirroring what `merge_extension` refuses:
    /// a required property the peer does not hold as required, on a type the
    /// peer knows; and the first subtype on a type the peer holds without any.
    fn destructive_facts(mine: &HashSet<String>, foreign: &HashSet<String>) -> Vec<String> {
        let mut out = Vec::new();

        // `prop:T:P:vt:required`, `edgeprop:E:P:vt:required`,
        // `subprop:T:S:P:vt:required`. Strip the "required" suffix and the
        // value type to get the slot, then ask whether the peer holds that
        // same slot as required. Absent or optional both mean the peer's data
        // was never held to the requirement.
        for fact in mine.difference(foreign) {
            let Some(slot) = fact.strip_suffix(":required") else {
                continue;
            };
            let (kind, prefix, rest) = match slot.split_once(':') {
                Some(("prop", rest)) => ("node type", "prop", rest),
                Some(("edgeprop", rest)) => ("edge type", "edgeprop", rest),
                Some(("subprop", rest)) => ("subtype", "subprop", rest),
                _ => continue,
            };
            // `rest` is "T:P:vt", or "T:S:P:vt" for subprop. Drop the value
            // type, then split the owner from the property name.
            let Some((owner_and_prop, _value_type)) = rest.rsplit_once(':') else {
                continue;
            };
            let Some((owner, property)) = owner_and_prop.rsplit_once(':') else {
                continue;
            };

            // Only a type the peer already knows can hold peer data.
            let peer_knows_owner = foreign.contains(&format!("type:{owner}"))
                || foreign.contains(&format!("edge:{owner}"))
                || owner
                    .split_once(':')
                    .is_some_and(|(t, _)| foreign.contains(&format!("type:{t}")));
            if !peer_knows_owner {
                continue;
            }

            // Same slot, any value type, required on the peer too.
            let head = format!("{prefix}:{owner_and_prop}");
            let peer_requires_it = foreign.iter().any(|f| {
                f.strip_suffix(":required")
                    .and_then(|s| s.rsplit_once(':'))
                    .is_some_and(|(h, _)| h == head)
            });
            if peer_requires_it {
                continue;
            }

            out.push(format!(
                "required property '{property}' on {kind} '{owner}', which the peer \
                 does not require: its entries written without it would quarantine"
            ));
        }

        // The first subtype on a type the peer holds with none.
        let mut flipped: Vec<&str> = Vec::new();
        for fact in mine.difference(foreign) {
            let Some((type_name, _sub)) = fact
                .strip_prefix("subtype:")
                .and_then(|rest| rest.split_once(':'))
            else {
                continue;
            };
            if !foreign.contains(&format!("type:{type_name}")) || flipped.contains(&type_name) {
                continue;
            }
            let peer_has_subtypes = foreign
                .iter()
                .any(|f| f.starts_with(&format!("subtype:{type_name}:")));
            if !peer_has_subtypes {
                flipped.push(type_name);
            }
        }
        for type_name in flipped {
            out.push(format!(
                "node type '{type_name}' declares subtypes and the peer's does not: \
                 every node the peer wrote without one would quarantine"
            ));
        }

        out.sort();
        out
    }

    /// Compare this ontology against a foreign peer's hash and fingerprint.
    pub fn check_compatibility(
        &self,
        foreign_hash: &[u8; 32],
        foreign_fingerprint: &HashSet<String>,
    ) -> Compatibility {
        if &self.content_hash() == foreign_hash {
            return Compatibility::Identical;
        }

        let my_fp = self.fingerprint();

        // H3: ordered superset-then-subset. Equal fact sets with different
        // hashes used to fall into a `(true, true) => Identical` arm commented
        // "shouldn't happen" — which is exactly what fired whenever the
        // emitter was blind to a constraint the validator enforced. With the
        // emitter complete, equal facts and a differing hash is a genuine
        // divergence and must be reported as one.
        if my_fp == *foreign_fingerprint {
            return Compatibility::Divergent;
        }
        if foreign_fingerprint.is_subset(&my_fp) {
            if Self::destructive_facts(&my_fp, foreign_fingerprint).is_empty() {
                return Compatibility::Superset;
            }
            return Compatibility::DestructiveSuperset;
        }
        if my_fp.is_subset(foreign_fingerprint) {
            return Compatibility::Subset;
        }
        Compatibility::Divergent
    }

    /// Emit one fact per declared constraint, walking the constraint map the
    /// validator consults rather than a hand-written parallel list (H3).
    /// Values are serialized canonically so differing bounds differ as facts.
    fn fingerprint_constraints(
        facts: &mut HashSet<String>,
        type_name: &str,
        prop_name: &str,
        prop_def: &PropertyDef,
    ) {
        let Some(constraints) = &prop_def.constraints else {
            return;
        };
        for (cname, cvalue) in constraints {
            match cvalue {
                // Enum members are emitted individually so that adding a member
                // is a superset rather than a divergence.
                serde_json::Value::Array(items) if cname == "enum" => {
                    for val in items {
                        let rendered = match val.as_str() {
                            Some(s) => s.to_string(),
                            None => val.to_string(),
                        };
                        facts.insert(format!(
                            "constraint:{type_name}:{prop_name}:enum:{rendered}"
                        ));
                    }
                }
                other => {
                    facts.insert(format!(
                        "constraint:{type_name}:{prop_name}:{cname}:{other}"
                    ));
                }
            }
        }
    }
}

/// Validation errors returned when an operation violates the ontology.
#[derive(Debug, Clone, PartialEq)]
pub enum ValidationError {
    UnknownNodeType(String),
    UnknownEdgeType(String),
    InvalidSource {
        edge_type: String,
        node_type: String,
        allowed: Vec<String>,
    },
    InvalidTarget {
        edge_type: String,
        node_type: String,
        allowed: Vec<String>,
    },
    MissingRequiredProperty {
        type_name: String,
        property: String,
    },
    WrongPropertyType {
        type_name: String,
        property: String,
        expected: ValueType,
        got: String,
    },
    UnknownProperty {
        type_name: String,
        property: String,
    },
    MissingSubtype {
        node_type: String,
        allowed: Vec<String>,
    },
    UnknownSubtype {
        node_type: String,
        subtype: String,
        allowed: Vec<String>,
    },
    UnexpectedSubtype {
        node_type: String,
        subtype: String,
    },
    /// A property value violates a constraint (enum, range, etc.)
    ConstraintViolation {
        type_name: String,
        property: String,
        constraint: String,
        message: String,
    },
    /// A constraint name no validator enforces (S3): silently inert otherwise.
    UnknownConstraint {
        type_name: String,
        property: String,
        constraint: String,
        known: Vec<String>,
    },
}

impl std::fmt::Display for ValidationError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            ValidationError::UnknownNodeType(t) => write!(f, "unknown node type: '{t}'"),
            ValidationError::UnknownEdgeType(t) => write!(f, "unknown edge type: '{t}'"),
            ValidationError::InvalidSource {
                edge_type,
                node_type,
                allowed,
            } => write!(
                f,
                "edge '{edge_type}' cannot have source type '{node_type}' (allowed: {allowed:?})"
            ),
            ValidationError::InvalidTarget {
                edge_type,
                node_type,
                allowed,
            } => write!(
                f,
                "edge '{edge_type}' cannot have target type '{node_type}' (allowed: {allowed:?})"
            ),
            ValidationError::MissingRequiredProperty {
                type_name,
                property,
            } => write!(f, "'{type_name}' requires property '{property}'"),
            ValidationError::WrongPropertyType {
                type_name,
                property,
                expected,
                got,
            } => write!(
                f,
                "'{type_name}'.'{property}' expects {expected:?}, got {got}"
            ),
            ValidationError::UnknownProperty {
                type_name,
                property,
            } => write!(f, "'{type_name}' has no property '{property}' in ontology"),
            ValidationError::MissingSubtype { node_type, allowed } => {
                write!(f, "'{node_type}' requires a subtype (allowed: {allowed:?})")
            }
            ValidationError::UnknownSubtype {
                node_type,
                subtype,
                allowed,
            } => write!(
                f,
                "'{node_type}' has no subtype '{subtype}' (allowed: {allowed:?})"
            ),
            ValidationError::UnexpectedSubtype { node_type, subtype } => write!(
                f,
                "'{node_type}' does not define subtypes, but got subtype '{subtype}'"
            ),
            ValidationError::ConstraintViolation {
                type_name,
                property,
                constraint,
                message,
            } => write!(
                f,
                "'{type_name}'.'{property}' violates constraint '{constraint}': {message}"
            ),
            ValidationError::UnknownConstraint {
                type_name,
                property,
                constraint,
                known,
            } => write!(
                f,
                "'{type_name}'.'{property}' declares unknown constraint '{constraint}' \
                 (enforced: {}); nothing would check it. Prefix it '{}' to declare it \
                 deliberately unenforced.",
                known.join(", "),
                UNENFORCED_CONSTRAINT_PREFIX
            ),
        }
    }
}

/// An additive ontology extension — monotonic evolution only (R-03).
#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
pub struct OntologyExtension {
    /// New node types to add.
    #[serde(default)]
    pub node_types: BTreeMap<String, NodeTypeDef>,
    /// New edge types to add.
    #[serde(default)]
    pub edge_types: BTreeMap<String, EdgeTypeDef>,
    /// Updates to existing node types (add properties, subtypes, relax required).
    #[serde(default)]
    pub node_type_updates: BTreeMap<String, NodeTypeUpdate>,
    /// Updates to existing edge types (widen endpoint bindings, add properties).
    ///
    /// Added after a downstream outage: binding a new source or target type to
    /// an edge type that already exists had no vocabulary at all, and the
    /// attempt was silently accepted as a no-op. Widening is monotonic — the
    /// edge type only ever accepts more — so it is safe for convergence.
    ///
    /// NOTE: this field is appended LAST. `OntologyExtension` serializes as a
    /// positional array, so field order is the wire format; a new field must
    /// go at the end, and older builds cannot read extensions that carry it.
    #[serde(default)]
    pub edge_type_updates: BTreeMap<String, EdgeTypeUpdate>,
}

/// Monotonic update to an existing edge type.
#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
pub struct EdgeTypeUpdate {
    /// Node types to add to `source_types` (widening only).
    #[serde(default)]
    pub add_source_types: Vec<String>,
    /// Node types to add to `target_types` (widening only).
    #[serde(default)]
    pub add_target_types: Vec<String>,
    /// New optional properties on the edge type.
    #[serde(default)]
    pub add_properties: BTreeMap<String, PropertyDef>,
}

impl EdgeTypeUpdate {
    fn is_empty(&self) -> bool {
        self.add_source_types.is_empty()
            && self.add_target_types.is_empty()
            && self.add_properties.is_empty()
    }
}

/// Additive update to an existing node type.
#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
pub struct NodeTypeUpdate {
    /// New optional properties to add.
    #[serde(default)]
    pub add_properties: BTreeMap<String, PropertyDef>,
    /// Properties to relax from required to optional.
    #[serde(default)]
    pub relax_properties: Vec<String>,
    /// New subtypes to add.
    #[serde(default)]
    pub add_subtypes: BTreeMap<String, SubtypeDef>,
}

/// Errors from monotonic ontology extension (R-03).
#[derive(Debug, Clone, PartialEq)]
pub enum MonotonicityError {
    DuplicateNodeType(String),
    DuplicateEdgeType(String),
    UnknownNodeType(String),
    /// An `edge_type_updates` entry names an edge type that does not exist.
    UnknownEdgeType(String),
    /// A new endpoint binding references a node type that does not exist.
    UnknownBindingType {
        edge_type: String,
        node_type: String,
    },
    /// A binding that is already present — the extension would change nothing.
    DuplicateBinding {
        edge_type: String,
        node_type: String,
    },
    /// The extension parses but expresses no change (S-noop). Accepting it
    /// writes a no-op entry to the replicated log and tells the caller the
    /// schema evolved when it has not.
    EmptyExtension,
    DuplicateProperty {
        type_name: String,
        property: String,
    },
    UnknownProperty {
        type_name: String,
        property: String,
    },
    /// A required property introduced onto a type that already exists. Every
    /// entry of that type written without it was valid when written and would
    /// quarantine on the next materialization.
    RequiredPropertyOnExistingType {
        kind: &'static str,
        type_name: String,
        property: String,
    },
    /// Subtypes introduced onto a node type that had none. Once a type
    /// declares subtypes, a node without one fails validation, so every node
    /// of that type written so far would quarantine.
    SubtypesOnSubtypelessType {
        type_name: String,
        subtypes: Vec<String>,
    },
    /// Wraps a ValidationError from validate_self() after merge.
    ValidationFailed(ValidationError),
}

impl std::fmt::Display for MonotonicityError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            MonotonicityError::DuplicateNodeType(t) => {
                write!(f, "node type '{t}' already exists")
            }
            MonotonicityError::DuplicateEdgeType(t) => {
                write!(f, "edge type '{t}' already exists")
            }
            MonotonicityError::UnknownNodeType(t) => {
                write!(f, "cannot update unknown node type '{t}'")
            }
            MonotonicityError::UnknownEdgeType(t) => {
                write!(f, "cannot update unknown edge type '{t}'")
            }
            MonotonicityError::UnknownBindingType {
                edge_type,
                node_type,
            } => write!(
                f,
                "edge type '{edge_type}' cannot bind to unknown node type '{node_type}'"
            ),
            MonotonicityError::DuplicateBinding {
                edge_type,
                node_type,
            } => write!(
                f,
                "edge type '{edge_type}' already binds '{node_type}'; this extension \
                 would change nothing"
            ),
            MonotonicityError::RequiredPropertyOnExistingType {
                kind,
                type_name,
                property,
            } => write!(
                f,
                "cannot add required property '{property}' to {kind} '{type_name}': \
                 entries written before this extension did not have to carry it, \
                 and every one of them would be quarantined on the next \
                 materialization, silently. Add it as optional (required: false) \
                 instead, or declare a new type."
            ),
            MonotonicityError::SubtypesOnSubtypelessType {
                type_name,
                subtypes,
            } => write!(
                f,
                "cannot add subtypes {subtypes:?} to node type '{type_name}', which \
                 declares none: once a type has subtypes every node of it must name \
                 one, so every '{type_name}' node written so far would be quarantined \
                 on the next materialization, silently. Subtypes have to be declared \
                 when the type is created."
            ),
            MonotonicityError::EmptyExtension => write!(
                f,
                "extension expresses no change; nothing would be added. An extension \
                 that changes nothing must not be written to the log"
            ),
            MonotonicityError::DuplicateProperty {
                type_name,
                property,
            } => {
                write!(f, "property '{property}' already exists on '{type_name}'")
            }
            MonotonicityError::UnknownProperty {
                type_name,
                property,
            } => {
                write!(
                    f,
                    "property '{property}' does not exist on '{type_name}' (cannot relax)"
                )
            }
            MonotonicityError::ValidationFailed(e) => {
                write!(f, "ontology validation failed after merge: {e}")
            }
        }
    }
}

impl Ontology {
    // -- RDFS-level class hierarchy (Step 2) --

    /// Return all ancestor types of `node_type` (transitive parent_type chain).
    /// Does not include `node_type` itself. Returns empty vec if no parent.
    pub fn ancestors(&self, node_type: &str) -> Vec<&str> {
        let mut result = Vec::new();
        let mut current = node_type;
        // Guard against cycles (max 100 levels — no real ontology is deeper)
        for _ in 0..100 {
            match self
                .node_types
                .get(current)
                .and_then(|d| d.parent_type.as_deref())
            {
                Some(parent) => {
                    result.push(parent);
                    current = parent;
                }
                None => break,
            }
        }
        result
    }

    /// Return all descendant types of `node_type` (types whose ancestor chain includes it).
    /// Does not include `node_type` itself.
    pub fn descendants(&self, node_type: &str) -> Vec<&str> {
        // Collect all types that have node_type anywhere in their ancestor chain.
        self.node_types
            .iter()
            .filter(|(name, _)| {
                name.as_str() != node_type && self.ancestors(name).contains(&node_type)
            })
            .map(|(name, _)| name.as_str())
            .collect()
    }

    /// Check if `child_type` is the same as or a descendant of `parent_type`.
    pub fn is_subtype_of(&self, child_type: &str, parent_type: &str) -> bool {
        child_type == parent_type || self.ancestors(child_type).contains(&parent_type)
    }

    /// Get all properties for a type, including those inherited from ancestors.
    /// Ancestors' properties are applied first (most general), then overridden
    /// by more specific types. Same order as Python MRO: parent first, child overrides.
    pub fn effective_properties(&self, node_type: &str) -> BTreeMap<String, PropertyDef> {
        let mut chain: Vec<&str> = self.ancestors(node_type);
        chain.reverse(); // most general first
        chain.push(node_type);

        let mut props = BTreeMap::new();
        for t in chain {
            if let Some(def) = self.node_types.get(t) {
                for (k, v) in &def.properties {
                    props.insert(k.clone(), v.clone());
                }
            }
        }
        props
    }

    /// Validate that a node type exists and its properties conform.
    ///
    /// If the type defines subtypes (D-024), `subtype` must be `Some` and
    /// properties are validated against the subtype's definition.
    /// If the type does not define subtypes, `subtype` must be `None`.
    pub fn validate_node(
        &self,
        node_type: &str,
        subtype: Option<&str>,
        properties: &BTreeMap<String, Value>,
    ) -> Result<(), ValidationError> {
        self.validate_node_mode(node_type, subtype, properties, ValidationMode::Full)
    }

    /// `validate_node` with an explicit enforcement mode (S2).
    pub fn validate_node_mode(
        &self,
        node_type: &str,
        subtype: Option<&str>,
        properties: &BTreeMap<String, Value>,
        mode: ValidationMode,
    ) -> Result<(), ValidationError> {
        let def = self
            .node_types
            .get(node_type)
            .ok_or_else(|| ValidationError::UnknownNodeType(node_type.to_string()))?;

        // Step 2: use effective_properties (includes inherited from ancestors)
        let base_props = self.effective_properties(node_type);

        match (&def.subtypes, subtype) {
            // Type has subtypes and caller provided one
            (Some(subtypes), Some(st)) => {
                match subtypes.get(st) {
                    Some(st_def) => {
                        // Known subtype — merge inherited + type-level + subtype-level
                        let mut merged = base_props;
                        merged.extend(st_def.properties.clone());
                        validate_properties(node_type, &merged, properties, mode)
                    }
                    None => {
                        // D-026: unknown subtype — validate inherited + type-level only
                        validate_properties(node_type, &base_props, properties, mode)
                    }
                }
            }
            // Type has subtypes but caller didn't provide one — error
            (Some(subtypes), None) => Err(ValidationError::MissingSubtype {
                node_type: node_type.to_string(),
                allowed: subtypes.keys().cloned().collect(),
            }),
            // D-026: accept subtypes even if type doesn't declare any
            (None, Some(_st)) => validate_properties(node_type, &base_props, properties, mode),
            // Type has no subtypes and caller didn't provide one — validate as before
            (None, None) => validate_properties(node_type, &base_props, properties, mode),
        }
    }

    /// Validate that an edge type exists, source/target types are allowed,
    /// and properties conform.
    pub fn validate_edge(
        &self,
        edge_type: &str,
        source_node_type: &str,
        target_node_type: &str,
        properties: &BTreeMap<String, Value>,
    ) -> Result<(), ValidationError> {
        self.validate_edge_mode(
            edge_type,
            source_node_type,
            target_node_type,
            properties,
            ValidationMode::Full,
        )
    }

    /// `validate_edge` with an explicit enforcement mode (S2).
    pub fn validate_edge_mode(
        &self,
        edge_type: &str,
        source_node_type: &str,
        target_node_type: &str,
        properties: &BTreeMap<String, Value>,
        mode: ValidationMode,
    ) -> Result<(), ValidationError> {
        let def = self
            .edge_types
            .get(edge_type)
            .ok_or_else(|| ValidationError::UnknownEdgeType(edge_type.to_string()))?;

        // Hierarchy-aware: accept if actual type IS one of the allowed types
        // OR is a descendant of any allowed type (RDFS rdfs9).
        if !def
            .source_types
            .iter()
            .any(|t| self.is_subtype_of(source_node_type, t))
        {
            return Err(ValidationError::InvalidSource {
                edge_type: edge_type.to_string(),
                node_type: source_node_type.to_string(),
                allowed: def.source_types.clone(),
            });
        }

        if !def
            .target_types
            .iter()
            .any(|t| self.is_subtype_of(target_node_type, t))
        {
            return Err(ValidationError::InvalidTarget {
                edge_type: edge_type.to_string(),
                node_type: target_node_type.to_string(),
                allowed: def.target_types.clone(),
            });
        }

        validate_properties(edge_type, &def.properties, properties, mode)
    }

    /// Validate a single property update on an EDGE (H2). The node-shaped
    /// `validate_property_update` cannot serve here: callers that looked up
    /// only nodes silently skipped validation for every edge property.
    pub fn validate_edge_property_update(
        &self,
        edge_type: &str,
        key: &str,
        value: &Value,
    ) -> Result<(), ValidationError> {
        let def = match self.edge_types.get(edge_type) {
            Some(d) => d,
            None => return Ok(()), // Unknown edge type — can't validate
        };
        // D-026: unknown properties accepted without validation.
        let prop_def = match def.properties.get(key) {
            Some(d) => d,
            None => return Ok(()),
        };
        if prop_def.value_type != ValueType::Any && !value_matches_type(value, &prop_def.value_type)
        {
            return Err(ValidationError::WrongPropertyType {
                type_name: edge_type.to_string(),
                property: key.to_string(),
                expected: prop_def.value_type.clone(),
                got: value_type_name(value).to_string(),
            });
        }
        if let Some(constraints) = &prop_def.constraints {
            validate_constraints(edge_type, key, value, constraints)?;
        }
        Ok(())
    }

    /// Validate a single property update against the ontology.
    /// Checks that the value type matches the property definition.
    /// Unknown properties are accepted (D-026: ontology defines minimum, not maximum).
    pub fn validate_property_update(
        &self,
        node_type: &str,
        subtype: Option<&str>,
        key: &str,
        value: &Value,
    ) -> Result<(), ValidationError> {
        let def = match self.node_types.get(node_type) {
            Some(d) => d,
            None => return Ok(()), // Unknown node type — can't validate
        };

        // Merge type-level + subtype-level property definitions
        let mut merged = def.properties.clone();
        if let (Some(subtypes), Some(st)) = (&def.subtypes, subtype) {
            if let Some(st_def) = subtypes.get(st) {
                merged.extend(st_def.properties.clone());
            }
        }

        // D-026: unknown properties accepted without validation
        let prop_def = match merged.get(key) {
            Some(d) => d,
            None => return Ok(()),
        };

        // Type check
        if prop_def.value_type != ValueType::Any && !value_matches_type(value, &prop_def.value_type)
        {
            return Err(ValidationError::WrongPropertyType {
                type_name: node_type.to_string(),
                property: key.to_string(),
                expected: prop_def.value_type.clone(),
                got: value_type_name(value).to_string(),
            });
        }

        // Constraint check
        if let Some(constraints) = &prop_def.constraints {
            validate_constraints(node_type, key, value, constraints)?;
        }

        Ok(())
    }

    /// Validate that the ontology itself is internally consistent.
    /// All source_types/target_types in edge defs must reference existing node types.
    pub fn validate_self(&self) -> Result<(), ValidationError> {
        // Validate edge source/target references
        for (edge_name, edge_def) in &self.edge_types {
            for src in &edge_def.source_types {
                if !self.node_types.contains_key(src) {
                    return Err(ValidationError::InvalidSource {
                        edge_type: edge_name.clone(),
                        node_type: src.clone(),
                        allowed: self.node_types.keys().cloned().collect(),
                    });
                }
            }
            for tgt in &edge_def.target_types {
                if !self.node_types.contains_key(tgt) {
                    return Err(ValidationError::InvalidTarget {
                        edge_type: edge_name.clone(),
                        node_type: tgt.clone(),
                        allowed: self.node_types.keys().cloned().collect(),
                    });
                }
            }
        }
        // Validate parent_type references (Step 2: class hierarchy)
        for (type_name, type_def) in &self.node_types {
            if let Some(ref parent) = type_def.parent_type {
                if !self.node_types.contains_key(parent) {
                    return Err(ValidationError::UnknownNodeType(format!(
                        "{}: parent_type '{}' does not exist",
                        type_name, parent
                    )));
                }
            }
        }
        // S3: an unknown constraint name is inert forever and invisible to the
        // fingerprint, so a typo silently disables the rule it was meant to
        // impose. Reject it here, which covers both ontology entry points
        // (construction and extension). `x_` stays available for constraints
        // this validator deliberately does not enforce.
        for (type_name, type_def) in &self.node_types {
            for (prop_name, prop_def) in &type_def.properties {
                Self::check_constraint_names(type_name, prop_name, prop_def)?;
            }
            if let Some(subtypes) = &type_def.subtypes {
                for (sub_name, sub_def) in subtypes {
                    for (prop_name, prop_def) in &sub_def.properties {
                        Self::check_constraint_names(
                            &format!("{type_name}:{sub_name}"),
                            prop_name,
                            prop_def,
                        )?;
                    }
                }
            }
        }
        for (edge_name, edge_def) in &self.edge_types {
            for (prop_name, prop_def) in &edge_def.properties {
                Self::check_constraint_names(edge_name, prop_name, prop_def)?;
            }
        }
        Ok(())
    }

    fn check_constraint_names(
        type_name: &str,
        prop_name: &str,
        prop_def: &PropertyDef,
    ) -> Result<(), ValidationError> {
        let Some(constraints) = &prop_def.constraints else {
            return Ok(());
        };
        for cname in constraints.keys() {
            if ENFORCED_CONSTRAINTS.contains(&cname.as_str())
                || cname.starts_with(UNENFORCED_CONSTRAINT_PREFIX)
            {
                continue;
            }
            return Err(ValidationError::UnknownConstraint {
                type_name: type_name.to_string(),
                property: prop_name.to_string(),
                constraint: cname.clone(),
                known: ENFORCED_CONSTRAINTS.iter().map(|s| s.to_string()).collect(),
            });
        }
        Ok(())
    }

    /// R-03: Merge an additive extension into this ontology.
    /// Only monotonic (additive) changes are allowed:
    /// - New node types (must not already exist)
    /// - New edge types (must not already exist)
    /// - Updates to existing node types: add OPTIONAL properties, relax
    ///   required→optional, add subtypes to a type that already declares some
    ///
    /// "Additive" means no entry already in the oplog stops validating. A
    /// change that is additive on the declarations but retroactively
    /// invalidates data is refused: see `RequiredPropertyOnExistingType` and
    /// `SubtypesOnSubtypelessType`.
    pub fn merge_extension(&mut self, ext: &OntologyExtension) -> Result<(), MonotonicityError> {
        // An extension that expresses no change must not be accepted: it
        // returns a hash, appends to the replicated log, and tells the caller
        // the schema evolved when nothing did.
        if ext.node_types.is_empty()
            && ext.edge_types.is_empty()
            && ext.node_type_updates.values().all(|u| {
                u.add_properties.is_empty()
                    && u.relax_properties.is_empty()
                    && u.add_subtypes.is_empty()
            })
            && ext.edge_type_updates.values().all(|u| u.is_empty())
        {
            return Err(MonotonicityError::EmptyExtension);
        }

        // Validate: new node types don't already exist
        for name in ext.node_types.keys() {
            if self.node_types.contains_key(name) {
                return Err(MonotonicityError::DuplicateNodeType(name.clone()));
            }
        }

        // Validate: new edge types don't already exist
        for name in ext.edge_types.keys() {
            if self.edge_types.contains_key(name) {
                return Err(MonotonicityError::DuplicateEdgeType(name.clone()));
            }
        }

        // Validate node_type_updates reference existing types
        for (type_name, update) in &ext.node_type_updates {
            let def = self
                .node_types
                .get(type_name)
                .ok_or_else(|| MonotonicityError::UnknownNodeType(type_name.clone()))?;

            // Validate: add_properties don't already exist
            for prop_name in update.add_properties.keys() {
                if def.properties.contains_key(prop_name) {
                    return Err(MonotonicityError::DuplicateProperty {
                        type_name: type_name.clone(),
                        property: prop_name.clone(),
                    });
                }
            }

            // Validate: relax_properties exist and are currently required
            for prop_name in &update.relax_properties {
                match def.properties.get(prop_name) {
                    Some(prop_def) if prop_def.required => {} // ok
                    Some(_) => {} // already optional — idempotent, allow it
                    None => {
                        return Err(MonotonicityError::UnknownProperty {
                            type_name: type_name.clone(),
                            property: prop_name.clone(),
                        });
                    }
                }
            }

            // A required property on a type that already exists retroactively
            // invalidates every entry written without it. Syntactically
            // additive, semantically a delete.
            for (prop_name, prop_def) in &update.add_properties {
                if prop_def.required {
                    return Err(MonotonicityError::RequiredPropertyOnExistingType {
                        kind: "node type",
                        type_name: type_name.clone(),
                        property: prop_name.clone(),
                    });
                }
            }

            // Validate: add_subtypes don't already exist (if subtypes are defined)
            if !update.add_subtypes.is_empty() {
                match def.subtypes {
                    // Going from no subtypes to some makes `subtype` mandatory
                    // where it was forbidden, so every existing node of the
                    // type stops validating.
                    None => {
                        return Err(MonotonicityError::SubtypesOnSubtypelessType {
                            type_name: type_name.clone(),
                            subtypes: update.add_subtypes.keys().cloned().collect(),
                        });
                    }
                    Some(ref existing) => {
                        for st_name in update.add_subtypes.keys() {
                            if existing.contains_key(st_name) {
                                return Err(MonotonicityError::DuplicateProperty {
                                    type_name: type_name.clone(),
                                    property: format!("subtype:{st_name}"),
                                });
                            }
                        }
                    }
                }

                // D-026 accepts a node naming a subtype the ontology has not
                // declared, validating type-level properties only. Declaring
                // that subtype with a required property quarantines it.
                for (st_name, st_def) in &update.add_subtypes {
                    for (prop_name, prop_def) in &st_def.properties {
                        if prop_def.required {
                            return Err(MonotonicityError::RequiredPropertyOnExistingType {
                                kind: "subtype",
                                type_name: format!("{type_name}:{st_name}"),
                                property: prop_name.clone(),
                            });
                        }
                    }
                }
            }
        }

        // Apply: extend node_types
        self.node_types.extend(ext.node_types.clone());

        // Validate edge_type_updates: the edge type must exist, every new
        // binding must reference a node type that exists, and a binding that
        // is already present would change nothing.
        for (edge_name, update) in &ext.edge_type_updates {
            let def = self
                .edge_types
                .get(edge_name)
                .ok_or_else(|| MonotonicityError::UnknownEdgeType(edge_name.clone()))?;

            for (bindings, existing) in [
                (&update.add_source_types, &def.source_types),
                (&update.add_target_types, &def.target_types),
            ] {
                for node_type in bindings {
                    // The node type may be arriving in this same extension.
                    if !self.node_types.contains_key(node_type)
                        && !ext.node_types.contains_key(node_type)
                    {
                        return Err(MonotonicityError::UnknownBindingType {
                            edge_type: edge_name.clone(),
                            node_type: node_type.clone(),
                        });
                    }
                    if existing.contains(node_type) {
                        return Err(MonotonicityError::DuplicateBinding {
                            edge_type: edge_name.clone(),
                            node_type: node_type.clone(),
                        });
                    }
                }
            }

            for (prop_name, prop_def) in &update.add_properties {
                if def.properties.contains_key(prop_name) {
                    return Err(MonotonicityError::DuplicateProperty {
                        type_name: edge_name.clone(),
                        property: prop_name.clone(),
                    });
                }
                if prop_def.required {
                    return Err(MonotonicityError::RequiredPropertyOnExistingType {
                        kind: "edge type",
                        type_name: edge_name.clone(),
                        property: prop_name.clone(),
                    });
                }
            }
        }

        // Apply: extend edge_types
        self.edge_types.extend(ext.edge_types.clone());

        // Apply: widen existing edge types
        for (edge_name, update) in &ext.edge_type_updates {
            let def = self.edge_types.get_mut(edge_name).unwrap(); // validated above
            def.source_types.extend(update.add_source_types.clone());
            def.target_types.extend(update.add_target_types.clone());
            def.properties.extend(update.add_properties.clone());
        }

        // Apply: update existing node types
        for (type_name, update) in &ext.node_type_updates {
            let def = self.node_types.get_mut(type_name).unwrap(); // validated above

            // Add new properties
            def.properties.extend(update.add_properties.clone());

            // Relax required → optional
            for prop_name in &update.relax_properties {
                if let Some(prop_def) = def.properties.get_mut(prop_name) {
                    prop_def.required = false;
                }
            }

            // Add subtypes
            if !update.add_subtypes.is_empty() {
                let subtypes = def.subtypes.get_or_insert_with(BTreeMap::new);
                subtypes.extend(update.add_subtypes.clone());
            }
        }

        // Validate the merged ontology is internally consistent
        self.validate_self()
            .map_err(MonotonicityError::ValidationFailed)?;

        Ok(())
    }
}

/// Validate properties against their definitions.
fn validate_properties(
    type_name: &str,
    defs: &BTreeMap<String, PropertyDef>,
    values: &BTreeMap<String, Value>,
    mode: ValidationMode,
) -> Result<(), ValidationError> {
    // Check required properties are present. Skipped only for a checkpoint's
    // synthetic inner ops, whose values arrive as separate UpdateProperty ops.
    if mode == ValidationMode::Full {
        for (prop_name, prop_def) in defs {
            if prop_def.required && !values.contains_key(prop_name) {
                return Err(ValidationError::MissingRequiredProperty {
                    type_name: type_name.to_string(),
                    property: prop_name.clone(),
                });
            }
        }
    }

    // Check all provided properties are known and correctly typed
    for (prop_name, value) in values {
        // D-026: accept unknown properties without validation.
        // The ontology defines the minimum, not the maximum.
        let prop_def = match defs.get(prop_name) {
            Some(def) => def,
            None => continue,
        };

        if prop_def.value_type != ValueType::Any {
            let actual_type = value_type_name(value);
            let expected = &prop_def.value_type;
            if !value_matches_type(value, expected) {
                return Err(ValidationError::WrongPropertyType {
                    type_name: type_name.to_string(),
                    property: prop_name.clone(),
                    expected: expected.clone(),
                    got: actual_type.to_string(),
                });
            }
        }

        // Validate constraints (if any)
        if let Some(constraints) = &prop_def.constraints {
            validate_constraints(type_name, prop_name, value, constraints)?;
        }
    }

    Ok(())
}

/// Validate a property value against its constraints.
/// Built-in constraints: "enum" (allowed values), "min"/"max" (numeric range).
/// Unknown constraint names are silently ignored — enables forward compatibility
/// with community-contributed constraint types.
fn validate_constraints(
    type_name: &str,
    prop_name: &str,
    value: &Value,
    constraints: &BTreeMap<String, serde_json::Value>,
) -> Result<(), ValidationError> {
    // "enum": list of allowed string values
    if let Some(serde_json::Value::Array(allowed)) = constraints.get("enum") {
        if let Value::String(s) = value {
            let allowed_strs: Vec<&str> = allowed.iter().filter_map(|v| v.as_str()).collect();
            if !allowed_strs.contains(&s.as_str()) {
                return constraint_err(
                    type_name,
                    prop_name,
                    "enum",
                    format!("value '{}' not in allowed set {:?}", s, allowed_strs),
                );
            }
        }
    }

    // Numeric bounds (4 variants share the same extract-compare pattern)
    check_numeric_bound(
        type_name,
        prop_name,
        value,
        constraints,
        "min",
        |n, b| n < b,
        |n, b| format!("value {} is less than minimum {}", n, b),
    )?;
    check_numeric_bound(
        type_name,
        prop_name,
        value,
        constraints,
        "max",
        |n, b| n > b,
        |n, b| format!("value {} exceeds maximum {}", n, b),
    )?;
    check_numeric_bound(
        type_name,
        prop_name,
        value,
        constraints,
        "min_exclusive",
        |n, b| n <= b,
        |n, b| format!("value {} must be greater than {}", n, b),
    )?;
    check_numeric_bound(
        type_name,
        prop_name,
        value,
        constraints,
        "max_exclusive",
        |n, b| n >= b,
        |n, b| format!("value {} must be less than {}", n, b),
    )?;

    // String length bounds
    check_string_length(
        type_name,
        prop_name,
        value,
        constraints,
        "min_length",
        |len, bound| len < bound,
        |len, bound| format!("string length {} is less than minimum {}", len, bound),
    )?;
    check_string_length(
        type_name,
        prop_name,
        value,
        constraints,
        "max_length",
        |len, bound| len > bound,
        |len, bound| format!("string length {} exceeds maximum {}", len, bound),
    )?;

    // "pattern": regex match on string values
    if let Some(serde_json::Value::String(pattern)) = constraints.get("pattern") {
        if let Value::String(s) = value {
            match regex::Regex::new(pattern) {
                Ok(re) if !re.is_match(s) => {
                    return constraint_err(
                        type_name,
                        prop_name,
                        "pattern",
                        format!("value '{}' does not match pattern '{}'", s, pattern),
                    );
                }
                Err(e) => {
                    return constraint_err(
                        type_name,
                        prop_name,
                        "pattern",
                        format!("invalid regex pattern '{}': {}", pattern, e),
                    );
                }
                _ => {}
            }
        }
    }

    // Unknown constraint names are silently ignored (forward compat).
    Ok(())
}

/// Helper: extract numeric value from a Value.
fn value_as_f64(value: &Value) -> Option<f64> {
    match value {
        Value::Int(n) => Some(*n as f64),
        Value::Float(n) => Some(*n),
        _ => None,
    }
}

/// Helper: check a numeric bound constraint.
fn check_numeric_bound(
    type_name: &str,
    prop_name: &str,
    value: &Value,
    constraints: &BTreeMap<String, serde_json::Value>,
    key: &str,
    violates: impl Fn(f64, f64) -> bool,
    msg: impl Fn(f64, f64) -> String,
) -> Result<(), ValidationError> {
    if let Some(bound_val) = constraints.get(key) {
        if let Some(bound) = bound_val.as_f64() {
            if let Some(n) = value_as_f64(value) {
                if violates(n, bound) {
                    return constraint_err(type_name, prop_name, key, msg(n, bound));
                }
            }
        }
    }
    Ok(())
}

/// Helper: check a string length constraint.
fn check_string_length(
    type_name: &str,
    prop_name: &str,
    value: &Value,
    constraints: &BTreeMap<String, serde_json::Value>,
    key: &str,
    violates: impl Fn(u64, u64) -> bool,
    msg: impl Fn(u64, u64) -> String,
) -> Result<(), ValidationError> {
    if let Some(serde_json::Value::Number(n)) = constraints.get(key) {
        if let (Some(bound), Value::String(s)) = (n.as_u64(), value) {
            if violates(s.len() as u64, bound) {
                return constraint_err(type_name, prop_name, key, msg(s.len() as u64, bound));
            }
        }
    }
    Ok(())
}

/// Helper: construct a ConstraintViolation error.
fn constraint_err(
    type_name: &str,
    prop_name: &str,
    constraint: &str,
    message: String,
) -> Result<(), ValidationError> {
    Err(ValidationError::ConstraintViolation {
        type_name: type_name.to_string(),
        property: prop_name.to_string(),
        constraint: constraint.to_string(),
        message,
    })
}

fn value_matches_type(value: &Value, expected: &ValueType) -> bool {
    matches!(
        (value, expected),
        (Value::Null, _)
            | (Value::String(_), ValueType::String)
            | (Value::Int(_), ValueType::Int)
            | (Value::Float(_), ValueType::Float)
            | (Value::Bool(_), ValueType::Bool)
            | (Value::List(_), ValueType::List)
            | (Value::Map(_), ValueType::Map)
            | (_, ValueType::Any)
    )
}

fn value_type_name(value: &Value) -> &'static str {
    match value {
        Value::Null => "null",
        Value::Bool(_) => "bool",
        Value::Int(_) => "int",
        Value::Float(_) => "float",
        Value::String(_) => "string",
        Value::List(_) => "list",
        Value::Map(_) => "map",
    }
}

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

    /// `OntologyExtension` serializes as a POSITIONAL array, so its field
    /// count is the wire format. `edge_type_updates` was appended last; a
    /// legacy 3-element extension, as written by every build up to 0.3.0,
    /// must still load. Older builds cannot read the 4-element form — that is
    /// why PROTOCOL_VERSION moved.
    #[test]
    fn legacy_three_field_extension_still_deserializes() {
        let legacy = (
            BTreeMap::<String, NodeTypeDef>::new(),
            BTreeMap::<String, EdgeTypeDef>::new(),
            BTreeMap::<String, NodeTypeUpdate>::new(),
        );
        let bytes = rmp_serde::to_vec(&legacy).unwrap();
        assert_eq!(bytes[0], 0x93, "legacy fixture is not 3 elements");

        let restored: OntologyExtension =
            rmp_serde::from_slice(&bytes).expect("legacy extension must load");
        assert!(restored.edge_type_updates.is_empty());
    }

    #[test]
    fn extension_wire_format_is_a_positional_array_of_four() {
        let ext = OntologyExtension::default();
        let bytes = rmp_serde::to_vec(&ext).unwrap();
        assert_eq!(
            bytes[0], 0x94,
            "OntologyExtension is no longer a 4-element positional array. \
             Field order and count are the wire format: append new fields at \
             the end and move PROTOCOL_VERSION."
        );
    }

    fn devops_ontology() -> Ontology {
        Ontology {
            node_types: BTreeMap::from([
                (
                    "signal".into(),
                    NodeTypeDef {
                        description: Some("Something observed".into()),
                        properties: BTreeMap::from([(
                            "severity".into(),
                            PropertyDef {
                                value_type: ValueType::String,
                                required: true,
                                description: None,
                                constraints: None,
                            },
                        )]),
                        subtypes: None,
                        parent_type: None,
                    },
                ),
                (
                    "entity".into(),
                    NodeTypeDef {
                        description: Some("Something that exists".into()),
                        properties: BTreeMap::from([
                            (
                                "status".into(),
                                PropertyDef {
                                    value_type: ValueType::String,
                                    required: false,
                                    description: None,
                                    constraints: None,
                                },
                            ),
                            (
                                "port".into(),
                                PropertyDef {
                                    value_type: ValueType::Int,
                                    required: false,
                                    description: None,
                                    constraints: None,
                                },
                            ),
                        ]),
                        subtypes: None,
                        parent_type: None,
                    },
                ),
                (
                    "rule".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::new(),
                        subtypes: None,
                        parent_type: None,
                    },
                ),
                (
                    "action".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::new(),
                        subtypes: None,
                        parent_type: None,
                    },
                ),
            ]),
            edge_types: BTreeMap::from([
                (
                    "OBSERVES".into(),
                    EdgeTypeDef {
                        description: None,
                        source_types: vec!["signal".into()],
                        target_types: vec!["entity".into()],
                        properties: BTreeMap::new(),
                    },
                ),
                (
                    "TRIGGERS".into(),
                    EdgeTypeDef {
                        description: None,
                        source_types: vec!["signal".into()],
                        target_types: vec!["rule".into()],
                        properties: BTreeMap::new(),
                    },
                ),
                (
                    "RUNS_ON".into(),
                    EdgeTypeDef {
                        description: None,
                        source_types: vec!["entity".into()],
                        target_types: vec!["entity".into()],
                        properties: BTreeMap::new(),
                    },
                ),
            ]),
        }
    }

    // --- Node validation ---

    #[test]
    fn validate_node_valid() {
        let ont = devops_ontology();
        let props = BTreeMap::from([("severity".into(), Value::String("critical".into()))]);
        assert!(ont.validate_node("signal", None, &props).is_ok());
    }

    #[test]
    fn validate_node_unknown_type() {
        let ont = devops_ontology();
        let err = ont
            .validate_node("potato", None, &BTreeMap::new())
            .unwrap_err();
        assert!(matches!(err, ValidationError::UnknownNodeType(t) if t == "potato"));
    }

    #[test]
    fn validate_node_missing_required() {
        let ont = devops_ontology();
        let err = ont
            .validate_node("signal", None, &BTreeMap::new())
            .unwrap_err();
        assert!(
            matches!(err, ValidationError::MissingRequiredProperty { property, .. } if property == "severity")
        );
    }

    #[test]
    fn validate_node_wrong_type() {
        let ont = devops_ontology();
        let props = BTreeMap::from([("severity".into(), Value::Int(5))]);
        let err = ont.validate_node("signal", None, &props).unwrap_err();
        assert!(
            matches!(err, ValidationError::WrongPropertyType { property, .. } if property == "severity")
        );
    }

    #[test]
    fn validate_node_unknown_property_accepted() {
        // D-026: unknown properties are accepted without validation
        let ont = devops_ontology();
        let props = BTreeMap::from([
            ("severity".into(), Value::String("warn".into())),
            ("bogus".into(), Value::Bool(true)),
        ]);
        assert!(ont.validate_node("signal", None, &props).is_ok());
    }

    #[test]
    fn validate_node_optional_property_absent() {
        let ont = devops_ontology();
        // entity has optional "status" — omitting it is fine
        assert!(ont.validate_node("entity", None, &BTreeMap::new()).is_ok());
    }

    #[test]
    fn validate_node_null_accepted_for_any_type() {
        let ont = devops_ontology();
        // Null is accepted for any typed property (represents absence)
        let props = BTreeMap::from([("severity".into(), Value::Null)]);
        assert!(ont.validate_node("signal", None, &props).is_ok());
    }

    // --- Edge validation ---

    #[test]
    fn validate_edge_valid() {
        let ont = devops_ontology();
        assert!(ont
            .validate_edge("OBSERVES", "signal", "entity", &BTreeMap::new())
            .is_ok());
    }

    #[test]
    fn validate_edge_unknown_type() {
        let ont = devops_ontology();
        let err = ont
            .validate_edge("FLIES_TO", "signal", "entity", &BTreeMap::new())
            .unwrap_err();
        assert!(matches!(err, ValidationError::UnknownEdgeType(t) if t == "FLIES_TO"));
    }

    #[test]
    fn validate_edge_invalid_source() {
        let ont = devops_ontology();
        // OBSERVES requires source=signal, not entity
        let err = ont
            .validate_edge("OBSERVES", "entity", "entity", &BTreeMap::new())
            .unwrap_err();
        assert!(matches!(err, ValidationError::InvalidSource { .. }));
    }

    #[test]
    fn validate_edge_invalid_target() {
        let ont = devops_ontology();
        // OBSERVES requires target=entity, not signal
        let err = ont
            .validate_edge("OBSERVES", "signal", "signal", &BTreeMap::new())
            .unwrap_err();
        assert!(matches!(err, ValidationError::InvalidTarget { .. }));
    }

    // --- Self-validation ---

    #[test]
    fn validate_self_consistent() {
        let ont = devops_ontology();
        assert!(ont.validate_self().is_ok());
    }

    #[test]
    fn validate_self_dangling_source() {
        let ont = Ontology {
            node_types: BTreeMap::from([(
                "entity".into(),
                NodeTypeDef {
                    description: None,
                    properties: BTreeMap::new(),
                    subtypes: None,
                    parent_type: None,
                },
            )]),
            edge_types: BTreeMap::from([(
                "OBSERVES".into(),
                EdgeTypeDef {
                    description: None,
                    source_types: vec!["ghost".into()], // doesn't exist
                    target_types: vec!["entity".into()],
                    properties: BTreeMap::new(),
                },
            )]),
        };
        let err = ont.validate_self().unwrap_err();
        assert!(
            matches!(err, ValidationError::InvalidSource { node_type, .. } if node_type == "ghost")
        );
    }

    #[test]
    fn validate_self_dangling_target() {
        let ont = Ontology {
            node_types: BTreeMap::from([(
                "signal".into(),
                NodeTypeDef {
                    description: None,
                    properties: BTreeMap::new(),
                    subtypes: None,
                    parent_type: None,
                },
            )]),
            edge_types: BTreeMap::from([(
                "OBSERVES".into(),
                EdgeTypeDef {
                    description: None,
                    source_types: vec!["signal".into()],
                    target_types: vec!["phantom".into()], // doesn't exist
                    properties: BTreeMap::new(),
                },
            )]),
        };
        let err = ont.validate_self().unwrap_err();
        assert!(
            matches!(err, ValidationError::InvalidTarget { node_type, .. } if node_type == "phantom")
        );
    }

    // --- Serialization ---

    // --- New constraint tests (Step 1: SHACL-inspired vocabulary) ---

    fn constrained_ontology() -> Ontology {
        Ontology {
            node_types: BTreeMap::from([(
                "item".into(),
                NodeTypeDef {
                    description: None,
                    properties: BTreeMap::from([
                        (
                            "slug".into(),
                            PropertyDef {
                                value_type: ValueType::String,
                                required: false,
                                description: None,
                                constraints: Some(BTreeMap::from([
                                    (
                                        "pattern".to_string(),
                                        serde_json::Value::String("^[a-z0-9-]+$".to_string()),
                                    ),
                                    (
                                        "min_length".to_string(),
                                        serde_json::Value::Number(1.into()),
                                    ),
                                    (
                                        "max_length".to_string(),
                                        serde_json::Value::Number(63.into()),
                                    ),
                                ])),
                            },
                        ),
                        (
                            "score".into(),
                            PropertyDef {
                                value_type: ValueType::Float,
                                required: false,
                                description: None,
                                constraints: Some(BTreeMap::from([
                                    ("min_exclusive".to_string(), serde_json::json!(0.0)),
                                    ("max_exclusive".to_string(), serde_json::json!(100.0)),
                                ])),
                            },
                        ),
                    ]),
                    subtypes: None,
                    parent_type: None,
                },
            )]),
            edge_types: BTreeMap::new(),
        }
    }

    #[test]
    fn pattern_valid_slug() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("slug".into(), Value::String("my-project-1".into()))]);
        assert!(ont.validate_node("item", None, &props).is_ok());
    }

    #[test]
    fn pattern_rejects_uppercase() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("slug".into(), Value::String("My-Project".into()))]);
        assert!(ont.validate_node("item", None, &props).is_err());
    }

    #[test]
    fn pattern_rejects_spaces() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("slug".into(), Value::String("has space".into()))]);
        assert!(ont.validate_node("item", None, &props).is_err());
    }

    #[test]
    fn min_length_accepts_valid() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("slug".into(), Value::String("a".into()))]);
        assert!(ont.validate_node("item", None, &props).is_ok());
    }

    #[test]
    fn min_length_rejects_empty() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("slug".into(), Value::String("".into()))]);
        let err = ont.validate_node("item", None, &props).unwrap_err();
        assert!(
            matches!(err, ValidationError::ConstraintViolation { constraint, .. } if constraint == "min_length")
        );
    }

    #[test]
    fn max_length_rejects_too_long() {
        let ont = constrained_ontology();
        let long = "a".repeat(64);
        let props = BTreeMap::from([("slug".into(), Value::String(long))]);
        let err = ont.validate_node("item", None, &props).unwrap_err();
        assert!(
            matches!(err, ValidationError::ConstraintViolation { constraint, .. } if constraint == "max_length")
        );
    }

    #[test]
    fn max_length_accepts_boundary() {
        let ont = constrained_ontology();
        let exact = "a".repeat(63);
        let props = BTreeMap::from([("slug".into(), Value::String(exact))]);
        assert!(ont.validate_node("item", None, &props).is_ok());
    }

    #[test]
    fn min_exclusive_rejects_boundary() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("score".into(), Value::Float(0.0))]);
        let err = ont.validate_node("item", None, &props).unwrap_err();
        assert!(
            matches!(err, ValidationError::ConstraintViolation { constraint, .. } if constraint == "min_exclusive")
        );
    }

    #[test]
    fn min_exclusive_accepts_above() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("score".into(), Value::Float(0.001))]);
        assert!(ont.validate_node("item", None, &props).is_ok());
    }

    #[test]
    fn max_exclusive_rejects_boundary() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("score".into(), Value::Float(100.0))]);
        let err = ont.validate_node("item", None, &props).unwrap_err();
        assert!(
            matches!(err, ValidationError::ConstraintViolation { constraint, .. } if constraint == "max_exclusive")
        );
    }

    #[test]
    fn max_exclusive_accepts_below() {
        let ont = constrained_ontology();
        let props = BTreeMap::from([("score".into(), Value::Float(99.999))]);
        assert!(ont.validate_node("item", None, &props).is_ok());
    }

    // --- Serialization ---

    #[test]
    fn ontology_roundtrip_msgpack() {
        let ont = devops_ontology();
        let bytes = rmp_serde::to_vec(&ont).unwrap();
        let decoded: Ontology = rmp_serde::from_slice(&bytes).unwrap();
        assert_eq!(ont, decoded);
    }

    #[test]
    fn ontology_roundtrip_json() {
        let ont = devops_ontology();
        let json = serde_json::to_string(&ont).unwrap();
        let decoded: Ontology = serde_json::from_str(&json).unwrap();
        assert_eq!(ont, decoded);
    }

    // --- Step 2: RDFS class hierarchy tests ---

    fn hierarchy_ontology() -> Ontology {
        // thing → entity → server (two levels)
        //       → event
        Ontology {
            node_types: BTreeMap::from([
                (
                    "thing".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::from([(
                            "name".into(),
                            PropertyDef {
                                value_type: ValueType::String,
                                required: true,
                                description: None,
                                constraints: None,
                            },
                        )]),
                        subtypes: None,
                        parent_type: None, // root
                    },
                ),
                (
                    "entity".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::from([(
                            "status".into(),
                            PropertyDef {
                                value_type: ValueType::String,
                                required: false,
                                description: None,
                                constraints: None,
                            },
                        )]),
                        subtypes: None,
                        parent_type: Some("thing".into()), // entity extends thing
                    },
                ),
                (
                    "server".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::from([(
                            "ip".into(),
                            PropertyDef {
                                value_type: ValueType::String,
                                required: false,
                                description: None,
                                constraints: None,
                            },
                        )]),
                        subtypes: None,
                        parent_type: Some("entity".into()), // server extends entity
                    },
                ),
                (
                    "event".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::new(),
                        subtypes: None,
                        parent_type: Some("thing".into()), // event extends thing
                    },
                ),
            ]),
            edge_types: BTreeMap::from([(
                "RELATES_TO".into(),
                EdgeTypeDef {
                    description: None,
                    source_types: vec!["thing".into()], // accepts any thing descendant
                    target_types: vec!["entity".into()], // accepts entity or server
                    properties: BTreeMap::new(),
                },
            )]),
        }
    }

    #[test]
    fn ancestors_empty_for_root() {
        let ont = hierarchy_ontology();
        assert!(ont.ancestors("thing").is_empty());
    }

    #[test]
    fn ancestors_single_parent() {
        let ont = hierarchy_ontology();
        assert_eq!(ont.ancestors("entity"), vec!["thing"]);
    }

    #[test]
    fn ancestors_transitive() {
        let ont = hierarchy_ontology();
        // server → entity → thing
        assert_eq!(ont.ancestors("server"), vec!["entity", "thing"]);
    }

    #[test]
    fn descendants_of_root() {
        let ont = hierarchy_ontology();
        let mut desc = ont.descendants("thing");
        desc.sort();
        assert_eq!(desc, vec!["entity", "event", "server"]);
    }

    #[test]
    fn descendants_of_entity() {
        let ont = hierarchy_ontology();
        assert_eq!(ont.descendants("entity"), vec!["server"]);
    }

    #[test]
    fn descendants_of_leaf() {
        let ont = hierarchy_ontology();
        assert!(ont.descendants("server").is_empty());
    }

    #[test]
    fn is_subtype_of_self() {
        let ont = hierarchy_ontology();
        assert!(ont.is_subtype_of("server", "server"));
    }

    #[test]
    fn is_subtype_of_parent() {
        let ont = hierarchy_ontology();
        assert!(ont.is_subtype_of("server", "entity"));
        assert!(ont.is_subtype_of("server", "thing"));
    }

    #[test]
    fn is_not_subtype_of_sibling() {
        let ont = hierarchy_ontology();
        assert!(!ont.is_subtype_of("server", "event"));
    }

    #[test]
    fn effective_properties_inherits() {
        let ont = hierarchy_ontology();
        let props = ont.effective_properties("server");
        // server should have: name (from thing), status (from entity), ip (own)
        assert!(props.contains_key("name"));
        assert!(props.contains_key("status"));
        assert!(props.contains_key("ip"));
    }

    #[test]
    fn effective_properties_root_has_own_only() {
        let ont = hierarchy_ontology();
        let props = ont.effective_properties("thing");
        assert!(props.contains_key("name"));
        assert!(!props.contains_key("status"));
    }

    #[test]
    fn validate_node_inherits_required_from_ancestor() {
        let ont = hierarchy_ontology();
        // server requires "name" (inherited from thing)
        let err = ont.validate_node("server", None, &BTreeMap::new());
        assert!(err.is_err());

        let props = BTreeMap::from([("name".into(), Value::String("web-01".into()))]);
        assert!(ont.validate_node("server", None, &props).is_ok());
    }

    #[test]
    fn validate_edge_hierarchy_aware() {
        let ont = hierarchy_ontology();
        // RELATES_TO: source=thing, target=entity
        // server is-a thing, server is-a entity → both should pass
        let empty = BTreeMap::new();
        assert!(ont
            .validate_edge("RELATES_TO", "server", "server", &empty)
            .is_ok());
        assert!(ont
            .validate_edge("RELATES_TO", "event", "entity", &empty)
            .is_ok());
        assert!(ont
            .validate_edge("RELATES_TO", "thing", "entity", &empty)
            .is_ok());
    }

    #[test]
    fn validate_edge_hierarchy_rejects_wrong_branch() {
        let ont = hierarchy_ontology();
        // RELATES_TO target must be entity or descendant. event is not entity's descendant.
        let empty = BTreeMap::new();
        assert!(ont
            .validate_edge("RELATES_TO", "thing", "event", &empty)
            .is_err());
    }

    #[test]
    fn validate_self_rejects_dangling_parent() {
        let ont = Ontology {
            node_types: BTreeMap::from([(
                "orphan".into(),
                NodeTypeDef {
                    description: None,
                    properties: BTreeMap::new(),
                    subtypes: None,
                    parent_type: Some("ghost".into()), // doesn't exist
                },
            )]),
            edge_types: BTreeMap::new(),
        };
        assert!(ont.validate_self().is_err());
    }

    // -- Ontology hashing and fingerprinting --

    fn pet_ontology() -> Ontology {
        Ontology {
            node_types: BTreeMap::from([
                (
                    "animal".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::from([(
                            "name".into(),
                            PropertyDef {
                                value_type: ValueType::String,
                                required: true,
                                description: None,
                                constraints: None,
                            },
                        )]),
                        subtypes: None,
                        parent_type: None,
                    },
                ),
                (
                    "shelter".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::new(),
                        subtypes: None,
                        parent_type: None,
                    },
                ),
            ]),
            edge_types: BTreeMap::from([(
                "LIVES_AT".into(),
                EdgeTypeDef {
                    description: None,
                    source_types: vec!["animal".into()],
                    target_types: vec!["shelter".into()],
                    properties: BTreeMap::new(),
                },
            )]),
        }
    }

    fn prop(required: bool) -> PropertyDef {
        PropertyDef {
            value_type: ValueType::String,
            required,
            description: None,
            constraints: None,
        }
    }

    fn subtype(props: BTreeMap<String, PropertyDef>) -> SubtypeDef {
        SubtypeDef {
            description: None,
            properties: props,
        }
    }

    // -- A: extensions that would invalidate existing entries are refused --

    #[test]
    fn refuses_required_property_on_an_existing_node_type() {
        let mut ont = pet_ontology();
        let ext = OntologyExtension {
            node_type_updates: BTreeMap::from([(
                "animal".into(),
                NodeTypeUpdate {
                    add_properties: BTreeMap::from([("owner".into(), prop(true))]),
                    ..Default::default()
                },
            )]),
            ..Default::default()
        };
        assert_eq!(
            ont.merge_extension(&ext),
            Err(MonotonicityError::RequiredPropertyOnExistingType {
                kind: "node type",
                type_name: "animal".into(),
                property: "owner".into(),
            })
        );
        // Refused means unchanged, not half-applied.
        assert_eq!(ont, pet_ontology());
    }

    #[test]
    fn refuses_required_property_on_an_existing_edge_type() {
        let mut ont = pet_ontology();
        let ext = OntologyExtension {
            edge_type_updates: BTreeMap::from([(
                "LIVES_AT".into(),
                EdgeTypeUpdate {
                    add_properties: BTreeMap::from([("since".into(), prop(true))]),
                    ..Default::default()
                },
            )]),
            ..Default::default()
        };
        assert!(matches!(
            ont.merge_extension(&ext),
            Err(MonotonicityError::RequiredPropertyOnExistingType {
                kind: "edge type",
                ..
            })
        ));
        assert_eq!(ont, pet_ontology());
    }

    #[test]
    fn refuses_the_first_subtype_on_a_subtypeless_type() {
        let mut ont = pet_ontology();
        let ext = OntologyExtension {
            node_type_updates: BTreeMap::from([(
                "animal".into(),
                NodeTypeUpdate {
                    add_subtypes: BTreeMap::from([("dog".into(), subtype(BTreeMap::new()))]),
                    ..Default::default()
                },
            )]),
            ..Default::default()
        };
        assert_eq!(
            ont.merge_extension(&ext),
            Err(MonotonicityError::SubtypesOnSubtypelessType {
                type_name: "animal".into(),
                subtypes: vec!["dog".into()],
            })
        );
        assert_eq!(ont, pet_ontology());
    }

    #[test]
    fn refuses_required_property_on_a_new_subtype() {
        // D-026 lets a node name a subtype the ontology has not declared, so
        // declaring it with a required property can quarantine that node.
        let mut ont = pet_ontology();
        ont.node_types.get_mut("animal").unwrap().subtypes =
            Some(BTreeMap::from([("cat".into(), subtype(BTreeMap::new()))]));
        let before = ont.clone();

        let ext = OntologyExtension {
            node_type_updates: BTreeMap::from([(
                "animal".into(),
                NodeTypeUpdate {
                    add_subtypes: BTreeMap::from([(
                        "dog".into(),
                        subtype(BTreeMap::from([("breed".into(), prop(true))])),
                    )]),
                    ..Default::default()
                },
            )]),
            ..Default::default()
        };
        assert!(matches!(
            ont.merge_extension(&ext),
            Err(MonotonicityError::RequiredPropertyOnExistingType {
                kind: "subtype",
                ..
            })
        ));
        assert_eq!(ont, before);
    }

    #[test]
    fn allows_an_optional_property_and_a_subtype_on_a_subtyped_type() {
        let mut ont = pet_ontology();
        ont.node_types.get_mut("animal").unwrap().subtypes =
            Some(BTreeMap::from([("cat".into(), subtype(BTreeMap::new()))]));

        let ext = OntologyExtension {
            node_type_updates: BTreeMap::from([(
                "animal".into(),
                NodeTypeUpdate {
                    add_properties: BTreeMap::from([("owner".into(), prop(false))]),
                    add_subtypes: BTreeMap::from([(
                        "dog".into(),
                        subtype(BTreeMap::from([("breed".into(), prop(false))])),
                    )]),
                    ..Default::default()
                },
            )]),
            ..Default::default()
        };
        assert_eq!(ont.merge_extension(&ext), Ok(()));
    }

    #[test]
    fn allows_a_required_property_on_a_brand_new_type() {
        let mut ont = pet_ontology();
        let ext = OntologyExtension {
            node_types: BTreeMap::from([(
                "vet".into(),
                NodeTypeDef {
                    description: None,
                    properties: BTreeMap::from([("license".into(), prop(true))]),
                    subtypes: None,
                    parent_type: None,
                },
            )]),
            ..Default::default()
        };
        assert_eq!(ont.merge_extension(&ext), Ok(()));
    }

    // -- D: naming a destructive superset from fingerprints alone --

    #[test]
    fn destructive_changes_flags_a_newly_required_property() {
        let old = pet_ontology();
        let mut new = pet_ontology();
        new.node_types
            .get_mut("shelter")
            .unwrap()
            .properties
            .insert("capacity".into(), prop(true));

        let changes = new.destructive_changes(&old.fingerprint());
        assert_eq!(changes.len(), 1, "{changes:?}");
        assert!(changes[0].contains("capacity") && changes[0].contains("shelter"));
    }

    #[test]
    fn destructive_changes_flags_a_property_the_peer_holds_as_optional() {
        // Absent and optional are the same thing here: neither peer entry had
        // to carry it.
        let mut old = pet_ontology();
        old.node_types
            .get_mut("shelter")
            .unwrap()
            .properties
            .insert("capacity".into(), prop(false));
        let mut new = pet_ontology();
        new.node_types
            .get_mut("shelter")
            .unwrap()
            .properties
            .insert("capacity".into(), prop(true));

        assert_eq!(new.destructive_changes(&old.fingerprint()).len(), 1);
    }

    #[test]
    fn destructive_changes_flags_a_newly_required_edge_property() {
        let old = pet_ontology();
        let mut new = pet_ontology();
        new.edge_types
            .get_mut("LIVES_AT")
            .unwrap()
            .properties
            .insert("since".into(), prop(true));

        let changes = new.destructive_changes(&old.fingerprint());
        assert_eq!(changes.len(), 1, "{changes:?}");
        assert!(changes[0].contains("since") && changes[0].contains("LIVES_AT"));
    }

    #[test]
    fn destructive_changes_flags_a_newly_required_subtype_property() {
        let mut old = pet_ontology();
        old.node_types.get_mut("animal").unwrap().subtypes =
            Some(BTreeMap::from([("cat".into(), subtype(BTreeMap::new()))]));
        let mut new = old.clone();
        new.node_types
            .get_mut("animal")
            .unwrap()
            .subtypes
            .as_mut()
            .unwrap()
            .insert(
                "dog".into(),
                subtype(BTreeMap::from([("breed".into(), prop(true))])),
            );

        let changes = new.destructive_changes(&old.fingerprint());
        assert_eq!(changes.len(), 1, "{changes:?}");
        assert!(changes[0].contains("breed"), "{changes:?}");
    }

    #[test]
    fn destructive_changes_flags_the_subtype_flip_once_per_type() {
        let old = pet_ontology();
        let mut new = pet_ontology();
        new.node_types.get_mut("animal").unwrap().subtypes = Some(BTreeMap::from([
            ("cat".into(), subtype(BTreeMap::new())),
            ("dog".into(), subtype(BTreeMap::new())),
        ]));

        let changes = new.destructive_changes(&old.fingerprint());
        assert_eq!(changes.len(), 1, "two subtypes, one flip: {changes:?}");
        assert!(changes[0].contains("animal"));
    }

    #[test]
    fn destructive_changes_ignores_a_type_the_peer_never_had() {
        // A brand new type with required properties holds no peer data.
        let old = pet_ontology();
        let mut new = pet_ontology();
        new.node_types.insert(
            "vet".into(),
            NodeTypeDef {
                description: None,
                properties: BTreeMap::from([("license".into(), prop(true))]),
                subtypes: Some(BTreeMap::from([(
                    "surgeon".into(),
                    subtype(BTreeMap::new()),
                )])),
                parent_type: None,
            },
        );
        assert_eq!(
            new.destructive_changes(&old.fingerprint()),
            Vec::<String>::new()
        );
    }

    #[test]
    fn destructive_changes_ignores_an_optional_property() {
        let old = pet_ontology();
        let mut new = pet_ontology();
        new.node_types
            .get_mut("shelter")
            .unwrap()
            .properties
            .insert("capacity".into(), prop(false));
        assert_eq!(
            new.destructive_changes(&old.fingerprint()),
            Vec::<String>::new()
        );
    }

    #[test]
    fn check_compatibility_separates_destructive_from_safe_supersets() {
        let old = pet_ontology();
        let (old_hash, old_fp) = (old.content_hash(), old.fingerprint());

        let mut safe = pet_ontology();
        safe.node_types
            .get_mut("shelter")
            .unwrap()
            .properties
            .insert("capacity".into(), prop(false));
        assert_eq!(
            safe.check_compatibility(&old_hash, &old_fp),
            Compatibility::Superset
        );

        let mut destructive = pet_ontology();
        destructive
            .node_types
            .get_mut("shelter")
            .unwrap()
            .properties
            .insert("capacity".into(), prop(true));
        assert_eq!(
            destructive.check_compatibility(&old_hash, &old_fp),
            Compatibility::DestructiveSuperset
        );
    }

    #[test]
    fn check_compatibility_subset_and_divergent_are_unaffected() {
        let old = pet_ontology();
        let mut newer = pet_ontology();
        newer
            .node_types
            .get_mut("shelter")
            .unwrap()
            .properties
            .insert("capacity".into(), prop(true));

        assert_eq!(
            old.check_compatibility(&newer.content_hash(), &newer.fingerprint()),
            Compatibility::Subset
        );
    }

    #[test]
    fn content_hash_deterministic() {
        let a = pet_ontology();
        let b = pet_ontology();
        assert_eq!(a.content_hash(), b.content_hash());
    }

    #[test]
    fn content_hash_is_32_bytes() {
        let ont = pet_ontology();
        let hash = ont.content_hash();
        assert_eq!(hash.len(), 32);
        assert_ne!(hash, [0u8; 32]); // not all zeros
    }

    #[test]
    fn content_hash_changes_on_new_type() {
        let mut ont = pet_ontology();
        let hash_before = ont.content_hash();
        ont.node_types.insert(
            "volunteer".into(),
            NodeTypeDef {
                description: None,
                properties: BTreeMap::new(),
                subtypes: None,
                parent_type: None,
            },
        );
        let hash_after = ont.content_hash();
        assert_ne!(hash_before, hash_after);
    }

    #[test]
    fn content_hash_changes_on_new_property() {
        let mut ont = pet_ontology();
        let hash_before = ont.content_hash();
        ont.node_types.get_mut("animal").unwrap().properties.insert(
            "microchip_id".into(),
            PropertyDef {
                value_type: ValueType::String,
                required: false,
                description: None,
                constraints: None,
            },
        );
        let hash_after = ont.content_hash();
        assert_ne!(hash_before, hash_after);
    }

    #[test]
    fn fingerprint_contains_types() {
        let ont = pet_ontology();
        let fp = ont.fingerprint();
        assert!(fp.contains("type:animal"));
        assert!(fp.contains("type:shelter"));
        assert!(fp.contains("edge:LIVES_AT"));
    }

    #[test]
    fn fingerprint_contains_properties() {
        let ont = pet_ontology();
        let fp = ont.fingerprint();
        assert!(fp.contains("prop:animal:name:string:required"));
    }

    #[test]
    fn fingerprint_contains_edge_constraints() {
        let ont = pet_ontology();
        let fp = ont.fingerprint();
        assert!(fp.contains("edge:LIVES_AT:src:animal"));
        assert!(fp.contains("edge:LIVES_AT:tgt:shelter"));
    }

    #[test]
    fn fingerprint_contains_parent_type() {
        let ont = Ontology {
            node_types: BTreeMap::from([
                (
                    "entity".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::new(),
                        subtypes: None,
                        parent_type: None,
                    },
                ),
                (
                    "server".into(),
                    NodeTypeDef {
                        description: None,
                        properties: BTreeMap::new(),
                        subtypes: None,
                        parent_type: Some("entity".into()),
                    },
                ),
            ]),
            edge_types: BTreeMap::new(),
        };
        let fp = ont.fingerprint();
        assert!(fp.contains("type:server:parent:entity"));
    }

    #[test]
    fn fingerprint_contains_subtypes() {
        let ont = Ontology {
            node_types: BTreeMap::from([(
                "entity".into(),
                NodeTypeDef {
                    description: None,
                    properties: BTreeMap::new(),
                    subtypes: Some(BTreeMap::from([(
                        "project".into(),
                        SubtypeDef {
                            description: None,
                            properties: BTreeMap::from([(
                                "slug".into(),
                                PropertyDef {
                                    value_type: ValueType::String,
                                    required: true,
                                    description: None,
                                    constraints: None,
                                },
                            )]),
                        },
                    )])),
                    parent_type: None,
                },
            )]),
            edge_types: BTreeMap::new(),
        };
        let fp = ont.fingerprint();
        assert!(fp.contains("subtype:entity:project"));
        assert!(fp.contains("subprop:entity:project:slug:string:required"));
    }

    #[test]
    fn fingerprint_superset_after_extension() {
        let base = pet_ontology();
        let base_fp = base.fingerprint();

        let mut extended = pet_ontology();
        extended.node_types.insert(
            "volunteer".into(),
            NodeTypeDef {
                description: None,
                properties: BTreeMap::new(),
                subtypes: None,
                parent_type: None,
            },
        );
        let ext_fp = extended.fingerprint();

        // Extended is strict superset of base
        assert!(base_fp.is_subset(&ext_fp));
        assert!(!ext_fp.is_subset(&base_fp));
    }

    #[test]
    fn check_compatibility_identical() {
        let a = pet_ontology();
        let b = pet_ontology();
        let verdict = a.check_compatibility(&b.content_hash(), &b.fingerprint());
        assert_eq!(verdict, Compatibility::Identical);
    }

    #[test]
    fn check_compatibility_superset() {
        let base = pet_ontology();

        let mut extended = pet_ontology();
        extended.node_types.insert(
            "volunteer".into(),
            NodeTypeDef {
                description: None,
                properties: BTreeMap::new(),
                subtypes: None,
                parent_type: None,
            },
        );

        // Extended checking base: extended is superset
        let verdict = extended.check_compatibility(&base.content_hash(), &base.fingerprint());
        assert_eq!(verdict, Compatibility::Superset);
    }

    #[test]
    fn check_compatibility_subset() {
        let base = pet_ontology();

        let mut extended = pet_ontology();
        extended.node_types.insert(
            "volunteer".into(),
            NodeTypeDef {
                description: None,
                properties: BTreeMap::new(),
                subtypes: None,
                parent_type: None,
            },
        );

        // Base checking extended: base is subset
        let verdict = base.check_compatibility(&extended.content_hash(), &extended.fingerprint());
        assert_eq!(verdict, Compatibility::Subset);
    }

    #[test]
    fn check_compatibility_divergent() {
        // Two independent extensions from the same base
        let mut branch_a = pet_ontology();
        branch_a.node_types.insert(
            "volunteer".into(),
            NodeTypeDef {
                description: None,
                properties: BTreeMap::new(),
                subtypes: None,
                parent_type: None,
            },
        );

        let mut branch_b = pet_ontology();
        branch_b.node_types.insert(
            "adoption".into(),
            NodeTypeDef {
                description: None,
                properties: BTreeMap::new(),
                subtypes: None,
                parent_type: None,
            },
        );

        let verdict =
            branch_a.check_compatibility(&branch_b.content_hash(), &branch_b.fingerprint());
        assert_eq!(verdict, Compatibility::Divergent);
    }

    #[test]
    fn fingerprint_contains_enum_constraints() {
        let ont = Ontology {
            node_types: BTreeMap::from([(
                "server".into(),
                NodeTypeDef {
                    description: None,
                    properties: BTreeMap::from([(
                        "status".into(),
                        PropertyDef {
                            value_type: ValueType::String,
                            required: true,
                            description: None,
                            constraints: Some(BTreeMap::from([(
                                "enum".into(),
                                serde_json::json!(["active", "standby"]),
                            )])),
                        },
                    )]),
                    subtypes: None,
                    parent_type: None,
                },
            )]),
            edge_types: BTreeMap::new(),
        };
        let fp = ont.fingerprint();
        assert!(fp.contains("constraint:server:status:enum:active"));
        assert!(fp.contains("constraint:server:status:enum:standby"));
    }
}