ringkernel_core/

provenance.rs

//! PROV-O provenance attribution for message envelopes.
//!
//! Per `docs/superpowers/specs/2026-04-17-v1.1-vyngraph-gaps.md` section 3.4,
//! this module provides optional per-message attribution metadata for NSAI
//! (neuro-symbolic AI) reasoning chains such as VynGraph audit workloads.
//!
//! ## Overview
//!
//! The full W3C PROV-O vocabulary is large; v1.1 supports the eight core
//! relations that cover 95%+ of NSAI reasoning chains:
//!
//! | Relation           | Types                | Example                                         |
//! |--------------------|----------------------|-------------------------------------------------|
//! | `wasAttributedTo`  | Entity   -> Agent    | fraud alert attributed to `fraud_triangle`      |
//! | `wasGeneratedBy`   | Entity   -> Activity | consolidated balance generated by consolidation |
//! | `wasDerivedFrom`   | Entity   -> Entity   | source-trace lineage for audit evidence         |
//! | `used`             | Activity -> Entity   | SoD check used journal entries                  |
//! | `wasInformedBy`    | Activity -> Activity | going-concern informed by cash-flow analysis    |
//! | `wasAssociatedWith`| Activity -> Agent    | LLM generation associated with auditor prompt   |
//! | `actedOnBehalfOf`  | Agent    -> Agent    | assistant acted on behalf of partner            |
//! | `Plan` subtype     | n/a                  | audit programs as plans                         |
//!
//! Qualified relations (`qualifiedAttribution`, etc.) are deferred to v1.5 -
//! HLC already provides the temporal qualification v1.1 needs.
//!
//! ## Design
//!
//! - Zero cost when unused: `MessageEnvelope::provenance` is `Option<_>`.
//! - 4 inline relation slots cover the common case; overflow spills to an
//!   off-band record referenced by `overflow_ref`.
//! - `Plan` is an Entity subclass (matches PROV-O spec) tracked via `plan_id`.
//! - All identifiers are `u64`; the caller (VynGraph) owns the ID namespace.
//!
//! ## Example
//!
//! ```
//! use ringkernel_core::provenance::{
//!     ProvNodeType, ProvRelationKind, ProvenanceBuilder,
//! };
//! use ringkernel_core::hlc::HlcTimestamp;
//!
//! // IDs are u64 — caller (e.g., VynGraph) owns the ID namespace
//! const FRAUD_ALERT_ID: u64 = 0xDEAD_BEEF_0001;
//! const FRAUD_TRIANGLE_AGENT: u64 = 0xA6E0_7751_0002;
//! const GAAP_RUN_ACTIVITY: u64 = 0xAC71_7170_0003;
//!
//! let hdr = ProvenanceBuilder::new(ProvNodeType::Entity, FRAUD_ALERT_ID)
//!     .with_timestamp(HlcTimestamp::now(1))
//!     .with_relation(ProvRelationKind::WasAttributedTo, FRAUD_TRIANGLE_AGENT)
//!     .with_relation(ProvRelationKind::WasGeneratedBy, GAAP_RUN_ACTIVITY)
//!     .build()
//!     .unwrap();
//! assert_eq!(hdr.relation_count(), 2);
//! ```

use crate::hlc::HlcTimestamp;

/// Maximum number of relations that fit inline (without overflow spill).
///
/// Chosen to cover 95%+ of NSAI reasoning steps (most have 1-3 PROV edges).
pub const INLINE_RELATION_SLOTS: usize = 4;

/// Maximum chain depth when walking `wasDerivedFrom` / `wasInformedBy`
/// relations during validation. Guards against pathological graphs.
pub const MAX_CHAIN_DEPTH: usize = 256;

/// Classification of a PROV-O node.
///
/// Per the W3C PROV-O data model, a node is one of three top-level kinds
/// (Entity, Activity, Agent). `Plan` is a Plan-subclass of Entity tracked
/// explicitly so we can recognize audit programs without an extra lookup.
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, Hash, rkyv::Archive, rkyv::Serialize, rkyv::Deserialize,
)]
#[archive(compare(PartialEq))]
#[repr(u8)]
pub enum ProvNodeType {
    /// A PROV Entity: data item, artifact, fact.
    Entity = 0,
    /// A PROV Activity: computation, reasoning step, consolidation run.
    Activity = 1,
    /// A PROV Agent: an auditor, an analytic, an LLM.
    Agent = 2,
    /// A Plan (Entity subclass) - e.g. an audit program.
    Plan = 3,
}

