proofborne_core/

routing.rs

use std::collections::{BTreeMap, BTreeSet};

use serde::{Deserialize, Serialize};
use thiserror::Error;

use crate::{ProviderCapabilities, SCHEMA_VERSION, hash_json};

/// Deterministic routing reducer understood by this release.
pub const ROUTING_ALGORITHM_VERSION: &str = "proofborne.routing.deterministic.v1";
/// Version of the proof-carrying local model-catalog contract.
pub const MODEL_CATALOG_VERSION: &str = "proofborne.model-catalog.v1";
/// Pricing is expressed in micro-US-dollars per one million tokens.
pub const ROUTING_PRICE_TOKEN_SCALE: u64 = 1_000_000;

/// Portable capability that a route may require from a provider adapter.
#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq, PartialOrd, Ord)]
#[serde(rename_all = "snake_case")]
pub enum RoutingCapability {
    /// Requires streaming output (chunked transport).
    Streaming,
    /// Requires tool / function calling support.
    Tools,
    /// Requires JSON-structured output without free-form text.
    StructuredOutput,
    /// Requires image / video / audio inputs.
    MultimodalInput,
}

impl RoutingCapability {
    fn is_supported_by(self, capabilities: &ProviderCapabilities) -> bool {
        match self {
            Self::Streaming => capabilities.streaming,
            Self::Tools => capabilities.tools,
            Self::StructuredOutput => capabilities.structured_output,
            Self::MultimodalInput => capabilities.multimodal_input,
        }
    }
}

/// Provenance of the context-window value used by routing.
#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "snake_case")]
pub enum RoutingContextSource {
    /// Declared directly by the provider adapter.
    Provider,
    /// Pinned by a local, version-controlled profile.
    Profile,
    /// Conservative runtime fallback recorded explicitly in the plan.
    RuntimeFallback,
}

/// Immutable local pricing used only for deterministic preflight estimates.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct ModelPricing {
    /// Maximum input charge in micro-USD per one million tokens.
    pub input_microusd_per_million_tokens: u64,
    /// Maximum output charge in micro-USD per one million tokens.
    pub output_microusd_per_million_tokens: u64,
}

impl ModelPricing {
    /// Computes a ceiling estimate without floating point arithmetic.
    pub fn estimate(
        &self,
        max_input_tokens: u64,
        reserved_output_tokens: u64,
    ) -> Result<u64, RoutingError> {
        let input = estimate_component(max_input_tokens, self.input_microusd_per_million_tokens)?;
        let output = estimate_component(
            reserved_output_tokens,
            self.output_microusd_per_million_tokens,
        )?;
        input.checked_add(output).ok_or(RoutingError::CostOverflow)
    }
}

fn estimate_component(tokens: u64, rate: u64) -> Result<u64, RoutingError> {
    let numerator = u128::from(tokens)
        .checked_mul(u128::from(rate))
        .ok_or(RoutingError::CostOverflow)?;
    let scale = u128::from(ROUTING_PRICE_TOKEN_SCALE);
    let estimate = numerator
        .checked_add(scale.saturating_sub(1))
        .ok_or(RoutingError::CostOverflow)?
        / scale;
    u64::try_from(estimate).map_err(|_| RoutingError::CostOverflow)
}

/// One content-addressed model description in the local catalog.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct ModelDescriptor {
    /// BLAKE3 identity over every remaining descriptor field.
    pub id: String,
    /// Adapter identifier.
    pub provider: String,
    /// Exact provider model selector.
    pub model: String,
    /// Adapter capabilities observed before routing.
    pub capabilities: ProviderCapabilities,
    /// Effective context boundary used by the compaction budget.
    pub context_tokens: u64,
    /// Provenance of `context_tokens`.
    pub context_source: RoutingContextSource,
    /// Optional pinned pricing. Unknown pricing cannot satisfy a priced budget.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub pricing: Option<ModelPricing>,
    /// Optional conservative latency ceiling in milliseconds.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub expected_latency_ms: Option<u64>,
}

impl ModelDescriptor {
    /// Constructs a descriptor, validates material fields, and computes its content-addressed ID.
    #[allow(clippy::too_many_arguments)]
    pub fn new(
        provider: impl Into<String>,
        model: impl Into<String>,
        capabilities: ProviderCapabilities,
        context_tokens: u64,
        context_source: RoutingContextSource,
        pricing: Option<ModelPricing>,
        expected_latency_ms: Option<u64>,
    ) -> Result<Self, RoutingError> {
        let mut descriptor = Self {
            id: String::new(),
            provider: provider.into(),
            model: model.into(),
            capabilities,
            context_tokens,
            context_source,
            pricing,
            expected_latency_ms,
        };
        descriptor.validate_material()?;
        descriptor.id = descriptor.material_digest()?;
        Ok(descriptor)
    }

    /// Material-digests the descriptor's non-ID fields.
    pub fn material_digest(&self) -> Result<String, RoutingError> {
        Ok(hash_json(&self.material_value()))
    }

    /// Validates material fields and ensures the ID matches the material digest.
    pub fn validate(&self) -> Result<(), RoutingError> {
        self.validate_material()?;
        if !valid_digest(&self.id) || self.id != self.material_digest()? {
            return Err(RoutingError::DescriptorDigest(self.id.clone()));
        }
        Ok(())
    }

    fn material_value(&self) -> serde_json::Value {
        serde_json::json!({
            "provider": self.provider,
            "model": self.model,
            "capabilities": self.capabilities,
            "contextTokens": self.context_tokens,
            "contextSource": self.context_source,
            "pricing": self.pricing,
            "expectedLatencyMs": self.expected_latency_ms,
        })
    }

