use serde::Serialize;
use serde_json::Value;
use crate::config::Config;
use crate::model::{Step, Trace};
use crate::similarity::step_similarity;
#[derive(Clone, Debug, PartialEq, Serialize)]
#[serde(tag = "op", rename_all = "snake_case")]
pub enum Op {
Equal {
a: usize,
b: usize,
},
Change {
a: usize,
b: usize,
similarity: f64,
fields: Vec<FieldDiff>,
},
Insert {
b: usize,
},
Delete {
a: usize,
},
}
impl Op {
pub fn is_equal(&self) -> bool {
matches!(self, Op::Equal { .. })
}
}
#[derive(Clone, Debug, PartialEq, Serialize)]
pub struct FieldDiff {
pub path: String,
#[serde(flatten)]
pub change: Change,
}
#[derive(Clone, Debug, PartialEq, Serialize)]
#[serde(tag = "change", rename_all = "snake_case")]
pub enum Change {
Added {
value: String,
},
Removed {
value: String,
},
Modified {
old: String,
new: String,
#[serde(skip_serializing_if = "Option::is_none")]
inline: Option<Vec<Inline>>,
},
}
#[derive(Clone, Debug, PartialEq, Serialize)]
#[serde(tag = "t", content = "v", rename_all = "snake_case")]
pub enum Inline {
Equal(String),
Insert(String),
Delete(String),
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize)]
pub struct Stats {
pub equal: usize,
pub changed: usize,
pub inserted: usize,
pub deleted: usize,
}
#[derive(Clone, Debug, PartialEq, Serialize)]
pub struct Diff {
pub ops: Vec<Op>,
pub similarity: f64,
pub first_divergence: Option<usize>,
pub stats: Stats,
}
impl Diff {
pub fn is_identical(&self) -> bool {
self.first_divergence.is_none()
}
}
#[derive(Clone, Copy, PartialEq)]
enum Move {
Diag, Up, Left, }
const INF: f64 = f64::INFINITY;
pub fn align(a: &Trace, b: &Trace, cfg: &Config) -> Diff {
let n = a.steps.len();
let m = b.steps.len();
let idx = |i: usize, j: usize| i * (m + 1) + j;
let mut cost = vec![0.0f64; (n + 1) * (m + 1)];
let mut back = vec![Move::Diag; (n + 1) * (m + 1)];
for i in 1..=n {
cost[idx(i, 0)] = i as f64;
back[idx(i, 0)] = Move::Up;
}
for j in 1..=m {
cost[idx(0, j)] = j as f64;
back[idx(0, j)] = Move::Left;
}
for i in 1..=n {
for j in 1..=m {
let sim = step_similarity(&a.steps[i - 1], &b.steps[j - 1], &cfg.weights);
let sub = if sim >= cfg.align_floor {
cost[idx(i - 1, j - 1)] + (1.0 - sim)
} else {
INF
};
let del = cost[idx(i - 1, j)] + 1.0;
let ins = cost[idx(i, j - 1)] + 1.0;
let (best, mv) = if sub <= del && sub <= ins {
(sub, Move::Diag)
} else if del <= ins {
(del, Move::Up)
} else {
(ins, Move::Left)
};
cost[idx(i, j)] = best;
back[idx(i, j)] = mv;
}
}
let mut ops = Vec::new();
let (mut i, mut j) = (n, m);
while i > 0 || j > 0 {
match back[idx(i, j)] {
Move::Diag if i > 0 && j > 0 => {
let (sa, sb) = (&a.steps[i - 1], &b.steps[j - 1]);
let sim = step_similarity(sa, sb, &cfg.weights);
if sim >= cfg.equal_threshold && sa.meta == sb.meta {
ops.push(Op::Equal { a: i - 1, b: j - 1 });
} else {
ops.push(Op::Change {
a: i - 1,
b: j - 1,
similarity: sim,
fields: field_diffs(sa, sb),
});
}
i -= 1;
j -= 1;
}
Move::Up if i > 0 => {
ops.push(Op::Delete { a: i - 1 });
i -= 1;
}
Move::Left if j > 0 => {
ops.push(Op::Insert { b: j - 1 });
j -= 1;
}
_ if i > 0 => {
ops.push(Op::Delete { a: i - 1 });
i -= 1;
}
_ => {
ops.push(Op::Insert { b: j - 1 });
j -= 1;
}
}
}
ops.reverse();
let mut stats = Stats::default();
let mut first_divergence = None;
for (k, op) in ops.iter().enumerate() {
match op {
Op::Equal { .. } => stats.equal += 1,
Op::Change { .. } => stats.changed += 1,
Op::Insert { .. } => stats.inserted += 1,
Op::Delete { .. } => stats.deleted += 1,
}
if first_divergence.is_none() && !op.is_equal() {
first_divergence = Some(k);
}
}
let total = (n + m) as f64;
let similarity = if total == 0.0 {
1.0
} else {
(1.0 - cost[idx(n, m)] / total).clamp(0.0, 1.0)
};
Diff {
ops,
similarity,
first_divergence,
stats,
}
}
fn render(v: &Value) -> String {
match v {
Value::String(s) => s.clone(),
other => other.to_string(),
}
}
fn field_diffs(a: &Step, b: &Step) -> Vec<FieldDiff> {
let mut out = Vec::new();
diff_opt_text("role", &a.role, &b.role, false, &mut out);
diff_opt_text("name", &a.name, &b.name, true, &mut out);
diff_opt_text("content", &a.content, &b.content, true, &mut out);
match (&a.args, &b.args) {
(None, None) => {}
(Some(x), None) => out.push(FieldDiff {
path: "args".into(),
change: Change::Removed { value: render(x) },
}),
(None, Some(y)) => out.push(FieldDiff {
path: "args".into(),
change: Change::Added { value: render(y) },
}),
(Some(x), Some(y)) => diff_value("args", x, y, &mut out),
}
for key in union_keys(a, b) {
let path = format!("meta.{key}");
match (a.meta.get(&key), b.meta.get(&key)) {
(Some(x), Some(y)) if x != y => diff_value(&path, x, y, &mut out),
(Some(x), None) => out.push(FieldDiff {
path,
change: Change::Removed { value: render(x) },
}),
(None, Some(y)) => out.push(FieldDiff {
path,
change: Change::Added { value: render(y) },
}),
_ => {}
}
}
out
}
fn union_keys(a: &Step, b: &Step) -> Vec<String> {
let mut keys: Vec<String> = a.meta.keys().cloned().collect();
for k in b.meta.keys() {
if !a.meta.contains_key(k) {
keys.push(k.clone());
}
}
keys
}
fn diff_opt_text(
path: &str,
a: &Option<String>,
b: &Option<String>,
inline: bool,
out: &mut Vec<FieldDiff>,
) {
match (a, b) {
(Some(x), Some(y)) if x != y => out.push(FieldDiff {
path: path.into(),
change: Change::Modified {
old: x.clone(),
new: y.clone(),
inline: if inline {
Some(inline_diff(x, y))
} else {
None
},
},
}),
(Some(x), None) => out.push(FieldDiff {
path: path.into(),
change: Change::Removed { value: x.clone() },
}),
(None, Some(y)) => out.push(FieldDiff {
path: path.into(),
change: Change::Added { value: y.clone() },
}),
_ => {}
}
}
fn diff_value(path: &str, a: &Value, b: &Value, out: &mut Vec<FieldDiff>) {
match (a, b) {
(Value::Object(x), Value::Object(y)) => {
let mut keys: Vec<&String> = x.keys().collect();
for k in y.keys() {
if !x.contains_key(k) {
keys.push(k);
}
}
for k in keys {
let child = format!("{path}.{k}");
match (x.get(k), y.get(k)) {
(Some(va), Some(vb)) if va != vb => diff_value(&child, va, vb, out),
(Some(va), None) => out.push(FieldDiff {
path: child,
change: Change::Removed { value: render(va) },
}),
(None, Some(vb)) => out.push(FieldDiff {
path: child,
change: Change::Added { value: render(vb) },
}),
_ => {}
}
}
}
(Value::Array(x), Value::Array(y)) => {
let max = x.len().max(y.len());
for k in 0..max {
let child = format!("{path}[{k}]");
match (x.get(k), y.get(k)) {
(Some(va), Some(vb)) if va != vb => diff_value(&child, va, vb, out),
(Some(va), None) => out.push(FieldDiff {
path: child,
change: Change::Removed { value: render(va) },
}),
(None, Some(vb)) => out.push(FieldDiff {
path: child,
change: Change::Added { value: render(vb) },
}),
_ => {}
}
}
}
_ if a != b => {
let inline = match (a, b) {
(Value::String(x), Value::String(y)) => Some(inline_diff(x, y)),
_ => None,
};
out.push(FieldDiff {
path: path.into(),
change: Change::Modified {
old: render(a),
new: render(b),
inline,
},
});
}
_ => {}
}
}
pub fn inline_diff(a: &str, b: &str) -> Vec<Inline> {
let at: Vec<&str> = a.split_whitespace().collect();
let bt: Vec<&str> = b.split_whitespace().collect();
let (n, m) = (at.len(), bt.len());
let mut lcs = vec![0u32; (n + 1) * (m + 1)];
let at_idx = |i: usize, j: usize| i * (m + 1) + j;
for i in (0..n).rev() {
for j in (0..m).rev() {
lcs[at_idx(i, j)] = if at[i] == bt[j] {
lcs[at_idx(i + 1, j + 1)] + 1
} else {
lcs[at_idx(i + 1, j)].max(lcs[at_idx(i, j + 1)])
};
}
}
let mut out = Vec::new();
let (mut i, mut j) = (0, 0);
while i < n && j < m {
if at[i] == bt[j] {
out.push(Inline::Equal(at[i].to_string()));
i += 1;
j += 1;
} else if lcs[at_idx(i + 1, j)] >= lcs[at_idx(i, j + 1)] {
out.push(Inline::Delete(at[i].to_string()));
i += 1;
} else {
out.push(Inline::Insert(bt[j].to_string()));
j += 1;
}
}
while i < n {
out.push(Inline::Delete(at[i].to_string()));
i += 1;
}
while j < m {
out.push(Inline::Insert(bt[j].to_string()));
j += 1;
}
out
}
#[cfg(test)]
mod tests {
use super::*;
use crate::model::StepKind;
use serde_json::json;
fn msg(role: &str, content: &str) -> Step {
Step::new(StepKind::Message)
.with_role(role)
.with_content(content)
}
#[test]
fn identical_traces_are_all_equal() {
let t = Trace::from_steps(vec![msg("user", "hi"), msg("assistant", "hello")]);
let d = align(&t, &t, &Config::default());
assert!(d.is_identical());
assert_eq!(d.similarity, 1.0);
assert_eq!(d.stats.equal, 2);
}
#[test]
fn inserted_step_is_detected() {
let a = Trace::from_steps(vec![msg("user", "hi")]);
let b = Trace::from_steps(vec![msg("user", "hi"), msg("assistant", "hello")]);
let d = align(&a, &b, &Config::default());
assert_eq!(d.stats.inserted, 1);
assert_eq!(d.stats.equal, 1);
assert_eq!(d.first_divergence, Some(1));
}
#[test]
fn changed_tool_arg_is_a_change_not_a_replace() {
let a = Trace::from_steps(vec![
Step::new(StepKind::ToolCall)
.with_name("get_weather")
.with_args(json!({"city": "Paris"})),
]);
let b = Trace::from_steps(vec![
Step::new(StepKind::ToolCall)
.with_name("get_weather")
.with_args(json!({"city": "Berlin"})),
]);
let d = align(&a, &b, &Config::default());
assert_eq!(d.stats.changed, 1);
assert_eq!(d.stats.inserted, 0);
assert_eq!(d.stats.deleted, 0);
let Op::Change { fields, .. } = &d.ops[0] else {
panic!("expected change, got {:?}", d.ops[0]);
};
assert_eq!(fields.len(), 1);
assert_eq!(fields[0].path, "args.city");
}
#[test]
fn dissimilar_steps_become_delete_plus_insert() {
let a = Trace::from_steps(vec![msg("user", "the quick brown fox")]);
let b = Trace::from_steps(vec![
Step::new(StepKind::ToolCall)
.with_name("unrelated")
.with_args(json!({"x": 1})),
]);
let d = align(&a, &b, &Config::default());
assert_eq!(d.stats.deleted, 1);
assert_eq!(d.stats.inserted, 1);
assert_eq!(d.stats.changed, 0);
}
#[test]
fn inline_diff_marks_word_changes() {
let d = inline_diff("the quick brown fox", "the slow brown fox");
assert!(d.contains(&Inline::Delete("quick".into())));
assert!(d.contains(&Inline::Insert("slow".into())));
assert!(d.contains(&Inline::Equal("brown".into())));
}
}