diff options
Diffstat (limited to 'src/federation/store')
| -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> { |
