icydb-core 0.188.3

//! Module: index::predicate
//! Responsibility: compiled index-only predicate program model + execution.
//! Does not own: semantic predicate resolution or planner route policy.
//! Boundary: query/load paths use this for conservative index prefiltering.

pub(crate) mod compile;
#[cfg(test)]
mod tests;

use crate::{
    db::index::{EncodedValue, IndexKey},
    error::InternalError,
    value::Value,
};
#[cfg(test)]
use crate::{db::predicate::Predicate, model::index::IndexModel};
use std::cell::Cell;

pub(crate) use compile::{
    IndexCompilePolicy, compile_index_program, compile_index_program_for_targets,
};

/// Resolve the canonical generated predicate semantics for one filtered index.
#[cfg(test)]
pub(in crate::db) fn canonical_index_predicate(index: &IndexModel) -> Option<&'static Predicate> {
    index.predicate_semantics()
}

///
/// IndexPredicateProgram
///
/// Index-only predicate program compiled against index component positions.
/// This is a conservative subset used for raw-index-key predicate evaluation.
///

#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) enum IndexPredicateProgram {
    True,
    False,
    And(Vec<Self>),
    Or(Vec<Self>),
    Not(Box<Self>),
    Compare {
        component_index: usize,
        op: IndexCompareOp,
        literal: IndexLiteral,
    },
}

///
/// IndexCompareOp
///
/// Operator subset that can be evaluated directly on canonical encoded index bytes.
///

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum IndexCompareOp {
    Eq,
    Ne,
    Lt,
    Lte,
    Gt,
    Gte,
    In,
    NotIn,
}

///
/// IndexLiteral
///
/// Encoded literal payload used by one index-only compare operation.
///

#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) enum IndexLiteral {
    One(Vec<u8>),
    // Small membership lists keep their encoded literal order and use linear
    // evaluation to avoid sort/dedup overhead on the common branch-set sizes.
    Many(Vec<Vec<u8>>),
    // Larger membership lists are sorted/deduped once at compile time and use
    // binary search in the index-predicate hot loop.
    ManySorted(Vec<Vec<u8>>),
}

// Compare one encoded index component against one compiled literal payload.
pub(crate) fn eval_index_compare(
    component: &[u8],
    op: IndexCompareOp,
    literal: &IndexLiteral,
) -> bool {
    match (op, literal) {
        (IndexCompareOp::Eq, IndexLiteral::One(expected)) => component == expected.as_slice(),
        (IndexCompareOp::Ne, IndexLiteral::One(expected)) => component != expected.as_slice(),
        (IndexCompareOp::Lt, IndexLiteral::One(expected)) => component < expected.as_slice(),
        (IndexCompareOp::Lte, IndexLiteral::One(expected)) => component <= expected.as_slice(),
        (IndexCompareOp::Gt, IndexLiteral::One(expected)) => component > expected.as_slice(),
        (IndexCompareOp::Gte, IndexLiteral::One(expected)) => component >= expected.as_slice(),
        (IndexCompareOp::In, IndexLiteral::Many(candidates)) => {
            candidates.iter().any(|candidate| component == candidate)
        }
        (IndexCompareOp::NotIn, IndexLiteral::Many(candidates)) => {
            candidates.iter().all(|candidate| component != candidate)
        }
        (IndexCompareOp::In, IndexLiteral::ManySorted(candidates)) => candidates
            .binary_search_by(|candidate| candidate.as_slice().cmp(component))
            .is_ok(),
        (IndexCompareOp::NotIn, IndexLiteral::ManySorted(candidates)) => candidates
            .binary_search_by(|candidate| candidate.as_slice().cmp(component))
            .is_err(),
        (
            IndexCompareOp::Eq
            | IndexCompareOp::Ne
            | IndexCompareOp::Lt
            | IndexCompareOp::Lte
            | IndexCompareOp::Gt
            | IndexCompareOp::Gte,
            IndexLiteral::Many(_) | IndexLiteral::ManySorted(_),
        )
        | (IndexCompareOp::In | IndexCompareOp::NotIn, IndexLiteral::One(_)) => false,
    }
}

///
/// IndexPredicateExecution
///
/// Execution-time wrapper for one compiled index predicate program.
/// Carries optional observability counters used by load execution tracing.
///

