vortex_trace/

determinism.rs

//! Determinism verification: double-run same-seed trace identity.
//!
//! Runs a simulation twice with the same seed and verifies that both
//! runs produce bit-identical traces. Any divergence indicates a
//! non-determinism bug (e.g., HashMap iteration order, thread scheduling,
//! system time leaking into the sim).

use crate::{SimTrace, TraceEvent, TraceEventKind};

/// Result of a determinism check.
#[derive(Debug, Clone)]
pub struct DeterminismResult {
    /// Whether the two runs produced identical traces.
    pub deterministic: bool,
    /// First diverging event index (if any).
    pub divergence_at: Option<usize>,
    /// Description of the divergence (if any).
    pub divergence_description: Option<String>,
    /// Number of events in run 1.
    pub run1_events: usize,
    /// Number of events in run 2.
    pub run2_events: usize,
}

impl DeterminismResult {
    /// Whether the simulation is deterministic.
    pub fn is_deterministic(&self) -> bool {
        self.deterministic
    }
}

/// Verify determinism by running a simulation twice and comparing traces.
///
/// - `sim_fn`: `(seed) -> SimTrace` — runs the simulation with a seed and
///   returns the resulting trace.
/// - `seed`: the seed to test with.
///
/// ```
/// use vortex_trace::determinism::verify_determinism;
/// use vortex_trace::{SimTrace, TraceEventKind};
///
/// let result = verify_determinism(42, |seed| {
///     let mut trace = SimTrace::new();
///     // Deterministic simulation: same seed → same events
///     for i in 0..10 {
///         trace.record(i, 1, TraceEventKind::TimerFired {
///             timer_type: format!("t{}", seed + i),
///         });
///     }
///     trace
/// });
/// assert!(result.is_deterministic());
/// ```
pub fn verify_determinism<F>(seed: u64, sim_fn: F) -> DeterminismResult
where
    F: Fn(u64) -> SimTrace,
{
    let trace1 = sim_fn(seed);
    let trace2 = sim_fn(seed);

    compare_traces(&trace1, &trace2)
}

/// Compare two traces for equality, returning detailed divergence info.
pub fn compare_traces(trace1: &SimTrace, trace2: &SimTrace) -> DeterminismResult {
    let events1 = trace1.events();
    let events2 = trace2.events();

    if events1.len() != events2.len() {
        return DeterminismResult {
            deterministic: false,
            divergence_at: Some(events1.len().min(events2.len())),
            divergence_description: Some(format!(
                "Trace length mismatch: run1={}, run2={}",
                events1.len(),
                events2.len()
            )),
            run1_events: events1.len(),
            run2_events: events2.len(),
        };
    }

    for (i, (e1, e2)) in events1.iter().zip(events2.iter()).enumerate() {
        if let Some(desc) = events_differ(e1, e2) {
            return DeterminismResult {
                deterministic: false,
                divergence_at: Some(i),
                divergence_description: Some(format!("Event {i}: {desc}")),
                run1_events: events1.len(),
                run2_events: events2.len(),
            };
        }
    }

    DeterminismResult {
        deterministic: true,
        divergence_at: None,
        divergence_description: None,
        run1_events: events1.len(),
        run2_events: events2.len(),
    }
}

/// Compare two events, returning a description of the difference if any.
fn events_differ(e1: &TraceEvent, e2: &TraceEvent) -> Option<String> {
    if e1.tick != e2.tick {
        return Some(format!("tick differs: {} vs {}", e1.tick, e2.tick));
    }
    if e1.node_id != e2.node_id {
        return Some(format!("node_id differs: {} vs {}", e1.node_id, e2.node_id));
    }
    if !event_kinds_equal(&e1.kind, &e2.kind) {
        return Some(format!("kind differs: {:?} vs {:?}", e1.kind, e2.kind));
    }
    None
}

/// Compare two event kinds for equality.
fn event_kinds_equal(a: &TraceEventKind, b: &TraceEventKind) -> bool {
    match (a, b) {
        (
            TraceEventKind::MessageSent {
                to: to1,
                msg_type: mt1,
                size_bytes: s1,
            },
            TraceEventKind::MessageSent {
                to: to2,
                msg_type: mt2,
                size_bytes: s2,
            },
        ) => to1 == to2 && mt1 == mt2 && s1 == s2,
        (
            TraceEventKind::MessageDelivered {
                from: f1,
                msg_type: mt1,
                size_bytes: s1,
            },
            TraceEventKind::MessageDelivered {
                from: f2,
                msg_type: mt2,
                size_bytes: s2,
            },
        ) => f1 == f2 && mt1 == mt2 && s1 == s2,
        (
            TraceEventKind::MessageDropped {
                from: f1,
                to: t1,
                reason: r1,
            },
            TraceEventKind::MessageDropped {
                from: f2,
                to: t2,
                reason: r2,
            },
        ) => f1 == f2 && t1 == t2 && r1 == r2,
        (
            TraceEventKind::TimerFired { timer_type: t1 },
            TraceEventKind::TimerFired { timer_type: t2 },
        ) => t1 == t2,
        (
            TraceEventKind::StateTransition {
                from_state: fs1,
                to_state: ts1,
                metadata: m1,
            },
            TraceEventKind::StateTransition {
                from_state: fs2,
                to_state: ts2,
                metadata: m2,
            },
        ) => fs1 == fs2 && ts1 == ts2 && m1 == m2,
        (
            TraceEventKind::FaultInjected {
                fault_type: ft1,
                details: d1,
            },
            TraceEventKind::FaultInjected {
                fault_type: ft2,
                details: d2,
            },
        ) => ft1 == ft2 && d1 == d2,
        (
            TraceEventKind::FaultHealed {
                fault_type: ft1,
                details: d1,
            },
            TraceEventKind::FaultHealed {
                fault_type: ft2,
                details: d2,
            },
        ) => ft1 == ft2 && d1 == d2,
        (
            TraceEventKind::StorageOp {
                op_type: ot1,
                key_count: kc1,
            },
            TraceEventKind::StorageOp {
                op_type: ot2,
                key_count: kc2,
            },
        ) => ot1 == ot2 && kc1 == kc2,
        (
            TraceEventKind::Custom { tag: t1, data: d1 },
            TraceEventKind::Custom { tag: t2, data: d2 },
        ) => t1 == t2 && d1 == d2,
        _ => false, // Different variants
    }
}

