car-memgine 0.48.0

//! Structured context eviction — deterministic, budget-bounded (arXiv
//! 2606.11213, *Beyond Compaction: Structured Context Eviction for Long-Horizon
//! Agents*; with the safety guard from arXiv 2606.22528, *Governance Decay*).
//!
//! See `docs/proposals/context-eviction.md`. When the context window fills,
//! CAR's only lever today is semantic *summarization* (cluster → score →
//! summarize). CWL adds the cheaper first move: **eviction** — deterministically
//! drop low-value trajectory episodes whose effects are already persisted, while
//! preserving the user's turns and the active reasoning frontier. Governance
//! Decay adds the rule that makes it safe: constraints are **pinned** and never
//! evicted, so compaction can't silently erase an in-context safety constraint.
//!
//! Pure, LLM-free, deterministic — the papers' whole point, and CAR's. The
//! caller maps `car-memgine`'s live working set into [`ContextEpisode`]s; the
//! policy decides what to drop.

use serde::{Deserialize, Serialize};

/// The type of a trajectory episode, which sets its retention tier.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum EpisodeKind {
    /// A governance/safety constraint — pin-protected (Governance Decay).
    Constraint,
    /// A user turn — preserved longest (the task intent).
    UserTurn,
    /// The agent's own reasoning — the exploratory frontier.
    AgentReasoning,
    /// A tool/action result.
    ActionResult,
    /// An environment observation.
    Observation,
}

/// One typed episode of the agent's trajectory.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ContextEpisode {
    pub id: String,
    pub kind: EpisodeKind,
    /// Token cost of keeping this episode in context.
    #[serde(default)]
    pub tokens: u64,
    /// Whether this episode's effects are already persisted in the environment /
    /// memory — if so it's safe to drop (its information survives elsewhere).
    #[serde(default)]
    pub persisted: bool,
    /// Never evict (constraints, identity). The Governance-Decay guard.
    #[serde(default)]
    pub pinned: bool,
    /// Higher = more recent. The active-reasoning frontier is the high-recency
    /// tail; within a tier the oldest episodes are evicted first.
    #[serde(default)]
    pub recency: u64,
}

/// The eviction decision.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct EvictionPlan {
    /// Episode ids to evict, in the order they were chosen.
    pub evicted: Vec<String>,
    /// Tokens retained after eviction.
    pub retained_tokens: u64,
    /// Tokens consumed by the un-evictable pinned floor.
    pub pinned_tokens: u64,
    /// True when the retained set fits `budget`. False means even after evicting
    /// everything evictable the pinned/retained floor exceeds budget — the
    /// caller must fall back to summarization.
    pub within_budget: bool,
}

/// Eviction tier: lower evicts first. Pinned episodes get no tier (never
/// evicted). `None` = pinned/never-evict.
fn tier(e: &ContextEpisode) -> Option<u8> {
    if e.pinned || e.kind == EpisodeKind::Constraint {
        return None; // never evict — Governance-Decay guard
    }
    Some(match e.kind {
        EpisodeKind::ActionResult | EpisodeKind::Observation if e.persisted => 0,
        EpisodeKind::ActionResult | EpisodeKind::Observation => 1,
        EpisodeKind::AgentReasoning => 2,
        EpisodeKind::UserTurn => 3,
        EpisodeKind::Constraint => unreachable!("constraints are pinned above"),
    })
}

