car-memgine 0.48.0

//! Which steps of a completed trajectory left a trace in the final state.
//!
//! # The observation this comes from
//!
//! Shepherd (arXiv 2605.10913, Appendix D) reports that **68–82% of *passing*
//! agent trajectories admit a strictly shorter passing rerun** — mean 21.4 → 8.9
//! model calls on SWE-Bench Verified, and in the extreme an 80-step baseline
//! shortened to 7. A best-of-N=5 control rules out baseline variance. The first
//! solution an agent finds is mostly exploration it did not, in retrospect,
//! need.
//!
//! Counter-intuitively, the *stronger* worker's longer baselines compressed
//! **more** in absolute terms (12.5 vs 10.2 calls saved) — longer trajectories
//! carry more excisable wandering, not less.
//!
//! # What this module computes, and what it deliberately does not
//!
//! Shepherd's method reruns the worker from a restored scope at a chosen fork
//! step and counts a compression only when the rerun **passes the verifier in
//! strictly fewer calls**. CAR cannot do that: restoring a worker to the scope
//! at step *f* is proposal item 4, and the macOS primitives for it were measured
//! and found constrained (see `docs/proposals/shepherd-substrate-adoption.md`).
//! Without the rerun, "this trajectory compresses to N steps" is an
//! unfalsifiable claim, and this module does not make it.
//!
//! What it computes instead is falsifiable from data CAR already records:
//! **which actions left a trace in the final state**. Each `TraceEvent` carries
//! `state_after` as the *delta* that action produced (`None` when it produced
//! none), so a last-writer walk decides, per action, whether any key it wrote
//! survives to the end.
//!
//! That is a strictly weaker claim than Shepherd's, and the difference matters:
//!
//! * **"Left no trace" is not "was unnecessary."** An action whose write was
//!   later overwritten may still have been how the agent *learned* the value it
//!   finally wrote. `TraceEvent` records no per-action read set, so nothing here
//!   can distinguish a wasted write from a load-bearing intermediate one.
//! * **State is not the world.** An action can change no state and still have
//!   sent an email or charged a card. This sees `car_state`, not effects that
//!   escaped it — the same boundary `Reversibility` exists to describe.
//!
//! So read the output as *"these steps did not contribute to the final state"*,
//! which is worth knowing, and not as *"these steps could have been skipped"*,
//! which requires the rerun CAR cannot yet perform.
//!
//! # What it is for
//!
//! `distill::success_distillation_prompt` turns a trajectory into skills. Fed
//! the whole trajectory, it distils the wandering; fed
//! [`effective_events`], it distils the path that actually moved the state.
//! Whether the result generalises is the question Shepherd explicitly leaves
//! open — and CAR's skill graph already arbitrates it, since a distilled skill
//! carries success/fail counts and auto-degrades when
//! `fail_count > success_count + 2`.

use crate::distill::TraceEvent;
use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet};

/// Why an action is not part of the state-effective subsequence.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
#[non_exhaustive]
pub enum DropReason {
    /// The action failed. Its own state contribution, if any, is recorded but
    /// the action did not succeed.
    Failed,
    /// The action succeeded and produced no state delta at all
    /// (`state_after == None`). It may still have had effects outside
    /// `car_state` — see the module docs.
    NoStateEffect,
    /// Every key this action wrote was written again later, so none of its
    /// values survive to the final state. **Not** evidence the action was
    /// pointless: a later write may have been computed from this one.
    Superseded,
}

/// One action that left no trace in the final state.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub struct DroppedStep {
    /// Index into the `events` slice that was analysed.
    pub index: usize,
    pub action_id: Option<String>,
    pub tool: Option<String>,
    pub reason: DropReason,
    /// Keys this action wrote that were later overwritten. Empty for
    /// `NoStateEffect`.
    pub superseded_keys: Vec<String>,
}

/// The result of a last-writer analysis over one trajectory.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub struct Compression {
    /// Indices of actions with at least one surviving written key, in order.
    pub effective: Vec<usize>,
    /// Actions that left no trace, with why.
    pub dropped: Vec<DroppedStep>,
    /// Total actions considered (events with an `action_succeeded` or
    /// `action_failed` kind; context events are not actions and are ignored).
    pub total_actions: usize,
}

impl Compression {
    /// Fraction of actions that left a trace in the final state, in `0.0..=1.0`.
    /// An empty trajectory is `1.0` — nothing was dropped.
    pub fn effective_ratio(&self) -> f64 {
        if self.total_actions == 0 {
            return 1.0;
        }
        self.effective.len() as f64 / self.total_actions as f64
    }

    /// One-line summary for a log.
    pub fn summary(&self) -> String {
        format!(
            "{}/{} actions left a trace in final state ({:.0}%); dropped {} \
             (no-effect {}, superseded {}, failed {})",
            self.effective.len(),
            self.total_actions,
            self.effective_ratio() * 100.0,
            self.dropped.len(),
            self.count(DropReason::NoStateEffect),
            self.count(DropReason::Superseded),
            self.count(DropReason::Failed),
        )
    }

