diff options
| author | tv <tv@krebsco.de> | 2026-11-16 16:19:03 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 18:01:29 +0100 |
| commit | ceddd407c434edde2a1490b912854444dcda97fe (patch) | |
| tree | 7133190c796549d7d178b6cedfce375b15d9c852 /src/federation/store/memory.rs | |
| parent | 7bb467a013a9146620b633e3c3cdd21e3a48f80f (diff) | |
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.
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)]); + } +} |
