Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

36.6 KB
Raw Blame
//! Minimal storage-neutral predicate-index intermediate representation.
#![deny(missing_docs)]

use std::{
    cmp::Ordering,
    collections::{BTreeSet, HashSet},
};

use chrono::{DateTime, Utc};
use serde::{Deserialize, Deserializer, Serialize};
use thiserror::Error;

#[cfg(test)]
mod test;

/// Maximum expression depth accepted by the generic index.
pub const MAX_EXPRESSION_DEPTH: usize = 64;
/// Maximum expression nodes accepted by one query.
pub const MAX_EXPRESSION_NODES: usize = 2_048;
/// Maximum query page size.
pub const MAX_QUERY_LIMIT: u16 = 500;
/// Maximum bytes in a token.
pub const MAX_TOKEN_BYTES: usize = 128;
/// Maximum bytes in an exact value.
pub const MAX_EXACT_VALUE_BYTES: usize = 16 * 1_024;
/// Maximum distinct attribute names in one index document or patch.
/// Set-valued attributes may contain any number of individually bounded values.
pub const MAX_ATTRIBUTES_PER_DOCUMENT: usize = 256;
/// Maximum distinct records whose optimistic projections may be merged into one query.
pub const MAX_OPTIMISTIC_RECORDS_PER_QUERY: usize = 128;

/// A stable, opaque vocabulary token owned by a profile compiler.
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize)]
#[serde(transparent)]
pub struct Token(String);

impl<'de> Deserialize<'de> for Token {
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        Self::new(String::deserialize(deserializer)?).map_err(serde::de::Error::custom)
    }
}

impl Token {
    /// Construct a validated token.
    pub fn new(value: impl Into<String>) -> Result<Self, ValidationError> {
        let value = value.into();
        let valid_bytes = !value.is_empty()
            && value.len() <= MAX_TOKEN_BYTES
            && value
                .bytes()
                .all(|byte| byte.is_ascii_alphanumeric() || b"._:-".contains(&byte));
        if !valid_bytes {
            return Err(ValidationError::InvalidToken(value));
        }
        Ok(Self(value))
    }

    /// Read the token text.
    pub fn as_str(&self) -> &str {
        &self.0
    }
}

/// A versioned projection and compiler profile.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(transparent)]
pub struct Profile(Token);

impl Profile {
    /// Construct a profile from a validated token.
    pub fn new(token: Token) -> Self {
        Self(token)
    }

    /// Read the profile token.
    pub fn token(&self) -> &Token {
        &self.0
    }
}

/// A normalized GraphQL cache record key.
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize)]
#[serde(transparent)]
pub struct RecordKey(String);

impl<'de> Deserialize<'de> for RecordKey {
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        Self::new(String::deserialize(deserializer)?).map_err(serde::de::Error::custom)
    }
}

impl RecordKey {
    /// Construct a non-empty bounded normalized record key.
    pub fn new(value: impl Into<String>) -> Result<Self, ValidationError> {
        let value = value.into();
        if value.is_empty() || value.len() > MAX_EXACT_VALUE_BYTES {
            return Err(ValidationError::InvalidRecordKey);
        }
        Ok(Self(value))
    }

    /// Read the normalized key.
    pub fn as_str(&self) -> &str {
        &self.0
    }
}

/// Canonical bytes for an exact-match posting value.
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize)]
#[serde(transparent)]
pub struct ExactValue(Vec<u8>);

impl<'de> Deserialize<'de> for ExactValue {
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        Self::new(Vec::<u8>::deserialize(deserializer)?).map_err(serde::de::Error::custom)
    }
}

impl ExactValue {
    /// Construct a bounded exact value.
    pub fn new(bytes: impl Into<Vec<u8>>) -> Result<Self, ValidationError> {
        let bytes = bytes.into();
        if bytes.len() > MAX_EXACT_VALUE_BYTES {
            return Err(ValidationError::ExactValueTooLarge(bytes.len()));
        }
        Ok(Self(bytes))
    }

    /// Construct a canonical UTF-8 value.
    pub fn utf8(value: impl AsRef<str>) -> Result<Self, ValidationError> {
        Self::new(value.as_ref().as_bytes())
    }

    /// Read the canonical bytes.
    pub fn as_bytes(&self) -> &[u8] {
        &self.0
    }
}

