use super::{Comparison, 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 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| {
predicate.field == *name
&& !predicate
.comparison
.accepts_absent(predicate.value == IndexValue::Absent)
})
})
})
})
}
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
{
Some(predicate.value)
} else {
None
}
})
}