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)]
struct Key(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());
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);
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.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())
}
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")
}
}
}