    fn validate_material(&self) -> Result<(), RoutingError> {
        if self.provider.trim().is_empty() || self.model.trim().is_empty() {
            return Err(RoutingError::EmptyIdentity);
        }
        if self.context_tokens == 0 || self.expected_latency_ms == Some(0) {
            return Err(RoutingError::InvalidDescriptor(self.model.clone()));
        }
        Ok(())
    }
}

/// Versioned, content-addressed catalog embedded in every routing plan.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct ModelCatalog {
    /// Schema version enforced against `SCHEMA_VERSION`.
    pub schema_version: String,
    /// Catalog contract version enforced against `MODEL_CATALOG_VERSION`.
    pub catalog_version: String,
    /// Content-addressed model descriptors, sorted by `id`.
    pub descriptors: Vec<ModelDescriptor>,
}

impl ModelCatalog {
    /// Creates a new catalog from descriptors, validates, and digest-sorts them by `id`.
    pub fn new(mut descriptors: Vec<ModelDescriptor>) -> Result<Self, RoutingError> {
        descriptors.sort_by(|left, right| left.id.cmp(&right.id));
        let catalog = Self {
            schema_version: SCHEMA_VERSION.to_owned(),
            catalog_version: MODEL_CATALOG_VERSION.to_owned(),
            descriptors,
        };
        catalog.validate()?;
        Ok(catalog)
    }

    /// Validates schema version, catalog version, descriptor digests, sort order, and non-emptiness.
    pub fn validate(&self) -> Result<(), RoutingError> {
        if self.schema_version != SCHEMA_VERSION {
            return Err(RoutingError::UnsupportedSchema(self.schema_version.clone()));
        }
        if self.catalog_version != MODEL_CATALOG_VERSION {
            return Err(RoutingError::UnsupportedCatalog(
                self.catalog_version.clone(),
            ));
        }
        let mut previous = None;
        for descriptor in &self.descriptors {
            descriptor.validate()?;
            if previous.is_some_and(|id: &str| id >= descriptor.id.as_str()) {
                return Err(RoutingError::CatalogOrder);
            }
            previous = Some(descriptor.id.as_str());
        }
        if self.descriptors.is_empty() {
            return Err(RoutingError::EmptyCatalog);
        }
        Ok(())
    }

    /// Computes a canonical BLAKE3 digest over the validated catalog JSON.
    pub fn digest(&self) -> Result<String, RoutingError> {
        self.validate()?;
        let value = serde_json::to_value(self).map_err(|_| RoutingError::Serialization)?;
        Ok(hash_json(&value))
    }
}

/// Executable candidate bound to a catalog descriptor and runtime authority.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct RoutingCandidate {
    /// Stable digest over profile, descriptor, authority, and credential identity.
    pub id: String,
    /// Content-addressed model descriptor this candidate references.
    pub descriptor_id: String,
    /// Lower values are preferred. Candidate ID breaks ties deterministically.
    pub preference_rank: u32,
    /// User-defined profile name used for deterministic preference and configuration.
    pub profile: String,
    /// Secret-free authority digest, including credential identity when present.
    pub authority_hash: String,
    /// False when an explicitly required credential could not be resolved.
    pub credential_available: bool,
    /// Explicit local kill switch.
    pub enabled: bool,
}

impl RoutingCandidate {
    /// Constructs a candidate, material-digests its fields, and validates the result.
    pub fn new(
        descriptor_id: impl Into<String>,
        preference_rank: u32,
        profile: impl Into<String>,
        authority_hash: impl Into<String>,
        credential_available: bool,
        enabled: bool,
    ) -> Result<Self, RoutingError> {
        let mut candidate = Self {
            id: String::new(),
            descriptor_id: descriptor_id.into(),
            preference_rank,
            profile: profile.into(),
            authority_hash: authority_hash.into(),
            credential_available,
            enabled,
        };
        candidate.validate_material()?;
        candidate.id = candidate.material_digest()?;
        Ok(candidate)
    }

    /// Material-digests the candidate's profile-bound fields without the ID.
    pub fn material_digest(&self) -> Result<String, RoutingError> {
        Ok(hash_json(&self.material_value()))
    }

    /// Validates material fields and ensures the ID matches the material digest.
    pub fn validate(&self) -> Result<(), RoutingError> {
        self.validate_material()?;
        if !valid_digest(&self.id) || self.id != self.material_digest()? {
            return Err(RoutingError::CandidateDigest(self.id.clone()));
        }
        Ok(())
    }

    fn material_value(&self) -> serde_json::Value {
        serde_json::json!({
            "descriptorId": self.descriptor_id,
            "preferenceRank": self.preference_rank,
            "profile": self.profile,
            "authorityHash": self.authority_hash,
            "credentialAvailable": self.credential_available,
            "enabled": self.enabled,
        })
    }

    fn validate_material(&self) -> Result<(), RoutingError> {
        if self.profile.trim().is_empty()
            || !valid_digest(&self.descriptor_id)
            || !valid_digest(&self.authority_hash)
        {
            return Err(RoutingError::InvalidCandidate(self.profile.clone()));
        }
        Ok(())
    }
}

