//! 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, events: Vec>, ids: Vec, deps: HashMap>, } impl History { fn new(root: Vec) -> Self { Self { root, events: Vec::new(), ids: Vec::new(), deps: HashMap::new(), } } fn push(&mut self, event: Vec) { 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 { 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 { 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 { (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> { 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, all: &mut Vec>) { if order.len() == self.events.len() { all.push(order.clone()); return; } let placed: BTreeSet = 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::>() .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 = 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) -> (Vec, BTreeSet, 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, BTreeSet, u64, Option, 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 = 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 = 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 = 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)> = 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 = history.written().into_iter().rev().collect(); for order in [history.written(), backwards] { let mut pinned: Store = 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(()) }); }