Skip to main content

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}