/// Assert that a simulation is deterministic (same seed produces identical trace).
///
/// This is the recommended way to enforce R-11 in CI. Call this macro in your
/// test functions to automatically run the simulation twice and assert trace identity.
///
/// ```rust,ignore
/// use vortex_trace::assert_deterministic;
///
/// #[test]
/// fn test_my_simulation_is_deterministic() {
///     assert_deterministic!(42, |seed| {
///         let mut trace = vortex_trace::SimTrace::new();
///         // ... run your simulation ...
///         trace
///     });
/// }
/// ```
#[macro_export]
macro_rules! assert_deterministic {
    ($seed:expr, $sim_fn:expr) => {{
        let result = $crate::verify_determinism($seed, $sim_fn);
        assert!(
            result.is_deterministic(),
            "DETERMINISM VIOLATION (R-11): seed={}, divergence at event {:?}: {}",
            $seed,
            result.divergence_at,
            result
                .divergence_description
                .as_deref()
                .unwrap_or("unknown"),
        );
    }};
}

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

    #[test]
    fn test_deterministic_simulation() {
        let result = verify_determinism(42, |seed| {
            let mut trace = SimTrace::new();
            for i in 0..10 {
                trace.record(
                    i,
                    1,
                    TraceEventKind::TimerFired {
                        timer_type: format!("t{}", seed + i),
                    },
                );
            }
            trace
        });
        assert!(result.is_deterministic());
        assert_eq!(result.run1_events, 10);
        assert_eq!(result.run2_events, 10);
    }

    #[test]
    fn test_non_deterministic_simulation() {
        use std::sync::atomic::{AtomicU64, Ordering};
        static CALL_COUNT: AtomicU64 = AtomicU64::new(0);

        let result = verify_determinism(42, |_seed| {
            let call = CALL_COUNT.fetch_add(1, Ordering::SeqCst);
            let mut trace = SimTrace::new();
            trace.record(
                call,
                1,
                TraceEventKind::Custom {
                    tag: "test".into(),
                    data: format!("call={call}"),
                },
            );
            trace
        });
        assert!(!result.is_deterministic());
        assert_eq!(result.divergence_at, Some(0));
    }

    #[test]
    fn test_length_mismatch() {
        use std::sync::atomic::{AtomicU64, Ordering};
        static CALL_COUNT2: AtomicU64 = AtomicU64::new(0);

        let result = verify_determinism(42, |_seed| {
            let call = CALL_COUNT2.fetch_add(1, Ordering::SeqCst);
            let mut trace = SimTrace::new();
            for i in 0..=call {
                trace.record(
                    i,
                    1,
                    TraceEventKind::TimerFired {
                        timer_type: "t".into(),
                    },
                );
            }
            trace
        });
        assert!(!result.is_deterministic());
        assert!(
            result
                .divergence_description
                .unwrap()
                .contains("length mismatch")
        );
    }

    #[test]
    fn test_compare_traces_identical() {
        let mut t1 = SimTrace::new();
        let mut t2 = SimTrace::new();
        for i in 0..5 {
            let kind = TraceEventKind::MessageSent {
                to: 2,
                msg_type: "rpc".into(),
                size_bytes: 64,
            };
            t1.record(i, 1, kind.clone());
            t2.record(i, 1, kind);
        }
        let result = compare_traces(&t1, &t2);
        assert!(result.is_deterministic());
    }

    #[test]
    fn test_compare_traces_divergent() {
        let mut t1 = SimTrace::new();
        let mut t2 = SimTrace::new();
        t1.record(
            0,
            1,
            TraceEventKind::TimerFired {
                timer_type: "a".into(),
            },
        );
        t2.record(
            0,
            1,
            TraceEventKind::TimerFired {
                timer_type: "b".into(),
            },
        );
        let result = compare_traces(&t1, &t2);
        assert!(!result.is_deterministic());
        assert_eq!(result.divergence_at, Some(0));
    }
}