/// Runtime-owned requirements and hard budgets for one model decision.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct RoutingRequirements {
    /// Capabilities the route must support (e.g. streaming, tools).
    #[serde(default)]
    pub required_capabilities: BTreeSet<RoutingCapability>,
    /// Minimum context window any eligible candidate must offer.
    pub min_context_tokens: u64,
    /// Max input token budget for the route decision.
    pub max_input_tokens: u64,
    /// Reserved output token budget reserved for responses.
    pub reserved_output_tokens: u64,
    /// Optional maximum estimated cost in micro-USD.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub max_estimated_cost_microusd: Option<u64>,
    /// Optional maximum accepted latency in milliseconds.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub max_latency_ms: Option<u64>,
    /// When true, pricing-unknown candidates are excluded.
    #[serde(default)]
    pub require_known_pricing: bool,
    /// When true, latency-unknown candidates are excluded.
    #[serde(default)]
    pub require_known_latency: bool,
}

impl RoutingRequirements {
    /// Rejects zero or negative budgets and missing required values.
    pub fn validate(&self) -> Result<(), RoutingError> {
        if self.min_context_tokens == 0
            || self.max_input_tokens == 0
            || self.reserved_output_tokens == 0
            || self.reserved_output_tokens == u64::MAX
            || self.max_estimated_cost_microusd == Some(0)
            || self.max_latency_ms == Some(0)
        {
            return Err(RoutingError::InvalidRequirements);
        }
        Ok(())
    }
}

/// State and authority bindings that make a routing decision non-replayable.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct RoutingBindings {
    /// Hash of the full routing contract payload.
    pub contract_hash: String,
    /// Hash of the policy applied during routing.
    pub policy_hash: String,
    /// Optional hash of the tool-calling authority when present.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub tool_authority_hash: Option<String>,
    /// Content-addressed digest of the model catalog.
    pub catalog_hash: String,
    /// Hash of the run-controls configuration.
    pub run_controls_hash: String,
    /// Monotonic step counter for sequential provider invocations.
    pub step: u64,
    /// Monotonic workspace generation for replay protection.
    pub workspace_generation: u64,
    /// Opaque state binding that pins this decision to prior outputs.
    pub state_binding: String,
    /// Monotonic watermark tracking side effects to prevent replay.
    pub side_effect_watermark: u64,
    /// Optional candidate ID locked for the entire step.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub locked_candidate_id: Option<String>,
}

impl RoutingBindings {
    fn validate(&self) -> Result<(), RoutingError> {
        for digest in [
            Some(self.contract_hash.as_str()),
            Some(self.policy_hash.as_str()),
            self.tool_authority_hash.as_deref(),
            Some(self.catalog_hash.as_str()),
            Some(self.run_controls_hash.as_str()),
            Some(self.state_binding.as_str()),
            self.locked_candidate_id.as_deref(),
        ]
        .into_iter()
        .flatten()
        {
            if !valid_digest(digest) {
                return Err(RoutingError::InvalidBinding(digest.to_owned()));
            }
        }
        Ok(())
    }
}

/// Stable reason why a candidate cannot execute.
#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq, PartialOrd, Ord)]
#[serde(rename_all = "snake_case")]
pub enum RoutingExclusionReason {
    /// Candidate `enabled` is `false`.
    Disabled,
    /// A required credential could not be resolved.
    CredentialUnavailable,
    /// A required `RoutingCapability` is not advertised.
    MissingCapability,
    /// The candidate's context window is smaller than `min_context_tokens`.
    ContextWindowTooSmall,
    /// The candidate has no pricing data and `require_known_pricing` is true.
    PricingUnknown,
    /// The candidate's estimated cost exceeds `max_estimated_cost_microusd`.
    CostBudgetExceeded,
    /// The candidate has no latency estimate and `require_known_latency` is true.
    LatencyUnknown,
    /// The candidate's estimated latency exceeds `max_latency_ms`.
    LatencyBudgetExceeded,
    /// The step has a locked candidate that differs from this candidate.
    SessionRouteLocked,
    /// A fallback is blocked because a side effect was already recorded.
    FallbackBlockedAfterSideEffect,
}

/// Deterministic reducer output for one candidate.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct RoutingSelection {
    /// The candidate evaluated by the reducer.
    pub candidate: RoutingCandidate,
    /// Whether this candidate is eligible for execution.
    pub eligible: bool,
    /// Reasons for exclusion when `eligible` is `false`.
    #[serde(default)]
    pub reasons: BTreeSet<RoutingExclusionReason>,
    /// Required capabilities this candidate lacks.
    #[serde(default)]
    pub missing_capabilities: BTreeSet<RoutingCapability>,
    /// Pre-computed cost estimate for this candidate.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub estimated_max_cost_microusd: Option<u64>,
}

/// Proof-carrying deterministic route plan for exactly one provider step.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct RoutingPlan {
    /// Schema version enforced against `SCHEMA_VERSION`.
    pub schema_version: String,
    /// Algorithm version enforced against `ROUTING_ALGORITHM_VERSION`.
    pub algorithm_version: String,
    /// Embedded model catalog governing candidate descriptors.
    pub catalog: ModelCatalog,
    /// Hard budgets and requirements for the route decision.
    pub requirements: RoutingRequirements,
    /// Non-replayability bindings including state and side-effect watermarks.
    pub bindings: RoutingBindings,
    /// Deterministic reduction results, one per candidate, in preference order.
    pub selections: Vec<RoutingSelection>,
}