impl ProvNodeType {
    /// Try to parse from the wire `u8` discriminant.
    pub const fn from_u8(value: u8) -> Option<Self> {
        match value {
            0 => Some(Self::Entity),
            1 => Some(Self::Activity),
            2 => Some(Self::Agent),
            3 => Some(Self::Plan),
            _ => None,
        }
    }

    /// Convert to the `u8` discriminant.
    pub const fn as_u8(self) -> u8 {
        self as u8
    }

    /// Whether this node is Entity-like (Entity or Plan).
    pub const fn is_entity(self) -> bool {
        matches!(self, Self::Entity | Self::Plan)
    }
}

/// PROV-O relation kind (edge label).
///
/// `None = 0` indicates an empty slot in [`ProvenanceHeader::relations`].
/// This makes the zero-value representation safe and lets arrays of
/// relations be default-initialised cheaply.
#[derive(
    Debug,
    Clone,
    Copy,
    PartialEq,
    Eq,
    Hash,
    Default,
    rkyv::Archive,
    rkyv::Serialize,
    rkyv::Deserialize,
)]
#[archive(compare(PartialEq))]
#[repr(u8)]
pub enum ProvRelationKind {
    /// Empty slot - no relation.
    #[default]
    None = 0,
    /// Entity was attributed to Agent.
    WasAttributedTo = 1,
    /// Entity was generated by Activity.
    WasGeneratedBy = 2,
    /// Entity was derived from another Entity.
    WasDerivedFrom = 3,
    /// Activity used an Entity.
    Used = 4,
    /// Activity was informed by another Activity.
    WasInformedBy = 5,
    /// Activity was associated with an Agent.
    WasAssociatedWith = 6,
    /// Agent acted on behalf of another Agent.
    ActedOnBehalfOf = 7,
}

impl ProvRelationKind {
    /// Try to parse from the wire `u8` discriminant.
    pub const fn from_u8(value: u8) -> Option<Self> {
        match value {
            0 => Some(Self::None),
            1 => Some(Self::WasAttributedTo),
            2 => Some(Self::WasGeneratedBy),
            3 => Some(Self::WasDerivedFrom),
            4 => Some(Self::Used),
            5 => Some(Self::WasInformedBy),
            6 => Some(Self::WasAssociatedWith),
            7 => Some(Self::ActedOnBehalfOf),
            _ => None,
        }
    }

    /// Convert to the `u8` discriminant.
    pub const fn as_u8(self) -> u8 {
        self as u8
    }

    /// Whether this slot carries a real relation (kind != None).
    pub const fn is_some(self) -> bool {
        !matches!(self, Self::None)
    }

    /// Expected PROV-O source node type for this relation's subject.
    ///
    /// Useful for type-check helpers before adding a relation to a builder.
    pub const fn expected_source_type(self) -> Option<ProvNodeType> {
        match self {
            Self::None => None,
            Self::WasAttributedTo | Self::WasGeneratedBy | Self::WasDerivedFrom => {
                Some(ProvNodeType::Entity)
            }
            Self::Used | Self::WasInformedBy | Self::WasAssociatedWith => {
                Some(ProvNodeType::Activity)
            }
            Self::ActedOnBehalfOf => Some(ProvNodeType::Agent),
        }
    }
}

/// A single PROV-O relation edge (kind + target node ID).
///
/// Compact 16-byte representation (after alignment padding) packed into the
/// inline relation array of [`ProvenanceHeader`].
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, Default, rkyv::Archive, rkyv::Serialize, rkyv::Deserialize,
)]
#[repr(C)]
pub struct ProvRelation {
    /// Relation label (`None` marks an empty slot).
    pub kind: ProvRelationKind,
    /// Target PROV node ID. Meaningless when `kind == None`.
    pub target_id: u64,
}

