car-memgine 0.48.0

//! Per-layer fingerprinting of an assembled context, and the diff between two.
//!
//! # What this is for
//!
//! CLAUDE.md carries a standing instruction about StateBench results:
//!
//! > Before believing any per-track delta, check whether the change even alters
//! > that track's assembled context — dump it both ways and diff. If the
//! > context is identical the delta is noise, full stop, and that check costs
//! > no API calls.
//!
//! That instruction exists because the per-track noise floor is **±15pp**. Each
//! track carries ~15 queries, so one query is ~6.7pp and a 3-run mean still
//! moves enormously. It was measured directly: between two sweeps whose
//! assembled context was byte-identical on a track, `scope_permission` moved
//! 85.4% → 70.8%. Nothing in the code changed that track's input, and the
//! number moved 14.6 points.
//!
//! So the question "did my change alter this context at all?" is worth more
//! than another eval run, and it is answerable offline. This module answers it,
//! and answers the follow-up — *which layer* changed — so a real delta can be
//! attributed instead of guessed at.
//!
//! # What this is NOT
//!
//! Not a cache, and not a speedup. The Shepherd proposal's item 2 also
//! describes a `(component-hash, inputs-hash)` replay cache that reuses
//! unaffected work across runs; that needs `assemble_context` decomposed into
//! components with declared inputs, and it is explicitly still open. This is
//! the interpretability half, which needs no refactor and no eval budget.
//!
//! Fingerprints are equality evidence, not similarity evidence. Two contexts
//! whose layer hashes match are byte-identical in that layer; two that differ
//! differ *somehow*, and the byte/line counts say how much, not what. Read the
//! text when you need to know what.
//!
//! # Determinism
//!
//! SHA-256 over the layer's exact bytes, so a fingerprint is comparable across
//! runs, machines, and CAR versions. Deliberately not `DefaultHasher`, whose
//! output is not stable across Rust releases — a fingerprint you cannot compare
//! to yesterday's is not a fingerprint.

use serde::{Deserialize, Serialize};
use sha2::{Digest, Sha256};
use std::collections::BTreeMap;

/// One `## `-delimited layer of an assembled context.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub struct LayerFingerprint {
    /// SHA-256 of the layer's body, hex, first 16 chars — enough to make a
    /// collision irrelevant for equality checking while staying readable in a
    /// log line.
    pub hash: String,
    /// Byte length of the layer body (excluding its `## ` header line).
    pub bytes: usize,
    /// Line count of the layer body — the unit a human scans a context in.
    pub lines: usize,
}

/// A fingerprint of one assembled context, layer by layer.
///
/// `#[non_exhaustive]`: this is a diagnostic record that will grow fields
/// (per-layer token estimates are the obvious next one), and it should not
/// break a consumer when it does — the lesson from Parslee-ai/car#855.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub struct ContextFingerprint {
    /// Layer name (the `## ` header text) → its fingerprint. `BTreeMap` so
    /// serialization and iteration are deterministic, which matters when the
    /// output is being diffed.
    pub layers: BTreeMap<String, LayerFingerprint>,
    /// Layer names in the order the assembler emitted them. The order is
    /// itself meaningful — CAR assembles relevance-ascending, most relevant
    /// last for recency attention — so a reordering is a real change that
    /// per-layer hashes alone would miss.
    pub order: Vec<String>,
    /// SHA-256 of the whole context, hex, first 16 chars.
    pub full_hash: String,
    /// Total byte length of the context.
    pub total_bytes: usize,
}

/// What changed between two fingerprints.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub struct ContextDiff {
    /// True when the two contexts are byte-identical. **This is the verdict
    /// that matters**: if it holds for a track, any observed metric delta on
    /// that track is noise, and no eval run will tell you otherwise.
    pub identical: bool,
    /// Layers present in both, with different content.
    pub changed: Vec<LayerDelta>,
    /// Layers only in the "after" context.
    pub added: Vec<String>,
    /// Layers only in the "before" context.
    pub removed: Vec<String>,
    /// True when both contexts have the same layers but in a different order.
    pub reordered: bool,
    /// Total byte change, after − before.
    pub byte_delta: i64,
}

/// One layer that differs between two contexts.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub struct LayerDelta {
    pub layer: String,
    pub before_bytes: usize,
    pub after_bytes: usize,
    pub before_lines: usize,
    pub after_lines: usize,
}

fn short_sha(bytes: &[u8]) -> String {
    let digest = Sha256::digest(bytes);
    hex_of(&digest[..8])
}

fn hex_of(bytes: &[u8]) -> String {
    bytes.iter().map(|b| format!("{b:02x}")).collect()
}