/// One side of an integer range.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum RangeBound {
    /// Include the bound value.
    Inclusive(i64),
    /// Exclude the bound value.
    Exclusive(i64),
}

/// A bounded Boolean predicate over generic facts.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum PredicateExpr {
    /// Match every document in the selected profile/partition universe.
    All,
    /// Match no documents.
    None,
    /// Match an exact posting.
    Exact {
        /// Fact vocabulary token.
        attribute: Token,
        /// Canonical exact value.
        value: ExactValue,
    },
    /// Match an ordered integer range.
    I64Range {
        /// Fact vocabulary token.
        attribute: Token,
        /// Optional lower bound.
        lower: Option<RangeBound>,
        /// Optional upper bound.
        upper: Option<RangeBound>,
    },
    /// Intersect two result sets.
    And(Box<Self>, Box<Self>),
    /// Union two result sets.
    Or(Box<Self>, Box<Self>),
    /// Subtract a result set from the profile/partition universe.
    Not(Box<Self>),
    /// Match at least one value of an exact attribute.
    ExactExists {
        /// Fact vocabulary token.
        attribute: Token,
    },
    /// Exclusive keyset boundary over a sort fact and normalized key.
    After {
        /// Sort attribute.
        attribute: Token,
        /// Last returned sort value.
        value: i64,
        /// Last returned normalized key.
        key: RecordKey,
        /// Value ordering.
        direction: SortDirection,
        /// Tie-break ordering.
        tie_direction: SortDirection,
    },
}

impl PredicateExpr {
    /// Validate bounds and apply non-expanding Boolean identities.
    pub fn validate_and_simplify(self) -> Result<Self, ValidationError> {
        let mut stack = vec![(&self, 1usize)];
        let mut nodes = 0usize;
        while let Some((expr, depth)) = stack.pop() {
            if depth > MAX_EXPRESSION_DEPTH {
                return Err(ValidationError::ExpressionDepth);
            }
            nodes += 1;
            if nodes > MAX_EXPRESSION_NODES {
                return Err(ValidationError::ExpressionNodes);
            }
            match expr {
                Self::And(left, right) | Self::Or(left, right) => {
                    stack.push((left, depth + 1));
                    stack.push((right, depth + 1));
                }
                Self::Not(expr) => stack.push((expr, depth + 1)),
                Self::All
                | Self::None
                | Self::Exact { .. }
                | Self::I64Range { .. }
                | Self::ExactExists { .. }
                | Self::After { .. } => {}
            }
        }

        simplify(self)
    }
}

/// One exact fact in an index document.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct ExactFact {
    /// Fact vocabulary token.
    pub attribute: Token,
    /// Canonical exact value.
    pub value: ExactValue,
}

/// One ordered integer fact in an index document.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct IntegerFact {
    /// Fact vocabulary token.
    pub attribute: Token,
    /// Integer value.
    pub value: i64,
}

/// Generic projection of one normalized cache record.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct IndexDocument {
    /// Normalized cache record key.
    pub record_key: RecordKey,
    /// Projection profile.
    pub profile: Profile,
    /// Entity partition token.
    pub partition: Token,
    /// Exact-match facts.
    pub exact_facts: Vec<ExactFact>,
    /// Ordered integer facts.
    pub integer_facts: Vec<IntegerFact>,
    /// Ordered sort facts.
    pub sort_facts: Vec<IntegerFact>,
}

fn validate_attribute_count<'a>(
    attributes: impl IntoIterator<Item = &'a Token>,
) -> Result<(), ValidationError> {
    let mut distinct = HashSet::new();
    for attribute in attributes {
        distinct.insert(attribute);
        if distinct.len() > MAX_ATTRIBUTES_PER_DOCUMENT {
            return Err(ValidationError::DocumentAttributes);
        }
    }
    Ok(())
}

impl IndexDocument {
    /// Put facts in deterministic order and remove duplicate membership facts.
    pub fn canonicalize(&mut self) {
        self.exact_facts.sort();
        self.exact_facts.dedup();
        self.integer_facts.sort();
        self.integer_facts.dedup();
        self.sort_facts.sort();
    }

