use super::{Comparison, Predicate, QueryOperand, Request};
use crate::{EntitySchema, Error, IndexSchema, IndexValue, key, store::admit_index_prefix};
pub(super) struct IndexPath<'a> {
pub index: &'a IndexSchema,
pub prefix: Vec<u8>,
pub fixed: usize,
}
pub(super) enum Path<'a> {
Primary,
Index(IndexPath<'a>),
Sort(Vec<(usize, bool)>),
}
pub(super) fn select<'a>(
entity: &'a EntitySchema,
request: &Request<'_>,
) -> Result<Path<'a>, Error> {
let mut positions = [(0, false); 4];
if let Some(order) = &request.order {
if order.is_empty() {
return Err(Error::InvalidQuery);
}
for (i, name) in order.iter().enumerate() {
let position = entity
.fields
.iter()
.position(|f| f.name == *name)
.ok_or(Error::InvalidQuery)?;
let field = &entity.fields[position];
if !key::supports(field.value)
|| order[..i].contains(name)
|| (*name == entity.primary_key && i + 1 != order.len())
{
return Err(Error::InvalidQuery);
}
positions[i] = (position, request.order_descending & (1 << i) != 0);
}
}
if let Some((name, values)) = &request.index {
let index = entity
.indexes
.iter()
.find(|i| i.name == *name)
.ok_or(Error::InvalidQuery)?;
if values.len() > index.fields.len() {
return Err(Error::InvalidQuery);
}
let prefix = admit_index_prefix(entity, index, values)?;
if !complete_membership(entity, index, values, request)
|| !satisfies(entity, request, Some(index), values.len())
{
return Err(Error::InvalidQuery);
}
return Ok(Path::Index(IndexPath {
index,
prefix,
fixed: values.len(),
}));
}
if request.order.is_none() {
return Ok(Path::Primary);
}
let primary_fits = satisfies(entity, request, None, 0);
let mut best: Option<(&IndexSchema, Vec<IndexValue<'_>>)> = None;
for index in entity.indexes {
let values: Vec<_> = index
.fields
.iter()
.map_while(|name| equality(request, name))
.collect();
if !complete_membership(entity, index, &values, request)
|| !satisfies(entity, request, Some(index), values.len())
{
continue;
}
let rank = (
std::cmp::Reverse(values.len()),
index.fields.len(),
index.name,
);
if best.as_ref().is_none_or(|(old, old_values)| {
rank < (
std::cmp::Reverse(old_values.len()),
old.fields.len(),
old.name,
)
}) {
best = Some((index, values));
}
}
if primary_fits && best.as_ref().is_none_or(|(_, values)| values.is_empty()) {
return Ok(Path::Primary);
}
let Some((index, values)) = best else {
if request.cursor.is_some() {
return Err(Error::InvalidQuery);
}
let mut positions =
positions[..request.order.as_ref().ok_or(Error::InvalidQuery)?.len()].to_vec();
let primary = entity
.fields
.iter()
.position(|f| f.name == entity.primary_key)
.ok_or(Error::InvalidQuery)?;
if positions.last().map(|(position, _)| *position) != Some(primary) {
positions.push((primary, false));
}
return Ok(Path::Sort(positions));
};
Ok(Path::Index(IndexPath {
index,
prefix: admit_index_prefix(entity, index, &values)?,
fixed: values.len(),
}))
}
fn covers(request: &Request<'_>, index: &IndexSchema, values: &[IndexValue<'_>]) -> bool {
request.predicates.iter().all(|p| {
!p.or_next
&& p.comparison == Comparison::Eq
&& index.fields.iter().zip(values).any(|(name, value)| {
*name == p.field && matches!(p.operand, QueryOperand::Literal(v) if v == *value)
})
})
}
pub(super) fn count_prefix<'a>(
entity: &'a EntitySchema,
request: &Request<'_>,
plan: &mut super::Plan<'a>,
) -> Result<bool, Error> {
if let Some((_, values)) = &request.index {
return Ok(plan
.index
.is_some_and(|index| covers(request, index, values)));
}
for index in entity.indexes {
let values: Vec<_> = index
.fields
.iter()
.map_while(|field| equality(request, field))
.collect();
if !covers(request, index, &values)
|| !complete_membership(entity, index, &values, request)
|| (index.present_only && values.contains(&IndexValue::Absent))
{
continue;
}
match admit_index_prefix(entity, index, &values) {
Ok(prefix) => {
plan.prefix = prefix;
plan.index = Some(index);
plan.fixed_components = values.len();
return Ok(true);
}
Err(Error::Limit) => continue,
Err(error) => return Err(error),
}
}
Ok(false)
}
fn requires_presence(predicate: &Predicate<'_>, name: &str, entity: &EntitySchema) -> bool {
match predicate.operand {
QueryOperand::Length(_) => {
predicate.field == name && !predicate.comparison.accepts_absent(false)
}
QueryOperand::Literal(value) => {
predicate.field == name
&& !predicate
.comparison
.accepts_absent(value == IndexValue::Absent)
}
QueryOperand::Field(right) => {
let other = if predicate.field == name {
right
} else if right == name {
predicate.field
} else {
return false;
};
!predicate.comparison.accepts_absent(false)
&& (!predicate.comparison.accepts_absent(true)
|| entity
.fields
.iter()
.any(|field| field.name == other && !field.optional))
}
}
}
fn complete_membership(
entity: &EntitySchema,
index: &IndexSchema,
values: &[IndexValue<'_>],
request: &Request<'_>,
) -> bool {
!index.present_only
|| index.fields.iter().enumerate().all(|(i, name)| {
entity
.fields
.iter()
.find(|f| f.name == *name)
.is_some_and(|field| {
!field.optional
|| values.get(i).is_some_and(|v| *v != IndexValue::Absent)
|| request
.predicates
.split_inclusive(|p| !p.or_next)
.any(|clause| {
clause
.iter()
.all(|predicate| requires_presence(predicate, name, entity))
})
})
})
}
fn satisfies(
entity: &EntitySchema,
request: &Request<'_>,
index: Option<&IndexSchema>,
prefix_len: usize,
) -> bool {
let Some(order) = &request.order else {
return true;
};
let fields = index.map_or(&[][..], |i| i.fields);
let fixed =
|name: &&str| fields[..prefix_len].contains(name) || equality(request, name).is_some();
if fixed(&entity.primary_key) {
return true;
}
if request.order_descending != 0 {
let descending = request.primary_descending(entity);
if order.iter().enumerate().any(|(i, name)| {
(request.order_descending & (1 << i) != 0) != descending && !fixed(name)
}) {
return false;
}
}
let wanted = order
.iter()
.copied()
.take_while(|name| *name != entity.primary_key)
.filter(|name| !fixed(name))
.chain(std::iter::once(entity.primary_key));
let supplied = fields
.iter()
.copied()
.take_while(|name| *name != entity.primary_key)
.filter(|name| !fixed(name))
.chain(std::iter::once(entity.primary_key));
wanted.eq(supplied)
}
fn equality<'a>(request: &Request<'a>, field: &str) -> Option<IndexValue<'a>> {
request
.predicates
.split_inclusive(|p| !p.or_next)
.find_map(|clause| {
if let [predicate] = clause
&& predicate.field == field
&& predicate.comparison == Comparison::Eq
&& let QueryOperand::Literal(value) = predicate.operand
{
Some(value)
} else {
None
}
})
}