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,
RangeIndexMoveError, 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!(matching_slots(&index, 200..=200)?.is_empty());
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())
}
#[test]
fn invalid_mutation_words_preserve_all_range_membership() -> Result<(), &'static str> {
use super::RangeIndexMoveError;
let mut index = RangeIndex::<NarrowKey>::try_new(2).map_err(|_| "storage")?;
let slot = StableSlot::new(0);
let _inserted = index
.try_prepare_insert(NarrowKey(1), slot)
.map_err(|_| "insert")?
.commit();
let before = index.blocks.clone();
assert!(matches!(
index.try_prepare_insert(NarrowKey(4), StableSlot::new(1)),
Err(RangeIndexInsertError::OrderedWordOutsideWidth {
key: NarrowKey(4),
ordered_word: 4,
bits: 2
})
));
assert!(
matches!(index.try_prepare_insert(NarrowKey(1), slot), Err(RangeIndexInsertError::AlreadyPresent { key: NarrowKey(1), slot: found }) if found == slot)
);
assert!(matches!(
index.try_prepare_remove(NarrowKey(4), slot),
Err(RangeIndexRemoveError::OrderedWordOutsideWidth {
key: NarrowKey(4),
ordered_word: 4,
bits: 2
})
));
assert!(matches!(
index.try_prepare_move(NarrowKey(4), NarrowKey(1), slot),
Err(RangeIndexMoveError::SourceOrderedWordOutsideWidth {
source: NarrowKey(4),
target: NarrowKey(1),
ordered_word: 4,
bits: 2
})
));
assert!(matches!(
index.try_prepare_move(NarrowKey(1), NarrowKey(4), slot),
Err(RangeIndexMoveError::TargetOrderedWordOutsideWidth {
source: NarrowKey(1),
target: NarrowKey(4),
ordered_word: 4,
bits: 2
})
));
assert_eq!(index.blocks, before);
assert_eq!(index.len(), 1);
assert_eq!(
index
.try_prepare_move(NarrowKey(1), NarrowKey(1), slot)
.map_err(|_| "unchanged")?
.commit(),
RangeIndexMoveOutcome::Unchanged {
key: NarrowKey(1),
slot
}
);
assert_eq!(index.blocks, before);
assert_eq!(index.len(), 1);
Ok(())
}
#[test]
fn removing_or_moving_the_wrong_range_membership_preserves_the_index() -> Result<(), &'static str> {
use super::RangeIndexMoveError;
let mut index = populated_index(&[7])?;
let slot = StableSlot::new(0);
let before = index.blocks.clone();
assert!(
matches!(index.try_prepare_remove(8, slot), Err(RangeIndexRemoveError::Inconsistent { key: 8, slot: found, reason: RangeIndexInconsistency::StoredWordMismatch { expected: 8, actual: 7 } }) if found == slot)
);
assert!(
matches!(index.try_prepare_move(8, 9, slot), Err(RangeIndexMoveError::Inconsistent { source: 8, target: 9, slot: found, reason: RangeIndexInconsistency::StoredWordMismatch { expected: 8, actual: 7 } }) if found == slot)
);
assert_eq!(index.blocks, before);
assert_eq!(index.len(), 1);
let _removed = index
.try_prepare_remove(7, slot)
.map_err(|_| "remove")?
.commit();
assert!(
matches!(index.try_prepare_remove(7, slot), Err(RangeIndexRemoveError::Inconsistent { key: 7, slot: found, reason: RangeIndexInconsistency::MemberAbsent }) if found == slot)
);
assert!(
matches!(index.try_prepare_move(7, 8, slot), Err(RangeIndexMoveError::Inconsistent { source: 7, target: 8, slot: found, reason: RangeIndexInconsistency::MemberAbsent }) if found == slot)
);
assert!(index.is_empty());
assert!(matching_slots(&index, ..)?.is_empty());
Ok(())
}
#[test]
fn stale_bit_planes_refuse_new_members_without_publishing() -> Result<(), &'static str> {
let mut index = populated_index(&[7])?;
let slot = StableSlot::new(0);
let Some(members) = index.blocks.first_mut() else {
return Err("membership word");
};
*members = 0;
index.member_count = 0;
let before = index.blocks.clone();
assert!(
matches!(index.try_prepare_insert(9, slot), Err(RangeIndexInsertError::Inconsistent { key: 9, slot: found, reason: RangeIndexInconsistency::StaleBitMembership { bit: 0 } }) if found == slot)
);
assert_eq!(index.blocks, before);
assert_eq!(index.len(), 0);
Ok(())
}
#[test]
fn invalid_storage_dimensions_are_refused_before_editing_any_bit_planes() -> Result<(), &'static str>
{
let mut index = RangeIndex::<u64>::try_new(1).map_err(|_| "allocation")?;
let original = index.blocks.clone();
index.maximum_rows = usize::MAX;
assert!(matches!(
index.find(..),
Err(RangeIndexLookupError::Inconsistent {
reason: RangeIndexInconsistency::StorageCapacityOverflow {
maximum_rows: usize::MAX,
bits: 64
}
})
));
assert!(matches!(
index.try_prepare_move(0, 1, StableSlot::new(0)),
Err(RangeIndexMoveError::Inconsistent {
reason: RangeIndexInconsistency::StorageCapacityOverflow {
maximum_rows: usize::MAX,
bits: 64
},
..
})
));
assert_eq!(index.blocks, original);
assert_eq!(index.member_count, 0);
Ok(())
}