    /// Validate bounded attribute counts and unique sort attributes.
    pub fn validate(&self) -> Result<(), ValidationError> {
        validate_attribute_count(
            self.exact_facts
                .iter()
                .map(|fact| &fact.attribute)
                .chain(self.integer_facts.iter().map(|fact| &fact.attribute))
                .chain(self.sort_facts.iter().map(|fact| &fact.attribute)),
        )?;
        let mut sort_attributes = HashSet::new();
        if self
            .sort_facts
            .iter()
            .any(|fact| !sort_attributes.insert(&fact.attribute))
        {
            return Err(ValidationError::DuplicateSortFact);
        }
        Ok(())
    }

    /// Evaluate an expression against this document's facts.
    pub fn matches(&self, expr: &PredicateExpr) -> bool {
        match expr {
            PredicateExpr::All => true,
            PredicateExpr::None => false,
            PredicateExpr::Exact { attribute, value } => self
                .exact_facts
                .iter()
                .any(|fact| &fact.attribute == attribute && &fact.value == value),
            PredicateExpr::ExactExists { attribute } => self
                .exact_facts
                .iter()
                .any(|fact| &fact.attribute == attribute),
            PredicateExpr::I64Range {
                attribute,
                lower,
                upper,
            } => self.integer_facts.iter().any(|fact| {
                &fact.attribute == attribute
                    && lower.is_none_or(|bound| lower_matches(fact.value, bound))
                    && upper.is_none_or(|bound| upper_matches(fact.value, bound))
            }),
            PredicateExpr::After {
                attribute,
                value,
                key,
                direction,
                tie_direction,
            } => self
                .sort_facts
                .iter()
                .find(|fact| &fact.attribute == attribute)
                .is_some_and(|fact| {
                    sorts_after(
                        (fact.value, &self.record_key),
                        (*value, key),
                        *direction,
                        *tie_direction,
                    )
                }),
            PredicateExpr::And(left, right) => self.matches(left) && self.matches(right),
            PredicateExpr::Or(left, right) => self.matches(left) || self.matches(right),
            PredicateExpr::Not(expr) => !self.matches(expr),
        }
    }
}

/// Predicate for one entity partition.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct PartitionPredicate {
    /// Partition vocabulary token.
    pub partition: Token,
    /// Predicate evaluated only inside that partition's universe.
    pub predicate: PredicateExpr,
}

/// Ordering direction for a local initial page.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum SortDirection {
    /// Lowest values first.
    Asc,
    /// Highest values first.
    Desc,
}

/// Unvalidated generic exact-index query descriptor.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct IndexQuery {
    /// Required profile.
    pub profile: Profile,
    /// Complete partition predicates.
    pub partitions: Vec<PartitionPredicate>,
    /// Sort-fact attribute.
    pub sort_attribute: Token,
    /// Sort direction.
    pub sort_direction: SortDirection,
    /// Stable record-key tie-break direction.
    pub tie_break_direction: SortDirection,
    /// Bounded initial-page size.
    pub limit: u16,
}

/// Validated generic exact-index query.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
#[serde(transparent)]
pub struct ValidatedIndexQuery(IndexQuery);

impl<'de> Deserialize<'de> for ValidatedIndexQuery {
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        Self::new(IndexQuery::deserialize(deserializer)?).map_err(serde::de::Error::custom)
    }
}

impl ValidatedIndexQuery {
    /// Validate and simplify a query descriptor.
    pub fn new(mut query: IndexQuery) -> Result<Self, ValidationError> {
        if query.limit == 0 || query.limit > MAX_QUERY_LIMIT {
            return Err(ValidationError::Limit(query.limit));
        }
        if query.partitions.is_empty() {
            return Err(ValidationError::NoPartitions);
        }
        let mut partitions = HashSet::new();
        for partition in &mut query.partitions {
            if !partitions.insert(&partition.partition) {
                return Err(ValidationError::DuplicatePartition);
            }
            partition.predicate = std::mem::replace(&mut partition.predicate, PredicateExpr::None)
                .validate_and_simplify()?;
        }
        Ok(Self(query))
    }

    /// Access the validated descriptor.
    pub fn as_query(&self) -> &IndexQuery {
        &self.0
    }

    /// Clone this query with a different validated initial-page limit.
    pub fn with_limit(&self, limit: u16) -> Result<Self, ValidationError> {
        let mut query = self.0.clone();
        query.limit = limit;
        Self::new(query)
    }

