car_planner/

lib.rs

//! Proposal scoring and search for Common Agent Runtime.
//!
//! Sits between the model and car-engine: scores N candidate proposals using
//! static verification + cost estimation, picks the best, and provides fallback
//! ordering for replan scenarios.
//!
//! Inspired by MARS (budget-aware MCTS) — uses verify() + simulate() as the
//! evaluation function, not LLM calls. Pure Rust, zero inference cost.
//!
//! ## Usage
//!
//! ```rust,ignore
//! use car_planner::{Planner, PlannerConfig, ScoredProposal};
//!
//! let planner = Planner::new(PlannerConfig::default());
//! let candidates = vec![proposal_a, proposal_b, proposal_c];
//! let ranked = planner.rank(&candidates, Some(&state), Some(&tools));
//! let best = &ranked[0]; // highest score first
//! ```

use car_ir::ActionProposal;
use car_verify::VerifyResult;
use serde::Serialize;
use serde_json::Value;
use std::collections::{HashMap, HashSet};

/// Historical tool success rates computed from the trajectory store.
/// Pass to `rank_with_feedback()` to bias scoring based on past outcomes.
#[derive(Debug, Clone, Default)]
pub struct ToolFeedback {
    /// Per-tool success rate (0.0–1.0). Tools not in the map are assumed 0.5 (no data).
    pub tool_success_rates: HashMap<String, f64>,
    /// Per-tool `(succeeded, dispatched)` counts backing each rate, when the
    /// feedback came from [`ToolFeedback::dispatched_from_trajectories`].
    ///
    /// A rate is not self-describing: `1.0` from one observation and `1.0` from
    /// five hundred are the same number and very different evidence. Consumers
    /// that price risk on these rates need the sample size to say how much to
    /// trust them, so it travels alongside. Empty for feedback built by
    /// [`ToolFeedback::from_trajectories`], which does not track it.
    pub tool_dispatch_counts: HashMap<String, (u64, u64)>,
}

impl ToolFeedback {
    /// Compute **dispatch-conditional** tool feedback — `P(tool succeeds | the
    /// action was actually dispatched)`.
    ///
    /// This differs from [`ToolFeedback::from_trajectories`] in what lands in
    /// the denominator, and the difference is not cosmetic. That constructor
    /// counts *every* event carrying a tool name, including `action_rejected`
    /// (the validator or policy refused the action) and `action_skipped` (an
    /// upstream failure meant it never ran). Neither is evidence about the
    /// tool: nothing was dispatched, so the tool had no opportunity to fail.
    ///
    /// For scoring that conflation is defensible — a tool whose actions keep
    /// getting rejected genuinely is a worse bet, and that is the signal
    /// `rank_with_feedback` wants. For **Monte Carlo rollout** it is a
    /// double-count: `car_verify::simulate_monte_carlo` already models
    /// rejection structurally, deriving it from the dependency cascade, so a
    /// rate that has rejections baked in penalizes the tool twice and reports
    /// a plan as more fragile than the evidence supports.
    ///
    /// Rates are **Laplace-smoothed** — `(succeeded + 1) / (dispatched + 2)`,
    /// the posterior mean under a uniform prior. One success becomes 0.67
    /// rather than a categorical 1.0, while 100/100 becomes 0.99; evidence
    /// still dominates once there is any. This avoids the alternative of a
    /// hard minimum-sample cliff, where a tool's rate would lurch from the
    /// 0.5 default to 1.0 on crossing some arbitrary count. Raw counts are
    /// preserved in [`Self::tool_dispatch_counts`] for callers that want to
    /// smooth differently or report the underlying evidence.
    ///
    /// Tools that were never dispatched in the window are absent from the map
    /// entirely rather than present at 0.5 — "no evidence" and "evidence of a
    /// coin flip" are different claims, and the consumer applies its own
    /// default.
    pub fn dispatched_from_trajectories(trajectories: &[car_memgine::Trajectory]) -> Self {
        // (succeeded, dispatched). `dispatched` counts only outcomes where the
        // tool actually ran: succeeded or failed.
        let mut counts: HashMap<String, (u64, u64)> = HashMap::new();
        for traj in trajectories {
            for event in &traj.events {
                let Some(ref tool) = event.tool else { continue };
                let succeeded = match event.kind.as_str() {
                    "action_succeeded" => true,
                    "action_failed" => false,
                    // action_rejected / action_skipped / unknown: never
                    // dispatched, so not evidence about this tool.
                    _ => continue,
                };
                let entry = counts.entry(tool.clone()).or_default();
                entry.1 += 1;
                if succeeded {
                    entry.0 += 1;
                }
            }
        }

        let tool_success_rates = counts
            .iter()
            .map(|(tool, &(succeeded, dispatched))| {
                let smoothed = (succeeded as f64 + 1.0) / (dispatched as f64 + 2.0);
                (tool.clone(), smoothed)
            })
            .collect();

        Self {
            tool_success_rates,
            tool_dispatch_counts: counts,
        }
    }

    /// Compute tool feedback from a trajectory store.
    pub fn from_trajectories(trajectories: &[car_memgine::Trajectory]) -> Self {
        let mut tool_outcomes: HashMap<String, (u64, u64)> = HashMap::new(); // (success, total)
        for traj in trajectories {
            for event in &traj.events {
                if let Some(ref tool) = event.tool {
                    let entry = tool_outcomes.entry(tool.clone()).or_default();
                    entry.1 += 1; // total
                    if event.kind == "action_succeeded" {
                        entry.0 += 1; // success
                    }
                }
            }
        }

        let tool_success_rates = tool_outcomes
            .into_iter()
            .map(|(tool, (success, total))| {
                (
                    tool,
                    if total > 0 {
                        success as f64 / total as f64
                    } else {
                        0.5
                    },
                )
            })
            .collect();

        Self {
            tool_success_rates,
            tool_dispatch_counts: HashMap::new(),
        }
    }