    fn count(&self, reason: DropReason) -> usize {
        self.dropped.iter().filter(|d| d.reason == reason).count()
    }
}

fn is_action(kind: &str) -> bool {
    matches!(
        kind,
        "action_succeeded" | "action_failed" | "action_rejected" | "policy_violation"
    )
}

/// Analyse which actions in a completed trajectory left a trace in the final
/// state.
///
/// Single forward pass to find the last writer of each key, then one pass to
/// classify. `O(events × keys-per-event)`, no allocation per key beyond the
/// last-writer map, and pure — the same trajectory always yields the same
/// answer, which is what lets a result be compared across runs.
pub fn analyze(events: &[TraceEvent]) -> Compression {
    // Last writer per key. A later write to the same key supersedes an earlier
    // one for the purposes of "what survives", regardless of value — writing
    // the same value twice still means the first write is not what the final
    // state holds.
    let mut last_writer: BTreeMap<&str, usize> = BTreeMap::new();
    for (i, ev) in events.iter().enumerate() {
        if !is_action(&ev.kind) {
            continue;
        }
        if let Some(delta) = &ev.state_after {
            for key in delta.keys() {
                last_writer.insert(key.as_str(), i);
            }
        }
    }

    let mut effective = Vec::new();
    let mut dropped = Vec::new();
    let mut total_actions = 0usize;

    for (i, ev) in events.iter().enumerate() {
        if !is_action(&ev.kind) {
            continue;
        }
        total_actions += 1;

        // A failed action is reported as failed even if it wrote something —
        // "this step failed" is the more useful fact about it, and lumping it
        // in with superseded writes would hide it.
        if ev.kind != "action_succeeded" {
            dropped.push(DroppedStep {
                index: i,
                action_id: ev.action_id.clone(),
                tool: ev.tool.clone(),
                reason: DropReason::Failed,
                superseded_keys: Vec::new(),
            });
            continue;
        }

        let Some(delta) = &ev.state_after else {
            dropped.push(DroppedStep {
                index: i,
                action_id: ev.action_id.clone(),
                tool: ev.tool.clone(),
                reason: DropReason::NoStateEffect,
                superseded_keys: Vec::new(),
            });
            continue;
        };

        let mut survives = false;
        let mut overwritten: BTreeSet<String> = BTreeSet::new();
        for key in delta.keys() {
            if last_writer.get(key.as_str()) == Some(&i) {
                survives = true;
            } else {
                overwritten.insert(key.clone());
            }
        }

        if survives {
            effective.push(i);
        } else {
            dropped.push(DroppedStep {
                index: i,
                action_id: ev.action_id.clone(),
                tool: ev.tool.clone(),
                reason: DropReason::Superseded,
                superseded_keys: overwritten.into_iter().collect(),
            });
        }
    }

    Compression {
        effective,
        dropped,
        total_actions,
    }
}