impl ProvRelation {
    /// An empty relation slot.
    pub const EMPTY: Self = Self {
        kind: ProvRelationKind::None,
        target_id: 0,
    };

    /// Build a new relation.
    pub const fn new(kind: ProvRelationKind, target_id: u64) -> Self {
        Self { kind, target_id }
    }

    /// Whether this slot is populated.
    pub const fn is_some(&self) -> bool {
        self.kind.is_some()
    }
}

/// PROV-O attribution metadata attached to a message envelope.
///
/// - Absent: `MessageEnvelope::provenance == None` - 1 byte overhead.
/// - Present: ~`size_of::<ProvenanceHeader>()` bytes inline (verified by test
///   [`tests::test_provenance_header_size`]). The spec notes a ~88 byte
///   target; actual size depends on natural alignment and is asserted in the
///   test module.
/// - With >4 relations: one extra cache line referenced by `overflow_ref`
///   (caller owns that off-band record).
#[derive(Debug, Clone, Copy, PartialEq, Eq, rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)]
#[repr(C)]
pub struct ProvenanceHeader {
    /// Classification of the node this header describes.
    pub node_type: ProvNodeType,

    /// Globally unique PROV node ID (Entity/Activity/Agent/Plan).
    pub node_id: u64,

    /// Inline PROV relations. Empty slots have `kind == ProvRelationKind::None`.
    /// When more than 4 relations are needed, callers set `overflow_ref`.
    pub relations: [ProvRelation; INLINE_RELATION_SLOTS],

    /// Optional off-band pointer to an extended relations record. `None`
    /// when all relations fit inline.
    pub overflow_ref: Option<u64>,

    /// HLC timestamp of the PROV event (generation / attribution time).
    pub prov_timestamp: HlcTimestamp,

    /// Optional Plan ID when this activity is executed under a Plan.
    pub plan_id: Option<u64>,
}

impl ProvenanceHeader {
    /// Construct a header with all empty relation slots.
    pub const fn new(node_type: ProvNodeType, node_id: u64) -> Self {
        Self {
            node_type,
            node_id,
            relations: [ProvRelation::EMPTY; INLINE_RELATION_SLOTS],
            overflow_ref: None,
            prov_timestamp: HlcTimestamp::zero(),
            plan_id: None,
        }
    }

    /// Number of populated inline relations.
    pub fn relation_count(&self) -> usize {
        self.relations.iter().filter(|r| r.is_some()).count()
    }

    /// Whether any overflow relations are referenced.
    pub const fn has_overflow(&self) -> bool {
        self.overflow_ref.is_some()
    }

    /// Iterate over the populated inline relations.
    pub fn iter_relations(&self) -> impl Iterator<Item = &ProvRelation> {
        self.relations.iter().filter(|r| r.is_some())
    }

    /// Find the first relation of a given kind, if present inline.
    pub fn find_relation(&self, kind: ProvRelationKind) -> Option<&ProvRelation> {
        self.relations.iter().find(|r| r.kind == kind)
    }

    /// Validate structural invariants that are cheap to check.
    ///
    /// - `node_id` must be non-zero (0 is reserved as "unset").
    /// - At most one self-loop is allowed (would indicate a cycle).
    /// - Relation kinds must be consistent with the declared `node_type` when
    ///   they have an expected source type.
    pub fn validate(&self) -> Result<(), ProvenanceError> {
        if self.node_id == 0 {
            return Err(ProvenanceError::InvalidNodeId);
        }

        for rel in self.iter_relations() {
            if rel.target_id == self.node_id {
                return Err(ProvenanceError::SelfLoop {
                    node_id: self.node_id,
                });
            }
            if let Some(expected) = rel.kind.expected_source_type() {
                if expected != self.node_type
                    && !(expected == ProvNodeType::Entity && self.node_type == ProvNodeType::Plan)
                {
                    return Err(ProvenanceError::KindTypeMismatch {
                        kind: rel.kind,
                        node_type: self.node_type,
                    });
                }
            }
        }

        Ok(())
    }
}

impl Default for ProvenanceHeader {
    fn default() -> Self {
        Self::new(ProvNodeType::Entity, 0)
    }
}