    /// Add an exclusive, direction-aware keyset boundary without changing sort semantics.
    pub fn after(&self, value: i64, key: RecordKey) -> Result<Self, ValidationError> {
        let mut query = self.0.clone();
        for partition in &mut query.partitions {
            partition.predicate = PredicateExpr::And(
                Box::new(partition.predicate.clone()),
                Box::new(PredicateExpr::After {
                    attribute: query.sort_attribute.clone(),
                    value,
                    key: key.clone(),
                    direction: query.sort_direction,
                    tie_direction: query.tie_break_direction,
                }),
            );
        }
        Self::new(query)
    }

    /// Whether a row sorts after a keyset boundary, as [`Self::after`] decides.
    pub fn sorts_after(&self, row: (i64, &RecordKey), boundary: (i64, &RecordKey)) -> bool {
        sorts_after(
            row,
            boundary,
            self.0.sort_direction,
            self.0.tie_break_direction,
        )
    }

    /// Whether this query can inspect documents in `profile` and `partition`.
    pub fn includes_scope(&self, profile: &Profile, partition: &Token) -> bool {
        self.0.profile == *profile
            && self
                .0
                .partitions
                .iter()
                .any(|candidate| candidate.partition == *partition)
    }

    /// Whether this query depends on an attribute in one selected partition.
    ///
    /// The sort attribute is always a dependency. Predicate attributes are
    /// collected without expanding the Boolean expression.
    pub fn depends_on_attribute(&self, partition: &Token, attribute: &Token) -> bool {
        let Some(candidate) = self
            .0
            .partitions
            .iter()
            .find(|candidate| candidate.partition == *partition)
        else {
            return false;
        };
        self.0.sort_attribute == *attribute
            || expression_depends_on(&candidate.predicate, attribute)
    }

    /// Collect predicate and sort attributes inspected in one selected partition.
    pub fn dependent_attributes(&self, partition: &Token) -> BTreeSet<Token> {
        let mut attributes = BTreeSet::from([self.0.sort_attribute.clone()]);
        if let Some(candidate) = self
            .0
            .partitions
            .iter()
            .find(|candidate| candidate.partition == *partition)
        {
            collect_expression_attributes(&candidate.predicate, &mut attributes);
        }
        attributes
    }
}

/// Why a known projection is not currently safe to query.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum ProjectionIncompleteKind {
    /// An update may have changed indexed facts.
    Dirty,
    /// A supported normalized record arrived without its required projection.
    Missing,
    /// The record carries a projection version this client cannot interpret.
    IncompatibleVersion,
}

/// Current effective uncertainty after composing optimistic projection changes.
///
/// `AllExcept` is needed so an exact later patch can make one attribute known
/// after a wildcard unknown mutation without incorrectly clearing uncertainty
/// for every other possible profile attribute.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum OptimisticUncertainty {
    /// Only the listed attributes are uncertain.
    Attributes(BTreeSet<Token>),
    /// Every attribute except the listed attributes is uncertain.
    AllExcept(BTreeSet<Token>),
}

impl Default for OptimisticUncertainty {
    fn default() -> Self {
        Self::Attributes(BTreeSet::new())
    }
}

impl OptimisticUncertainty {
    /// Whether no attribute is uncertain.
    pub fn is_empty(&self) -> bool {
        matches!(self, Self::Attributes(attributes) if attributes.is_empty())
    }

    /// Whether one attribute remains uncertain.
    pub fn affects(&self, attribute: &Token) -> bool {
        match self {
            Self::Attributes(attributes) => attributes.contains(attribute),
            Self::AllExcept(certain) => !certain.contains(attribute),
        }
    }

    /// Mark listed attributes uncertain, or every attribute when the slice is empty.
    pub fn mark(&mut self, attributes: &[Token]) {
        if attributes.is_empty() {
            *self = Self::AllExcept(BTreeSet::new());
            return;
        }
        match self {
            Self::Attributes(uncertain) => uncertain.extend(attributes.iter().cloned()),
            Self::AllExcept(certain) => {
                for attribute in attributes {
                    certain.remove(attribute);
                }
            }
        }
    }