#[derive(Clone, Copy)]
pub(in crate::db) struct IndexPredicateExecution<'a> {
    pub(in crate::db) program: &'a IndexPredicateProgram,
    pub(in crate::db) rejected_keys_counter: Option<&'a Cell<u64>>,
}

// Evaluate one compiled index-only program against one decoded index key.
pub(in crate::db) fn eval_index_program_on_decoded_key(
    key: &IndexKey,
    program: &IndexPredicateProgram,
) -> Result<bool, InternalError> {
    // Evaluate recursively over the compiled index-only predicate tree.
    match program {
        IndexPredicateProgram::True => Ok(true),
        IndexPredicateProgram::False => Ok(false),
        IndexPredicateProgram::And(children) => {
            for child in children {
                if !eval_index_program_on_decoded_key(key, child)? {
                    return Ok(false);
                }
            }

            Ok(true)
        }
        IndexPredicateProgram::Or(children) => {
            for child in children {
                if eval_index_program_on_decoded_key(key, child)? {
                    return Ok(true);
                }
            }

            Ok(false)
        }
        IndexPredicateProgram::Not(inner) => Ok(!eval_index_program_on_decoded_key(key, inner)?),
        IndexPredicateProgram::Compare {
            component_index,
            op,
            literal,
        } => {
            let Some(component) = key.component(*component_index) else {
                return Err(InternalError::index_only_predicate_component_required());
            };

            Ok(eval_index_compare(component, *op, literal))
        }
    }
}

/// Evaluate one compiled index-only program against known prefix components.
///
/// Returns `None` when the available prefix does not contain every component
/// needed to decide the predicate. Callers may only prune a whole prefix when
/// this returns `Some(false)`.
#[must_use]
pub(in crate::db) fn eval_index_program_on_prefix_components(
    components: &[Vec<u8>],
    program: &IndexPredicateProgram,
) -> Option<bool> {
    match program {
        IndexPredicateProgram::True => Some(true),
        IndexPredicateProgram::False => Some(false),
        IndexPredicateProgram::And(children) => {
            eval_index_and_on_prefix_components(components, children.as_slice())
        }
        IndexPredicateProgram::Or(children) => {
            eval_index_or_on_prefix_components(components, children.as_slice())
        }
        IndexPredicateProgram::Not(inner) => {
            eval_index_program_on_prefix_components(components, inner).map(|passed| !passed)
        }
        IndexPredicateProgram::Compare {
            component_index,
            op,
            literal,
        } => components
            .get(*component_index)
            .map(|component| eval_index_compare(component.as_slice(), *op, literal)),
    }
}

fn eval_index_and_on_prefix_components(
    components: &[Vec<u8>],
    children: &[IndexPredicateProgram],
) -> Option<bool> {
    let mut all_known = true;
    for child in children {
        match eval_index_program_on_prefix_components(components, child) {
            Some(true) => {}
            Some(false) => return Some(false),
            None => all_known = false,
        }
    }

    all_known.then_some(true)
}

fn eval_index_or_on_prefix_components(
    components: &[Vec<u8>],
    children: &[IndexPredicateProgram],
) -> Option<bool> {
    let mut all_known = true;
    for child in children {
        match eval_index_program_on_prefix_components(components, child) {
            Some(true) => return Some(true),
            Some(false) => {}
            None => all_known = false,
        }
    }

    all_known.then_some(false)
}

/// Evaluate one compiled index-only execution request and update observability
/// counters when a key is rejected by index-only filtering.
pub(in crate::db) fn eval_index_execution_on_decoded_key(
    key: &IndexKey,
    execution: IndexPredicateExecution<'_>,
) -> Result<bool, InternalError> {
    let passed = eval_index_program_on_decoded_key(key, execution.program)?;
    if !passed && let Some(counter) = execution.rejected_keys_counter {
        counter.set(counter.get().saturating_add(1));
    }

    Ok(passed)
}

/// Build canonical index-component bytes for one literal.
#[must_use]
pub(in crate::db) fn literal_index_component_bytes(value: &Value) -> Option<Vec<u8>> {
    let encoded = EncodedValue::try_from_ref(value).ok()?;

    Some(encoded.encoded().to_vec())
}