asupersync/trace/
divergence.rs

1//! Replay divergence diagnostics for actionable debugging.
2//!
3//! When a replay diverges from the recorded trace, this module provides
4//! structured diagnostics to help identify the root cause:
5//!
6//! - **Minimal divergent prefix**: the smallest trace prefix that reproduces the issue
7//! - **First-violation isolation**: pinpoints the exact event where divergence begins
8//! - **Affected entity analysis**: identifies tasks, regions, and timers involved
9//! - **Context window**: surrounding events for before/after comparison
10//! - **Structured output**: JSON-serializable for CI integration
11//!
12//! # Usage
13//!
14//! ```ignore
15//! use asupersync::trace::divergence::{DivergenceReport, diagnose_divergence};
16//! use asupersync::trace::replayer::DivergenceError;
17//!
18//! // After catching a divergence error during replay:
19//! let report = diagnose_divergence(&trace, &divergence_error, DiagnosticConfig::default());
20//! println!("{}", report.to_text());
21//! println!("{}", report.to_json().unwrap());
22//! ```
23
24use crate::trace::replay::{ReplayEvent, ReplayTrace};
25use crate::trace::replayer::DivergenceError;
26use serde::Serialize;
27use std::collections::BTreeSet;
28use std::fmt;
29
30// =============================================================================
31// Configuration
32// =============================================================================
33
34/// Configuration for divergence diagnostics.
35#[derive(Debug, Clone)]
36pub struct DiagnosticConfig {
37    /// Number of events to include before the divergence point.
38    pub context_before: usize,
39    /// Number of expected events to include after the divergence point.
40    pub context_after: usize,
41    /// Maximum length of the minimal prefix (0 = no limit).
42    pub max_prefix_len: usize,
43}
44
45impl Default for DiagnosticConfig {
46    fn default() -> Self {
47        Self {
48            context_before: 10,
49            context_after: 5,
50            max_prefix_len: 0,
51        }
52    }
53}
54
55// =============================================================================
56// Event Summary (compact, serializable representation)
57// =============================================================================
58
59/// A compact, human-readable summary of a replay event.
60#[derive(Debug, Clone, Serialize, PartialEq, Eq)]
61pub struct EventSummary {
62    /// Event index in the trace.
63    pub index: usize,
64    /// Event type name.
65    pub event_type: String,
66    /// Key details as human-readable string.
67    pub details: String,
68    /// Task ID involved, if any.
69    #[serde(skip_serializing_if = "Option::is_none")]
70    pub task_id: Option<u64>,
71    /// Region ID involved, if any.
72    #[serde(skip_serializing_if = "Option::is_none")]
73    pub region_id: Option<u64>,
74}
75
76impl EventSummary {
77    /// Create a summary from a replay event at a given index.
78    #[must_use]
79    pub fn from_event(index: usize, event: &ReplayEvent) -> Self {
80        let (event_type, details, task_id, region_id) = summarize_event(event);
81        Self {
82            index,
83            event_type,
84            details,
85            task_id,
86            region_id,
87        }
88    }
89}
90
91// =============================================================================
92// Affected Entities
93// =============================================================================
94
95/// Entities involved in or affected by the divergence.
96#[derive(Debug, Clone, Serialize, Default)]
97pub struct AffectedEntities {
98    /// Task IDs directly referenced at the divergence point.
99    pub tasks: Vec<u64>,
100    /// Region IDs directly referenced at the divergence point.
101    pub regions: Vec<u64>,
102    /// Timer IDs directly referenced at the divergence point.
103    pub timers: Vec<u64>,
104    /// Scheduler lane affected (if identifiable).
105    #[serde(skip_serializing_if = "Option::is_none")]
106    pub scheduler_lane: Option<String>,
107}
108
109// =============================================================================
110// Divergence Category
111// =============================================================================
112
113/// High-level category of the divergence.
114#[derive(Debug, Clone, Copy, Serialize, PartialEq, Eq)]
115pub enum DivergenceCategory {
116    /// A different task was scheduled than expected.
117    SchedulingOrder,
118    /// A task completed with a different outcome.
119    OutcomeMismatch,
120    /// Virtual time advanced differently.
121    TimeDivergence,
122    /// Timer events differ.
123    TimerMismatch,
124    /// I/O events differ.
125    IoMismatch,
126    /// RNG values differ (seed or generated value).
127    RngMismatch,
128    /// Region lifecycle events differ.
129    RegionMismatch,
130    /// Different event types entirely.
131    EventTypeMismatch,
132    /// Trace ended but execution continued (or vice versa).
133    LengthMismatch,
134    /// Waker events differ.
135    WakerMismatch,
136    /// Chaos injection events differ.
137    ChaosMismatch,
138    /// Checkpoint mismatch (state drift).
139    CheckpointMismatch,
140}
141
142impl fmt::Display for DivergenceCategory {
143    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
144        match self {
145            Self::SchedulingOrder => write!(f, "scheduling-order"),
146            Self::OutcomeMismatch => write!(f, "outcome-mismatch"),
147            Self::TimeDivergence => write!(f, "time-divergence"),
148            Self::TimerMismatch => write!(f, "timer-mismatch"),
149            Self::IoMismatch => write!(f, "io-mismatch"),
150            Self::RngMismatch => write!(f, "rng-mismatch"),
151            Self::RegionMismatch => write!(f, "region-mismatch"),
152            Self::EventTypeMismatch => write!(f, "event-type-mismatch"),
153            Self::LengthMismatch => write!(f, "length-mismatch"),
154            Self::WakerMismatch => write!(f, "waker-mismatch"),
155            Self::ChaosMismatch => write!(f, "chaos-mismatch"),
156            Self::CheckpointMismatch => write!(f, "checkpoint-mismatch"),
157        }
158    }
159}
160
161// =============================================================================
162// Divergence Report
163// =============================================================================
164
165/// Structured diagnostics report for a replay divergence.
166///
167/// Contains all information needed to understand and debug a divergence:
168/// the exact divergence point, surrounding context, affected entities,
169/// category, and actionable guidance.
170#[derive(Debug, Clone, Serialize)]
171pub struct DivergenceReport {
172    /// High-level category of the divergence.
173    pub category: DivergenceCategory,
174
175    /// Event index where divergence was detected.
176    pub divergence_index: usize,
177
178    /// Total events in the recorded trace.
179    pub trace_length: usize,
180
181    /// Percentage of trace that replayed successfully before divergence.
182    pub replay_progress_pct: f64,
183
184    /// Summary of the expected event.
185    pub expected: EventSummary,
186
187    /// Summary of the actual event.
188    pub actual: EventSummary,
189
190    /// Human-readable explanation of what went wrong.
191    pub explanation: String,
192
193    /// Actionable suggestion for debugging.
194    pub suggestion: String,
195
196    /// Context window: events immediately before the divergence.
197    pub context_before: Vec<EventSummary>,
198
199    /// Context window: expected events immediately after the divergence.
200    pub context_after: Vec<EventSummary>,
201
202    /// Entities affected by the divergence.
203    pub affected: AffectedEntities,
204
205    /// Length of the minimal divergent prefix (events 0..=divergence_index).
206    pub minimal_prefix_len: usize,
207
208    /// Seed from the trace metadata.
209    pub seed: u64,
210}
211
212impl DivergenceReport {
213    /// Serialize the report to a pretty-printed JSON string.
214    ///
215    /// # Errors
216    ///
217    /// Returns an error if serialization fails.
218    pub fn to_json(&self) -> Result<String, serde_json::Error> {
219        serde_json::to_string_pretty(self)
220    }
221
222    /// Render a human-readable text report.
223    #[must_use]
224    pub fn to_text(&self) -> String {
225        use std::fmt::Write;
226        let mut out = String::new();
227        out.push_str("=== Replay Divergence Report ===\n\n");
228
229        let _ = writeln!(out, "Category:   {}", self.category);
230        let _ = writeln!(
231            out,
232            "Event:      {} of {} ({:.1}% replayed)",
233            self.divergence_index, self.trace_length, self.replay_progress_pct
234        );
235        let _ = writeln!(out, "Seed:       0x{:016x}", self.seed);
236        let _ = writeln!(out, "Min prefix: {} events\n", self.minimal_prefix_len);
237
238        let _ = writeln!(
239            out,
240            "Expected: [{}] {}",
241            self.expected.event_type, self.expected.details
242        );
243        let _ = writeln!(
244            out,
245            "Actual:   [{}] {}\n",
246            self.actual.event_type, self.actual.details
247        );
248
249        let _ = writeln!(out, "Explanation: {}", self.explanation);
250        let _ = writeln!(out, "Suggestion:  {}\n", self.suggestion);
251
252        if !self.affected.tasks.is_empty() {
253            let _ = writeln!(out, "Affected tasks:   {:?}", self.affected.tasks);
254        }
255        if !self.affected.regions.is_empty() {
256            let _ = writeln!(out, "Affected regions: {:?}", self.affected.regions);
257        }
258        if !self.affected.timers.is_empty() {
259            let _ = writeln!(out, "Affected timers:  {:?}", self.affected.timers);
260        }
261
262        if !self.context_before.is_empty() {
263            out.push_str("\n--- Context (before) ---\n");
264            for ev in &self.context_before {
265                let _ = writeln!(out, "  [{}] {} {}", ev.index, ev.event_type, ev.details);
266            }
267        }
268
269        let _ = writeln!(out, "  [{}] >>> DIVERGENCE <<<", self.divergence_index);
270
271        if !self.context_after.is_empty() {
272            out.push_str("--- Context (expected after) ---\n");
273            for ev in &self.context_after {
274                let _ = writeln!(out, "  [{}] {} {}", ev.index, ev.event_type, ev.details);
275            }
276        }
277
278        out
279    }
280}
281
282// =============================================================================
283// Diagnosis Entry Point
284// =============================================================================
285
286/// Produce a structured [`DivergenceReport`] from a divergence error and its trace.
287///
288/// This is the main entry point for divergence diagnostics. Given the recorded
289/// trace and the error from the replayer, it analyzes the divergence and
290/// produces a rich, actionable report.
291#[must_use]
292pub fn diagnose_divergence(
293    trace: &ReplayTrace,
294    error: &DivergenceError,
295    config: &DiagnosticConfig,
296) -> DivergenceReport {
297    let idx = error.index;
298    let trace_len = trace.events.len();
299
300    // Category
301    let category = classify_divergence(error.expected.as_ref(), &error.actual);
302
303    // Summaries
304    let expected = error.expected.as_ref().map_or_else(
305        || EventSummary {
306            index: idx,
307            event_type: "TraceExhausted".to_string(),
308            details: "recorded trace ended before this event".to_string(),
309            task_id: None,
310            region_id: None,
311        },
312        |event| EventSummary::from_event(idx, event),
313    );
314    let actual = EventSummary::from_event(idx, &error.actual);
315
316    // Context windows
317    let context_before = build_context_before(&trace.events, idx, config.context_before);
318    let context_after = build_context_after(&trace.events, idx, config.context_after);
319
320    // Affected entities
321    let affected = extract_affected_entities(error.expected.as_ref(), &error.actual);
322
323    // Explanation and suggestion
324    let explanation = build_explanation(category, error.expected.as_ref(), &error.actual);
325    let suggestion = build_suggestion(category, &affected);
326
327    // Minimal prefix length
328    let minimal_prefix_len = if config.max_prefix_len > 0 {
329        (idx + 1).min(config.max_prefix_len)
330    } else {
331        idx + 1
332    };
333
334    // Progress
335    let replay_progress_pct = if trace_len == 0 {
336        0.0
337    } else {
338        let idx_f = f64::from(idx.min(u32::MAX as usize) as u32);
339        let len_f = f64::from(trace_len.min(u32::MAX as usize) as u32);
340        (idx_f / len_f) * 100.0
341    };
342
343    DivergenceReport {
344        category,
345        divergence_index: idx,
346        trace_length: trace_len,
347        replay_progress_pct,
348        expected,
349        actual,
350        explanation,
351        suggestion,
352        context_before,
353        context_after,
354        affected,
355        minimal_prefix_len,
356        seed: trace.metadata.seed,
357    }
358}
359
360/// Extract the minimal divergent prefix: the shortest sub-trace that still
361/// demonstrates the divergence.
362///
363/// Returns the prefix as a new `ReplayTrace` containing events `0..=divergence_index`.
364#[must_use]
365pub fn minimal_divergent_prefix(trace: &ReplayTrace, divergence_index: usize) -> ReplayTrace {
366    let end = (divergence_index + 1).min(trace.events.len());
367    ReplayTrace {
368        metadata: trace.metadata.clone(),
369        events: trace.events[..end].to_vec(),
370        cursor: 0,
371    }
372}
373
374// =============================================================================
375// Prefix Minimization (bd-2fywr)
376// =============================================================================
377
378/// Configuration for prefix minimization.
379#[derive(Debug, Clone)]
380pub struct MinimizationConfig {
381    /// Minimum prefix length to consider (floor for binary search).
382    ///
383    /// Defaults to 1 (the algorithm will try prefixes as short as 1 event).
384    pub min_prefix_len: usize,
385
386    /// Maximum number of oracle evaluations before stopping.
387    ///
388    /// Binary search on a prefix of length N needs at most `ceil(log2(N))`
389    /// evaluations, but this provides a hard ceiling in case the oracle is
390    /// expensive. Set to 0 for unlimited.
391    pub max_evaluations: usize,
392}
393
394impl Default for MinimizationConfig {
395    fn default() -> Self {
396        Self {
397            min_prefix_len: 1,
398            max_evaluations: 0,
399        }
400    }
401}
402
403/// Result of prefix minimization.
404#[derive(Debug)]
405pub struct MinimizationResult {
406    /// The minimized prefix as a `ReplayTrace`.
407    pub prefix: ReplayTrace,
408
409    /// Number of events in the minimized prefix.
410    pub minimized_len: usize,
411
412    /// Number of events in the original prefix.
413    pub original_len: usize,
414
415    /// Number of oracle evaluations performed.
416    pub evaluations: usize,
417
418    /// Whether the search was cut short by `max_evaluations`.
419    pub truncated: bool,
420}
421
422/// Minimize a divergent prefix using binary search.
423///
424/// Given a `ReplayTrace` whose full prefix reproduces a failure, finds the
425/// shortest sub-prefix `events[0..k]` that still reproduces. The `oracle`
426/// callback is called with candidate sub-prefixes and must return `true` if
427/// the sub-prefix reproduces the target failure.
428///
429/// # Algorithm
430///
431/// Binary search over prefix length. Assumes monotonicity: if `events[0..k]`
432/// reproduces, then `events[0..j]` for all `j >= k` also reproduces. This
433/// holds for deterministic replay with a fixed seed — once enough of the
434/// schedule is replayed to trigger the failure, adding more events cannot
435/// un-trigger it.
436///
437/// # Determinism
438///
439/// The algorithm is deterministic. Determinism of the overall process depends
440/// on the oracle callback (which should use `LabRuntime` with a fixed seed).
441///
442/// # Panics
443///
444/// Panics if the trace is empty.
445pub fn minimize_divergent_prefix<F>(
446    trace: &ReplayTrace,
447    config: &MinimizationConfig,
448    mut oracle: F,
449) -> MinimizationResult
450where
451    F: FnMut(&[ReplayEvent]) -> bool,
452{
453    let n = trace.events.len();
454    assert!(n > 0, "cannot minimize an empty trace");
455
456    let min_len = config.min_prefix_len.max(1);
457    let mut evaluations = 0u32;
458    let max_evals = if config.max_evaluations == 0 {
459        u32::MAX
460    } else {
461        config.max_evaluations as u32
462    };
463
464    // Trivial case: trace is already at or below the floor.
465    if n <= min_len {
466        return MinimizationResult {
467            prefix: trace.clone(),
468            minimized_len: n,
469            original_len: n,
470            evaluations: 0,
471            truncated: false,
472        };
473    }
474
475    // Binary search: find smallest `k` in [min_len, n] where oracle(events[0..k]) is true.
476    // We know oracle(events[0..n]) is true (the full prefix reproduces).
477    let mut left = min_len;
478    let mut right = n;
479
480    while left < right {
481        if evaluations >= max_evals {
482            // Budget exhausted — return the best known reproducing prefix.
483            return MinimizationResult {
484                prefix: slice_trace(trace, right),
485                minimized_len: right,
486                original_len: n,
487                evaluations: evaluations as usize,
488                truncated: true,
489            };
490        }
491
492        let mid = left + (right - left) / 2;
493        evaluations += 1;
494
495        if oracle(&trace.events[..mid]) {
496            right = mid;
497        } else {
498            left = mid + 1;
499        }
500    }
501
502    MinimizationResult {
503        prefix: slice_trace(trace, left),
504        minimized_len: left,
505        original_len: n,
506        evaluations: evaluations as usize,
507        truncated: false,
508    }
509}
510
511/// Build a `ReplayTrace` from the first `len` events of `source`.
512fn slice_trace(source: &ReplayTrace, len: usize) -> ReplayTrace {
513    ReplayTrace {
514        metadata: source.metadata.clone(),
515        events: source.events[..len].to_vec(),
516        cursor: 0,
517    }
518}
519
520// =============================================================================
521// Classification
522// =============================================================================
523
524/// Classify a divergence by comparing expected and actual events.
525fn classify_divergence(expected: Option<&ReplayEvent>, actual: &ReplayEvent) -> DivergenceCategory {
526    use std::mem::discriminant;
527
528    let Some(expected) = expected else {
529        return DivergenceCategory::LengthMismatch;
530    };
531
532    if discriminant(expected) != discriminant(actual) {
533        return DivergenceCategory::EventTypeMismatch;
534    }
535
536    match (expected, actual) {
537        (ReplayEvent::TaskScheduled { .. }, ReplayEvent::TaskScheduled { .. }) => {
538            DivergenceCategory::SchedulingOrder
539        }
540        (ReplayEvent::TaskCompleted { .. }, ReplayEvent::TaskCompleted { .. }) => {
541            DivergenceCategory::OutcomeMismatch
542        }
543        (ReplayEvent::TimeAdvanced { .. }, ReplayEvent::TimeAdvanced { .. }) => {
544            DivergenceCategory::TimeDivergence
545        }
546        (ReplayEvent::TimerCreated { .. }, ReplayEvent::TimerCreated { .. })
547        | (ReplayEvent::TimerFired { .. }, ReplayEvent::TimerFired { .. })
548        | (ReplayEvent::TimerCancelled { .. }, ReplayEvent::TimerCancelled { .. }) => {
549            DivergenceCategory::TimerMismatch
550        }
551        (ReplayEvent::IoReady { .. }, ReplayEvent::IoReady { .. })
552        | (ReplayEvent::IoResult { .. }, ReplayEvent::IoResult { .. })
553        | (ReplayEvent::IoError { .. }, ReplayEvent::IoError { .. }) => {
554            DivergenceCategory::IoMismatch
555        }
556        (ReplayEvent::RngSeed { .. }, ReplayEvent::RngSeed { .. })
557        | (ReplayEvent::RngValue { .. }, ReplayEvent::RngValue { .. }) => {
558            DivergenceCategory::RngMismatch
559        }
560        (ReplayEvent::RegionCreated { .. }, ReplayEvent::RegionCreated { .. })
561        | (ReplayEvent::RegionClosed { .. }, ReplayEvent::RegionClosed { .. })
562        | (ReplayEvent::RegionCancelled { .. }, ReplayEvent::RegionCancelled { .. }) => {
563            DivergenceCategory::RegionMismatch
564        }
565        (ReplayEvent::WakerWake { .. }, ReplayEvent::WakerWake { .. })
566        | (ReplayEvent::WakerBatchWake { .. }, ReplayEvent::WakerBatchWake { .. }) => {
567            DivergenceCategory::WakerMismatch
568        }
569        (ReplayEvent::ChaosInjection { .. }, ReplayEvent::ChaosInjection { .. }) => {
570            DivergenceCategory::ChaosMismatch
571        }
572        (ReplayEvent::Checkpoint { .. }, ReplayEvent::Checkpoint { .. }) => {
573            DivergenceCategory::CheckpointMismatch
574        }
575        _ => DivergenceCategory::EventTypeMismatch,
576    }
577}
578
579// =============================================================================
580// Context Windows
581// =============================================================================
582
583fn build_context_before(events: &[ReplayEvent], idx: usize, count: usize) -> Vec<EventSummary> {
584    let clamped_idx = idx.min(events.len());
585    let start = clamped_idx.saturating_sub(count);
586    events[start..clamped_idx]
587        .iter()
588        .enumerate()
589        .map(|(i, ev)| EventSummary::from_event(start + i, ev))
590        .collect()
591}
592
593fn build_context_after(events: &[ReplayEvent], idx: usize, count: usize) -> Vec<EventSummary> {
594    let after_start = idx + 1;
595    if after_start >= events.len() {
596        return Vec::new();
597    }
598    let end = (after_start + count).min(events.len());
599    events[after_start..end]
600        .iter()
601        .enumerate()
602        .map(|(i, ev)| EventSummary::from_event(after_start + i, ev))
603        .collect()
604}
605
606// =============================================================================
607// Entity Extraction
608// =============================================================================
609
610fn extract_affected_entities(
611    expected: Option<&ReplayEvent>,
612    actual: &ReplayEvent,
613) -> AffectedEntities {
614    let mut tasks = BTreeSet::new();
615    let mut regions = BTreeSet::new();
616    let mut timers = BTreeSet::new();
617    let mut lane = None;
618
619    if let Some(expected_event) = expected {
620        collect_event_entities(expected_event, &mut tasks, &mut regions, &mut timers);
621    }
622    collect_event_entities(actual, &mut tasks, &mut regions, &mut timers);
623
624    // Determine scheduler lane from scheduling events
625    if let Some(ReplayEvent::TaskScheduled { task: e, .. }) = expected
626        && let ReplayEvent::TaskScheduled { task: a, .. } = actual
627        && e != a
628    {
629        lane = Some(format!("ready (expected task {e:?}, got {a:?})"));
630    }
631
632    AffectedEntities {
633        tasks: tasks.into_iter().collect(),
634        regions: regions.into_iter().collect(),
635        timers: timers.into_iter().collect(),
636        scheduler_lane: lane,
637    }
638}
639
640fn collect_event_entities(
641    event: &ReplayEvent,
642    tasks: &mut BTreeSet<u64>,
643    regions: &mut BTreeSet<u64>,
644    timers: &mut BTreeSet<u64>,
645) {
646    match event {
647        ReplayEvent::TaskScheduled { task, .. }
648        | ReplayEvent::TaskYielded { task }
649        | ReplayEvent::TaskCompleted { task, .. }
650        | ReplayEvent::WakerWake { task } => {
651            tasks.insert(task.0);
652        }
653        ReplayEvent::TaskSpawned { task, region, .. } => {
654            tasks.insert(task.0);
655            regions.insert(region.0);
656        }
657        ReplayEvent::TimerCreated { timer_id, .. }
658        | ReplayEvent::TimerFired { timer_id }
659        | ReplayEvent::TimerCancelled { timer_id } => {
660            timers.insert(*timer_id);
661        }
662        ReplayEvent::RegionCreated { region, parent, .. } => {
663            regions.insert(region.0);
664            if let Some(p) = parent {
665                regions.insert(p.0);
666            }
667        }
668        ReplayEvent::RegionClosed { region, .. } | ReplayEvent::RegionCancelled { region, .. } => {
669            regions.insert(region.0);
670        }
671        ReplayEvent::ChaosInjection { task, .. } => {
672            if let Some(t) = task {
673                tasks.insert(t.0);
674            }
675        }
676        ReplayEvent::IoReady { .. }
677        | ReplayEvent::IoResult { .. }
678        | ReplayEvent::IoError { .. }
679        | ReplayEvent::RngSeed { .. }
680        | ReplayEvent::RngValue { .. }
681        | ReplayEvent::TimeAdvanced { .. }
682        | ReplayEvent::WakerBatchWake { .. }
683        | ReplayEvent::Checkpoint { .. } => {}
684    }
685}
686
687// =============================================================================
688// Explanations and Suggestions
689// =============================================================================
690
691#[allow(clippy::too_many_lines)]
692fn build_explanation(
693    category: DivergenceCategory,
694    expected: Option<&ReplayEvent>,
695    actual: &ReplayEvent,
696) -> String {
697    if expected.is_none() {
698        return "Recorded trace is exhausted but execution continued. This indicates extra runtime activity beyond the captured trace boundary.".to_string();
699    }
700
701    let expected = expected.expect("checked above");
702
703    match category {
704        DivergenceCategory::SchedulingOrder => {
705            if let (
706                ReplayEvent::TaskScheduled {
707                    task: e,
708                    at_tick: et,
709                    ..
710                },
711                ReplayEvent::TaskScheduled {
712                    task: a,
713                    at_tick: at,
714                    ..
715                },
716            ) = (expected, actual)
717            {
718                if e == a {
719                    format!(
720                        "Task {e:?} was scheduled at tick {at} instead of expected tick {et}. \
721                         The scheduler made the same choice but at a different time."
722                    )
723                } else {
724                    format!(
725                        "Scheduler chose task {a:?} at tick {at} instead of expected task {e:?} at tick {et}. \
726                         The ready queue ordering diverged."
727                    )
728                }
729            } else {
730                "Scheduling order diverged from recorded trace.".to_string()
731            }
732        }
733        DivergenceCategory::OutcomeMismatch => {
734            if let (
735                ReplayEvent::TaskCompleted {
736                    task: e,
737                    outcome: eo,
738                },
739                ReplayEvent::TaskCompleted {
740                    task: a,
741                    outcome: ao,
742                },
743            ) = (expected, actual)
744            {
745                let outcome_name = |o: u8| match o {
746                    0 => "Ok",
747                    1 => "Err",
748                    2 => "Cancelled",
749                    3 => "Panicked",
750                    _ => "Unknown",
751                };
752                if e == a {
753                    format!(
754                        "Task {:?} completed with {} (expected {}). \
755                         The task's internal logic took a different path.",
756                        e,
757                        outcome_name(*ao),
758                        outcome_name(*eo)
759                    )
760                } else {
761                    format!(
762                        "Different task completed: got {:?} ({}) instead of {:?} ({}).",
763                        a,
764                        outcome_name(*ao),
765                        e,
766                        outcome_name(*eo)
767                    )
768                }
769            } else {
770                "Task completion outcome diverged.".to_string()
771            }
772        }
773        DivergenceCategory::TimeDivergence => {
774            "Virtual time advanced to a different value. This usually indicates \
775             a timer or sleep duration changed between record and replay."
776                .to_string()
777        }
778        DivergenceCategory::TimerMismatch => {
779            "Timer event (create/fire/cancel) diverged. Check if timer registration \
780             order or deadlines changed."
781                .to_string()
782        }
783        DivergenceCategory::IoMismatch => {
784            "I/O event diverged. The simulated I/O layer returned different results. \
785             This may indicate a Lab reactor configuration change."
786                .to_string()
787        }
788        DivergenceCategory::RngMismatch => {
789            "RNG seed or value mismatch. The deterministic RNG produced different output. \
790             Verify the seed is identical and no additional RNG calls were inserted."
791                .to_string()
792        }
793        DivergenceCategory::RegionMismatch => {
794            "Region lifecycle event diverged. A region was created, closed, or cancelled \
795             differently than recorded."
796                .to_string()
797        }
798        DivergenceCategory::EventTypeMismatch => {
799            format!(
800                "Completely different event types: expected {} but got {}. \
801                 The execution path diverged significantly.",
802                event_type_name(expected),
803                event_type_name(actual)
804            )
805        }
806        DivergenceCategory::LengthMismatch => {
807            "Trace ended but execution continued (or vice versa).".to_string()
808        }
809        DivergenceCategory::WakerMismatch => {
810            "Waker event diverged. A different task was woken or batch count differs.".to_string()
811        }
812        DivergenceCategory::ChaosMismatch => {
813            "Chaos injection event diverged. The fault injection decisions differ.".to_string()
814        }
815        DivergenceCategory::CheckpointMismatch => {
816            "Checkpoint state mismatch. The runtime state at a synchronization point \
817             differs from the recording, indicating accumulated drift."
818                .to_string()
819        }
820    }
821}
822
823fn build_suggestion(category: DivergenceCategory, affected: &AffectedEntities) -> String {
824    let mut suggestion = match category {
825        DivergenceCategory::SchedulingOrder => {
826            "Check for non-deterministic task readiness (e.g., I/O completion order, \
827             timer resolution). Use a fixed seed and verify the scheduler configuration \
828             matches the recording."
829                .to_string()
830        }
831        DivergenceCategory::OutcomeMismatch => {
832            "The task produced a different result. Check for external state dependencies, \
833             non-deterministic error paths, or changed business logic."
834                .to_string()
835        }
836        DivergenceCategory::TimeDivergence => {
837            "Verify the Lab runtime clock configuration matches. Check for changed \
838             sleep/timeout durations in the code under test."
839                .to_string()
840        }
841        DivergenceCategory::RngMismatch => {
842            "Ensure the same seed is used. If new RNG calls were added between record \
843             and replay, the sequence will shift. Use derive_entropy_seed() for \
844             subsystem-specific RNG isolation."
845                .to_string()
846        }
847        DivergenceCategory::EventTypeMismatch => {
848            "The execution diverged so significantly that a completely different event \
849             was produced. Look for code changes that alter the control flow, such as \
850             added/removed spawns, new I/O operations, or changed cancellation paths."
851                .to_string()
852        }
853        DivergenceCategory::CheckpointMismatch => {
854            "State accumulated drift before this checkpoint. Examine the events between \
855             the previous checkpoint and this one for subtle differences."
856                .to_string()
857        }
858        _ => "Compare the expected and actual events above. Check for code changes, \
859             configuration differences, or non-deterministic external dependencies."
860            .to_string(),
861    };
862
863    if !affected.tasks.is_empty() {
864        use std::fmt::Write;
865        let _ = write!(suggestion, " Focus on task(s): {:?}.", affected.tasks);
866    }
867
868    suggestion
869}
870
871// =============================================================================
872// Event Summarization
873// =============================================================================
874
875/// Returns (event_type, details, optional_task_id, optional_region_id).
876#[allow(clippy::too_many_lines)]
877fn summarize_event(event: &ReplayEvent) -> (String, String, Option<u64>, Option<u64>) {
878    match event {
879        ReplayEvent::TaskScheduled { task, at_tick } => (
880            "TaskScheduled".into(),
881            format!("task={task:?} tick={at_tick}"),
882            Some(task.0),
883            None,
884        ),
885        ReplayEvent::TaskYielded { task } => (
886            "TaskYielded".into(),
887            format!("task={task:?}"),
888            Some(task.0),
889            None,
890        ),
891        ReplayEvent::TaskCompleted { task, outcome } => {
892            let outcome_str = match outcome {
893                0 => "Ok",
894                1 => "Err",
895                2 => "Cancelled",
896                3 => "Panicked",
897                _ => "Unknown",
898            };
899            (
900                "TaskCompleted".into(),
901                format!("task={task:?} outcome={outcome_str}"),
902                Some(task.0),
903                None,
904            )
905        }
906        ReplayEvent::TaskSpawned {
907            task,
908            region,
909            at_tick,
910        } => (
911            "TaskSpawned".into(),
912            format!("task={task:?} region={region:?} tick={at_tick}"),
913            Some(task.0),
914            Some(region.0),
915        ),
916        ReplayEvent::TimeAdvanced {
917            from_nanos,
918            to_nanos,
919        } => (
920            "TimeAdvanced".into(),
921            format!("{from_nanos}ns -> {to_nanos}ns"),
922            None,
923            None,
924        ),
925        ReplayEvent::TimerCreated {
926            timer_id,
927            deadline_nanos,
928        } => (
929            "TimerCreated".into(),
930            format!("timer={timer_id} deadline={deadline_nanos}ns"),
931            None,
932            None,
933        ),
934        ReplayEvent::TimerFired { timer_id } => {
935            ("TimerFired".into(), format!("timer={timer_id}"), None, None)
936        }
937        ReplayEvent::TimerCancelled { timer_id } => (
938            "TimerCancelled".into(),
939            format!("timer={timer_id}"),
940            None,
941            None,
942        ),
943        ReplayEvent::IoReady { token, readiness } => (
944            "IoReady".into(),
945            format!("token={token} readiness=0x{readiness:02x}"),
946            None,
947            None,
948        ),
949        ReplayEvent::IoResult { token, bytes } => (
950            "IoResult".into(),
951            format!("token={token} bytes={bytes}"),
952            None,
953            None,
954        ),
955        ReplayEvent::IoError { token, kind } => (
956            "IoError".into(),
957            format!("token={token} kind={kind}"),
958            None,
959            None,
960        ),
961        ReplayEvent::RngSeed { seed } => ("RngSeed".into(), format!("0x{seed:016x}"), None, None),
962        ReplayEvent::RngValue { value } => {
963            ("RngValue".into(), format!("0x{value:016x}"), None, None)
964        }
965        ReplayEvent::ChaosInjection { kind, task, data } => {
966            let kind_str = match kind {
967                0 => "cancel",
968                1 => "delay",
969                2 => "io_error",
970                3 => "wakeup_storm",
971                4 => "budget",
972                _ => "unknown",
973            };
974            (
975                "ChaosInjection".into(),
976                format!("kind={kind_str} task={task:?} data={data}"),
977                task.map(|t| t.0),
978                None,
979            )
980        }
981        ReplayEvent::RegionCreated {
982            region,
983            parent,
984            at_tick,
985        } => (
986            "RegionCreated".into(),
987            format!("region={region:?} parent={parent:?} tick={at_tick}"),
988            None,
989            Some(region.0),
990        ),
991        ReplayEvent::RegionClosed { region, outcome } => {
992            let outcome_str = match outcome {
993                0 => "Ok",
994                1 => "Err",
995                2 => "Cancelled",
996                3 => "Panicked",
997                _ => "Unknown",
998            };
999            (
1000                "RegionClosed".into(),
1001                format!("region={region:?} outcome={outcome_str}"),
1002                None,
1003                Some(region.0),
1004            )
1005        }
1006        ReplayEvent::RegionCancelled {
1007            region,
1008            cancel_kind,
1009        } => (
1010            "RegionCancelled".into(),
1011            format!("region={region:?} cancel_kind={cancel_kind}"),
1012            None,
1013            Some(region.0),
1014        ),
1015        ReplayEvent::WakerWake { task } => (
1016            "WakerWake".into(),
1017            format!("task={task:?}"),
1018            Some(task.0),
1019            None,
1020        ),
1021        ReplayEvent::WakerBatchWake { count } => (
1022            "WakerBatchWake".into(),
1023            format!("count={count}"),
1024            None,
1025            None,
1026        ),
1027        ReplayEvent::Checkpoint {
1028            sequence,
1029            time_nanos,
1030            active_tasks,
1031            active_regions,
1032        } => (
1033            "Checkpoint".into(),
1034            format!(
1035                "seq={sequence} time={time_nanos}ns tasks={active_tasks} regions={active_regions}"
1036            ),
1037            None,
1038            None,
1039        ),
1040    }
1041}
1042
1043fn event_type_name(event: &ReplayEvent) -> &'static str {
1044    match event {
1045        ReplayEvent::TaskScheduled { .. } => "TaskScheduled",
1046        ReplayEvent::TaskYielded { .. } => "TaskYielded",
1047        ReplayEvent::TaskCompleted { .. } => "TaskCompleted",
1048        ReplayEvent::TaskSpawned { .. } => "TaskSpawned",
1049        ReplayEvent::TimeAdvanced { .. } => "TimeAdvanced",
1050        ReplayEvent::TimerCreated { .. } => "TimerCreated",
1051        ReplayEvent::TimerFired { .. } => "TimerFired",
1052        ReplayEvent::TimerCancelled { .. } => "TimerCancelled",
1053        ReplayEvent::IoReady { .. } => "IoReady",
1054        ReplayEvent::IoResult { .. } => "IoResult",
1055        ReplayEvent::IoError { .. } => "IoError",
1056        ReplayEvent::RngSeed { .. } => "RngSeed",
1057        ReplayEvent::RngValue { .. } => "RngValue",
1058        ReplayEvent::ChaosInjection { .. } => "ChaosInjection",
1059        ReplayEvent::RegionCreated { .. } => "RegionCreated",
1060        ReplayEvent::RegionClosed { .. } => "RegionClosed",
1061        ReplayEvent::RegionCancelled { .. } => "RegionCancelled",
1062        ReplayEvent::WakerWake { .. } => "WakerWake",
1063        ReplayEvent::WakerBatchWake { .. } => "WakerBatchWake",
1064        ReplayEvent::Checkpoint { .. } => "Checkpoint",
1065    }
1066}
1067
1068// =============================================================================
1069// Tests
1070// =============================================================================
1071
1072#[cfg(test)]
1073mod tests {
1074    use super::*;
1075    use crate::trace::replay::TraceMetadata;
1076    use crate::trace::{CompactRegionId, CompactTaskId};
1077
1078    fn make_trace(seed: u64, events: Vec<ReplayEvent>) -> ReplayTrace {
1079        ReplayTrace {
1080            metadata: TraceMetadata::new(seed),
1081            events,
1082            cursor: 0,
1083        }
1084    }
1085
1086    fn make_error(index: usize, expected: ReplayEvent, actual: ReplayEvent) -> DivergenceError {
1087        DivergenceError {
1088            index,
1089            expected: Some(expected),
1090            actual,
1091            context: String::new(),
1092        }
1093    }
1094
1095    fn scrub_divergence_text(text: &str) -> String {
1096        text.replace("Seed:       0x000000000000beef", "Seed:       [SEED]")
1097    }
1098
1099    // -------------------------------------------------------------------------
1100    // Classification tests
1101    // -------------------------------------------------------------------------
1102
1103    #[test]
1104    fn classify_scheduling_order() {
1105        let cat = classify_divergence(
1106            Some(&ReplayEvent::TaskScheduled {
1107                task: CompactTaskId(1),
1108                at_tick: 0,
1109            }),
1110            &ReplayEvent::TaskScheduled {
1111                task: CompactTaskId(2),
1112                at_tick: 0,
1113            },
1114        );
1115        assert_eq!(cat, DivergenceCategory::SchedulingOrder);
1116    }
1117
1118    #[test]
1119    fn classify_outcome_mismatch() {
1120        let cat = classify_divergence(
1121            Some(&ReplayEvent::TaskCompleted {
1122                task: CompactTaskId(1),
1123                outcome: 0,
1124            }),
1125            &ReplayEvent::TaskCompleted {
1126                task: CompactTaskId(1),
1127                outcome: 2,
1128            },
1129        );
1130        assert_eq!(cat, DivergenceCategory::OutcomeMismatch);
1131    }
1132
1133    #[test]
1134    fn classify_event_type_mismatch() {
1135        let cat = classify_divergence(
1136            Some(&ReplayEvent::RngSeed { seed: 42 }),
1137            &ReplayEvent::TaskScheduled {
1138                task: CompactTaskId(1),
1139                at_tick: 0,
1140            },
1141        );
1142        assert_eq!(cat, DivergenceCategory::EventTypeMismatch);
1143    }
1144
1145    #[test]
1146    fn classify_time_divergence() {
1147        let cat = classify_divergence(
1148            Some(&ReplayEvent::TimeAdvanced {
1149                from_nanos: 0,
1150                to_nanos: 1000,
1151            }),
1152            &ReplayEvent::TimeAdvanced {
1153                from_nanos: 0,
1154                to_nanos: 2000,
1155            },
1156        );
1157        assert_eq!(cat, DivergenceCategory::TimeDivergence);
1158    }
1159
1160    #[test]
1161    fn classify_rng_mismatch() {
1162        let cat = classify_divergence(
1163            Some(&ReplayEvent::RngSeed { seed: 42 }),
1164            &ReplayEvent::RngSeed { seed: 99 },
1165        );
1166        assert_eq!(cat, DivergenceCategory::RngMismatch);
1167    }
1168
1169    #[test]
1170    fn classify_checkpoint_mismatch() {
1171        let cat = classify_divergence(
1172            Some(&ReplayEvent::Checkpoint {
1173                sequence: 1,
1174                time_nanos: 100,
1175                active_tasks: 3,
1176                active_regions: 1,
1177            }),
1178            &ReplayEvent::Checkpoint {
1179                sequence: 1,
1180                time_nanos: 100,
1181                active_tasks: 5,
1182                active_regions: 1,
1183            },
1184        );
1185        assert_eq!(cat, DivergenceCategory::CheckpointMismatch);
1186    }
1187
1188    // -------------------------------------------------------------------------
1189    // Full report tests
1190    // -------------------------------------------------------------------------
1191
1192    #[test]
1193    fn diagnose_scheduling_divergence() {
1194        let events = vec![
1195            ReplayEvent::RngSeed { seed: 42 },
1196            ReplayEvent::TaskSpawned {
1197                task: CompactTaskId(1),
1198                region: CompactRegionId(100),
1199                at_tick: 0,
1200            },
1201            ReplayEvent::TaskSpawned {
1202                task: CompactTaskId(2),
1203                region: CompactRegionId(100),
1204                at_tick: 0,
1205            },
1206            ReplayEvent::TaskScheduled {
1207                task: CompactTaskId(1),
1208                at_tick: 1,
1209            },
1210            ReplayEvent::TaskScheduled {
1211                task: CompactTaskId(2),
1212                at_tick: 2,
1213            },
1214        ];
1215        let trace = make_trace(0xDEAD, events);
1216
1217        let error = make_error(
1218            3,
1219            ReplayEvent::TaskScheduled {
1220                task: CompactTaskId(1),
1221                at_tick: 1,
1222            },
1223            ReplayEvent::TaskScheduled {
1224                task: CompactTaskId(2),
1225                at_tick: 1,
1226            },
1227        );
1228
1229        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1230
1231        assert_eq!(report.category, DivergenceCategory::SchedulingOrder);
1232        assert_eq!(report.divergence_index, 3);
1233        assert_eq!(report.trace_length, 5);
1234        assert_eq!(report.minimal_prefix_len, 4);
1235        assert_eq!(report.seed, 0xDEAD);
1236        assert!(report.replay_progress_pct > 50.0);
1237        assert!(report.affected.tasks.contains(&1));
1238        assert!(report.affected.tasks.contains(&2));
1239        assert!(report.explanation.contains("Scheduler chose"));
1240        assert!(!report.context_before.is_empty());
1241    }
1242
1243    #[test]
1244    fn diagnose_outcome_divergence() {
1245        let events = vec![
1246            ReplayEvent::TaskScheduled {
1247                task: CompactTaskId(1),
1248                at_tick: 0,
1249            },
1250            ReplayEvent::TaskCompleted {
1251                task: CompactTaskId(1),
1252                outcome: 0,
1253            },
1254        ];
1255        let trace = make_trace(42, events);
1256
1257        let error = make_error(
1258            1,
1259            ReplayEvent::TaskCompleted {
1260                task: CompactTaskId(1),
1261                outcome: 0,
1262            },
1263            ReplayEvent::TaskCompleted {
1264                task: CompactTaskId(1),
1265                outcome: 3,
1266            },
1267        );
1268
1269        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1270
1271        assert_eq!(report.category, DivergenceCategory::OutcomeMismatch);
1272        assert!(report.explanation.contains("Panicked"));
1273        assert!(report.explanation.contains("Ok"));
1274    }
1275
1276    #[test]
1277    fn diagnose_event_type_mismatch() {
1278        let events = vec![
1279            ReplayEvent::RngSeed { seed: 42 },
1280            ReplayEvent::TaskScheduled {
1281                task: CompactTaskId(1),
1282                at_tick: 0,
1283            },
1284        ];
1285        let trace = make_trace(42, events);
1286
1287        let error = make_error(
1288            1,
1289            ReplayEvent::TaskScheduled {
1290                task: CompactTaskId(1),
1291                at_tick: 0,
1292            },
1293            ReplayEvent::TimerFired { timer_id: 99 },
1294        );
1295
1296        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1297
1298        assert_eq!(report.category, DivergenceCategory::EventTypeMismatch);
1299        assert!(report.explanation.contains("TaskScheduled"));
1300        assert!(report.explanation.contains("TimerFired"));
1301    }
1302
1303    #[test]
1304    fn diagnose_trace_exhausted_divergence() {
1305        let events = vec![ReplayEvent::RngSeed { seed: 42 }];
1306        let trace = make_trace(0xCAFE, events);
1307        let error = DivergenceError {
1308            index: 1,
1309            expected: None,
1310            actual: ReplayEvent::RngSeed { seed: 99 },
1311            context: "Trace ended but execution continued".to_string(),
1312        };
1313
1314        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1315
1316        assert_eq!(report.category, DivergenceCategory::LengthMismatch);
1317        assert_eq!(report.expected.event_type, "TraceExhausted");
1318        assert!(
1319            report
1320                .expected
1321                .details
1322                .contains("recorded trace ended before this event")
1323        );
1324        assert!(report.explanation.contains("trace is exhausted"));
1325        assert_eq!(report.actual.event_type, "RngSeed");
1326    }
1327
1328    // -------------------------------------------------------------------------
1329    // Context window tests
1330    // -------------------------------------------------------------------------
1331
1332    #[test]
1333    fn context_window_bounds() {
1334        let events: Vec<_> = (0..20)
1335            .map(|i| ReplayEvent::RngValue { value: i })
1336            .collect();
1337        let trace = make_trace(42, events);
1338
1339        let error = make_error(
1340            10,
1341            ReplayEvent::RngValue { value: 10 },
1342            ReplayEvent::RngValue { value: 99 },
1343        );
1344
1345        let config = DiagnosticConfig {
1346            context_before: 3,
1347            context_after: 2,
1348            ..DiagnosticConfig::default()
1349        };
1350
1351        let report = diagnose_divergence(&trace, &error, &config);
1352
1353        assert_eq!(report.context_before.len(), 3);
1354        assert_eq!(report.context_after.len(), 2);
1355        assert_eq!(report.context_before[0].index, 7);
1356        assert_eq!(report.context_before[2].index, 9);
1357        assert_eq!(report.context_after[0].index, 11);
1358    }
1359
1360    #[test]
1361    fn context_window_at_start() {
1362        let events = vec![
1363            ReplayEvent::RngSeed { seed: 42 },
1364            ReplayEvent::RngSeed { seed: 43 },
1365        ];
1366        let trace = make_trace(42, events);
1367
1368        let error = make_error(
1369            0,
1370            ReplayEvent::RngSeed { seed: 42 },
1371            ReplayEvent::RngSeed { seed: 99 },
1372        );
1373
1374        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1375
1376        assert!(report.context_before.is_empty());
1377        assert_eq!(report.context_after.len(), 1);
1378    }
1379
1380    #[test]
1381    fn context_window_at_end() {
1382        let events = vec![
1383            ReplayEvent::RngSeed { seed: 42 },
1384            ReplayEvent::RngSeed { seed: 43 },
1385        ];
1386        let trace = make_trace(42, events);
1387
1388        let error = make_error(
1389            1,
1390            ReplayEvent::RngSeed { seed: 43 },
1391            ReplayEvent::RngSeed { seed: 99 },
1392        );
1393
1394        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1395
1396        assert_eq!(report.context_before.len(), 1);
1397        assert!(report.context_after.is_empty());
1398    }
1399
1400    // -------------------------------------------------------------------------
1401    // Minimal prefix tests
1402    // -------------------------------------------------------------------------
1403
1404    #[test]
1405    fn minimal_prefix_extraction() {
1406        let events: Vec<_> = (0..10)
1407            .map(|i| ReplayEvent::RngValue { value: i })
1408            .collect();
1409        let trace = make_trace(42, events);
1410
1411        let prefix = minimal_divergent_prefix(&trace, 5);
1412        assert_eq!(prefix.events.len(), 6); // 0..=5
1413        assert_eq!(prefix.metadata.seed, 42);
1414    }
1415
1416    #[test]
1417    fn minimal_prefix_at_zero() {
1418        let events = vec![ReplayEvent::RngSeed { seed: 42 }];
1419        let trace = make_trace(42, events);
1420
1421        let prefix = minimal_divergent_prefix(&trace, 0);
1422        assert_eq!(prefix.events.len(), 1);
1423    }
1424
1425    #[test]
1426    fn minimal_prefix_beyond_trace() {
1427        let events = vec![ReplayEvent::RngSeed { seed: 42 }];
1428        let trace = make_trace(42, events);
1429
1430        let prefix = minimal_divergent_prefix(&trace, 100);
1431        assert_eq!(prefix.events.len(), 1); // clamped to trace length
1432    }
1433
1434    // -------------------------------------------------------------------------
1435    // Serialization tests
1436    // -------------------------------------------------------------------------
1437
1438    #[test]
1439    fn report_serializes_to_json() {
1440        let events = vec![
1441            ReplayEvent::RngSeed { seed: 42 },
1442            ReplayEvent::TaskScheduled {
1443                task: CompactTaskId(1),
1444                at_tick: 0,
1445            },
1446        ];
1447        let trace = make_trace(42, events);
1448
1449        let error = make_error(
1450            1,
1451            ReplayEvent::TaskScheduled {
1452                task: CompactTaskId(1),
1453                at_tick: 0,
1454            },
1455            ReplayEvent::TaskScheduled {
1456                task: CompactTaskId(2),
1457                at_tick: 0,
1458            },
1459        );
1460
1461        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1462        let json = report.to_json().expect("serialize");
1463
1464        // Verify JSON is valid and contains key fields
1465        let parsed: serde_json::Value = serde_json::from_str(&json).expect("parse");
1466        assert_eq!(parsed["category"], "SchedulingOrder");
1467        assert_eq!(parsed["divergence_index"], 1);
1468        assert_eq!(parsed["seed"], 42);
1469    }
1470
1471    #[test]
1472    fn report_renders_text() {
1473        let events = vec![ReplayEvent::TaskScheduled {
1474            task: CompactTaskId(1),
1475            at_tick: 0,
1476        }];
1477        let trace = make_trace(0xBEEF, events);
1478
1479        let error = make_error(
1480            0,
1481            ReplayEvent::TaskScheduled {
1482                task: CompactTaskId(1),
1483                at_tick: 0,
1484            },
1485            ReplayEvent::TaskScheduled {
1486                task: CompactTaskId(2),
1487                at_tick: 0,
1488            },
1489        );
1490
1491        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1492        let text = report.to_text();
1493
1494        assert!(text.contains("Replay Divergence Report"));
1495        assert!(text.contains("scheduling-order"));
1496        assert!(text.contains("0x000000000000beef"));
1497        assert!(text.contains("DIVERGENCE"));
1498    }
1499
1500    // -------------------------------------------------------------------------
1501    // Entity extraction tests
1502    // -------------------------------------------------------------------------
1503
1504    #[test]
1505    fn extract_task_entities() {
1506        let affected = extract_affected_entities(
1507            Some(&ReplayEvent::TaskScheduled {
1508                task: CompactTaskId(1),
1509                at_tick: 0,
1510            }),
1511            &ReplayEvent::TaskScheduled {
1512                task: CompactTaskId(2),
1513                at_tick: 0,
1514            },
1515        );
1516
1517        assert_eq!(affected.tasks, vec![1, 2]);
1518        assert!(affected.regions.is_empty());
1519        assert!(affected.scheduler_lane.is_some());
1520    }
1521
1522    #[test]
1523    fn extract_region_entities() {
1524        let affected = extract_affected_entities(
1525            Some(&ReplayEvent::RegionCreated {
1526                region: CompactRegionId(10),
1527                parent: Some(CompactRegionId(5)),
1528                at_tick: 0,
1529            }),
1530            &ReplayEvent::RegionCreated {
1531                region: CompactRegionId(10),
1532                parent: None,
1533                at_tick: 0,
1534            },
1535        );
1536
1537        assert!(affected.tasks.is_empty());
1538        assert!(affected.regions.contains(&10));
1539        assert!(affected.regions.contains(&5));
1540    }
1541
1542    #[test]
1543    fn extract_timer_entities() {
1544        let affected = extract_affected_entities(
1545            Some(&ReplayEvent::TimerFired { timer_id: 42 }),
1546            &ReplayEvent::TimerFired { timer_id: 99 },
1547        );
1548
1549        assert!(affected.tasks.is_empty());
1550        assert_eq!(affected.timers, vec![42, 99]);
1551    }
1552
1553    // -------------------------------------------------------------------------
1554    // Event summary tests
1555    // -------------------------------------------------------------------------
1556
1557    #[test]
1558    fn event_summary_from_task_scheduled() {
1559        let summary = EventSummary::from_event(
1560            5,
1561            &ReplayEvent::TaskScheduled {
1562                task: CompactTaskId(42),
1563                at_tick: 10,
1564            },
1565        );
1566
1567        assert_eq!(summary.index, 5);
1568        assert_eq!(summary.event_type, "TaskScheduled");
1569        assert!(summary.details.contains("tick=10"));
1570        assert_eq!(summary.task_id, Some(42));
1571        assert_eq!(summary.region_id, None);
1572    }
1573
1574    #[test]
1575    fn event_summary_from_region_created() {
1576        let summary = EventSummary::from_event(
1577            0,
1578            &ReplayEvent::RegionCreated {
1579                region: CompactRegionId(7),
1580                parent: None,
1581                at_tick: 0,
1582            },
1583        );
1584
1585        assert_eq!(summary.event_type, "RegionCreated");
1586        assert_eq!(summary.region_id, Some(7));
1587        assert_eq!(summary.task_id, None);
1588    }
1589
1590    // -------------------------------------------------------------------------
1591    // Prefix minimization tests (bd-2fywr)
1592    // -------------------------------------------------------------------------
1593
1594    #[test]
1595    fn minimize_finds_exact_threshold() {
1596        // 10 events. Failure reproduces when prefix length >= 6.
1597        let events: Vec<_> = (0..10)
1598            .map(|i| ReplayEvent::RngValue { value: i })
1599            .collect();
1600        let trace = make_trace(42, events);
1601
1602        let threshold = 6;
1603        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1604            prefix.len() >= threshold
1605        });
1606
1607        assert_eq!(result.minimized_len, threshold);
1608        assert_eq!(result.original_len, 10);
1609        assert_eq!(result.prefix.events.len(), threshold);
1610        assert!(!result.truncated);
1611    }
1612
1613    #[test]
1614    fn minimize_already_minimal() {
1615        // Single event — already minimal.
1616        let trace = make_trace(42, vec![ReplayEvent::RngSeed { seed: 42 }]);
1617
1618        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |_| true);
1619
1620        assert_eq!(result.minimized_len, 1);
1621        assert_eq!(result.evaluations, 0);
1622        assert!(!result.truncated);
1623    }
1624
1625    #[test]
1626    fn minimize_full_prefix_required() {
1627        // Only the full prefix (length 10) reproduces.
1628        let events: Vec<_> = (0..10)
1629            .map(|i| ReplayEvent::RngValue { value: i })
1630            .collect();
1631        let trace = make_trace(42, events);
1632
1633        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1634            prefix.len() >= 10
1635        });
1636
1637        assert_eq!(result.minimized_len, 10);
1638        assert!(!result.truncated);
1639    }
1640
1641    #[test]
1642    fn minimize_respects_min_prefix_len() {
1643        // Failure reproduces at length >= 3, but min is 5.
1644        let events: Vec<_> = (0..10)
1645            .map(|i| ReplayEvent::RngValue { value: i })
1646            .collect();
1647        let trace = make_trace(42, events);
1648
1649        let config = MinimizationConfig {
1650            min_prefix_len: 5,
1651            max_evaluations: 0,
1652        };
1653
1654        let result = minimize_divergent_prefix(&trace, &config, |prefix| prefix.len() >= 3);
1655
1656        // Search starts at min_prefix_len=5, and oracle is true at 5,
1657        // so result is 5.
1658        assert_eq!(result.minimized_len, 5);
1659    }
1660
1661    #[test]
1662    fn minimize_respects_max_evaluations() {
1663        // 1000 events, threshold at 500. With max_evaluations=2,
1664        // we can't binary-search all the way.
1665        let events: Vec<_> = (0..1000)
1666            .map(|i| ReplayEvent::RngValue { value: i })
1667            .collect();
1668        let trace = make_trace(42, events);
1669
1670        let config = MinimizationConfig {
1671            min_prefix_len: 1,
1672            max_evaluations: 2,
1673        };
1674
1675        let result = minimize_divergent_prefix(&trace, &config, |prefix| prefix.len() >= 500);
1676
1677        assert!(result.truncated);
1678        assert_eq!(result.evaluations, 2);
1679        // Should still have found a shorter prefix than original.
1680        assert!(result.minimized_len <= 1000);
1681        // And it should be a reproducing prefix (>= 500).
1682        assert!(result.minimized_len >= 500);
1683    }
1684
1685    #[test]
1686    fn minimize_preserves_metadata() {
1687        let events: Vec<_> = (0..10)
1688            .map(|i| ReplayEvent::RngValue { value: i })
1689            .collect();
1690        let trace = make_trace(0xBEEF, events);
1691
1692        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1693            prefix.len() >= 5
1694        });
1695
1696        assert_eq!(result.prefix.metadata.seed, 0xBEEF);
1697    }
1698
1699    #[test]
1700    fn minimize_binary_search_efficiency() {
1701        // 1024 events. Binary search should take at most ceil(log2(1024)) = 10 evals.
1702        let events: Vec<_> = (0..1024)
1703            .map(|i| ReplayEvent::RngValue { value: i })
1704            .collect();
1705        let trace = make_trace(42, events);
1706
1707        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1708            prefix.len() >= 300
1709        });
1710
1711        assert_eq!(result.minimized_len, 300);
1712        assert!(
1713            result.evaluations <= 10,
1714            "evaluations={}",
1715            result.evaluations
1716        );
1717    }
1718
1719    #[test]
1720    fn minimize_threshold_one() {
1721        // Any non-empty prefix reproduces.
1722        let events: Vec<_> = (0..100)
1723            .map(|i| ReplayEvent::RngValue { value: i })
1724            .collect();
1725        let trace = make_trace(42, events);
1726
1727        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |_| true);
1728
1729        assert_eq!(result.minimized_len, 1);
1730    }
1731
1732    // =========================================================================
1733    // Wave 59 – pure data-type trait coverage
1734    // =========================================================================
1735
1736    #[test]
1737    fn diagnostic_config_debug_clone() {
1738        let cfg = DiagnosticConfig::default();
1739        let dbg = format!("{cfg:?}");
1740        assert!(dbg.contains("DiagnosticConfig"), "{dbg}");
1741        let cloned = cfg;
1742        assert_eq!(cloned.context_before, 10);
1743    }
1744
1745    #[test]
1746    fn affected_entities_debug_clone_default() {
1747        let ae = AffectedEntities::default();
1748        let dbg = format!("{ae:?}");
1749        assert!(dbg.contains("AffectedEntities"), "{dbg}");
1750        let cloned = ae;
1751        assert!(cloned.tasks.is_empty());
1752    }
1753
1754    #[test]
1755    fn divergence_report_text_snapshot_scrubbed() {
1756        let trace = make_trace(
1757            0xBEEF,
1758            vec![
1759                ReplayEvent::TaskScheduled {
1760                    task: CompactTaskId(1),
1761                    at_tick: 0,
1762                },
1763                ReplayEvent::TaskScheduled {
1764                    task: CompactTaskId(2),
1765                    at_tick: 1,
1766                },
1767                ReplayEvent::TaskCompleted {
1768                    task: CompactTaskId(2),
1769                    outcome: 0,
1770                },
1771            ],
1772        );
1773
1774        let error = make_error(
1775            1,
1776            ReplayEvent::TaskScheduled {
1777                task: CompactTaskId(2),
1778                at_tick: 1,
1779            },
1780            ReplayEvent::TaskScheduled {
1781                task: CompactTaskId(3),
1782                at_tick: 1,
1783            },
1784        );
1785
1786        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1787        insta::assert_snapshot!(
1788            "divergence_report_text_scrubbed",
1789            scrub_divergence_text(&report.to_text())
1790        );
1791    }
1792}
asupersync/trace/divergence.rs

asupersync/trace/
divergence.rs