    /// Mark attributes exact after a deterministic replacement patch.
    pub fn clear(&mut self, attributes: impl IntoIterator<Item = Token>) {
        match self {
            Self::Attributes(uncertain) => {
                for attribute in attributes {
                    uncertain.remove(&attribute);
                }
            }
            Self::AllExcept(certain) => certain.extend(attributes),
        }
    }
}

/// Current fully composed optimistic projection for one record key.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum OptimisticProjectionState {
    /// Complete effective facts.
    Complete(IndexDocument),
    /// Effective tombstone. Authoritative facts remain suppressed.
    Deleted {
        /// Normalized record key.
        record_key: RecordKey,
        /// Projection profile.
        profile: Profile,
        /// Entity partition.
        partition: Token,
    },
    /// Authority is suppressed, but exact effective facts cannot be proven.
    Incomplete {
        /// Normalized record key.
        record_key: RecordKey,
        /// Projection profile.
        profile: Profile,
        /// Entity partition.
        partition: Token,
        /// Why exact composition failed.
        kind: ProjectionIncompleteKind,
    },
}

impl OptimisticProjectionState {
    /// Read the affected normalized record key.
    pub fn record_key(&self) -> &RecordKey {
        match self {
            Self::Complete(document) => &document.record_key,
            Self::Deleted { record_key, .. } | Self::Incomplete { record_key, .. } => record_key,
        }
    }

    /// Read the effective profile.
    pub fn profile(&self) -> &Profile {
        match self {
            Self::Complete(document) => &document.profile,
            Self::Deleted { profile, .. } | Self::Incomplete { profile, .. } => profile,
        }
    }

    /// Read the effective partition.
    pub fn partition(&self) -> &Token {
        match self {
            Self::Complete(document) => &document.partition,
            Self::Deleted { partition, .. } | Self::Incomplete { partition, .. } => partition,
        }
    }

    /// Validate complete facts when this state contains a document.
    pub fn validate(&self) -> Result<(), ValidationError> {
        match self {
            Self::Complete(document) => document.validate(),
            Self::Deleted { .. } | Self::Incomplete { .. } => Ok(()),
        }
    }
}

/// Effective shadow value whose owner already has a durable mutation ID.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct EffectiveOptimisticProjection {
    /// Greatest active mutation ID affecting this record.
    pub owner: u64,
    /// Fully composed projection, tombstone, or incomplete marker.
    pub state: OptimisticProjectionState,
    /// Uncertainty still effective after all active mutations.
    pub uncertainty: OptimisticUncertainty,
}

impl EffectiveOptimisticProjection {
    /// Validate owner and effective projection bounds.
    pub fn validate(&self) -> Result<(), ValidationError> {
        if self.owner == 0 {
            return Err(ValidationError::InvalidOptimisticOwner);
        }
        self.state.validate()
    }
}

/// Effective shadow value awaiting the mutation ID assigned during enqueue.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct PendingOptimisticProjection {
    /// Fully composed projection, tombstone, or incomplete marker.
    pub state: OptimisticProjectionState,
    /// Uncertainty still effective after applying the new mutation.
    pub uncertainty: OptimisticUncertainty,
}

impl PendingOptimisticProjection {
    /// Validate effective projection bounds.
    pub fn validate(&self) -> Result<(), ValidationError> {
        self.state.validate()
    }
}

/// One ordered optimistic change to a generic projection.
///
/// Optimistic changes are layered over authoritative [`IndexDocument`] values;
/// they never overwrite the authoritative projection needed for rollback.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum OptimisticProjectionMutation {
    /// Replace the effective projection with a complete optimistic document.
    Replace(IndexDocument),
    /// Replace selected attributes on the preceding effective projection.
    Patch {
        /// Normalized record key.
        record_key: RecordKey,
        /// Projection profile.
        profile: Profile,
        /// Entity partition.
        partition: Token,
        /// Complete replacement values for each exact attribute.
        exact: Vec<ExactAttributePatch>,
        /// Complete replacement values for each integer attribute.
        integers: Vec<IntegerAttributePatch>,
        /// Replacement values for sort attributes.
        sorts: Vec<IntegerFact>,
    },
    /// Hide the record from the effective local view while retaining its base projection.
    Delete {
        /// Normalized record key.
        record_key: RecordKey,
        /// Projection profile.
        profile: Profile,
        /// Entity partition.
        partition: Token,
    },
    /// The optimistic mutation may change facts that were not deterministically projected.
    Unknown {
        /// Normalized record key.
        record_key: RecordKey,
        /// Projection profile.
        profile: Profile,
        /// Entity partition.
        partition: Token,
        /// Potentially changed attributes. Empty means every attribute.
        affected_attributes: Vec<Token>,
    },
    /// Edit individual set members without replacing other contributors.
    PatchExact {
        /// Normalized record key.
        record_key: RecordKey,
        /// Projection profile.
        profile: Profile,
        /// Entity partition.
        partition: Token,
        /// Members to remove before inserting replacements.
        remove: Vec<ExactFact>,
        /// Members to insert (idempotently).
        insert: Vec<ExactFact>,
    },
}

