diff options
Diffstat (limited to 'src/federation/store/memory.rs')
| -rw-r--r-- | src/federation/store/memory.rs | 426 |
1 files changed, 426 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)]); + } +} |