impl RoutingPlan {
    /// Validates all inputs, builds candidate selections, and constructs the plan.
    pub fn build(
        catalog: ModelCatalog,
        requirements: RoutingRequirements,
        bindings: RoutingBindings,
        mut candidates: Vec<RoutingCandidate>,
    ) -> Result<Self, RoutingError> {
        catalog.validate()?;
        requirements.validate()?;
        bindings.validate()?;
        if catalog.digest()? != bindings.catalog_hash {
            return Err(RoutingError::CatalogBinding);
        }
        candidates.sort_by(|left, right| {
            (left.preference_rank, &left.id).cmp(&(right.preference_rank, &right.id))
        });
        validate_candidate_set(
            &catalog,
            &candidates,
            bindings.locked_candidate_id.as_deref(),
        )?;
        let selections = compute_selections(&catalog, &requirements, &bindings, candidates)?;
        let plan = Self {
            schema_version: SCHEMA_VERSION.to_owned(),
            algorithm_version: ROUTING_ALGORITHM_VERSION.to_owned(),
            catalog,
            requirements,
            bindings,
            selections,
        };
        plan.validate()?;
        Ok(plan)
    }

    /// Validates schema, algorithm, catalog, requirements, bindings, and determinism.
    pub fn validate(&self) -> Result<(), RoutingError> {
        if self.schema_version != SCHEMA_VERSION {
            return Err(RoutingError::UnsupportedSchema(self.schema_version.clone()));
        }
        if self.algorithm_version != ROUTING_ALGORITHM_VERSION {
            return Err(RoutingError::UnsupportedAlgorithm(
                self.algorithm_version.clone(),
            ));
        }
        self.catalog.validate()?;
        self.requirements.validate()?;
        self.bindings.validate()?;
        if self.catalog.digest()? != self.bindings.catalog_hash {
            return Err(RoutingError::CatalogBinding);
        }
        let candidates = self
            .selections
            .iter()
            .map(|selection| selection.candidate.clone())
            .collect::<Vec<_>>();
        validate_candidate_set(
            &self.catalog,
            &candidates,
            self.bindings.locked_candidate_id.as_deref(),
        )?;
        let expected = compute_selections(
            &self.catalog,
            &self.requirements,
            &self.bindings,
            candidates,
        )?;
        if expected != self.selections {
            return Err(RoutingError::SelectionMismatch);
        }
        Ok(())
    }

    /// Computes a canonical BLAKE3 digest over the validated plan JSON.
    pub fn digest(&self) -> Result<String, RoutingError> {
        self.validate()?;
        let value = serde_json::to_value(self).map_err(|_| RoutingError::Serialization)?;
        Ok(hash_json(&value))
    }

    /// Returns candidate IDs in preference order where `eligible` is `true`.
    pub fn eligible_candidate_ids(&self) -> Vec<String> {
        self.selections
            .iter()
            .filter(|selection| selection.eligible)
            .map(|selection| selection.candidate.id.clone())
            .collect()
    }

    /// Returns the ID of the single eligible candidate, or `None` if none.
    pub fn selected_candidate_id(&self) -> Option<&str> {
        self.selections
            .iter()
            .find(|selection| selection.eligible)
            .map(|selection| selection.candidate.id.as_str())
    }

    /// Returns the smallest context boundary among candidates that may execute.
    pub fn minimum_eligible_context_tokens(&self) -> Option<u64> {
        let descriptors = self
            .catalog
            .descriptors
            .iter()
            .map(|descriptor| (descriptor.id.as_str(), descriptor.context_tokens))
            .collect::<BTreeMap<_, _>>();
        self.selections
            .iter()
            .filter(|selection| selection.eligible)
            .filter_map(|selection| {
                descriptors
                    .get(selection.candidate.descriptor_id.as_str())
                    .copied()
            })
            .min()
    }
}

fn validate_candidate_set(
    catalog: &ModelCatalog,
    candidates: &[RoutingCandidate],
    locked_candidate_id: Option<&str>,
) -> Result<(), RoutingError> {
    if candidates.is_empty() {
        return Err(RoutingError::EmptyCandidates);
    }
    let descriptors = catalog
        .descriptors
        .iter()
        .map(|descriptor| descriptor.id.as_str())
        .collect::<BTreeSet<_>>();
    let mut ids = BTreeSet::new();
    let mut previous = None;
    for candidate in candidates {
        candidate.validate()?;
        if !descriptors.contains(candidate.descriptor_id.as_str()) {
            return Err(RoutingError::UnknownDescriptor(
                candidate.descriptor_id.clone(),
            ));
        }
        if !ids.insert(candidate.id.as_str()) {
            return Err(RoutingError::DuplicateCandidate(candidate.id.clone()));
        }
        let key = (candidate.preference_rank, candidate.id.as_str());
        if previous.is_some_and(|prior| prior >= key) {
            return Err(RoutingError::CandidateOrder);
        }
        previous = Some(key);
    }
    if let Some(locked) = locked_candidate_id
        && !ids.contains(locked)
    {
        return Err(RoutingError::UnknownLockedCandidate(locked.to_owned()));
    }
    Ok(())
}