/// Complete replacement of one exact attribute's values.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ExactAttributePatch {
    /// Attribute to replace.
    pub attribute: Token,
    /// New values. Empty removes the attribute from the effective projection.
    pub values: Vec<ExactValue>,
}

/// Complete replacement of one integer attribute's values.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct IntegerAttributePatch {
    /// Attribute to replace.
    pub attribute: Token,
    /// New values. Empty removes the attribute from the effective projection.
    pub values: Vec<i64>,
}

impl OptimisticProjectionMutation {
    /// Validate the optimistic projection payload.
    pub fn validate(&self) -> Result<(), ValidationError> {
        let Self::Patch {
            exact,
            integers,
            sorts,
            ..
        } = self
        else {
            return match self {
                Self::Replace(document) => document.validate(),
                Self::Delete { .. } | Self::Unknown { .. } => Ok(()),
                Self::PatchExact { remove, insert, .. } => validate_attribute_count(
                    remove.iter().chain(insert).map(|fact| &fact.attribute),
                ),
                Self::Patch { .. } => unreachable!(),
            };
        };

        validate_attribute_count(
            exact
                .iter()
                .map(|patch| &patch.attribute)
                .chain(integers.iter().map(|patch| &patch.attribute))
                .chain(sorts.iter().map(|fact| &fact.attribute)),
        )?;
        let mut attributes = HashSet::new();
        if exact
            .iter()
            .any(|patch| !attributes.insert(&patch.attribute))
        {
            return Err(ValidationError::DuplicateExactPatchAttribute);
        }
        attributes.clear();
        if integers
            .iter()
            .any(|patch| !attributes.insert(&patch.attribute))
        {
            return Err(ValidationError::DuplicateIntegerPatchAttribute);
        }
        attributes.clear();
        if sorts.iter().any(|fact| !attributes.insert(&fact.attribute)) {
            return Err(ValidationError::DuplicateSortPatchAttribute);
        }
        Ok(())
    }

    /// Read the affected normalized record key.
    pub fn record_key(&self) -> &RecordKey {
        match self {
            Self::Replace(document) => &document.record_key,
            Self::Patch { record_key, .. }
            | Self::Delete { record_key, .. }
            | Self::Unknown { record_key, .. }
            | Self::PatchExact { record_key, .. } => record_key,
        }
    }

    /// Read the affected profile.
    pub fn profile(&self) -> &Profile {
        match self {
            Self::Replace(document) => &document.profile,
            Self::Patch { profile, .. }
            | Self::Delete { profile, .. }
            | Self::Unknown { profile, .. }
            | Self::PatchExact { profile, .. } => profile,
        }
    }

    /// Read the affected partition.
    pub fn partition(&self) -> &Token {
        match self {
            Self::Replace(document) => &document.partition,
            Self::Patch { partition, .. }
            | Self::Delete { partition, .. }
            | Self::Unknown { partition, .. }
            | Self::PatchExact { partition, .. } => partition,
        }
    }

    /// Whether uncertainty in this mutation intersects a validated query.
    pub fn makes_query_uncertain(&self, query: &ValidatedIndexQuery) -> bool {
        let Self::Unknown {
            profile,
            partition,
            affected_attributes,
            ..
        } = self
        else {
            return false;
        };
        query.includes_scope(profile, partition)
            && (affected_attributes.is_empty()
                || affected_attributes
                    .iter()
                    .any(|attribute| query.depends_on_attribute(partition, attribute)))
    }
}

