diff options
| author | tv <tv@krebsco.de> | 2026-11-16 16:51:43 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 18:01:56 +0100 |
| commit | 62037cc131ab52c926debeacbef86d7728ecda2e (patch) | |
| tree | 69515916a8912ac61e11c1722f7219f9ff999d27 /src | |
| parent | 4d13b874821220a65b8f74f6d0dd48028ec4c0f8 (diff) | |
store: properties over generated histories
Two to four writers, each knowing what it wrote and what was written when it last caught
up with the others, write the test fold's events on one or two events they know. Eras
and cuts are numbered by their history, each number written once, or, for some
properties, as often as it comes. A store offered them is checked against the whole
history, read from the root with nothing forgotten:
* it holds the same whatever order the events come in: every order putting each after
what it builds on, for up to six events; some shuffled beyond; and backwards, where
every event waits until the first comes;
* it judges every event as the whole history does, the store's own refusals aside;
* what builds on a refused event is refused;
* what it took is above its checkpoint's heads, the cut naming the checkpoint among it,
and it reads as its checkpoint and what it took, and as its whole history;
* a node starting from its checkpoint holds what it holds.
A failing history is cut down, events taken out with what builds on them for as long as
it still fails, and printed.
Diffstat (limited to 'src')
| -rw-r--r-- | src/federation/store/mod.rs | 2 | ||||
| -rw-r--r-- | src/federation/store/properties.rs | 437 | ||||
| -rw-r--r-- | src/federation/store/testfold.rs | 5 |
3 files changed, 444 insertions, 0 deletions
diff --git a/src/federation/store/mod.rs b/src/federation/store/mod.rs index 73ed029..c87f337 100644 --- a/src/federation/store/mod.rs +++ b/src/federation/store/mod.rs @@ -10,6 +10,8 @@ use crate::transport::Hex; pub(crate) mod memory; #[cfg(test)] +mod properties; +#[cfg(test)] pub(crate) mod testfold; /// An event's name: the SHA-256 of its bytes, written as 64 lower-case hex digits. diff --git a/src/federation/store/properties.rs b/src/federation/store/properties.rs new file mode 100644 index 0000000..c3b6171 --- /dev/null +++ b/src/federation/store/properties.rs @@ -0,0 +1,437 @@ +//! The store's properties over generated histories (`docs/federation-tests.md`, Properties): +//! writers that see some of what the others wrote build on it with the test fold's events, +//! and what a store holds is checked against the whole history, read from the root with +//! nothing forgotten. A failing history is cut down, events taken out with what builds on +//! them for as long as it still fails, and printed. + +use std::collections::{BTreeMap, BTreeSet, HashMap}; + +use super::memory::{Refusal, Store}; +use super::testfold::{self, State, TestFold}; +use super::{Fold, Id}; +use crate::testrand::{Rng, for_seeds}; + +/// The most events a history has. +const MOST: usize = 20; + +/// Histories this small are offered in every order that puts each event after what it +/// builds on; larger ones in some orders, seeded. +const EVERY_ORDER: usize = 6; + +const KEYS: [&str; 3] = ["a", "b", "c"]; + +/// A root and events, in the order written: each after what it builds on. +#[derive(Clone)] +struct History { + root: Vec<u8>, + events: Vec<Vec<u8>>, + ids: Vec<Id>, + deps: HashMap<Id, Vec<Id>>, +} + +impl History { + fn new(root: Vec<u8>) -> Self { + Self { + root, + events: Vec::new(), + ids: Vec::new(), + deps: HashMap::new(), + } + } + + fn push(&mut self, event: Vec<u8>) { + let id = Id::of(&event); + self.deps + .insert(id, TestFold::dependencies(&event).unwrap_or_default()); + self.ids.push(id); + self.events.push(event); + } + + fn root_id(&self) -> Id { + Id::of(&self.root) + } + + /// The events of `ids` and all they build on, the root aside. + fn history(&self, ids: &[Id]) -> BTreeSet<Id> { + let mut history = BTreeSet::new(); + let mut todo = ids.to_vec(); + while let Some(id) = todo.pop() { + if let Some(deps) = self.deps.get(&id) + && history.insert(id) + { + todo.extend(deps); + } + } + history + } + + /// What the events of `ids` and all they build on read as, from the root, with + /// nothing forgotten. + fn read(&self, ids: &[Id]) -> State { + let history = self.history(ids); + let mut state = TestFold::start(&self.root, &[]).expect("a root reads"); + for (id, event) in self.ids.iter().zip(&self.events) { + if history.contains(id) { + TestFold::add(&mut state, id, event); + } + } + state + } + + /// A store offered the events in `order`, by their places in the history. + fn store(&self, order: &[usize]) -> Store<TestFold> { + let mut store = Store::new(self.root.clone(), Vec::new()).expect("a root starts a store"); + for &i in order { + store.offer(self.events[i].clone()); + } + store + } + + /// The order written. + fn written(&self) -> Vec<usize> { + (0..self.events.len()).collect() + } + + /// Orders to offer the events in: every one that puts each after what it builds on, + /// where there are few; else the order written and some shuffled, seeded. Backwards + /// too, where every event waits until the first comes. + fn orders(&self) -> Vec<Vec<usize>> { + let n = self.events.len(); + let mut orders = if n <= EVERY_ORDER { + let mut all = Vec::new(); + self.after_dependencies(&mut Vec::new(), &mut all); + all + } else { + let mut rng = Rng::new(n as u64); + let mut orders = vec![self.written()]; + for _ in 0..4 { + let mut order = self.written(); + rng.shuffle(&mut order); + orders.push(order); + } + orders + }; + orders.push(self.written().into_iter().rev().collect()); + orders + } + + /// Every order beginning with `order` that puts each event after what it builds on. + fn after_dependencies(&self, order: &mut Vec<usize>, all: &mut Vec<Vec<usize>>) { + if order.len() == self.events.len() { + all.push(order.clone()); + return; + } + let placed: BTreeSet<Id> = order.iter().map(|&i| self.ids[i]).collect(); + for (i, id) in self.ids.iter().enumerate() { + let ready = self.deps[id] + .iter() + .all(|dep| placed.contains(dep) || !self.deps.contains_key(dep)); + if !placed.contains(id) && ready { + order.push(i); + self.after_dependencies(order, all); + order.pop(); + } + } + } + + /// The history without the event at `i`, and what builds on it. + fn without(&self, i: usize) -> Self { + let mut gone = BTreeSet::from([self.ids[i]]); + let mut history = Self::new(self.root.clone()); + for (id, event) in self.ids.iter().zip(&self.events) { + if gone.contains(id) || self.deps[id].iter().any(|dep| gone.contains(dep)) { + gone.insert(*id); + } else { + history.push(event.clone()); + } + } + history + } + + /// The root's ID, then each event's with its bytes, in the order written. + fn show(&self) -> String { + let events = self + .ids + .iter() + .zip(&self.events) + .map(|(id, event)| format!("{id} {}", String::from_utf8_lossy(event))); + std::iter::once(format!("root {}", self.root_id())) + .chain(events) + .collect::<Vec<_>>() + .join("\n") + } +} + +/// One of `ids`, of the latest five more often than not. +fn pick(rng: &mut Rng, ids: &[Id]) -> Id { + if rng.chance(0.6) { + *rng.pick(&ids[ids.len().saturating_sub(5)..]) + } else { + *rng.pick(ids) + } +} + +/// A history of up to `MOST` events by two to four writers. Each builds on one event it +/// knows or two: the root, what it wrote, and what was written when it last caught up with +/// the others. Eras and cuts are numbered by their history; unless `conflicts`, no two +/// have one number. +fn generate(rng: &mut Rng, conflicts: bool) -> History { + let mut history = History::new(testfold::root("properties")); + let writers = rng.between(2, 4); + let mut known = vec![vec![history.root_id()]; writers]; + let mut eras = BTreeSet::new(); + let mut cuts = BTreeSet::new(); + for i in 0..rng.between(1, MOST) { + let writer = rng.below(writers); + if rng.chance(0.2) { + known[writer] = std::iter::once(history.root_id()) + .chain(history.ids.iter().copied()) + .collect(); + } + let mut deps = vec![pick(rng, &known[writer])]; + let other = pick(rng, &known[writer]); + if rng.chance(0.3) && !deps.contains(&other) { + deps.push(other); + } + let at = history.read(&deps); + let key = *rng.pick(&KEYS); + let value = i.to_string(); + let put = testfold::put(&deps, key, &value); + let mut event = match rng.below(20) { + 0 => testfold::lock(&deps, key), + 1..=3 => { + let n = at.era().0 + 1; + if eras.insert(n) || conflicts { + testfold::era(&deps, n, &value) + } else { + put.clone() + } + } + 4 | 5 => { + let n = at.cut() + 1; + // What it builds on, or one event of its history. + let past: Vec<Id> = history.history(&deps).into_iter().collect(); + let heads = if past.is_empty() || rng.chance(0.7) { + deps.clone() + } else { + vec![*rng.pick(&past)] + }; + if cuts.insert(n) || conflicts { + testfold::cut(&deps, n, &heads) + } else { + put.clone() + } + } + 6 => testfold::junk(&deps), + _ => put.clone(), + }; + if history.deps.contains_key(&Id::of(&event)) { + event = put; + } + known[writer].push(Id::of(&event)); + history.push(event); + } + history +} + +/// Checks `property` on histories from `cases` seeds, with eras and cuts of one number or +/// without; a failing history is cut down and printed. +fn check(cases: u64, conflicts: bool, property: impl Fn(&History) -> Result<(), String>) { + for_seeds(cases, |rng| { + let history = generate(rng, conflicts); + if let Err(why) = property(&history) { + let (history, why) = cut_down(history, why, &property); + panic!("{why}, in the history\n{}", history.show()); + } + }); +} + +/// The history with every event taken out, with what builds on it, that it fails without. +fn cut_down( + mut history: History, + mut why: String, + property: &impl Fn(&History) -> Result<(), String>, +) -> (History, String) { + 'shorter: loop { + for i in (0..history.events.len()).rev() { + let shorter = history.without(i); + if let Err(still) = property(&shorter) { + (history, why) = (shorter, still); + continue 'shorter; + } + } + return (history, why); + } +} + +/// What a store holds, to compare stores by: its checkpoint, what it took after it, and +/// what it reads as. +fn holding(store: &Store<TestFold>) -> (Vec<u8>, BTreeSet<Id>, State) { + ( + store.checkpoint().to_vec(), + store.taken().iter().copied().collect(), + store.state().clone(), + ) +} + +/// What a state says, to compare a store's with its whole history's: what counts, what is +/// locked, the era and its tag, and the cut. +type Says = ( + BTreeMap<String, String>, + BTreeSet<String>, + u64, + Option<String>, + u64, +); + +fn says(state: &State) -> Says { + let (era, tag) = state.era(); + ( + state.counts(), + state.locks().clone(), + era, + tag.cloned(), + state.cut(), + ) +} + +#[test] +fn a_store_holds_the_same_whatever_order_events_come_in() { + check(100, false, |history| { + let held = holding(&history.store(&history.written())); + for order in history.orders() { + if holding(&history.store(&order)) != held { + return Err(format!( + "offered in the order {order:?}, it holds otherwise" + )); + } + } + Ok(()) + }); +} + +#[test] +fn a_store_judges_every_event_as_its_whole_history_does() { + for conflicts in [false, true] { + check(200, conflicts, |history| { + let store = history.store(&history.written()); + for (id, event) in history.ids.iter().zip(&history.events) { + let judged = TestFold::judge(&history.read(&history.deps[id]), id, event); + let refusal = store.refusal(id); + if refusal.is_none() && judged.is_err() { + return Err(format!("{id} is taken, its whole history refuses it")); + } + // A cut numbered as one taken, at a history without that one, a store judges + // by the checkpoint it moved to, after the history's. + if !conflicts && matches!(refusal, Some(Refusal::Judged(_))) && judged.is_ok() { + return Err(format!("{id} is refused, its whole history takes it")); + } + } + Ok(()) + }); + } +} + +#[test] +fn what_builds_on_a_refused_event_is_refused() { + for conflicts in [false, true] { + check(200, conflicts, |history| { + let backwards: Vec<usize> = history.written().into_iter().rev().collect(); + for order in [history.written(), backwards] { + let store = history.store(&order); + for id in &history.ids { + let refused = history.deps[id] + .iter() + .find(|dep| store.refusal(dep).is_some()); + if let Some(dep) = refused + && store.refusal(id).is_none() + { + return Err(format!("{id} is taken, built on {dep}, which is refused")); + } + } + } + Ok(()) + }); + } +} + +#[test] +fn a_store_reads_as_its_whole_history_does() { + for conflicts in [false, true] { + check(200, conflicts, |history| { + let store = history.store(&history.written()); + let (at, _) = TestFold::parts(store.checkpoint()).expect("a checkpoint"); + let heads: BTreeSet<Id> = if at.is_empty() { + BTreeSet::from([store.id()]) + } else { + at.iter().copied().collect() + }; + // What it took after its checkpoint is above its heads. + let taken: BTreeSet<Id> = store.taken().iter().copied().collect(); + for id in store.taken() { + let deps = &history.deps[id]; + let on = deps + .iter() + .all(|dep| heads.contains(dep) || taken.contains(dep)); + let above = deps.iter().any(|dep| taken.contains(dep)) + || heads.iter().all(|head| deps.contains(head)); + if !on || !above { + return Err(format!("{id} is taken, not above the checkpoint's heads")); + } + } + // Moving to its checkpoint refused nothing that named it. + if !at.is_empty() && store.state().named() != Some(&at[..]) { + return Err("the cut naming its checkpoint isn't taken".to_owned()); + } + // It reads as its checkpoint and what it took after it. + let kept: Vec<(Id, Vec<u8>)> = store + .kept() + .into_iter() + .map(|bytes| (Id::of(&bytes), bytes)) + .collect(); + let mut state = TestFold::start(store.checkpoint(), &kept).expect("it reads"); + for id in store.taken() { + TestFold::add(&mut state, id, store.get(id).expect("taken")); + } + if state != *store.state() { + return Err("it reads otherwise than its checkpoint and what it took".to_owned()); + } + // And as its whole history. + let whole = history.read(&store.heads()); + if says(&whole) != says(&state) { + return Err(format!( + "it reads {:?}, its whole history {:?}", + says(&state), + says(&whole) + )); + } + Ok(()) + }); + } +} + +#[test] +fn a_node_starting_from_the_checkpoint_holds_what_the_others_do() { + check(200, false, |history| { + let store = history.store(&history.written()); + if TestFold::parts(store.checkpoint()).is_some_and(|(at, _)| at.is_empty()) { + return Ok(()); + } + let backwards: Vec<usize> = history.written().into_iter().rev().collect(); + for order in [history.written(), backwards] { + let mut pinned: Store<TestFold> = + Store::pinned(store.id(), store.checkpoint().to_vec(), store.kept()) + .map_err(|why| format!("its checkpoint isn't one to start from: {why:?}"))?; + for &i in &order { + pinned.offer(history.events[i].clone()); + } + if holding(&pinned) != holding(&store) { + return Err(format!( + "offered in the order {order:?}, one starting from the checkpoint holds \ + otherwise" + )); + } + } + Ok(()) + }); +} diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs index 7e3b703..094c424 100644 --- a/src/federation/store/testfold.rs +++ b/src/federation/store/testfold.rs @@ -186,6 +186,11 @@ impl State { self.cut } + /// The heads the latest cut names, where it is one of the state's events. + pub(crate) fn named(&self) -> Option<&[Id]> { + self.cuts.get(&self.cut).map(Vec::as_slice) + } + /// The events here above `heads` (`docs/store.md`, Events): each with them all in its /// history, and each of its dependencies one of them or above them. fn above(&self, heads: &BTreeSet<Id>) -> BTreeSet<Id> { |