/// Builder for [`ProvenanceHeader`].
///
/// Collects relations in a `Vec` so callers don't have to think about inline
/// vs overflow slots. On `build`, the first `INLINE_RELATION_SLOTS` relations
/// are packed inline; any remainder is signalled by setting `overflow_ref`.
///
/// Overflow record storage is the caller's responsibility; the builder just
/// records the pointer.
#[derive(Debug, Clone)]
pub struct ProvenanceBuilder {
    node_type: ProvNodeType,
    node_id: u64,
    relations: Vec<ProvRelation>,
    overflow_ref: Option<u64>,
    prov_timestamp: HlcTimestamp,
    plan_id: Option<u64>,
}

impl ProvenanceBuilder {
    /// Start a new builder for a given PROV node.
    pub fn new(node_type: ProvNodeType, node_id: u64) -> Self {
        Self {
            node_type,
            node_id,
            relations: Vec::new(),
            overflow_ref: None,
            prov_timestamp: HlcTimestamp::zero(),
            plan_id: None,
        }
    }

    /// Set the HLC timestamp for the PROV event.
    pub fn with_timestamp(mut self, ts: HlcTimestamp) -> Self {
        self.prov_timestamp = ts;
        self
    }

    /// Set the Plan ID this activity follows (if any).
    pub fn with_plan(mut self, plan_id: u64) -> Self {
        self.plan_id = Some(plan_id);
        self
    }

    /// Add a PROV-O relation edge. `None` kind is rejected by
    /// [`ProvenanceBuilder::build`].
    pub fn with_relation(mut self, kind: ProvRelationKind, target_id: u64) -> Self {
        self.relations.push(ProvRelation::new(kind, target_id));
        self
    }

    /// Explicitly set the overflow record pointer. Callers typically let
    /// `build` set this automatically when more than 4 relations are added.
    pub fn with_overflow_ref(mut self, overflow_ref: u64) -> Self {
        self.overflow_ref = Some(overflow_ref);
        self
    }

    /// Finalise the builder and validate the result.
    ///
    /// If more than [`INLINE_RELATION_SLOTS`] relations were added and
    /// [`Self::with_overflow_ref`] was not called explicitly,
    /// [`ProvenanceError::OverflowNotSet`] is returned - callers must make
    /// the overflow record accessible through an out-of-band ID.
    pub fn build(self) -> Result<ProvenanceHeader, ProvenanceError> {
        // Reject explicit `None` kind entries - they'd collide with empty slots.
        for rel in &self.relations {
            if rel.kind == ProvRelationKind::None {
                return Err(ProvenanceError::InvalidRelationKind);
            }
        }

        let mut header = ProvenanceHeader::new(self.node_type, self.node_id);
        header.prov_timestamp = self.prov_timestamp;
        header.plan_id = self.plan_id;
        header.overflow_ref = self.overflow_ref;

        let inline_take = self.relations.len().min(INLINE_RELATION_SLOTS);
        for (slot, rel) in header.relations[..inline_take]
            .iter_mut()
            .zip(self.relations.iter().take(inline_take))
        {
            *slot = *rel;
        }

        if self.relations.len() > INLINE_RELATION_SLOTS && self.overflow_ref.is_none() {
            return Err(ProvenanceError::OverflowNotSet {
                excess: self.relations.len() - INLINE_RELATION_SLOTS,
            });
        }

        header.validate()?;
        Ok(header)
    }
}

/// Errors raised when constructing or validating provenance headers.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ProvenanceError {
    /// `node_id == 0` - reserved for "unset".
    InvalidNodeId,
    /// A relation's kind was set to `None`, which marks empty slots.
    InvalidRelationKind,
    /// The source `node_type` does not match the relation's expected type.
    KindTypeMismatch {
        /// The offending relation kind.
        kind: ProvRelationKind,
        /// The declared node type.
        node_type: ProvNodeType,
    },
    /// A relation pointed back at the node itself (direct cycle).
    SelfLoop {
        /// The node ID whose relation looped back.
        node_id: u64,
    },
    /// A chain traversal exceeded [`MAX_CHAIN_DEPTH`].
    ChainTooDeep {
        /// The depth at which traversal aborted.
        depth: usize,
    },
    /// A cycle was detected while traversing a chain.
    CycleDetected {
        /// The node ID where the cycle closed.
        at_node: u64,
    },
    /// More than 4 relations were added without setting `overflow_ref`.
    OverflowNotSet {
        /// Number of relations beyond the inline capacity.
        excess: usize,
    },
}

