diff options
| -rw-r--r-- | src/federation/store/memory.rs | 426 | ||||
| -rw-r--r-- | src/federation/store/mod.rs | 4 | ||||
| -rw-r--r-- | src/federation/store/testfold.rs | 373 |
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() + } +} |
