use alloc::vec::Vec;
use super::{SlotSet, SlotSetInsertError, SlotSetInsertOutcome, SlotSetRemoveOutcome, StableSlot};
#[test]
fn folds_preserve_remaining_order_across_containers_and_both_ends() {
for values in [
Vec::new(),
alloc::vec![u32::MAX],
alloc::vec![0, 1, 63, 64, 65_535, 65_536, 131_072, u32::MAX],
(0..4_097).collect(),
(0..65_537).collect(),
] {
let set = SlotSet(values.iter().copied().collect());
for (front, back) in [(0, 0), (1, 0), (0, 1), (3, 2), (values.len(), 1)] {
let mut expected: alloc::collections::VecDeque<_> = values.iter().copied().collect();
let mut borrowed = set.slots();
let mut owned = set.clone().into_slots();
for _ in 0..front {
let value = expected.pop_front().map(StableSlot::new);
assert_eq!(borrowed.next(), value);
assert_eq!(owned.next(), value);
}
for _ in 0..back {
let value = expected.pop_back().map(StableSlot::new);
assert_eq!(borrowed.next_back(), value);
assert_eq!(owned.next_back(), value);
}
let mut ordered = alloc::vec![17];
ordered.extend(expected);
let append = |mut values: Vec<u32>, slot: StableSlot| {
values.push(slot.value());
values
};
assert_eq!(borrowed.fold(alloc::vec![17], append), ordered);
assert_eq!(owned.fold(alloc::vec![17], append), ordered);
}
}
}
#[test]
fn slots_preserve_sorted_membership() -> Result<(), &'static str> {
let first = StableSlot::new(0);
let mut set = SlotSet::one(first);
for value in [65_537, 3, 4_096, 1] {
let slot = StableSlot::new(value);
assert_eq!(
set.try_prepare_insert(slot)
.map_err(|_| "slot insertion failed")?
.commit(),
SlotSetInsertOutcome::Inserted { slot }
);
}
let collected = set.slots().map(StableSlot::value).collect::<Vec<_>>();
assert_eq!(collected, [0, 1, 3, 4_096, 65_537]);
assert_eq!(set.len(), 5);
let mut slots = set.slots();
assert_eq!(slots.size_hint(), (5, Some(5)));
#[cfg(target_pointer_width = "64")]
assert_eq!(slots.len(), 5);
assert_eq!(slots.next(), Some(StableSlot::new(0)));
assert_eq!(slots.next_back(), Some(StableSlot::new(65_537)));
assert_eq!(slots.size_hint(), (3, Some(3)));
#[cfg(target_pointer_width = "64")]
assert_eq!(slots.len(), 3);
assert_eq!(slots.by_ref().count(), 3);
assert_eq!(slots.next(), None);
assert_eq!(slots.next_back(), None);
let mut owned = set.into_slots();
assert_eq!(owned.size_hint(), (5, Some(5)));
assert_eq!(owned.next(), Some(StableSlot::new(0)));
assert_eq!(owned.next_back(), Some(StableSlot::new(65_537)));
assert_eq!(owned.size_hint(), (3, Some(3)));
assert_eq!(owned.by_ref().count(), 3);
assert_eq!(owned.size_hint(), (0, Some(0)));
assert_eq!(owned.next(), None);
assert_eq!(owned.next_back(), None);
Ok(())
}
#[test]
fn abandoned_insertions_publish_nothing() -> Result<(), &'static str> {
let mut set = SlotSet::one(StableSlot::new(0));
{
let prepared = set
.try_prepare_insert(StableSlot::new(1))
.map_err(|_| "preparation failed")?;
assert_eq!(prepared.slot(), StableSlot::new(1));
}
assert!(!set.contains(StableSlot::new(1)));
Ok(())
}
#[test]
fn duplicate_and_remove_outcomes_preserve_the_slot() -> Result<(), &'static str> {
let slot = StableSlot::new(7);
let mut set = SlotSet::one(slot);
assert!(matches!(
set.try_prepare_insert(slot),
Err(SlotSetInsertError::AlreadyPresent { slot: duplicate }) if duplicate == slot
));
assert_eq!(set.remove(slot), SlotSetRemoveOutcome::Removed { slot });
assert!(set.is_empty());
assert_eq!(set.remove(slot), SlotSetRemoveOutcome::Absent { slot });
Ok(())
}
#[test]
fn set_algebra_composes_secondary_memberships() -> Result<(), &'static str> {
let left = set([1, 2, 4])?;
let right = set([2, 3, 4])?;
assert_eq!(values(&left.union(&right)), [1, 2, 3, 4]);
assert_eq!(values(&left.intersection(&right)), [2, 4]);
assert_eq!(values(&left.excluding(&right)), [1]);
assert_eq!(values(&left.union_excluding_overlap(&right)), [1, 3]);
assert!(!left.is_disjoint(&right));
assert!(left.intersection(&right).is_subset(&left));
assert!(set([7])?.is_disjoint(&left));
let mut assigned = set([1, 2, 4])?;
assigned.union_assign(&right);
assert_eq!(values(&assigned), [1, 2, 3, 4]);
assigned = set([1, 2, 4])?;
assigned.intersection_assign(&right);
assert_eq!(values(&assigned), [2, 4]);
assert_eq!(
values(&set([1, 2, 4])?.intersection_reusing(&right)),
[2, 4]
);
assert_eq!(
values(&set([1, 2, 3, 4, 5])?.intersection_reusing(&set([2, 4])?)),
[2, 4]
);
assert_eq!(
values(&set([1, 2, 3, 4, 5])?.intersection_owned(set([2, 4])?)),
[2, 4]
);
assigned = set([1, 2, 4])?;
assigned.exclude_assign(&right);
assert_eq!(values(&assigned), [1]);
assigned = set([1, 2, 4])?;
assigned.union_excluding_overlap_assign(&right);
assert_eq!(values(&assigned), [1, 3]);
Ok(())
}
fn set<const N: usize>(values: [u32; N]) -> Result<SlotSet, &'static str> {
let Some((first, remaining)) = values.split_first() else {
return Err("test set was empty");
};
let mut slots = SlotSet::one(StableSlot::new(*first));
for value in remaining {
let SlotSetInsertOutcome::Inserted { .. } = slots
.try_prepare_insert(StableSlot::new(*value))
.map_err(|_| "test slot was duplicated")?
.commit();
}
Ok(slots)
}
fn values(slots: &SlotSet) -> Vec<u32> {
slots.slots().map(StableSlot::value).collect()
}
#[test]
fn owned_chunks_match_the_oracle_across_representation_and_universe_edges()
-> Result<(), &'static str> {
let shapes = [
Vec::new(),
alloc::vec![0, 1, 65_535, 65_536, u32::MAX],
(0..4096).collect(),
(0..4097).collect(),
(0..65_537).collect(),
(0..65_537).step_by(3).collect(),
(u32::MAX - 4096..=u32::MAX).collect(),
];
for left in &shapes {
for right in &shapes {
let a = SlotSet(left.iter().copied().collect());
let b = SlotSet(right.iter().copied().collect());
let oracle_a: roaring::RoaringBitmap = left.iter().copied().collect();
let oracle_b: roaring::RoaringBitmap = right.iter().copied().collect();
for (actual, expected) in [
(a.union(&b), &oracle_a | &oracle_b),
(a.intersection(&b), &oracle_a & &oracle_b),
(a.excluding(&b), &oracle_a - &oracle_b),
(a.union_excluding_overlap(&b), &oracle_a ^ &oracle_b),
(
SlotSet::combine_reads(
crate::storage::query_workspace::MembershipOperation::Union,
a.read(),
b.read(),
),
&oracle_a | &oracle_b,
),
(
SlotSet::combine_reads(
crate::storage::query_workspace::MembershipOperation::Intersection,
a.read(),
b.read(),
),
&oracle_a & &oracle_b,
),
(
SlotSet::combine_reads(
crate::storage::query_workspace::MembershipOperation::Difference,
a.read(),
b.read(),
),
&oracle_a - &oracle_b,
),
(
SlotSet::combine_reads(
crate::storage::query_workspace::MembershipOperation::SymmetricDifference,
a.read(),
b.read(),
),
&oracle_a ^ &oracle_b,
),
] {
assert_eq!(actual.len(), expected.len());
assert!(actual.slots().map(StableSlot::value).eq(expected.iter()));
assert!(
actual
.clone()
.into_slots()
.rev()
.map(StableSlot::value)
.eq(expected.iter().rev())
);
}
assert_eq!(a.is_subset(&b), oracle_a.is_subset(&oracle_b));
assert_eq!(a.is_disjoint(&b), oracle_a.is_disjoint(&oracle_b));
}
}
let mut actual = SlotSet((0..4097).collect());
assert!(matches!(
actual.remove(StableSlot::new(4096)),
SlotSetRemoveOutcome::Removed { .. }
));
assert_eq!(values(&actual), (0..4096).collect::<Vec<_>>());
for slot in (0..4096).rev().map(StableSlot::new) {
assert!(matches!(
actual.remove(slot),
SlotSetRemoveOutcome::Removed { .. }
));
}
assert!(actual.is_empty());
Ok(())
}
proptest::proptest! {
#[test]
fn arbitrary_owned_chunks_match_set_laws(
left in proptest::collection::vec(proptest::prelude::any::<u32>(), 0..128),
right in proptest::collection::vec(proptest::prelude::any::<u32>(), 0..128),
) {
use alloc::collections::BTreeSet;
let a = SlotSet(left.iter().copied().collect());
let b = SlotSet(right.iter().copied().collect());
let left: BTreeSet<_> = left.into_iter().collect();
let right: BTreeSet<_> = right.into_iter().collect();
for (actual, expected) in [
(a.union(&b), left.union(&right).copied().collect::<Vec<_>>()),
(a.intersection(&b), left.intersection(&right).copied().collect()),
(a.excluding(&b), left.difference(&right).copied().collect()),
(a.union_excluding_overlap(&b), left.symmetric_difference(&right).copied().collect()),
] {
proptest::prop_assert_eq!(&values(&actual), &expected);
let mut iter = actual.into_slots();
let mut expected = expected.into_iter();
loop {
let front = expected.next();
proptest::prop_assert_eq!(iter.next().map(StableSlot::value), front);
let back = expected.next_back();
proptest::prop_assert_eq!(iter.next_back().map(StableSlot::value), back);
if front.is_none() && back.is_none() { break; }
}
proptest::prop_assert_eq!(iter.size_hint(), (0, Some(0)));
}
proptest::prop_assert_eq!(a.is_subset(&b), left.is_subset(&right));
proptest::prop_assert_eq!(a.is_disjoint(&b), left.is_disjoint(&right));
}
}
#[test]
fn streamed_words_preserve_sparse_dense_and_partial_final_chunks() -> Result<(), &'static str> {
for words in [
Vec::new(),
alloc::vec![0; 1025],
alloc::vec![u64::MAX; 1025],
(0_u64..1025)
.map(|word| word.wrapping_mul(0x8080_0000_0101_0101))
.collect(),
] {
let mut source = words.iter();
let set = SlotSet::try_from_words(words.len(), |output| {
for (output, input) in output.iter_mut().zip(source.by_ref()) {
*output = *input;
}
Ok::<_, &'static str>(())
})?;
let expected = words
.iter()
.enumerate()
.flat_map(|(ordinal, word)| {
(0..64).filter_map(move |bit| {
(word & (1_u64 << bit) != 0).then_some(((ordinal as u32) << 6) | bit)
})
})
.collect::<Vec<_>>();
assert_eq!(values(&set), expected);
}
let result = SlotSet::try_from_words(3, |_| Err("source refused"));
assert_eq!(result.err(), Some("source refused"));
Ok(())
}
#[test]
fn duplicate_and_missing_members_leave_sparse_and_dense_payloads_unchanged() {
for len in [3, 5000] {
let mut set = SlotSet((0..len).collect());
assert!(set.contains(StableSlot::new(1)));
assert!(!set.contains(StableSlot::new(len)));
assert!(!set.contains(StableSlot::new(u32::MAX)));
assert!(!set.0.insert(1));
assert!(!set.0.remove(len));
assert_eq!(set.len(), u64::from(len));
assert!(set.slots().map(StableSlot::value).eq(0..len));
}
assert!(super::SlotSetRead::Empty.chunks().next_back().is_none());
}
#[test]
fn word_source_cannot_exceed_the_stable_slot_universe() {
extern crate std;
assert!(
std::panic::catch_unwind(|| {
let _result = SlotSet::try_from_words((1 << 26) + 1, |_| Ok::<_, ()>(()));
})
.is_err()
);
}
#[test]
fn owned_iteration_can_finish_the_back_chunk_from_the_front() {
for values in [
alloc::vec![0, 1, 2],
(0..5000).collect(),
alloc::vec![0, 1, 65_536, 65_537],
] {
let set = SlotSet(values.iter().copied().collect());
let mut slots = set.into_slots();
assert_eq!(
slots.next_back().map(StableSlot::value),
values.last().copied()
);
for expected in values.iter().take(values.len().saturating_sub(1)) {
assert_eq!(slots.next().map(StableSlot::value), Some(*expected));
}
assert_eq!(slots.size_hint(), (0, Some(0)));
assert!(slots.next().is_none());
assert!(slots.next_back().is_none());
}
}