dreamwell_engine/

chronoshift.rs

// Chronoshift — deterministic timeline replay, checkpoint, and fork primitives.
//
// Provides:
//   - CheckpointBuilder:  snapshot creation from event streams and state
//   - ReplayEngine:       deterministic event replay with chain validation
//   - ForkSpec:           timeline fork specification
//   - TimelineDiff:       structural comparison between divergent timelines
//   - ProofBundle:        cryptographic proof of a timeline segment (Merkle tree)
//   - StateSnapshot:      serializable simulation state at a tick
//   - CanonEventSnapshot: lightweight event record for replay
//
// Hashing strategy (per CRYPTOGRAPHY.md):
//   - FNV-1a (64-bit): fast deterministic digests for event chains and tick hashes
//   - BLAKE3 (256-bit): cryptographic hashes for state snapshots and Merkle trees

use serde::{Deserialize, Serialize};

// Note: fnv1a_64 import removed — all hashing in chronoshift now uses BLAKE3.

// =============================================================================
// Error Types
// =============================================================================

/// Errors produced by Chronobreak operations.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum ChronoshiftError {
    /// Referenced checkpoint does not exist for the given timeline and tick.
    CheckpointNotFound { timeline: String, tick: u64 },
    /// Digest chain is broken at the specified event.
    DigestChainBroken {
        tick: u64,
        seq: u64,
        expected: String,
        actual: String,
    },
    /// Replay produced a different hash than the original, indicating
    /// non-determinism or state corruption.
    DeterminismViolation {
        tick: u64,
        source_hash: String,
        replay_hash: String,
    },
    /// Maximum number of concurrent forks has been reached.
    ForkLimitExceeded { max: u32, current: u32 },
    /// Replay buffer would exceed the maximum event cap.
    ReplayOverflow { max: usize, attempted: usize },
    /// Event tick is less than the previous event's tick (out of order).
    TickOrderViolation { prev_tick: u64, curr_tick: u64 },
    /// The requested replay range is invalid (from > to, or zero-length).
    ReplayRangeInvalid { from: u64, to: u64 },
    /// Referenced timeline does not exist.
    TimelineNotFound { timeline: String },
    /// Timeline has expired and can no longer be read or replayed.
    TimelineExpired { timeline: String, expired_at: u64 },
    /// Fork would exceed the compute budget cap.
    ComputeCapExceeded { cap_pct: u32 },
}

impl core::fmt::Display for ChronoshiftError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            Self::CheckpointNotFound { timeline, tick } => {
                write!(f, "checkpoint_not_found: timeline={timeline}, tick={tick}")
            }
            Self::DigestChainBroken {
                tick,
                seq,
                expected,
                actual,
            } => {
                write!(
                    f,
                    "digest_chain_broken: tick={tick}, seq={seq}, expected={expected}, actual={actual}"
                )
            }
            Self::DeterminismViolation {
                tick,
                source_hash,
                replay_hash,
            } => {
                write!(
                    f,
                    "determinism_violation: tick={tick}, source={source_hash}, replay={replay_hash}"
                )
            }
            Self::ForkLimitExceeded { max, current } => {
                write!(f, "fork_limit_exceeded: max={max}, current={current}")
            }
            Self::ReplayOverflow { max, attempted } => {
                write!(f, "replay_overflow: max={max}, attempted={attempted}")
            }
            Self::TickOrderViolation { prev_tick, curr_tick } => {
                write!(f, "tick_order_violation: prev_tick={prev_tick}, curr_tick={curr_tick}")
            }
            Self::ReplayRangeInvalid { from, to } => {
                write!(f, "replay_range_invalid: from={from}, to={to}")
            }
            Self::TimelineNotFound { timeline } => {
                write!(f, "timeline_not_found: {timeline}")
            }
            Self::TimelineExpired { timeline, expired_at } => {
                write!(f, "timeline_expired: {timeline}, expired_at={expired_at}")
            }
            Self::ComputeCapExceeded { cap_pct } => {
                write!(f, "compute_cap_exceeded: cap_pct={cap_pct}")
            }
        }
    }
}

// =============================================================================
// Data Snapshots
// =============================================================================

/// Lightweight event record for replay. Contains only the fields needed
/// to reconstruct the digest chain and replay deterministically.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct CanonEventSnapshot {
    pub event_id: String,
    pub timeline_id: String,
    pub event_type: String,
    pub scope_key: String,
    pub actor_id: String,
    pub target_id: String,
    pub payload: String,
    pub tick: u64,
    pub seq: u64,
    pub digest: String,
    pub prev_event_id: String,
}