fn compute_selections(
    catalog: &ModelCatalog,
    requirements: &RoutingRequirements,
    bindings: &RoutingBindings,
    candidates: Vec<RoutingCandidate>,
) -> Result<Vec<RoutingSelection>, RoutingError> {
    let descriptors = catalog
        .descriptors
        .iter()
        .map(|descriptor| (descriptor.id.as_str(), descriptor))
        .collect::<BTreeMap<_, _>>();
    let minimum_context_tokens = requirements
        .min_context_tokens
        .max(requirements.reserved_output_tokens + 1);
    let mut selections = Vec::with_capacity(candidates.len());
    for candidate in candidates {
        let descriptor = descriptors
            .get(candidate.descriptor_id.as_str())
            .copied()
            .ok_or_else(|| RoutingError::UnknownDescriptor(candidate.descriptor_id.clone()))?;
        let missing_capabilities = requirements
            .required_capabilities
            .iter()
            .copied()
            .filter(|capability| !capability.is_supported_by(&descriptor.capabilities))
            .collect::<BTreeSet<_>>();
        let estimated_max_cost_microusd = descriptor
            .pricing
            .as_ref()
            .map(|pricing| {
                pricing.estimate(
                    requirements.max_input_tokens,
                    requirements.reserved_output_tokens,
                )
            })
            .transpose()?;
        let mut reasons = BTreeSet::new();
        if !candidate.enabled {
            reasons.insert(RoutingExclusionReason::Disabled);
        }
        if !candidate.credential_available {
            reasons.insert(RoutingExclusionReason::CredentialUnavailable);
        }
        if !missing_capabilities.is_empty() {
            reasons.insert(RoutingExclusionReason::MissingCapability);
        }
        if descriptor.context_tokens < minimum_context_tokens {
            reasons.insert(RoutingExclusionReason::ContextWindowTooSmall);
        }
        if requirements.require_known_pricing && descriptor.pricing.is_none() {
            reasons.insert(RoutingExclusionReason::PricingUnknown);
        }
        if let Some(maximum) = requirements.max_estimated_cost_microusd {
            match estimated_max_cost_microusd {
                Some(estimate) if estimate > maximum => {
                    reasons.insert(RoutingExclusionReason::CostBudgetExceeded);
                }
                None => {
                    reasons.insert(RoutingExclusionReason::PricingUnknown);
                }
                Some(_) => {}
            }
        }
        if requirements.require_known_latency && descriptor.expected_latency_ms.is_none() {
            reasons.insert(RoutingExclusionReason::LatencyUnknown);
        }
        if let Some(maximum) = requirements.max_latency_ms {
            match descriptor.expected_latency_ms {
                Some(estimate) if estimate > maximum => {
                    reasons.insert(RoutingExclusionReason::LatencyBudgetExceeded);
                }
                None => {
                    reasons.insert(RoutingExclusionReason::LatencyUnknown);
                }
                Some(_) => {}
            }
        }
        if let Some(locked) = bindings.locked_candidate_id.as_deref()
            && candidate.id != locked
        {
            reasons.insert(RoutingExclusionReason::SessionRouteLocked);
        }
        selections.push(RoutingSelection {
            candidate,
            eligible: reasons.is_empty(),
            reasons,
            missing_capabilities,
            estimated_max_cost_microusd,
        });
    }

    if bindings.locked_candidate_id.is_none() && bindings.side_effect_watermark > 0 {
        let mut retained_one = false;
        for selection in &mut selections {
            if selection.eligible && !retained_one {
                retained_one = true;
            } else if selection.eligible {
                selection
                    .reasons
                    .insert(RoutingExclusionReason::FallbackBlockedAfterSideEffect);
                selection.eligible = false;
            }
        }
    }
    Ok(selections)
}

/// Outcome of one provider attempt committed by a routing receipt.
#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "snake_case")]
pub enum RoutingAttemptOutcome {
    /// The attempt failed before producing any visible output.
    FailedBeforeVisibleOutput,
    /// The attempt failed after producing visible output.
    FailedAfterVisibleOutput,
    /// The attempt completed successfully.
    Succeeded,
    /// Runtime cancellation interrupted this attempt.
    Cancelled,
}

/// One secret-free attempt in exact execution order.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct RoutingAttemptReceipt {
    /// ID of the candidate this attempt targeted.
    pub candidate_id: String,
    /// Outcome of the provider attempt.
    pub outcome: RoutingAttemptOutcome,
    /// Hash of the provider error, when `outcome` is not `Succeeded`.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub error_hash: Option<String>,
}

/// Terminal reducer state for one provider step.
#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "snake_case")]
pub enum RoutingReceiptOutcome {
    /// An eligible candidate was selected and succeeded.
    Selected,
    /// All eligible candidates failed before producing visible output.
    Exhausted,
    /// No eligible candidate could execute (empty eligible set or blocked).
    Blocked,
    /// The runtime stopped before invoking an otherwise eligible candidate.
    NotInvoked,
    /// Cooperative cancellation interrupted route execution.
    Cancelled,
    /// Recovery found a provider attempt without a durable terminal receipt.
    Ambiguous,
}

/// Deterministic execution receipt bound to exactly one routing plan.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
pub struct RoutingReceipt {
    /// Schema version enforced against `SCHEMA_VERSION`.
    pub schema_version: String,
    /// Algorithm version enforced against `ROUTING_ALGORITHM_VERSION`.
    pub algorithm_version: String,
    /// Content-addressed digest of the bound `RoutingPlan`.
    pub plan_hash: String,
    /// Monotonic step counter matching the plan bindings.
    pub step: u64,
    /// Monotonic workspace generation matching the plan bindings.
    pub workspace_generation: u64,
    /// State binding matching the plan bindings.
    pub state_binding: String,
    /// Side-effect watermark matching the plan bindings.
    pub side_effect_watermark: u64,
    /// Provider attempts in exact execution order.
    pub attempts: Vec<RoutingAttemptReceipt>,
    /// The ID of the candidate that succeeded, when `outcome` is `Selected`.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub selected_candidate_id: Option<String>,
    /// Terminal reducer state for the step.
    pub outcome: RoutingReceiptOutcome,
}

