use alloc::vec::Vec;
use core::ops::{Bound, RangeBounds};
use proptest::{prelude::*, test_runner::TestCaseError};
use super::{
RangeIndex, RangeIndexCreationError, RangeIndexInconsistency, RangeIndexInsertError,
RangeIndexInsertOutcome, RangeIndexKey, RangeIndexLookupError, RangeIndexMembership,
RangeIndexMoveOutcome, RangeIndexRemoveError, RangeIndexRemoveOutcome,
};
use crate::storage::warp_table::secondary_index::StableSlot;
#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
struct NarrowKey(u8);
impl RangeIndexKey for NarrowKey {
const BITS: u32 = 2;
fn ordered_word(self) -> u64 {
u64::from(self.0)
}
}
#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
struct ZeroBitKey;
impl RangeIndexKey for ZeroBitKey {
const BITS: u32 = 0;
fn ordered_word(self) -> u64 {
0
}
}
#[test]
fn primitive_ordered_words_preserve_numeric_order() -> Result<(), &'static str> {
assert_adjacent_words_increase(i8::MIN..=i8::MAX)?;
assert_adjacent_words_increase(u8::MIN..=u8::MAX)?;
assert_adjacent_words_increase([i64::MIN, -1, 0, 1, i64::MAX])?;
assert_adjacent_words_increase([u64::MIN, 1, u64::MAX])?;
Ok(())
}
#[test]
fn lookup_honors_every_standard_bound_shape() -> Result<(), &'static str> {
let index = populated_index(&[5, 10, 10, 15, 250])?;
assert_eq!(matching_slots(&index, 10..=10)?, [1, 2]);
assert!(matching_slots(&index, 11..=11)?.is_empty());
assert_eq!(matching_slots(&index, 10..=15)?, [1, 2, 3]);
assert_eq!(matching_slots(&index, 10..15)?, [1, 2]);
assert_eq!(matching_slots(&index, ..10)?, [0]);
assert_eq!(matching_slots(&index, 10..)?, [1, 2, 3, 4]);
assert_eq!(matching_slots(&index, ..)?, [0, 1, 2, 3, 4]);
assert!(matching_slots(&index, 10..10)?.is_empty());
assert!(matches!(
index.find((Bound::Included(11), Bound::Excluded(10))),
Err(RangeIndexLookupError::ReversedBounds { .. })
));
Ok(())
}
#[test]
fn invalid_key_contracts_are_reported_without_panicking() -> Result<(), &'static str> {
assert!(matches!(
RangeIndex::<ZeroBitKey>::try_new(1),
Err(RangeIndexCreationError::InvalidBitWidth { bits: 0 })
));
let index =
RangeIndex::<NarrowKey>::try_new(1).map_err(|_| "narrow index storage was unavailable")?;
assert!(matches!(
index.find(NarrowKey(4)..),
Err(RangeIndexLookupError::OrderedWordOutsideWidth {
key: NarrowKey(4),
ordered_word: 4,
bits: 2,
})
));
Ok(())
}
#[test]
fn impossible_capacity_and_corrupt_storage_are_reported() -> Result<(), &'static str> {
assert!(matches!(
RangeIndex::<u64>::try_new(usize::MAX),
Err(RangeIndexCreationError::CapacityOverflow {
maximum_rows: usize::MAX,
bits: u64::BITS,
})
));
let mut index =
RangeIndex::<u8>::try_new(1).map_err(|_| "range index storage was unavailable")?;
let _removed = index.blocks.pop();
assert!(matches!(
index.find(..),
Err(RangeIndexLookupError::Inconsistent {
reason: RangeIndexInconsistency::BlockStorageLengthMismatch {
expected: 9,
actual: 8,
},
})
));
Ok(())
}
#[test]
fn invalid_slot_and_member_count_are_reported() -> Result<(), &'static str> {
let mut index =
RangeIndex::<u8>::try_new(1).map_err(|_| "range index storage was unavailable")?;
assert!(matches!(
index.try_prepare_insert(10, StableSlot::new(1)),
Err(RangeIndexInsertError::Inconsistent {
key: 10,
slot,
reason: RangeIndexInconsistency::SlotOutsideCapacity { maximum_rows: 1 },
}) if slot == StableSlot::new(1)
));
let _inserted = index
.try_prepare_insert(10, StableSlot::new(0))
.map_err(|_| "insertion could not be prepared")?
.commit();
index.member_count = 0;
assert!(matches!(
index.try_prepare_remove(10, StableSlot::new(0)),
Err(RangeIndexRemoveError::Inconsistent {
key: 10,
slot,
reason: RangeIndexInconsistency::MemberCountMismatch { members: 0 },
}) if slot == StableSlot::new(0)
));
Ok(())
}
#[test]
fn capacity_and_membership_counts_follow_committed_mutations() -> Result<(), &'static str> {
let mut index =
RangeIndex::<u8>::try_new(2).map_err(|_| "range index storage was unavailable")?;
assert_eq!(index.capacity(), 2);
assert_eq!(index.len(), 0);
assert!(index.is_empty());
let _inserted = index
.try_prepare_insert(10, StableSlot::new(0))
.map_err(|_| "insertion could not be prepared")?
.commit();
assert_eq!(index.capacity(), 2);
assert_eq!(index.len(), 1);
assert!(!index.is_empty());
Ok(())
}
#[test]
fn prepared_mutations_commit_or_restore_the_complete_bit_slice() -> Result<(), &'static str> {
let mut index =
RangeIndex::<u8>::try_new(2).map_err(|_| "range index storage was unavailable")?;
let first = StableSlot::new(0);
let second = StableSlot::new(1);
core::mem::drop(
index
.try_prepare_insert(10, first)
.map_err(|_| "insertion could not be prepared")?,
);
assert!(index.is_empty());
assert_eq!(matching_slots(&index, ..)?, Vec::<u32>::new());
assert_eq!(
index
.try_prepare_insert(10, first)
.map_err(|_| "insertion could not be prepared")?
.commit(),
RangeIndexInsertOutcome::Inserted {
key: 10,
slot: first,
}
);
assert_eq!(matching_slots(&index, 10..=10)?, [0]);
core::mem::drop(
index
.try_prepare_move(10, 200, first)
.map_err(|_| "move could not be prepared")?,
);
assert_eq!(matching_slots(&index, 10..=10)?, [0]);
assert_eq!(matching_slots(&index, 200..=200)?, []);
assert_eq!(
index
.try_prepare_move(10, 200, first)
.map_err(|_| "move could not be prepared")?
.commit(),
RangeIndexMoveOutcome::Moved {
source: 10,
target: 200,
slot: first,
}
);
assert_eq!(matching_slots(&index, 200..=200)?, [0]);
assert_eq!(
index
.try_prepare_insert(20, second)
.map_err(|_| "second insertion could not be prepared")?
.commit(),
RangeIndexInsertOutcome::Inserted {
key: 20,
slot: second,
}
);
assert!(matches!(
index.try_prepare_insert(30, StableSlot::new(12)),
Err(RangeIndexInsertError::Full { .. })
));
{
let _prepared = index
.try_prepare_remove(200, first)
.map_err(|_| "removal could not be prepared")?;
}
assert_eq!(matching_slots(&index, 200..=200)?, [0]);
assert_eq!(
index
.try_prepare_remove(200, first)
.map_err(|_| "removal could not be prepared")?
.commit(),
RangeIndexRemoveOutcome::Removed {
key: 200,
slot: first,
}
);
assert_eq!(matching_slots(&index, ..)?, [1]);
Ok(())
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(128))]
#[test]
fn bit_sliced_ranges_match_a_linear_model(
values in prop::collection::vec(any::<u8>(), 0..128),
start in any::<u8>(),
end in any::<u8>(),
include_start in any::<bool>(),
include_end in any::<bool>(),
) {
let index = populated_index(&values)
.map_err(TestCaseError::fail)?;
let bounds = (
if include_start { Bound::Included(start) } else { Bound::Excluded(start) },
if include_end { Bound::Included(end) } else { Bound::Excluded(end) },
);
if start > end {
let reversed = matches!(
index.find(bounds),
Err(RangeIndexLookupError::ReversedBounds { .. })
);
prop_assert!(reversed);
} else {
let actual = matching_slots(&index, bounds)
.map_err(TestCaseError::fail)?;
let expected = values
.iter()
.enumerate()
.filter(|(_, value)| {
(if include_start { **value >= start } else { **value > start })
&& (if include_end { **value <= end } else { **value < end })
})
.map(|(slot, _)| u32::try_from(slot))
.collect::<Result<Vec<_>, _>>()
.map_err(|_| TestCaseError::fail("modeled slot exceeded u32"))?;
prop_assert_eq!(actual, expected);
}
}
}
fn assert_adjacent_words_increase<Key: RangeIndexKey>(
values: impl IntoIterator<Item = Key>,
) -> Result<(), &'static str> {
let values = values.into_iter().collect::<Vec<_>>();
for pair in values.windows(2) {
let [left, right] = pair else {
return Err("adjacent window did not contain two values");
};
if left.ordered_word() >= right.ordered_word() {
return Err("ordered words did not preserve numeric order");
}
}
Ok(())
}
fn populated_index(values: &[u8]) -> Result<RangeIndex<u8>, &'static str> {
let mut index =
RangeIndex::try_new(values.len()).map_err(|_| "range index storage was unavailable")?;
for (slot, key) in values.iter().copied().enumerate() {
let stable_slot = StableSlot::new(u32::try_from(slot).map_err(|_| "slot exceeded u32")?);
let outcome = index
.try_prepare_insert(key, stable_slot)
.map_err(|_| "range index insertion could not be prepared")?
.commit();
if outcome
!= (RangeIndexInsertOutcome::Inserted {
key,
slot: stable_slot,
})
{
return Err("range index insertion reported a different member");
}
}
Ok(index)
}
fn matching_slots(
index: &RangeIndex<u8>,
bounds: impl RangeBounds<u8>,
) -> Result<Vec<u32>, &'static str> {
let membership = index.find(bounds).map_err(|_| "range lookup failed")?;
let (_, slots) = RangeIndexMembership::into_parts(membership);
Ok(slots
.map(|slots| slots.slots().map(|slot| slot.value()).collect())
.unwrap_or_default())
}