/// Serializable snapshot of simulation state at a specific tick.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct StateSnapshot {
    pub timeline_id: String,
    pub tick: u64,
    pub entity_count: u64,
    pub event_count: u64,
    /// Head of each scope's digest chain: (scope_key, latest_digest).
    pub scope_chain_heads: Vec<(String, String)>,
    pub state_hash: String,
}

/// Immutable checkpoint record produced by `CheckpointBuilder::build`.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct CheckpointSnapshot {
    pub timeline_id: String,
    pub tick: u64,
    pub event_hash: String,
    pub state_hash: String,
}

// =============================================================================
// Fork Specification
// =============================================================================

/// Visibility level for forked timelines.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum ForkVisibilityLevel {
    Private,
    Shared,
    Public,
}

/// Specification for creating a new timeline fork from a parent.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct ForkSpec {
    pub parent_timeline: String,
    pub fork_tick: u64,
    pub name: String,
    pub visibility: ForkVisibilityLevel,
    /// Maximum compute budget as a percentage (0..=100).
    pub compute_cap_pct: u32,
    /// Time-to-live in ticks. The fork expires at `fork_tick + ttl_ticks`.
    pub ttl_ticks: u64,
}

// =============================================================================
// CheckpointBuilder
// =============================================================================

/// Constructs checkpoint snapshots from event streams and state.
pub struct CheckpointBuilder {
    timeline_id: String,
    tick: u64,
}

impl CheckpointBuilder {
    /// Create a builder targeting a specific timeline and tick.
    pub fn new(timeline_id: &str, tick: u64) -> Self {
        Self {
            timeline_id: timeline_id.to_string(),
            tick,
        }
    }

    /// Compute the BLAKE3 chain hash over all events up to this checkpoint.
    ///
    /// Events are hashed in order by feeding each event's digest.
    /// This produces the same result regardless of how many times it is
    /// computed, as long as the input events are in canonical order.
    pub fn compute_event_hash(events: &[CanonEventSnapshot]) -> String {
        let mut hasher = blake3::Hasher::new_derive_key("dreamwell.checkpoint.events.v1");
        for event in events {
            hasher.update(event.digest.as_bytes());
            hasher.update(b"|");
        }
        hasher.finalize().to_hex().to_string()
    }

    /// Compute BLAKE3 hash of the serialized state snapshot.
    pub fn compute_state_hash(state: &StateSnapshot) -> Result<String, String> {
        let serialized = serde_json::to_string(state).map_err(|e| format!("state_hash_serialization_failed:{}", e))?;
        Ok(blake3::hash(serialized.as_bytes()).to_hex().to_string())
    }

    /// Build a complete checkpoint snapshot.
    pub fn build(&self, events: &[CanonEventSnapshot], state: &StateSnapshot) -> Result<CheckpointSnapshot, String> {
        let event_hash = Self::compute_event_hash(events);
        let state_hash = Self::compute_state_hash(state)?;
        Ok(CheckpointSnapshot {
            timeline_id: self.timeline_id.clone(),
            tick: self.tick,
            event_hash,
            state_hash,
        })
    }
}

// =============================================================================
// ReplayEngine
// =============================================================================

/// Replays canon events from a source timeline onto a target timeline.
///
/// Events are validated for digest chain integrity before replay.
/// The engine supports tick-by-tick and range-based replay, and can
/// produce a determinism hash for comparison with the original.
/// Maximum number of events a ReplayEngine buffer will accept.
pub const MAX_REPLAY_EVENTS: usize = 1_000_000;

pub struct ReplayEngine {
    source_timeline: String,
    target_timeline: String,
    from_tick: u64,
    to_tick: u64,
    events: Vec<CanonEventSnapshot>,
}

impl ReplayEngine {
    /// Create a replay engine for the given source/target and tick range.
    pub fn new(source: &str, target: &str, from_tick: u64, to_tick: u64) -> Self {
        Self {
            source_timeline: source.to_string(),
            target_timeline: target.to_string(),
            from_tick,
            to_tick,
            events: Vec::new(),
        }
    }

    /// Return a reference to the source timeline ID.
    pub fn source_timeline(&self) -> &str {
        &self.source_timeline
    }

    /// Return a reference to the target timeline ID.
    pub fn target_timeline(&self) -> &str {
        &self.target_timeline
    }

    /// Return the start tick (inclusive).
    pub fn from_tick(&self) -> u64 {
        self.from_tick
    }

    /// Return the end tick (inclusive).
    pub fn to_tick(&self) -> u64 {
        self.to_tick
    }

    /// Return a reference to all loaded events.
    pub fn events(&self) -> &[CanonEventSnapshot] {
        &self.events
    }

