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 Key = ItemId;
type Columns = ItemColumns;
type ColumnsCreationError = TryReserveError;
type Indexes = ();
type IndexesCreationError = 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 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>(
key: &'row Self::Key,
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: key, quantity },
})
}
fn get_mut<'row>(
key: &'row Self::Key,
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: key, 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_keys_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.primary_keys.capacity() >= 2);
assert!(table.columns().quantities.capacity() >= 2);
Ok(())
}
#[test]
fn warp_table_resolves_explicit_keys_and_preserves_failures() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(capacity(2)?).map_err(|_| "table storage was unavailable")?;
let first_key = ItemId::new(7);
let first = item(11);
assert_eq!(
table.get(first_key),
WarpTableGetOutcome::Absent { key: first_key }
);
assert_eq!(
table.insert_with_id(first_key, first),
WarpTableInsertWithIdOutcome::Inserted {
key: first_key,
row: 0,
}
);
assert_eq!(
table.insert_with_id(first_key, first),
WarpTableInsertWithIdOutcome::AlreadyPresent {
key: first_key,
existing_row: 0,
rejected: first,
}
);
let second_key = ItemId::new(15);
let second = item(13);
assert_eq!(
table.insert_with_id(second_key, second),
WarpTableInsertWithIdOutcome::Inserted {
key: second_key,
row: 1,
}
);
assert_eq!(table.primary_keys(), [first_key, second_key]);
assert_eq!(table.columns().quantities, [11, 13]);
assert_eq!(
table.get_at(0),
WarpTableGetAtOutcome::Present {
dense_row: 0,
row: ItemRef {
id: &first_key,
quantity: &11,
},
}
);
assert_eq!(
table.get_at(2),
WarpTableGetAtOutcome::Absent { dense_row: 2 }
);
let third_key = ItemId::new(23);
let third = item(17);
assert_eq!(
table.insert_with_id(third_key, third),
WarpTableInsertWithIdOutcome::Full {
key: third_key,
rejected: third,
}
);
assert_eq!(
table.get(first_key),
WarpTableGetOutcome::Present {
row: ItemRef {
id: &first_key,
quantity: &11,
},
}
);
table.columns.quantities.pop();
assert!(catch_unwind(AssertUnwindSafe(|| table.get(second_key))).is_err());
assert!(catch_unwind(AssertUnwindSafe(|| table.get_at(1))).is_err());
table.primary_keys.pop();
assert!(catch_unwind(AssertUnwindSafe(|| table.get_at(0))).is_err());
assert!(catch_unwind(AssertUnwindSafe(|| table.insert_with_id(third_key, 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 {
key: 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 (key, row) in rows {
assert!(matches!(
table.insert_with_id(key, row),
WarpTableInsertWithIdOutcome::Inserted { .. }
));
}
assert_eq!(
table.remove(rows[1].0),
WarpTableRemoveOutcome::Removed {
key: rows[1].0,
removed: rows[1].1,
relocation: WarpTableRowRelocation::Relocated {
key: rows[2].0,
from: 2,
to: 1,
},
}
);
assert!(matches!(
table.get(rows[2].0),
WarpTableGetOutcome::Present { .. }
));
assert_eq!(table.primary_keys(), [rows[0].0, rows[2].0]);
assert_eq!(table.columns().quantities, [11, 17]);
assert_eq!(
table.remove(rows[1].0),
WarpTableRemoveOutcome::Absent { key: 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_key() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(capacity(2)?).map_err(|_| "table storage was unavailable")?;
let key = ItemId::new(7);
let original = item(11);
assert!(matches!(
table.insert_with_id(key, original),
WarpTableInsertWithIdOutcome::Inserted { .. }
));
let absent_key = ItemId::new(9);
let absent = item(17);
assert_eq!(
table.replace(absent_key, absent),
WarpTableReplaceOutcome::Absent {
key: absent_key,
rejected: absent,
}
);
let replacement = item(19);
assert_eq!(
table.replace(key, replacement),
WarpTableReplaceOutcome::Replaced {
key,
row: 0,
previous: original,
}
);
assert_eq!(table.primary_keys(), [key]);
assert_eq!(table.columns().quantities, [replacement.quantity]);
table.columns.quantities.pop();
let rejected = item(23);
assert!(catch_unwind(AssertUnwindSafe(|| table.replace(key, rejected))).is_err());
Ok(())
}
#[test]
fn warp_table_updates_a_present_key_through_its_mutable_row() -> Result<(), &'static str> {
let mut table =
WarpTable::<Item>::try_new(capacity(1)?).map_err(|_| "table storage was unavailable")?;
let key = ItemId::new(7);
assert!(matches!(
table.insert_with_id(key, item(11)),
WarpTableInsertWithIdOutcome::Inserted { .. }
));
assert_eq!(
table.update(key, |row| {
assert_eq!(*row.id, key);
let previous = *row.quantity;
*row.quantity = 13;
previous
}),
WarpTableUpdateOutcome::Updated {
key,
row: 0,
output: 11,
}
);
assert_eq!(table.columns().quantities, [13]);
assert_eq!(
table.update(ItemId::new(9), |_| ()),
WarpTableUpdateOutcome::Absent {
key: ItemId::new(9),
}
);
Ok(())
}
#[derive(Clone, Copy, Debug)]
enum ModelOperation {
Insert { key: ItemId, row: Item },
Replace { key: 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 {
key: ItemId::new(u64::from(id)),
row: item(u32::from(quantity)),
}),
3 => (0_u8..32, any::<u16>()).prop_map(|(id, quantity)| ModelOperation::Replace {
key: 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 { key, row } => {
let expected = match model.iter().position(|stored| stored.0 == key) {
Some(existing_row) => WarpTableInsertWithIdOutcome::AlreadyPresent {
key,
existing_row,
rejected: row,
},
None if model.len() >= capacity => {
WarpTableInsertWithIdOutcome::Full { key, rejected: row }
}
None => {
let dense_row = model.len();
model.push((key, row));
WarpTableInsertWithIdOutcome::Inserted {
key,
row: dense_row,
}
}
};
prop_assert_eq!(table.insert_with_id(key, row), expected);
}
ModelOperation::Replace { key, replacement } => {
let expected = match model.iter().position(|stored| stored.0 == key) {
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 { key, row, previous }
}
None => WarpTableReplaceOutcome::Absent {
key,
rejected: replacement,
},
};
prop_assert_eq!(table.replace(key, replacement), expected);
}
ModelOperation::Remove(key) => {
let expected = match model.iter().position(|stored| stored.0 == key) {
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 {
key: moved.0,
from: last_row,
to: row,
}
};
let removed = model.swap_remove(row);
WarpTableRemoveOutcome::Removed {
key,
removed: removed.1,
relocation,
}
}
None => WarpTableRemoveOutcome::Absent { key },
};
prop_assert_eq!(table.remove(key), expected);
}
ModelOperation::Get(key) => {
let expected = match model.iter().find(|stored| stored.0 == key) {
Some(stored) => WarpTableGetOutcome::Present {
row: ItemRef {
id: &stored.0,
quantity: &stored.1.quantity,
},
},
None => WarpTableGetOutcome::Absent { key },
};
prop_assert_eq!(table.get(key), 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.primary_keys().len(), model.len());
prop_assert_eq!(table.columns().quantities.len(), model.len());
for ((key, quantity), expected) in table
.primary_keys()
.iter()
.zip(&table.columns().quantities)
.zip(model)
{
prop_assert_eq!(key, &expected.0);
prop_assert_eq!(quantity, &expected.1.quantity);
match table.get(expected.0) {
WarpTableGetOutcome::Present { row, .. } => {
prop_assert_eq!(row.id, key);
prop_assert_eq!(row.quantity, quantity);
}
WarpTableGetOutcome::Absent { .. } => {
prop_assert!(false, "indexed lookup lost a modeled row");
}
}
}
Ok(())
}