use alloc::{collections::TryReserveError, vec::Vec};
use core::{convert::Infallible, mem, num::NonZeroU32};
extern crate std;
use self::std::panic::{AssertUnwindSafe, catch_unwind};
use proptest::prelude::*;
use proptest::test_runner::{TestCaseError, TestCaseResult};
use super::{
Capacity, IndexKey, WarpId, WarpTable, WarpTableGetAtOutcome, WarpTableGetOutcome,
WarpTableInsertOutcome, WarpTableInsertWithIdOutcome, WarpTableRemoveOutcome,
WarpTableReplaceOutcome, WarpTableRow, WarpTableRowGetError, WarpTableRowGetOutcome,
WarpTableRowRelocation, WarpTableRowReplaceError, WarpTableRowReplaceOutcome,
WarpTableUpdateOutcome, integer_index_word,
};
crate::value_wrapper! {
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct ItemId(u64);
}
impl IndexKey for ItemId {
fn index_word(self) -> u64 {
integer_index_word(self.value())
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Item {
quantity: u32,
}
struct ItemColumns {
quantities: Vec<u32>,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct ItemRef<'row> {
id: &'row ItemId,
quantity: &'row u32,
}
struct ItemMut<'row> {
id: &'row ItemId,
quantity: &'row mut u32,
}
impl WarpTableRow for Item {
type Id = ItemId;
type Columns = ItemColumns;
type ColumnsCreationError = TryReserveError;
type Indexes = ();
type IndexesCreationError = Infallible;
type UniqueConflict = Infallible;
type IndexesInsertError = Infallible;
type PreparedIndexesInsert<'indexes> = ();
type IndexesRemoveError = Infallible;
type PreparedIndexesRemove<'indexes> = ();
type IndexesReplaceError = Infallible;
type PreparedIndexesReplace<'indexes> = ();
type Ref<'row> = ItemRef<'row>;
type Mut<'row> = ItemMut<'row>;
type Query<'table, Brand: 'table> = ();
type MutQuery<'table, Brand: 'table> = ();
type DetachedQuery<'indexes> = ();
fn try_new_columns(maximum_rows: usize) -> Result<Self::Columns, Self::ColumnsCreationError> {
let mut quantities = Vec::new();
quantities.try_reserve_exact(maximum_rows)?;
Ok(ItemColumns { quantities })
}
fn try_new_indexes(_: usize) -> Result<Self::Indexes, Self::IndexesCreationError> {
Ok(())
}
fn query<'table, Brand>(_: &'table WarpTable<Self, Brand>) -> Self::Query<'table, Brand>
where
Brand: 'table,
{
}
fn query_mut<'table, Brand>(
_: &'table mut WarpTable<Self, Brand>,
) -> Self::MutQuery<'table, Brand>
where
Brand: 'table,
{
}
fn detached_query(_: &Self::Indexes) -> Self::DetachedQuery<'_> {}
fn unique_insert_conflict(_: &Self::Indexes, _: &Self) -> Option<Self::UniqueConflict> {
None
}
fn unique_replace_conflict(
_: &Self::Indexes,
_: Self::Ref<'_>,
_: &Self,
) -> Option<Self::UniqueConflict> {
None
}
fn try_prepare_indexes_insert<'indexes>(
_: &'indexes mut Self::Indexes,
_: &Self,
) -> Result<Self::PreparedIndexesInsert<'indexes>, Self::IndexesInsertError> {
Ok(())
}
fn commit_indexes_insert(_: Self::PreparedIndexesInsert<'_>) {}
fn try_prepare_indexes_remove<'indexes>(
_: &'indexes mut Self::Indexes,
_: Self::Ref<'_>,
_: usize,
) -> Result<Self::PreparedIndexesRemove<'indexes>, Self::IndexesRemoveError> {
Ok(())
}
fn commit_indexes_remove(_: Self::PreparedIndexesRemove<'_>) {}
fn try_prepare_indexes_replace<'indexes>(
_: &'indexes mut Self::Indexes,
_: Self::Ref<'_>,
_: &Self,
_: usize,
) -> Result<Self::PreparedIndexesReplace<'indexes>, Self::IndexesReplaceError> {
Ok(())
}
fn commit_indexes_replace(_: Self::PreparedIndexesReplace<'_>) {}
fn append(columns: &mut Self::Columns, row: Self) {
columns.quantities.push(row.quantity);
}
fn swap_remove(columns: &mut Self::Columns, index: usize) -> Self {
Self {
quantity: columns.quantities.swap_remove(index),
}
}
fn get<'row>(
id: &'row Self::Id,
columns: &'row Self::Columns,
index: usize,
) -> Result<WarpTableRowGetOutcome<Self::Ref<'row>>, WarpTableRowGetError> {
let Some(quantity) = columns.quantities.get(index) else {
return Err(WarpTableRowGetError::ColumnUnavailable {
column: 0,
row: index,
});
};
Ok(WarpTableRowGetOutcome::Present {
row: ItemRef { id, quantity },
})
}
fn get_mut<'row>(
id: &'row Self::Id,
columns: &'row mut Self::Columns,
_: &'row mut Self::Indexes,
index: usize,
) -> Result<WarpTableRowGetOutcome<Self::Mut<'row>>, WarpTableRowGetError> {
let Some(quantity) = columns.quantities.get_mut(index) else {
return Err(WarpTableRowGetError::ColumnUnavailable {
column: 0,
row: index,
});
};
Ok(WarpTableRowGetOutcome::Present {
row: ItemMut { id, quantity },
})
}
fn replace(
columns: &mut Self::Columns,
index: usize,
replacement: Self,
) -> Result<WarpTableRowReplaceOutcome<Self>, WarpTableRowReplaceError<Self>> {
let Some(quantity) = columns.quantities.get_mut(index) else {
return Err(WarpTableRowReplaceError::ColumnUnavailable {
column: 0,
row: index,
rejected: replacement,
});
};
let previous = Self {
quantity: mem::replace(quantity, replacement.quantity),
};
Ok(WarpTableRowReplaceOutcome::Replaced { previous })
}
}
#[derive(Debug, Eq, super::WarpTableRow, PartialEq)]
struct GeneratedItem {
quantity: u32,
}
fn item(quantity: u32) -> Item {
Item { quantity }
}
fn capacity(value: u32) -> Result<Capacity, &'static str> {
NonZeroU32::new(value)
.map(Capacity::new)
.ok_or("capacity was zero")
}
#[test]
fn warp_table_reserves_ids_and_every_column_at_construction() -> Result<(), &'static str> {
let capacity = capacity(2)?;
let table =
WarpTable::<Item>::try_new(capacity).map_err(|_| "table storage was unavailable")?;
assert_eq!(table.capacity(), capacity);
assert!(table.is_empty());
assert!(table.ids.capacity() >= 2);
assert!(table.columns().quantities.capacity() >= 2);
Ok(())
}
#[test]
fn warp_table_resolves_explicit_ids_and_preserves_failures() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(capacity(2)?).map_err(|_| "table storage was unavailable")?;
let first_id = ItemId::new(7);
let first = item(11);
assert_eq!(
table.get(first_id),
WarpTableGetOutcome::Absent { id: first_id }
);
assert_eq!(
table.insert_with_id(first_id, first),
WarpTableInsertWithIdOutcome::Inserted {
id: first_id,
row: 0,
}
);
assert_eq!(
table.insert_with_id(first_id, first),
WarpTableInsertWithIdOutcome::AlreadyPresent {
id: first_id,
existing_row: 0,
rejected: first,
}
);
let second_id = ItemId::new(15);
let second = item(13);
assert_eq!(
table.insert_with_id(second_id, second),
WarpTableInsertWithIdOutcome::Inserted {
id: second_id,
row: 1,
}
);
assert_eq!(table.ids(), [first_id, second_id]);
assert_eq!(table.columns().quantities, [11, 13]);
assert_eq!(
table.get_at(0),
WarpTableGetAtOutcome::Present {
dense_row: 0,
row: ItemRef {
id: &first_id,
quantity: &11,
},
}
);
assert_eq!(
table.get_at(2),
WarpTableGetAtOutcome::Absent { dense_row: 2 }
);
let third_id = ItemId::new(23);
let third = item(17);
assert_eq!(
table.insert_with_id(third_id, third),
WarpTableInsertWithIdOutcome::Full {
id: third_id,
rejected: third,
}
);
assert_eq!(
table.get(first_id),
WarpTableGetOutcome::Present {
row: ItemRef {
id: &first_id,
quantity: &11,
},
}
);
table.columns.quantities.pop();
assert!(catch_unwind(AssertUnwindSafe(|| table.get(second_id))).is_err());
assert!(catch_unwind(AssertUnwindSafe(|| table.get_at(1))).is_err());
table.ids.pop();
assert!(catch_unwind(AssertUnwindSafe(|| table.get_at(0))).is_err());
assert!(catch_unwind(AssertUnwindSafe(|| table.insert_with_id(third_id, third))).is_err());
Ok(())
}
#[test]
fn generated_ids_skip_restored_ids_and_report_exhaustion() -> Result<(), &'static str> {
let mut table = WarpTable::<GeneratedItem>::try_new(capacity(3)?)
.map_err(|_| "table storage was unavailable")?;
let first_id = WarpId::<GeneratedItem>::MIN;
assert!(matches!(
table.insert_with_id(first_id, GeneratedItem { quantity: 11 }),
WarpTableInsertWithIdOutcome::Inserted { .. }
));
let WarpTableInsertOutcome::Inserted {
id: inserted_id,
row: inserted_row,
} = table.insert(GeneratedItem { quantity: 13 })
else {
return Err("generated insertion failed");
};
assert_eq!(inserted_id.value().get(), 2);
assert_eq!(inserted_row, 1);
let WarpTableGetOutcome::Present { row, .. } = table.get(inserted_id) else {
return Err("generated item was unavailable");
};
assert_eq!(row.quantity, &13);
table.next_id = None;
assert_eq!(
table.insert(GeneratedItem { quantity: 17 }),
WarpTableInsertOutcome::IdentifiersExhausted {
rejected: GeneratedItem { quantity: 17 },
}
);
let mut full = WarpTable::<GeneratedItem>::try_new(capacity(1)?)
.map_err(|_| "full table storage was unavailable")?;
assert!(matches!(
full.insert(GeneratedItem { quantity: 19 }),
WarpTableInsertOutcome::Inserted { .. }
));
let next_id = full.next_id;
assert_eq!(
full.insert(GeneratedItem { quantity: 23 }),
WarpTableInsertOutcome::Full {
rejected: GeneratedItem { quantity: 23 },
}
);
assert_eq!(full.next_id, next_id);
Ok(())
}
#[test]
fn warp_table_removes_rows_and_reports_dense_relocation() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(capacity(3)?).map_err(|_| "table storage was unavailable")?;
let rows = [
(ItemId::new(7), item(11)),
(ItemId::new(15), item(13)),
(ItemId::new(23), item(17)),
];
for (id, row) in rows {
assert!(matches!(
table.insert_with_id(id, row),
WarpTableInsertWithIdOutcome::Inserted { .. }
));
}
assert_eq!(
table.remove(rows[1].0),
WarpTableRemoveOutcome::Removed {
id: rows[1].0,
removed: rows[1].1,
relocation: WarpTableRowRelocation::Relocated {
id: rows[2].0,
from: 2,
to: 1,
},
}
);
assert!(matches!(
table.get(rows[2].0),
WarpTableGetOutcome::Present { .. }
));
assert_eq!(table.ids(), [rows[0].0, rows[2].0]);
assert_eq!(table.columns().quantities, [11, 17]);
assert_eq!(
table.remove(rows[1].0),
WarpTableRemoveOutcome::Absent { id: rows[1].0 }
);
table.columns.quantities.pop();
assert!(catch_unwind(AssertUnwindSafe(|| table.remove(rows[0].0))).is_err());
Ok(())
}
#[test]
fn warp_table_replaces_only_a_present_id() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(capacity(2)?).map_err(|_| "table storage was unavailable")?;
let id = ItemId::new(7);
let original = item(11);
assert!(matches!(
table.insert_with_id(id, original),
WarpTableInsertWithIdOutcome::Inserted { .. }
));
let absent_id = ItemId::new(9);
let absent = item(17);
assert_eq!(
table.replace(absent_id, absent),
WarpTableReplaceOutcome::Absent {
id: absent_id,
rejected: absent,
}
);
let replacement = item(19);
assert_eq!(
table.replace(id, replacement),
WarpTableReplaceOutcome::Replaced {
id,
row: 0,
previous: original,
}
);
assert_eq!(table.ids(), [id]);
assert_eq!(table.columns().quantities, [replacement.quantity]);
table.columns.quantities.pop();
let rejected = item(23);
assert!(catch_unwind(AssertUnwindSafe(|| table.replace(id, rejected))).is_err());
Ok(())
}
#[test]
fn warp_table_updates_a_present_id_through_its_mutable_row() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(capacity(1)?).map_err(|_| "table storage was unavailable")?;
let id = ItemId::new(7);
assert!(matches!(
table.insert_with_id(id, item(11)),
WarpTableInsertWithIdOutcome::Inserted { .. }
));
assert_eq!(
table.update(id, |row| {
assert_eq!(*row.id, id);
let previous = *row.quantity;
*row.quantity = 13;
previous
}),
WarpTableUpdateOutcome::Updated {
id,
row: 0,
output: 11,
}
);
assert_eq!(table.columns().quantities, [13]);
assert_eq!(
table.update(ItemId::new(9), |_| ()),
WarpTableUpdateOutcome::Absent { id: ItemId::new(9) }
);
Ok(())
}
#[derive(Clone, Copy, Debug)]
enum ModelOperation {
Insert { id: ItemId, row: Item },
Replace { id: ItemId, replacement: Item },
Remove(ItemId),
Get(ItemId),
}
fn model_operation_strategy() -> impl Strategy<Value = ModelOperation> {
prop_oneof![
4 => (0_u8..32, any::<u16>()).prop_map(|(id, quantity)| ModelOperation::Insert {
id: ItemId::new(u64::from(id)),
row: item(u32::from(quantity)),
}),
3 => (0_u8..32, any::<u16>()).prop_map(|(id, quantity)| ModelOperation::Replace {
id: ItemId::new(u64::from(id)),
replacement: item(u32::from(quantity)),
}),
2 => (0_u8..32).prop_map(|id| ModelOperation::Remove(ItemId::new(u64::from(id)))),
2 => (0_u8..32).prop_map(|id| ModelOperation::Get(ItemId::new(u64::from(id)))),
]
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(128))]
#[test]
fn warp_table_matches_a_dense_reference_model(
maximum_rows in 1_u32..=16,
operations in prop::collection::vec(model_operation_strategy(), 1..128),
) {
let Some(maximum_rows) = NonZeroU32::new(maximum_rows) else {
return Err(TestCaseError::fail("generated capacity was zero"));
};
let capacity = Capacity::new(maximum_rows);
let model_capacity = usize::try_from(maximum_rows.get())
.map_err(|_| TestCaseError::fail("capacity was not representable"))?;
let mut table = WarpTable::<Item>::try_new(capacity)
.map_err(|_| TestCaseError::fail("table storage was unavailable"))?;
let mut model = Vec::new();
for operation in operations {
apply_model_operation(&mut table, &mut model, model_capacity, operation)?;
assert_table_matches_model(&table, &model)?;
}
}
}
fn apply_model_operation(
table: &mut WarpTable<Item>,
model: &mut Vec<(ItemId, Item)>,
capacity: usize,
operation: ModelOperation,
) -> TestCaseResult {
match operation {
ModelOperation::Insert { id, row } => {
let expected = match model.iter().position(|stored| stored.0 == id) {
Some(existing_row) => WarpTableInsertWithIdOutcome::AlreadyPresent {
id,
existing_row,
rejected: row,
},
None if model.len() >= capacity => {
WarpTableInsertWithIdOutcome::Full { id, rejected: row }
}
None => {
let dense_row = model.len();
model.push((id, row));
WarpTableInsertWithIdOutcome::Inserted { id, row: dense_row }
}
};
prop_assert_eq!(table.insert_with_id(id, row), expected);
}
ModelOperation::Replace { id, replacement } => {
let expected = match model.iter().position(|stored| stored.0 == id) {
Some(row) => {
let Some(stored) = model.get_mut(row) else {
return Err(TestCaseError::fail("modeled row was unavailable"));
};
let previous = mem::replace(&mut stored.1, replacement);
WarpTableReplaceOutcome::Replaced { id, row, previous }
}
None => WarpTableReplaceOutcome::Absent {
id,
rejected: replacement,
},
};
prop_assert_eq!(table.replace(id, replacement), expected);
}
ModelOperation::Remove(id) => {
let expected = match model.iter().position(|stored| stored.0 == id) {
Some(row) => {
let Some(last_row) = model.len().checked_sub(1) else {
return Err(TestCaseError::fail("located a row in an empty model"));
};
let relocation = if row == last_row {
WarpTableRowRelocation::Stable
} else {
let Some(moved) = model.get(last_row) else {
return Err(TestCaseError::fail("last model row was unavailable"));
};
WarpTableRowRelocation::Relocated {
id: moved.0,
from: last_row,
to: row,
}
};
let removed = model.swap_remove(row);
WarpTableRemoveOutcome::Removed {
id,
removed: removed.1,
relocation,
}
}
None => WarpTableRemoveOutcome::Absent { id },
};
prop_assert_eq!(table.remove(id), expected);
}
ModelOperation::Get(id) => {
let expected = match model.iter().find(|stored| stored.0 == id) {
Some(stored) => WarpTableGetOutcome::Present {
row: ItemRef {
id: &stored.0,
quantity: &stored.1.quantity,
},
},
None => WarpTableGetOutcome::Absent { id },
};
prop_assert_eq!(table.get(id), expected);
}
}
Ok(())
}
fn assert_table_matches_model(table: &WarpTable<Item>, model: &[(ItemId, Item)]) -> TestCaseResult {
prop_assert_eq!(table.len(), model.len());
prop_assert_eq!(table.is_empty(), model.is_empty());
prop_assert_eq!(table.ids().len(), model.len());
prop_assert_eq!(table.columns().quantities.len(), model.len());
for ((id, quantity), expected) in table
.ids()
.iter()
.zip(&table.columns().quantities)
.zip(model)
{
prop_assert_eq!(id, &expected.0);
prop_assert_eq!(quantity, &expected.1.quantity);
match table.get(expected.0) {
WarpTableGetOutcome::Present { row, .. } => {
prop_assert_eq!(row.id, id);
prop_assert_eq!(row.quantity, quantity);
}
WarpTableGetOutcome::Absent { .. } => {
prop_assert!(false, "indexed lookup lost a modeled row");
}
}
}
Ok(())
}