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<Key: RangeIndexKey>(
index: &RangeIndex<Key>,
bounds: impl RangeBounds<Key>,
) -> 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(())
}
#[test]
fn caller_workspace_reuses_words_and_matches_every_bound_shape() -> Result<(), &'static str> {
use super::RangeQueryWorkspace;
for count in [0, 1, 63, 64, 65, 129] {
let mut index = RangeIndex::<u8>::try_new(count).map_err(|_| "index")?;
let values = (0..count)
.map(|value| u8::try_from(value).map_err(|_| "key"))
.collect::<Result<Vec<_>, _>>()?;
for (slot, key) in values.iter().copied().enumerate() {
let slot = StableSlot::new(u32::try_from(slot).map_err(|_| "slot")?);
let _inserted = index
.try_prepare_insert(key, slot)
.map_err(|_| "insert")?
.commit();
}
let required = count.div_ceil(64);
let mut storage = alloc::vec![u64::MAX; required.checked_add(1).ok_or("length")?];
{
let mut workspace = RangeQueryWorkspace::new(&mut storage);
for lower in [
Bound::Unbounded,
Bound::Included(0),
Bound::Excluded(0),
Bound::Included(64),
Bound::Excluded(64),
Bound::Included(255),
] {
for upper in [
Bound::Unbounded,
Bound::Included(0),
Bound::Excluded(0),
Bound::Included(64),
Bound::Excluded(64),
Bound::Included(255),
] {
let range = (lower, upper);
let result = index.find_with(range, &mut workspace);
if let (
Bound::Included(a) | Bound::Excluded(a),
Bound::Included(b) | Bound::Excluded(b),
) = range
&& a > b
{
assert!(matches!(
result,
Err(super::RangeWorkspaceLookupError::Lookup {
reason: RangeIndexLookupError::ReversedBounds { .. }
})
));
continue;
}
let (bounds, words, len) = result.map_err(|_| "lookup")?.into_parts();
assert_eq!(bounds, super::RangeIndexBounds::from_range(range));
assert_eq!(words.len(), required);
let expected = values.iter().filter(|value| range.contains(value)).count();
assert_eq!(len, u64::try_from(expected).map_err(|_| "count")?);
for (slot, value) in values.iter().enumerate() {
let word = words.get(slot / 64).ok_or("word")?;
assert_eq!(
word & 1_u64.rotate_left(u32::try_from(slot % 64).map_err(|_| "bit")?)
!= 0,
range.contains(value)
);
}
let owned = index
.find(range)
.map_err(|_| "owned lookup")?
.into_parts()
.1;
assert_eq!(owned.as_ref().map_or(0, |slots| slots.len()), len);
}
}
}
assert_eq!(storage.last(), Some(&u64::MAX));
}
let index = RangeIndex::<u8>::try_new(65).map_err(|_| "index")?;
let mut storage = [19];
let mut workspace = RangeQueryWorkspace::new(&mut storage);
assert!(matches!(
index.find_with(.., &mut workspace),
Err(super::RangeWorkspaceLookupError::WorkspaceTooSmall {
required_words: 2,
available_words: 1
})
));
assert_eq!(storage, [19]);
Ok(())
}
#[test]
fn workspace_refusals_preserve_invalid_keys_and_storage_coordinates() -> Result<(), &'static str> {
use super::{RangeQueryWorkspace, RangeWorkspaceLookupError};
let mut words = [19];
let mut workspace = RangeQueryWorkspace::new(&mut words);
let index = RangeIndex::<NarrowKey>::try_new(1).map_err(|_| "index")?;
for bounds in [
(Bound::Included(NarrowKey(4)), Bound::Unbounded),
(Bound::Unbounded, Bound::Included(NarrowKey(4))),
] {
assert!(matches!(
index.find_with(bounds, &mut workspace),
Err(RangeWorkspaceLookupError::Lookup {
reason: RangeIndexLookupError::OrderedWordOutsideWidth {
key: NarrowKey(4),
ordered_word: 4,
bits: 2,
},
})
));
}
let mut index = RangeIndex::<u8>::try_new(1).map_err(|_| "index")?;
let _removed = index.blocks.pop();
assert!(matches!(
index.find_with(.., &mut workspace),
Err(RangeWorkspaceLookupError::Lookup {
reason: RangeIndexLookupError::Inconsistent {
reason: RangeIndexInconsistency::BlockStorageLengthMismatch {
expected: 9,
actual: 8
},
},
})
));
assert_eq!(words, [19]);
Ok(())
}
#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
struct WordKey<const BITS: u32>(u64);
impl<const BITS: u32> RangeIndexKey for WordKey<BITS> {
const BITS: u32 = BITS;
fn ordered_word(self) -> u64 {
self.0
}
}
fn exercise_word_mutations<const BITS: u32>(
values: [u64; 9],
target: usize,
replacement: u64,
) -> Result<(), &'static str> {
let mask = u64::MAX
.checked_shr(u64::BITS.abs_diff(BITS))
.unwrap_or_default();
let mut values = values.map(|value| WordKey::<BITS>(value & mask));
let replacement = WordKey::<BITS>(replacement & mask);
let slots = [0, 1, 62, 63, 64, 65, 126, 127, 128];
let slot = StableSlot::new(*slots.get(target).ok_or("target slot")?);
let source = *values.get(target).ok_or("source key")?;
let mut index = RangeIndex::try_new(129).map_err(|_| "storage")?;
for (slot, value) in slots.into_iter().zip(values) {
let _inserted = index
.try_prepare_insert(value, StableSlot::new(slot))
.map_err(|_| "insert")?
.commit();
}
let before = index.blocks.clone();
drop(
index
.try_prepare_move(source, replacement, slot)
.map_err(|_| "cancel move")?,
);
assert_eq!(index.blocks, before);
assert_eq!(index.len(), 9);
drop(
index
.try_prepare_remove(source, slot)
.map_err(|_| "cancel removal")?,
);
assert_eq!(index.blocks, before);
assert_eq!(index.len(), 9);
let _removed = index
.try_prepare_remove(source, slot)
.map_err(|_| "remove")?
.commit();
let removed = index.blocks.clone();
drop(
index
.try_prepare_insert(replacement, slot)
.map_err(|_| "cancel insertion")?,
);
assert_eq!(index.blocks, removed);
assert_eq!(index.len(), 8);
let _inserted = index
.try_prepare_insert(source, slot)
.map_err(|_| "reinsert")?
.commit();
assert_eq!(index.blocks, before);
let _moved = index
.try_prepare_move(source, replacement, slot)
.map_err(|_| "move")?
.commit();
*values.get_mut(target).ok_or("target key")? = replacement;
assert_eq!(index.len(), 9);
for boundary in values {
let expected = slots
.into_iter()
.zip(values)
.filter_map(|(slot, value)| (value <= boundary).then_some(slot))
.collect::<Vec<_>>();
assert_eq!(matching_slots(&index, ..=boundary)?, expected);
}
for (slot, value) in slots.into_iter().zip(values) {
let _removed = index
.try_prepare_remove(value, StableSlot::new(slot))
.map_err(|_| "drain")?
.commit();
}
assert!(index.is_empty());
assert!(index.blocks.iter().all(|word| *word == 0));
Ok(())
}
#[test]
fn full_width_extremes_preserve_neighbors_and_restore_cancelled_edits() -> Result<(), &'static str>
{
let values = [
0,
1,
1 << 63,
u64::MAX,
u64::MAX >> 1,
0x5555_5555_5555_5555,
0xAAAA_AAAA_AAAA_AAAA,
1 << 32,
(1 << 32) - 1,
];
for target in 0..values.len() {
for replacement in values {
exercise_word_mutations::<64>(values, target, replacement)?;
}
}
Ok(())
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(128))]
#[test]
fn arbitrary_word_widths_preserve_mutations_and_cancellation(
values in any::<[u64; 9]>(),
target in 0_usize..9,
replacement in any::<u64>(),
) {
exercise_word_mutations::<1>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<2>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<7>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<8>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<9>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<15>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<16>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<17>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<31>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<32>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<33>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<63>(values, target, replacement).map_err(TestCaseError::fail)?;
exercise_word_mutations::<64>(values, target, replacement).map_err(TestCaseError::fail)?;
}
}