diff options
Diffstat (limited to 'src/federation/store/testfold.rs')
| -rw-r--r-- | src/federation/store/testfold.rs | 373 |
1 files changed, 373 insertions, 0 deletions
diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs new file mode 100644 index 0000000..4b7e1b2 --- /dev/null +++ b/src/federation/store/testfold.rs @@ -0,0 +1,373 @@ +//! 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<String>, + 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<String> }, + Junk, +} + +/// A checkpoint, a root among them. +#[derive(Serialize, Deserialize)] +struct Checkpoint { + name: String, + at: Vec<String>, + keeps: Vec<String>, + era: u64, + tag: String, + cut: u64, + locks: Vec<String>, +} + +/// An event of this fold, built on `deps`. +pub(crate) fn event(deps: &[Id], kind: Kind) -> Vec<u8> { + let mut deps: Vec<String> = 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<u8> { + event( + deps, + Kind::Put { + key: key.to_owned(), + value: value.to_owned(), + }, + ) +} + +pub(crate) fn lock(deps: &[Id], key: &str) -> Vec<u8> { + event( + deps, + Kind::Lock { + key: key.to_owned(), + }, + ) +} + +pub(crate) fn era(deps: &[Id], n: u64, tag: &str) -> Vec<u8> { + event( + deps, + Kind::Era { + n, + tag: tag.to_owned(), + }, + ) +} + +pub(crate) fn cut(deps: &[Id], n: u64, heads: &[Id]) -> Vec<u8> { + let mut heads: Vec<String> = heads.iter().map(Id::to_string).collect(); + heads.sort(); + event(deps, Kind::Cut { n, heads }) +} + +pub(crate) fn junk(deps: &[Id]) -> Vec<u8> { + event(deps, Kind::Junk) +} + +/// A root, named so that tests can tell several apart. +pub(crate) fn root(name: &str) -> Vec<u8> { + 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<u8> { + 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<Id, Vec<Id>>, + /// What the checkpoint keeps: in the history of every event after it. + before: BTreeSet<Id>, + /// The heads the checkpoint was built at. + at: BTreeSet<Id>, + puts: BTreeMap<String, BTreeSet<Id>>, + values: BTreeMap<Id, String>, + locks: BTreeSet<String>, + era: u64, + tags: BTreeMap<u64, String>, + cut: u64, + cuts: BTreeMap<u64, Vec<Id>>, +} + +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<Id> = 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<String, String> { + self.counting() + .into_iter() + .map(|(key, id)| (key, self.values[&id].clone())) + .collect() + } + + fn counting(&self) -> BTreeMap<String, Id> { + 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<String> { + &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<Id>, Kind)> { + let event: Event = serde_json::from_slice(bytes).ok()?; + let deps = event + .deps + .iter() + .map(|dep| Id::from_hex(dep)) + .collect::<Option<Vec<_>>>()?; + Some((deps, event.kind)) +} + +fn ids(texts: &[String]) -> Option<Vec<Id>> { + texts.iter().map(|text| Id::from_hex(text)).collect() +} + +fn hex(ids: impl IntoIterator<Item = Id>) -> Vec<String> { + let mut texts: Vec<String> = 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<Vec<Id>> { + 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<u8>, Vec<Id>) { + let keeps: Vec<Id> = 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<Id>, Vec<Id>)> { + let checkpoint: Checkpoint = serde_json::from_slice(checkpoint).ok()?; + Some((ids(&checkpoint.at)?, ids(&checkpoint.keeps)?)) + } + + fn start(checkpoint: &[u8], kept: &[(Id, Vec<u8>)]) -> Result<State, Refused> { + 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<u8>, Vec<Id>), Refused> { + let (era, tag): (u64, String) = + serde_json::from_slice(spec).map_err(|_| Refused::new("no spec"))?; + let mut counting: BTreeMap<String, Id> = 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<Id> = 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<Vec<Id>> { + let heads = now.cuts.get(&now.cut)?; + (heads.iter().copied().collect::<BTreeSet<_>>() != now.at).then(|| heads.clone()) + } + + fn members(_state: &State) -> Vec<(String, String)> { + Vec::new() + } +} |
