use core::{iter::FusedIterator, slice};
mod order;
#[cfg(feature = "alloc")]
use super::AllocatedStorage;
use super::WarpTableBacking;
use crate::storage::warp_table::inconsistency::invariant_violation;
use crate::storage::warp_table::stable_slots::{
StableSlot, StableSlotResolveOutcome, StableSlotResolver,
};
use crate::storage::warp_table::{
WarpTable, WarpTableGetAtOutcome, WarpTableInconsistency, WarpTableRow,
};
#[derive(
::core::clone::Clone,
::core::marker::Copy,
::core::fmt::Debug,
::core::cmp::Eq,
::core::cmp::PartialEq,
)]
pub struct DenseSelectionStorageTooSmall {
pub required: u64,
pub available: usize,
}
#[must_use]
pub struct DenseSelectionRows<
'table,
'workspace,
Row: WarpTableRow,
#[cfg(feature = "alloc")] Brand = Row,
#[cfg(not(feature = "alloc"))] Brand,
#[cfg(feature = "alloc")] Backing: WarpTableBacking<Row> = AllocatedStorage,
#[cfg(not(feature = "alloc"))] Backing: WarpTableBacking<Row>,
> {
table: &'table WarpTable<Row, Brand, Backing>,
rows: slice::Iter<'workspace, usize>,
}
pub(super) fn dense_rows<'workspace, Row: WarpTableRow, Brand, Backing: WarpTableBacking<Row>>(
table: &WarpTable<Row, Brand, Backing>,
count: u64,
slots: impl Iterator<Item = StableSlot>,
storage: &'workspace mut [usize],
) -> Result<&'workspace [usize], DenseSelectionStorageTooSmall>
where
Backing::Indexes: StableSlotResolver,
{
let refusal = DenseSelectionStorageTooSmall {
required: count,
available: storage.len(),
};
let count = usize::try_from(count).map_err(|_| refusal)?;
let (rows, scratch) = storage.split_at_mut_checked(count).ok_or(refusal)?;
let filled = slots.fold(0_usize, |filled, slot| {
let row = rows.get_mut(filled).unwrap_or_else(|| {
invariant_violation("selection contains more rows than its cardinality")
});
let StableSlotResolveOutcome::Resolved { dense_row, .. } = table
.__indexes()
.resolve_stable_slot(slot)
.unwrap_or_else(|reason| invariant_violation(reason));
*row = dense_row;
filled.saturating_add(1)
});
if filled != count {
invariant_violation("selection contains fewer rows than its cardinality");
}
order::sort(rows, table.len(), scratch);
Ok(rows)
}
impl<'table, 'workspace, Row: WarpTableRow, Brand, Backing: WarpTableBacking<Row>>
DenseSelectionRows<'table, 'workspace, Row, Brand, Backing>
{
pub(super) fn new(
table: &'table WarpTable<Row, Brand, Backing>,
rows: &'workspace [usize],
) -> Self {
Self {
table,
rows: rows.iter(),
}
}
fn row(&self, dense_row: usize) -> Row::Ref<'table> {
match self.table.get_at(dense_row) {
WarpTableGetAtOutcome::Present { row, .. } => row,
WarpTableGetAtOutcome::Absent { dense_row } => {
invariant_violation(WarpTableInconsistency::DenseRowUnavailable {
row: dense_row,
rows: self.table.len(),
})
}
}
}
}
impl<'table, Row: WarpTableRow, Brand, Backing: WarpTableBacking<Row>> Iterator
for DenseSelectionRows<'table, '_, Row, Brand, Backing>
{
type Item = Row::Ref<'table>;
fn next(&mut self) -> Option<Self::Item> {
let row = *self.rows.next()?;
Some(self.row(row))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.rows.size_hint()
}
fn fold<Acc, Fold: FnMut(Acc, Self::Item) -> Acc>(self, initial: Acc, mut fold: Fold) -> Acc {
let Some((first, last)) = self
.rows
.as_slice()
.first()
.zip(self.rows.as_slice().last())
else {
return initial;
};
if last
.checked_sub(*first)
.and_then(|span| span.checked_add(1))
== Some(self.rows.len())
{
let ids = self.table.ids().get(*first..=*last).unwrap_or_else(|| {
invariant_violation(WarpTableInconsistency::DenseRowUnavailable {
row: *last,
rows: self.table.len(),
})
});
return Backing::fold_rows(ids, self.table.columns(), *first, initial, fold)
.unwrap_or_else(|reason| {
invariant_violation(WarpTableInconsistency::from(reason))
});
}
let mut cursor = self.table.rows();
let mut next = 0_usize;
self.rows.fold(initial, |acc, dense_row| {
let skip = dense_row
.checked_sub(next)
.unwrap_or_else(|| invariant_violation("dense selection is not strictly ordered"));
let row = cursor.nth(skip).unwrap_or_else(|| {
invariant_violation(WarpTableInconsistency::DenseRowUnavailable {
row: *dense_row,
rows: self.table.len(),
})
});
next = dense_row.saturating_add(1);
fold(acc, row)
})
}
}
impl<Row: WarpTableRow, Brand, Backing: WarpTableBacking<Row>> DoubleEndedIterator
for DenseSelectionRows<'_, '_, Row, Brand, Backing>
{
fn next_back(&mut self) -> Option<Self::Item> {
let row = *self.rows.next_back()?;
Some(self.row(row))
}
}
impl<Row: WarpTableRow, Brand, Backing: WarpTableBacking<Row>> ExactSizeIterator
for DenseSelectionRows<'_, '_, Row, Brand, Backing>
{
}
impl<Row: WarpTableRow, Brand, Backing: WarpTableBacking<Row>> FusedIterator
for DenseSelectionRows<'_, '_, Row, Brand, Backing>
{
}
#[cfg(test)]
mod tests {
extern crate std;
use super::*;
use crate::storage::warp_table::{Capacity, WarpTableInsertOutcome};
use alloc::{collections::VecDeque, vec::Vec};
use core::{num::NonZeroU32, panic::AssertUnwindSafe};
use proptest::prelude::*;
use std::panic::catch_unwind;
#[derive(WarpTableRow)]
struct Item {
#[index(secondary)]
group: u8,
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(64))]
#[test]
fn folding_remaining_dense_rows_matches_physical_order(
selected in proptest::collection::vec(any::<bool>(), 0..257),
front in 0_usize..20,
back in 0_usize..20,
) {
let fail = proptest::test_runner::TestCaseError::fail;
let capacity = NonZeroU32::new(257).ok_or_else(|| fail("capacity"))?;
let mut table = WarpTable::<Item>::try_new(Capacity::new(capacity)).map_err(|_| fail("table"))?;
for value in 0..selected.len() {
prop_assert!(matches!(table.insert(Item { group: value as u8 }), WarpTableInsertOutcome::Inserted { .. }), "row insertion");
}
let positions = selected.iter().enumerate().filter_map(|(position, selected)| selected.then_some(position)).collect::<Vec<_>>();
let mut expected = table.rows().enumerate().filter_map(|(position, row)| {
selected.get(position).copied().filter(|selected| *selected).map(|_| (*row.id, *row.group))
}).collect::<VecDeque<_>>();
let mut actual = DenseSelectionRows::new(&table, &positions);
for _ in 0..front {
prop_assert_eq!(actual.next().map(|row| (*row.id, *row.group)), expected.pop_front());
}
for _ in 0..back {
prop_assert_eq!(actual.next_back().map(|row| (*row.id, *row.group)), expected.pop_back());
}
prop_assert_eq!(actual.len(), expected.len());
let folded = actual.fold(Vec::new(), |mut rows, row| {
rows.push((*row.id, *row.group));
rows
});
prop_assert_eq!(folded, expected.into_iter().collect::<Vec<_>>());
}
}
#[test]
fn inconsistent_memberships_cannot_become_dense_row_snapshots() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(Capacity::new(NonZeroU32::MIN)).map_err(|_| "table")?;
assert!(matches!(
table.insert(Item { group: 1 }),
WarpTableInsertOutcome::Inserted { .. }
));
let mut storage = [0; 2];
for (count, slots) in [(0, [0]), (2, [0]), (1, [1])] {
assert!(
catch_unwind(AssertUnwindSafe(|| {
let _result = dense_rows(
&table,
count,
slots.into_iter().map(StableSlot::new),
&mut storage,
);
}))
.is_err()
);
}
for reverse in [false, true] {
assert!(
catch_unwind(AssertUnwindSafe(|| {
let mut rows = DenseSelectionRows::new(&table, &[1]);
if reverse {
let _row = rows.next_back();
} else {
let _row = rows.next();
}
}))
.is_err()
);
}
assert!(
catch_unwind(AssertUnwindSafe(
|| DenseSelectionRows::new(&table, &[1]).fold(0, |_, _| 1)
))
.is_err()
);
for invalid in [[0, 0], [0, 2]] {
assert!(
catch_unwind(AssertUnwindSafe(|| {
DenseSelectionRows::new(&table, &invalid).fold(0, |_, _| 1)
}))
.is_err()
);
}
assert_eq!(DenseSelectionRows::new(&table, &[]).fold(7, |_, _| 1), 7);
let mut empty = DenseSelectionRows::new(&table, &[]);
assert_eq!(empty.len(), 0);
assert!(empty.next().is_none());
assert!(empty.next_back().is_none());
table.columns.group.clear();
assert!(
catch_unwind(AssertUnwindSafe(
|| DenseSelectionRows::new(&table, &[0]).fold(0, |_, _| 1)
))
.is_err()
);
let error = DenseSelectionStorageTooSmall {
required: 7,
available: 3,
};
let copied = error;
#[allow(clippy::clone_on_copy, reason = "exercise the public Clone contract")]
let cloned = error.clone();
assert_eq!(copied, cloned);
assert_eq!(
alloc::format!("{error:?}"),
"DenseSelectionStorageTooSmall { required: 7, available: 3 }"
);
Ok(())
}
}