aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/store
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/store')
-rw-r--r--src/federation/store/memory.rs426
-rw-r--r--src/federation/store/mod.rs4
-rw-r--r--src/federation/store/testfold.rs373
3 files changed, 803 insertions, 0 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs
new file mode 100644
index 0000000..4ff5386
--- /dev/null
+++ b/src/federation/store/memory.rs
@@ -0,0 +1,426 @@
+//! A store held in memory (`docs/store.md`): a checkpoint, the events it keeps, and the
+//! events taken after it, each judged at its history.
+
+use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
+
+use super::{Fold, Id, Refused};
+
+/// Why a store doesn't take an event.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum Refusal {
+ /// Its bytes are none of the fold's events.
+ None,
+ /// The fold refuses it at its history.
+ Judged(Refused),
+ /// It builds on an event the store refuses.
+ BuiltOn(Id),
+ /// It isn't above the checkpoint's heads: it builds on what came before them, or on
+ /// nothing.
+ NotAbove,
+}
+
+/// What became of an event offered to a store.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum Offered {
+ /// Taken, with the events that waited on it, in the order taken.
+ Taken(Vec<Id>),
+ /// Held already: taken, kept by the checkpoint, or one of its heads.
+ Held,
+ /// Waiting for dependencies the store doesn't hold.
+ Waiting,
+ /// Refused, and why; what waited on it is refused with it.
+ Refused(Refusal),
+}
+
+struct Event {
+ bytes: Vec<u8>,
+ dependencies: Vec<Id>,
+}
+
+/// A store and what it holds, of a fold `F`.
+pub(crate) struct Store<F: Fold> {
+ /// The store's ID: its root's.
+ id: Id,
+ /// The checkpoint it holds, as bytes.
+ checkpoint: Vec<u8>,
+ /// The heads every event after the checkpoint builds on: the checkpoint's, or, for a
+ /// root, the root's own ID.
+ heads: BTreeSet<Id>,
+ /// The events the checkpoint keeps.
+ kept: BTreeMap<Id, Vec<u8>>,
+ /// What the checkpoint and the events it keeps read as.
+ start: F::State,
+ /// The events taken after the checkpoint.
+ events: HashMap<Id, Event>,
+ /// Those events in the order taken: each after its dependencies.
+ order: Vec<Id>,
+ /// What everything held reads as.
+ state: F::State,
+ /// Events waiting for dependencies, and, by dependency, the events waiting for it.
+ waiting: HashMap<Id, Event>,
+ waits_for: HashMap<Id, BTreeSet<Id>>,
+ /// The events refused, and why.
+ refused: HashMap<Id, Refusal>,
+}
+
+impl<F: Fold> Store<F> {
+ /// A store starting from its root, with the events the root keeps.
+ pub(crate) fn new(root: Vec<u8>, kept: Vec<Vec<u8>>) -> Result<Self, Refused> {
+ let id = Id::of(&root);
+ let (_, keeps) = F::parts(&root).ok_or_else(|| Refused::new("no checkpoint"))?;
+ let kept = matched(&keeps, kept)?;
+ let start = F::start(&root, &kept.clone().into_iter().collect::<Vec<_>>())?;
+ Ok(Self {
+ id,
+ checkpoint: root,
+ heads: BTreeSet::from([id]),
+ kept,
+ state: start.clone(),
+ start,
+ events: HashMap::new(),
+ order: Vec::new(),
+ waiting: HashMap::new(),
+ waits_for: HashMap::new(),
+ refused: HashMap::new(),
+ })
+ }
+
+ /// The store's ID: its root's.
+ pub(crate) fn id(&self) -> Id {
+ self.id
+ }
+
+ /// The checkpoint the store holds, as bytes.
+ pub(crate) fn checkpoint(&self) -> &[u8] {
+ &self.checkpoint
+ }
+
+ /// What everything the store holds reads as.
+ pub(crate) fn state(&self) -> &F::State {
+ &self.state
+ }
+
+ /// The events taken after the checkpoint, in the order taken.
+ pub(crate) fn taken(&self) -> &[Id] {
+ &self.order
+ }
+
+ /// The bytes of an event the store holds: taken, or kept by its checkpoint.
+ pub(crate) fn get(&self, id: &Id) -> Option<&[u8]> {
+ self.events
+ .get(id)
+ .map(|event| event.bytes.as_slice())
+ .or_else(|| self.kept.get(id).map(Vec::as_slice))
+ }
+
+ /// Why the store refused an event, where it did.
+ pub(crate) fn refusal(&self, id: &Id) -> Option<&Refusal> {
+ self.refused.get(id)
+ }
+
+ /// Whether an event waits for dependencies the store doesn't hold.
+ pub(crate) fn is_waiting(&self, id: &Id) -> bool {
+ self.waiting.contains_key(id)
+ }
+
+ /// What a new event builds on: the events nothing else held builds on, or the
+ /// checkpoint's heads where nothing came after it.
+ pub(crate) fn heads(&self) -> Vec<Id> {
+ let built_on: HashSet<&Id> = self
+ .events
+ .values()
+ .flat_map(|event| &event.dependencies)
+ .collect();
+ let heads: Vec<Id> = self
+ .order
+ .iter()
+ .filter(|id| !built_on.contains(id))
+ .copied()
+ .collect();
+ if heads.is_empty() {
+ self.heads.iter().copied().collect()
+ } else {
+ heads
+ }
+ }
+
+ /// Offers an event: it is taken once the store holds its dependencies, where the fold
+ /// takes it at its history.
+ pub(crate) fn offer(&mut self, bytes: Vec<u8>) -> Offered {
+ let id = Id::of(&bytes);
+ if self.events.contains_key(&id) || self.kept.contains_key(&id) || self.heads.contains(&id)
+ {
+ return Offered::Held;
+ }
+ if let Some(refusal) = self.refused.get(&id) {
+ return Offered::Refused(refusal.clone());
+ }
+ if self.waiting.contains_key(&id) {
+ return Offered::Waiting;
+ }
+ let Some(dependencies) = F::dependencies(&bytes) else {
+ return self.refuse(id, Refusal::None);
+ };
+ self.consider(
+ id,
+ Event {
+ bytes,
+ dependencies,
+ },
+ )
+ }
+
+ /// What the events of a history read as: those of `ids`, and all they build on.
+ pub(crate) fn state_at(&self, ids: &[Id]) -> F::State {
+ let history = self.history(ids);
+ let mut state = self.start.clone();
+ for id in self.order.iter().filter(|id| history.contains(id)) {
+ F::add(&mut state, id, &self.events[id].bytes);
+ }
+ state
+ }
+
+ /// The events taken after the checkpoint among `ids` and all they build on.
+ fn history(&self, ids: &[Id]) -> HashSet<Id> {
+ let mut history = HashSet::new();
+ let mut todo: Vec<Id> = ids.to_vec();
+ while let Some(id) = todo.pop() {
+ if let Some(event) = self.events.get(&id)
+ && history.insert(id)
+ {
+ todo.extend(&event.dependencies);
+ }
+ }
+ history
+ }
+
+ fn consider(&mut self, id: Id, event: Event) -> Offered {
+ let mut taken = Vec::new();
+ let mut todo = vec![(id, event)];
+ let mut first = None;
+ while let Some((id, event)) = todo.pop() {
+ let offered = self.judged(id, event, &mut taken);
+ if matches!(offered, Offered::Taken(_)) {
+ todo.extend(self.woken(&id));
+ }
+ first.get_or_insert(offered);
+ }
+ match first.expect("one event considered") {
+ Offered::Taken(_) => Offered::Taken(taken),
+ other => other,
+ }
+ }
+
+ /// The events that waited for `id` alone, now to be considered again.
+ fn woken(&mut self, id: &Id) -> Vec<(Id, Event)> {
+ let Some(waiters) = self.waits_for.remove(id) else {
+ return Vec::new();
+ };
+ let mut woken = Vec::new();
+ for waiter in waiters {
+ let still = self
+ .waits_for
+ .values()
+ .any(|waiting| waiting.contains(&waiter));
+ if !still && let Some(event) = self.waiting.remove(&waiter) {
+ woken.push((waiter, event));
+ }
+ }
+ woken
+ }
+
+ fn judged(&mut self, id: Id, event: Event, taken: &mut Vec<Id>) -> Offered {
+ if let Some(refused) = event
+ .dependencies
+ .iter()
+ .find(|dependency| self.refused.contains_key(dependency))
+ {
+ let refused = *refused;
+ return self.refuse(id, Refusal::BuiltOn(refused));
+ }
+ let before = |dependency: &Id| {
+ self.kept.contains_key(dependency) && !self.heads.contains(dependency)
+ };
+ if event.dependencies.iter().any(before) {
+ return self.refuse(id, Refusal::NotAbove);
+ }
+ let missing: Vec<Id> = event
+ .dependencies
+ .iter()
+ .filter(|dependency| {
+ !self.events.contains_key(dependency) && !self.heads.contains(dependency)
+ })
+ .copied()
+ .collect();
+ if !missing.is_empty() {
+ for dependency in missing {
+ self.waits_for.entry(dependency).or_default().insert(id);
+ }
+ self.waiting.insert(id, event);
+ return Offered::Waiting;
+ }
+ let above = event
+ .dependencies
+ .iter()
+ .any(|dependency| self.events.contains_key(dependency))
+ || self
+ .heads
+ .iter()
+ .all(|head| event.dependencies.contains(head));
+ if !above {
+ return self.refuse(id, Refusal::NotAbove);
+ }
+ let at = self.state_at(&event.dependencies);
+ if let Err(why) = F::judge(&at, &id, &event.bytes) {
+ return self.refuse(id, Refusal::Judged(why));
+ }
+ F::add(&mut self.state, &id, &event.bytes);
+ self.events.insert(id, event);
+ self.order.push(id);
+ taken.push(id);
+ Offered::Taken(vec![id])
+ }
+
+ /// Refuses an event, and what waits for it.
+ fn refuse(&mut self, id: Id, why: Refusal) -> Offered {
+ self.refused.insert(id, why.clone());
+ let mut todo = vec![id];
+ while let Some(refused) = todo.pop() {
+ for waiter in self.waits_for.remove(&refused).unwrap_or_default() {
+ if let Some(event) = self.waiting.remove(&waiter) {
+ for dependency in &event.dependencies {
+ if let Some(waiting) = self.waits_for.get_mut(dependency) {
+ waiting.remove(&waiter);
+ }
+ }
+ self.refused.insert(waiter, Refusal::BuiltOn(refused));
+ todo.push(waiter);
+ }
+ }
+ }
+ Offered::Refused(why)
+ }
+}
+
+/// The events a checkpoint keeps, by ID: each of `keeps` given once, and nothing else.
+fn matched(keeps: &[Id], kept: Vec<Vec<u8>>) -> Result<BTreeMap<Id, Vec<u8>>, Refused> {
+ let kept: BTreeMap<Id, Vec<u8>> = kept
+ .into_iter()
+ .map(|bytes| (Id::of(&bytes), bytes))
+ .collect();
+ let wanted: BTreeSet<&Id> = keeps.iter().collect();
+ if kept.keys().collect::<BTreeSet<_>>() != wanted {
+ return Err(Refused::new(
+ "the events given aren't those the checkpoint keeps",
+ ));
+ }
+ Ok(kept)
+}
+
+#[cfg(test)]
+mod tests {
+ use super::super::testfold::{self, TestFold};
+ use super::*;
+
+ fn store() -> Store<TestFold> {
+ Store::new(testfold::root("tests"), Vec::new()).expect("a root")
+ }
+
+ fn taken(offered: Offered) -> Id {
+ match offered {
+ Offered::Taken(ids) => ids[0],
+ other => panic!("not taken: {other:?}"),
+ }
+ }
+
+ #[test]
+ fn an_event_on_the_root_is_taken() {
+ let mut store = store();
+ let root = store.id();
+ let a = taken(store.offer(testfold::put(&[root], "a", "1")));
+ assert_eq!(store.heads(), vec![a]);
+ assert_eq!(store.state().counts()["a"], "1");
+ assert_eq!(store.offer(testfold::put(&[root], "a", "1")), Offered::Held);
+ }
+
+ #[test]
+ fn what_is_none_or_on_nothing_is_refused() {
+ let mut store = store();
+ assert_eq!(
+ store.offer(b"not an event".to_vec()),
+ Offered::Refused(Refusal::None)
+ );
+ assert_eq!(
+ store.offer(testfold::put(&[], "a", "1")),
+ Offered::Refused(Refusal::NotAbove)
+ );
+ let root = store.id();
+ assert!(matches!(
+ store.offer(testfold::junk(&[root])),
+ Offered::Refused(Refusal::Judged(_))
+ ));
+ }
+
+ #[test]
+ fn an_event_waits_for_what_it_builds_on() {
+ let mut store = store();
+ let root = store.id();
+ let first = testfold::put(&[root], "a", "1");
+ let a = Id::of(&first);
+ let second = testfold::put(&[a], "a", "2");
+ let b = Id::of(&second);
+ assert_eq!(store.offer(second), Offered::Waiting);
+ assert!(store.is_waiting(&b));
+ assert_eq!(store.offer(first), Offered::Taken(vec![a, b]));
+ assert_eq!(store.taken(), &[a, b]);
+ assert_eq!(store.state().counts()["a"], "2");
+ }
+
+ #[test]
+ fn what_builds_on_a_refused_event_is_refused() {
+ let mut store = store();
+ let root = store.id();
+ let bad = testfold::junk(&[root]);
+ let junk = Id::of(&bad);
+ let waiting = testfold::put(&[junk], "a", "1");
+ let waiter = Id::of(&waiting);
+ assert_eq!(store.offer(waiting), Offered::Waiting);
+ assert!(matches!(store.offer(bad), Offered::Refused(_)));
+ assert_eq!(store.refusal(&waiter), Some(&Refusal::BuiltOn(junk)));
+ assert_eq!(
+ store.offer(testfold::put(&[junk], "b", "1")),
+ Offered::Refused(Refusal::BuiltOn(junk))
+ );
+ }
+
+ #[test]
+ fn an_event_is_judged_at_its_history() {
+ let mut store = store();
+ let root = store.id();
+ let locked = taken(store.offer(testfold::lock(&[root], "a")));
+ // Built on the lock: refused there.
+ assert!(matches!(
+ store.offer(testfold::put(&[locked], "a", "1")),
+ Offered::Refused(Refusal::Judged(_))
+ ));
+ // Written beside it: taken, as nothing was locked at its history.
+ let beside = taken(store.offer(testfold::put(&[root], "a", "2")));
+ assert_eq!(store.state().counts()["a"], "2");
+ assert!(store.state_at(&[beside]).locks().is_empty());
+ assert!(store.state().locks().contains("a"));
+ }
+
+ #[test]
+ fn an_event_waits_until_all_it_builds_on_is_held() {
+ let mut store = store();
+ let root = store.id();
+ let one = testfold::put(&[root], "a", "1");
+ let two = testfold::put(&[root], "b", "1");
+ let both = testfold::put(&[Id::of(&one), Id::of(&two)], "c", "1");
+ assert_eq!(store.offer(both.clone()), Offered::Waiting);
+ assert!(matches!(store.offer(one), Offered::Taken(ids) if ids.len() == 1));
+ assert!(store.is_waiting(&Id::of(&both)));
+ assert!(matches!(store.offer(two), Offered::Taken(ids) if ids.len() == 2));
+ assert_eq!(store.heads(), vec![Id::of(&both)]);
+ }
+}
diff --git a/src/federation/store/mod.rs b/src/federation/store/mod.rs
index da05b4b..73ed029 100644
--- a/src/federation/store/mod.rs
+++ b/src/federation/store/mod.rs
@@ -8,6 +8,10 @@ use sha2::{Digest, Sha256};
use crate::transport::Hex;
+pub(crate) mod memory;
+#[cfg(test)]
+pub(crate) mod testfold;
+
/// An event's name: the SHA-256 of its bytes, written as 64 lower-case hex digits.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) struct Id(pub(crate) [u8; 32]);
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()
+ }
+}