impl RoutingReceipt {
    /// Constructs a receipt, validates it against the plan, and verifies all invariants.
    pub fn new(
        plan: &RoutingPlan,
        attempts: Vec<RoutingAttemptReceipt>,
        selected_candidate_id: Option<String>,
        outcome: RoutingReceiptOutcome,
    ) -> Result<Self, RoutingError> {
        let receipt = Self {
            schema_version: SCHEMA_VERSION.to_owned(),
            algorithm_version: ROUTING_ALGORITHM_VERSION.to_owned(),
            plan_hash: plan.digest()?,
            step: plan.bindings.step,
            workspace_generation: plan.bindings.workspace_generation,
            state_binding: plan.bindings.state_binding.clone(),
            side_effect_watermark: plan.bindings.side_effect_watermark,
            attempts,
            selected_candidate_id,
            outcome,
        };
        receipt.validate(plan)?;
        Ok(receipt)
    }

    /// Validates schema, algorithm, plan binding, attempt sequence, and outcome consistency.
    pub fn validate(&self, plan: &RoutingPlan) -> Result<(), RoutingError> {
        plan.validate()?;
        if self.schema_version != SCHEMA_VERSION {
            return Err(RoutingError::UnsupportedSchema(self.schema_version.clone()));
        }
        if self.algorithm_version != ROUTING_ALGORITHM_VERSION {
            return Err(RoutingError::UnsupportedAlgorithm(
                self.algorithm_version.clone(),
            ));
        }
        if self.plan_hash != plan.digest()?
            || self.step != plan.bindings.step
            || self.workspace_generation != plan.bindings.workspace_generation
            || self.state_binding != plan.bindings.state_binding
            || self.side_effect_watermark != plan.bindings.side_effect_watermark
        {
            return Err(RoutingError::ReceiptBinding);
        }
        let eligible = plan.eligible_candidate_ids();
        if self.attempts.len() > eligible.len() {
            return Err(RoutingError::ReceiptAttempts);
        }
        for (index, attempt) in self.attempts.iter().enumerate() {
            if eligible.get(index) != Some(&attempt.candidate_id)
                || !valid_digest(&attempt.candidate_id)
            {
                return Err(RoutingError::ReceiptAttempts);
            }
            match attempt.outcome {
                RoutingAttemptOutcome::Succeeded => {
                    if attempt.error_hash.is_some() || index + 1 != self.attempts.len() {
                        return Err(RoutingError::ReceiptAttempts);
                    }
                }
                RoutingAttemptOutcome::FailedBeforeVisibleOutput
                | RoutingAttemptOutcome::FailedAfterVisibleOutput
                | RoutingAttemptOutcome::Cancelled => {
                    if !attempt.error_hash.as_deref().is_some_and(valid_digest) {
                        return Err(RoutingError::ReceiptAttempts);
                    }
                }
            }
        }
        let last = self.attempts.last().map(|attempt| attempt.outcome);
        match self.outcome {
            RoutingReceiptOutcome::Selected => {
                let Some(selected) = self.selected_candidate_id.as_deref() else {
                    return Err(RoutingError::ReceiptOutcome);
                };
                if last != Some(RoutingAttemptOutcome::Succeeded)
                    || self
                        .attempts
                        .last()
                        .map(|attempt| attempt.candidate_id.as_str())
                        != Some(selected)
                {
                    return Err(RoutingError::ReceiptOutcome);
                }
            }
            RoutingReceiptOutcome::Exhausted => {
                if self.selected_candidate_id.is_some()
                    || self.attempts.len() != eligible.len()
                    || self.attempts.iter().any(|attempt| {
                        attempt.outcome != RoutingAttemptOutcome::FailedBeforeVisibleOutput
                    })
                {
                    return Err(RoutingError::ReceiptOutcome);
                }
            }
            RoutingReceiptOutcome::Blocked => {
                let blocked_without_attempt = eligible.is_empty() && self.attempts.is_empty();
                let blocked_after_visible = last
                    == Some(RoutingAttemptOutcome::FailedAfterVisibleOutput)
                    && self.selected_candidate_id.is_none();
                if !blocked_without_attempt && !blocked_after_visible {
                    return Err(RoutingError::ReceiptOutcome);
                }
            }
            RoutingReceiptOutcome::NotInvoked | RoutingReceiptOutcome::Ambiguous => {
                if eligible.is_empty()
                    || !self.attempts.is_empty()
                    || self.selected_candidate_id.is_some()
                {
                    return Err(RoutingError::ReceiptOutcome);
                }
            }
            RoutingReceiptOutcome::Cancelled => {
                let cancelled_before_attempt = eligible.len() > self.attempts.len()
                    && self.attempts.iter().all(|attempt| {
                        attempt.outcome == RoutingAttemptOutcome::FailedBeforeVisibleOutput
                    });
                let cancelled_during_attempt = last == Some(RoutingAttemptOutcome::Cancelled);
                if self.selected_candidate_id.is_some()
                    || (!cancelled_before_attempt && !cancelled_during_attempt)
                {
                    return Err(RoutingError::ReceiptOutcome);
                }
            }
        }
        Ok(())
    }

    /// Computes a canonical BLAKE3 digest over the validated receipt JSON.
    pub fn digest(&self, plan: &RoutingPlan) -> Result<String, RoutingError> {
        self.validate(plan)?;
        let value = serde_json::to_value(self).map_err(|_| RoutingError::Serialization)?;
        Ok(hash_json(&value))
    }
}

fn valid_digest(value: &str) -> bool {
    value.len() == 64
        && value
            .bytes()
            .all(|byte| byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte))
}

