//! A fold made for the store's tests (`docs/federation-tests.md`): smaller than the //! federation's, but judging by history, refusing by what a node took before, reading by //! what counts, and moving to checkpoints, as the federation does. //! //! * `put`: a value at a key, refused where the key is locked at its history. What a key //! holds is its latest put, none other having it in its history, then the lowest ID. //! * `lock`: a key locked for good. //! * `era`: era `n`, taken only where `n` is one past the era at its history; of two of one //! number, a node keeps the first it takes (as the federation's versions). //! * `cut`: cut `n`, naming heads to move the store to, as `era`: above the heads the latest //! cut of its history names, and holding that cut (or after the checkpoint the state //! starts from, where it holds none); none of them in another's history. It must be above //! them. //! * `junk`: refused wherever it is. use std::collections::{BTreeMap, BTreeSet}; use serde::{Deserialize, Serialize}; use super::{Fold, Id, Refused}; #[derive(Serialize, Deserialize)] struct Event { deps: Vec, kind: Kind, } #[derive(Clone, Serialize, Deserialize)] #[serde(rename_all = "lowercase")] pub(crate) enum Kind { Put { key: String, value: String }, Lock { key: String }, Era { n: u64, tag: String }, Cut { n: u64, heads: Vec }, Junk, } /// A checkpoint, a root among them. #[derive(Serialize, Deserialize)] struct Checkpoint { name: String, at: Vec, keeps: Vec, era: u64, tag: String, cut: u64, locks: Vec, } /// An event of this fold, built on `deps`. pub(crate) fn event(deps: &[Id], kind: Kind) -> Vec { let mut deps: Vec = deps.iter().map(Id::to_string).collect(); deps.sort(); deps.dedup(); serde_json::to_vec(&Event { deps, kind }).expect("an event encodes") } pub(crate) fn put(deps: &[Id], key: &str, value: &str) -> Vec { event( deps, Kind::Put { key: key.to_owned(), value: value.to_owned(), }, ) } pub(crate) fn lock(deps: &[Id], key: &str) -> Vec { event( deps, Kind::Lock { key: key.to_owned(), }, ) } pub(crate) fn era(deps: &[Id], n: u64, tag: &str) -> Vec { event( deps, Kind::Era { n, tag: tag.to_owned(), }, ) } pub(crate) fn cut(deps: &[Id], n: u64, heads: &[Id]) -> Vec { let mut heads: Vec = heads.iter().map(Id::to_string).collect(); heads.sort(); event(deps, Kind::Cut { n, heads }) } pub(crate) fn junk(deps: &[Id]) -> Vec { event(deps, Kind::Junk) } /// A root, named so that tests can tell several apart. pub(crate) fn root(name: &str) -> Vec { serde_json::to_vec(&Checkpoint { name: name.to_owned(), at: Vec::new(), keeps: Vec::new(), era: 0, tag: String::new(), cut: 0, locks: Vec::new(), }) .expect("a root encodes") } /// What a fork's root takes besides its heads: the era it starts in. pub(crate) fn fork_spec(era: u64, tag: &str) -> Vec { serde_json::to_vec(&(era, tag)).expect("a spec encodes") } #[derive(Clone, Debug, Default, PartialEq, Eq)] pub(crate) struct State { /// Every event added, by ID, with its dependencies. graph: BTreeMap>, /// What the checkpoint keeps: in the history of every event after it. before: BTreeSet, /// The heads the checkpoint was built at. at: BTreeSet, puts: BTreeMap>, values: BTreeMap, locks: BTreeSet, era: u64, tags: BTreeMap, cut: u64, /// The heads each cut names, by its number; and each cut, with its number. cuts: BTreeMap>, cut_events: BTreeMap, } impl State { /// Whether `b` is in the history of `a`. pub(crate) fn built_on(&self, a: &Id, b: &Id) -> bool { // What the checkpoint keeps is in the history of every event after it. Of the // checkpoint's heads, the state holds no history: as it tells, none builds on what // the checkpoint keeps, nor on another head. if self.before.contains(b) { return self.graph.contains_key(a) && !self.before.contains(a); } let mut seen = BTreeSet::new(); let mut todo: Vec = self.graph.get(a).cloned().unwrap_or_default(); while let Some(next) = todo.pop() { if next == *b { return true; } if seen.insert(next) { todo.extend(self.graph.get(&next).into_iter().flatten().copied()); } } false } /// What each key holds: its latest put, then the lowest ID. pub(crate) fn counts(&self) -> BTreeMap { self.counting() .into_iter() .map(|(key, id)| (key, self.values[&id].clone())) .collect() } fn counting(&self) -> BTreeMap { self.puts .iter() .filter_map(|(key, puts)| { puts.iter() .filter(|p| !puts.iter().any(|q| q != *p && self.built_on(q, p))) .min() .map(|id| (key.clone(), *id)) }) .collect() } pub(crate) fn locks(&self) -> &BTreeSet { &self.locks } pub(crate) fn era(&self) -> (u64, Option<&String>) { (self.era, self.tags.get(&self.era)) } pub(crate) fn cut(&self) -> u64 { 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) -> BTreeSet { let mut above = BTreeSet::new(); loop { let more: Vec = self .graph .iter() .filter(|(id, deps)| { !above.contains(*id) && !heads.contains(*id) && !deps.is_empty() && deps .iter() .all(|dep| heads.contains(dep) || above.contains(dep)) && (deps.iter().any(|dep| above.contains(dep)) || heads.iter().all(|head| deps.contains(head))) }) .map(|(id, _)| *id) .collect(); if more.is_empty() { return above; } above.extend(more); } } /// Whether an event built on `deps`, whose history reads as this state, may name /// `heads` for a checkpoint: as `cut` says, and the event above them. fn may_cut(&self, deps: &[Id], heads: &[Id]) -> bool { if heads.is_empty() || heads.windows(2).any(|pair| pair[0] >= pair[1]) { return false; } if heads .iter() .any(|a| heads.iter().any(|b| a != b && self.built_on(a, b))) { return false; } let after = match self.cuts.get(&self.cut) { // The latest cut of the history is one of the state's events. Some(current) => { let above = self.above(¤t.iter().copied().collect()); heads.iter().all(|head| above.contains(head)) && self.cut_events.iter().any(|(cut, n)| { *n == self.cut && heads .iter() .any(|head| head == cut || self.built_on(head, cut)) }) } // The latest cut is in the history of the checkpoint the state starts from: the // heads are after that checkpoint, or its own, which count as after the latest // cut and holding it, so that a node starting from it judges the cut naming it // as every node does. None => { heads.iter().eq(self.at.iter()) || heads .iter() .all(|head| self.graph.contains_key(head) && !self.before.contains(head)) } }; let named: BTreeSet = heads.iter().copied().collect(); let above = self.above(&named); after && deps .iter() .all(|dep| named.contains(dep) || above.contains(dep)) && (deps.iter().any(|dep| above.contains(dep)) || named.iter().all(|head| deps.contains(head))) } } fn decode(bytes: &[u8]) -> Option<(Vec, Kind)> { let event: Event = serde_json::from_slice(bytes).ok()?; let deps = event .deps .iter() .map(|dep| Id::from_hex(dep)) .collect::>>()?; Some((deps, event.kind)) } fn ids(texts: &[String]) -> Option> { texts.iter().map(|text| Id::from_hex(text)).collect() } fn hex(ids: impl IntoIterator) -> Vec { let mut texts: Vec = ids.into_iter().map(|id| id.to_string()).collect(); texts.sort(); texts } pub(crate) struct TestFold; impl Fold for TestFold { type State = State; const NAME: &'static str = "test"; const LARGEST: usize = 64 * 1024; fn dependencies(event: &[u8]) -> Option> { decode(event).map(|(deps, _)| deps) } fn judge(at: &State, _id: &Id, event: &[u8]) -> Result<(), Refused> { let (deps, kind) = decode(event).ok_or_else(|| Refused::new("no event"))?; match kind { Kind::Put { key, .. } if at.locks.contains(&key) => { Err(Refused::new(format!("{key} is locked"))) } Kind::Put { .. } | Kind::Lock { .. } => Ok(()), Kind::Era { n, .. } if n == at.era + 1 => Ok(()), Kind::Era { n, .. } => Err(Refused::new(format!("era {n} after {}", at.era))), Kind::Cut { n, heads } => { let heads = ids(&heads).ok_or_else(|| Refused::new("heads not IDs"))?; if n != at.cut + 1 { Err(Refused::new(format!("cut {n} after {}", at.cut))) } else if !at.may_cut(&deps, &heads) { Err(Refused::new("heads it may not name")) } else { Ok(()) } } Kind::Junk => Err(Refused::new("junk")), } } fn add(state: &mut State, id: &Id, event: &[u8]) { let Some((deps, kind)) = decode(event) else { return; }; state.graph.insert(*id, deps); match kind { Kind::Put { key, value } => { state.puts.entry(key).or_default().insert(*id); state.values.insert(*id, value); } Kind::Lock { key } => { state.locks.insert(key); } Kind::Era { n, tag } => { state.era = state.era.max(n); state.tags.insert(n, tag); } Kind::Cut { n, heads } => { state.cut = state.cut.max(n); state.cuts.insert(n, ids(&heads).unwrap_or_default()); state.cut_events.insert(*id, n); } Kind::Junk => {} } } fn keeps(now: &State, _id: &Id, event: &[u8]) -> bool { match decode(event) { Some((_, Kind::Era { n, tag })) => { n == now.era + 1 || now.tags.get(&n).is_some_and(|took| *took == tag) } Some((_, Kind::Cut { n, heads })) => { n == now.cut + 1 || now .cuts .get(&n) .is_some_and(|took| ids(&heads).is_some_and(|heads| *took == heads)) } _ => true, } } fn checkpoint(at: &State, heads: &[Id]) -> (Vec, Vec) { let keeps: Vec = at.counting().into_values().collect(); let checkpoint = Checkpoint { name: String::new(), at: hex(heads.iter().copied()), keeps: hex(keeps.iter().copied()), era: at.era, tag: at.tags.get(&at.era).cloned().unwrap_or_default(), cut: at.cut, locks: at.locks.iter().cloned().collect(), }; let bytes = serde_json::to_vec(&checkpoint).expect("a checkpoint encodes"); (bytes, keeps) } fn parts(checkpoint: &[u8]) -> Option<(Vec, Vec)> { let checkpoint: Checkpoint = serde_json::from_slice(checkpoint).ok()?; Some((ids(&checkpoint.at)?, ids(&checkpoint.keeps)?)) } fn start(checkpoint: &[u8], kept: &[(Id, Vec)]) -> Result { let checkpoint: Checkpoint = serde_json::from_slice(checkpoint).map_err(|_| Refused::new("no checkpoint"))?; let mut state = State { at: ids(&checkpoint.at) .ok_or_else(|| Refused::new("heads not IDs"))? .into_iter() .collect(), locks: checkpoint.locks.into_iter().collect(), era: checkpoint.era, cut: checkpoint.cut, ..State::default() }; state.tags.insert(checkpoint.era, checkpoint.tag); for (id, bytes) in kept { match decode(bytes) { Some((_, Kind::Put { key, value })) => { state.graph.insert(*id, Vec::new()); state.before.insert(*id); state.puts.entry(key).or_default().insert(*id); state.values.insert(*id, value); } _ => return Err(Refused::new("a checkpoint keeps puts only")), } } Ok(state) } fn fork(at: &State, heads: &[Id], spec: &[u8]) -> Result<(Vec, Vec), Refused> { let (era, tag): (u64, String) = serde_json::from_slice(spec).map_err(|_| Refused::new("no spec"))?; let keeps: Vec = at.counting().into_values().collect(); let root = Checkpoint { name: String::new(), at: hex(heads.iter().copied()), keeps: hex(keeps.iter().copied()), era, tag, cut: 0, locks: at.locks.iter().cloned().collect(), }; let bytes = serde_json::to_vec(&root).expect("a root encodes"); Ok((bytes, keeps)) } fn moves_to(now: &State) -> Option> { let heads = now.cuts.get(&now.cut)?; (heads.iter().copied().collect::>() != now.at).then(|| heads.clone()) } fn members(_state: &State) -> Vec<(String, String)> { Vec::new() } }