    /// Get the success rate for a tool, defaulting to 0.5 (no data).
    pub fn rate(&self, tool: &str) -> f64 {
        self.tool_success_rates.get(tool).copied().unwrap_or(0.5)
    }

    /// Average success rate across all tools in a proposal.
    pub fn proposal_tool_confidence(&self, proposal: &ActionProposal) -> f64 {
        let tool_calls: Vec<&str> = proposal
            .actions
            .iter()
            .filter(|a| a.action_type == car_ir::ActionType::ToolCall)
            .filter_map(|a| a.tool.as_deref())
            .collect();

        if tool_calls.is_empty() {
            return 1.0; // no tool calls = no tool risk
        }

        let sum: f64 = tool_calls.iter().map(|t| self.rate(t)).sum();
        sum / tool_calls.len() as f64
    }
}

/// Rough token estimate for a proposal: serialized JSON length ÷ 4.
/// Matches the heuristic used elsewhere in the codebase
/// (see `MemNode::token_estimate`). Accurate enough for ranking; an
/// embedding-tokenizer-backed estimate could replace this later.
pub fn estimate_proposal_tokens(proposal: &ActionProposal) -> usize {
    serde_json::to_string(proposal)
        .map(|s| s.len() / 4)
        .unwrap_or_else(|_| proposal.actions.len() * 32)
}

/// Configuration for proposal scoring.
#[derive(Debug, Clone)]
pub struct PlannerConfig {
    /// Weight for cost efficiency in the score (0.0–1.0).
    /// Higher = prefer cheaper proposals. Lower = prefer correctness.
    pub cost_weight: f64,
    /// Maximum actions before a proposal is penalized.
    pub action_budget: usize,
    /// Maximum tool calls before a proposal is penalized.
    pub tool_call_budget: usize,
    /// Validity penalty per write conflict detected in simulated state.
    pub conflict_penalty: f64,
    /// How much historical tool feedback influences the final score (0.0–1.0).
    /// Score = base * (1.0 - feedback_weight + feedback_weight * confidence).
    /// At 0.0 history is ignored; at 1.0 a tool with 0% success zeroes the score.
    pub feedback_weight: f64,
    /// Maximum estimated proposal tokens before a proposal is penalized.
    /// The estimate comes from the serialized proposal length (≈ 4 chars/token).
    /// Inspired by Meta-Harness (alphaXiv 2603.28052): context-token efficiency
    /// is a first-class optimization target, not an afterthought.
    pub token_budget: usize,
    /// Weight of the token-efficiency term within `cost_efficiency` (0.0–1.0).
    /// The remaining cost mass is split across actions/tools/parallelism.
    pub token_weight: f64,
    /// Weight of the **predicted-outcome** term in the final score (0.0–1.0),
    /// used only by [`Planner::rank_with_outcome`]. At `0.0` (the default)
    /// outcome scoring is off and ranking matches the static path exactly — so
    /// adding an `EffectModel` never changes behavior unless you opt in. Higher
    /// values let a plan that *reaches the goal* (per a verified Code World
    /// Model's prediction) outrank a cheaper plan that doesn't. This closes the
    /// "planning is outcome-blind" gap (Code World Models Slice 3 — see
    /// `docs/proposals/code-world-models.md`).
    pub outcome_weight: f64,
}

impl Default for PlannerConfig {
    fn default() -> Self {
        Self {
            cost_weight: 0.2,
            action_budget: 20,
            tool_call_budget: 10,
            conflict_penalty: 0.15,
            feedback_weight: 0.3,
            token_budget: 4000,
            token_weight: 0.25,
            outcome_weight: 0.0,
        }
    }
}

impl PlannerConfig {
    /// Create a PlannerConfig from a CostTarget.
    /// Maps soft targets into the planner's scoring parameters.
    /// Note: `target_duration_ms` is not used by the static planner (duration
    /// requires execution, which the planner avoids). It is reserved for
    /// future integration with runtime cost tracking.
    pub fn from_cost_target(target: &car_ir::CostTarget) -> Self {
        Self {
            cost_weight: target.cost_weight.clamp(0.0, 1.0),
            action_budget: target.target_actions as usize,
            tool_call_budget: target.target_tool_calls as usize,
            ..Default::default()
        }
    }
}

/// A proposal with its computed score and verification result.
#[derive(Debug, Clone, Serialize)]
pub struct ScoredProposal {
    /// Index into the original candidate list.
    pub index: usize,
    /// Overall score (0.0–1.0). Higher is better.
    pub score: f64,
    /// Validity score component (0.0–1.0).
    pub validity: f64,
    /// Cost efficiency score component (0.0–1.0).
    pub cost_efficiency: f64,
    /// Number of verification errors.
    pub error_count: usize,
    /// Number of verification warnings.
    pub warning_count: usize,
    /// Number of actions in the proposal.
    pub action_count: usize,
    /// Number of tool calls in the proposal.
    pub tool_call_count: usize,
    /// Number of DAG execution levels (parallelism depth).
    pub parallelism_levels: usize,
    /// Whether the proposal passed static verification.
    pub valid: bool,
    /// Number of state keys written by the simulated execution.
    pub state_keys_written: usize,
    /// Whether the proposal has write conflicts (multiple actions writing the same key).
    pub has_write_conflicts: bool,
    /// Historical tool confidence (0.0–1.0) based on trajectory feedback.
    /// 1.0 = all tools have perfect history, 0.5 = no data, <0.5 = tools frequently fail.
    pub historical_confidence: f64,
    /// Estimated prompt tokens required to describe this proposal (from
    /// serialized JSON length ÷ 4). Surfaces context cost so callers can
    /// trade quality for token budget.
    pub token_estimate: usize,
    /// `score / max(token_estimate, 1)` — quality per token.
    /// Lets callers rank by efficiency rather than raw quality when budget matters.
    pub quality_per_token: f64,
    /// Predicted-outcome value in `[0,1]` from a verified Code World Model +
    /// [`ValueFunction`], set by [`Planner::rank_with_outcome`]. `0.0` on the
    /// static paths (no model consulted) — so a value of `0.0` does not by
    /// itself mean "bad outcome", it means "outcome not scored".
    pub outcome_value: f64,
}

