//! 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`; 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, cuts: BTreeMap>, } impl State { /// Whether `b` is in the history of `a`. pub(crate) fn built_on(&self, a: &Id, b: &Id) -> bool { if self.before.contains(b) { return !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)) } /// Whether `heads` may be a checkpoint's here, and the state is above them. fn above(&self, heads: &[Id]) -> bool { let after = |id: &Id| self.graph.contains_key(id) && !self.before.contains(id); if heads.is_empty() || !heads.iter().all(after) { return false; } if heads.windows(2).any(|pair| pair[0] >= pair[1]) { return false; } let beside = |a: &Id, b: &Id| a != b && self.built_on(a, b); if heads.iter().any(|a| heads.iter().any(|b| beside(a, b))) { return false; } self.graph.keys().filter(|id| after(id)).all(|id| { heads.contains(id) || heads.iter().any(|head| self.built_on(head, id)) || heads.iter().all(|head| self.built_on(id, 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; fn dependencies(event: &[u8]) -> Option> { decode(event).map(|(deps, _)| deps) } fn judge(at: &State, _id: &Id, event: &[u8]) -> Result<(), Refused> { let (_, 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.above(&heads) { Err(Refused::new("not above its heads")) } 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()); } 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 mut counting: BTreeMap = BTreeMap::new(); let mut locks = BTreeSet::new(); for state in at { for (key, id) in state.counting() { let lowest = counting.entry(key).or_insert(id); *lowest = (*lowest).min(id); } locks.extend(state.locks.iter().cloned()); } let keeps: Vec = 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: locks.into_iter().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() } }