/// Routing contract or deterministic reduction failure.
#[derive(Debug, Clone, Error, PartialEq, Eq)]
pub enum RoutingError {
    /// A routing plan, receipt, or catalog carries an unsupported `schema_version`.
    #[error("unsupported routing schema: {0}")]
    UnsupportedSchema(String),
    /// A routing plan carries an unsupported `algorithm_version`.
    #[error("unsupported routing algorithm: {0}")]
    UnsupportedAlgorithm(String),
    /// A model catalog carries an unsupported `catalog_version`.
    #[error("unsupported model catalog: {0}")]
    UnsupportedCatalog(String),
    /// A routing identity field is empty when a non-empty value is required.
    #[error("routing identity is empty")]
    EmptyIdentity,
    /// A model descriptor failed validation (e.g. invalid digest, empty provider).
    #[error("invalid model descriptor: {0}")]
    InvalidDescriptor(String),
    /// The BLAKE3 digest in a model descriptor does not match its payload.
    #[error("model descriptor digest is invalid: {0}")]
    DescriptorDigest(String),
    /// A model catalog was constructed with zero descriptors.
    #[error("model catalog is empty")]
    EmptyCatalog,
    /// The model catalog descriptors are not strictly sorted by digest.
    #[error("model catalog descriptors are not strictly digest-sorted")]
    CatalogOrder,
    /// A routing candidate failed validation (e.g. empty profile, invalid digests).
    #[error("routing candidate is invalid: {0}")]
    InvalidCandidate(String),
    /// The routing candidate ID does not match the material digest.
    #[error("routing candidate digest is invalid: {0}")]
    CandidateDigest(String),
    /// The routing candidate list is empty when at least one is required.
    #[error("routing candidate list is empty")]
    EmptyCandidates,
    /// The routing candidates are not sorted in deterministic preference order.
    #[error("routing candidates are not in deterministic preference order")]
    CandidateOrder,
    /// Two or more routing candidates share the same digest identity.
    #[error("duplicate routing candidate: {0}")]
    DuplicateCandidate(String),
    /// A routing candidate references a descriptor ID absent from the catalog.
    #[error("routing candidate references an unknown descriptor: {0}")]
    UnknownDescriptor(String),
    /// The locked candidate ID in bindings does not match any candidate.
    #[error("locked routing candidate is absent: {0}")]
    UnknownLockedCandidate(String),
    /// Routing requirements failed validation (e.g. zero-valued budgets).
    #[error("routing requirements are invalid")]
    InvalidRequirements,
    /// A binding field is not a valid BLAKE3 hex digest.
    #[error("routing binding is not a canonical digest: {0}")]
    InvalidBinding(String),
    /// The model catalog digest in bindings does not match the catalog's canonical digest.
    #[error("model catalog digest does not match the routing binding")]
    CatalogBinding,
    /// The selections computed during plan validation disagree with the stored selections.
    #[error("routing selections disagree with deterministic reduction")]
    SelectionMismatch,
    /// A routing cost estimate overflowed `u64`.
    #[error("routing cost estimate overflowed")]
    CostOverflow,
    /// Serde serialization of a routing structure failed.
    #[error("routing contract serialization failed")]
    Serialization,
    /// The receipt's binding fields do not match the plan's binding values.
    #[error("routing receipt does not match plan bindings")]
    ReceiptBinding,
    /// The receipt attempt count, order, or per-attempt outcomes violate invariants.
    #[error("routing receipt attempt sequence is invalid")]
    ReceiptAttempts,
    /// The receipt terminal outcome is inconsistent with the attempt sequence.
    #[error("routing receipt outcome is inconsistent")]
    ReceiptOutcome,
}

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

    fn descriptor(model: &str, tools: bool, price: Option<u64>) -> ModelDescriptor {
        ModelDescriptor::new(
            "mock",
            model,
            ProviderCapabilities {
                streaming: false,
                tools,
                structured_output: true,
                multimodal_input: false,
                context_tokens: Some(32_768),
            },
            32_768,
            RoutingContextSource::Provider,
            price.map(|rate| ModelPricing {
                input_microusd_per_million_tokens: rate,
                output_microusd_per_million_tokens: rate,
            }),
            Some(1_000),
        )
        .unwrap()
    }

    fn plan(lock: Option<String>, side_effects: u64) -> RoutingPlan {
        let first = descriptor("a", true, Some(1_000));
        let second = descriptor("b", true, Some(2_000));
        let catalog = ModelCatalog::new(vec![second.clone(), first.clone()]).unwrap();
        let candidates = vec![
            RoutingCandidate::new(
                first.id.clone(),
                0,
                "primary",
                hash_bytes(b"primary-authority"),
                true,
                true,
            )
            .unwrap(),
            RoutingCandidate::new(
                second.id.clone(),
                1,
                "fallback",
                hash_bytes(b"fallback-authority"),
                true,
                true,
            )
            .unwrap(),
        ];
        let bindings = RoutingBindings {
            contract_hash: hash_bytes(b"contract"),
            policy_hash: hash_bytes(b"policy"),
            tool_authority_hash: None,
            catalog_hash: catalog.digest().unwrap(),
            run_controls_hash: hash_bytes(b"resume"),
            step: 0,
            workspace_generation: 0,
            state_binding: hash_bytes(b"workspace"),
            side_effect_watermark: side_effects,
            locked_candidate_id: lock,
        };
        RoutingPlan::build(
            catalog,
            RoutingRequirements {
                required_capabilities: [RoutingCapability::Tools].into_iter().collect(),
                min_context_tokens: 8_192,
                max_input_tokens: 8_192,
                reserved_output_tokens: 1_024,
                max_estimated_cost_microusd: Some(20),
                max_latency_ms: Some(2_000),
                require_known_pricing: true,
                require_known_latency: true,
            },
            bindings,
            candidates,
        )
        .unwrap()
    }

    #[test]
    fn plan_is_canonical_and_content_addressed() {
        let first = plan(None, 0);
        let second = plan(None, 0);
        assert_eq!(first, second);
        assert_eq!(first.digest().unwrap(), second.digest().unwrap());
        assert_eq!(first.eligible_candidate_ids().len(), 2);
    }

    #[test]
    fn side_effects_and_route_lock_remove_fallbacks() {
        let side_effect_plan = plan(None, 1);
        assert_eq!(side_effect_plan.eligible_candidate_ids().len(), 1);
        assert!(
            side_effect_plan.selections[1]
                .reasons
                .contains(&RoutingExclusionReason::FallbackBlockedAfterSideEffect)
        );
        let lock = side_effect_plan.selections[1].candidate.id.clone();
        let locked = plan(Some(lock.clone()), 0);
        assert_eq!(locked.eligible_candidate_ids(), vec![lock]);
        assert!(
            locked.selections[0]
                .reasons
                .contains(&RoutingExclusionReason::SessionRouteLocked)
        );
    }

    #[test]
    fn output_reserve_that_consumes_the_context_excludes_every_candidate() {
        let base = plan(None, 0);
        let candidates = base
            .selections
            .iter()
            .map(|selection| selection.candidate.clone())
            .collect();
        let routed = RoutingPlan::build(
            base.catalog,
            RoutingRequirements {
                min_context_tokens: 1,
                max_input_tokens: 1,
                reserved_output_tokens: 32_768,
                ..base.requirements
            },
            base.bindings,
            candidates,
        )
        .unwrap();

        assert!(routed.eligible_candidate_ids().is_empty());
        assert!(routed.selections.iter().all(|selection| {
            selection
                .reasons
                .contains(&RoutingExclusionReason::ContextWindowTooSmall)
        }));
    }

    #[test]
    fn priced_budget_excludes_unknown_and_expensive_models() {
        let cheap = descriptor("cheap", true, Some(1));
        let unknown = descriptor("unknown", true, None);
        let expensive = descriptor("expensive", true, Some(1_000_000));
        let catalog =
            ModelCatalog::new(vec![cheap.clone(), unknown.clone(), expensive.clone()]).unwrap();
        let candidates = [cheap, unknown, expensive]
            .into_iter()
            .enumerate()
            .map(|(rank, descriptor)| {
                RoutingCandidate::new(
                    descriptor.id,
                    u32::try_from(rank).unwrap(),
                    format!("p{rank}"),
                    hash_bytes(format!("authority-{rank}")),
                    true,
                    true,
                )
                .unwrap()
            })
            .collect();
        let bindings = RoutingBindings {
            contract_hash: hash_bytes(b"contract"),
            policy_hash: hash_bytes(b"policy"),
            tool_authority_hash: None,
            catalog_hash: catalog.digest().unwrap(),
            run_controls_hash: hash_bytes(b"resume"),
            step: 0,
            workspace_generation: 0,
            state_binding: hash_bytes(b"workspace"),
            side_effect_watermark: 0,
            locked_candidate_id: None,
        };
        let routed = RoutingPlan::build(
            catalog,
            RoutingRequirements {
                required_capabilities: BTreeSet::new(),
                min_context_tokens: 1,
                max_input_tokens: 10_000,
                reserved_output_tokens: 1_000,
                max_estimated_cost_microusd: Some(100),
                max_latency_ms: None,
                require_known_pricing: true,
                require_known_latency: false,
            },
            bindings,
            candidates,
        )
        .unwrap();
        assert_eq!(routed.eligible_candidate_ids().len(), 1);
        assert!(routed.selections.iter().any(|selection| {
            selection
                .reasons
                .contains(&RoutingExclusionReason::PricingUnknown)
        }));
        assert!(routed.selections.iter().any(|selection| {
            selection
                .reasons
                .contains(&RoutingExclusionReason::CostBudgetExceeded)
        }));
    }

    #[test]
    fn receipt_commits_exact_attempt_prefix_and_selection() {
        let plan = plan(None, 0);
        let eligible = plan.eligible_candidate_ids();
        let receipt = RoutingReceipt::new(
            &plan,
            vec![
                RoutingAttemptReceipt {
                    candidate_id: eligible[0].clone(),
                    outcome: RoutingAttemptOutcome::FailedBeforeVisibleOutput,
                    error_hash: Some(hash_bytes(b"transport")),
                },
                RoutingAttemptReceipt {
                    candidate_id: eligible[1].clone(),
                    outcome: RoutingAttemptOutcome::Succeeded,
                    error_hash: None,
                },
            ],
            Some(eligible[1].clone()),
            RoutingReceiptOutcome::Selected,
        )
        .unwrap();
        receipt.validate(&plan).unwrap();
        assert!(valid_digest(&receipt.digest(&plan).unwrap()));
    }

    #[test]
    fn plan_and_receipt_tampering_fail_closed() {
        let mut routed = plan(None, 0);
        routed.selections[0].eligible = false;
        assert_eq!(routed.validate(), Err(RoutingError::SelectionMismatch));

        let routed = plan(None, 0);
        let error =
            RoutingReceipt::new(&routed, Vec::new(), None, RoutingReceiptOutcome::Exhausted)
                .unwrap_err();
        assert_eq!(error, RoutingError::ReceiptOutcome);

        let mut unknown_field = serde_json::to_value(&routed).unwrap();
        unknown_field["uncommittedDiagnostic"] = serde_json::json!(true);
        assert!(serde_json::from_value::<RoutingPlan>(unknown_field).is_err());
    }
}