/// Proposal scorer and ranker.
pub struct Planner {
    config: PlannerConfig,
}

impl Planner {
    pub fn new(config: PlannerConfig) -> Self {
        Self { config }
    }

    /// Score a single proposal using static verification.
    pub fn score(
        &self,
        proposal: &ActionProposal,
        initial_state: Option<&HashMap<String, Value>>,
        registered_tools: Option<&HashSet<String>>,
    ) -> ScoredProposal {
        self.score_indexed(0, proposal, initial_state, registered_tools, None)
    }

    /// Score a single proposal, tracking its index in a candidate list.
    fn score_indexed(
        &self,
        index: usize,
        proposal: &ActionProposal,
        initial_state: Option<&HashMap<String, Value>>,
        registered_tools: Option<&HashSet<String>>,
        feedback: Option<&ToolFeedback>,
    ) -> ScoredProposal {
        let vr = car_verify::verify(proposal, initial_state, registered_tools, 100);
        self.score_from_verify(index, proposal, &vr, feedback)
    }

    /// Compute score from an already-computed VerifyResult.
    /// Uses static verification, simulated state, and optional historical feedback.
    fn score_from_verify(
        &self,
        index: usize,
        proposal: &ActionProposal,
        vr: &VerifyResult,
        feedback: Option<&ToolFeedback>,
    ) -> ScoredProposal {
        let error_count = vr.issues.iter().filter(|i| i.severity == "error").count();
        let warning_count = vr.issues.iter().filter(|i| i.severity == "warning").count();

        let action_count = proposal.actions.len();
        let tool_call_count = proposal
            .actions
            .iter()
            .filter(|a| a.action_type == car_ir::ActionType::ToolCall)
            .count();

        // Simulated state analysis
        let state_keys_written = vr.simulated_state.len();
        let has_write_conflicts = !vr.conflicts.is_empty();

        // Validity: 1.0 if clean, penalized by errors, warnings, and conflicts
        let validity = if error_count > 0 {
            0.0
        } else {
            let mut v = 1.0;
            v -= warning_count as f64 * 0.1;
            // Write conflicts are a strong signal of a bad plan
            if has_write_conflicts {
                v -= vr.conflicts.len() as f64 * self.config.conflict_penalty;
            }
            v.max(0.1)
        };

        // Cost efficiency: prefer fewer actions and tool calls within budget
        let action_ratio = if self.config.action_budget > 0 {
            1.0 - (action_count as f64 / self.config.action_budget as f64).min(1.0)
        } else {
            1.0
        };
        let tool_ratio = if self.config.tool_call_budget > 0 {
            1.0 - (tool_call_count as f64 / self.config.tool_call_budget as f64).min(1.0)
        } else {
            1.0
        };
        // Parallelism bonus: fewer levels = more parallelism = faster
        let parallelism_levels = vr.execution_levels.len();
        let parallelism_bonus = if action_count > 1 && parallelism_levels > 0 {
            1.0 - (parallelism_levels as f64 / action_count as f64).min(1.0)
        } else {
            0.0
        };
        // Token efficiency: prefer proposals that fit within the token budget.
        // Estimate tokens from the serialized proposal length (≈ 4 chars/token).
        let token_estimate = estimate_proposal_tokens(proposal);
        let token_ratio = if self.config.token_budget > 0 {
            1.0 - (token_estimate as f64 / self.config.token_budget as f64).min(1.0)
        } else {
            1.0
        };

        // Blend cost-efficiency terms. token_weight takes share from the other
        // terms proportionally — when token_weight=0 behaviour matches legacy.
        let tw = self.config.token_weight.clamp(0.0, 1.0);
        let rest = 1.0 - tw;
        let cost_efficiency = (action_ratio * (0.4 * rest)
            + tool_ratio * (0.4 * rest)
            + parallelism_bonus * (0.2 * rest)
            + token_ratio * tw)
            .clamp(0.0, 1.0);

        // Historical tool confidence from trajectory feedback
        let historical_confidence = feedback
            .map(|f| f.proposal_tool_confidence(proposal))
            .unwrap_or(1.0); // no feedback = assume full confidence

        // Combined score — invalid proposals always score 0.0
        // Formula: blend validity, cost_efficiency, and historical confidence
        let score = if error_count > 0 {
            0.0
        } else {
            let cw = self.config.cost_weight.clamp(0.0, 1.0);
            // Base score from validity and cost
            let base = validity * (1.0 - cw) + cost_efficiency * cw;
            // Scale by historical confidence (tools that fail often drag score down)
            let fw = self.config.feedback_weight.clamp(0.0, 1.0);
            base * (1.0 - fw + fw * historical_confidence)
        };

        let quality_per_token = if token_estimate > 0 {
            score / token_estimate as f64
        } else {
            score
        };

        ScoredProposal {
            index,
            score,
            validity,
            cost_efficiency,
            error_count,
            warning_count,
            action_count,
            tool_call_count,
            parallelism_levels,
            valid: vr.valid,
            state_keys_written,
            has_write_conflicts,
            historical_confidence,
            token_estimate,
            quality_per_token,
            outcome_value: 0.0,
        }
    }