/// Fingerprint an assembled context, splitting it on `## ` headers.
///
/// Content before the first header (the assembler emits none today, but a
/// caller may prepend) is recorded under the layer name `"(preamble)"` rather
/// than dropped — silently ignoring bytes would make `identical` lie, which is
/// the one thing this must never do.
///
/// A duplicate header name is disambiguated as `"Name#2"`, `"Name#3"`, … Two
/// layers with the same name are a real possibility (a caller concatenating
/// contexts) and collapsing them would lose content from the hash.
pub fn fingerprint_context(context: &str) -> ContextFingerprint {
    let mut layers: BTreeMap<String, LayerFingerprint> = BTreeMap::new();
    let mut order: Vec<String> = Vec::new();
    let mut seen: BTreeMap<String, usize> = BTreeMap::new();

    let mut current: Option<String> = None;
    let mut body = String::new();

    let flush = |name: Option<String>,
                 body: &mut String,
                 layers: &mut BTreeMap<String, LayerFingerprint>,
                 order: &mut Vec<String>,
                 seen: &mut BTreeMap<String, usize>| {
        let raw = match name {
            Some(n) => n,
            // Only record a preamble if it actually has content; an assembled
            // context normally starts with a header and would otherwise gain a
            // spurious empty layer.
            None if body.trim().is_empty() => return,
            None => "(preamble)".to_string(),
        };
        let count = seen.entry(raw.clone()).or_insert(0);
        *count += 1;
        let key = if *count == 1 {
            raw
        } else {
            format!("{raw}#{count}")
        };
        layers.insert(
            key.clone(),
            LayerFingerprint {
                hash: short_sha(body.as_bytes()),
                bytes: body.len(),
                lines: body.lines().count(),
            },
        );
        order.push(key);
        body.clear();
    };

    for line in context.lines() {
        if let Some(header) = line.strip_prefix("## ") {
            flush(
                current.take(),
                &mut body,
                &mut layers,
                &mut order,
                &mut seen,
            );
            current = Some(header.trim().to_string());
        } else {
            body.push_str(line);
            body.push('\n');
        }
    }
    flush(current, &mut body, &mut layers, &mut order, &mut seen);

    ContextFingerprint {
        layers,
        order,
        full_hash: short_sha(context.as_bytes()),
        total_bytes: context.len(),
    }
}

/// Compare two fingerprints — `before` and `after` an edit.
///
/// The result answers, in order of how much it should change your mind:
/// `identical` (any metric delta is noise), then `changed`/`added`/`removed`
/// (where to look), then the byte counts (how much).
pub fn diff(before: &ContextFingerprint, after: &ContextFingerprint) -> ContextDiff {
    let mut changed = Vec::new();
    let mut added = Vec::new();
    let mut removed = Vec::new();

    for (name, a) in &after.layers {
        match before.layers.get(name) {
            None => added.push(name.clone()),
            Some(b) if b.hash != a.hash => changed.push(LayerDelta {
                layer: name.clone(),
                before_bytes: b.bytes,
                after_bytes: a.bytes,
                before_lines: b.lines,
                after_lines: a.lines,
            }),
            Some(_) => {}
        }
    }
    for name in before.layers.keys() {
        if !after.layers.contains_key(name) {
            removed.push(name.clone());
        }
    }

    // Same layers, different sequence. Worth reporting separately: CAR
    // assembles relevance-ascending (most relevant last, for recency
    // attention), so order carries meaning that per-layer hashes cannot see.
    let reordered = before.order != after.order && added.is_empty() && removed.is_empty();

    ContextDiff {
        identical: before.full_hash == after.full_hash && before.total_bytes == after.total_bytes,
        changed,
        added,
        removed,
        reordered,
        byte_delta: after.total_bytes as i64 - before.total_bytes as i64,
    }
}

