veerdiff 0.1.0

Semantic diff engine for LLM and agent execution traces — find exactly where two runs veer apart.
Documentation
//! Normalization: deterministic transformations applied to a [`Trace`] before
//! it is diffed.
//!
//! Two runs of the same agent are rarely byte-identical even when they are
//! *behaviourally* identical: request ids change, timestamps advance, JSON keys
//! come back in a different order, whitespace drifts. Normalization removes that
//! noise so alignment compares meaning, not incidental formatting.
//!
//! The built-in maskers ([`Mask`]) are small hand-written scanners — no regular
//! expression engine is pulled in for the default build. Custom user-supplied
//! patterns are available behind the optional `regex` feature.

use serde::{Deserialize, Serialize};
use serde_json::Value;

use crate::model::{Map, Trace};

mod scan;

/// A built-in masker that replaces volatile substrings with a stable
/// placeholder (e.g. every UUID becomes `<uuid>`).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Mask {
    /// RFC-4122 style UUIDs → `<uuid>`.
    Uuid,
    /// ISO-8601 date-times → `<timestamp>`.
    Timestamp,
    /// Email addresses → `<email>`.
    Email,
    /// Long hexadecimal runs (ids, hashes; ≥ 32 chars) → `<hex>`.
    HexHash,
    /// Numeric literals → `<num>`.
    Number,
}

impl Mask {
    fn apply(self, s: &str) -> String {
        match self {
            Mask::Uuid => scan::mask_uuid(s),
            Mask::Timestamp => scan::mask_timestamp(s),
            Mask::Email => scan::mask_email(s),
            Mask::HexHash => scan::mask_hex(s),
            Mask::Number => scan::mask_number(s),
        }
    }
}

/// Configuration for the normalization pass.
///
/// [`Normalizer::default`] is deliberately conservative: it canonicalizes JSON
/// key order and trims surrounding whitespace, both of which are pure noise, but
/// changes nothing else. Everything more opinionated is opt-in.
#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
#[serde(default)]
pub struct Normalizer {
    /// Recursively sort object keys inside `args` so key order does not matter.
    pub canonicalize_json: bool,
    /// Trim leading/trailing whitespace from `content`.
    pub trim_whitespace: bool,
    /// Collapse internal runs of whitespace in `content` to a single space.
    pub collapse_whitespace: bool,
    /// Lowercase `content` before comparison.
    pub lowercase: bool,
    /// Round floating-point numbers in `args` to this many decimal places.
    pub round_numbers: Option<u32>,
    /// Metadata keys (on steps and on the trace) to drop entirely.
    pub drop_meta: Vec<String>,
    /// Built-in maskers to apply to `content`, `name`, and string leaves of
    /// `args`.
    pub mask: Vec<Mask>,
    /// Also apply [`mask`](Self::mask) to string values inside `meta`.
    pub mask_meta: bool,
}

impl Default for Normalizer {
    fn default() -> Self {
        Normalizer {
            canonicalize_json: true,
            trim_whitespace: true,
            collapse_whitespace: false,
            lowercase: false,
            round_numbers: None,
            drop_meta: Vec::new(),
            mask: Vec::new(),
            mask_meta: false,
        }
    }
}

impl Normalizer {
    /// A normalizer that performs no transformation at all.
    pub fn identity() -> Self {
        Normalizer {
            canonicalize_json: false,
            trim_whitespace: false,
            ..Normalizer::default()
        }
    }

    /// Apply the configured transformations to a trace in place.
    pub fn apply(&self, trace: &mut Trace) {
        self.drop_from_meta(&mut trace.meta);
        for step in &mut trace.steps {
            if let Some(name) = &mut step.name {
                *name = self.mask_text(name);
            }
            if let Some(content) = &mut step.content {
                *content = self.transform_text(content);
            }
            if let Some(args) = &mut step.args {
                self.transform_value(args);
            }
            self.drop_from_meta(&mut step.meta);
            if self.mask_meta {
                mask_object_strings(&mut step.meta, &self.mask);
            }
        }
    }

    fn drop_from_meta(&self, meta: &mut Map) {
        for key in &self.drop_meta {
            meta.remove(key);
        }
    }

    fn transform_text(&self, s: &str) -> String {
        let mut out = s.to_string();
        if self.trim_whitespace {
            out = out.trim().to_string();
        }
        if self.collapse_whitespace {
            out = collapse_ws(&out);
        }
        if self.lowercase {
            out = out.to_lowercase();
        }
        for m in &self.mask {
            out = m.apply(&out);
        }
        out
    }

    /// Text transform without the whitespace rules (used for `name`, an
    /// identifier where interior whitespace is meaningful).
    fn mask_text(&self, s: &str) -> String {
        let mut out = s.to_string();
        for m in &self.mask {
            out = m.apply(&out);
        }
        out
    }

    fn transform_value(&self, v: &mut Value) {
        if let Some(n) = self.round_numbers {
            round_numbers(v, n);
        }
        if !self.mask.is_empty() {
            mask_value_strings(v, &self.mask);
        }
        if self.canonicalize_json {
            canonicalize(v);
        }
    }
}

