use super::{Comparison, Plan, Request, Term, TermOperand};
use crate::{EntitySchema, Error, IndexSchema, store_key::StoreKey};
use std::{cmp::Ordering, ops::Bound};
type Bounds = (Bound<StoreKey>, Bound<StoreKey>);
pub(super) fn terminal_key(bounds: &Bounds, descending: bool) -> Option<&StoreKey> {
match if descending { &bounds.0 } else { &bounds.1 } {
Bound::Included(key) => Some(key),
_ => None,
}
}
fn successor(mut bytes: Vec<u8>) -> Result<Vec<u8>, Error> {
while bytes.last() == Some(&255) {
bytes.pop();
}
*bytes.last_mut().ok_or(Error::InvalidQuery)? += 1;
Ok(bytes)
}
struct Endpoint {
key: StoreKey,
inclusive: bool,
}
impl Endpoint {
fn tighten(&mut self, key: StoreKey, inclusive: bool, direction: Ordering) {
let order = key.cmp(&self.key);
if order == direction || (order == Ordering::Equal && !inclusive) {
*self = Self { key, inclusive };
}
}
fn into_bound(self) -> Bound<StoreKey> {
if self.inclusive {
Bound::Included(self.key)
} else {
Bound::Excluded(self.key)
}
}
}
fn bound_operand(term: &Term, secondary: bool, prefix_len: usize) -> Result<Option<&[u8]>, Error> {
let TermOperand::Literal { bytes, .. } = &term.operand else {
return Ok(None);
};
let operand = match term.comparison {
Comparison::Eq | Comparison::Lt | Comparison::Le | Comparison::Gt | Comparison::Ge => {
bytes.as_slice()
}
Comparison::StartsWith if secondary => {
bytes.strip_suffix(&[0, 0]).ok_or(Error::InvalidQuery)?
}
_ => return Ok(None),
};
Ok((prefix_len + operand.len() <= crate::MAX_INDEX_KEY_BYTES).then_some(operand))
}
fn next_field<'a>(
entity: &'a EntitySchema,
index: Option<&'a IndexSchema>,
fixed: usize,
) -> Option<(&'a str, bool)> {
if let Some(index) = index {
if let Some(field) = index.fields.get(fixed) {
return Some((field, true));
}
if index.unique {
return None;
}
}
Some((entity.primary_key, false))
}
pub(super) fn bounds_index_term(
entity: &EntitySchema,
index: &IndexSchema,
fixed: usize,
term: &Term,
prefix_len: usize,
) -> bool {
next_field(entity, Some(index), fixed).is_some_and(|(name, secondary)| {
name == entity.fields[term.position].name
&& matches!(bound_operand(term, secondary, prefix_len), Ok(Some(_)))
})
}
fn bounds_index_clause(
entity: &EntitySchema,
path: &super::order::IndexPath<'_>,
clause: &[Term],
) -> bool {
if let [term] = clause {
return bounds_index_term(entity, path.index, path.fixed, term, path.prefix.len());
}
next_field(entity, Some(path.index), path.fixed).is_some_and(|(field, _)| {
membership_interval(entity, field, clause, path.prefix.len()).is_some()
})
}
pub(super) fn has_secondary_bound(
entity: &EntitySchema,
plan: &Plan<'_>,
path: &super::order::IndexPath<'_>,
) -> bool {
plan.terms
.split_inclusive(|term| !term.or_next)
.any(|clause| bounds_index_clause(entity, path, clause))
}
fn membership_interval<'a>(
entity: &EntitySchema,
field: &str,
clause: &'a [Term],
prefix_len: usize,
) -> Option<(&'a [u8], &'a [u8])> {
let mut operands = clause.iter().map(|term| {
if entity.fields[term.position].name == field && term.comparison == Comparison::Eq {
bound_operand(term, false, prefix_len).ok().flatten()
} else {
None
}
});
let mut low = operands.next()??;
let mut high = low;
for operand in operands {
let key = operand?;
low = low.min(key);
high = high.max(key);
}
Some((low, high))
}
pub(super) fn preserves_primary_bounds(
entity: &EntitySchema,
plan: &Plan<'_>,
path: &super::order::IndexPath<'_>,
) -> bool {
plan.terms
.split_inclusive(|term| !term.or_next)
.all(|clause| {
let primary_bound = match clause {
[term] => {
term.position == plan.primary
&& matches!(bound_operand(term, false, plan.prefix.len()), Ok(Some(_)))
}
_ => membership_interval(entity, entity.primary_key, clause, plan.prefix.len())
.is_some(),
};
!primary_bound || bounds_index_clause(entity, path, clause)
})
}
pub(super) fn covers_primary(plan: &Plan<'_>) -> bool {
plan.index.is_none()
&& plan.terms.iter().all(|term| {
!term.or_next
&& term.position == plan.primary
&& matches!(bound_operand(term, false, plan.prefix.len()), Ok(Some(_)))
})
}
pub(super) fn bounds(
entity: &EntitySchema,
request: &Request<'_>,
plan: &Plan<'_>,
) -> Result<Option<Bounds>, Error> {
if super::order::literal_equalities(request).any(|(field, value)| {
value == crate::IndexValue::Absent
&& super::order::requires_present_field(entity, request, field)
}) {
return Ok(None);
}
let mut lower = Endpoint {
key: StoreKey::new(plan.prefix.clone())?,
inclusive: true,
};
let full_unique = plan
.index
.is_some_and(|index| index.unique && plan.fixed_components == index.fields.len());
let mut upper = if full_unique {
Endpoint {
key: lower.key.clone(),
inclusive: true,
}
} else {
Endpoint {
key: StoreKey::new(successor(plan.prefix.clone())?)?,
inclusive: false,
}
};
if let Some((field, secondary)) = next_field(entity, plan.index, plan.fixed_components) {
for clause in plan.terms.split_inclusive(|term| !term.or_next) {
let [term] = clause else {
if let Some((low, high)) =
membership_interval(entity, field, clause, plan.prefix.len())
{
lower.tighten(
StoreKey::new([plan.prefix.as_slice(), low].concat())?,
true,
Ordering::Greater,
);
let end = [plan.prefix.as_slice(), high].concat();
let end = if secondary { successor(end)? } else { end };
upper.tighten(StoreKey::new(end)?, !secondary, Ordering::Less);
}
continue;
};
if entity.fields[term.position].name != field {
continue;
}
let Some(operand) = bound_operand(term, secondary, plan.prefix.len())? else {
continue;
};
let mut bytes = plan.prefix.clone();
bytes.extend_from_slice(operand);
let end = if secondary
&& matches!(
term.comparison,
Comparison::Eq | Comparison::Gt | Comparison::Le | Comparison::StartsWith
) {
successor(bytes.clone())?
} else {
bytes.clone()
};
let key = StoreKey::new(bytes)?;
let end = StoreKey::new(end)?;
if secondary
&& entity.fields[term.position].optional
&& matches!(term.comparison, Comparison::Lt | Comparison::Le)
{
let mut present = plan.prefix.clone();
present.push(1);
lower.tighten(StoreKey::new(present)?, true, Ordering::Greater);
}
match term.comparison {
Comparison::Eq | Comparison::StartsWith => {
lower.tighten(key, true, Ordering::Greater);
upper.tighten(end, !secondary, Ordering::Less);
}
Comparison::Gt => lower.tighten(end, secondary, Ordering::Greater),
Comparison::Ge => lower.tighten(key, true, Ordering::Greater),
Comparison::Lt => upper.tighten(key, false, Ordering::Less),
Comparison::Le => upper.tighten(end, !secondary, Ordering::Less),
_ => {}
}
}
}
if let Some(cursor) = request.cursor {
let key = StoreKey::new(cursor.position.clone())?;
if plan.descending {
upper.tighten(key, cursor.inclusive, Ordering::Less);
} else {
lower.tighten(key, cursor.inclusive, Ordering::Greater);
}
}
if lower.key > upper.key || (lower.key == upper.key && !(lower.inclusive && upper.inclusive)) {
return Ok(None);
}
Ok(Some((lower.into_bound(), upper.into_bound())))
}