extern crate std;
use super::*;
use crate::storage::membership::MembershipKeyError;
use std::panic::catch_unwind;
#[test]
fn bounded_index_preserves_public_outcomes_and_cancelled_updates() -> Result<(), &'static str> {
let mut index = SecondaryIndex::<u8>::try_new_bounded(4, 2).map_err(|_| "index")?;
assert!(index.is_empty());
assert_eq!(index.len(), 0);
for (key, slot) in [(1, 0), (1, 1), (2, 2)] {
let _outcome = index
.try_prepare_insert(key, StableSlot::new(slot))
.map_err(|_| "insert")?
.commit();
}
let slot = StableSlot::new(3);
assert!(matches!(
index.try_prepare_insert(3, slot),
Err(SecondaryIndexInsertError::Full {
secondary_key: 3,
maximum_distinct_keys: 2,
..
})
));
assert!(matches!(
index.try_prepare_insert(1, StableSlot::new(0)),
Err(SecondaryIndexInsertError::AlreadyPresent {
secondary_key: 1,
..
})
));
assert!(matches!(
index.try_prepare_insert(1, StableSlot::new(9)),
Err(SecondaryIndexInsertError::Inconsistent { .. })
));
drop(index.try_prepare_insert(2, slot).map_err(|_| "prepare")?);
assert_eq!(index.find(2).into_parts().1.ok_or("members")?.len(), 1);
{
let removed_slot = StableSlot::new(1);
let prepared = index
.try_prepare_remove(1, removed_slot)
.map_err(|_| "prepare remove")?;
let SecondaryIndexPrepareRemoveOutcome::Prepared(prepared) = prepared else {
return Err("existing membership was not prepared");
};
assert_eq!(prepared.slot(), removed_slot);
drop(prepared);
}
assert_eq!(index.find(1).into_parts().1.ok_or("members")?.len(), 2);
assert_eq!(
index.remove(9, slot),
Ok(SecondaryIndexRemoveOutcome::BucketAbsent {
secondary_key: 9,
slot
})
);
assert_eq!(
index.remove(1, slot),
Ok(SecondaryIndexRemoveOutcome::SlotAbsent {
secondary_key: 1,
slot
})
);
for value in [4, u32::MAX] {
let slot = StableSlot::new(value);
assert_eq!(
index.remove(1, slot),
Ok(SecondaryIndexRemoveOutcome::SlotAbsent {
secondary_key: 1,
slot
})
);
assert_eq!(
index.remove(9, slot),
Ok(SecondaryIndexRemoveOutcome::BucketAbsent {
secondary_key: 9,
slot
})
);
}
assert_eq!(
index.remove(1, StableSlot::new(1)),
Ok(SecondaryIndexRemoveOutcome::RemovedFromBucket {
secondary_key: 1,
slot: StableSlot::new(1),
remaining_slots: 1
})
);
assert_eq!(
index.remove(1, StableSlot::new(0)),
Ok(SecondaryIndexRemoveOutcome::RemovedBucket {
secondary_key: 1,
slot: StableSlot::new(0)
})
);
assert_eq!(
index
.try_prepare_move(2, 2, StableSlot::new(2))
.map_err(|_| "unchanged")?
.commit(),
SecondaryIndexMoveOutcome::Unchanged {
secondary_key: 2,
slot: StableSlot::new(2)
}
);
assert_eq!(
index
.try_prepare_move(2, 3, StableSlot::new(2))
.map_err(|_| "rename")?
.commit(),
SecondaryIndexMoveOutcome::RenamedBucket {
source: 2,
target: 3,
slot: StableSlot::new(2)
}
);
assert!(matches!(
index.try_prepare_move(9, 3, slot),
Err(SecondaryIndexMoveError::SourceBucketAbsent { .. })
));
assert!(matches!(
index.try_prepare_move(3, 2, slot),
Err(SecondaryIndexMoveError::SourceSlotAbsent { .. })
));
assert!(matches!(
index.try_prepare_move(3, 2, StableSlot::new(9)),
Err(SecondaryIndexMoveError::Inconsistent { .. })
));
let _inserted = index
.try_prepare_insert(2, StableSlot::new(2))
.map_err(|_| "second membership")?
.commit();
assert!(matches!(
index.try_prepare_move(3, 2, StableSlot::new(2)),
Err(SecondaryIndexMoveError::TargetSlotAlreadyPresent { .. })
));
let _inserted = index
.try_prepare_insert(3, StableSlot::new(1))
.map_err(|_| "add")?
.commit();
assert!(matches!(
index.try_prepare_move(3, 4, StableSlot::new(1)),
Err(SecondaryIndexMoveError::Full {
maximum_distinct_keys: 2,
..
})
));
let _removed = index
.remove(2, StableSlot::new(2))
.map_err(|_| "remove target")?;
assert_eq!(
index
.try_prepare_move(3, 2, StableSlot::new(1))
.map_err(|_| "new target")?
.commit(),
SecondaryIndexMoveOutcome::MovedAndCreatedTargetBucket {
source: 3,
target: 2,
slot: StableSlot::new(1)
}
);
assert_eq!(
index
.try_prepare_move(2, 3, StableSlot::new(1))
.map_err(|_| "merge")?
.commit(),
SecondaryIndexMoveOutcome::MovedAndRemovedSourceBucket {
source: 2,
target: 3,
slot: StableSlot::new(1)
}
);
for value in [1, 2] {
let _removed = index
.remove(3, StableSlot::new(value))
.map_err(|_| "drain")?;
}
assert!(index.is_empty());
assert!(matches!(
SecondaryIndex::<u32>::try_new(usize::MAX),
Err(SecondaryIndexCreationError::Layout(_))
));
Ok(())
}
#[test]
fn changed_key_equality_refuses_removal_without_losing_memberships() -> Result<(), &'static str> {
use core::sync::atomic::{AtomicBool, Ordering};
static CORRUPTED: AtomicBool = AtomicBool::new(false);
#[derive(Clone, Copy, Debug, Eq)]
struct Key(u8);
impl PartialEq for Key {
fn eq(&self, other: &Self) -> bool {
CORRUPTED.load(Ordering::Relaxed) || self.0 == other.0
}
}
impl IndexKey for Key {
fn index_word(self) -> u64 {
0
}
}
let mut index = SecondaryIndex::<Key>::try_new_bounded(2, 2).map_err(|_| "index")?;
for key in [0, 1] {
let _outcome = index
.try_prepare_insert(Key(key), StableSlot::new(u32::from(key)))
.map_err(|_| "insert")?
.commit();
}
CORRUPTED.store(true, Ordering::Relaxed);
let result = index.remove(Key(0), StableSlot::new(0));
CORRUPTED.store(false, Ordering::Relaxed);
assert_eq!(
result,
Err(SecondaryIndexRemoveError::Inconsistent {
secondary_key: Key(0),
slot: StableSlot::new(0),
reason: SecondaryIndexInconsistency::Membership(MembershipIndexError::KeyIndex(
MembershipKeyError::StoredRowMismatch {
expected: 1,
actual: 0
}
))
})
);
for key in [0, 1] {
let members = index
.membership(Key(key))
.map_err(|_| "lookup")?
.ok_or("members")?;
assert_eq!(members.len(), 1);
assert!(members.contains(u32::from(key)));
}
Ok(())
}
#[test]
fn failures_keep_their_keys_slot_and_original_reason() {
let slot = StableSlot::new(7);
for reason in [
MembershipIndexError::InsufficientKeys {
required: 8,
available: 3,
},
MembershipIndexError::InsufficientHashBuckets {
required: 16,
available: 8,
},
MembershipIndexError::KeyIndex(MembershipKeyError::ProbeLimitReached),
MembershipIndexError::Memberships(MembershipDirectoryError::SlotOutsideCapacity {
slot: 7,
capacity: 4,
}),
] {
let expected = SecondaryIndexInconsistency::Membership(reason);
assert_eq!(
insert_error(11, slot, reason),
SecondaryIndexInsertError::Inconsistent {
secondary_key: 11,
slot,
reason: expected
}
);
assert_eq!(
remove_error(11, slot, reason),
SecondaryIndexRemoveError::Inconsistent {
secondary_key: 11,
slot,
reason: expected
}
);
let error = move_error(11, 13, slot, reason);
assert!(
matches!(error, SecondaryIndexMoveError::Inconsistent { source: 11, target: 13, slot: found, reason: got } if found == slot && got == expected)
);
}
assert_eq!(
insert_error(11, slot, MembershipIndexError::SourceKeyAbsent),
SecondaryIndexInsertError::Inconsistent {
secondary_key: 11,
slot,
reason: SecondaryIndexInconsistency::Membership(MembershipIndexError::SourceKeyAbsent)
}
);
assert!(
catch_unwind(|| bind_membership(11, Err(MembershipIndexError::SourceKeyAbsent))).is_err()
);
}
#[test]
fn an_outcome_from_the_wrong_operation_cannot_be_relabelled() {
for outcome in [
MembershipIndexUpdate::InsertedNewKey,
MembershipIndexUpdate::InsertedIntoExistingKey,
MembershipIndexUpdate::RemovedKey,
MembershipIndexUpdate::RemovedFromExistingKey,
MembershipIndexUpdate::MovedBetweenExistingKeys,
MembershipIndexUpdate::MovedAndRemovedSourceKey,
MembershipIndexUpdate::MovedAndCreatedTargetKey,
MembershipIndexUpdate::RenamedKey,
MembershipIndexUpdate::Unchanged,
] {
let slot = StableSlot::new(7);
if !matches!(
outcome,
MembershipIndexUpdate::InsertedNewKey | MembershipIndexUpdate::InsertedIntoExistingKey
) {
assert!(catch_unwind(|| insert_outcome(outcome, 11, slot)).is_err());
}
if !matches!(
outcome,
MembershipIndexUpdate::RemovedKey | MembershipIndexUpdate::RemovedFromExistingKey
) {
assert!(catch_unwind(|| remove_outcome(outcome, 11, slot, 2)).is_err());
}
if matches!(
outcome,
MembershipIndexUpdate::InsertedNewKey
| MembershipIndexUpdate::InsertedIntoExistingKey
| MembershipIndexUpdate::RemovedKey
| MembershipIndexUpdate::RemovedFromExistingKey
) {
assert!(catch_unwind(|| move_outcome(outcome, 11, 13, slot)).is_err());
}
}
}