#![cfg(all(feature = "storage", feature = "secondary-indexes"))]
use core::cmp::Ordering;
use core::num::NonZeroU32;
use pipecircuit::storage::warp_table::{
Capacity, OrderedRowLimit, OrderedSelection, OrderedSelectionFirstCuttingTiesOutcome,
OrderedSelectionFirstKeepingTiesOutcome, RangeIndexOrdering, WarpId, WarpTable,
WarpTableInsertOutcome, WarpTableRemoveOutcome, WarpTableRow,
};
use proptest::{prelude::*, test_runner::TestCaseError};
#[derive(WarpTableRow)]
struct Entry {
#[index(range)]
rank: u8,
#[index(range)]
weight: i16,
#[index(secondary)]
group: u8,
label: u16,
}
#[derive(Clone, Copy)]
struct ModeledEntry {
id: WarpId<Entry>,
rank: u8,
weight: i16,
group: u8,
label: u16,
}
#[derive(Clone, Copy, Debug)]
enum Operation {
Insert {
rank: u8,
weight: i16,
group: u8,
label: u16,
},
Remove {
position: usize,
},
}
#[derive(Clone, Copy, Debug)]
enum Candidates {
EveryRow,
Group(u8),
RankAtLeast(u8),
}
#[derive(Clone, Copy, Debug)]
enum Level {
LargestRank,
SmallestRank,
LargestWeight,
SmallestWeight,
}
#[derive(Clone, Copy, Debug)]
enum RowComparison {
Absent,
LabelAscending,
LabelDescending,
}
#[derive(Clone, Copy, Debug)]
enum TiePolicy {
Cut,
Keep,
}
type ModelKey = (Vec<i32>, Option<i32>);
const CAPACITY: u32 = 48;
proptest! {
#![proptest_config(ProptestConfig::with_cases(512))]
#[test]
fn ordered_selections_match_a_sorted_model(
operations in prop::collection::vec(operation(), 1..90),
candidates in candidates(),
first_level in level(),
second_level in prop::option::of(level()),
row_comparison in row_comparison(),
tie_policy in prop_oneof![Just(TiePolicy::Cut), Just(TiePolicy::Keep)],
limit in 1..20_u32,
) {
let (entries, model) = apply(&operations)?;
let limit_rows = usize::try_from(limit).map_err(|_| TestCaseError::fail("limit exceeded usize"))?;
let limit = OrderedRowLimit::new(
NonZeroU32::new(limit).ok_or(TestCaseError::fail("limit was zero"))?,
);
let levels = core::iter::once(first_level).chain(second_level).collect::<Vec<_>>();
let candidate_entries = model
.iter()
.copied()
.filter(|entry| candidates.includes(entry))
.collect::<Vec<_>>();
let key = |entry: &ModeledEntry| model_key(entry, &levels, row_comparison);
let expected = Expected::new(&candidate_entries, limit_rows, key);
let ordered = ordered(&entries, candidates, first_level, second_level)?;
let observed = match (row_comparison, tie_policy) {
(RowComparison::Absent, TiePolicy::Cut) => {
observed_cut(ordered.first_cutting_ties(limit), &model, key)?
}
(RowComparison::Absent, TiePolicy::Keep) => {
observed_kept(ordered.first_keeping_ties(limit), &model, key)?
}
(RowComparison::LabelAscending, TiePolicy::Cut) => observed_cut(
ordered
.then_compare_rows(|left, right| left.label.cmp(right.label))
.first_cutting_ties(limit),
&model,
key,
)?,
(RowComparison::LabelAscending, TiePolicy::Keep) => observed_kept(
ordered
.then_compare_rows(|left, right| left.label.cmp(right.label))
.first_keeping_ties(limit),
&model,
key,
)?,
(RowComparison::LabelDescending, TiePolicy::Cut) => observed_cut(
ordered
.then_compare_rows(|left, right| right.label.cmp(left.label))
.first_cutting_ties(limit),
&model,
key,
)?,
(RowComparison::LabelDescending, TiePolicy::Keep) => observed_kept(
ordered
.then_compare_rows(|left, right| right.label.cmp(left.label))
.first_keeping_ties(limit),
&model,
key,
)?,
};
expected.admits(&observed, limit_rows, tie_policy)?;
}
}
struct Expected {
leaders: Vec<ModeledEntry>,
tied: Vec<ModeledEntry>,
needed: usize,
exact: bool,
}
enum Observed {
Exact(Vec<ModeledEntry>),
TiesCut(Vec<ModeledEntry>, usize),
TiesKept(Vec<ModeledEntry>, Vec<ModeledEntry>),
}
impl Expected {
fn new(
candidates: &[ModeledEntry],
limit: usize,
key: impl Fn(&ModeledEntry) -> ModelKey,
) -> Self {
let mut sorted = candidates.to_vec();
sorted.sort_by_key(&key);
let Some(cutoff) = sorted.get(limit.saturating_sub(1)).map(&key) else {
return Self {
leaders: sorted,
tied: Vec::new(),
needed: 0,
exact: true,
};
};
let (leaders, rest): (Vec<_>, Vec<_>) =
sorted.into_iter().partition(|entry| key(entry) < cutoff);
let tied = rest
.into_iter()
.filter(|entry| key(entry) == cutoff)
.collect::<Vec<_>>();
let needed = limit.saturating_sub(leaders.len());
Self {
exact: tied.len() == needed,
leaders,
tied,
needed,
}
}
fn admits(
&self,
observed: &Observed,
limit: usize,
tie_policy: TiePolicy,
) -> Result<(), TestCaseError> {
match (observed, self.exact, tie_policy) {
(Observed::Exact(rows), true, TiePolicy::Cut | TiePolicy::Keep) => {
let winners = [self.leaders.as_slice(), self.tied.as_slice()].concat();
prop_assert_eq!(ids(rows), ids(&winners));
prop_assert!(rows.len() <= limit);
}
(Observed::TiesCut(rows, tied_rows_left_out), false, TiePolicy::Cut) => {
let (leaders, from_tied) = rows.split_at(self.leaders.len().min(rows.len()));
prop_assert_eq!(rows.len(), limit);
prop_assert_eq!(ids(leaders), ids(&self.leaders));
prop_assert_eq!(from_tied.len(), self.needed);
prop_assert!(
from_tied
.iter()
.all(|entry| self.tied.iter().any(|tied| tied.id == entry.id))
);
prop_assert_eq!(
*tied_rows_left_out,
self.tied.len().saturating_sub(self.needed)
);
}
(Observed::TiesKept(leaders, tied), false, TiePolicy::Keep) => {
prop_assert_eq!(ids(leaders), ids(&self.leaders));
prop_assert_eq!(ids(tied), ids(&self.tied));
prop_assert!(leaders.len() < limit);
prop_assert!(leaders.len().saturating_add(tied.len()) > limit);
}
(
Observed::Exact(_) | Observed::TiesCut(..) | Observed::TiesKept(..),
true | false,
TiePolicy::Cut | TiePolicy::Keep,
) => {
return Err(TestCaseError::fail(
"outcome variant disagreed with the model",
));
}
}
Ok(())
}
}
impl Candidates {
const fn includes(self, entry: &ModeledEntry) -> bool {
match self {
Self::EveryRow => true,
Self::Group(group) => entry.group == group,
Self::RankAtLeast(rank) => entry.rank >= rank,
}
}
}
fn ordered<'table>(
entries: &'table WarpTable<Entry>,
candidates: Candidates,
first_level: Level,
second_level: Option<Level>,
) -> Result<OrderedSelection<'table, Entry>, TestCaseError> {
let order = |q: EntryQuery<'table, Entry>| {
let first = level_ordering(&q, first_level);
match second_level {
Some(second_level) => first.then(level_ordering(&q, second_level)),
None => first,
}
};
Ok(match candidates {
Candidates::EveryRow => entries.query().ordered_by(order),
Candidates::Group(group) => entries.query().find_group(group).ordered_by(order),
Candidates::RankAtLeast(rank) => entries
.query()
.find_rank_in(rank..)
.map_err(|_| TestCaseError::fail("rank range was unavailable"))?
.ordered_by(order),
})
}
fn level_ordering<'table>(
q: &EntryQuery<'table, Entry>,
level: Level,
) -> RangeIndexOrdering<'table, Entry> {
match level {
Level::LargestRank => q.rank_largest_first(),
Level::SmallestRank => q.rank_smallest_first(),
Level::LargestWeight => q.weight_largest_first(),
Level::SmallestWeight => q.weight_smallest_first(),
}
}
fn model_key(entry: &ModeledEntry, levels: &[Level], row_comparison: RowComparison) -> ModelKey {
let level_keys = levels
.iter()
.map(|level| match level {
Level::LargestRank => i32::from(entry.rank).wrapping_neg(),
Level::SmallestRank => i32::from(entry.rank),
Level::LargestWeight => i32::from(entry.weight).wrapping_neg(),
Level::SmallestWeight => i32::from(entry.weight),
})
.collect();
let comparison_key = match row_comparison {
RowComparison::Absent => None,
RowComparison::LabelAscending => Some(i32::from(entry.label)),
RowComparison::LabelDescending => Some(i32::from(entry.label).wrapping_neg()),
};
(level_keys, comparison_key)
}
fn observed_cut(
outcome: Result<
OrderedSelectionFirstCuttingTiesOutcome<EntryRef<'_>>,
pipecircuit::storage::warp_table::RangeIndexOrderingError,
>,
model: &[ModeledEntry],
key: impl Fn(&ModeledEntry) -> ModelKey,
) -> Result<Observed, TestCaseError> {
match outcome.map_err(|_| TestCaseError::fail("ordering was inconsistent"))? {
OrderedSelectionFirstCuttingTiesOutcome::Exact { rows } => {
Ok(Observed::Exact(in_key_order(&rows, model, &key)?))
}
OrderedSelectionFirstCuttingTiesOutcome::TiesCut {
rows,
tied_rows_left_out,
} => Ok(Observed::TiesCut(
in_key_order(&rows, model, &key)?,
tied_rows_left_out,
)),
}
}
fn observed_kept(
outcome: Result<
OrderedSelectionFirstKeepingTiesOutcome<EntryRef<'_>>,
pipecircuit::storage::warp_table::RangeIndexOrderingError,
>,
model: &[ModeledEntry],
key: impl Fn(&ModeledEntry) -> ModelKey,
) -> Result<Observed, TestCaseError> {
match outcome.map_err(|_| TestCaseError::fail("ordering was inconsistent"))? {
OrderedSelectionFirstKeepingTiesOutcome::Exact { rows } => {
Ok(Observed::Exact(in_key_order(&rows, model, &key)?))
}
OrderedSelectionFirstKeepingTiesOutcome::TiesKept { leaders, tied } => {
let tied = modeled(&tied, model)?;
let tied_key = tied.first().map(&key);
prop_assert!(tied.iter().all(|entry| Some(key(entry)) == tied_key));
Ok(Observed::TiesKept(
in_key_order(&leaders, model, &key)?,
tied,
))
}
}
}
fn in_key_order(
rows: &[EntryRef<'_>],
model: &[ModeledEntry],
key: impl Fn(&ModeledEntry) -> ModelKey,
) -> Result<Vec<ModeledEntry>, TestCaseError> {
let entries = modeled(rows, model)?;
let in_order = entries.windows(2).all(|pair| match pair {
[left, right] => key(left).cmp(&key(right)) != Ordering::Greater,
_ => false,
});
prop_assert!(in_order);
Ok(entries)
}
fn modeled(
rows: &[EntryRef<'_>],
model: &[ModeledEntry],
) -> Result<Vec<ModeledEntry>, TestCaseError> {
rows.iter()
.map(|row| {
let entry = model
.iter()
.find(|entry| entry.id == *row.id)
.copied()
.ok_or(TestCaseError::fail("row was not modeled"))?;
prop_assert_eq!(
(entry.rank, entry.weight, entry.group, entry.label),
(*row.rank, *row.weight, *row.group, *row.label)
);
Ok(entry)
})
.collect()
}
fn ids(entries: &[ModeledEntry]) -> Vec<u64> {
let mut ids = entries
.iter()
.map(|entry| entry.id.value().get())
.collect::<Vec<_>>();
ids.sort_unstable();
ids
}
fn apply(operations: &[Operation]) -> Result<(WarpTable<Entry>, Vec<ModeledEntry>), TestCaseError> {
let capacity =
Capacity::new(NonZeroU32::new(CAPACITY).ok_or(TestCaseError::fail("capacity was zero"))?);
let mut entries = WarpTable::<Entry>::try_new(capacity)
.map_err(|_| TestCaseError::fail("entry storage was unavailable"))?;
let mut model = Vec::new();
for operation in operations.iter().copied() {
match operation {
Operation::Insert {
rank,
weight,
group,
label,
} => match entries.insert(Entry {
rank,
weight,
group,
label,
}) {
WarpTableInsertOutcome::Inserted { id, .. } => model.push(ModeledEntry {
id,
rank,
weight,
group,
label,
}),
WarpTableInsertOutcome::Full { .. } => {
prop_assert_eq!(model.len(), entries.len());
}
WarpTableInsertOutcome::IdentifiersExhausted { .. }
| WarpTableInsertOutcome::UniqueConflict { .. } => {
return Err(TestCaseError::fail("insertion failed unexpectedly"));
}
},
Operation::Remove { position } => {
let Some(position) = position.checked_rem(model.len()) else {
continue;
};
let removed = model.swap_remove(position);
let removed = matches!(
entries.remove(removed.id),
WarpTableRemoveOutcome::Removed { .. }
);
prop_assert!(removed);
}
}
}
Ok((entries, model))
}
fn operation() -> impl Strategy<Value = Operation> {
prop_oneof![
3 => (0..6_u8, -3..3_i16, 0..3_u8, 0..5_u16).prop_map(|(rank, weight, group, label)| {
Operation::Insert { rank, weight, group, label }
}),
1 => any::<usize>().prop_map(|position| Operation::Remove { position }),
]
}
fn candidates() -> impl Strategy<Value = Candidates> {
prop_oneof![
Just(Candidates::EveryRow),
(0..4_u8).prop_map(Candidates::Group),
(0..7_u8).prop_map(Candidates::RankAtLeast),
]
}
fn level() -> impl Strategy<Value = Level> {
prop_oneof![
Just(Level::LargestRank),
Just(Level::SmallestRank),
Just(Level::LargestWeight),
Just(Level::SmallestWeight),
]
}
fn row_comparison() -> impl Strategy<Value = RowComparison> {
prop_oneof![
Just(RowComparison::Absent),
Just(RowComparison::LabelAscending),
Just(RowComparison::LabelDescending),
]
}