use super::{
UniqueIndex, UniqueIndexCreationError, UniqueIndexInconsistency, UniqueIndexInsertError,
UniqueIndexInsertOutcome, UniqueIndexLookupError, UniqueIndexLookupOutcome,
UniqueIndexRemoveError, UniqueIndexRemoveOutcome, UniqueIndexReplaceError,
UniqueIndexReplaceOutcome,
};
use crate::storage::warp_table::IndexKey;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Key(u64);
impl IndexKey for Key {
fn index_word(self) -> u64 {
self.0
}
}
fn insert(index: &mut UniqueIndex<Key>, key: Key) -> Result<(), &'static str> {
let prepared = index
.try_prepare_insert(key)
.map_err(|_| "unique insertion was not prepared")?;
let UniqueIndexInsertOutcome::Inserted {
key: inserted,
row: _,
} = prepared.commit();
if inserted != key {
return Err("unique insertion changed its key");
}
Ok(())
}
#[test]
fn unique_index_reserves_bounded_storage() -> Result<(), &'static str> {
let index = UniqueIndex::<Key>::try_new(3).map_err(|_| "unique index unavailable")?;
assert_eq!(index.maximum_keys, 3);
assert!(index.keys.capacity() >= 3);
assert!(matches!(
UniqueIndex::<Key>::try_new(usize::MAX),
Err(UniqueIndexCreationError::CapacityOverflow { maximum_keys })
if maximum_keys == usize::MAX
));
assert!(matches!(
UniqueIndex::<Key>::try_new(usize::MAX / 4),
Err(UniqueIndexCreationError::IndexStorageUnavailable { .. })
));
Ok(())
}
#[test]
fn unique_index_insertions_are_atomic_bounded_and_unique() -> Result<(), &'static str> {
let mut index = UniqueIndex::try_new(1).map_err(|_| "unique index unavailable")?;
{
let _abandoned = index
.try_prepare_insert(Key(1))
.map_err(|_| "unique insertion was not prepared")?;
}
assert_eq!(
index.find(Key(1)),
Ok(UniqueIndexLookupOutcome::Absent { key: Key(1) })
);
insert(&mut index, Key(1))?;
assert_eq!(
index.find(Key(1)),
Ok(UniqueIndexLookupOutcome::Present {
key: Key(1),
row: 0,
})
);
assert_eq!(
index.try_prepare_insert(Key(1)).err(),
Some(UniqueIndexInsertError::AlreadyPresent {
key: Key(1),
existing_row: 0,
})
);
assert_eq!(
index.try_prepare_insert(Key(2)).err(),
Some(UniqueIndexInsertError::Full {
key: Key(2),
maximum_keys: 1,
})
);
Ok(())
}
#[test]
fn unique_index_replacement_preserves_dense_rows() -> Result<(), &'static str> {
let mut index = UniqueIndex::try_new(3).map_err(|_| "unique index unavailable")?;
insert(&mut index, Key(1))?;
insert(&mut index, Key(2))?;
assert_eq!(
index.try_prepare_replace(Key(9), Key(3), 0).err(),
Some(UniqueIndexReplaceError::SourceAbsent {
source: Key(9),
target: Key(3),
})
);
assert_eq!(
index.try_prepare_replace(Key(1), Key(2), 0).err(),
Some(UniqueIndexReplaceError::TargetPresent {
source: Key(1),
target: Key(2),
existing_row: 1,
})
);
assert_eq!(
index.try_prepare_replace(Key(1), Key(1), 1).err(),
Some(UniqueIndexReplaceError::Inconsistent {
source: Key(1),
target: Key(1),
reason: UniqueIndexInconsistency::ExpectedRowMismatch {
expected: 1,
actual: 0,
},
})
);
assert_eq!(
index.try_prepare_replace(Key(1), Key(3), 1).err(),
Some(UniqueIndexReplaceError::Inconsistent {
source: Key(1),
target: Key(3),
reason: UniqueIndexInconsistency::ExpectedRowMismatch {
expected: 1,
actual: 0,
},
})
);
let unchanged = index
.try_prepare_replace(Key(1), Key(1), 0)
.map_err(|_| "unchanged replacement was not prepared")?;
assert_eq!(
unchanged.commit(),
UniqueIndexReplaceOutcome::Unchanged {
key: Key(1),
row: 0,
}
);
let replacement = index
.try_prepare_replace(Key(1), Key(3), 0)
.map_err(|_| "replacement was not prepared")?;
assert_eq!(
replacement.commit(),
UniqueIndexReplaceOutcome::Replaced {
source: Key(1),
target: Key(3),
row: 0,
}
);
assert_eq!(
index.find(Key(1)),
Ok(UniqueIndexLookupOutcome::Absent { key: Key(1) })
);
assert_eq!(
index.find(Key(3)),
Ok(UniqueIndexLookupOutcome::Present {
key: Key(3),
row: 0,
})
);
Ok(())
}
#[test]
fn unique_index_removal_follows_dense_relocation() -> Result<(), &'static str> {
let mut index = UniqueIndex::try_new(3).map_err(|_| "unique index unavailable")?;
assert_eq!(
index.try_prepare_remove(Key(1)).err(),
Some(UniqueIndexRemoveError::Absent { key: Key(1) })
);
insert(&mut index, Key(1))?;
insert(&mut index, Key(2))?;
insert(&mut index, Key(3))?;
assert_eq!(
index.try_prepare_remove(Key(9)).err(),
Some(UniqueIndexRemoveError::Absent { key: Key(9) })
);
let removal = index
.try_prepare_remove(Key(2))
.map_err(|_| "unique removal was not prepared")?;
assert_eq!(
removal.commit(),
UniqueIndexRemoveOutcome::Removed {
key: Key(2),
row: 1,
}
);
assert_eq!(
index.find(Key(3)),
Ok(UniqueIndexLookupOutcome::Present {
key: Key(3),
row: 1,
})
);
Ok(())
}
#[test]
fn unique_index_preserves_exact_inconsistency_facts() -> Result<(), &'static str> {
let mut index = UniqueIndex::try_new(2).map_err(|_| "unique index unavailable")?;
insert(&mut index, Key(1))?;
insert(&mut index, Key(2))?;
let _ = index.keys.pop();
let reason = UniqueIndexInconsistency::KeyUnavailable { row: 1 };
assert_eq!(
index.find(Key(2)),
Err(UniqueIndexLookupError::Inconsistent {
key: Key(2),
reason,
})
);
assert_eq!(
index.try_prepare_insert(Key(2)).err(),
Some(UniqueIndexInsertError::Inconsistent {
key: Key(2),
reason,
})
);
assert_eq!(
index.try_prepare_remove(Key(1)).err(),
Some(UniqueIndexRemoveError::Inconsistent {
key: Key(1),
reason,
})
);
assert_eq!(
index.try_prepare_replace(Key(2), Key(3), 1).err(),
Some(UniqueIndexReplaceError::Inconsistent {
source: Key(2),
target: Key(3),
reason,
})
);
Ok(())
}
#[test]
fn unique_index_inconsistency_maps_every_dense_lookup_fact() {
use super::super::dense_key_index::IndexInconsistency;
for (dense, unique) in [
(
IndexInconsistency::BucketUnavailable { bucket: 3 },
UniqueIndexInconsistency::BucketUnavailable { bucket: 3 },
),
(
IndexInconsistency::StoredRowUnrepresentable { stored_row: 7 },
UniqueIndexInconsistency::StoredRowUnrepresentable { stored_row: 7 },
),
(
IndexInconsistency::KeyUnavailable { row: 11 },
UniqueIndexInconsistency::KeyUnavailable { row: 11 },
),
(
IndexInconsistency::StoredRowMismatch {
expected: 13,
actual: 17,
},
UniqueIndexInconsistency::StoredRowMismatch {
expected: 13,
actual: 17,
},
),
(
IndexInconsistency::ProbeLimitReached,
UniqueIndexInconsistency::ProbeLimitReached,
),
] {
assert_eq!(UniqueIndexInconsistency::from(dense), unique);
}
}
#[test]
fn commit_refusals_preserve_bucket_row_and_occupant() -> Result<(), &'static str> {
use super::UniqueIndexInconsistency;
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 },
UniqueIndexInconsistency::InsertRowUnrepresentable { bucket, row: 13 },
),
(
CommitInconsistency::RowReserved { vacancy, row: 17 },
UniqueIndexInconsistency::InsertRowReserved { bucket, row: 17 },
),
(
CommitInconsistency::VacancyUnavailable { vacancy, row: 19 },
UniqueIndexInconsistency::InsertVacancyUnavailable { bucket, row: 19 },
),
(
CommitInconsistency::VacancyOccupied {
vacancy,
row: 23,
occupying_row: 29,
},
UniqueIndexInconsistency::InsertVacancyOccupied {
bucket,
row: 23,
occupying_row: 29,
},
),
] {
assert_eq!(UniqueIndexInconsistency::from(dense), expected);
}
Ok(())
}
#[test]
fn unique_index_transactions_match_dense_rows_after_every_small_edit() -> Result<(), &'static str> {
for first in 0_u64..3 {
for second in 0_u64..3 {
if first == second {
continue;
}
for removed_row in 0..3 {
let mut index = UniqueIndex::try_new(3).map_err(|_| "unique index unavailable")?;
let mut model = alloc::vec::Vec::new();
for key in [Key(first), Key(second)] {
insert(&mut index, key)?;
model.push(key);
}
let third = (0_u64..3)
.find(|value| *value != first && *value != second)
.ok_or("third key unavailable")?;
insert(&mut index, Key(third))?;
model.push(Key(third));
for (row, source) in model.iter().copied().enumerate() {
let target = Key(17);
{
let _prepared = index
.try_prepare_replace(source, target, row)
.map_err(|_| "replacement unavailable")?;
}
assert_eq!(index.keys, model);
assert_eq!(
index.find(target),
Ok(UniqueIndexLookupOutcome::Absent { key: target })
);
assert_eq!(
index.find(source),
Ok(UniqueIndexLookupOutcome::Present { key: source, row })
);
}
let removed = *model.get(removed_row).ok_or("model removal unavailable")?;
{
let _prepared = index
.try_prepare_remove(removed)
.map_err(|_| "removal unavailable")?;
}
assert_eq!(index.keys, model);
assert_eq!(
index
.try_prepare_remove(removed)
.map_err(|_| "removal unavailable")?
.commit(),
UniqueIndexRemoveOutcome::Removed {
key: removed,
row: removed_row
}
);
assert_eq!(model.swap_remove(removed_row), removed);
let source = *model.first().ok_or("replacement source unavailable")?;
let replacement = Key(29);
assert_eq!(
index
.try_prepare_replace(source, replacement, 0)
.map_err(|_| "replacement unavailable")?
.commit(),
UniqueIndexReplaceOutcome::Replaced {
source,
target: replacement,
row: 0
}
);
*model.first_mut().ok_or("model source unavailable")? = replacement;
insert(&mut index, removed)?;
model.push(removed);
assert_eq!(index.keys, model);
for key in [Key(0), Key(1), Key(2), Key(17), replacement] {
let expected = match model.iter().position(|candidate| *candidate == key) {
Some(row) => UniqueIndexLookupOutcome::Present { key, row },
None => UniqueIndexLookupOutcome::Absent { key },
};
assert_eq!(index.find(key), Ok(expected));
}
}
}
}
Ok(())
}