    /// Append an event to the replay buffer.
    ///
    /// Returns `Err(ReplayOverflow)` if the buffer has reached `MAX_REPLAY_EVENTS`.
    pub fn add_event(&mut self, event: CanonEventSnapshot) -> Result<(), ChronoshiftError> {
        if self.events.len() >= MAX_REPLAY_EVENTS {
            return Err(ChronoshiftError::ReplayOverflow {
                max: MAX_REPLAY_EVENTS,
                attempted: self.events.len() + 1,
            });
        }
        self.events.push(event);
        Ok(())
    }

    /// Validate the digest chain of all loaded events.
    ///
    /// For each event after the first, recompute the expected digest from
    /// the event fields and compare it to the stored digest. The first
    /// event's digest is trusted as the chain root.
    ///
    /// Returns `Ok(())` if the chain is intact, or `Err` at the first
    /// broken link.
    pub fn validate_chain(&self) -> Result<(), ChronoshiftError> {
        if self.events.is_empty() {
            return Ok(());
        }

        for i in 1..self.events.len() {
            let prev = &self.events[i - 1];
            let curr = &self.events[i];

            // Tick ordering: current tick must not be less than previous tick.
            if curr.tick < prev.tick {
                return Err(ChronoshiftError::TickOrderViolation {
                    prev_tick: prev.tick,
                    curr_tick: curr.tick,
                });
            }

            // The current event must reference the previous event.
            if curr.prev_event_id != prev.event_id {
                return Err(ChronoshiftError::DigestChainBroken {
                    tick: curr.tick,
                    seq: curr.seq,
                    expected: prev.event_id.clone(),
                    actual: curr.prev_event_id.clone(),
                });
            }

            // Recompute the digest and verify.
            let recomputed = recompute_digest(curr);
            if recomputed != curr.digest {
                return Err(ChronoshiftError::DigestChainBroken {
                    tick: curr.tick,
                    seq: curr.seq,
                    expected: recomputed,
                    actual: curr.digest.clone(),
                });
            }
        }

        Ok(())
    }

    /// Get all events for a specific tick, in sequence order.
    pub fn replay_tick(&self, tick: u64) -> Vec<CanonEventSnapshot> {
        let mut tick_events: Vec<CanonEventSnapshot> = self.events.iter().filter(|e| e.tick == tick).cloned().collect();
        tick_events.sort_by_key(|e| e.seq);
        tick_events
    }

    /// Get all events in a tick range [from, to] inclusive, in order.
    pub fn replay_range(&self, from: u64, to: u64) -> Vec<CanonEventSnapshot> {
        if from > to {
            return Vec::new(); // inverted range returns empty — caller must validate
        }
        let mut range_events: Vec<CanonEventSnapshot> = self
            .events
            .iter()
            .filter(|e| e.tick >= from && e.tick <= to)
            .cloned()
            .collect();
        range_events.sort_by(|a, b| a.tick.cmp(&b.tick).then(a.seq.cmp(&b.seq)));
        range_events
    }

    /// Compute a BLAKE3 hash over all replayed events for determinism
    /// comparison. The hash covers event_id, event_type, tick, seq,
    /// and digest of every event in canonical order.
    pub fn compute_determinism_hash(&self) -> String {
        let mut sorted = self.events.clone();
        sorted.sort_by(|a, b| a.tick.cmp(&b.tick).then(a.seq.cmp(&b.seq)));

        let mut hasher = blake3::Hasher::new();
        for event in &sorted {
            hasher.update(event.event_id.as_bytes());
            hasher.update(event.event_type.as_bytes());
            hasher.update(&event.tick.to_le_bytes());
            hasher.update(&event.seq.to_le_bytes());
            hasher.update(event.digest.as_bytes());
        }
        hasher.finalize().to_hex().to_string()
    }
}

// =============================================================================
// Timeline Diff
// =============================================================================

/// A single event mismatch between two timelines at the same (tick, seq).
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct EventMismatch {
    pub tick: u64,
    pub seq: u64,
    pub source_digest: String,
    pub target_digest: String,
    pub source_event_type: String,
    pub target_event_type: String,
}

/// Structural diff result between two timelines over a tick range.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct TimelineDiff {
    pub source: String,
    pub target: String,
    pub from_tick: u64,
    pub to_tick: u64,
    pub source_event_count: u64,
    pub target_event_count: u64,
    /// The first tick at which the timelines diverge, if any.
    pub divergence_tick: Option<u64>,
    /// All events where the digests differ at the same (tick, seq).
    pub mismatched_events: Vec<EventMismatch>,
    /// True if all events in the overlap produced identical digests.
    pub determinism_verified: bool,
}

// =============================================================================
// ProofBundle
// =============================================================================