impl std::fmt::Display for ProvenanceError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::InvalidNodeId => write!(f, "provenance node_id must be non-zero"),
            Self::InvalidRelationKind => {
                write!(f, "relation kind None is reserved for empty slots")
            }
            Self::KindTypeMismatch { kind, node_type } => write!(
                f,
                "relation kind {:?} is not valid from node type {:?}",
                kind, node_type
            ),
            Self::SelfLoop { node_id } => {
                write!(f, "relation targets the source node itself ({})", node_id)
            }
            Self::ChainTooDeep { depth } => {
                write!(f, "provenance chain exceeded max depth ({})", depth)
            }
            Self::CycleDetected { at_node } => {
                write!(f, "provenance chain cycle detected at node {}", at_node)
            }
            Self::OverflowNotSet { excess } => write!(
                f,
                "{} relations overflowed inline slots; call with_overflow_ref",
                excess
            ),
        }
    }
}

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

/// Walk a derivation / informing chain to validate bounded depth and the
/// absence of cycles.
///
/// The caller supplies a closure that resolves each node ID to its (optional)
/// predecessor in the chain. The walk bails out with
/// [`ProvenanceError::CycleDetected`] if a node is revisited and with
/// [`ProvenanceError::ChainTooDeep`] after [`MAX_CHAIN_DEPTH`] hops.
pub fn validate_chain<F>(start: u64, mut next: F) -> Result<usize, ProvenanceError>
where
    F: FnMut(u64) -> Option<u64>,
{
    let mut seen: Vec<u64> = Vec::with_capacity(16);
    let mut cursor = Some(start);
    let mut depth = 0usize;

    while let Some(node) = cursor {
        if seen.contains(&node) {
            return Err(ProvenanceError::CycleDetected { at_node: node });
        }
        seen.push(node);
        depth += 1;
        if depth > MAX_CHAIN_DEPTH {
            return Err(ProvenanceError::ChainTooDeep { depth });
        }
        cursor = next(node);
    }
    Ok(depth)
}

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

    // ------------------------------------------------------------------
    // Type-level / representation tests
    // ------------------------------------------------------------------

    #[test]
    fn test_provenance_header_size() {
        // The spec quotes ~88 bytes as a target; we report the natural size
        // after alignment. This assertion is here to flag unexpected layout
        // drift during future changes.
        let size = std::mem::size_of::<ProvenanceHeader>();
        assert!(
            size <= 160,
            "ProvenanceHeader size {} exceeds reasonable envelope budget",
            size
        );
        // Log for visibility when running cargo test -- --nocapture.
        println!("ProvenanceHeader size: {} bytes", size);
    }

    #[test]
    fn test_prov_node_type_roundtrip() {
        for kind in [
            ProvNodeType::Entity,
            ProvNodeType::Activity,
            ProvNodeType::Agent,
            ProvNodeType::Plan,
        ] {
            assert_eq!(ProvNodeType::from_u8(kind.as_u8()), Some(kind));
        }
        assert_eq!(ProvNodeType::from_u8(99), None);
    }

    #[test]
    fn test_prov_relation_kind_roundtrip() {
        use ProvRelationKind::*;
        for kind in [
            None,
            WasAttributedTo,
            WasGeneratedBy,
            WasDerivedFrom,
            Used,
            WasInformedBy,
            WasAssociatedWith,
            ActedOnBehalfOf,
        ] {
            assert_eq!(ProvRelationKind::from_u8(kind.as_u8()), Some(kind));
        }
        assert_eq!(ProvRelationKind::from_u8(200), Option::None);
    }

    #[test]
    fn test_expected_source_type() {
        use ProvRelationKind::*;
        assert_eq!(
            WasAttributedTo.expected_source_type(),
            Some(ProvNodeType::Entity)
        );
        assert_eq!(Used.expected_source_type(), Some(ProvNodeType::Activity));
        assert_eq!(
            ActedOnBehalfOf.expected_source_type(),
            Some(ProvNodeType::Agent)
        );
        assert_eq!(None.expected_source_type(), Option::None);
    }

    // ------------------------------------------------------------------
    // Builder tests
    // ------------------------------------------------------------------

    #[test]
    fn test_builder_basic() {
        let hdr = ProvenanceBuilder::new(ProvNodeType::Entity, 0xDEADBEEF)
            .with_relation(ProvRelationKind::WasAttributedTo, 0xA1)
            .with_relation(ProvRelationKind::WasGeneratedBy, 0xA2)
            .build()
            .expect("valid provenance");

        assert_eq!(hdr.node_type, ProvNodeType::Entity);
        assert_eq!(hdr.node_id, 0xDEADBEEF);
        assert_eq!(hdr.relation_count(), 2);
        assert!(!hdr.has_overflow());
        assert_eq!(
            hdr.find_relation(ProvRelationKind::WasAttributedTo)
                .map(|r| r.target_id),
            Some(0xA1)
        );
    }

    #[test]
    fn test_builder_with_timestamp_and_plan() {
        let ts = HlcTimestamp::new(1234, 5, 1);
        let hdr = ProvenanceBuilder::new(ProvNodeType::Activity, 42)
            .with_timestamp(ts)
            .with_plan(99)
            .with_relation(ProvRelationKind::WasAssociatedWith, 7)
            .build()
            .unwrap();
        assert_eq!(hdr.prov_timestamp, ts);
        assert_eq!(hdr.plan_id, Some(99));
    }

    #[test]
    fn test_builder_fills_inline_slots_sequentially() {
        let hdr = ProvenanceBuilder::new(ProvNodeType::Entity, 1)
            .with_relation(ProvRelationKind::WasDerivedFrom, 10)
            .with_relation(ProvRelationKind::WasDerivedFrom, 11)
            .with_relation(ProvRelationKind::WasDerivedFrom, 12)
            .with_relation(ProvRelationKind::WasDerivedFrom, 13)
            .build()
            .unwrap();

        assert_eq!(hdr.relation_count(), 4);
        assert!(!hdr.has_overflow());
        for (i, r) in hdr.iter_relations().enumerate() {
            assert_eq!(r.target_id, 10 + i as u64);
        }
    }

    #[test]
    fn test_builder_overflow_without_ref_rejected() {
        let err = ProvenanceBuilder::new(ProvNodeType::Entity, 1)
            .with_relation(ProvRelationKind::WasDerivedFrom, 10)
            .with_relation(ProvRelationKind::WasDerivedFrom, 11)
            .with_relation(ProvRelationKind::WasDerivedFrom, 12)
            .with_relation(ProvRelationKind::WasDerivedFrom, 13)
            .with_relation(ProvRelationKind::WasDerivedFrom, 14)
            .build()
            .unwrap_err();
        assert_eq!(err, ProvenanceError::OverflowNotSet { excess: 1 });
    }

    #[test]
    fn test_builder_overflow_with_ref_succeeds() {
        let hdr = ProvenanceBuilder::new(ProvNodeType::Entity, 1)
            .with_relation(ProvRelationKind::WasDerivedFrom, 10)
            .with_relation(ProvRelationKind::WasDerivedFrom, 11)
            .with_relation(ProvRelationKind::WasDerivedFrom, 12)
            .with_relation(ProvRelationKind::WasDerivedFrom, 13)
            .with_relation(ProvRelationKind::WasDerivedFrom, 14)
            .with_relation(ProvRelationKind::WasDerivedFrom, 15)
            .with_overflow_ref(0xBEEF)
            .build()
            .unwrap();
        assert!(hdr.has_overflow());
        assert_eq!(hdr.overflow_ref, Some(0xBEEF));
        // Only 4 relations fit inline; the rest live in the overflow record.
        assert_eq!(hdr.relation_count(), INLINE_RELATION_SLOTS);
    }

    #[test]
    fn test_builder_rejects_none_relation() {
        let err = ProvenanceBuilder::new(ProvNodeType::Entity, 1)
            .with_relation(ProvRelationKind::None, 42)
            .build()
            .unwrap_err();
        assert_eq!(err, ProvenanceError::InvalidRelationKind);
    }

    #[test]
    fn test_builder_rejects_zero_node_id() {
        let err = ProvenanceBuilder::new(ProvNodeType::Entity, 0)
            .build()
            .unwrap_err();
        assert_eq!(err, ProvenanceError::InvalidNodeId);
    }

    #[test]
    fn test_builder_rejects_self_loop() {
        let err = ProvenanceBuilder::new(ProvNodeType::Entity, 7)
            .with_relation(ProvRelationKind::WasDerivedFrom, 7)
            .build()
            .unwrap_err();
        assert_eq!(err, ProvenanceError::SelfLoop { node_id: 7 });
    }

    #[test]
    fn test_builder_rejects_kind_type_mismatch() {
        // `Used` is Activity -> Entity; declaring from Entity is invalid.
        let err = ProvenanceBuilder::new(ProvNodeType::Entity, 1)
            .with_relation(ProvRelationKind::Used, 2)
            .build()
            .unwrap_err();
        assert_eq!(
            err,
            ProvenanceError::KindTypeMismatch {
                kind: ProvRelationKind::Used,
                node_type: ProvNodeType::Entity
            }
        );
    }

    #[test]
    fn test_plan_accepts_entity_relations() {
        // Plans are a subclass of Entity, so Entity relations must work.
        let hdr = ProvenanceBuilder::new(ProvNodeType::Plan, 100)
            .with_relation(ProvRelationKind::WasAttributedTo, 200)
            .build()
            .unwrap();
        assert_eq!(hdr.node_type, ProvNodeType::Plan);
    }

    // ------------------------------------------------------------------
    // Chain validation tests
    // ------------------------------------------------------------------

    #[test]
    fn test_validate_chain_simple() {
        // 1 -> 2 -> 3 -> end
        let parents = |n: u64| match n {
            1 => Some(2),
            2 => Some(3),
            _ => None,
        };
        assert_eq!(validate_chain(1, parents).unwrap(), 3);
    }

    #[test]
    fn test_validate_chain_detects_cycle() {
        // 1 -> 2 -> 1 cycle
        let parents = |n: u64| match n {
            1 => Some(2),
            2 => Some(1),
            _ => None,
        };
        let err = validate_chain(1, parents).unwrap_err();
        assert_eq!(err, ProvenanceError::CycleDetected { at_node: 1 });
    }

    #[test]
    fn test_validate_chain_depth_bounded() {
        // Unbounded linear chain should trip the depth guard.
        let parents = |n: u64| Some(n + 1);
        let err = validate_chain(1, parents).unwrap_err();
        assert!(matches!(err, ProvenanceError::ChainTooDeep { .. }));
    }

    // ------------------------------------------------------------------
    // Header helpers
    // ------------------------------------------------------------------

    #[test]
    fn test_header_iter_relations_skips_empty() {
        let mut hdr = ProvenanceHeader::new(ProvNodeType::Entity, 1);
        hdr.relations[0] = ProvRelation::new(ProvRelationKind::WasAttributedTo, 10);
        hdr.relations[2] = ProvRelation::new(ProvRelationKind::WasGeneratedBy, 20);
        let targets: Vec<u64> = hdr.iter_relations().map(|r| r.target_id).collect();
        assert_eq!(targets, vec![10, 20]);
    }

    #[test]
    fn test_header_validate_rejects_zero_node() {
        let hdr = ProvenanceHeader::new(ProvNodeType::Entity, 0);
        assert_eq!(hdr.validate().unwrap_err(), ProvenanceError::InvalidNodeId);
    }

    #[test]
    fn test_default_header_has_zero_node() {
        // Default exists for rkyv-friendliness; callers must fill node_id.
        let hdr = ProvenanceHeader::default();
        assert_eq!(hdr.node_id, 0);
        assert_eq!(hdr.relation_count(), 0);
    }
}