use alloc::vec::Vec;
extern crate std;
use self::std::panic::{AssertUnwindSafe, catch_unwind};
use super::{
SecondaryIndex, SecondaryIndexInsertError, SecondaryIndexInsertOutcome,
SecondaryIndexMoveError, SecondaryIndexMoveOutcome, SecondaryIndexPrepareRemoveOutcome,
SecondaryIndexRemoveOutcome,
};
use crate::storage::warp_table::IndexKey;
use crate::storage::warp_table::secondary_index::StableSlot;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) struct Key(pub(super) u64);
impl IndexKey for Key {
fn index_word(self) -> u64 {
self.0
}
}
#[test]
fn insertion_distinguishes_new_and_existing_keys() -> Result<(), &'static str> {
let mut index = SecondaryIndex::try_new(2).map_err(|_| "index storage unavailable")?;
assert!(index.is_empty());
assert_eq!(index.len(), 0);
let key = Key(7);
let first = StableSlot::new(3);
let second = StableSlot::new(5);
assert_eq!(
index
.try_prepare_insert(key, first)
.map_err(|_| "first preparation failed")?
.commit(),
SecondaryIndexInsertOutcome::CreatedBucket {
secondary_key: key,
slot: first,
}
);
assert_eq!(
index
.try_prepare_insert(key, second)
.map_err(|_| "second preparation failed")?
.commit(),
SecondaryIndexInsertOutcome::AddedToBucket {
secondary_key: key,
slot: second,
}
);
let lookup = index.find(key);
let slots = lookup.slots().ok_or("key was absent")?;
assert_eq!(slots.slots().collect::<Vec<_>>(), [first, second]);
assert_eq!(index.len(), 1);
assert!(!index.is_empty());
Ok(())
}
#[test]
fn abandoned_preparations_and_duplicates_preserve_membership() -> Result<(), &'static str> {
let mut index = SecondaryIndex::try_new(2).map_err(|_| "index storage unavailable")?;
let key = Key(11);
let first = StableSlot::new(1);
{
let prepared = index
.try_prepare_insert(key, first)
.map_err(|_| "vacant preparation failed")?;
assert_eq!((prepared.secondary_key(), prepared.slot()), (key, first));
}
let lookup = index.find(key);
assert!(lookup.slots().is_none() && *lookup.secondary_key() == key);
assert_eq!(
index
.try_prepare_insert(key, first)
.map_err(|_| "committed preparation failed")?
.commit(),
SecondaryIndexInsertOutcome::CreatedBucket {
secondary_key: key,
slot: first,
}
);
let second = StableSlot::new(2);
drop(
index
.try_prepare_insert(key, second)
.map_err(|_| "existing preparation failed")?,
);
let lookup = index.find(key);
let slots = lookup.slots().ok_or("key was absent")?;
assert_eq!(slots.slots().collect::<Vec<_>>(), [first]);
assert!(matches!(
index.try_prepare_insert(key, first),
Err(SecondaryIndexInsertError::AlreadyPresent {
secondary_key: duplicate,
slot,
})
if duplicate == key && slot == first
));
Ok(())
}
#[test]
fn distinct_key_capacity_is_explicit() -> Result<(), &'static str> {
let mut index = SecondaryIndex::try_new(1).map_err(|_| "index storage unavailable")?;
assert_eq!(
index
.try_prepare_insert(Key(1), StableSlot::new(0))
.map_err(|_| "first preparation failed")?
.commit(),
SecondaryIndexInsertOutcome::CreatedBucket {
secondary_key: Key(1),
slot: StableSlot::new(0),
}
);
assert!(matches!(
index.try_prepare_insert(Key(2), StableSlot::new(1)),
Err(SecondaryIndexInsertError::Full {
secondary_key: Key(2),
slot,
maximum_distinct_keys: 1,
}) if slot == StableSlot::new(1)
));
Ok(())
}
#[test]
fn lookup_fails_fast_for_broken_index_storage() -> Result<(), &'static str> {
let mut index = SecondaryIndex::try_new(1).map_err(|_| "index storage unavailable")?;
let key = Key(1);
insert_membership(&mut index, key, StableSlot::new(0))?;
index.slot_sets.pop();
assert!(catch_unwind(AssertUnwindSafe(|| index.find(key))).is_err());
Ok(())
}
#[test]
fn removal_distinguishes_membership_and_bucket_lifetimes() -> Result<(), &'static str> {
let mut index = SecondaryIndex::try_new(2).map_err(|_| "index storage unavailable")?;
let first_key = Key(1);
let second_key = Key(2);
let first_slot = StableSlot::new(10);
let retained_slot = StableSlot::new(11);
let relocated_slot = StableSlot::new(12);
for (secondary_key, slot, expected) in [
(
first_key,
first_slot,
SecondaryIndexInsertOutcome::CreatedBucket {
secondary_key: first_key,
slot: first_slot,
},
),
(
first_key,
retained_slot,
SecondaryIndexInsertOutcome::AddedToBucket {
secondary_key: first_key,
slot: retained_slot,
},
),
(
second_key,
relocated_slot,
SecondaryIndexInsertOutcome::CreatedBucket {
secondary_key: second_key,
slot: relocated_slot,
},
),
] {
assert_eq!(
index
.try_prepare_insert(secondary_key, slot)
.map_err(|_| "preparation failed")?
.commit(),
expected
);
}
assert_eq!(index.len(), 2);
assert!(!index.is_empty());
assert_eq!(
index.remove(first_key, StableSlot::new(99)),
Ok(SecondaryIndexRemoveOutcome::SlotAbsent {
secondary_key: first_key,
slot: StableSlot::new(99),
})
);
{
let prepared = match index
.try_prepare_remove(first_key, first_slot)
.map_err(|_| "removal preparation failed")?
{
SecondaryIndexPrepareRemoveOutcome::Prepared(prepared) => prepared,
SecondaryIndexPrepareRemoveOutcome::BucketAbsent { .. }
| SecondaryIndexPrepareRemoveOutcome::SlotAbsent { .. } => {
return Err("present membership was absent");
}
};
assert_eq!(
(prepared.secondary_key(), prepared.slot()),
(first_key, first_slot)
);
}
assert_eq!(slots(&index, first_key)?, [first_slot, retained_slot]);
let SecondaryIndexPrepareRemoveOutcome::Prepared(prepared) = index
.try_prepare_remove(first_key, first_slot)
.map_err(|_| "second removal preparation failed")?
else {
return Err("present membership was absent after abandoned preparation");
};
assert_eq!(
prepared.commit(),
super::SecondaryIndexCommitRemoveOutcome::RemovedFromBucket {
secondary_key: first_key,
slot: first_slot,
remaining_slots: 1,
}
);
assert_eq!(
index.remove(first_key, retained_slot),
Ok(SecondaryIndexRemoveOutcome::RemovedBucket {
secondary_key: first_key,
slot: retained_slot,
})
);
assert_eq!(index.len(), 1);
let lookup = index.find(second_key);
let slots = lookup.slots().ok_or("relocated bucket was absent")?;
assert_eq!(slots.slots().collect::<Vec<_>>(), [relocated_slot]);
assert_eq!(
index.remove(first_key, first_slot),
Ok(SecondaryIndexRemoveOutcome::BucketAbsent {
secondary_key: first_key,
slot: first_slot,
})
);
Ok(())
}
#[test]
fn prepared_moves_are_atomic_and_report_both_bucket_lifetimes() -> Result<(), &'static str> {
let mut index = SecondaryIndex::try_new(3).map_err(|_| "index storage unavailable")?;
let source = Key(1);
let target = Key(2);
let first = StableSlot::new(10);
let last = StableSlot::new(11);
let target_slot = StableSlot::new(12);
for (secondary_key, slot) in [(source, first), (source, last), (target, target_slot)] {
insert_membership(&mut index, secondary_key, slot)?;
}
assert_eq!(
index
.try_prepare_move(source, source, first)
.map_err(|_| "unchanged move preparation failed")?
.commit(),
SecondaryIndexMoveOutcome::Unchanged {
secondary_key: source,
slot: first,
}
);
drop(
index
.try_prepare_move(source, target, first)
.map_err(|_| "abandoned move preparation failed")?,
);
assert_eq!(slots(&index, source)?, [first, last]);
assert_eq!(slots(&index, target)?, [target_slot]);
assert_eq!(
index
.try_prepare_move(source, target, first)
.map_err(|_| "retained-source move preparation failed")?
.commit(),
SecondaryIndexMoveOutcome::MovedBetweenExistingBuckets {
source,
target,
slot: first,
}
);
assert_eq!(slots(&index, source)?, [last]);
assert_eq!(
index
.try_prepare_move(source, target, last)
.map_err(|_| "removed-source move preparation failed")?
.commit(),
SecondaryIndexMoveOutcome::MovedAndRemovedSourceBucket {
source,
target,
slot: last,
}
);
assert!(index.find(source).slots().is_none());
assert_eq!(slots(&index, target)?, [first, last, target_slot]);
Ok(())
}
#[test]
fn moves_create_or_rename_buckets_without_exceeding_capacity() -> Result<(), &'static str> {
let source = Key(1);
let target = Key(2);
let first = StableSlot::new(10);
let retained = StableSlot::new(11);
let mut index = SecondaryIndex::try_new(2).map_err(|_| "index storage unavailable")?;
for slot in [first, retained] {
insert_membership(&mut index, source, slot)?;
}
assert_eq!(
index
.try_prepare_move(source, target, first)
.map_err(|_| "new-target move preparation failed")?
.commit(),
SecondaryIndexMoveOutcome::MovedAndCreatedTargetBucket {
source,
target,
slot: first,
}
);
assert_eq!(slots(&index, source)?, [retained]);
assert_eq!(slots(&index, target)?, [first]);
let mut full = SecondaryIndex::try_new(1).map_err(|_| "full index storage unavailable")?;
insert_membership(&mut full, source, first)?;
assert_eq!(
full.try_prepare_move(source, target, first)
.map_err(|_| "rename preparation failed")?
.commit(),
SecondaryIndexMoveOutcome::RenamedBucket {
source,
target,
slot: first,
}
);
assert_eq!(full.len(), 1);
assert!(full.find(source).slots().is_none());
assert_eq!(slots(&full, target)?, [first]);
Ok(())
}
#[test]
fn rejected_moves_preserve_their_exact_membership_facts() -> Result<(), &'static str> {
let source = Key(1);
let target = Key(2);
let slot = StableSlot::new(10);
let mut index = SecondaryIndex::try_new(2).map_err(|_| "index storage unavailable")?;
insert_membership(&mut index, source, slot)?;
insert_membership(&mut index, target, slot)?;
assert!(matches!(
index.try_prepare_move(Key(99), target, slot),
Err(SecondaryIndexMoveError::SourceBucketAbsent {
source: Key(99),
..
})
));
assert!(matches!(
index.try_prepare_move(source, target, StableSlot::new(99)),
Err(SecondaryIndexMoveError::SourceSlotAbsent { .. })
));
assert!(matches!(
index.try_prepare_move(source, target, slot),
Err(SecondaryIndexMoveError::TargetSlotAlreadyPresent { .. })
));
assert_eq!(slots(&index, source)?, [slot]);
assert_eq!(slots(&index, target)?, [slot]);
Ok(())
}
fn slots(index: &SecondaryIndex<Key>, secondary_key: Key) -> Result<Vec<StableSlot>, &'static str> {
let lookup = index.find(secondary_key);
let slots = lookup.slots().ok_or("secondary key was absent")?;
Ok(slots.slots().collect())
}
pub(super) fn insert_membership(
index: &mut SecondaryIndex<Key>,
secondary_key: Key,
slot: StableSlot,
) -> Result<(), &'static str> {
let outcome = index
.try_prepare_insert(secondary_key, slot)
.map_err(|_| "insert preparation failed")?
.commit();
match outcome {
SecondaryIndexInsertOutcome::CreatedBucket {
secondary_key: actual_key,
slot: actual_slot,
}
| SecondaryIndexInsertOutcome::AddedToBucket {
secondary_key: actual_key,
slot: actual_slot,
} if actual_key == secondary_key && actual_slot == slot => Ok(()),
SecondaryIndexInsertOutcome::CreatedBucket { .. }
| SecondaryIndexInsertOutcome::AddedToBucket { .. } => {
Err("insert outcome did not retain its request")
}
}
}
#[test]
fn commit_refusals_preserve_bucket_row_and_occupant() -> Result<(), &'static str> {
use super::SecondaryIndexInconsistency;
use crate::storage::warp_table::dense_key_index::{
CommitInconsistency, DenseKeyIndex, PrepareInsertOutcome,
};
let index = DenseKeyIndex::try_new(2).map_err(|_| "dense index unavailable")?;
let PrepareInsertOutcome::Vacant(vacancy) = index
.prepare_insert(Key(17), &[])
.map_err(|_| "vacancy unavailable")?
else {
return Err("empty index reported a present key");
};
let bucket = vacancy.bucket();
for (dense, expected) in [
(
CommitInconsistency::RowUnrepresentable { vacancy, row: 13 },
SecondaryIndexInconsistency::InsertRowUnrepresentable { bucket, row: 13 },
),
(
CommitInconsistency::RowReserved { vacancy, row: 17 },
SecondaryIndexInconsistency::InsertRowReserved { bucket, row: 17 },
),
(
CommitInconsistency::VacancyUnavailable { vacancy, row: 19 },
SecondaryIndexInconsistency::InsertVacancyUnavailable { bucket, row: 19 },
),
(
CommitInconsistency::VacancyOccupied {
vacancy,
row: 23,
occupying_row: 29,
},
SecondaryIndexInconsistency::InsertVacancyOccupied {
bucket,
row: 23,
occupying_row: 29,
},
),
] {
assert_eq!(SecondaryIndexInconsistency::from(dense), expected);
}
Ok(())
}
#[test]
fn lookup_refusals_preserve_every_dense_index_fact() {
use super::SecondaryIndexInconsistency;
use crate::storage::warp_table::dense_key_index::IndexInconsistency;
for (dense, expected) in [
(
IndexInconsistency::BucketUnavailable { bucket: 3 },
SecondaryIndexInconsistency::BucketUnavailable { bucket: 3 },
),
(
IndexInconsistency::StoredRowUnrepresentable { stored_row: 7 },
SecondaryIndexInconsistency::StoredRowUnrepresentable { stored_row: 7 },
),
(
IndexInconsistency::KeyUnavailable { row: 11 },
SecondaryIndexInconsistency::KeyUnavailable { row: 11 },
),
(
IndexInconsistency::StoredRowMismatch {
expected: 13,
actual: 17,
},
SecondaryIndexInconsistency::StoredRowMismatch {
expected: 13,
actual: 17,
},
),
(
IndexInconsistency::ProbeLimitReached,
SecondaryIndexInconsistency::ProbeLimitReached,
),
] {
assert_eq!(SecondaryIndexInconsistency::from(dense), expected);
}
}
pub(super) fn index_state(index: &SecondaryIndex<Key>) -> (Vec<Key>, Vec<Vec<StableSlot>>) {
(
index.secondary_keys.clone(),
index
.slot_sets
.iter()
.map(|set| set.slots().collect())
.collect(),
)
}
#[test]
fn damaged_membership_storage_refuses_mutation_without_partial_changes() -> Result<(), &'static str>
{
use super::{SecondaryIndexInconsistency, SecondaryIndexRemoveError};
use crate::storage::warp_table::secondary_index::SlotSet;
let key = Key(17);
let target = Key(29);
let slot = StableSlot::new(13);
for remove_storage in [true, false] {
let mut index = SecondaryIndex::try_new(3).map_err(|_| "index unavailable")?;
insert_membership(&mut index, key, slot)?;
let reason = if remove_storage {
index.slot_sets.clear();
SecondaryIndexInconsistency::KeySlotSetLengthMismatch {
secondary_keys: 1,
slot_sets: 0,
}
} else {
index.slot_sets = alloc::vec![SlotSet::empty()];
SecondaryIndexInconsistency::EmptySlotSet { row: 0 }
};
let before = index_state(&index);
if remove_storage {
assert_eq!(
index.try_prepare_insert(key, slot).err(),
Some(SecondaryIndexInsertError::Inconsistent {
secondary_key: key,
slot,
reason
})
);
assert_eq!(index_state(&index), before);
}
assert_eq!(
index.try_prepare_remove(key, slot).err(),
Some(SecondaryIndexRemoveError::Inconsistent {
secondary_key: key,
slot,
reason
})
);
assert_eq!(index_state(&index), before);
let Some(SecondaryIndexMoveError::Inconsistent {
source: actual_source,
target: actual_target,
slot: actual_slot,
reason: actual_reason,
}) = index.try_prepare_move(key, target, slot).err()
else {
return Err("damaged source admitted a move");
};
assert_eq!(
(actual_source, actual_target, actual_slot, actual_reason),
(key, target, slot, reason)
);
assert_eq!(index_state(&index), before);
}
Ok(())
}
#[test]
fn dangling_dense_keys_reject_each_mutation_and_lookup() -> Result<(), &'static str> {
use super::{SecondaryIndexInconsistency, SecondaryIndexRemoveError};
let mut index = SecondaryIndex::try_new(3).map_err(|_| "index unavailable")?;
let first = Key(3);
let dangling = Key(19);
let target = Key(29);
let slot = StableSlot::new(7);
insert_membership(&mut index, first, StableSlot::new(5))?;
insert_membership(&mut index, dangling, slot)?;
index.secondary_keys.truncate(1);
index.slot_sets.truncate(1);
let reason = SecondaryIndexInconsistency::KeyUnavailable { row: 1 };
let before = index_state(&index);
assert_eq!(
index.try_prepare_insert(dangling, slot).err(),
Some(SecondaryIndexInsertError::Inconsistent {
secondary_key: dangling,
slot,
reason
})
);
assert_eq!(
index.try_prepare_remove(dangling, slot).err(),
Some(SecondaryIndexRemoveError::Inconsistent {
secondary_key: dangling,
slot,
reason
})
);
let Some(SecondaryIndexMoveError::Inconsistent {
source,
target: actual_target,
slot: actual_slot,
reason: actual_reason,
}) = index.try_prepare_move(dangling, target, slot).err()
else {
return Err("dangling source admitted a move");
};
assert_eq!(
(source, actual_target, actual_slot, actual_reason),
(dangling, target, slot, reason)
);
assert!(catch_unwind(AssertUnwindSafe(|| index.find(dangling))).is_err());
assert_eq!(index_state(&index), before);
Ok(())
}
#[test]
fn full_split_refusal_and_abandoned_moves_preserve_all_buckets() -> Result<(), &'static str> {
let source = Key(7);
let target = Key(13);
let first = StableSlot::new(17);
let second = StableSlot::new(19);
let mut full = SecondaryIndex::try_new(1).map_err(|_| "index unavailable")?;
for slot in [first, second] {
insert_membership(&mut full, source, slot)?;
}
let before = index_state(&full);
let Some(SecondaryIndexMoveError::Full {
source: actual_source,
target: actual_target,
slot,
maximum_distinct_keys,
}) = full.try_prepare_move(source, target, first).err()
else {
return Err("full split did not return capacity refusal");
};
assert_eq!(
(actual_source, actual_target, slot, maximum_distinct_keys),
(source, target, first, 1)
);
assert_eq!(index_state(&full), before);
for source_count in [1, 2] {
for target_exists in [true, false] {
let mut index = SecondaryIndex::try_new(3).map_err(|_| "index unavailable")?;
insert_membership(&mut index, source, first)?;
if source_count == 2 {
insert_membership(&mut index, source, second)?;
}
if target_exists {
insert_membership(&mut index, target, StableSlot::new(23))?;
}
let before = index_state(&index);
drop(
index
.try_prepare_move(source, target, first)
.map_err(|_| "move unavailable")?,
);
assert_eq!(index_state(&index), before);
for (key, membership) in before.0.iter().copied().zip(&before.1) {
assert_eq!(&slots(&index, key)?, membership);
}
}
}
Ok(())
}
#[test]
fn public_removal_reports_retained_membership_and_relocated_keys() -> Result<(), &'static str> {
let mut index = SecondaryIndex::try_new(3).map_err(|_| "index unavailable")?;
let source = Key(7);
let retained = Key(19);
let first = StableSlot::new(13);
let second = StableSlot::new(17);
insert_membership(&mut index, source, first)?;
insert_membership(&mut index, source, second)?;
insert_membership(&mut index, retained, StableSlot::new(23))?;
assert_eq!(
index.remove(source, first),
Ok(SecondaryIndexRemoveOutcome::RemovedFromBucket {
secondary_key: source,
slot: first,
remaining_slots: 1
})
);
assert_eq!(slots(&index, source)?, [second]);
assert_eq!(
index.remove(source, second),
Ok(SecondaryIndexRemoveOutcome::RemovedBucket {
secondary_key: source,
slot: second
})
);
assert_eq!(slots(&index, retained)?, [StableSlot::new(23)]);
assert_eq!(index.len(), 1);
Ok(())
}
#[test]
fn creation_refuses_unrepresentable_key_storage() {
assert!(matches!(
SecondaryIndex::<Key>::try_new(usize::MAX),
Err(super::SecondaryIndexCreationError::SecondaryKeyStorageUnavailable { .. })
));
}