/// Cryptographic proof of a timeline segment.
///
/// Binds a contiguous sequence of canon events to a Merkle root,
/// allowing offline verification of segment integrity without
/// replaying the full chain.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct ProofBundle {
    pub proof_id: String,
    pub timeline_id: String,
    pub from_tick: u64,
    pub to_tick: u64,
    pub event_count: u64,
    pub root_event_id: String,
    pub final_event_id: String,
    pub root_digest: String,
    pub final_digest: String,
    pub state_hash_start: String,
    pub state_hash_end: String,
    pub merkle_root: String,
    pub created_at_tick: u64,
}

impl ProofBundle {
    /// Compute the BLAKE3 Merkle root over event digests.
    pub fn compute_merkle_root(events: &[CanonEventSnapshot]) -> String {
        let leaves: Vec<String> = events.iter().map(|e| e.digest.clone()).collect();
        compute_merkle_tree(&leaves)
    }

    /// Verify the digest chain of the given events.
    ///
    /// Delegates to the same chain-validation logic used by `ReplayEngine`.
    pub fn verify_chain(events: &[CanonEventSnapshot]) -> Result<(), ChronoshiftError> {
        if events.is_empty() {
            return Ok(());
        }

        for i in 1..events.len() {
            let prev = &events[i - 1];
            let curr = &events[i];

            if curr.prev_event_id != prev.event_id {
                return Err(ChronoshiftError::DigestChainBroken {
                    tick: curr.tick,
                    seq: curr.seq,
                    expected: prev.event_id.clone(),
                    actual: curr.prev_event_id.clone(),
                });
            }

            let recomputed = recompute_digest(curr);
            if recomputed != curr.digest {
                return Err(ChronoshiftError::DigestChainBroken {
                    tick: curr.tick,
                    seq: curr.seq,
                    expected: recomputed,
                    actual: curr.digest.clone(),
                });
            }
        }

        Ok(())
    }
}

// =============================================================================
// Merkle Tree
// =============================================================================

/// Compute a binary Merkle tree root from leaf hashes using BLAKE3.
///
/// Leaves are hashed as-is (they are already hex-encoded digests).
/// Internal nodes are `BLAKE3(left || right)`. If the number of leaves
/// at any level is odd, the last leaf is promoted unpaired.
///
/// Returns the 64-character hex root hash. An empty input returns a
/// BLAKE3 hash of the empty string (well-defined zero value).
pub fn compute_merkle_tree(leaves: &[String]) -> String {
    if leaves.is_empty() {
        return blake3::hash(b"").to_hex().to_string();
    }

    // Hash each leaf to produce a uniform-length layer.
    let mut layer: Vec<blake3::Hash> = leaves.iter().map(|leaf| blake3::hash(leaf.as_bytes())).collect();

    while layer.len() > 1 {
        let mut next_layer = Vec::with_capacity(layer.len().div_ceil(2));

        let mut i = 0;
        while i + 1 < layer.len() {
            let mut hasher = blake3::Hasher::new();
            hasher.update(layer[i].as_bytes());
            hasher.update(layer[i + 1].as_bytes());
            next_layer.push(hasher.finalize());
            i += 2;
        }

        // Odd leaf: hash with itself per RFC 6962 style instead of promoting unpaired.
        if i < layer.len() {
            let mut hasher = blake3::Hasher::new();
            hasher.update(layer[i].as_bytes());
            hasher.update(layer[i].as_bytes());
            next_layer.push(hasher.finalize());
        }

        layer = next_layer;
    }

    layer[0].to_hex().to_string()
}

// =============================================================================
// Helper Functions
// =============================================================================

/// Recompute an event's BLAKE3 digest from its fields.
///
/// Delegates to `canon::compute_event_digest` to ensure a single source of truth
/// for the digest format.
fn recompute_digest(event: &CanonEventSnapshot) -> String {
    crate::canon::compute_event_digest(
        &event.event_id,
        &event.event_type,
        event.tick,
        event.seq,
        &event.timeline_id,
        &event.scope_key,
        &event.actor_id,
        &event.prev_event_id,
    )
}

