use std::collections::BTreeMap;
use std::ops::ControlFlow;
use proptest::prelude::*;
use super::config::SegConfig;
use super::fs::real;
use super::testkit::{TestClock, key_of, try_open_core};
use crate::error::DbError;
const KEYS: u8 = 24;
#[derive(Debug, Clone)]
enum Op {
Put(u8, u8),
Delete(u8),
Insert(u8, u8),
Seal,
SealOldest,
DropOldest,
Reopen,
DirtyReopen,
Hinted(u8),
}
fn op() -> impl Strategy<Value = Op> {
prop_oneof![
6 => (0..KEYS, any::<u8>()).prop_map(|(k, v)| Op::Put(k, v)),
3 => (0..KEYS).prop_map(Op::Delete),
3 => (0..KEYS, any::<u8>()).prop_map(|(k, v)| Op::Insert(k, v)),
2 => Just(Op::Seal),
2 => Just(Op::SealOldest),
1 => Just(Op::DropOldest),
1 => Just(Op::Reopen),
1 => Just(Op::DirtyReopen),
2 => any::<u8>().prop_map(Op::Hinted),
]
}
#[derive(Debug, Default)]
struct Layer {
rows: BTreeMap<u8, Option<u8>>,
sealed: bool,
frozen_at_ms: Option<u64>,
}
#[derive(Debug)]
struct Model {
layers: Vec<Layer>,
now_ms: u64,
}
impl Model {
fn new(now_ms: u64) -> Self {
Self {
layers: vec![Layer::default()],
now_ms,
}
}
fn active(&mut self) -> &mut Layer {
self.layers
.last_mut()
.expect("there is always an active layer")
}
fn get(&self, key: u8) -> Option<u8> {
self.layers
.iter()
.rev()
.find_map(|layer| layer.rows.get(&key).copied())
.flatten()
}
fn get_hinted(&self, key: u8, since_ms: u64) -> Option<u8> {
for layer in self.layers.iter().rev() {
if layer.frozen_at_ms.is_some_and(|at| at < since_ms) {
return None;
}
if let Some(&row) = layer.rows.get(&key) {
return row;
}
}
None
}
fn hints(&self) -> Vec<u64> {
let mut hints = vec![0, self.now_ms + 1];
for at in self.layers.iter().filter_map(|l| l.frozen_at_ms) {
hints.extend([at, at + 1]);
}
hints
}
fn len(&self) -> usize {
self.layers
.iter()
.map(|l| l.rows.values().filter(|v| v.is_some()).count())
.sum()
}
fn visible(&self) -> BTreeMap<u8, u8> {
(0..KEYS)
.filter_map(|k| self.get(k).map(|v| (k, v)))
.collect()
}
fn seal(&mut self) {
let now_ms = self.now_ms;
let active = self.active();
if !active.rows.is_empty() {
active.frozen_at_ms = Some(now_ms);
self.layers.push(Layer::default());
}
}
fn seal_oldest(&mut self) {
let last = self.layers.len() - 1;
let Some(at) = self.layers[..last].iter().position(|l| !l.sealed) else {
return;
};
let nothing_below = at == 0;
if nothing_below {
self.layers[at].rows.retain(|_, v| v.is_some());
}
if self.layers[at].rows.is_empty() {
self.layers.remove(at);
} else {
self.layers[at].sealed = true;
}
}
fn drop_oldest(&mut self) {
if self.layers.first().is_some_and(|l| l.sealed) {
self.layers.remove(0);
}
}
}
fn config() -> SegConfig {
SegConfig {
seal_max_keys: 1_000_000,
max_frozen_generations: 64,
shard_count: 3,
block_size: 256,
..SegConfig::test()
}
}
proptest! {
#![proptest_config(ProptestConfig {
cases: 48,
..ProptestConfig::default()
})]
#[test]
fn the_collection_behaves_like_its_model(ops in prop::collection::vec(op(), 1..80)) {
let dir = tempfile::tempdir().unwrap();
let clock = TestClock::new(1_000);
let mut core = try_open_core(dir.path(), config(), real(), &clock).unwrap();
let mut model = Model::new(1_000);
for (step, op) in ops.iter().enumerate() {
match *op {
Op::Put(k, v) => {
core.put(&key_of(u64::from(k)), &[v]).unwrap();
model.active().rows.insert(k, Some(v));
}
Op::Delete(k) => {
core.delete(&key_of(u64::from(k))).unwrap();
model.active().rows.insert(k, None);
}
Op::Insert(k, v) => {
let exists = model.get(k).is_some();
match core.insert(&key_of(u64::from(k)), &[v]) {
Ok(()) => {
prop_assert!(!exists, "step {step}: insert overwrote key {k}");
model.active().rows.insert(k, Some(v));
}
Err(DbError::KeyExists) => {
prop_assert!(exists, "step {step}: insert refused an absent key {k}");
}
Err(other) => return Err(TestCaseError::fail(format!("{other:?}"))),
}
}
Op::Seal => {
clock.advance(10);
model.now_ms += 10;
core.seal().unwrap();
model.seal();
}
Op::SealOldest => {
core.seal_oldest().unwrap();
model.seal_oldest();
}
Op::DropOldest => {
if let Some(oldest) = core.segments().first() {
let dropped = core.drop_segments_before(oldest.frozen_at_ms + 1).unwrap();
prop_assert_eq!(dropped, 1);
}
model.drop_oldest();
}
Op::Reopen => {
core.clean_shutdown().unwrap();
drop(core);
core = try_open_core(dir.path(), config(), real(), &clock).unwrap();
}
Op::DirtyReopen => {
core.durable_flush().unwrap();
drop(core);
core = try_open_core(dir.path(), config(), real(), &clock).unwrap();
}
Op::Hinted(pick) => {
let hints = model.hints();
let since = hints[usize::from(pick) % hints.len()];
for k in 0..KEYS {
prop_assert_eq!(
core.get_hinted(&key_of(u64::from(k)), since).unwrap(),
model.get_hinted(k, since).map(|v| vec![v]),
"step {}: key {} hinted at {}", step, k, since
);
}
}
}
prop_assert_eq!(core.len(), model.len(), "step {} ({:?}): len", step, op);
let frozen: Vec<u64> = core.segments().iter().map(|s| s.frozen_at_ms).collect();
let expected: Vec<u64> = model
.layers
.iter()
.filter(|l| l.sealed)
.filter_map(|l| l.frozen_at_ms)
.collect();
prop_assert_eq!(frozen, expected, "step {} ({:?}): segment freeze times", step, op);
for k in 0..KEYS {
let key = key_of(u64::from(k));
let expected = model.get(k);
prop_assert_eq!(
core.get(&key).unwrap(),
expected.map(|v| vec![v]),
"step {} ({:?}): key {}", step, op, k
);
prop_assert_eq!(core.contains(&key).unwrap(), expected.is_some());
}
}
let mut scanned = BTreeMap::new();
let mut twice = false;
core.scan(&mut |row| {
let (key, value) = row.unwrap();
let k = (0..KEYS).find(|&k| key_of(u64::from(k)) == key).expect("a known key");
twice |= scanned.insert(k, value).is_some();
ControlFlow::Continue(())
});
prop_assert!(!twice, "the scan produced a key twice");
let expected: BTreeMap<_, _> = model.visible().into_iter().map(|(k, v)| (k, vec![v])).collect();
prop_assert_eq!(&scanned, &expected);
prop_assert_eq!(core.count_exact().unwrap(), model.visible().len() as u64);
prop_assert_eq!(core.len(), model.len());
prop_assert_eq!(
core.segments().len(),
model.layers.iter().filter(|l| l.sealed).count()
);
prop_assert!(core.verify_all().unwrap().is_clean());
}
}
fn tree_key(k: u8) -> super::testkit::RawTestKey {
super::testkit::RawTestKey(key_of(255 + 73 * u64::from(k)))
}
fn model_tree(
path: &std::path::Path,
clock: &TestClock,
shards: usize,
) -> super::SegTree<super::testkit::RawTestKey, String, super::testkit::TextCodec> {
let mut cfg = config();
cfg.shard_count = shards;
super::SegTree::open_with(
path,
super::testkit::meta(),
&[8, 16],
cfg,
super::testkit::TextCodec,
super::core::OpenOptions {
fs: real(),
clock: clock.clock(),
worker: false,
},
)
.unwrap()
}
fn assert_tree_query(
tree: &super::SegTree<super::testkit::RawTestKey, String, super::testkit::TextCodec>,
query: super::SegRange<super::testkit::RawTestKey>,
expected: &[(super::testkit::RawTestKey, String)],
) {
for reverse in [false, true] {
let query = if reverse {
query.clone().rev()
} else {
query.clone()
};
let mut want = expected.to_vec();
if reverse {
want.reverse();
}
assert_eq!(
tree.scan(query.clone())
.collect::<crate::DbResult<Vec<_>>>()
.unwrap(),
want
);
assert_eq!(
tree.scan_keys(query.clone())
.collect::<crate::DbResult<Vec<_>>>()
.unwrap(),
want.iter().map(|r| r.0).collect::<Vec<_>>()
);
let mut cursor = None;
let mut paged = Vec::new();
let mut keys = Vec::new();
for _ in 0..=usize::from(KEYS) {
let page = tree.page(query.clone(), cursor.as_ref(), 3).unwrap();
let key_page = tree.keys_page(query.clone(), cursor.as_ref(), 3).unwrap();
assert_eq!(key_page.next, page.next);
keys.extend(key_page.keys);
paged.extend(page.items);
cursor = page.next;
if cursor.is_none() {
break;
}
}
assert!(
cursor.is_none(),
"pagination must terminate within the bound"
);
assert_eq!(paged, want);
assert_eq!(keys, want.iter().map(|r| r.0).collect::<Vec<_>>());
}
assert!(tree.page(query.clone(), None, 0).unwrap().items.is_empty());
assert!(tree.keys_page(query, None, 0).unwrap().keys.is_empty());
}
fn assert_tree_reads(
tree: &super::SegTree<super::testkit::RawTestKey, String, super::testkit::TextCodec>,
model: &Model,
pick: u8,
) {
use super::SegRange;
use crate::Key;
use std::ops::Bound;
let visible: BTreeMap<Vec<u8>, _> = model
.visible()
.into_iter()
.map(|(k, v)| {
(
tree_key(k).as_bytes().to_vec(),
(tree_key(k), v.to_string()),
)
})
.collect();
let expected: Vec<_> = visible.values().cloned().collect();
assert_eq!(
tree.iter().collect::<crate::DbResult<Vec<_>>>().unwrap(),
expected
);
assert_eq!(tree.first().unwrap(), expected.first().cloned());
assert_eq!(tree.last().unwrap(), expected.last().cloned());
for k in 0..KEYS {
assert_eq!(
tree.try_get(&tree_key(k)).unwrap(),
model.get(k).map(|v| v.to_string())
);
assert_eq!(
tree.try_contains(&tree_key(k)).unwrap(),
model.get(k).is_some()
);
assert_eq!(tree.get(&tree_key(k)), model.get(k).map(|v| v.to_string()));
assert_eq!(tree.contains(&tree_key(k)), model.get(k).is_some());
}
let hints = model.hints();
let since = hints[usize::from(pick) % hints.len()];
let hinted: Vec<_> = (0..KEYS)
.filter_map(|k| {
model
.get_hinted(k, since)
.map(|v| (tree_key(k), v.to_string()))
})
.collect::<BTreeMap<_, _>>()
.into_iter()
.collect();
for k in 0..KEYS {
assert_eq!(
tree.try_get_hinted(&tree_key(k), since).unwrap(),
model.get_hinted(k, since).map(|v| v.to_string())
);
}
assert_eq!(
tree.scan(SegRange::all().written_since(since))
.collect::<crate::DbResult<Vec<_>>>()
.unwrap(),
hinted
);
assert_tree_query(tree, SegRange::all().written_since(since), &hinted);
let start = tree_key(pick % KEYS);
let end = tree_key((pick.wrapping_add(7)) % KEYS);
let bounds = [
(Bound::Included(&start), Bound::Excluded(&end)),
(Bound::Excluded(&start), Bound::Included(&end)),
(Bound::Unbounded, Bound::Included(&end)),
(Bound::Included(&start), Bound::Unbounded),
];
for (lo, hi) in bounds {
let bounded: Vec<_> = visible
.iter()
.filter(|(bytes, _)| {
let low = match lo {
Bound::Included(k) => bytes.as_slice() >= k.as_bytes(),
Bound::Excluded(k) => bytes.as_slice() > k.as_bytes(),
Bound::Unbounded => true,
};
let high = match hi {
Bound::Included(k) => bytes.as_slice() <= k.as_bytes(),
Bound::Excluded(k) => bytes.as_slice() < k.as_bytes(),
Bound::Unbounded => true,
};
low && high
})
.map(|(_, row)| row.clone())
.collect();
assert_eq!(
tree.range_bounds(lo, hi)
.collect::<crate::DbResult<Vec<_>>>()
.unwrap(),
bounded
);
assert_tree_query(tree, SegRange::range(lo, hi), &bounded);
}
assert_eq!(
tree.range(&start, &end)
.collect::<crate::DbResult<Vec<_>>>()
.unwrap(),
expected
.iter()
.filter(|(k, _)| k.as_bytes() >= start.as_bytes() && k.as_bytes() < end.as_bytes())
.cloned()
.collect::<Vec<_>>()
);
for len in [0, 1, 8, 16, 32] {
let prefix = &start.as_bytes()[..len];
let rows: Vec<_> = expected
.iter()
.filter(|(k, _)| k.as_bytes().starts_with(prefix))
.cloned()
.collect();
assert_eq!(
tree.prefix_iter(prefix)
.collect::<crate::DbResult<Vec<_>>>()
.unwrap(),
rows
);
assert_tree_query(tree, SegRange::prefix(prefix), &rows);
}
assert_tree_query(tree, SegRange::all(), &expected);
assert!(tree.verify(super::VerifyScope::All).unwrap().is_clean());
}
proptest! {
#![proptest_config(ProptestConfig { cases: 48, ..ProptestConfig::default() })]
#[test]
fn tree_model_matches_btree_map(ops in prop::collection::vec(op(), 1..80)) {
let dir = tempfile::tempdir().unwrap();
let clock = TestClock::new(1_000);
let mut tree = model_tree(dir.path(), &clock, 3);
let mut model = Model::new(1_000);
for (step, op) in ops.iter().enumerate() {
match *op {
Op::Put(k, v) => { tree.put(&tree_key(k), &v.to_string()).unwrap(); model.active().rows.insert(k, Some(v)); }
Op::Delete(k) => { tree.delete(&tree_key(k)).unwrap(); model.active().rows.insert(k, None); }
Op::Insert(k, v) => {
let result = tree.insert(&tree_key(k), &v.to_string());
if model.get(k).is_some() { prop_assert!(matches!(result, Err(DbError::KeyExists))); }
else { result.unwrap(); model.active().rows.insert(k, Some(v)); }
}
Op::Seal => {
use crate::Key;
let expected: BTreeMap<Vec<u8>, _> = model.visible().into_iter()
.map(|(k, v)| (tree_key(k).as_bytes().to_vec(), (tree_key(k), v.to_string())))
.collect();
let mut expected: Vec<_> = expected.into_values().collect();
let query = if step % 2 == 0 { super::SegRange::all() } else { expected.reverse(); super::SegRange::all().rev() };
let mut suspended = tree.scan(query);
let first = suspended.next().transpose().unwrap();
clock.advance(10); model.now_ms += 10; tree.seal().unwrap(); model.seal();
let actual: Vec<_> = first.into_iter().chain(suspended.map(Result::unwrap)).collect();
prop_assert_eq!(actual, expected, "random freeze while iterator is suspended");
}
Op::SealOldest => { tree.core().seal_oldest().unwrap(); model.seal_oldest(); }
Op::DropOldest => {
if let Some(oldest) = tree.segments().first() { prop_assert_eq!(tree.drop_segments_before(oldest.frozen_at_ms + 1).unwrap(), 1); }
model.drop_oldest();
}
Op::Reopen | Op::DirtyReopen => {
if matches!(op, Op::Reopen) { tree.clean_shutdown().unwrap(); } else { tree.durable_flush().unwrap(); }
drop(tree);
tree = model_tree(dir.path(), &clock, 1 + step % 5);
}
Op::Hinted(_) => {}
}
prop_assert_eq!(tree.len(), model.len());
assert_tree_reads(&tree, &model, match op { Op::Hinted(pick) => *pick, _ => step as u8 });
}
}
}
#[test]
fn tree_model_refills_across_view_changes() {
use super::SegRange;
use super::testkit::raw_ordered_key as ordered_key;
for reverse in [false, true] {
let dir = tempfile::tempdir().unwrap();
let clock = TestClock::new(100);
let tree = model_tree(dir.path(), &clock, 3);
let expected: Vec<_> = (0..900)
.map(|n| (ordered_key(n), format!("v{n}")))
.collect();
for (k, v) in &expected {
tree.put(k, v).unwrap();
}
tree.seal().unwrap();
tree.core().seal_oldest().unwrap();
clock.advance(10);
for (k, v) in &expected {
tree.put(k, v).unwrap();
}
tree.seal().unwrap();
tree.core().seal_oldest().unwrap();
let q = if reverse {
SegRange::all().rev()
} else {
SegRange::all()
};
let mut iter = tree.scan(q);
let first = iter.next().unwrap().unwrap();
for _ in 0..3 {
tree.put(&ordered_key(450), &"v450".into()).unwrap();
clock.advance(10);
tree.seal().unwrap();
tree.core().seal_oldest().unwrap();
}
assert_eq!(tree.drop_segments_before(101).unwrap(), 1);
let rows: Vec<_> = std::iter::once(first)
.chain(iter.map(Result::unwrap))
.collect();
let want: Vec<_> = if reverse {
expected.into_iter().rev().collect()
} else {
expected
};
assert_eq!(rows, want);
assert!(tree.verify(super::VerifyScope::All).unwrap().is_clean());
}
}