/// Validation failure for generic index input.
#[derive(Debug, Error, PartialEq, Eq)]
pub enum ValidationError {
    /// A token is empty, too long, or contains non-portable bytes.
    #[error("invalid predicate-index token `{0}`")]
    InvalidToken(String),
    /// A normalized record key is empty or too large.
    #[error("invalid normalized record key")]
    InvalidRecordKey,
    /// An exact value is too large.
    #[error("exact value has {0} bytes")]
    ExactValueTooLarge(usize),
    /// The expression is too deep.
    #[error("predicate expression exceeds maximum depth")]
    ExpressionDepth,
    /// The expression contains too many nodes.
    #[error("predicate expression exceeds maximum node count")]
    ExpressionNodes,
    /// An integer range is inverted or empty.
    #[error("invalid integer range")]
    InvalidRange,
    /// A document or patch contains too many distinct attribute names.
    #[error("index document contains too many distinct attributes")]
    DocumentAttributes,
    /// A document has more than one sort value for an attribute.
    #[error("duplicate sort fact attribute")]
    DuplicateSortFact,
    /// An optimistic patch repeats an exact attribute.
    #[error("duplicate exact patch attribute")]
    DuplicateExactPatchAttribute,
    /// An optimistic patch repeats an integer attribute.
    #[error("duplicate integer patch attribute")]
    DuplicateIntegerPatchAttribute,
    /// An optimistic patch repeats a sort attribute.
    #[error("duplicate sort patch attribute")]
    DuplicateSortPatchAttribute,
    /// A query has no partition universes.
    #[error("index query has no partitions")]
    NoPartitions,
    /// A query repeats a partition.
    #[error("index query repeats a partition")]
    DuplicatePartition,
    /// A query limit is zero or too large.
    #[error("invalid index query limit {0}")]
    Limit(u16),
    /// A durable effective optimistic projection has no active owner.
    #[error("effective optimistic projection owner must be non-zero")]
    InvalidOptimisticOwner,
}

/// Pure reference result used for adapter conformance tests.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ReferenceHit {
    /// Normalized cache record key.
    pub record_key: RecordKey,
    /// Sort value selected by the query.
    pub sort_value: i64,
}

/// Evaluate a validated query over generic documents without storage.
pub fn evaluate_reference(
    query: &ValidatedIndexQuery,
    documents: &[IndexDocument],
) -> Vec<ReferenceHit> {
    let query = query.as_query();
    let mut hits = documents
        .iter()
        .filter(|document| document.profile == query.profile)
        .filter_map(|document| {
            let partition = query
                .partitions
                .iter()
                .find(|partition| partition.partition == document.partition)?;
            if !document.matches(&partition.predicate) {
                return None;
            }
            let sort_value = document
                .sort_facts
                .iter()
                .find(|fact| fact.attribute == query.sort_attribute)?
                .value;
            Some(ReferenceHit {
                record_key: document.record_key.clone(),
                sort_value,
            })
        })
        .collect::<Vec<_>>();

    hits.sort_by(|left, right| {
        directional_cmp(left.sort_value.cmp(&right.sort_value), query.sort_direction).then_with(
            || {
                directional_cmp(
                    left.record_key.cmp(&right.record_key),
                    query.tie_break_direction,
                )
            },
        )
    });
    hits.truncate(usize::from(query.limit));
    hits
}

/// Encode a UTC timestamp as signed Unix microseconds without millisecond loss.
pub fn utc_timestamp_micros(value: DateTime<Utc>) -> i64 {
    value.timestamp_micros()
}

fn expression_depends_on(expr: &PredicateExpr, attribute: &Token) -> bool {
    match expr {
        PredicateExpr::Exact {
            attribute: candidate,
            ..
        }
        | PredicateExpr::I64Range {
            attribute: candidate,
            ..
        }
        | PredicateExpr::ExactExists {
            attribute: candidate,
        }
        | PredicateExpr::After {
            attribute: candidate,
            ..
        } => candidate == attribute,
        PredicateExpr::And(left, right) | PredicateExpr::Or(left, right) => {
            expression_depends_on(left, attribute) || expression_depends_on(right, attribute)
        }
        PredicateExpr::Not(expr) => expression_depends_on(expr, attribute),
        PredicateExpr::All | PredicateExpr::None => false,
    }
}

