katra_trace/
verify.rs

1//! Trace verification: checks the invariants a well-formed trace must obey.
2
3use std::collections::HashSet;
4
5use katra_core::{EventKind, Phase};
6
7use crate::reader::TraceReader;
8use crate::record::TraceRecord;
9
10/// A single verification finding.
11#[derive(Clone, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
12pub struct VerifyIssue {
13    /// Whether this is an error (invariant violation) or a warning.
14    pub is_error: bool,
15    /// Human-readable description.
16    pub message: String,
17}
18
19/// The result of verifying a trace.
20#[derive(Clone, Debug, Default, serde::Serialize, serde::Deserialize)]
21pub struct VerifyReport {
22    /// Issues found.
23    pub issues: Vec<VerifyIssue>,
24    /// Events inspected.
25    pub event_count: u64,
26    /// Highest sequence number.
27    pub max_seq: u64,
28    /// Whether sequence numbers were strictly monotonic.
29    pub monotonic: bool,
30    /// Whether all causal links referenced earlier, existing events.
31    pub causal_ok: bool,
32    /// Number of begin spans without a matching end (by thread+span).
33    pub unclosed_spans: u64,
34}
35
36impl VerifyReport {
37    /// True if no error-level issues were found.
38    pub fn is_clean(&self) -> bool {
39        !self.issues.iter().any(|i| i.is_error)
40    }
41}
42
43/// Verify every invariant of a trace stream, consuming it.
44pub fn verify(reader: &mut TraceReader) -> VerifyReport {
45    let mut report = VerifyReport::default();
46    let mut seen_seqs: HashSet<u64> = HashSet::new();
47    let mut last_seq: Option<u64> = None;
48    // (thread, span) -> count of open begins
49    let mut open_spans: std::collections::HashMap<(u64, u64), u64> =
50        std::collections::HashMap::new();
51
52    loop {
53        match reader.next_record() {
54            Ok(Some(TraceRecord::Event(ev))) => {
55                report.event_count += 1;
56                if ev.seq.0 > report.max_seq {
57                    report.max_seq = ev.seq.0;
58                }
59                if let Some(last) = last_seq {
60                    if ev.seq.0 <= last {
61                        report.monotonic = false;
62                        report.issues.push(VerifyIssue {
63                            is_error: true,
64                            message: format!("sequence not monotonic: {} after {}", ev.seq.0, last),
65                        });
66                    }
67                }
68                last_seq = Some(ev.seq.0);
69                if !seen_seqs.insert(ev.seq.0) {
70                    report.issues.push(VerifyIssue {
71                        is_error: true,
72                        message: format!("duplicate sequence {}", ev.seq.0),
73                    });
74                }
75                // Causal links must point at earlier events.
76                for cause in &ev.causes {
77                    if !seen_seqs.contains(cause) {
78                        report.causal_ok = false;
79                        report.issues.push(VerifyIssue {
80                            is_error: true,
81                            message: format!(
82                                "event {} references unknown/future cause {}",
83                                ev.seq.0, cause
84                            ),
85                        });
86                    }
87                }
88                // Span balance.
89                match ev.phase {
90                    Phase::Begin => {
91                        if let Some(span) = ev.span_id {
92                            let key = (ev.thread_id, span.0);
93                            *open_spans.entry(key).or_insert(0) += 1;
94                        } else {
95                            report.issues.push(VerifyIssue {
96                                is_error: true,
97                                message: format!("event {} is Begin without span_id", ev.seq.0),
98                            });
99                        }
100                    }
101                    Phase::End => {
102                        if let Some(span) = ev.span_id {
103                            let key = (ev.thread_id, span.0);
104                            match open_spans.get_mut(&key) {
105                                Some(n) if *n > 0 => {
106                                    *n -= 1;
107                                    if *n == 0 {
108                                        open_spans.remove(&key);
109                                    }
110                                }
111                                _ => {
112                                    report.issues.push(VerifyIssue {
113                                        is_error: true,
114                                        message: format!(
115                                            "event {} is End without matching Begin \
116                                             (thread {}, span {})",
117                                            ev.seq.0, ev.thread_id, span.0
118                                        ),
119                                    });
120                                }
121                            }
122                        }
123                    }
124                    _ => {}
125                }
126            }
127            Ok(Some(TraceRecord::SessionSummary(_))) => {}
128            Ok(Some(_)) => {}
129            Ok(None) => break,
130            Err(e) => {
131                report
132                    .issues
133                    .push(VerifyIssue { is_error: true, message: format!("read error: {e}") });
134                break;
135            }
136        }
137    }
138
139    report.unclosed_spans = open_spans.values().sum();
140    for ((thread, span), count) in open_spans {
141        if count > 0 {
142            report.issues.push(VerifyIssue {
143                is_error: true,
144                message: format!("unclosed span: thread {thread}, span {span}, {count} begins"),
145            });
146        }
147    }
148    if report.monotonic {
149        report.issues.push(VerifyIssue {
150            is_error: false,
151            message: "sequence numbers strictly monotonic".into(),
152        });
153    }
154    if report.causal_ok && report.event_count > 0 {
155        report.issues.push(VerifyIssue {
156            is_error: false,
157            message: "all causal links reference existing earlier events".into(),
158        });
159    }
160    report
161}
162
163/// Whether a kind participates in the semantic graph rebuild (nodes).
164pub fn is_graph_kind(kind: EventKind) -> bool {
165    matches!(
166        kind,
167        EventKind::FileRead
168            | EventKind::NtReadFile
169            | EventKind::IoRead
170            | EventKind::KatraDecompress
171            | EventKind::KatraStaging
172            | EventKind::ResourceUpload
173            | EventKind::Barrier
174            | EventKind::FenceWait
175            | EventKind::FenceSignal
176            | EventKind::Present
177            | EventKind::GpuDraw
178            | EventKind::GpuComputeDispatch
179            | EventKind::KatraPrefetch
180            | EventKind::KatraAllocate
181            | EventKind::CacheHit
182            | EventKind::CacheMiss
183            | EventKind::PipelineCreate
184            | EventKind::ShaderTranslate
185            | EventKind::KatraIoWait
186    )
187}
katra_trace/verify.rs

katra_trace/
verify.rs
