use super::selection::SelectionMembership;
use super::{RangeIndexLookupOutcome, SecondaryIndexLookupOutcome, Selection};
use crate::storage::warp_table::WarpTableRow;
#[doc(hidden)]
pub trait SelectionOperand<'table, Row: WarpTableRow, Brand> {
type Output;
fn and_with(self, left: Selection<'table, Row, Brand>) -> Self::Output;
fn or_with(self, left: Selection<'table, Row, Brand>) -> Self::Output;
fn and_not_with(self, left: Selection<'table, Row, Brand>) -> Self::Output;
fn xor_with(self, left: Selection<'table, Row, Brand>) -> Self::Output;
}
impl<'table, Row: WarpTableRow, Brand> Selection<'table, Row, Brand> {
pub fn or_selection(self, other: impl Into<Self>) -> Self {
self.union_selection(other.into())
}
pub fn and_selection(self, other: impl Into<Self>) -> Self {
self.intersection_selection(other.into())
}
pub fn and_not_selection(self, other: impl Into<Self>) -> Self {
self.excluding_selection(other.into())
}
pub fn xor_selection(self, other: impl Into<Self>) -> Self {
self.union_excluding_overlap_selection(other.into())
}
pub fn and<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
let table = self.table;
find(Row::query(table)).and_with(self)
}
pub fn or<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
let table = self.table;
find(Row::query(table)).or_with(self)
}
pub fn and_not<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
let table = self.table;
find(Row::query(table)).and_not_with(self)
}
pub fn xor<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
let table = self.table;
find(Row::query(table)).xor_with(self)
}
pub fn is_disjoint(&self, other: impl Into<Self>) -> bool {
memberships_are_disjoint(&self.membership, &other.into().membership)
}
pub fn is_subset(&self, other: impl Into<Self>) -> bool {
membership_is_subset(&self.membership, &other.into().membership)
}
fn union_selection(self, other: Self) -> Self {
let membership = match (self.membership, other.membership) {
(SelectionMembership::Empty, right) => right,
(left, SelectionMembership::Empty) => left,
(SelectionMembership::Borrowed(left), SelectionMembership::Borrowed(right)) => {
SelectionMembership::Owned(left.union(right))
}
(SelectionMembership::Borrowed(left), SelectionMembership::Owned(mut right)) => {
right.union_assign(left);
SelectionMembership::Owned(right)
}
(SelectionMembership::Owned(mut left), SelectionMembership::Borrowed(right)) => {
left.union_assign(right);
SelectionMembership::Owned(left)
}
(SelectionMembership::Owned(mut left), SelectionMembership::Owned(right)) => {
left.union_assign(&right);
SelectionMembership::Owned(left)
}
};
Self {
table: self.table,
membership,
}
}
fn intersection_selection(self, other: Self) -> Self {
let membership = match (self.membership, other.membership) {
(SelectionMembership::Empty, _) | (_, SelectionMembership::Empty) => {
SelectionMembership::Empty
}
(SelectionMembership::Borrowed(left), SelectionMembership::Borrowed(right)) => {
SelectionMembership::Owned(left.intersection(right))
}
(SelectionMembership::Borrowed(left), SelectionMembership::Owned(right)) => {
SelectionMembership::Owned(right.intersection_reusing(left))
}
(SelectionMembership::Owned(left), SelectionMembership::Borrowed(right)) => {
SelectionMembership::Owned(left.intersection_reusing(right))
}
(SelectionMembership::Owned(left), SelectionMembership::Owned(right)) => {
SelectionMembership::Owned(left.intersection_owned(right))
}
};
Self {
table: self.table,
membership,
}
}
fn excluding_selection(self, other: Self) -> Self {
let membership = match (self.membership, other.membership) {
(SelectionMembership::Empty, _) => SelectionMembership::Empty,
(left, SelectionMembership::Empty) => left,
(SelectionMembership::Borrowed(left), SelectionMembership::Borrowed(right)) => {
SelectionMembership::Owned(left.excluding(right))
}
(SelectionMembership::Borrowed(left), SelectionMembership::Owned(right)) => {
SelectionMembership::Owned(left.excluding(&right))
}
(SelectionMembership::Owned(mut left), SelectionMembership::Borrowed(right)) => {
left.exclude_assign(right);
SelectionMembership::Owned(left)
}
(SelectionMembership::Owned(mut left), SelectionMembership::Owned(right)) => {
left.exclude_assign(&right);
SelectionMembership::Owned(left)
}
};
Self {
table: self.table,
membership,
}
}
fn union_excluding_overlap_selection(self, other: Self) -> Self {
let membership = match (self.membership, other.membership) {
(SelectionMembership::Empty, right) => right,
(left, SelectionMembership::Empty) => left,
(SelectionMembership::Borrowed(left), SelectionMembership::Borrowed(right)) => {
SelectionMembership::Owned(left.union_excluding_overlap(right))
}
(SelectionMembership::Borrowed(left), SelectionMembership::Owned(mut right)) => {
right.union_excluding_overlap_assign(left);
SelectionMembership::Owned(right)
}
(SelectionMembership::Owned(mut left), SelectionMembership::Borrowed(right)) => {
left.union_excluding_overlap_assign(right);
SelectionMembership::Owned(left)
}
(SelectionMembership::Owned(mut left), SelectionMembership::Owned(right)) => {
left.union_excluding_overlap_assign(&right);
SelectionMembership::Owned(left)
}
};
Self {
table: self.table,
membership,
}
}
}
fn memberships_are_disjoint(
left: &SelectionMembership<'_>,
right: &SelectionMembership<'_>,
) -> bool {
match (left, right) {
(SelectionMembership::Empty, _) | (_, SelectionMembership::Empty) => true,
(SelectionMembership::Borrowed(left), SelectionMembership::Borrowed(right)) => {
left.is_disjoint(right)
}
(SelectionMembership::Borrowed(left), SelectionMembership::Owned(right)) => {
left.is_disjoint(right)
}
(SelectionMembership::Owned(left), SelectionMembership::Borrowed(right)) => {
left.is_disjoint(right)
}
(SelectionMembership::Owned(left), SelectionMembership::Owned(right)) => {
left.is_disjoint(right)
}
}
}
fn membership_is_subset(left: &SelectionMembership<'_>, right: &SelectionMembership<'_>) -> bool {
match (left, right) {
(SelectionMembership::Empty, _) => true,
(_, SelectionMembership::Empty) => false,
(SelectionMembership::Borrowed(left), SelectionMembership::Borrowed(right)) => {
left.is_subset(right)
}
(SelectionMembership::Borrowed(left), SelectionMembership::Owned(right)) => {
left.is_subset(right)
}
(SelectionMembership::Owned(left), SelectionMembership::Borrowed(right)) => {
left.is_subset(right)
}
(SelectionMembership::Owned(left), SelectionMembership::Owned(right)) => {
left.is_subset(right)
}
}
}
impl<'table, Row: WarpTableRow, Brand> SelectionOperand<'table, Row, Brand>
for Selection<'table, Row, Brand>
{
type Output = Selection<'table, Row, Brand>;
fn and_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.and_selection(self)
}
fn or_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.or_selection(self)
}
fn and_not_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.and_not_selection(self)
}
fn xor_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.xor_selection(self)
}
}
impl<'table, Row, Brand, OtherSelection, Error> SelectionOperand<'table, Row, Brand>
for Result<OtherSelection, Error>
where
Row: WarpTableRow + 'table,
Brand: 'table,
OtherSelection: Into<Selection<'table, Row, Brand>>,
{
type Output = Result<Selection<'table, Row, Brand>, Error>;
fn and_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
self.map(|right| left.and_selection(right))
}
fn or_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
self.map(|right| left.or_selection(right))
}
fn and_not_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
self.map(|right| left.and_not_selection(right))
}
fn xor_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
self.map(|right| left.xor_selection(right))
}
}
macro_rules! impl_lookup_algebra {
($outcome:ident) => {
impl<'table, Row: WarpTableRow, Brand, Key> SelectionOperand<'table, Row, Brand>
for $outcome<'table, Row, Brand, Key>
{
type Output = Selection<'table, Row, Brand>;
fn and_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.and_selection(self)
}
fn or_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.or_selection(self)
}
fn and_not_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.and_not_selection(self)
}
fn xor_with(self, left: Selection<'table, Row, Brand>) -> Self::Output {
left.xor_selection(self)
}
}
impl<'table, Row: WarpTableRow, Brand, Key> $outcome<'table, Row, Brand, Key> {
pub fn or_selection(
self,
other: impl Into<Selection<'table, Row, Brand>>,
) -> Selection<'table, Row, Brand> {
self.into_selection().or_selection(other)
}
pub fn and_selection(
self,
other: impl Into<Selection<'table, Row, Brand>>,
) -> Selection<'table, Row, Brand> {
self.into_selection().and_selection(other)
}
pub fn and_not_selection(
self,
other: impl Into<Selection<'table, Row, Brand>>,
) -> Selection<'table, Row, Brand> {
self.into_selection().and_not_selection(other)
}
pub fn xor_selection(
self,
other: impl Into<Selection<'table, Row, Brand>>,
) -> Selection<'table, Row, Brand> {
self.into_selection().xor_selection(other)
}
pub fn and<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
self.into_selection().and(find)
}
pub fn or<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
self.into_selection().or(find)
}
pub fn and_not<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
self.into_selection().and_not(find)
}
pub fn xor<Operand>(
self,
find: impl FnOnce(Row::Query<'table, Brand>) -> Operand,
) -> Operand::Output
where
Brand: 'table,
Operand: SelectionOperand<'table, Row, Brand>,
{
self.into_selection().xor(find)
}
}
};
}
impl_lookup_algebra!(SecondaryIndexLookupOutcome);
impl_lookup_algebra!(RangeIndexLookupOutcome);
impl<'table, Row: WarpTableRow, Brand, SecondaryKey>
SecondaryIndexLookupOutcome<'table, Row, Brand, SecondaryKey>
{
pub fn is_disjoint<OtherKey>(
&self,
other: &SecondaryIndexLookupOutcome<'table, Row, Brand, OtherKey>,
) -> bool {
memberships_are_disjoint(&self.selection().membership, &other.selection().membership)
}
pub fn is_subset<OtherKey>(
&self,
other: &SecondaryIndexLookupOutcome<'table, Row, Brand, OtherKey>,
) -> bool {
membership_is_subset(&self.selection().membership, &other.selection().membership)
}
}
#[cfg(test)]
mod tests {
use core::num::NonZeroU32;
use super::*;
use crate::storage::warp_table::secondary_index::{SlotSet, SlotSetInsertOutcome, StableSlot};
use crate::storage::warp_table::{Capacity, WarpTable, WarpTableRow};
#[derive(WarpTableRow)]
struct Row {
value: u8,
}
#[test]
fn algebra_covers_borrowed_owned_and_empty_memberships() -> Result<(), &'static str> {
let table = table()?;
macro_rules! cover_operation {
($operation:ident, $expected:expr) => {{
let left = set([1, 2])?;
let right = set([2, 3])?;
assert_eq!(
values(borrowed(&table, &left).$operation(borrowed(&table, &right))),
$expected,
);
assert_eq!(
values(borrowed(&table, &left).$operation(owned(&table, set([2, 3])?))),
$expected,
);
assert_eq!(
values(owned(&table, set([1, 2])?).$operation(borrowed(&table, &right))),
$expected,
);
assert_eq!(
values(owned(&table, set([1, 2])?).$operation(owned(&table, set([2, 3])?))),
$expected,
);
}};
}
cover_operation!(union_selection, [1, 2, 3]);
cover_operation!(intersection_selection, [2]);
cover_operation!(excluding_selection, [1]);
cover_operation!(union_excluding_overlap_selection, [1, 3]);
assert_eq!(
empty(&table).or_selection(owned(&table, set([1])?)).len(),
1
);
assert_eq!(
owned(&table, set([1])?).or_selection(empty(&table)).len(),
1
);
assert!(
empty(&table)
.and_selection(owned(&table, set([1])?))
.is_empty()
);
assert!(
owned(&table, set([1])?)
.and_selection(empty(&table))
.is_empty()
);
assert!(
empty(&table)
.and_not_selection(owned(&table, set([1])?))
.is_empty()
);
assert_eq!(
owned(&table, set([1])?)
.and_not_selection(empty(&table))
.len(),
1
);
assert_eq!(
empty(&table).xor_selection(owned(&table, set([1])?)).len(),
1
);
assert_eq!(
owned(&table, set([1])?).xor_selection(empty(&table)).len(),
1
);
Ok(())
}
#[test]
fn predicates_cover_every_membership_representation() -> Result<(), &'static str> {
let left = set([1])?;
let right = set([2])?;
assert!(memberships_are_disjoint(
&SelectionMembership::Borrowed(&left),
&SelectionMembership::Borrowed(&right),
));
assert!(memberships_are_disjoint(
&SelectionMembership::Borrowed(&left),
&SelectionMembership::Owned(set([2])?),
));
assert!(memberships_are_disjoint(
&SelectionMembership::Owned(set([1])?),
&SelectionMembership::Borrowed(&right),
));
assert!(memberships_are_disjoint(
&SelectionMembership::Owned(set([1])?),
&SelectionMembership::Owned(set([2])?),
));
assert!(memberships_are_disjoint(
&SelectionMembership::Empty,
&SelectionMembership::Owned(set([2])?),
));
let superset = set([1, 2])?;
assert!(membership_is_subset(
&SelectionMembership::Borrowed(&left),
&SelectionMembership::Borrowed(&superset),
));
assert!(membership_is_subset(
&SelectionMembership::Borrowed(&left),
&SelectionMembership::Owned(set([1, 2])?),
));
assert!(membership_is_subset(
&SelectionMembership::Owned(set([1])?),
&SelectionMembership::Borrowed(&superset),
));
assert!(membership_is_subset(
&SelectionMembership::Owned(set([1])?),
&SelectionMembership::Owned(set([1, 2])?),
));
assert!(membership_is_subset(
&SelectionMembership::Empty,
&SelectionMembership::Empty,
));
assert!(!membership_is_subset(
&SelectionMembership::Owned(set([1])?),
&SelectionMembership::Empty,
));
assert!(matches!(set([]), Err("test set was empty")));
Ok(())
}
fn table() -> Result<WarpTable<Row>, &'static str> {
WarpTable::try_new(Capacity::new(NonZeroU32::MIN))
.map_err(|_| "table storage was unavailable")
}
fn empty(table: &WarpTable<Row>) -> Selection<'_, Row> {
Selection::empty(table)
}
fn borrowed<'table>(
table: &'table WarpTable<Row>,
slots: &'table SlotSet,
) -> Selection<'table, Row> {
Selection::borrowed(table, slots)
}
fn owned(table: &WarpTable<Row>, slots: SlotSet) -> Selection<'_, Row> {
Selection {
table,
membership: SelectionMembership::Owned(slots),
}
}
fn set<const N: usize>(values: [u32; N]) -> Result<SlotSet, &'static str> {
let Some((first, rest)) = values.split_first() else {
return Err("test set was empty");
};
let mut set = SlotSet::one(StableSlot::new(*first));
for value in rest {
let SlotSetInsertOutcome::Inserted { .. } = set
.try_prepare_insert(StableSlot::new(*value))
.map_err(|_| "test slot was duplicated")?
.commit();
}
Ok(set)
}
fn values(selection: Selection<'_, Row>) -> alloc::vec::Vec<u32> {
match selection.membership {
SelectionMembership::Empty => alloc::vec::Vec::new(),
SelectionMembership::Borrowed(slots) => slots.slots().map(StableSlot::value).collect(),
SelectionMembership::Owned(slots) => slots.slots().map(StableSlot::value).collect(),
}
}
}