aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/store/testfold.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/store/testfold.rs')
-rw-r--r--src/federation/store/testfold.rs373
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()
+ }
+}