/// The state-effective subsequence, ready for
/// [`crate::distill::success_distillation_prompt`].
///
/// Distilling the whole trajectory distils the wandering too. Distilling this
/// distils the path that moved the state — subject to every caveat in the
/// module docs, most importantly that a dropped step may have been how the
/// agent learned what to write.
pub fn effective_events(events: &[TraceEvent]) -> Vec<&TraceEvent> {
    analyze(events)
        .effective
        .into_iter()
        .map(|i| &events[i])
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;
    use std::collections::HashMap;

    fn ev(kind: &str, id: &str, tool: &str, delta: Option<&[(&str, i64)]>) -> TraceEvent {
        TraceEvent {
            kind: kind.to_string(),
            action_id: Some(id.to_string()),
            tool: Some(tool.to_string()),
            data: json!({}),
            duration_ms: Some(1.0),
            state_before: None,
            state_after: delta.map(|kvs| {
                kvs.iter()
                    .map(|(k, v)| (k.to_string(), json!(v)))
                    .collect::<HashMap<String, serde_json::Value>>()
            }),
            reward: Some(if kind == "action_succeeded" { 1.0 } else { 0.0 }),
        }
    }

    #[test]
    fn a_superseded_write_does_not_survive() {
        // The core of the analysis: a1 writes `x`, a2 overwrites it. Only a2's
        // value is in the final state.
        let events = vec![
            ev("action_succeeded", "a1", "set", Some(&[("x", 1)])),
            ev("action_succeeded", "a2", "set", Some(&[("x", 2)])),
        ];
        let c = analyze(&events);
        assert_eq!(c.effective, vec![1]);
        assert_eq!(c.dropped.len(), 1);
        assert_eq!(c.dropped[0].reason, DropReason::Superseded);
        assert_eq!(c.dropped[0].superseded_keys, vec!["x".to_string()]);
    }

    #[test]
    fn a_partially_superseded_action_still_counts_as_effective() {
        // a1 writes x and y; only x is overwritten. y survives, so a1 DID
        // contribute to the final state and must not be dropped — dropping it
        // would lose y from a distilled skill.
        let events = vec![
            ev("action_succeeded", "a1", "set", Some(&[("x", 1), ("y", 9)])),
            ev("action_succeeded", "a2", "set", Some(&[("x", 2)])),
        ];
        let c = analyze(&events);
        assert_eq!(c.effective, vec![0, 1]);
        assert!(c.dropped.is_empty(), "{:?}", c.dropped);
    }

    #[test]
    fn an_action_with_no_state_delta_is_dropped_as_no_effect() {
        let events = vec![
            ev("action_succeeded", "a1", "search", None),
            ev("action_succeeded", "a2", "set", Some(&[("x", 1)])),
        ];
        let c = analyze(&events);
        assert_eq!(c.effective, vec![1]);
        assert_eq!(c.dropped[0].reason, DropReason::NoStateEffect);
        assert!(c.dropped[0].superseded_keys.is_empty());
    }

    #[test]
    fn a_failed_action_is_reported_as_failed_not_superseded() {
        // Even when it wrote something that was later overwritten: "this failed"
        // is the more useful fact, and folding it into Superseded would hide it.
        let events = vec![
            ev("action_failed", "a1", "deploy", Some(&[("x", 1)])),
            ev("action_succeeded", "a2", "deploy", Some(&[("x", 2)])),
        ];
        let c = analyze(&events);
        assert_eq!(c.effective, vec![1]);
        assert_eq!(c.dropped[0].reason, DropReason::Failed);
    }

    #[test]
    fn context_events_are_not_counted_as_actions() {
        // `state_changed` is a context event, not an action. Counting it would
        // inflate total_actions and understate the effective ratio.
        let mut ctx = ev("state_changed", "c1", "n/a", Some(&[("x", 1)]));
        ctx.action_id = None;
        let events = vec![ctx, ev("action_succeeded", "a1", "set", Some(&[("y", 1)]))];
        let c = analyze(&events);
        assert_eq!(c.total_actions, 1);
        assert_eq!(c.effective, vec![1]);
    }

    #[test]
    fn the_shepherd_shape_reproduces_a_long_exploratory_prefix() {
        // Shepherd's Appendix D shape: a passing trajectory whose prefix is
        // exploration. Eight searches that change nothing, three writes to the
        // same key, one final write that survives — 12 actions, 1 effective.
        let mut events: Vec<TraceEvent> = (0..8)
            .map(|i| ev("action_succeeded", &format!("s{i}"), "search", None))
            .collect();
        for i in 0..3 {
            events.push(ev(
                "action_succeeded",
                &format!("w{i}"),
                "set",
                Some(&[("answer", i)]),
            ));
        }
        events.push(ev(
            "action_succeeded",
            "final",
            "set",
            Some(&[("answer", 42)]),
        ));

        let c = analyze(&events);
        assert_eq!(c.total_actions, 12);
        assert_eq!(c.effective.len(), 1);
        assert_eq!(c.effective_ratio(), 1.0 / 12.0);
        assert_eq!(c.dropped.len(), 11);

        // And the effective subsequence is what distillation should consume.
        let eff = effective_events(&events);
        assert_eq!(eff.len(), 1);
        assert_eq!(eff[0].action_id.as_deref(), Some("final"));
    }

    #[test]
    fn a_fully_effective_trajectory_drops_nothing() {
        // The guard against an analysis that always finds something to cut.
        let events = vec![
            ev("action_succeeded", "a1", "set", Some(&[("x", 1)])),
            ev("action_succeeded", "a2", "set", Some(&[("y", 2)])),
            ev("action_succeeded", "a3", "set", Some(&[("z", 3)])),
        ];
        let c = analyze(&events);
        assert_eq!(c.effective, vec![0, 1, 2]);
        assert!(c.dropped.is_empty());
        assert_eq!(c.effective_ratio(), 1.0);
        assert!(c.summary().contains("3/3"));
    }

    #[test]
    fn empty_trajectory_is_vacuously_effective() {
        let c = analyze(&[]);
        assert_eq!(c.total_actions, 0);
        assert_eq!(c.effective_ratio(), 1.0);
        assert!(c.dropped.is_empty());
    }

    #[test]
    fn rewriting_the_same_value_still_supersedes() {
        // Supersession is about which write the final state holds, not about
        // whether the value differs. a1's write is not what is in the state.
        let events = vec![
            ev("action_succeeded", "a1", "set", Some(&[("x", 7)])),
            ev("action_succeeded", "a2", "set", Some(&[("x", 7)])),
        ];
        let c = analyze(&events);
        assert_eq!(c.effective, vec![1]);
        assert_eq!(c.dropped[0].reason, DropReason::Superseded);
    }

    #[test]
    fn analysis_is_deterministic() {
        let events = vec![
            ev("action_succeeded", "a1", "set", Some(&[("x", 1), ("y", 2)])),
            ev("action_succeeded", "a2", "set", Some(&[("x", 3)])),
            ev("action_failed", "a3", "deploy", None),
        ];
        assert_eq!(analyze(&events), analyze(&events));
    }
}