use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use serde::{Deserialize, Serialize};
use crate::journal::JournalSnapshot;
use crate::record::RunEventKind;
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct TeamTraceNode {
pub event_id: String,
pub run_id: String,
pub seq: u64,
pub kind: RunEventKind,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub parent: Option<String>,
#[serde(default, skip_serializing_if = "Vec::is_empty")]
pub children: Vec<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub depth: Option<u32>,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct TeamTrace {
pub run_ids: Vec<String>,
pub roots: Vec<String>,
pub nodes: Vec<TeamTraceNode>,
}
impl TeamTrace {
pub fn assemble(snapshots: &[JournalSnapshot]) -> Self {
let mut events: BTreeMap<String, (String, u64, RunEventKind, Option<String>)> =
BTreeMap::new();
for snapshot in snapshots {
for event in &snapshot.events {
events.entry(event.id.clone()).or_insert_with(|| {
(
event.run_id.clone(),
event.seq,
event.kind,
event.parent.clone(),
)
});
}
}
let mut children_of: HashMap<String, Vec<String>> = HashMap::new();
let mut roots: BTreeSet<String> = BTreeSet::new();
for (id, (_, _, _, parent)) in &events {
match parent {
Some(parent_id) if events.contains_key(parent_id) => {
children_of
.entry(parent_id.clone())
.or_default()
.push(id.clone());
}
_ => {
roots.insert(id.clone());
}
}
}
for children in children_of.values_mut() {
children.sort_by_key(|a| node_order(&events, a));
}
let mut depth_of: HashMap<String, u32> = HashMap::new();
let mut visited: HashSet<String> = HashSet::new();
let mut queue: VecDeque<(String, u32)> = VecDeque::new();
for root in &roots {
queue.push_back((root.clone(), 0));
}
while let Some((id, depth)) = queue.pop_front() {
if !visited.insert(id.clone()) {
continue;
}
depth_of.insert(id.clone(), depth);
if let Some(children) = children_of.get(&id) {
for child in children {
queue.push_back((child.clone(), depth + 1));
}
}
}
let mut run_ids: Vec<String> = events
.values()
.map(|(run_id, _, _, _)| run_id.clone())
.collect::<BTreeSet<_>>()
.into_iter()
.collect();
run_ids.sort();
let nodes: Vec<TeamTraceNode> = {
let mut keyed: Vec<((String, u64), TeamTraceNode)> = events
.into_iter()
.map(|(id, (run_id, seq, kind, parent))| {
let node = TeamTraceNode {
children: children_of.remove(&id).unwrap_or_default(),
depth: depth_of.get(&id).copied(),
event_id: id,
run_id: run_id.clone(),
seq,
kind,
parent,
};
((node.run_id.clone(), seq), node)
})
.collect();
keyed.sort_by(|a, b| a.0.cmp(&b.0));
keyed.into_iter().map(|(_, node)| node).collect()
};
Self {
run_ids,
roots: roots.into_iter().collect(),
nodes,
}
}
pub fn is_connected(&self) -> bool {
self.roots.len() == 1
&& !self.nodes.is_empty()
&& self.nodes.iter().all(|node| node.depth.is_some())
}
pub fn node(&self, event_id: &str) -> Option<&TeamTraceNode> {
self.nodes.iter().find(|node| node.event_id == event_id)
}
}
fn node_order(
events: &BTreeMap<String, (String, u64, RunEventKind, Option<String>)>,
id: &str,
) -> (String, u64) {
match events.get(id) {
Some((run_id, seq, _, _)) => (run_id.clone(), *seq),
None => (String::new(), 0),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::journal::JournalSnapshot;
use crate::record::{Effect, EventStatus, PayloadRef, RunEvent};
use serde_json::json;
fn snapshot(run_id: &str, events: Vec<RunEvent>) -> JournalSnapshot {
JournalSnapshot {
run_id: run_id.to_string(),
thread_id: format!("thread:{run_id}"),
events,
artifacts: BTreeMap::new(),
artifact_refs: BTreeMap::new(),
head_hash: String::new(),
}
}
fn event(run_id: &str, seq: u64, kind: RunEventKind, parent: Option<&str>) -> RunEvent {
RunEvent {
id: format!("{run_id}:{seq}"),
run_id: run_id.to_string(),
thread_id: format!("thread:{run_id}"),
node_id: None,
seq,
kind,
effect: Effect::Pure,
input: None,
output: Some(PayloadRef::inline(json!({"seq": seq}))),
latency_ms: None,
tokens: None,
cost_usd: None,
status: EventStatus::Ok,
parent: parent.map(str::to_string),
recorded_at: chrono::DateTime::from_timestamp_millis(1_800_000_000_000).unwrap(),
}
}
fn stitched_snapshots() -> (JournalSnapshot, JournalSnapshot) {
let coordination = snapshot(
"coordination:acme:c1",
vec![
event(
"coordination:acme:c1",
1,
RunEventKind::CoordinationStart,
None,
),
event(
"coordination:acme:c1",
2,
RunEventKind::MailboxSend,
Some("coordination:acme:c1:1"),
),
event(
"coordination:acme:c1",
3,
RunEventKind::MailboxReceive,
Some("coordination:acme:c1:2"),
),
event(
"coordination:acme:c1",
4,
RunEventKind::CoordinationEnd,
Some("coordination:acme:c1:1"),
),
],
);
let member = snapshot(
"run:member-a",
vec![
event(
"run:member-a",
1,
RunEventKind::SuperStepStart,
Some("coordination:acme:c1:2"),
),
event(
"run:member-a",
2,
RunEventKind::ModelCall,
Some("run:member-a:1"),
),
],
);
(coordination, member)
}
#[test]
fn assembles_one_connected_tree_across_journals() {
let (coordination, member) = stitched_snapshots();
let trace = TeamTrace::assemble(&[coordination, member]);
assert!(trace.is_connected());
assert_eq!(trace.roots, vec!["coordination:acme:c1:1".to_string()]);
assert_eq!(
trace.run_ids,
vec![
"coordination:acme:c1".to_string(),
"run:member-a".to_string()
]
);
let depth = |id: &str| trace.node(id).and_then(|n| n.depth);
assert_eq!(depth("coordination:acme:c1:1"), Some(0));
assert_eq!(depth("coordination:acme:c1:2"), Some(1));
assert_eq!(depth("coordination:acme:c1:3"), Some(2));
assert_eq!(depth("coordination:acme:c1:4"), Some(1));
assert_eq!(depth("run:member-a:1"), Some(2));
assert_eq!(depth("run:member-a:2"), Some(3));
let send = trace.node("coordination:acme:c1:2").unwrap();
assert_eq!(
send.children,
vec![
"coordination:acme:c1:3".to_string(),
"run:member-a:1".to_string()
]
);
}
#[test]
fn assembly_is_deterministic_under_snapshot_order() {
let (coordination, member) = stitched_snapshots();
let forward = TeamTrace::assemble(&[coordination.clone(), member.clone()]);
let reversed = TeamTrace::assemble(&[member, coordination]);
assert_eq!(forward, reversed);
assert_eq!(
serde_json::to_string(&forward).unwrap(),
serde_json::to_string(&reversed).unwrap()
);
}
#[test]
fn parent_outside_the_assembled_set_is_a_root() {
let (_, member) = stitched_snapshots();
let trace = TeamTrace::assemble(&[member]);
assert!(trace.is_connected());
assert_eq!(trace.roots, vec!["run:member-a:1".to_string()]);
let root = trace.node("run:member-a:1").unwrap();
assert_eq!(root.parent.as_deref(), Some("coordination:acme:c1:2"));
assert_eq!(root.depth, Some(0));
}
#[test]
fn two_roots_are_not_connected() {
let a = snapshot(
"run:a",
vec![event("run:a", 1, RunEventKind::SuperStepStart, None)],
);
let b = snapshot(
"run:b",
vec![event("run:b", 1, RunEventKind::SuperStepStart, None)],
);
let trace = TeamTrace::assemble(&[a, b]);
assert!(!trace.is_connected());
assert_eq!(trace.roots.len(), 2);
}
#[test]
fn parent_cycle_neither_hangs_nor_connects() {
let cycled = snapshot(
"run:a",
vec![
event("run:a", 1, RunEventKind::SuperStepStart, Some("run:a:2")),
event("run:a", 2, RunEventKind::ModelCall, Some("run:a:1")),
],
);
let trace = TeamTrace::assemble(&[cycled]);
assert!(trace.roots.is_empty());
assert!(trace.nodes.iter().all(|node| node.depth.is_none()));
assert!(!trace.is_connected());
}
#[test]
fn child_sorting_uses_seq_not_lexical_id_order() {
let snap = snapshot(
"run:a",
vec![
event("run:a", 1, RunEventKind::SuperStepStart, None),
event("run:a", 2, RunEventKind::ModelCall, Some("run:a:1")),
event("run:a", 10, RunEventKind::ModelCall, Some("run:a:1")),
],
);
let trace = TeamTrace::assemble(&[snap]);
let root = trace.node("run:a:1").unwrap();
assert_eq!(
root.children,
vec!["run:a:2".to_string(), "run:a:10".to_string()]
);
}
#[test]
fn empty_assembly_is_empty_and_not_connected() {
let trace = TeamTrace::assemble(&[]);
assert!(trace.run_ids.is_empty());
assert!(trace.roots.is_empty());
assert!(trace.nodes.is_empty());
assert!(!trace.is_connected());
}
#[test]
fn duplicate_journals_collapse_to_one_fact() {
let (coordination, _) = stitched_snapshots();
let trace = TeamTrace::assemble(&[coordination.clone(), coordination]);
assert_eq!(trace.nodes.len(), 4);
assert!(trace.is_connected());
}
}