/// Recursively sort object keys so that key order is not observable.
pub fn canonicalize(v: &mut Value) {
    match v {
        Value::Object(map) => {
            let mut entries: Vec<(String, Value)> = std::mem::take(map).into_iter().collect();
            entries.sort_by(|a, b| a.0.cmp(&b.0));
            for (k, mut val) in entries {
                canonicalize(&mut val);
                map.insert(k, val);
            }
        }
        Value::Array(items) => items.iter_mut().for_each(canonicalize),
        _ => {}
    }
}

fn round_numbers(v: &mut Value, ndigits: u32) {
    match v {
        Value::Number(n) => {
            if let Some(f) = n.as_f64()
                && !n.is_i64()
                && !n.is_u64()
                && let Some(rounded) = round_to(f, ndigits)
            {
                *v = rounded;
            }
        }
        Value::Array(items) => items.iter_mut().for_each(|x| round_numbers(x, ndigits)),
        Value::Object(map) => map.values_mut().for_each(|x| round_numbers(x, ndigits)),
        _ => {}
    }
}

fn round_to(f: f64, ndigits: u32) -> Option<Value> {
    let factor = 10f64.powi(ndigits as i32);
    let rounded = (f * factor).round() / factor;
    serde_json::Number::from_f64(rounded).map(Value::Number)
}

fn mask_value_strings(v: &mut Value, masks: &[Mask]) {
    match v {
        Value::String(s) => {
            let mut out = s.clone();
            for m in masks {
                out = m.apply(&out);
            }
            *s = out;
        }
        Value::Array(items) => items.iter_mut().for_each(|x| mask_value_strings(x, masks)),
        Value::Object(map) => mask_object_strings(map, masks),
        _ => {}
    }
}

fn mask_object_strings(map: &mut Map, masks: &[Mask]) {
    for val in map.values_mut() {
        mask_value_strings(val, masks);
    }
}

fn collapse_ws(s: &str) -> String {
    let mut out = String::with_capacity(s.len());
    let mut in_ws = false;
    for c in s.chars() {
        if c.is_whitespace() {
            if !in_ws {
                out.push(' ');
                in_ws = true;
            }
        } else {
            out.push(c);
            in_ws = false;
        }
    }
    out
}

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

    #[test]
    fn canonicalize_sorts_nested_keys() {
        let mut v = json!({"b": 1, "a": {"z": 2, "y": 3}});
        canonicalize(&mut v);
        let s = serde_json::to_string(&v).unwrap();
        assert_eq!(s, r#"{"a":{"y":3,"z":2},"b":1}"#);
    }

    #[test]
    fn default_normalizer_trims_and_canonicalizes_only() {
        let n = Normalizer::default();
        let mut trace = Trace::from_steps(vec![
            Step::new(StepKind::Message)
                .with_role("user")
                .with_content("  hello  "),
            Step::new(StepKind::ToolCall)
                .with_name("f")
                .with_args(json!({"b": 1, "a": 2})),
        ]);
        n.apply(&mut trace);
        assert_eq!(trace.steps[0].content.as_deref(), Some("hello"));
        assert_eq!(
            serde_json::to_string(trace.steps[1].args.as_ref().unwrap()).unwrap(),
            r#"{"a":2,"b":1}"#
        );
    }

    #[test]
    fn drop_meta_removes_volatile_keys() {
        let mut step = Step::new(StepKind::Message).with_content("x");
        step.meta.insert("id".into(), json!("abc"));
        step.meta.insert("keep".into(), json!(1));
        let mut trace = Trace::from_steps(vec![step]);
        let n = Normalizer {
            drop_meta: vec!["id".into()],
            ..Normalizer::default()
        };
        n.apply(&mut trace);
        assert!(!trace.steps[0].meta.contains_key("id"));
        assert!(trace.steps[0].meta.contains_key("keep"));
    }

    #[test]
    fn masking_replaces_volatile_substrings_in_content_and_args() {
        let n = Normalizer {
            mask: vec![Mask::Uuid, Mask::Timestamp],
            ..Normalizer::default()
        };
        let mut trace = Trace::from_steps(vec![
            Step::new(StepKind::Message)
                .with_content("run 550e8400-e29b-41d4-a716-446655440000 at 2024-01-02T03:04:05Z"),
            Step::new(StepKind::ToolCall)
                .with_name("f")
                .with_args(json!({"req": "550e8400-e29b-41d4-a716-446655440000"})),
        ]);
        n.apply(&mut trace);
        assert_eq!(
            trace.steps[0].content.as_deref(),
            Some("run <uuid> at <timestamp>")
        );
        assert_eq!(
            trace.steps[1].args.as_ref().unwrap()["req"],
            json!("<uuid>")
        );
    }

    #[test]
    fn round_numbers_applies_to_floats_only() {
        let n = Normalizer {
            round_numbers: Some(2),
            ..Normalizer::default()
        };
        let mut trace = Trace::from_steps(vec![
            Step::new(StepKind::ToolCall)
                .with_name("f")
                .with_args(json!({"temp": 0.126_789, "count": 7})),
        ]);
        n.apply(&mut trace);
        let args = trace.steps[0].args.as_ref().unwrap();
        assert_eq!(args["temp"], json!(0.13));
        assert_eq!(args["count"], json!(7));
    }
}