veerdiff 0.1.0

Semantic diff engine for LLM and agent execution traces — find exactly where two runs veer apart.
Documentation
//! Similarity metrics used to score how alike two steps (or two JSON values)
//! are. Alignment turns these `[0, 1]` scores into edit costs.
//!
//! Text similarity uses the Sørensen–Dice coefficient over character bigrams,
//! which is cheap (`O(n)`), tolerant of small edits, and — unlike raw edit
//! distance — naturally length-normalized. Structured (`args`) similarity is a
//! recursive walk over JSON that rewards matching shape and matching leaves.

use serde::{Deserialize, Serialize};
use serde_json::Value;
use std::collections::HashMap;

use crate::model::Step;

/// `1.0` for `true`, `0.0` for `false`.
#[inline]
fn b2f(b: bool) -> f64 {
    if b { 1.0 } else { 0.0 }
}

/// Relative importance of each comparable field when scoring two steps.
///
/// A field only contributes when it is present on at least one of the two
/// steps, so comparing two tool calls is driven by `name` + `args` while
/// comparing two messages is driven by `role` + `content`.
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct Weights {
    /// Weight of the `role` field (exact match).
    pub role: f64,
    /// Weight of the `name` field (fuzzy match).
    pub name: f64,
    /// Weight of the `content` field (fuzzy text match).
    pub content: f64,
    /// Weight of the `args` field (structural match).
    pub args: f64,
}

impl Default for Weights {
    fn default() -> Self {
        Weights {
            role: 1.0,
            name: 2.0,
            content: 3.0,
            args: 3.0,
        }
    }
}

/// Sørensen–Dice similarity of two strings over character bigrams, in `[0, 1]`.
///
/// Strings shorter than two characters have no bigrams, so they fall back to
/// exact equality. Two empty strings are considered identical.
pub fn text_similarity(a: &str, b: &str) -> f64 {
    if a == b {
        return 1.0;
    }
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    if a.len() < 2 || b.len() < 2 {
        // No bigrams to compare; we already know they are not exactly equal.
        return 0.0;
    }

    let mut counts: HashMap<(char, char), i32> = HashMap::with_capacity(a.len());
    for w in a.windows(2) {
        *counts.entry((w[0], w[1])).or_insert(0) += 1;
    }

    let mut intersection = 0usize;
    for w in b.windows(2) {
        let key = (w[0], w[1]);
        if let Some(c) = counts.get_mut(&key)
            && *c > 0
        {
            *c -= 1;
            intersection += 1;
        }
    }

    let total = (a.len() - 1) + (b.len() - 1);
    (2.0 * intersection as f64) / total as f64
}

/// Recursive structural similarity of two JSON values, in `[0, 1]`.
///
/// * `null`/`null`, equal booleans, and equal numbers score `1.0`.
/// * Strings use [`text_similarity`].
/// * Arrays are compared positionally and penalized for length differences.
/// * Objects are compared over the union of their keys; keys present on only
///   one side contribute `0`.
/// * Mismatched value *types* score `0.0`.
pub fn value_similarity(a: &Value, b: &Value) -> f64 {
    match (a, b) {
        (Value::Null, Value::Null) => 1.0,
        (Value::Bool(x), Value::Bool(y)) => b2f(x == y),
        (Value::Number(x), Value::Number(y)) => b2f(x == y),
        (Value::String(x), Value::String(y)) => text_similarity(x, y),
        (Value::Array(x), Value::Array(y)) => {
            if x.is_empty() && y.is_empty() {
                return 1.0;
            }
            let max = x.len().max(y.len());
            let common = x.len().min(y.len());
            let mut sum = 0.0;
            for i in 0..common {
                sum += value_similarity(&x[i], &y[i]);
            }
            sum / max as f64
        }
        (Value::Object(x), Value::Object(y)) => {
            if x.is_empty() && y.is_empty() {
                return 1.0;
            }
            let mut keys: Vec<&String> = x.keys().collect();
            for k in y.keys() {
                if !x.contains_key(k) {
                    keys.push(k);
                }
            }
            if keys.is_empty() {
                return 1.0;
            }
            let mut sum = 0.0;
            for k in &keys {
                // Keys present on only one side contribute 0.
                if let (Some(va), Some(vb)) = (x.get(*k), y.get(*k)) {
                    sum += value_similarity(va, vb);
                }
            }
            sum / keys.len() as f64
        }
        _ => 0.0,
    }
}