fn collect_expression_attributes(expr: &PredicateExpr, attributes: &mut BTreeSet<Token>) {
    match expr {
        PredicateExpr::Exact { attribute, .. }
        | PredicateExpr::I64Range { attribute, .. }
        | PredicateExpr::ExactExists { attribute }
        | PredicateExpr::After { attribute, .. } => {
            attributes.insert(attribute.clone());
        }
        PredicateExpr::And(left, right) | PredicateExpr::Or(left, right) => {
            collect_expression_attributes(left, attributes);
            collect_expression_attributes(right, attributes);
        }
        PredicateExpr::Not(expr) => collect_expression_attributes(expr, attributes),
        PredicateExpr::All | PredicateExpr::None => {}
    }
}

fn simplify(expr: PredicateExpr) -> Result<PredicateExpr, ValidationError> {
    Ok(match expr {
        PredicateExpr::And(left, right) => match (simplify(*left)?, simplify(*right)?) {
            (PredicateExpr::None, _) | (_, PredicateExpr::None) => PredicateExpr::None,
            (PredicateExpr::All, right) => right,
            (left, PredicateExpr::All) => left,
            (left, right) => PredicateExpr::And(Box::new(left), Box::new(right)),
        },
        PredicateExpr::Or(left, right) => match (simplify(*left)?, simplify(*right)?) {
            (PredicateExpr::All, _) | (_, PredicateExpr::All) => PredicateExpr::All,
            (PredicateExpr::None, right) => right,
            (left, PredicateExpr::None) => left,
            (left, right) => PredicateExpr::Or(Box::new(left), Box::new(right)),
        },
        PredicateExpr::Not(expr) => match simplify(*expr)? {
            PredicateExpr::All => PredicateExpr::None,
            PredicateExpr::None => PredicateExpr::All,
            PredicateExpr::Not(expr) => *expr,
            expr => PredicateExpr::Not(Box::new(expr)),
        },
        PredicateExpr::I64Range {
            attribute,
            lower,
            upper,
        } => {
            validate_range(lower, upper)?;
            PredicateExpr::I64Range {
                attribute,
                lower,
                upper,
            }
        }
        expr @ (PredicateExpr::All
        | PredicateExpr::None
        | PredicateExpr::Exact { .. }
        | PredicateExpr::ExactExists { .. }
        | PredicateExpr::After { .. }) => expr,
    })
}

fn validate_range(
    lower: Option<RangeBound>,
    upper: Option<RangeBound>,
) -> Result<(), ValidationError> {
    let Some(lower) = lower else { return Ok(()) };
    let Some(upper) = upper else { return Ok(()) };
    let lower_value = match lower {
        RangeBound::Inclusive(value) | RangeBound::Exclusive(value) => value,
    };
    let upper_value = match upper {
        RangeBound::Inclusive(value) | RangeBound::Exclusive(value) => value,
    };
    let non_empty_at_equality =
        matches!(lower, RangeBound::Inclusive(_)) && matches!(upper, RangeBound::Inclusive(_));
    if lower_value > upper_value || (lower_value == upper_value && !non_empty_at_equality) {
        return Err(ValidationError::InvalidRange);
    }
    Ok(())
}

fn lower_matches(value: i64, bound: RangeBound) -> bool {
    match bound {
        RangeBound::Inclusive(lower) => value >= lower,
        RangeBound::Exclusive(lower) => value > lower,
    }
}

fn upper_matches(value: i64, bound: RangeBound) -> bool {
    match bound {
        RangeBound::Inclusive(upper) => value <= upper,
        RangeBound::Exclusive(upper) => value < upper,
    }
}

fn sorts_after(
    (value, key): (i64, &RecordKey),
    (boundary_value, boundary_key): (i64, &RecordKey),
    direction: SortDirection,
    tie_direction: SortDirection,
) -> bool {
    directional_cmp(value.cmp(&boundary_value), direction)
        .then_with(|| directional_cmp(key.cmp(boundary_key), tie_direction))
        == Ordering::Greater
}

fn directional_cmp(ordering: Ordering, direction: SortDirection) -> Ordering {
    match direction {
        SortDirection::Asc => ordering,
        SortDirection::Desc => ordering.reverse(),
    }
}