//! 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, /// Its history takes it, but the node doesn't, by what it took before. Own, /// Its operator had the node drop it. Dropped, } /// 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)); } if !F::keeps(&self.state, &id, &event.bytes) { return self.refuse(id, Refusal::Own); } F::add(&mut self.state, &id, &event.bytes); self.events.insert(id, event); self.order.push(id); taken.push(id); Offered::Taken(vec![id]) } /// The events refused, and why: for reports. pub(crate) fn refused(&self) -> impl Iterator { self.refused.iter() } /// Drops events taken after the checkpoint, with everything built on them, as their /// operator has the node do: it refuses them from then on, until its operator allows /// them again. What the checkpoint keeps, or holds by ID, it drops not: every event /// after it builds on that. Returns what it dropped, in the order taken. pub(crate) fn drop_taken(&mut self, ids: &[Id]) -> Result, Refused> { if let Some(id) = ids.iter().find(|id| !self.events.contains_key(id)) { return Err(Refused::new(format!( "{id} isn't an event taken after the checkpoint" ))); } let mut dropped: HashMap = ids.iter().map(|id| (*id, Refusal::Dropped)).collect(); for id in &self.order { if dropped.contains_key(id) { continue; } if let Some(on) = self.events[id] .dependencies .iter() .find(|dependency| dropped.contains_key(dependency)) { let on = *on; dropped.insert(*id, Refusal::BuiltOn(on)); } } let order: Vec = self .order .iter() .filter(|id| dropped.contains_key(id)) .copied() .collect(); self.order.retain(|id| !dropped.contains_key(id)); for id in &order { self.events.remove(id); } self.refused.extend(dropped); let mut state = self.start.clone(); for id in &self.order { F::add(&mut state, id, &self.events[id].bytes); } self.state = state; Ok(order) } /// Takes back what the node refused of its own, or dropped, as its operator says /// otherwise: `ids`, and what was refused for being built on them. They are taken when /// offered again, where the store takes them then. pub(crate) fn allow(&mut self, ids: &[Id]) { let mut todo: Vec = ids .iter() .filter(|id| matches!(self.refused.get(id), Some(Refusal::Own | Refusal::Dropped))) .copied() .collect(); while let Some(id) = todo.pop() { self.refused.remove(&id); todo.extend( self.refused .iter() .filter(|(_, why)| **why == Refusal::BuiltOn(id)) .map(|(waiter, _)| *waiter), ); } } /// 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 a_node_keeps_the_first_of_two_eras_of_one_number() { let mut store = store(); let root = store.id(); let one = taken(store.offer(testfold::era(&[root], 1, "one"))); let other = testfold::era(&[root], 1, "other"); let beside = Id::of(&other); assert_eq!(store.offer(other.clone()), Offered::Refused(Refusal::Own)); assert_eq!( store.offer(testfold::put(&[beside], "a", "1")), Offered::Refused(Refusal::BuiltOn(beside)) ); // The same era written again, at another history before it, is one the node // took; at a history after it, it is no era there. let elsewhere = taken(store.offer(testfold::put(&[root], "b", "1"))); assert!(matches!( store.offer(testfold::era(&[elsewhere], 1, "one")), Offered::Taken(_) )); assert!(matches!( store.offer(testfold::era(&[one], 1, "one")), Offered::Refused(Refusal::Judged(_)) )); assert_eq!(store.state().era(), (1, Some(&"one".to_owned()))); } #[test] fn an_operator_drops_what_its_node_took_and_takes_the_other() { let mut store = store(); let root = store.id(); let one = taken(store.offer(testfold::era(&[root], 1, "one"))); let on = taken(store.offer(testfold::put(&[one], "a", "1"))); let unrelated = taken(store.offer(testfold::put(&[root], "b", "1"))); let other = testfold::era(&[root], 1, "other"); let beside = Id::of(&other); assert_eq!(store.offer(other.clone()), Offered::Refused(Refusal::Own)); assert_eq!(store.drop_taken(&[one]), Ok(vec![one, on])); assert_eq!(store.taken(), &[unrelated]); assert_eq!(store.state().era(), (0, Some(&String::new()))); assert_eq!(store.refusal(&on), Some(&Refusal::BuiltOn(one))); store.allow(&[beside]); assert_eq!(store.offer(other), Offered::Taken(vec![beside])); assert_eq!(store.state().era(), (1, Some(&"other".to_owned()))); assert_eq!( store.offer(testfold::era(&[root], 1, "one")), Offered::Refused(Refusal::Dropped) ); assert!(store.drop_taken(&[root]).is_err()); } #[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)]); } }