/// Similarity of two optional strings, treating "both absent" as not
/// applicable. Returns `None` when the field is absent on both sides.
fn opt_text(a: &Option<String>, b: &Option<String>) -> Option<f64> {
    match (a, b) {
        (None, None) => None,
        (Some(x), Some(y)) => Some(text_similarity(x, y)),
        _ => Some(0.0),
    }
}

fn opt_value(a: &Option<Value>, b: &Option<Value>) -> Option<f64> {
    match (a, b) {
        (None, None) => None,
        (Some(x), Some(y)) => Some(value_similarity(x, y)),
        _ => Some(0.0),
    }
}

fn opt_exact(a: &Option<String>, b: &Option<String>) -> Option<f64> {
    match (a, b) {
        (None, None) => None,
        (x, y) => Some(b2f(x == y)),
    }
}

/// Overall similarity of two steps in `[0, 1]`.
///
/// Steps of different [`kind`](crate::model::StepKind) are treated as
/// incomparable and score `0.0`. Otherwise the score is a weighted average over
/// the fields that are present on either side, using `weights`.
pub fn step_similarity(a: &Step, b: &Step, weights: &Weights) -> f64 {
    if a.kind != b.kind {
        return 0.0;
    }

    let mut total_weight = 0.0;
    let mut acc = 0.0;
    let mut add = |w: f64, s: Option<f64>| {
        if let Some(s) = s {
            total_weight += w;
            acc += w * s;
        }
    };

    add(weights.role, opt_exact(&a.role, &b.role));
    add(weights.name, opt_text(&a.name, &b.name));
    add(weights.content, opt_text(&a.content, &b.content));
    add(weights.args, opt_value(&a.args, &b.args));

    if total_weight == 0.0 {
        // Same kind, no comparable fields on either side (e.g. two bare
        // events): treat as identical.
        1.0
    } else {
        acc / total_weight
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::model::StepKind;
    use serde_json::json;

    #[test]
    fn identical_text_is_one_and_disjoint_is_zero() {
        assert_eq!(text_similarity("hello", "hello"), 1.0);
        assert_eq!(text_similarity("", ""), 1.0);
        assert_eq!(text_similarity("abcd", "wxyz"), 0.0);
    }

    #[test]
    fn near_text_scores_between_zero_and_one() {
        let s = text_similarity("get_weather", "get_weather_v2");
        assert!(s > 0.6 && s < 1.0, "unexpected similarity {s}");
    }

    #[test]
    fn single_char_strings_fall_back_to_equality() {
        assert_eq!(text_similarity("a", "a"), 1.0);
        assert_eq!(text_similarity("a", "b"), 0.0);
    }

    #[test]
    fn value_similarity_handles_nested_objects() {
        let a = json!({"city": "Paris", "units": "metric"});
        let b = json!({"city": "Paris", "units": "imperial"});
        let s = value_similarity(&a, &b);
        // One of two keys matches exactly; the other differs.
        assert!(s > 0.4 && s < 0.9, "unexpected {s}");

        assert_eq!(value_similarity(&json!(42), &json!(42)), 1.0);
        assert_eq!(value_similarity(&json!(42), &json!("42")), 0.0);
        assert_eq!(value_similarity(&json!({}), &json!({})), 1.0);
    }

    #[test]
    fn different_kinds_are_incomparable() {
        let m = Step::new(StepKind::Message).with_content("hi");
        let t = Step::new(StepKind::ToolCall).with_name("hi");
        assert_eq!(step_similarity(&m, &t, &Weights::default()), 0.0);
    }

    #[test]
    fn identical_tool_calls_score_one() {
        let a = Step::new(StepKind::ToolCall)
            .with_name("get_weather")
            .with_args(json!({"city": "Paris"}));
        let b = a.clone();
        assert_eq!(step_similarity(&a, &b, &Weights::default()), 1.0);
    }

    #[test]
    fn changed_arg_lowers_but_does_not_zero_similarity() {
        let a = Step::new(StepKind::ToolCall)
            .with_name("get_weather")
            .with_args(json!({"city": "Paris"}));
        let b = Step::new(StepKind::ToolCall)
            .with_name("get_weather")
            .with_args(json!({"city": "Berlin"}));
        let s = step_similarity(&a, &b, &Weights::default());
        // name matches (weight 2) but the arg value fully differs (weight 3):
        // (2·1 + 3·0) / 5 = 0.4 — clearly paired, clearly not identical.
        assert!((0.3..1.0).contains(&s), "unexpected {s}");
    }
}