use alloc::vec::Vec;
use core::{mem, num::NonZeroU32};
use proptest::{
prelude::*,
test_runner::{TestCaseError, TestCaseResult},
};
use crate::storage::warp_table::{
Capacity, RangeIndexLookupOutcome, SecondaryIndexLookupOutcome, Selection, WarpTable,
WarpTableInsertWithIdOutcome, WarpTableRemoveOutcome, WarpTableReplaceOutcome, WarpTableRow,
WarpTableRowRelocation,
};
#[derive(Clone, Copy, Debug, Eq, WarpTableRow, PartialEq)]
#[index(primary = u8)]
struct ModelItem {
#[index(range)]
quantity: u16,
#[index(secondary)]
category: u8,
#[index(secondary)]
status: u8,
}
#[derive(Clone, Copy, Debug)]
enum Operation {
Insert { id: u8, row: ModelItem },
Replace { id: u8, row: ModelItem },
Remove { id: u8 },
}
fn operation() -> impl Strategy<Value = Operation> {
let row = (any::<u16>(), 0_u8..4, 0_u8..3).prop_map(|(quantity, category, status)| ModelItem {
quantity,
category,
status,
});
prop_oneof![
4 => (0_u8..16, row.clone()).prop_map(|(id, row)| Operation::Insert { id, row }),
3 => (0_u8..16, row).prop_map(|(id, row)| Operation::Replace { id, row }),
2 => (0_u8..16).prop_map(|id| Operation::Remove { id }),
]
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(128))]
#[test]
fn secondary_indexes_match_a_dense_reference_model(
maximum_rows in 1_u32..=12,
operations in prop::collection::vec(operation(), 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 maximum_rows = usize::try_from(maximum_rows.get())
.map_err(|_| TestCaseError::fail("capacity was not representable"))?;
let mut table = WarpTable::<ModelItem>::try_new(capacity)
.map_err(|_| TestCaseError::fail("table storage was unavailable"))?;
let mut model = Vec::new();
for operation in operations {
apply(&mut table, &mut model, maximum_rows, operation)?;
assert_model(&table, &model)?;
}
}
}
fn apply(
table: &mut WarpTable<ModelItem>,
model: &mut Vec<(u8, ModelItem)>,
capacity: usize,
operation: Operation,
) -> Result<(), TestCaseError> {
match operation {
Operation::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);
}
Operation::Replace { id, row } => {
let expected = match model.iter().position(|stored| stored.0 == id) {
Some(dense_row) => {
let Some(stored) = model.get_mut(dense_row) else {
return Err(TestCaseError::fail("modeled row was unavailable"));
};
WarpTableReplaceOutcome::Replaced {
id,
row: dense_row,
previous: mem::replace(&mut stored.1, row),
}
}
None => WarpTableReplaceOutcome::Absent { id, rejected: row },
};
prop_assert_eq!(table.replace(id, row), expected);
}
Operation::Remove { id } => {
let expected = match model.iter().position(|stored| stored.0 == id) {
Some(dense_row) => remove_model_row(model, id, dense_row)?,
None => WarpTableRemoveOutcome::Absent { id },
};
prop_assert_eq!(table.remove(id), expected);
}
}
Ok(())
}
fn remove_model_row(
model: &mut Vec<(u8, ModelItem)>,
id: u8,
dense_row: usize,
) -> Result<WarpTableRemoveOutcome<u8, ModelItem>, TestCaseError> {
let Some(last_row) = model.len().checked_sub(1) else {
return Err(TestCaseError::fail("located a row in an empty model"));
};
let relocation = if dense_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: dense_row,
}
};
let removed = model.swap_remove(dense_row);
Ok(WarpTableRemoveOutcome::Removed {
id,
removed: removed.1,
relocation,
})
}
fn assert_model(table: &WarpTable<ModelItem>, model: &[(u8, ModelItem)]) -> TestCaseResult {
prop_assert_eq!(table.len(), model.len());
let mut rows = table.rows();
for (dense_row, expected) in model.iter().enumerate() {
let Some(row) = rows.next() else {
return Err(TestCaseError::fail("modeled dense row was unavailable"));
};
prop_assert_eq!(*row.id, expected.0);
prop_assert_eq!(
dense_row,
model
.iter()
.position(|stored| stored.0 == *row.id)
.ok_or_else(|| TestCaseError::fail("indexed row was absent from the model"))?
);
prop_assert_eq!(
(row.quantity, row.category, row.status),
(
&expected.1.quantity,
&expected.1.category,
&expected.1.status,
)
);
}
prop_assert!(rows.next().is_none());
for category in 0_u8..4 {
let expected = matching_ids(model, |row| row.category == category);
assert_lookup(table.query().find_category(category), expected)?;
}
for status in 0_u8..3 {
let expected = matching_ids(model, |row| row.status == status);
assert_lookup(table.query().find_status(status), expected)?;
}
for (start, end) in [(0, 1024), (1025, 32_767), (32_768, u16::MAX)] {
let expected = matching_ids(model, |row| (start..=end).contains(&row.quantity));
let lookup = table
.query()
.find_quantity_in(start..=end)
.map_err(|_| TestCaseError::fail("range index was inconsistent"))?;
match lookup {
RangeIndexLookupOutcome::Absent { .. } => prop_assert!(expected.is_empty()),
RangeIndexLookupOutcome::Present { selection, .. } => {
prop_assert!(!expected.is_empty());
assert_selection_ids(selection, expected)?;
}
}
}
assert_intersections(table, model)
}
fn matching_ids(model: &[(u8, ModelItem)], predicate: impl Fn(&ModelItem) -> bool) -> Vec<u8> {
model
.iter()
.filter(|stored| predicate(&stored.1))
.map(|stored| stored.0)
.collect()
}
fn assert_lookup(
lookup: SecondaryIndexLookupOutcome<'_, ModelItem, ModelItem, u8>,
expected: Vec<u8>,
) -> TestCaseResult {
match lookup {
SecondaryIndexLookupOutcome::Absent { .. } => prop_assert!(expected.is_empty()),
SecondaryIndexLookupOutcome::Present { selection, .. } => {
prop_assert!(!expected.is_empty());
assert_selection_ids(selection, expected)?;
}
}
Ok(())
}
fn assert_selection_ids(
selection: Selection<'_, ModelItem>,
mut expected: Vec<u8>,
) -> TestCaseResult {
let mut actual = Vec::new();
for row in selection.rows() {
actual.push(*row.id);
}
actual.sort_unstable();
expected.sort_unstable();
prop_assert_eq!(actual, expected);
Ok(())
}
fn assert_intersections(table: &WarpTable<ModelItem>, model: &[(u8, ModelItem)]) -> TestCaseResult {
for category in 0_u8..4 {
for status in 0_u8..3 {
let expected = matching_ids(model, |row| {
row.category == category && row.status == status
});
let selection = table
.query()
.find_category(category)
.and(|q| q.find_status(status));
assert_selection_ids(selection, expected)?;
}
}
Ok(())
}