/// Compare two event streams and produce a structural diff.
///
/// Both streams are filtered to the `[from_tick, to_tick]` range.
/// Events are matched by (tick, seq) pairs; mismatches are recorded
/// when digests differ. The divergence tick is the first tick
/// containing a mismatch.
pub fn diff_timelines(
    source: &[CanonEventSnapshot],
    target: &[CanonEventSnapshot],
    from_tick: u64,
    to_tick: u64,
) -> TimelineDiff {
    let source_filtered: Vec<&CanonEventSnapshot> = source
        .iter()
        .filter(|e| e.tick >= from_tick && e.tick <= to_tick)
        .collect();
    let target_filtered: Vec<&CanonEventSnapshot> = target
        .iter()
        .filter(|e| e.tick >= from_tick && e.tick <= to_tick)
        .collect();

    let source_timeline = source_filtered
        .first()
        .map(|e| e.timeline_id.clone())
        .unwrap_or_default();
    let target_timeline = target_filtered
        .first()
        .map(|e| e.timeline_id.clone())
        .unwrap_or_default();

    // Build lookup: (tick, seq) -> event for the target.
    let mut target_map: std::collections::HashMap<(u64, u64), &CanonEventSnapshot> = std::collections::HashMap::new();
    for event in &target_filtered {
        target_map.insert((event.tick, event.seq), event);
    }

    let mut mismatched_events = Vec::new();
    let mut divergence_tick: Option<u64> = None;

    for src_event in &source_filtered {
        let key = (src_event.tick, src_event.seq);
        if let Some(tgt_event) = target_map.get(&key) {
            if src_event.digest != tgt_event.digest {
                mismatched_events.push(EventMismatch {
                    tick: src_event.tick,
                    seq: src_event.seq,
                    source_digest: src_event.digest.clone(),
                    target_digest: tgt_event.digest.clone(),
                    source_event_type: src_event.event_type.clone(),
                    target_event_type: tgt_event.event_type.clone(),
                });
                if divergence_tick.is_none() || src_event.tick < divergence_tick.unwrap() {
                    divergence_tick = Some(src_event.tick);
                }
            }
        } else {
            // Source event has no counterpart in target — divergence.
            mismatched_events.push(EventMismatch {
                tick: src_event.tick,
                seq: src_event.seq,
                source_digest: src_event.digest.clone(),
                target_digest: String::new(),
                source_event_type: src_event.event_type.clone(),
                target_event_type: String::new(),
            });
            if divergence_tick.is_none() || src_event.tick < divergence_tick.unwrap() {
                divergence_tick = Some(src_event.tick);
            }
        }
    }

    // Check for target events not present in source.
    let mut source_map: std::collections::HashMap<(u64, u64), &CanonEventSnapshot> = std::collections::HashMap::new();
    for event in &source_filtered {
        source_map.insert((event.tick, event.seq), event);
    }
    for tgt_event in &target_filtered {
        let key = (tgt_event.tick, tgt_event.seq);
        if !source_map.contains_key(&key) {
            mismatched_events.push(EventMismatch {
                tick: tgt_event.tick,
                seq: tgt_event.seq,
                source_digest: String::new(),
                target_digest: tgt_event.digest.clone(),
                source_event_type: String::new(),
                target_event_type: tgt_event.event_type.clone(),
            });
            if divergence_tick.is_none() || tgt_event.tick < divergence_tick.unwrap() {
                divergence_tick = Some(tgt_event.tick);
            }
        }
    }

    // Sort mismatches by (tick, seq) for deterministic output.
    mismatched_events.sort_by(|a, b| a.tick.cmp(&b.tick).then(a.seq.cmp(&b.seq)));

    let determinism_verified = mismatched_events.is_empty();

    TimelineDiff {
        source: source_timeline,
        target: target_timeline,
        from_tick,
        to_tick,
        source_event_count: source_filtered.len() as u64,
        target_event_count: target_filtered.len() as u64,
        divergence_tick,
        mismatched_events,
        determinism_verified,
    }
}

/// Check whether two event streams are deterministically equivalent.
///
/// Returns `true` if both streams have the same length and every
/// event at the same index has an identical digest.
pub fn verify_determinism(original: &[CanonEventSnapshot], replay: &[CanonEventSnapshot]) -> bool {
    if original.len() != replay.len() {
        return false;
    }
    original.iter().zip(replay.iter()).all(|(o, r)| o.digest == r.digest)
}

/// Compute the BLAKE3 hash of all events at a specific tick.
///
/// Events are filtered to the given tick, sorted by seq, and their
/// digests are fed into a BLAKE3 hasher. Returns a 64-character hex string.
pub fn compute_tick_hash(events: &[CanonEventSnapshot], tick: u64) -> String {
    let mut tick_events: Vec<&CanonEventSnapshot> = events.iter().filter(|e| e.tick == tick).collect();
    tick_events.sort_by_key(|e| e.seq);

    let mut hasher = blake3::Hasher::new_derive_key("dreamwell.chronoshift.tick.v1");
    for event in &tick_events {
        hasher.update(event.digest.as_bytes());
        hasher.update(b"|");
    }

    hasher.finalize().to_hex().to_string()
}

