rusty_agent_runtime/team_trace.rs
1//! TeamTrace: cross-journal trace assembly for the Agent Fabric (R0.7
2//! wave 3).
3//!
4//! A coordination pattern's evidence does not live in one journal. The
5//! pattern's own journal holds the `CoordinationStart` → `MailboxSend` →
6//! `MailboxReceive` → `CoordinationEnd` spine, and member agents write
7//! their own run journals. Every event carries a `parent` link, so the
8//! causal tree exists in the data — but each journal only stores its own
9//! slice of it. TeamTrace is the read-side algorithm that stitches those
10//! slices back into one tree: give it the snapshots (already integrity
11//! verified by [`crate::journal::Journal::from_snapshot`]) and it returns
12//! one deterministic, connected view.
13//!
14//! The module is deliberately read-only and pure: assembly never writes,
15//! never mutates the journals, and never invents links. A node whose
16//! parent is absent from the assembled set is a **root** — that is the
17//! cross-journal stitch: the coordination journal's `MailboxSend` is the
18//! parent of events in a member run's journal, and the stitch holds
19//! because both sides record the same deterministic event ids.
20//!
21//! Determinism is the contract: the same snapshots always assemble into
22//! the byte-identical trace (`run_ids` sorted, nodes sorted by
23//! `(run_id, seq)`, children sorted by the child's `(run_id, seq)`). The
24//! trace is evidence, and evidence that depends on iteration order is not
25//! evidence.
26
27use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
28
29use serde::{Deserialize, Serialize};
30
31use crate::journal::JournalSnapshot;
32use crate::record::RunEventKind;
33
34/// One node in an assembled team trace: a single journaled event plus its
35/// position in the cross-journal causal tree.
36#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
37pub struct TeamTraceNode {
38 /// The event's deterministic id (`{run_id}:{seq}`).
39 pub event_id: String,
40
41 /// The journal (run) this event was recorded in.
42 pub run_id: String,
43
44 /// The event's sequence number within its own journal.
45 pub seq: u64,
46
47 /// What happened.
48 pub kind: RunEventKind,
49
50 /// The parent event id as journaled. `None` for a causal root; an id
51 /// outside the assembled set means the parent lives in a journal that
52 /// was not part of this assembly (the node is then a root of this
53 /// trace, and `parent` still names where it hangs in the wider tree).
54 #[serde(default, skip_serializing_if = "Option::is_none")]
55 pub parent: Option<String>,
56
57 /// The event ids of this node's children inside the assembled set,
58 /// sorted by the child's `(run_id, seq)` — deterministic regardless of
59 /// the order snapshots were supplied in.
60 #[serde(default, skip_serializing_if = "Vec::is_empty")]
61 pub children: Vec<String>,
62
63 /// The node's depth below a root (root = 0). `None` when the node is
64 /// unreachable from every root — the signature of a parent cycle that
65 /// no root can enter, which a hand-edited or corrupted journal could
66 /// produce. [`TeamTrace::is_connected`] refuses such traces.
67 #[serde(default, skip_serializing_if = "Option::is_none")]
68 pub depth: Option<u32>,
69}
70
71/// A cross-journal causal tree assembled from verified journal snapshots
72/// (R0.7 wave 3).
73#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
74pub struct TeamTrace {
75 /// Every run id that contributed events, sorted — the journals this
76 /// trace stitched together.
77 pub run_ids: Vec<String>,
78
79 /// The event ids of the trace's roots, sorted. A connected
80 /// coordination has exactly one root: its `CoordinationStart` event.
81 pub roots: Vec<String>,
82
83 /// Every node, sorted by `(run_id, seq)` — a total, deterministic
84 /// order over the whole assembled tree.
85 pub nodes: Vec<TeamTraceNode>,
86}
87
88impl TeamTrace {
89 /// Assemble one trace from verified journal snapshots.
90 ///
91 /// The algorithm:
92 ///
93 /// 1. Collect every event of every snapshot into nodes keyed by event
94 /// id. Duplicate ids (the same journal supplied twice) collapse —
95 /// the event is one fact.
96 /// 2. Link children: an event whose `parent` names an event inside the
97 /// assembled set is that node's child. A parent outside the set
98 /// does not make the event parentless — `parent` keeps naming it —
99 /// but it does make the event a root *of this trace*.
100 /// 3. Assign depths breadth-first from the roots, with a visited set
101 /// so a parent cycle can never loop the walk; cycle members that no
102 /// root reaches keep `depth: None`.
103 pub fn assemble(snapshots: &[JournalSnapshot]) -> Self {
104 // Pass 1: collect events. BTreeMap keyed by event id collapses
105 // duplicate journals and gives a stable iteration order for free.
106 let mut events: BTreeMap<String, (String, u64, RunEventKind, Option<String>)> =
107 BTreeMap::new();
108 for snapshot in snapshots {
109 for event in &snapshot.events {
110 events.entry(event.id.clone()).or_insert_with(|| {
111 (
112 event.run_id.clone(),
113 event.seq,
114 event.kind,
115 event.parent.clone(),
116 )
117 });
118 }
119 }
120
121 // Pass 2: children adjacency, keyed by parent event id.
122 let mut children_of: HashMap<String, Vec<String>> = HashMap::new();
123 let mut roots: BTreeSet<String> = BTreeSet::new();
124 for (id, (_, _, _, parent)) in &events {
125 match parent {
126 Some(parent_id) if events.contains_key(parent_id) => {
127 children_of
128 .entry(parent_id.clone())
129 .or_default()
130 .push(id.clone());
131 }
132 _ => {
133 roots.insert(id.clone());
134 }
135 }
136 }
137 // Sort each child list by the child's (run_id, seq), not the id
138 // string — lexical order would rank "run:10" before "run:2".
139 for children in children_of.values_mut() {
140 children.sort_by_key(|a| node_order(&events, a));
141 }
142
143 // Pass 3: depths, breadth-first from every root, cycle-safe.
144 let mut depth_of: HashMap<String, u32> = HashMap::new();
145 let mut visited: HashSet<String> = HashSet::new();
146 let mut queue: VecDeque<(String, u32)> = VecDeque::new();
147 for root in &roots {
148 queue.push_back((root.clone(), 0));
149 }
150 while let Some((id, depth)) = queue.pop_front() {
151 if !visited.insert(id.clone()) {
152 continue;
153 }
154 depth_of.insert(id.clone(), depth);
155 if let Some(children) = children_of.get(&id) {
156 for child in children {
157 queue.push_back((child.clone(), depth + 1));
158 }
159 }
160 }
161
162 let mut run_ids: Vec<String> = events
163 .values()
164 .map(|(run_id, _, _, _)| run_id.clone())
165 .collect::<BTreeSet<_>>()
166 .into_iter()
167 .collect();
168 run_ids.sort();
169
170 let nodes: Vec<TeamTraceNode> = {
171 let mut keyed: Vec<((String, u64), TeamTraceNode)> = events
172 .into_iter()
173 .map(|(id, (run_id, seq, kind, parent))| {
174 let node = TeamTraceNode {
175 children: children_of.remove(&id).unwrap_or_default(),
176 depth: depth_of.get(&id).copied(),
177 event_id: id,
178 run_id: run_id.clone(),
179 seq,
180 kind,
181 parent,
182 };
183 ((node.run_id.clone(), seq), node)
184 })
185 .collect();
186 keyed.sort_by(|a, b| a.0.cmp(&b.0));
187 keyed.into_iter().map(|(_, node)| node).collect()
188 };
189
190 Self {
191 run_ids,
192 roots: roots.into_iter().collect(),
193 nodes,
194 }
195 }
196
197 /// `true` when the assembled trace is one connected tree: exactly one
198 /// root, and every node reachable from it (no detached cycles). A
199 /// coordination's journal set should always assemble connected — the
200 /// `CoordinationStart` event is the single causal root; anything else
201 /// means journals are missing from the assembly or events were
202 /// corrupted, and the caller should treat the trace as incomplete
203 /// evidence rather than as a tree.
204 pub fn is_connected(&self) -> bool {
205 self.roots.len() == 1
206 && !self.nodes.is_empty()
207 && self.nodes.iter().all(|node| node.depth.is_some())
208 }
209
210 /// Look up one node by event id.
211 pub fn node(&self, event_id: &str) -> Option<&TeamTraceNode> {
212 self.nodes.iter().find(|node| node.event_id == event_id)
213 }
214}
215
216/// The `(run_id, seq)` sort key of an event id already collected into the
217/// events map. Assembly only calls this for ids known to be present.
218fn node_order(
219 events: &BTreeMap<String, (String, u64, RunEventKind, Option<String>)>,
220 id: &str,
221) -> (String, u64) {
222 match events.get(id) {
223 Some((run_id, seq, _, _)) => (run_id.clone(), *seq),
224 None => (String::new(), 0),
225 }
226}
227
228#[cfg(test)]
229mod tests {
230 use super::*;
231 use crate::journal::JournalSnapshot;
232 use crate::record::{Effect, EventStatus, PayloadRef, RunEvent};
233 use serde_json::json;
234
235 /// Build a minimal journal snapshot with the given events. Assembly
236 /// reads only `events`, so the hash chain fields are inert here — the
237 /// integrity contract is upheld by `Journal::from_snapshot` before
238 /// snapshots ever reach `assemble`.
239 fn snapshot(run_id: &str, events: Vec<RunEvent>) -> JournalSnapshot {
240 JournalSnapshot {
241 run_id: run_id.to_string(),
242 thread_id: format!("thread:{run_id}"),
243 events,
244 artifacts: BTreeMap::new(),
245 // W4 additive field: this helper assembles in-memory snapshots,
246 // which never reference an external artifact store.
247 artifact_refs: BTreeMap::new(),
248 head_hash: String::new(),
249 }
250 }
251
252 fn event(run_id: &str, seq: u64, kind: RunEventKind, parent: Option<&str>) -> RunEvent {
253 RunEvent {
254 id: format!("{run_id}:{seq}"),
255 run_id: run_id.to_string(),
256 thread_id: format!("thread:{run_id}"),
257 node_id: None,
258 seq,
259 kind,
260 effect: Effect::Pure,
261 input: None,
262 output: Some(PayloadRef::inline(json!({"seq": seq}))),
263 latency_ms: None,
264 tokens: None,
265 cost_usd: None,
266 status: EventStatus::Ok,
267 parent: parent.map(str::to_string),
268 recorded_at: chrono::DateTime::from_timestamp_millis(1_800_000_000_000).unwrap(),
269 }
270 }
271
272 /// The canonical coordination spine, stitched across two journals:
273 /// the coordination journal holds start/send/receive/end, the member
274 /// journal holds the member run's own events parented onto the send.
275 fn stitched_snapshots() -> (JournalSnapshot, JournalSnapshot) {
276 let coordination = snapshot(
277 "coordination:acme:c1",
278 vec![
279 event(
280 "coordination:acme:c1",
281 1,
282 RunEventKind::CoordinationStart,
283 None,
284 ),
285 event(
286 "coordination:acme:c1",
287 2,
288 RunEventKind::MailboxSend,
289 Some("coordination:acme:c1:1"),
290 ),
291 event(
292 "coordination:acme:c1",
293 3,
294 RunEventKind::MailboxReceive,
295 Some("coordination:acme:c1:2"),
296 ),
297 event(
298 "coordination:acme:c1",
299 4,
300 RunEventKind::CoordinationEnd,
301 Some("coordination:acme:c1:1"),
302 ),
303 ],
304 );
305 let member = snapshot(
306 "run:member-a",
307 vec![
308 event(
309 "run:member-a",
310 1,
311 RunEventKind::SuperStepStart,
312 Some("coordination:acme:c1:2"),
313 ),
314 event(
315 "run:member-a",
316 2,
317 RunEventKind::ModelCall,
318 Some("run:member-a:1"),
319 ),
320 ],
321 );
322 (coordination, member)
323 }
324
325 #[test]
326 fn assembles_one_connected_tree_across_journals() {
327 let (coordination, member) = stitched_snapshots();
328 let trace = TeamTrace::assemble(&[coordination, member]);
329
330 assert!(trace.is_connected());
331 assert_eq!(trace.roots, vec!["coordination:acme:c1:1".to_string()]);
332 assert_eq!(
333 trace.run_ids,
334 vec![
335 "coordination:acme:c1".to_string(),
336 "run:member-a".to_string()
337 ]
338 );
339
340 // Depths: start 0 → send 1 → receive 2; end hangs off start at 1;
341 // the member run stitches under the send at 2, its model call at 3.
342 let depth = |id: &str| trace.node(id).and_then(|n| n.depth);
343 assert_eq!(depth("coordination:acme:c1:1"), Some(0));
344 assert_eq!(depth("coordination:acme:c1:2"), Some(1));
345 assert_eq!(depth("coordination:acme:c1:3"), Some(2));
346 assert_eq!(depth("coordination:acme:c1:4"), Some(1));
347 assert_eq!(depth("run:member-a:1"), Some(2));
348 assert_eq!(depth("run:member-a:2"), Some(3));
349
350 // Children are deterministic and reflect the cross-journal stitch.
351 let send = trace.node("coordination:acme:c1:2").unwrap();
352 assert_eq!(
353 send.children,
354 vec![
355 "coordination:acme:c1:3".to_string(),
356 "run:member-a:1".to_string()
357 ]
358 );
359 }
360
361 #[test]
362 fn assembly_is_deterministic_under_snapshot_order() {
363 let (coordination, member) = stitched_snapshots();
364 let forward = TeamTrace::assemble(&[coordination.clone(), member.clone()]);
365 let reversed = TeamTrace::assemble(&[member, coordination]);
366 assert_eq!(forward, reversed);
367 // And byte-deterministic on the wire.
368 assert_eq!(
369 serde_json::to_string(&forward).unwrap(),
370 serde_json::to_string(&reversed).unwrap()
371 );
372 }
373
374 #[test]
375 fn parent_outside_the_assembled_set_is_a_root() {
376 // Only the member journal supplied: its RunStart parents onto a
377 // send event that is not in the set, so it becomes a root — with
378 // `parent` still naming the missing link.
379 let (_, member) = stitched_snapshots();
380 let trace = TeamTrace::assemble(&[member]);
381 assert!(trace.is_connected());
382 assert_eq!(trace.roots, vec!["run:member-a:1".to_string()]);
383 let root = trace.node("run:member-a:1").unwrap();
384 assert_eq!(root.parent.as_deref(), Some("coordination:acme:c1:2"));
385 assert_eq!(root.depth, Some(0));
386 }
387
388 #[test]
389 fn two_roots_are_not_connected() {
390 let a = snapshot(
391 "run:a",
392 vec![event("run:a", 1, RunEventKind::SuperStepStart, None)],
393 );
394 let b = snapshot(
395 "run:b",
396 vec![event("run:b", 1, RunEventKind::SuperStepStart, None)],
397 );
398 let trace = TeamTrace::assemble(&[a, b]);
399 assert!(!trace.is_connected());
400 assert_eq!(trace.roots.len(), 2);
401 }
402
403 #[test]
404 fn parent_cycle_neither_hangs_nor_connects() {
405 // a:1 → a:2 → a:1: a cycle no root can enter. The walk must
406 // terminate (visited set), the cycle nodes stay depth-less, and the
407 // trace reports not-connected instead of inventing a tree.
408 let cycled = snapshot(
409 "run:a",
410 vec![
411 event("run:a", 1, RunEventKind::SuperStepStart, Some("run:a:2")),
412 event("run:a", 2, RunEventKind::ModelCall, Some("run:a:1")),
413 ],
414 );
415 let trace = TeamTrace::assemble(&[cycled]);
416 assert!(trace.roots.is_empty());
417 assert!(trace.nodes.iter().all(|node| node.depth.is_none()));
418 assert!(!trace.is_connected());
419 }
420
421 #[test]
422 fn child_sorting_uses_seq_not_lexical_id_order() {
423 // "run:a:10" sorts before "run:a:2" lexically; the trace must order
424 // children by sequence.
425 let snap = snapshot(
426 "run:a",
427 vec![
428 event("run:a", 1, RunEventKind::SuperStepStart, None),
429 event("run:a", 2, RunEventKind::ModelCall, Some("run:a:1")),
430 event("run:a", 10, RunEventKind::ModelCall, Some("run:a:1")),
431 ],
432 );
433 let trace = TeamTrace::assemble(&[snap]);
434 let root = trace.node("run:a:1").unwrap();
435 assert_eq!(
436 root.children,
437 vec!["run:a:2".to_string(), "run:a:10".to_string()]
438 );
439 }
440
441 #[test]
442 fn empty_assembly_is_empty_and_not_connected() {
443 let trace = TeamTrace::assemble(&[]);
444 assert!(trace.run_ids.is_empty());
445 assert!(trace.roots.is_empty());
446 assert!(trace.nodes.is_empty());
447 assert!(!trace.is_connected());
448 }
449
450 #[test]
451 fn duplicate_journals_collapse_to_one_fact() {
452 let (coordination, _) = stitched_snapshots();
453 let trace = TeamTrace::assemble(&[coordination.clone(), coordination]);
454 assert_eq!(trace.nodes.len(), 4);
455 assert!(trace.is_connected());
456 }
457}