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/memory.rs | 426 +++++++++++++++++++++++++++++++++++++++ src/federation/store/mod.rs | 4 + src/federation/store/testfold.rs | 373 ++++++++++++++++++++++++++++++++++ 3 files changed, 803 insertions(+) create mode 100644 src/federation/store/memory.rs create mode 100644 src/federation/store/testfold.rs 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), + /// 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, + dependencies: Vec, +} + +/// A store and what it holds, of a fold `F`. +pub(crate) struct Store { + /// The store's ID: its root's. + id: Id, + /// The checkpoint it holds, as bytes. + checkpoint: Vec, + /// The heads every event after the checkpoint builds on: the checkpoint's, or, for a + /// root, the root's own ID. + heads: BTreeSet, + /// The events the checkpoint keeps. + kept: BTreeMap>, + /// What the checkpoint and the events it keeps read as. + start: F::State, + /// The events taken after the checkpoint. + events: HashMap, + /// Those events in the order taken: each after its dependencies. + order: Vec, + /// What everything held reads as. + state: F::State, + /// Events waiting for dependencies, and, by dependency, the events waiting for it. + waiting: HashMap, + waits_for: HashMap>, + /// The events refused, and why. + refused: HashMap, +} + +impl Store { + /// A store starting from its root, with the events the root keeps. + pub(crate) fn new(root: Vec, kept: Vec>) -> Result { + 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::>())?; + 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 { + let built_on: HashSet<&Id> = self + .events + .values() + .flat_map(|event| &event.dependencies) + .collect(); + let heads: Vec = 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) -> 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 { + let mut history = HashSet::new(); + let mut todo: Vec = 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) -> 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 = 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>) -> Result>, Refused> { + let kept: BTreeMap> = kept + .into_iter() + .map(|bytes| (Id::of(&bytes), bytes)) + .collect(); + let wanted: BTreeSet<&Id> = keeps.iter().collect(); + if kept.keys().collect::>() != 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 { + 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, + 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