// =============================================================================
// Tests
// =============================================================================

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

    fn make_event(
        id: &str,
        timeline: &str,
        event_type: &str,
        tick: u64,
        seq: u64,
        prev_id: &str,
    ) -> CanonEventSnapshot {
        let scope_key = format!("tl:{}/lvl:world/id:test", timeline);
        let digest =
            crate::canon::compute_event_digest(id, event_type, tick, seq, timeline, &scope_key, "actor_1", prev_id);
        CanonEventSnapshot {
            event_id: id.to_string(),
            timeline_id: timeline.to_string(),
            event_type: event_type.to_string(),
            scope_key,
            actor_id: "actor_1".to_string(),
            target_id: "target_1".to_string(),
            payload: "{}".to_string(),
            tick,
            seq,
            digest,
            prev_event_id: prev_id.to_string(),
        }
    }

    fn make_chain(timeline: &str, count: usize) -> Vec<CanonEventSnapshot> {
        let mut events = Vec::with_capacity(count);
        let mut prev_id = String::new();
        for i in 0..count {
            let id = format!("evt:{timeline}:{}:{:06}", i / 3, i % 3);
            let tick = (i / 3) as u64;
            let seq = (i % 3) as u64;
            let event = make_event(&id, timeline, "test_event", tick, seq, &prev_id);
            prev_id = id;
            events.push(event);
        }
        events
    }

    #[test]
    fn test_checkpoint_builder_event_hash_deterministic() {
        let events = make_chain("tl_sacred", 5);
        let hash_a = CheckpointBuilder::compute_event_hash(&events);
        let hash_b = CheckpointBuilder::compute_event_hash(&events);
        assert_eq!(hash_a, hash_b);
        assert_eq!(hash_a.len(), 64);
    }

    #[test]
    fn test_checkpoint_builder_state_hash_uses_blake3() {
        let state = StateSnapshot {
            timeline_id: "tl_sacred".to_string(),
            tick: 10,
            entity_count: 100,
            event_count: 50,
            scope_chain_heads: vec![("scope_a".to_string(), "abc123".to_string())],
            state_hash: String::new(),
        };
        let hash = CheckpointBuilder::compute_state_hash(&state).unwrap();
        // BLAKE3 hex is 64 characters.
        assert_eq!(hash.len(), 64);
    }

    #[test]
    fn test_checkpoint_builder_build() {
        let events = make_chain("tl_sacred", 3);
        let state = StateSnapshot {
            timeline_id: "tl_sacred".to_string(),
            tick: 1,
            entity_count: 10,
            event_count: 3,
            scope_chain_heads: vec![],
            state_hash: String::new(),
        };
        let builder = CheckpointBuilder::new("tl_sacred", 1);
        let cp = builder.build(&events, &state).unwrap();
        assert_eq!(cp.timeline_id, "tl_sacred");
        assert_eq!(cp.tick, 1);
        assert!(!cp.event_hash.is_empty());
        assert!(!cp.state_hash.is_empty());
    }

    #[test]
    fn test_replay_engine_validate_chain_ok() {
        let events = make_chain("tl_a", 6);
        let mut engine = ReplayEngine::new("tl_a", "tl_b", 0, 2);
        for e in events {
            engine.add_event(e).unwrap();
        }
        assert!(engine.validate_chain().is_ok());
    }

    #[test]
    fn test_replay_engine_validate_chain_broken() {
        let mut events = make_chain("tl_a", 4);
        // Break the chain by altering the second event's prev pointer.
        events[2].prev_event_id = "wrong_id".to_string();
        let mut engine = ReplayEngine::new("tl_a", "tl_b", 0, 1);
        for e in events {
            engine.add_event(e).unwrap();
        }
        let result = engine.validate_chain();
        assert!(result.is_err());
        match result.unwrap_err() {
            ChronoshiftError::DigestChainBroken { tick, .. } => {
                assert_eq!(tick, 0);
            }
            other => panic!("unexpected error: {other:?}"),
        }
    }

    #[test]
    fn test_replay_engine_replay_tick() {
        let events = make_chain("tl_a", 9);
        let mut engine = ReplayEngine::new("tl_a", "tl_b", 0, 3);
        for e in events {
            engine.add_event(e).unwrap();
        }
        let tick_1 = engine.replay_tick(1);
        assert_eq!(tick_1.len(), 3);
        for e in &tick_1 {
            assert_eq!(e.tick, 1);
        }
        // Verify sorted by seq.
        assert!(tick_1[0].seq <= tick_1[1].seq);
        assert!(tick_1[1].seq <= tick_1[2].seq);
    }

    #[test]
    fn test_replay_engine_replay_range() {
        let events = make_chain("tl_a", 9);
        let mut engine = ReplayEngine::new("tl_a", "tl_b", 0, 3);
        for e in events {
            engine.add_event(e).unwrap();
        }
        let range = engine.replay_range(0, 1);
        assert_eq!(range.len(), 6);
        for e in &range {
            assert!(e.tick <= 1);
        }
    }

    #[test]
    fn test_replay_engine_determinism_hash() {
        let events = make_chain("tl_a", 5);
        let mut engine = ReplayEngine::new("tl_a", "tl_b", 0, 2);
        for e in events.clone() {
            engine.add_event(e).unwrap();
        }
        let hash_a = engine.compute_determinism_hash();
        let hash_b = engine.compute_determinism_hash();
        assert_eq!(hash_a, hash_b);
        assert_eq!(hash_a.len(), 64); // BLAKE3
    }

    #[test]
    fn test_replay_engine_accessors() {
        let engine = ReplayEngine::new("src", "tgt", 10, 20);
        assert_eq!(engine.source_timeline(), "src");
        assert_eq!(engine.target_timeline(), "tgt");
        assert_eq!(engine.from_tick(), 10);
        assert_eq!(engine.to_tick(), 20);
        assert!(engine.events().is_empty());
    }

    #[test]
    fn test_diff_timelines_identical() {
        let events = make_chain("tl_a", 6);
        let diff = diff_timelines(&events, &events, 0, 2);
        assert!(diff.determinism_verified);
        assert!(diff.divergence_tick.is_none());
        assert!(diff.mismatched_events.is_empty());
        assert_eq!(diff.source_event_count, 6);
        assert_eq!(diff.target_event_count, 6);
    }

    #[test]
    fn test_diff_timelines_divergent() {
        let source = make_chain("tl_a", 6);
        let mut target = make_chain("tl_a", 6);
        // Alter an event's digest in the target at index 3 (tick 1).
        target[3].digest = "0000000000000000".to_string();
        let diff = diff_timelines(&source, &target, 0, 2);
        assert!(!diff.determinism_verified);
        assert_eq!(diff.divergence_tick, Some(1));
        assert!(!diff.mismatched_events.is_empty());
    }

    #[test]
    fn test_diff_timelines_different_lengths() {
        let source = make_chain("tl_a", 6);
        let target = make_chain("tl_b", 3);
        let diff = diff_timelines(&source, &target, 0, 2);
        assert!(!diff.determinism_verified);
        assert_eq!(diff.source_event_count, 6);
        assert_eq!(diff.target_event_count, 3);
    }

    #[test]
    fn test_verify_determinism_true() {
        let events = make_chain("tl_a", 5);
        assert!(verify_determinism(&events, &events));
    }

    #[test]
    fn test_verify_determinism_false_different_digests() {
        let original = make_chain("tl_a", 3);
        let mut replay = original.clone();
        replay[1].digest = "ffffffffffffffff".to_string();
        assert!(!verify_determinism(&original, &replay));
    }

    #[test]
    fn test_verify_determinism_false_different_lengths() {
        let original = make_chain("tl_a", 5);
        let replay = make_chain("tl_a", 3);
        assert!(!verify_determinism(&original, &replay));
    }

    #[test]
    fn test_compute_tick_hash_deterministic() {
        let events = make_chain("tl_a", 9);
        let hash_a = compute_tick_hash(&events, 1);
        let hash_b = compute_tick_hash(&events, 1);
        assert_eq!(hash_a, hash_b);
        assert_eq!(hash_a.len(), 64);
    }

    #[test]
    fn test_compute_tick_hash_different_ticks() {
        let events = make_chain("tl_a", 9);
        let hash_0 = compute_tick_hash(&events, 0);
        let hash_1 = compute_tick_hash(&events, 1);
        assert_ne!(hash_0, hash_1);
    }

    #[test]
    fn test_compute_tick_hash_empty_tick() {
        let events = make_chain("tl_a", 3);
        let hash = compute_tick_hash(&events, 999);
        // Should still produce a valid 64-char BLAKE3 hex digest.
        assert_eq!(hash.len(), 64);
    }

    #[test]
    fn test_merkle_tree_single_leaf() {
        let leaves = vec!["abc123".to_string()];
        let root = compute_merkle_tree(&leaves);
        let expected = blake3::hash(b"abc123").to_hex().to_string();
        assert_eq!(root, expected);
    }

    #[test]
    fn test_merkle_tree_two_leaves() {
        let leaves = vec!["aaa".to_string(), "bbb".to_string()];
        let root = compute_merkle_tree(&leaves);

        let left = blake3::hash(b"aaa");
        let right = blake3::hash(b"bbb");
        let mut hasher = blake3::Hasher::new();
        hasher.update(left.as_bytes());
        hasher.update(right.as_bytes());
        let expected = hasher.finalize().to_hex().to_string();
        assert_eq!(root, expected);
    }

    #[test]
    fn test_merkle_tree_odd_leaves() {
        let leaves = vec!["a".to_string(), "b".to_string(), "c".to_string()];
        let root = compute_merkle_tree(&leaves);
        assert_eq!(root.len(), 64);
    }

    #[test]
    fn test_merkle_tree_empty() {
        let root = compute_merkle_tree(&[]);
        let expected = blake3::hash(b"").to_hex().to_string();
        assert_eq!(root, expected);
    }

    #[test]
    fn test_merkle_tree_deterministic() {
        let leaves: Vec<String> = (0..8).map(|i| format!("leaf_{i}")).collect();
        let root_a = compute_merkle_tree(&leaves);
        let root_b = compute_merkle_tree(&leaves);
        assert_eq!(root_a, root_b);
    }

    #[test]
    fn test_proof_bundle_compute_merkle_root() {
        let events = make_chain("tl_a", 4);
        let root = ProofBundle::compute_merkle_root(&events);
        assert_eq!(root.len(), 64);
    }

    #[test]
    fn test_proof_bundle_verify_chain_ok() {
        let events = make_chain("tl_a", 5);
        assert!(ProofBundle::verify_chain(&events).is_ok());
    }

    #[test]
    fn test_proof_bundle_verify_chain_broken() {
        let mut events = make_chain("tl_a", 4);
        events[1].digest = "0000000000000000".to_string();
        assert!(ProofBundle::verify_chain(&events).is_err());
    }

    #[test]
    fn test_fork_spec_roundtrip() {
        let spec = ForkSpec {
            parent_timeline: "tl_sacred".to_string(),
            fork_tick: 100,
            name: "what_if_war".to_string(),
            visibility: ForkVisibilityLevel::Shared,
            compute_cap_pct: 25,
            ttl_ticks: 500,
        };
        let json = serde_json::to_string(&spec).unwrap();
        let deserialized: ForkSpec = serde_json::from_str(&json).unwrap();
        assert_eq!(spec, deserialized);
    }

    #[test]
    fn test_chronoshift_error_display() {
        let err = ChronoshiftError::CheckpointNotFound {
            timeline: "tl_a".to_string(),
            tick: 42,
        };
        let msg = format!("{err}");
        assert!(msg.contains("checkpoint_not_found"));
        assert!(msg.contains("tl_a"));
        assert!(msg.contains("42"));
    }

    #[test]
    fn test_state_snapshot_serialization() {
        let state = StateSnapshot {
            timeline_id: "tl_sacred".to_string(),
            tick: 50,
            entity_count: 1000,
            event_count: 500,
            scope_chain_heads: vec![
                ("world:ayora".to_string(), "abc123".to_string()),
                ("realm:verdant".to_string(), "def456".to_string()),
            ],
            state_hash: "deadbeef".to_string(),
        };
        let json = serde_json::to_string(&state).unwrap();
        let deserialized: StateSnapshot = serde_json::from_str(&json).unwrap();
        assert_eq!(state, deserialized);
    }

    #[test]
    fn test_replay_engine_empty_chain_validates() {
        let engine = ReplayEngine::new("a", "b", 0, 0);
        assert!(engine.validate_chain().is_ok());
    }

    #[test]
    fn test_replay_engine_single_event_validates() {
        let events = make_chain("tl_a", 1);
        let mut engine = ReplayEngine::new("tl_a", "tl_b", 0, 0);
        engine.add_event(events[0].clone()).unwrap();
        assert!(engine.validate_chain().is_ok());
    }

    #[test]
    fn test_replay_engine_overflow() {
        let mut engine = ReplayEngine::new("a", "b", 0, 0);
        // Fill to the cap — we can't actually push 1M events in a test, so
        // directly set the events vec length and test the guard.
        engine.events = Vec::with_capacity(0);
        engine
            .events
            .resize(MAX_REPLAY_EVENTS, make_event("e", "t", "x", 0, 0, ""));
        let result = engine.add_event(make_event("overflow", "t", "x", 1, 0, "e"));
        assert!(result.is_err());
        match result.unwrap_err() {
            ChronoshiftError::ReplayOverflow { max, .. } => {
                assert_eq!(max, MAX_REPLAY_EVENTS);
            }
            other => panic!("unexpected error: {other:?}"),
        }
    }

    #[test]
    fn test_validate_chain_tick_order_violation() {
        // Create two events where the second has a lower tick than the first.
        let e0 = make_event("evt:tl_a:10:000000", "tl_a", "test_event", 10, 0, "");
        let e1 = make_event("evt:tl_a:5:000000", "tl_a", "test_event", 5, 0, "evt:tl_a:10:000000");
        let mut engine = ReplayEngine::new("tl_a", "tl_b", 0, 20);
        engine.add_event(e0).unwrap();
        engine.add_event(e1).unwrap();
        let result = engine.validate_chain();
        assert!(result.is_err());
        match result.unwrap_err() {
            ChronoshiftError::TickOrderViolation { prev_tick, curr_tick } => {
                assert_eq!(prev_tick, 10);
                assert_eq!(curr_tick, 5);
            }
            other => panic!("unexpected error: {other:?}"),
        }
    }
}