use super::{
StableSlot, StableSlotInsertError, StableSlotRemoveOutcome, StableSlotResolveOutcome,
StableSlotRowRelocation, StableSlots, StableSlotsInconsistency,
};
use crate::storage::warp_table::secondary_index::SlotSet;
#[test]
fn stable_slots_follow_dense_relocation_and_reuse() -> Result<(), &'static str> {
let mut slots = StableSlots::try_new(3).map_err(|_| "slot storage unavailable")?;
let first = slots
.try_prepare_insert()
.map_err(|_| "first slot unavailable")?
.commit();
let second = slots
.try_prepare_insert()
.map_err(|_| "second slot unavailable")?
.commit();
let third = slots
.try_prepare_insert()
.map_err(|_| "third slot unavailable")?
.commit();
assert_eq!(
(first, second, third),
(StableSlot::new(0), StableSlot::new(1), StableSlot::new(2))
);
{
let prepared = slots
.try_prepare_remove(1)
.map_err(|_| "second slot removal unavailable")?;
assert_eq!(prepared.slot(), second);
}
assert_eq!(
slots.resolve(second),
Ok(StableSlotResolveOutcome::Resolved {
slot: second,
dense_row: 1,
})
);
assert_eq!(slots.slot(1), Ok(second));
assert_eq!(
slots
.try_prepare_remove(1)
.map_err(|_| "second slot removal unavailable")?
.commit(),
StableSlotRemoveOutcome::Removed {
slot: second,
relocation: StableSlotRowRelocation::Relocated {
slot: third,
from: 2,
to: 1,
},
}
);
assert_eq!(
slots.resolve(third),
Ok(StableSlotResolveOutcome::Resolved {
slot: third,
dense_row: 1,
})
);
assert_eq!(slots.slot(1), Ok(third));
assert_eq!(
slots.resolve_slots(&SlotSet::one(second)).next(),
Some(Err(StableSlotsInconsistency::SlotVacant { slot: second }))
);
let retained = SlotSet::one(first).union(&SlotSet::one(third));
let mut retained = slots.resolve_slots(&retained);
assert_eq!(retained.size_hint(), (2, Some(2)));
#[cfg(target_pointer_width = "64")]
assert_eq!(retained.len(), 2);
assert_eq!(
retained.next_back(),
Some(Ok(StableSlotResolveOutcome::Resolved {
slot: third,
dense_row: 1,
}))
);
assert_eq!(
retained.next(),
Some(Ok(StableSlotResolveOutcome::Resolved {
slot: first,
dense_row: 0,
}))
);
assert_eq!(retained.size_hint(), (0, Some(0)));
#[cfg(target_pointer_width = "64")]
assert_eq!(retained.len(), 0);
assert_eq!(retained.next(), None);
assert_eq!(retained.next_back(), None);
let reused = slots
.try_prepare_insert()
.map_err(|_| "reused slot unavailable")?
.commit();
assert_eq!(reused, second);
assert_eq!(
slots.resolve(reused),
Ok(StableSlotResolveOutcome::Resolved {
slot: reused,
dense_row: 2,
})
);
assert_eq!(
slots.try_prepare_insert().map(|prepared| prepared.slot()),
Err(StableSlotInsertError::Full { maximum_rows: 3 })
);
assert_eq!(
slots.remove(2),
Ok(StableSlotRemoveOutcome::Removed {
slot: reused,
relocation: StableSlotRowRelocation::Stable,
})
);
assert_eq!(
slots.resolve(reused),
Err(StableSlotsInconsistency::SlotVacant { slot: reused })
);
Ok(())
}
#[test]
fn abandoned_preparation_publishes_nothing() -> Result<(), &'static str> {
let mut slots = StableSlots::try_new(1).map_err(|_| "slot storage unavailable")?;
let reserved = {
let prepared = slots
.try_prepare_insert()
.map_err(|_| "prepared slot unavailable")?;
prepared.slot()
};
let committed = slots
.try_prepare_insert()
.map_err(|_| "slot changed after abandonment")?
.commit();
assert_eq!(committed, reserved);
assert_eq!(
slots.resolve(committed),
Ok(StableSlotResolveOutcome::Resolved {
slot: committed,
dense_row: 0,
})
);
Ok(())
}
#[derive(Debug, Eq, PartialEq)]
struct StoredState {
rows: alloc::vec::Vec<StableSlot>,
locations: alloc::vec::Vec<Result<u32, Option<StableSlot>>>,
first_free: Option<StableSlot>,
}
fn stored_state(slots: &StableSlots) -> StoredState {
StoredState {
rows: slots.row_to_slot.clone(),
locations: slots
.slot_locations
.iter()
.map(|location| match location {
super::SlotLocation::Occupied(row) => Ok(*row),
super::SlotLocation::Free(next) => Err(*next),
})
.collect(),
first_free: slots.first_free,
}
}
#[test]
fn invalid_free_heads_are_rejected_without_consuming_storage() -> Result<(), &'static str> {
let mut slots = StableSlots::try_new(3).map_err(|_| "slot storage unavailable")?;
let occupied = slots
.try_prepare_insert()
.map_err(|_| "slot unavailable")?
.commit();
for (head, reason) in [
(
StableSlot::new(7),
StableSlotsInconsistency::SlotUnavailable {
slot: StableSlot::new(7),
},
),
(
occupied,
StableSlotsInconsistency::SlotOccupied {
slot: occupied,
row: 0,
},
),
] {
slots.first_free = Some(head);
let before = stored_state(&slots);
assert_eq!(
slots.try_prepare_insert().err(),
Some(StableSlotInsertError::Inconsistent { reason })
);
assert_eq!(stored_state(&slots), before);
}
Ok(())
}
#[test]
fn invalid_dense_links_preserve_exact_facts_and_storage() -> Result<(), &'static str> {
let first = StableSlot::new(0);
let second = StableSlot::new(1);
let missing = StableSlot::new(9);
let mut slots = StableSlots::try_new(2).map_err(|_| "slot storage unavailable")?;
assert_eq!(
slots.remove(0),
Err(StableSlotsInconsistency::RowUnavailable { row: 0 })
);
assert_eq!(
slots.slot(3),
Err(StableSlotsInconsistency::RowUnavailable { row: 3 })
);
assert_eq!(
slots.resolve(missing),
Err(StableSlotsInconsistency::SlotUnavailable { slot: missing })
);
for expected in [first, second] {
assert_eq!(
slots
.try_prepare_insert()
.map_err(|_| "slot unavailable")?
.commit(),
expected
);
}
assert_eq!(
slots.remove(2),
Err(StableSlotsInconsistency::RowUnavailable { row: 2 })
);
for (rows, locations, reason) in [
(
alloc::vec![missing, second],
alloc::vec![
super::SlotLocation::Occupied(0),
super::SlotLocation::Occupied(1)
],
StableSlotsInconsistency::SlotUnavailable { slot: missing },
),
(
alloc::vec![first, second],
alloc::vec![
super::SlotLocation::Free(None),
super::SlotLocation::Occupied(1)
],
StableSlotsInconsistency::SlotVacant { slot: first },
),
(
alloc::vec![first, second],
alloc::vec![
super::SlotLocation::Occupied(7),
super::SlotLocation::Occupied(1)
],
StableSlotsInconsistency::SlotRowMismatch {
slot: first,
expected: 0,
actual: 7,
},
),
(
alloc::vec![first, first],
alloc::vec![
super::SlotLocation::Occupied(0),
super::SlotLocation::Occupied(1)
],
StableSlotsInconsistency::DuplicateSlot { slot: first },
),
(
alloc::vec![first, second],
alloc::vec![
super::SlotLocation::Occupied(0),
super::SlotLocation::Occupied(9)
],
StableSlotsInconsistency::SlotRowMismatch {
slot: second,
expected: 1,
actual: 9,
},
),
] {
slots.row_to_slot = rows;
slots.slot_locations = locations;
let before = stored_state(&slots);
assert_eq!(slots.try_prepare_remove(0).err(), Some(reason));
assert_eq!(stored_state(&slots), before);
}
Ok(())
}
#[test]
fn slot_capacity_and_row_representation_are_checked() -> Result<(), &'static str> {
let mut empty = StableSlots::try_new(0).map_err(|_| "zero capacity unavailable")?;
assert_eq!(
empty.try_prepare_insert().err(),
Some(StableSlotInsertError::Full { maximum_rows: 0 })
);
if let Some(too_large) = usize::try_from(u32::MAX)
.ok()
.and_then(|maximum| maximum.checked_add(1))
{
assert!(
matches!(StableSlots::try_new(too_large), Err(super::StableSlotsCreationError::CapacityUnrepresentable { maximum_rows, .. }) if maximum_rows == too_large)
);
assert_eq!(
empty.validate_location(StableSlot::new(0), too_large),
Err(StableSlotsInconsistency::RowUnrepresentable { row: too_large })
);
}
Ok(())
}
#[test]
fn every_small_removal_order_preserves_identity_and_reuses_the_free_chain()
-> Result<(), &'static str> {
for first_removed in 0..4 {
for second_removed in 0..3 {
for third_removed in 0..2 {
let mut slots = StableSlots::try_new(4).map_err(|_| "slot storage unavailable")?;
let mut model = alloc::vec::Vec::new();
for value in 0..4 {
let slot = slots
.try_prepare_insert()
.map_err(|_| "slot unavailable")?
.commit();
assert_eq!(slot, StableSlot::new(value));
model.push(slot);
}
let mut freed = alloc::vec::Vec::new();
for row in [first_removed, second_removed, third_removed, 0] {
let removed = *model.get(row).ok_or("model row unavailable")?;
let last_row = model.len().checked_sub(1).ok_or("model empty")?;
let last = *model.last().ok_or("model last row unavailable")?;
let relocation = if row == last_row {
StableSlotRowRelocation::Stable
} else {
StableSlotRowRelocation::Relocated {
slot: last,
from: last_row,
to: row,
}
};
let before = stored_state(&slots);
{
let prepared = slots
.try_prepare_remove(row)
.map_err(|_| "removal unavailable")?;
assert_eq!(prepared.slot(), removed);
}
assert_eq!(stored_state(&slots), before);
assert_eq!(
slots.remove(row),
Ok(StableSlotRemoveOutcome::Removed {
slot: removed,
relocation
})
);
assert_eq!(model.swap_remove(row), removed);
freed.push(removed);
for (dense_row, slot) in model.iter().copied().enumerate() {
assert_eq!(slots.slot(dense_row), Ok(slot));
assert_eq!(
slots.resolve(slot),
Ok(StableSlotResolveOutcome::Resolved { slot, dense_row })
);
}
for slot in &freed {
assert_eq!(
slots.resolve(*slot),
Err(StableSlotsInconsistency::SlotVacant { slot: *slot })
);
}
}
for (dense_row, slot) in freed.into_iter().rev().enumerate() {
let before = stored_state(&slots);
{
let prepared = slots
.try_prepare_insert()
.map_err(|_| "reuse preparation unavailable")?;
assert_eq!(prepared.slot(), slot);
}
assert_eq!(stored_state(&slots), before);
assert_eq!(
slots
.try_prepare_insert()
.map_err(|_| "reuse unavailable")?
.commit(),
slot
);
assert_eq!(
slots.resolve(slot),
Ok(StableSlotResolveOutcome::Resolved { slot, dense_row })
);
}
assert_eq!(slots.first_free, None);
assert_eq!(
slots.try_prepare_insert().err(),
Some(StableSlotInsertError::Full { maximum_rows: 4 })
);
}
}
}
Ok(())
}
#[test]
fn representation_boundaries_preserve_slot_and_row_refusals() -> Result<(), alloc::string::String> {
use super::inconsistency::{new_slot, row, slot_index, stored_row};
for value in [0, u32::from(u16::MAX), u32::from(u16::MAX) + 1, u32::MAX] {
let slot = StableSlot::new(value);
assert_eq!(slot_index::<u64>(slot), Ok(u64::from(value)));
assert_eq!(stored_row::<u64>(slot, value), Ok(u64::from(value)));
match u16::try_from(value) {
Ok(expected) => {
assert_eq!(slot_index::<u16>(slot), Ok(expected));
assert_eq!(stored_row::<u16>(slot, value), Ok(expected));
}
Err(_) => {
assert_eq!(
slot_index::<u16>(slot),
Err(StableSlotsInconsistency::SlotUnrepresentable { slot })
);
assert_eq!(
stored_row::<u16>(slot, value),
Err(StableSlotsInconsistency::StoredRowUnrepresentable {
slot,
stored_row: value
})
);
}
}
}
assert_eq!(row(0), Ok(0));
assert_eq!(new_slot(0), Ok(StableSlot::new(0)));
if let Some(outside) = usize::try_from(u32::MAX)
.ok()
.and_then(|maximum| maximum.checked_add(1))
{
let reason = StableSlotsInconsistency::RowUnrepresentable { row: outside };
assert_eq!(row(outside), Err(reason));
assert_eq!(
StableSlotInsertError::from(reason),
StableSlotInsertError::Inconsistent { reason }
);
assert_eq!(
new_slot(outside),
Err(StableSlotsInconsistency::NewSlotUnrepresentable { slot: outside })
);
}
Ok(())
}