From ceddd407c434edde2a1490b912854444dcda97fe Mon Sep 17 00:00:00 2001 From: tv Date: Mon, 16 Nov 2026 16:19:03 +0000 Subject: store: a store held in memory, and a fold for its tests A store starts from its root, with the events the root keeps, and holds the events taken after it. An event offered is taken once the store holds its dependencies, where it is above the store's heads (built on an event after them, or on all of them) and the fold takes it at its history: the state its history reads as, folded from the checkpoint. An event waits for what it builds on, and is taken when that comes; one built on a refused event, or whose bytes are none of the fold's, is refused, with what waits for it. The fold made for the tests judges by history (a put refused where its key is locked), reads by what counts (a key's latest put, then the lowest ID), refuses by what a node took before (two eras of one number), and moves to checkpoints (cuts), as the federation does, so that the later stages' tests have something to exercise. --- src/federation/store/testfold.rs | 373 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 373 insertions(+) create mode 100644 src/federation/store/testfold.rs (limited to 'src/federation/store/testfold.rs') 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, + 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() + } +} -- cgit v1.3.1