aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/store/properties.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/store/properties.rs')
-rw-r--r--src/federation/store/properties.rs437
1 files changed, 437 insertions, 0 deletions
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(())
+ });
+}