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