    /// Rank multiple candidate proposals. Returns scored proposals sorted
    /// by score descending (best first).
    pub fn rank(
        &self,
        candidates: &[ActionProposal],
        initial_state: Option<&HashMap<String, Value>>,
        registered_tools: Option<&HashSet<String>>,
    ) -> Vec<ScoredProposal> {
        self.rank_with_feedback(candidates, initial_state, registered_tools, None)
    }

    /// Rank with historical tool feedback from trajectory store.
    pub fn rank_with_feedback(
        &self,
        candidates: &[ActionProposal],
        initial_state: Option<&HashMap<String, Value>>,
        registered_tools: Option<&HashSet<String>>,
        feedback: Option<&ToolFeedback>,
    ) -> Vec<ScoredProposal> {
        let mut scored: Vec<ScoredProposal> = candidates
            .iter()
            .enumerate()
            .map(|(i, p)| self.score_indexed(i, p, initial_state, registered_tools, feedback))
            .collect();

        // Sort by score descending, then by action_count ascending (tiebreaker)
        scored.sort_by(|a, b| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
                .then(a.action_count.cmp(&b.action_count))
                // Final deterministic tie-break: input order. Stable-sort
                // already preserved this, but making it explicit keeps
                // equal-score ranking from depending on sort stability.
                .then(a.index.cmp(&b.index))
        });

        scored
    }

    /// Pick the best valid proposal from candidates.
    /// Returns None if all candidates have errors.
    pub fn pick_best(
        &self,
        candidates: &[ActionProposal],
        initial_state: Option<&HashMap<String, Value>>,
        registered_tools: Option<&HashSet<String>>,
    ) -> Option<(usize, ScoredProposal)> {
        let ranked = self.rank_with_feedback(candidates, initial_state, registered_tools, None);
        ranked.into_iter().find(|s| s.valid).map(|s| (s.index, s))
    }

    /// Rank candidates by **predicted outcome** as well as validity/cost
    /// (Code World Models Slice 3). For each candidate, the predicted final
    /// state is computed with [`car_verify::simulate_with_model`] against the
    /// injected `model` — a verified Code World Model (e.g. a
    /// [`car_verify::cwm::GatedEffectModel`]) — and scored by `value`. The
    /// outcome value is blended into the static score with
    /// `PlannerConfig::outcome_weight`:
    /// `score = static_score * (1 - outcome_weight) + outcome_value *
    /// outcome_weight` for valid proposals (invalid ones stay `0.0`).
    ///
    /// This is the step that makes planning *outcome-aware*: a plan that reaches
    /// the goal can outrank a cheaper plan that doesn't. It is library-only by
    /// construction — like `car_verify::synthesize_cwm`, it takes injected trait
    /// objects (the model and the value function), which don't cross the FFI
    /// boundary; the stateless predictive primitive is `simulate_with_predictions`.
    ///
    /// With `outcome_weight == 0.0` (the default) the blend is a no-op and the
    /// ordering matches [`Planner::rank_with_feedback`] exactly — opting in an
    /// `EffectModel` never silently changes behavior.
    pub fn rank_with_outcome(
        &self,
        candidates: &[ActionProposal],
        initial_state: Option<&HashMap<String, Value>>,
        registered_tools: Option<&HashSet<String>>,
        feedback: Option<&ToolFeedback>,
        model: &dyn car_verify::cwm::EffectModel,
        value: &dyn ValueFunction,
    ) -> Vec<ScoredProposal> {
        let ow = self.config.outcome_weight.clamp(0.0, 1.0);
        let mut scored: Vec<ScoredProposal> = candidates
            .iter()
            .enumerate()
            .map(|(i, p)| {
                let mut sp = self.score_indexed(i, p, initial_state, registered_tools, feedback);
                // Predict the final state with the verified model and value it.
                let predicted = car_verify::simulate_with_model(p, initial_state, model);
                sp.outcome_value = value.value(&predicted).clamp(0.0, 1.0);
                // Blend only for valid proposals and only when opted in — an
                // invalid plan stays 0.0, and ow==0 reproduces the static score.
                if sp.error_count == 0 && ow > 0.0 {
                    sp.score = sp.score * (1.0 - ow) + sp.outcome_value * ow;
                    sp.quality_per_token = if sp.token_estimate > 0 {
                        sp.score / sp.token_estimate as f64
                    } else {
                        sp.score
                    };
                }
                sp
            })
            .collect();

        scored.sort_by(|a, b| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
                .then(a.action_count.cmp(&b.action_count))
                // Final deterministic tie-break: input order. Stable-sort
                // already preserved this, but making it explicit keeps
                // equal-score ranking from depending on sort stability.
                .then(a.index.cmp(&b.index))
        });
        scored
    }
}

/// Scores a predicted final state in `[0,1]` — higher is better. The paper's
/// generated value heuristic plugs in here; [`GoalKeysValue`] is a concrete,
/// dependency-free default. Implementations should be pure functions of the
/// state so ranking stays deterministic.
pub trait ValueFunction {
    fn value(&self, final_state: &HashMap<String, Value>) -> f64;
}

/// Default [`ValueFunction`]: the fraction of desired `(key, value)` goals that
/// the predicted final state satisfies. Numeric-aware (`1` matches `1.0`) so an
/// int that round-tripped through a float doesn't read as unmet. An empty goal
/// set scores `1.0` (vacuously satisfied) — set `outcome_weight` to `0.0` if you
/// have no goals rather than relying on this.
pub struct GoalKeysValue {
    pub goals: HashMap<String, Value>,
}

impl GoalKeysValue {
    pub fn new(goals: HashMap<String, Value>) -> Self {
        Self { goals }
    }
}