/// Plan a deterministic, budget-bounded eviction over typed episodes. Evicts the
/// lowest tier first, oldest-within-tier first, never a pinned episode, stopping
/// as soon as the retained tokens fit `budget`. Pure and deterministic.
pub fn plan_eviction(episodes: &[ContextEpisode], budget: u64) -> EvictionPlan {
    let total: u64 = episodes.iter().map(|e| e.tokens).sum();
    let pinned_tokens: u64 = episodes
        .iter()
        .filter(|e| tier(e).is_none())
        .map(|e| e.tokens)
        .sum();

    // Candidates ordered by eviction priority: tier ascending, then recency
    // ascending (oldest first), then id for a stable tie-break.
    let mut candidates: Vec<(&ContextEpisode, u8)> = episodes
        .iter()
        .filter_map(|e| tier(e).map(|t| (e, t)))
        .collect();
    candidates.sort_by(|a, b| {
        a.1.cmp(&b.1)
            .then(a.0.recency.cmp(&b.0.recency))
            .then(a.0.id.cmp(&b.0.id))
    });

    let mut retained = total;
    let mut evicted = Vec::new();
    for (e, _) in candidates {
        if retained <= budget {
            break;
        }
        evicted.push(e.id.clone());
        retained -= e.tokens;
    }

    EvictionPlan {
        evicted,
        retained_tokens: retained,
        pinned_tokens,
        within_budget: retained <= budget,
    }
}

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

    fn ep(
        id: &str,
        kind: EpisodeKind,
        tokens: u64,
        persisted: bool,
        recency: u64,
    ) -> ContextEpisode {
        ContextEpisode {
            id: id.into(),
            kind,
            tokens,
            persisted,
            pinned: false,
            recency,
        }
    }

    #[test]
    fn under_budget_evicts_nothing() {
        let eps = vec![ep("a", EpisodeKind::UserTurn, 10, false, 1)];
        let plan = plan_eviction(&eps, 100);
        assert!(plan.evicted.is_empty());
        assert!(plan.within_budget);
        assert_eq!(plan.retained_tokens, 10);
    }

    #[test]
    fn persisted_action_results_evicted_first() {
        // Over budget by exactly the persisted action result's tokens.
        let eps = vec![
            ep("user", EpisodeKind::UserTurn, 30, false, 5),
            ep("persisted_act", EpisodeKind::ActionResult, 40, true, 2),
            ep("reasoning", EpisodeKind::AgentReasoning, 20, false, 4),
        ];
        // total 90; budget 60 → must drop 30+. The persisted action (tier 0, 40t)
        // goes first → retained 50 ≤ 60, stop.
        let plan = plan_eviction(&eps, 60);
        assert_eq!(plan.evicted, vec!["persisted_act".to_string()]);
        assert!(plan.within_budget);
        assert_eq!(plan.retained_tokens, 50);
    }

    #[test]
    fn user_turns_kept_over_reasoning_and_actions() {
        let eps = vec![
            ep("user", EpisodeKind::UserTurn, 50, false, 9),
            ep("reasoning", EpisodeKind::AgentReasoning, 50, false, 8),
            ep("act", EpisodeKind::ActionResult, 50, false, 7),
        ];
        // total 150, budget 60 → evict tier1 act (50→100) then tier2 reasoning
        // (100→50). User turn (tier 3) survives.
        let plan = plan_eviction(&eps, 60);
        assert_eq!(
            plan.evicted,
            vec!["act".to_string(), "reasoning".to_string()]
        );
        assert_eq!(plan.retained_tokens, 50);
        assert!(plan.within_budget);
    }

    #[test]
    fn oldest_within_tier_evicted_first() {
        let eps = vec![
            ep("new_act", EpisodeKind::ActionResult, 30, true, 9),
            ep("old_act", EpisodeKind::ActionResult, 30, true, 1),
        ];
        // total 60, budget 40 → drop one persisted action; the older one first.
        let plan = plan_eviction(&eps, 40);
        assert_eq!(plan.evicted, vec!["old_act".to_string()]);
    }

    #[test]
    fn constraints_are_never_evicted() {
        let eps = vec![
            ep("c", EpisodeKind::Constraint, 80, false, 1),
            ep("act", EpisodeKind::ActionResult, 40, true, 2),
        ];
        // budget 10: even after evicting the action, the 80t constraint remains.
        let plan = plan_eviction(&eps, 10);
        assert_eq!(plan.evicted, vec!["act".to_string()]);
        assert_eq!(plan.pinned_tokens, 80);
        assert!(!plan.within_budget, "pinned floor exceeds budget");
        assert_eq!(plan.retained_tokens, 80);
    }

    #[test]
    fn explicit_pin_protects_any_kind() {
        let mut e = ep("act", EpisodeKind::ActionResult, 50, true, 1);
        e.pinned = true;
        let plan = plan_eviction(&[e], 10);
        assert!(plan.evicted.is_empty());
        assert_eq!(plan.pinned_tokens, 50);
        assert!(!plan.within_budget);
    }

    #[test]
    fn within_budget_false_when_floor_too_high_then_caller_summarizes() {
        // All user turns (tier 3, evictable) but budget below their sum after
        // dropping everything else — eviction still can't fit → summarize.
        let eps = vec![
            ep("u1", EpisodeKind::UserTurn, 60, false, 1),
            ep("u2", EpisodeKind::UserTurn, 60, false, 2),
        ];
        let plan = plan_eviction(&eps, 50);
        // Both user turns are evictable (tier 3); to fit 50 we drop one → 60 left,
        // still > 50, drop the other → 0. within_budget true (0 ≤ 50).
        assert!(plan.within_budget);
        assert_eq!(plan.evicted.len(), 2);
    }
}