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    // -------------------------------------------------------------------------
1096    // Classification tests
1097    // -------------------------------------------------------------------------
1098
1099    #[test]
1100    fn classify_scheduling_order() {
1101        let cat = classify_divergence(
1102            Some(&ReplayEvent::TaskScheduled {
1103                task: CompactTaskId(1),
1104                at_tick: 0,
1105            }),
1106            &ReplayEvent::TaskScheduled {
1107                task: CompactTaskId(2),
1108                at_tick: 0,
1109            },
1110        );
1111        assert_eq!(cat, DivergenceCategory::SchedulingOrder);
1112    }
1113
1114    #[test]
1115    fn classify_outcome_mismatch() {
1116        let cat = classify_divergence(
1117            Some(&ReplayEvent::TaskCompleted {
1118                task: CompactTaskId(1),
1119                outcome: 0,
1120            }),
1121            &ReplayEvent::TaskCompleted {
1122                task: CompactTaskId(1),
1123                outcome: 2,
1124            },
1125        );
1126        assert_eq!(cat, DivergenceCategory::OutcomeMismatch);
1127    }
1128
1129    #[test]
1130    fn classify_event_type_mismatch() {
1131        let cat = classify_divergence(
1132            Some(&ReplayEvent::RngSeed { seed: 42 }),
1133            &ReplayEvent::TaskScheduled {
1134                task: CompactTaskId(1),
1135                at_tick: 0,
1136            },
1137        );
1138        assert_eq!(cat, DivergenceCategory::EventTypeMismatch);
1139    }
1140
1141    #[test]
1142    fn classify_time_divergence() {
1143        let cat = classify_divergence(
1144            Some(&ReplayEvent::TimeAdvanced {
1145                from_nanos: 0,
1146                to_nanos: 1000,
1147            }),
1148            &ReplayEvent::TimeAdvanced {
1149                from_nanos: 0,
1150                to_nanos: 2000,
1151            },
1152        );
1153        assert_eq!(cat, DivergenceCategory::TimeDivergence);
1154    }
1155
1156    #[test]
1157    fn classify_rng_mismatch() {
1158        let cat = classify_divergence(
1159            Some(&ReplayEvent::RngSeed { seed: 42 }),
1160            &ReplayEvent::RngSeed { seed: 99 },
1161        );
1162        assert_eq!(cat, DivergenceCategory::RngMismatch);
1163    }
1164
1165    #[test]
1166    fn classify_checkpoint_mismatch() {
1167        let cat = classify_divergence(
1168            Some(&ReplayEvent::Checkpoint {
1169                sequence: 1,
1170                time_nanos: 100,
1171                active_tasks: 3,
1172                active_regions: 1,
1173            }),
1174            &ReplayEvent::Checkpoint {
1175                sequence: 1,
1176                time_nanos: 100,
1177                active_tasks: 5,
1178                active_regions: 1,
1179            },
1180        );
1181        assert_eq!(cat, DivergenceCategory::CheckpointMismatch);
1182    }
1183
1184    // -------------------------------------------------------------------------
1185    // Full report tests
1186    // -------------------------------------------------------------------------
1187
1188    #[test]
1189    fn diagnose_scheduling_divergence() {
1190        let events = vec![
1191            ReplayEvent::RngSeed { seed: 42 },
1192            ReplayEvent::TaskSpawned {
1193                task: CompactTaskId(1),
1194                region: CompactRegionId(100),
1195                at_tick: 0,
1196            },
1197            ReplayEvent::TaskSpawned {
1198                task: CompactTaskId(2),
1199                region: CompactRegionId(100),
1200                at_tick: 0,
1201            },
1202            ReplayEvent::TaskScheduled {
1203                task: CompactTaskId(1),
1204                at_tick: 1,
1205            },
1206            ReplayEvent::TaskScheduled {
1207                task: CompactTaskId(2),
1208                at_tick: 2,
1209            },
1210        ];
1211        let trace = make_trace(0xDEAD, events);
1212
1213        let error = make_error(
1214            3,
1215            ReplayEvent::TaskScheduled {
1216                task: CompactTaskId(1),
1217                at_tick: 1,
1218            },
1219            ReplayEvent::TaskScheduled {
1220                task: CompactTaskId(2),
1221                at_tick: 1,
1222            },
1223        );
1224
1225        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1226
1227        assert_eq!(report.category, DivergenceCategory::SchedulingOrder);
1228        assert_eq!(report.divergence_index, 3);
1229        assert_eq!(report.trace_length, 5);
1230        assert_eq!(report.minimal_prefix_len, 4);
1231        assert_eq!(report.seed, 0xDEAD);
1232        assert!(report.replay_progress_pct > 50.0);
1233        assert!(report.affected.tasks.contains(&1));
1234        assert!(report.affected.tasks.contains(&2));
1235        assert!(report.explanation.contains("Scheduler chose"));
1236        assert!(!report.context_before.is_empty());
1237    }
1238
1239    #[test]
1240    fn diagnose_outcome_divergence() {
1241        let events = vec![
1242            ReplayEvent::TaskScheduled {
1243                task: CompactTaskId(1),
1244                at_tick: 0,
1245            },
1246            ReplayEvent::TaskCompleted {
1247                task: CompactTaskId(1),
1248                outcome: 0,
1249            },
1250        ];
1251        let trace = make_trace(42, events);
1252
1253        let error = make_error(
1254            1,
1255            ReplayEvent::TaskCompleted {
1256                task: CompactTaskId(1),
1257                outcome: 0,
1258            },
1259            ReplayEvent::TaskCompleted {
1260                task: CompactTaskId(1),
1261                outcome: 3,
1262            },
1263        );
1264
1265        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1266
1267        assert_eq!(report.category, DivergenceCategory::OutcomeMismatch);
1268        assert!(report.explanation.contains("Panicked"));
1269        assert!(report.explanation.contains("Ok"));
1270    }
1271
1272    #[test]
1273    fn diagnose_event_type_mismatch() {
1274        let events = vec![
1275            ReplayEvent::RngSeed { seed: 42 },
1276            ReplayEvent::TaskScheduled {
1277                task: CompactTaskId(1),
1278                at_tick: 0,
1279            },
1280        ];
1281        let trace = make_trace(42, events);
1282
1283        let error = make_error(
1284            1,
1285            ReplayEvent::TaskScheduled {
1286                task: CompactTaskId(1),
1287                at_tick: 0,
1288            },
1289            ReplayEvent::TimerFired { timer_id: 99 },
1290        );
1291
1292        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1293
1294        assert_eq!(report.category, DivergenceCategory::EventTypeMismatch);
1295        assert!(report.explanation.contains("TaskScheduled"));
1296        assert!(report.explanation.contains("TimerFired"));
1297    }
1298
1299    #[test]
1300    fn diagnose_trace_exhausted_divergence() {
1301        let events = vec![ReplayEvent::RngSeed { seed: 42 }];
1302        let trace = make_trace(0xCAFE, events);
1303        let error = DivergenceError {
1304            index: 1,
1305            expected: None,
1306            actual: ReplayEvent::RngSeed { seed: 99 },
1307            context: "Trace ended but execution continued".to_string(),
1308        };
1309
1310        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1311
1312        assert_eq!(report.category, DivergenceCategory::LengthMismatch);
1313        assert_eq!(report.expected.event_type, "TraceExhausted");
1314        assert!(
1315            report
1316                .expected
1317                .details
1318                .contains("recorded trace ended before this event")
1319        );
1320        assert!(report.explanation.contains("trace is exhausted"));
1321        assert_eq!(report.actual.event_type, "RngSeed");
1322    }
1323
1324    // -------------------------------------------------------------------------
1325    // Context window tests
1326    // -------------------------------------------------------------------------
1327
1328    #[test]
1329    fn context_window_bounds() {
1330        let events: Vec<_> = (0..20)
1331            .map(|i| ReplayEvent::RngValue { value: i })
1332            .collect();
1333        let trace = make_trace(42, events);
1334
1335        let error = make_error(
1336            10,
1337            ReplayEvent::RngValue { value: 10 },
1338            ReplayEvent::RngValue { value: 99 },
1339        );
1340
1341        let config = DiagnosticConfig {
1342            context_before: 3,
1343            context_after: 2,
1344            ..DiagnosticConfig::default()
1345        };
1346
1347        let report = diagnose_divergence(&trace, &error, &config);
1348
1349        assert_eq!(report.context_before.len(), 3);
1350        assert_eq!(report.context_after.len(), 2);
1351        assert_eq!(report.context_before[0].index, 7);
1352        assert_eq!(report.context_before[2].index, 9);
1353        assert_eq!(report.context_after[0].index, 11);
1354    }
1355
1356    #[test]
1357    fn context_window_at_start() {
1358        let events = vec![
1359            ReplayEvent::RngSeed { seed: 42 },
1360            ReplayEvent::RngSeed { seed: 43 },
1361        ];
1362        let trace = make_trace(42, events);
1363
1364        let error = make_error(
1365            0,
1366            ReplayEvent::RngSeed { seed: 42 },
1367            ReplayEvent::RngSeed { seed: 99 },
1368        );
1369
1370        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1371
1372        assert!(report.context_before.is_empty());
1373        assert_eq!(report.context_after.len(), 1);
1374    }
1375
1376    #[test]
1377    fn context_window_at_end() {
1378        let events = vec![
1379            ReplayEvent::RngSeed { seed: 42 },
1380            ReplayEvent::RngSeed { seed: 43 },
1381        ];
1382        let trace = make_trace(42, events);
1383
1384        let error = make_error(
1385            1,
1386            ReplayEvent::RngSeed { seed: 43 },
1387            ReplayEvent::RngSeed { seed: 99 },
1388        );
1389
1390        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1391
1392        assert_eq!(report.context_before.len(), 1);
1393        assert!(report.context_after.is_empty());
1394    }
1395
1396    // -------------------------------------------------------------------------
1397    // Minimal prefix tests
1398    // -------------------------------------------------------------------------
1399
1400    #[test]
1401    fn minimal_prefix_extraction() {
1402        let events: Vec<_> = (0..10)
1403            .map(|i| ReplayEvent::RngValue { value: i })
1404            .collect();
1405        let trace = make_trace(42, events);
1406
1407        let prefix = minimal_divergent_prefix(&trace, 5);
1408        assert_eq!(prefix.events.len(), 6); // 0..=5
1409        assert_eq!(prefix.metadata.seed, 42);
1410    }
1411
1412    #[test]
1413    fn minimal_prefix_at_zero() {
1414        let events = vec![ReplayEvent::RngSeed { seed: 42 }];
1415        let trace = make_trace(42, events);
1416
1417        let prefix = minimal_divergent_prefix(&trace, 0);
1418        assert_eq!(prefix.events.len(), 1);
1419    }
1420
1421    #[test]
1422    fn minimal_prefix_beyond_trace() {
1423        let events = vec![ReplayEvent::RngSeed { seed: 42 }];
1424        let trace = make_trace(42, events);
1425
1426        let prefix = minimal_divergent_prefix(&trace, 100);
1427        assert_eq!(prefix.events.len(), 1); // clamped to trace length
1428    }
1429
1430    // -------------------------------------------------------------------------
1431    // Serialization tests
1432    // -------------------------------------------------------------------------
1433
1434    #[test]
1435    fn report_serializes_to_json() {
1436        let events = vec![
1437            ReplayEvent::RngSeed { seed: 42 },
1438            ReplayEvent::TaskScheduled {
1439                task: CompactTaskId(1),
1440                at_tick: 0,
1441            },
1442        ];
1443        let trace = make_trace(42, events);
1444
1445        let error = make_error(
1446            1,
1447            ReplayEvent::TaskScheduled {
1448                task: CompactTaskId(1),
1449                at_tick: 0,
1450            },
1451            ReplayEvent::TaskScheduled {
1452                task: CompactTaskId(2),
1453                at_tick: 0,
1454            },
1455        );
1456
1457        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1458        let json = report.to_json().expect("serialize");
1459
1460        // Verify JSON is valid and contains key fields
1461        let parsed: serde_json::Value = serde_json::from_str(&json).expect("parse");
1462        assert_eq!(parsed["category"], "SchedulingOrder");
1463        assert_eq!(parsed["divergence_index"], 1);
1464        assert_eq!(parsed["seed"], 42);
1465    }
1466
1467    #[test]
1468    fn report_renders_text() {
1469        let events = vec![ReplayEvent::TaskScheduled {
1470            task: CompactTaskId(1),
1471            at_tick: 0,
1472        }];
1473        let trace = make_trace(0xBEEF, events);
1474
1475        let error = make_error(
1476            0,
1477            ReplayEvent::TaskScheduled {
1478                task: CompactTaskId(1),
1479                at_tick: 0,
1480            },
1481            ReplayEvent::TaskScheduled {
1482                task: CompactTaskId(2),
1483                at_tick: 0,
1484            },
1485        );
1486
1487        let report = diagnose_divergence(&trace, &error, &DiagnosticConfig::default());
1488        let text = report.to_text();
1489
1490        assert!(text.contains("Replay Divergence Report"));
1491        assert!(text.contains("scheduling-order"));
1492        assert!(text.contains("0x000000000000beef"));
1493        assert!(text.contains("DIVERGENCE"));
1494    }
1495
1496    // -------------------------------------------------------------------------
1497    // Entity extraction tests
1498    // -------------------------------------------------------------------------
1499
1500    #[test]
1501    fn extract_task_entities() {
1502        let affected = extract_affected_entities(
1503            Some(&ReplayEvent::TaskScheduled {
1504                task: CompactTaskId(1),
1505                at_tick: 0,
1506            }),
1507            &ReplayEvent::TaskScheduled {
1508                task: CompactTaskId(2),
1509                at_tick: 0,
1510            },
1511        );
1512
1513        assert_eq!(affected.tasks, vec![1, 2]);
1514        assert!(affected.regions.is_empty());
1515        assert!(affected.scheduler_lane.is_some());
1516    }
1517
1518    #[test]
1519    fn extract_region_entities() {
1520        let affected = extract_affected_entities(
1521            Some(&ReplayEvent::RegionCreated {
1522                region: CompactRegionId(10),
1523                parent: Some(CompactRegionId(5)),
1524                at_tick: 0,
1525            }),
1526            &ReplayEvent::RegionCreated {
1527                region: CompactRegionId(10),
1528                parent: None,
1529                at_tick: 0,
1530            },
1531        );
1532
1533        assert!(affected.tasks.is_empty());
1534        assert!(affected.regions.contains(&10));
1535        assert!(affected.regions.contains(&5));
1536    }
1537
1538    #[test]
1539    fn extract_timer_entities() {
1540        let affected = extract_affected_entities(
1541            Some(&ReplayEvent::TimerFired { timer_id: 42 }),
1542            &ReplayEvent::TimerFired { timer_id: 99 },
1543        );
1544
1545        assert!(affected.tasks.is_empty());
1546        assert_eq!(affected.timers, vec![42, 99]);
1547    }
1548
1549    // -------------------------------------------------------------------------
1550    // Event summary tests
1551    // -------------------------------------------------------------------------
1552
1553    #[test]
1554    fn event_summary_from_task_scheduled() {
1555        let summary = EventSummary::from_event(
1556            5,
1557            &ReplayEvent::TaskScheduled {
1558                task: CompactTaskId(42),
1559                at_tick: 10,
1560            },
1561        );
1562
1563        assert_eq!(summary.index, 5);
1564        assert_eq!(summary.event_type, "TaskScheduled");
1565        assert!(summary.details.contains("tick=10"));
1566        assert_eq!(summary.task_id, Some(42));
1567        assert_eq!(summary.region_id, None);
1568    }
1569
1570    #[test]
1571    fn event_summary_from_region_created() {
1572        let summary = EventSummary::from_event(
1573            0,
1574            &ReplayEvent::RegionCreated {
1575                region: CompactRegionId(7),
1576                parent: None,
1577                at_tick: 0,
1578            },
1579        );
1580
1581        assert_eq!(summary.event_type, "RegionCreated");
1582        assert_eq!(summary.region_id, Some(7));
1583        assert_eq!(summary.task_id, None);
1584    }
1585
1586    // -------------------------------------------------------------------------
1587    // Prefix minimization tests (bd-2fywr)
1588    // -------------------------------------------------------------------------
1589
1590    #[test]
1591    fn minimize_finds_exact_threshold() {
1592        // 10 events. Failure reproduces when prefix length >= 6.
1593        let events: Vec<_> = (0..10)
1594            .map(|i| ReplayEvent::RngValue { value: i })
1595            .collect();
1596        let trace = make_trace(42, events);
1597
1598        let threshold = 6;
1599        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1600            prefix.len() >= threshold
1601        });
1602
1603        assert_eq!(result.minimized_len, threshold);
1604        assert_eq!(result.original_len, 10);
1605        assert_eq!(result.prefix.events.len(), threshold);
1606        assert!(!result.truncated);
1607    }
1608
1609    #[test]
1610    fn minimize_already_minimal() {
1611        // Single event — already minimal.
1612        let trace = make_trace(42, vec![ReplayEvent::RngSeed { seed: 42 }]);
1613
1614        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |_| true);
1615
1616        assert_eq!(result.minimized_len, 1);
1617        assert_eq!(result.evaluations, 0);
1618        assert!(!result.truncated);
1619    }
1620
1621    #[test]
1622    fn minimize_full_prefix_required() {
1623        // Only the full prefix (length 10) reproduces.
1624        let events: Vec<_> = (0..10)
1625            .map(|i| ReplayEvent::RngValue { value: i })
1626            .collect();
1627        let trace = make_trace(42, events);
1628
1629        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1630            prefix.len() >= 10
1631        });
1632
1633        assert_eq!(result.minimized_len, 10);
1634        assert!(!result.truncated);
1635    }
1636
1637    #[test]
1638    fn minimize_respects_min_prefix_len() {
1639        // Failure reproduces at length >= 3, but min is 5.
1640        let events: Vec<_> = (0..10)
1641            .map(|i| ReplayEvent::RngValue { value: i })
1642            .collect();
1643        let trace = make_trace(42, events);
1644
1645        let config = MinimizationConfig {
1646            min_prefix_len: 5,
1647            max_evaluations: 0,
1648        };
1649
1650        let result = minimize_divergent_prefix(&trace, &config, |prefix| prefix.len() >= 3);
1651
1652        // Search starts at min_prefix_len=5, and oracle is true at 5,
1653        // so result is 5.
1654        assert_eq!(result.minimized_len, 5);
1655    }
1656
1657    #[test]
1658    fn minimize_respects_max_evaluations() {
1659        // 1000 events, threshold at 500. With max_evaluations=2,
1660        // we can't binary-search all the way.
1661        let events: Vec<_> = (0..1000)
1662            .map(|i| ReplayEvent::RngValue { value: i })
1663            .collect();
1664        let trace = make_trace(42, events);
1665
1666        let config = MinimizationConfig {
1667            min_prefix_len: 1,
1668            max_evaluations: 2,
1669        };
1670
1671        let result = minimize_divergent_prefix(&trace, &config, |prefix| prefix.len() >= 500);
1672
1673        assert!(result.truncated);
1674        assert_eq!(result.evaluations, 2);
1675        // Should still have found a shorter prefix than original.
1676        assert!(result.minimized_len <= 1000);
1677        // And it should be a reproducing prefix (>= 500).
1678        assert!(result.minimized_len >= 500);
1679    }
1680
1681    #[test]
1682    fn minimize_preserves_metadata() {
1683        let events: Vec<_> = (0..10)
1684            .map(|i| ReplayEvent::RngValue { value: i })
1685            .collect();
1686        let trace = make_trace(0xBEEF, events);
1687
1688        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1689            prefix.len() >= 5
1690        });
1691
1692        assert_eq!(result.prefix.metadata.seed, 0xBEEF);
1693    }
1694
1695    #[test]
1696    fn minimize_binary_search_efficiency() {
1697        // 1024 events. Binary search should take at most ceil(log2(1024)) = 10 evals.
1698        let events: Vec<_> = (0..1024)
1699            .map(|i| ReplayEvent::RngValue { value: i })
1700            .collect();
1701        let trace = make_trace(42, events);
1702
1703        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |prefix| {
1704            prefix.len() >= 300
1705        });
1706
1707        assert_eq!(result.minimized_len, 300);
1708        assert!(
1709            result.evaluations <= 10,
1710            "evaluations={}",
1711            result.evaluations
1712        );
1713    }
1714
1715    #[test]
1716    fn minimize_threshold_one() {
1717        // Any non-empty prefix reproduces.
1718        let events: Vec<_> = (0..100)
1719            .map(|i| ReplayEvent::RngValue { value: i })
1720            .collect();
1721        let trace = make_trace(42, events);
1722
1723        let result = minimize_divergent_prefix(&trace, &MinimizationConfig::default(), |_| true);
1724
1725        assert_eq!(result.minimized_len, 1);
1726    }
1727
1728    // =========================================================================
1729    // Wave 59 – pure data-type trait coverage
1730    // =========================================================================
1731
1732    #[test]
1733    fn diagnostic_config_debug_clone() {
1734        let cfg = DiagnosticConfig::default();
1735        let dbg = format!("{cfg:?}");
1736        assert!(dbg.contains("DiagnosticConfig"), "{dbg}");
1737        let cloned = cfg;
1738        assert_eq!(cloned.context_before, 10);
1739    }
1740
1741    #[test]
1742    fn affected_entities_debug_clone_default() {
1743        let ae = AffectedEntities::default();
1744        let dbg = format!("{ae:?}");
1745        assert!(dbg.contains("AffectedEntities"), "{dbg}");
1746        let cloned = ae;
1747        assert!(cloned.tasks.is_empty());
1748    }
1749}
asupersync/trace/divergence.rs

asupersync/trace/
divergence.rs