/// Numeric-aware value equality (mirrors `car_verify`'s rationale: an int that
/// floatified must still match), recursing through arrays/objects.
fn values_equal(a: &Value, b: &Value) -> bool {
    match (a, b) {
        (Value::Number(x), Value::Number(y)) => match (x.as_f64(), y.as_f64()) {
            (Some(fx), Some(fy)) => fx == fy,
            _ => x == y,
        },
        (Value::Array(xs), Value::Array(ys)) => {
            xs.len() == ys.len() && xs.iter().zip(ys).all(|(x, y)| values_equal(x, y))
        }
        (Value::Object(xs), Value::Object(ys)) => {
            xs.len() == ys.len()
                && xs
                    .iter()
                    .all(|(k, x)| ys.get(k).is_some_and(|y| values_equal(x, y)))
        }
        _ => a == b,
    }
}

impl ValueFunction for GoalKeysValue {
    fn value(&self, final_state: &HashMap<String, Value>) -> f64 {
        if self.goals.is_empty() {
            return 1.0;
        }
        let satisfied = self
            .goals
            .iter()
            .filter(|(k, v)| final_state.get(*k).is_some_and(|fv| values_equal(fv, v)))
            .count();
        satisfied as f64 / self.goals.len() as f64
    }
}

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

    fn tool_call(tool: &str, params: HashMap<String, Value>) -> Action {
        {
            let mut a = Action::new(ActionType::ToolCall);
            a.id = format!("a-{}", tool);
            a.tool = Some(tool.to_string());
            a.parameters = params;
            a
        }
    }

    fn state_write(key: &str, value: Value) -> Action {
        {
            let mut a = Action::new(ActionType::StateWrite);
            a.id = format!("sw-{}", key);
            a.parameters = [
                ("key".to_string(), Value::from(key)),
                ("value".to_string(), value),
            ]
            .into();
            a.max_retries = 0;
            a
        }
    }

    fn proposal(id: &str, actions: Vec<Action>) -> ActionProposal {
        ActionProposal {
            id: id.to_string(),
            source: "test".to_string(),
            actions,
            // FIXED, not `Utc::now()`. Scoring feeds `estimate_proposal_tokens`
            // (= `serde_json::to_string(proposal).len() / 4`) into token
            // efficiency, and chrono's RFC3339 output TRIMS trailing zeros from
            // the fractional seconds — so the serialized length depends on *when
            // the clock happened to tick*. Two structurally identical proposals
            // built microseconds apart could therefore get different token
            // estimates, different scores, and flip a supposedly-tied ranking.
            // That made `outcome_weight_decides_between_equal_cost_plans` flaky
            // on every platform (~3 in 25 locally); it only got noticed when the
            // Windows gate started running the whole workspace.
            timestamp: chrono::DateTime::from_timestamp(0, 0).expect("epoch is a valid timestamp"),
            context: HashMap::new(),
        }
    }

    #[test]
    fn score_clean_proposal() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["search".into()].into();
        let p = proposal(
            "p1",
            vec![tool_call(
                "search",
                [("q".into(), Value::from("rust"))].into(),
            )],
        );

        let scored = planner.score(&p, None, Some(&tools));
        assert!(scored.valid);
        assert!(scored.score > 0.5);
        assert_eq!(scored.error_count, 0);
        assert_eq!(scored.action_count, 1);
        assert_eq!(scored.tool_call_count, 1);
    }

    #[test]
    fn score_invalid_proposal_unregistered_tool() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["search".into()].into();
        let p = proposal("p1", vec![tool_call("nonexistent", HashMap::new())]);

        let scored = planner.score(&p, None, Some(&tools));
        assert!(!scored.valid);
        assert_eq!(scored.validity, 0.0);
        assert!(scored.error_count > 0);
    }

    #[test]
    fn rank_prefers_valid_over_invalid() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["search".into()].into();

        let valid = proposal(
            "valid",
            vec![tool_call(
                "search",
                [("q".into(), Value::from("test"))].into(),
            )],
        );
        let invalid = proposal("invalid", vec![tool_call("nonexistent", HashMap::new())]);

        let ranked = planner.rank(&[invalid, valid], None, Some(&tools));
        assert!(ranked[0].valid);
        assert!(!ranked[1].valid);
        assert_eq!(ranked[0].index, 1); // the valid one was at index 1
    }

    #[test]
    fn rank_prefers_cheaper_among_valid() {
        let planner = Planner::new(PlannerConfig {
            cost_weight: 0.5, // strong cost preference
            action_budget: 10,
            tool_call_budget: 5,
            ..Default::default()
        });
        let tools: HashSet<String> = ["a".into(), "b".into(), "c".into()].into();

        let cheap = proposal("cheap", vec![tool_call("a", HashMap::new())]);
        let expensive = proposal(
            "expensive",
            vec![
                tool_call("a", HashMap::new()),
                tool_call("b", HashMap::new()),
                tool_call("c", HashMap::new()),
            ],
        );

        let ranked = planner.rank(&[expensive, cheap], None, Some(&tools));
        // Cheap should rank higher due to cost_weight
        assert_eq!(ranked[0].index, 1); // cheap was at index 1
        assert!(ranked[0].cost_efficiency > ranked[1].cost_efficiency);
    }

    #[test]
    fn pick_best_skips_invalid() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["ok".into()].into();

        let bad = proposal("bad", vec![tool_call("nonexistent", HashMap::new())]);
        let good = proposal("good", vec![tool_call("ok", HashMap::new())]);

        let result = planner.pick_best(&[bad, good], None, Some(&tools));
        assert!(result.is_some());
        let (idx, scored) = result.unwrap();
        assert_eq!(idx, 1);
        assert!(scored.valid);
    }

    #[test]
    fn pick_best_returns_none_when_all_invalid() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = HashSet::new();

        let bad1 = proposal("bad1", vec![tool_call("x", HashMap::new())]);
        let bad2 = proposal("bad2", vec![tool_call("y", HashMap::new())]);

        let result = planner.pick_best(&[bad1, bad2], None, Some(&tools));
        assert!(result.is_none());
    }

    #[test]
    fn score_state_write_only() {
        let planner = Planner::new(PlannerConfig::default());
        let p = proposal("sw", vec![state_write("key", Value::from("value"))]);

        let scored = planner.score(&p, None, None);
        assert!(scored.valid);
        assert_eq!(scored.tool_call_count, 0);
        assert_eq!(scored.action_count, 1);
    }

    #[test]
    fn parallelism_bonus_rewards_independent_actions() {
        let planner = Planner::new(PlannerConfig {
            cost_weight: 0.5,
            action_budget: 10,
            tool_call_budget: 5,
            ..Default::default()
        });
        let tools: HashSet<String> = ["a".into(), "b".into()].into();

        // Two independent actions → 1 DAG level (parallel)
        let parallel = proposal(
            "par",
            vec![
                tool_call("a", HashMap::new()),
                tool_call("b", HashMap::new()),
            ],
        );

        // Two dependent actions → 2 DAG levels (sequential)
        let mut seq_actions = vec![
            tool_call("a", HashMap::new()),
            tool_call("b", HashMap::new()),
        ];
        seq_actions[1].state_dependencies.push("key".into());
        // First action writes "key" so second depends on it
        seq_actions[0]
            .expected_effects
            .insert("key".into(), Value::from("v"));
        let sequential = proposal("seq", seq_actions);

        let par_score = planner.score(&parallel, None, Some(&tools));
        let seq_score = planner.score(&sequential, None, Some(&tools));

        // Parallel should have better cost_efficiency due to parallelism bonus
        assert!(
            par_score.cost_efficiency >= seq_score.cost_efficiency,
            "parallel={:.3} should >= sequential={:.3}",
            par_score.cost_efficiency,
            seq_score.cost_efficiency
        );
    }

    #[test]
    fn state_write_tracks_keys() {
        let planner = Planner::new(PlannerConfig::default());
        let p = proposal(
            "sw",
            vec![
                state_write("key_a", Value::from("val_a")),
                state_write("key_b", Value::from("val_b")),
            ],
        );

        let scored = planner.score(&p, None, None);
        assert!(scored.valid);
        assert_eq!(scored.state_keys_written, 2);
        assert!(!scored.has_write_conflicts);
    }

    #[test]
    fn write_conflict_penalizes_score() {
        let planner = Planner::new(PlannerConfig::default());
        // Two actions writing the same key = conflict
        let p = proposal(
            "conflict",
            vec![
                state_write("shared_key", Value::from("v1")),
                state_write("shared_key", Value::from("v2")),
            ],
        );

        let scored = planner.score(&p, None, None);
        assert!(scored.has_write_conflicts);
        // Conflict penalty should reduce validity
        assert!(
            scored.validity < 1.0,
            "expected conflict penalty, got validity={:.3}",
            scored.validity
        );
    }

    #[test]
    fn feedback_penalizes_tools_that_fail_often() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["reliable".into(), "flaky".into()].into();

        let reliable_plan = proposal("reliable", vec![tool_call("reliable", HashMap::new())]);
        let flaky_plan = proposal("flaky", vec![tool_call("flaky", HashMap::new())]);

        let feedback = ToolFeedback {
            tool_success_rates: [("reliable".into(), 0.95), ("flaky".into(), 0.2)].into(),
            ..Default::default()
        };

        let ranked = planner.rank_with_feedback(
            &[flaky_plan, reliable_plan],
            None,
            Some(&tools),
            Some(&feedback),
        );

        // Reliable plan should rank higher
        assert_eq!(ranked[0].index, 1, "reliable plan should rank first");
        assert!(ranked[0].historical_confidence > ranked[1].historical_confidence);
        assert!(
            ranked[0].score > ranked[1].score,
            "reliable={:.3} should > flaky={:.3}",
            ranked[0].score,
            ranked[1].score
        );
    }

    #[test]
    fn feedback_from_trajectories() {
        use car_memgine::{TraceEvent, Trajectory, TrajectoryOutcome};

        let trajectories = vec![
            Trajectory {
                proposal_id: "t1".into(),
                source: "test".into(),
                action_count: 1,
                events: vec![TraceEvent {
                    kind: "action_succeeded".into(),
                    action_id: Some("a1".into()),
                    tool: Some("good_tool".into()),
                    data: serde_json::json!({}),
                    ..Default::default()
                }],
                outcome: TrajectoryOutcome::Success,
                timestamp: chrono::Utc::now(),
                duration_ms: 100.0,
                replan_attempts: 0,
            },
            Trajectory {
                proposal_id: "t2".into(),
                source: "test".into(),
                action_count: 1,
                events: vec![TraceEvent {
                    kind: "action_failed".into(),
                    action_id: Some("a2".into()),
                    tool: Some("bad_tool".into()),
                    data: serde_json::json!({}),
                    ..Default::default()
                }],
                outcome: TrajectoryOutcome::Failed,
                timestamp: chrono::Utc::now(),
                duration_ms: 50.0,
                replan_attempts: 0,
            },
        ];

        let feedback = ToolFeedback::from_trajectories(&trajectories);
        assert!((feedback.rate("good_tool") - 1.0).abs() < 0.01);
        assert!((feedback.rate("bad_tool") - 0.0).abs() < 0.01);
        assert!((feedback.rate("unknown") - 0.5).abs() < 0.01); // default
    }

    #[test]
    fn token_estimate_surfaced_and_nonzero() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["a".into()].into();
        let p = proposal("p1", vec![tool_call("a", HashMap::new())]);

        let scored = planner.score(&p, None, Some(&tools));
        assert!(scored.token_estimate > 0);
        assert!(scored.quality_per_token > 0.0);
        assert!(
            (scored.quality_per_token - scored.score / scored.token_estimate as f64).abs() < 1e-9
        );
    }

    #[test]
    fn tiny_token_budget_penalizes_proposals() {
        // When the token budget is very small, all proposals exceed it and
        // token_ratio saturates to 0, dragging cost_efficiency below 1.0.
        let planner = Planner::new(PlannerConfig {
            token_budget: 10, // way below any real proposal
            token_weight: 0.8,
            cost_weight: 0.5,
            ..Default::default()
        });
        let tools: HashSet<String> = ["a".into()].into();
        let p = proposal("p1", vec![tool_call("a", HashMap::new())]);
        let scored = planner.score(&p, None, Some(&tools));
        assert!(scored.valid);
        assert!(
            scored.cost_efficiency < 0.5,
            "small token budget should tank cost_efficiency, got {:.3}",
            scored.cost_efficiency
        );
    }

    #[test]
    fn token_weight_zero_matches_legacy_blend() {
        // With token_weight=0, cost_efficiency should match the legacy
        // (action/tool/parallelism) formula: 0.4a + 0.4t + 0.2p.
        let planner = Planner::new(PlannerConfig {
            token_weight: 0.0,
            ..Default::default()
        });
        let tools: HashSet<String> = ["a".into()].into();
        let p = proposal("p1", vec![tool_call("a", HashMap::new())]);
        let scored = planner.score(&p, None, Some(&tools));
        let action_ratio = 1.0 - (1.0 / 20.0); // budget=20
        let tool_ratio = 1.0 - (1.0 / 10.0); // budget=10
        let expected = action_ratio * 0.4 + tool_ratio * 0.4 + 0.0 * 0.2;
        assert!(
            (scored.cost_efficiency - expected).abs() < 1e-6,
            "cost_efficiency={:.6} expected={:.6}",
            scored.cost_efficiency,
            expected
        );
    }

    #[test]
    fn no_feedback_means_full_confidence() {
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["a".into()].into();
        let p = proposal("p1", vec![tool_call("a", HashMap::new())]);

        let scored = planner.score(&p, None, Some(&tools));
        assert!((scored.historical_confidence - 1.0).abs() < 0.01);
    }

    // --- Slice 3: outcome-aware ranking ---

    use car_verify::cwm::{GatedEffectModel, GatedPrediction};

    #[test]
    fn goal_keys_value_is_fraction_satisfied() {
        let goals: HashMap<String, Value> = [
            ("x".to_string(), Value::from(1)),
            ("y".to_string(), Value::from(2)),
        ]
        .into();
        let v = GoalKeysValue::new(goals);

        let mut state: HashMap<String, Value> = HashMap::new();
        state.insert("x".to_string(), Value::from(1.0)); // 1 == 1.0 (numeric-aware)
        assert!((v.value(&state) - 0.5).abs() < 1e-9);
        state.insert("y".to_string(), Value::from(2));
        assert!((v.value(&state) - 1.0).abs() < 1e-9);
    }

    #[test]
    fn empty_goal_is_vacuously_satisfied() {
        let v = GoalKeysValue::new(HashMap::new());
        assert_eq!(v.value(&HashMap::new()), 1.0);
    }

    #[test]
    fn outcome_weight_zero_is_a_noop() {
        // Default config has outcome_weight 0.0 → score must equal the static
        // path even though the model predicts the goal.
        let planner = Planner::new(PlannerConfig::default());
        let tools: HashSet<String> = ["search".into()].into();
        let p = proposal(
            "p1",
            vec![tool_call("search", [("q".into(), Value::from("x"))].into())],
        );
        let base = planner.rank(std::slice::from_ref(&p), None, Some(&tools));

        let mut preds = HashMap::new();
        preds.insert(
            "a-search".to_string(),
            GatedPrediction {
                effects: [("goal".to_string(), Value::Bool(true))].into(),
                accuracy: 1.0,
            },
        );
        let model = GatedEffectModel {
            predictions: preds,
            min_accuracy: 0.5,
        };
        let val = GoalKeysValue::new([("goal".to_string(), Value::Bool(true))].into());

        let out = planner.rank_with_outcome(&[p], None, Some(&tools), None, &model, &val);
        // Outcome value is computed and surfaced...
        assert!((out[0].outcome_value - 1.0).abs() < 1e-9);
        // ...but with outcome_weight 0.0 the score is unchanged.
        assert!((out[0].score - base[0].score).abs() < 1e-9);
    }

    #[test]
    fn outcome_weight_decides_between_equal_cost_plans() {
        // Two structurally identical, equal-cost candidates (same tool, same
        // params) differing only in action id — so the *only* thing that can
        // change the ranking is the predicted outcome, not cost/parallelism.
        let tools: HashSet<String> = ["fetch".into()].into();
        let mut aa = tool_call("fetch", [("q".into(), Value::from("x"))].into());
        aa.id = "a-act".to_string();
        let mut bb = tool_call("fetch", [("q".into(), Value::from("x"))].into());
        bb.id = "b-act".to_string();
        let cands = vec![proposal("A", vec![aa]), proposal("B", vec![bb])];

        // The verified model: B's action reaches the goal; A abstains.
        let mut preds = HashMap::new();
        preds.insert(
            "b-act".to_string(),
            GatedPrediction {
                effects: [("goal".to_string(), Value::Bool(true))].into(),
                accuracy: 0.99,
            },
        );
        let model = GatedEffectModel {
            predictions: preds,
            min_accuracy: 0.9,
        };
        let val = GoalKeysValue::new([("goal".to_string(), Value::Bool(true))].into());

        // No outcome weight → equal scores, stable order keeps input order (A first).
        let planner0 = Planner::new(PlannerConfig::default());
        let r0 = planner0.rank_with_outcome(&cands, None, Some(&tools), None, &model, &val);
        assert_eq!(r0[0].index, 0);

        // With outcome weight, the goal-reaching B overtakes A.
        let planner1 = Planner::new(PlannerConfig {
            outcome_weight: 0.8,
            ..Default::default()
        });
        let r1 = planner1.rank_with_outcome(&cands, None, Some(&tools), None, &model, &val);
        assert_eq!(
            r1[0].index, 1,
            "outcome weight lifts the goal-reaching plan first"
        );

        let b_sp = r1.iter().find(|s| s.index == 1).unwrap();
        let a_sp = r1.iter().find(|s| s.index == 0).unwrap();
        assert!((b_sp.outcome_value - 1.0).abs() < 1e-9);
        assert!((a_sp.outcome_value - 0.0).abs() < 1e-9);
    }

    // --- dispatch-conditional feedback ---

    fn trace(kind: &str, tool: &str) -> car_memgine::TraceEvent {
        car_memgine::TraceEvent {
            kind: kind.to_string(),
            action_id: Some(format!("a-{tool}")),
            tool: Some(tool.to_string()),
            data: Value::Null,
            duration_ms: None,
            state_before: None,
            state_after: None,
            reward: None,
        }
    }

    fn traj(events: Vec<car_memgine::TraceEvent>) -> car_memgine::Trajectory {
        car_memgine::Trajectory {
            proposal_id: "p".into(),
            source: "test".into(),
            action_count: events.len(),
            events,
            outcome: car_memgine::TrajectoryOutcome::Success,
            timestamp: chrono::Utc::now(),
            duration_ms: 0.0,
            replan_attempts: 0,
        }
    }

    #[test]
    fn rejections_are_not_evidence_about_the_tool() {
        // `api` ran twice and succeeded both times. It was also rejected eight
        // times — by the validator or policy, before dispatch — so the tool
        // never had a chance to fail on those.
        let mut events = vec![
            trace("action_succeeded", "api"),
            trace("action_succeeded", "api"),
        ];
        for _ in 0..8 {
            events.push(trace("action_rejected", "api"));
        }
        let ts = vec![traj(events)];

        // The scoring constructor counts all ten: 2/10 = 0.2. That is a
        // deliberate signal for ranking, and unchanged here.
        let scoring = ToolFeedback::from_trajectories(&ts);
        assert!((scoring.rate("api") - 0.2).abs() < 1e-9);

        // The dispatch-conditional constructor counts the two that ran.
        // Laplace-smoothed: (2+1)/(2+2) = 0.75.
        let dispatched = ToolFeedback::dispatched_from_trajectories(&ts);
        assert!(
            (dispatched.rate("api") - 0.75).abs() < 1e-9,
            "got {}",
            dispatched.rate("api")
        );
        assert_eq!(dispatched.tool_dispatch_counts["api"], (2, 2));
    }

    #[test]
    fn skipped_actions_are_excluded_too() {
        let ts = vec![traj(vec![
            trace("action_succeeded", "t"),
            trace("action_failed", "t"),
            trace("action_skipped", "t"),
            trace("action_skipped", "t"),
        ])];
        let f = ToolFeedback::dispatched_from_trajectories(&ts);
        // Only the succeeded + failed pair is evidence: (1+1)/(2+2) = 0.5.
        assert_eq!(f.tool_dispatch_counts["t"], (1, 2));
        assert!((f.rate("t") - 0.5).abs() < 1e-9);
    }

    #[test]
    fn smoothing_tempers_small_samples_without_a_cliff() {
        let one_success = ToolFeedback::dispatched_from_trajectories(&[traj(vec![trace(
            "action_succeeded",
            "t",
        )])]);
        // A single success is not a categorical guarantee.
        assert!((one_success.rate("t") - 2.0 / 3.0).abs() < 1e-9);

        let many = ToolFeedback::dispatched_from_trajectories(&[traj(
            (0..100).map(|_| trace("action_succeeded", "t")).collect(),
        )]);
        // With real evidence the prior stops mattering, and the rate rises
        // smoothly rather than jumping at a threshold.
        assert!(many.rate("t") > 0.99);
        assert!(many.rate("t") > one_success.rate("t"));
        assert_eq!(many.tool_dispatch_counts["t"], (100, 100));
    }

    #[test]
    fn a_tool_that_never_ran_is_absent_not_a_coin_flip() {
        let f = ToolFeedback::dispatched_from_trajectories(&[traj(vec![trace(
            "action_rejected",
            "never_ran",
        )])]);
        // No dispatch = no evidence. The key is absent so the consumer applies
        // its own default, rather than us asserting 0.5 as an observation.
        assert!(!f.tool_success_rates.contains_key("never_ran"));
        assert!(!f.tool_dispatch_counts.contains_key("never_ran"));
        // `rate()` still answers with the no-data default.
        assert!((f.rate("never_ran") - 0.5).abs() < 1e-9);
    }

    #[test]
    fn a_consistently_failing_tool_reads_low() {
        let f = ToolFeedback::dispatched_from_trajectories(&[traj(
            (0..50).map(|_| trace("action_failed", "broken")).collect(),
        )]);
        assert!(f.rate("broken") < 0.02, "got {}", f.rate("broken"));
        assert_eq!(f.tool_dispatch_counts["broken"], (0, 50));
    }
}