impl ContextDiff {
    /// One-line human summary, for an eval log where the full record would
    /// drown the result it is annotating.
    pub fn summary(&self) -> String {
        if self.identical {
            return "context identical — any metric delta here is noise".to_string();
        }
        let mut parts = Vec::new();
        if !self.changed.is_empty() {
            let names: Vec<&str> = self.changed.iter().map(|d| d.layer.as_str()).collect();
            parts.push(format!("changed: {}", names.join(", ")));
        }
        if !self.added.is_empty() {
            parts.push(format!("added: {}", self.added.join(", ")));
        }
        if !self.removed.is_empty() {
            parts.push(format!("removed: {}", self.removed.join(", ")));
        }
        if self.reordered {
            parts.push("layer order changed".to_string());
        }
        format!("{} ({:+} bytes)", parts.join("; "), self.byte_delta)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    const CTX: &str = "\
## Identity
You are CAR.

## Current Facts
- deploy target is fly.io
- the db is postgres

## Recent Context
user: what is the target?
";

    #[test]
    fn identical_contexts_are_reported_identical() {
        // The verdict the whole module exists to deliver: if this is true for a
        // track, no amount of re-running will make its delta mean anything.
        let d = diff(&fingerprint_context(CTX), &fingerprint_context(CTX));
        assert!(d.identical);
        assert!(d.changed.is_empty() && d.added.is_empty() && d.removed.is_empty());
        assert_eq!(d.byte_delta, 0);
        assert!(d.summary().contains("noise"));
    }

    #[test]
    fn a_change_is_localised_to_its_layer() {
        // The follow-up question: a real delta should be attributable, not
        // guessed at. Only Current Facts moves; Identity and Recent Context
        // must be reported unchanged or the attribution is worthless.
        let after = CTX.replace("the db is postgres", "the db is sqlite");
        let d = diff(&fingerprint_context(CTX), &fingerprint_context(&after));
        assert!(!d.identical);
        assert_eq!(d.changed.len(), 1, "{:?}", d.changed);
        assert_eq!(d.changed[0].layer, "Current Facts");
        assert!(d.added.is_empty() && d.removed.is_empty());
    }

    #[test]
    fn added_and_removed_layers_are_distinguished_from_edits() {
        // Appended with no extra newline: CTX already ends with one, and an
        // extra blank line would land in the PREVIOUS layer's body and show up
        // as a change there. That is correct behaviour — a stray newline is a
        // real byte the model sees, so `identical` must not hide it — but it
        // would make this test about whitespace instead of about layer
        // addition.
        let after = format!("{CTX}## Known Unknowns\n- unclear: the region\n");
        let d = diff(&fingerprint_context(CTX), &fingerprint_context(&after));
        assert_eq!(d.added, vec!["Known Unknowns".to_string()]);
        assert!(
            d.changed.is_empty(),
            "adding a layer must not perturb existing ones: {:?}",
            d.changed
        );

        let back = diff(&fingerprint_context(&after), &fingerprint_context(CTX));
        assert_eq!(back.removed, vec!["Known Unknowns".to_string()]);
        assert!(back.byte_delta < 0);
    }

    #[test]
    fn reordering_is_detected_even_though_every_layer_hash_matches() {
        // CAR assembles relevance-ascending — most relevant LAST, for recency
        // attention — so moving a layer changes what the model attends to even
        // when no byte of any layer changed. Per-layer hashes alone cannot see
        // this, which is why `order` is part of the fingerprint.
        let reordered = "\
## Current Facts
- deploy target is fly.io
- the db is postgres

## Identity
You are CAR.

## Recent Context
user: what is the target?
";
        let a = fingerprint_context(CTX);
        let b = fingerprint_context(reordered);
        assert_eq!(a.layers, b.layers, "every layer body is unchanged");
        let d = diff(&a, &b);
        assert!(!d.identical, "a reordered context is not identical");
        assert!(d.reordered);
        assert!(d.summary().contains("order"));
    }

    #[test]
    fn content_before_the_first_header_is_not_silently_dropped() {
        // `identical` must never lie. Bytes outside any `## ` section still
        // reach the model, so they have to reach the hash.
        let with_preamble = format!("a caller-prepended note\n{CTX}");
        let d = diff(
            &fingerprint_context(CTX),
            &fingerprint_context(&with_preamble),
        );
        assert!(!d.identical);
        assert_eq!(d.added, vec!["(preamble)".to_string()]);
    }

    #[test]
    fn duplicate_layer_names_do_not_collapse() {
        // Two layers with the same header (a caller concatenating contexts).
        // Collapsing them would drop content from the fingerprint and let
        // `identical` report true for two different contexts.
        let doubled = format!("{CTX}\n## Current Facts\n- a second block\n");
        let fp = fingerprint_context(&doubled);
        assert!(fp.layers.contains_key("Current Facts"));
        assert!(
            fp.layers.contains_key("Current Facts#2"),
            "second block must get its own entry: {:?}",
            fp.layers.keys().collect::<Vec<_>>()
        );
    }

    #[test]
    fn fingerprints_are_stable_across_calls() {
        // A fingerprint that is not reproducible cannot be compared to
        // yesterday's, which is the entire use case.
        assert_eq!(fingerprint_context(CTX), fingerprint_context(CTX));
    }

    #[test]
    fn empty_context_is_handled() {
        let fp = fingerprint_context("");
        assert!(fp.layers.is_empty());
        assert_eq!(fp.total_bytes, 0);
        assert!(diff(&fp, &fingerprint_context("")).identical);
    }
}