//! 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, /// What a move to a checkpoint forgot that came before its heads: held as accounted /// for, and nothing after the checkpoint builds on it. forgotten: HashSet, } impl Store { /// A store starting from its root, with the events the root keeps: its events build /// on the root itself. pub(crate) fn new(root: Vec, kept: Vec>) -> Result { let id = Id::of(&root); Self::starting(id, root, BTreeSet::from([id]), kept) } /// A store of ID `id` starting from a checkpoint its operator pins, with the events it /// keeps: its events build on the heads it was built at. pub(crate) fn pinned(id: Id, checkpoint: Vec, kept: Vec>) -> Result { let (at, _) = F::parts(&checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?; if at.is_empty() { return Err(Refused::new("a checkpoint without heads is a root")); } Self::starting(id, checkpoint, at.into_iter().collect(), kept) } fn starting( id: Id, checkpoint: Vec, heads: BTreeSet, kept: Vec>, ) -> Result { let (_, keeps) = F::parts(&checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?; let kept = matched(&keeps, kept)?; let start = F::start(&checkpoint, &kept.clone().into_iter().collect::>())?; Ok(Self { id, checkpoint, heads, kept, state: start.clone(), start, events: HashMap::new(), order: Vec::new(), waiting: HashMap::new(), waits_for: HashMap::new(), refused: HashMap::new(), forgotten: HashSet::new(), }) } /// The root of a fork at heads of one store or of several, each given with its heads, /// made by `spec`: its bytes, and those of the events it keeps. A fork at heads of /// several stores merges them. pub(crate) fn fork( sides: &[(&Self, &[Id])], spec: &[u8], ) -> Result<(Vec, Vec>), Refused> { let mut states = Vec::new(); let mut heads = BTreeSet::new(); for (store, at) in sides { if let Some(head) = at.iter().find(|head| !store.holds(head)) { return Err(Refused::new(format!("{head} isn't held there"))); } states.push(store.state_at(at)); heads.extend(at.iter().copied()); } let heads: Vec = heads.into_iter().collect(); let states: Vec<&F::State> = states.iter().collect(); let (root, keeps) = F::fork(&states, &heads, spec)?; let kept = keeps .iter() .map(|id| { sides .iter() .find_map(|(store, _)| store.get(id)) .map(<[u8]>::to_vec) .ok_or_else(|| Refused::new(format!("{id} isn't held"))) }) .collect::, _>>()?; Ok((root, kept)) } /// Whether `root` is the root of the fork at those heads, made by `spec`, as a node /// holding them builds it. pub(crate) fn checks_fork(sides: &[(&Self, &[Id])], spec: &[u8], root: &[u8]) -> bool { Self::fork(sides, spec).is_ok_and(|(built, _)| built == root) } /// Whether the store holds an event: taken after its checkpoint, or one of its heads. pub(crate) fn holds(&self, id: &Id) -> bool { self.events.contains_key(id) || self.heads.contains(id) } /// 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 } /// The events the checkpoint keeps, as bytes, in the order of their IDs. pub(crate) fn kept(&self) -> Vec> { self.kept.values().cloned().collect() } /// 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) || self.forgotten.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); } if !taken.is_empty() { while self.moved() {} } match first.expect("one event considered") { Offered::Taken(_) => Offered::Taken(taken), other => other, } } /// Moves to the checkpoint the fold names, where it names a later one: builds it at its /// heads, forgets what came before them but what it keeps, and every event not above /// them, refusing those from then on. Whether it moved. fn moved(&mut self) -> bool { let Some(named) = F::moves_to(&self.state) else { return false; }; let heads: BTreeSet = named.into_iter().collect(); if heads == self.heads || heads.is_empty() || !heads.iter().all(|head| self.events.contains_key(head)) { return false; } let beside = heads.iter().any(|head| { let history = self.history(&self.events[head].dependencies); heads.iter().any(|other| history.contains(other)) }); if beside { return false; } let ids: Vec = heads.iter().copied().collect(); let at = self.state_at(&ids); let (checkpoint, keeps) = F::checkpoint(&at, &ids); let Some(kept) = keeps .iter() .map(|id| self.get(id).map(<[u8]>::to_vec)) .collect::>>() else { return false; }; let Ok(kept) = matched(&keeps, kept) else { return false; }; let Ok(start) = F::start(&checkpoint, &kept.clone().into_iter().collect::>()) else { return false; }; let before = self.history(&ids); let mut above: HashSet = HashSet::new(); for id in self.order.iter().filter(|id| !before.contains(id)) { let dependencies = &self.events[id].dependencies; let on = dependencies .iter() .all(|dependency| heads.contains(dependency) || above.contains(dependency)); let holds = dependencies .iter() .any(|dependency| above.contains(dependency)) || heads.iter().all(|head| dependencies.contains(head)); if on && holds { above.insert(*id); } } for id in &self.order { if before.contains(id) { if !kept.contains_key(id) && !heads.contains(id) { self.forgotten.insert(*id); } } else if !above.contains(id) { self.refused.insert(*id, Refusal::NotAbove); } } let old = std::mem::replace(&mut self.heads, heads); self.forgotten .extend(old.into_iter().filter(|head| !self.heads.contains(head))); self.forgotten.extend( self.kept .keys() .filter(|id| !kept.contains_key(id)) .copied(), ); self.checkpoint = checkpoint; self.kept = kept; self.order.retain(|id| above.contains(id)); self.events.retain(|id, _| above.contains(id)); let mut state = start.clone(); for id in &self.order { F::add(&mut state, id, &self.events[id].bytes); } self.start = start; self.state = state; let stale: Vec = self .waiting .iter() .filter(|(_, event)| { event.dependencies.iter().any(|dependency| { self.forgotten.contains(dependency) || self.refused.contains_key(dependency) }) }) .map(|(id, _)| *id) .collect(); for id in stale { if let Some(event) = self.waiting.remove(&id) { for dependency in &event.dependencies { if let Some(waiting) = self.waits_for.get_mut(dependency) { waiting.remove(&id); } } } self.refuse(id, Refusal::NotAbove); } true } /// 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.forgotten.contains(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()); } /// A store whose root holds puts and a lock, cut at the lock: the cut's ID, the lock's, /// and the first put's, which the checkpoint forgets. fn cut_at_a_lock() -> (Store, Id, Id, Id) { let mut store = store(); let root = store.id(); let first = taken(store.offer(testfold::put(&[root], "a", "1"))); let second = taken(store.offer(testfold::put(&[first], "a", "2"))); let lock = taken(store.offer(testfold::lock(&[second], "b"))); let cut = taken(store.offer(testfold::cut(&[lock], 1, &[lock]))); (store, cut, lock, first) } #[test] fn a_cut_moves_the_store_to_a_checkpoint() { let (mut store, cut, lock, first) = cut_at_a_lock(); assert_eq!( TestFold::parts(store.checkpoint()).map(|(at, _)| at), Some(vec![lock]) ); assert_eq!(store.taken(), &[cut]); assert_eq!(store.kept().len(), 1); assert_eq!(store.state().counts()["a"], "2"); assert!(store.state().locks().contains("b")); // After it: taken. On what it forgot, or the root: not above its heads. assert!(matches!( store.offer(testfold::put(&[cut], "a", "3")), Offered::Taken(_) )); assert_eq!(store.state().counts()["a"], "3"); assert_eq!( store.offer(testfold::put(&[first], "c", "1")), Offered::Refused(Refusal::NotAbove) ); // On its heads, but naming what came before them too: not above them. let second = Id::of(&testfold::put(&[first], "a", "2")); assert_eq!( store.offer(testfold::put(&[lock, second], "c", "1")), Offered::Refused(Refusal::NotAbove) ); let root = store.id(); assert_eq!( store.offer(testfold::put(&[root], "c", "1")), Offered::Refused(Refusal::NotAbove) ); // A head brought again is held; so is what came before it. assert_eq!( store.offer(testfold::lock( &[Id::of(&testfold::put(&[first], "a", "2"))], "b" )), Offered::Held ); assert_eq!(store.offer(testfold::put(&[root], "a", "1")), Offered::Held); } #[test] fn what_was_taken_beside_the_heads_is_refused_by_the_move() { let mut store = store(); let root = store.id(); let here = taken(store.offer(testfold::put(&[root], "a", "1"))); let beside = taken(store.offer(testfold::put(&[root], "b", "1"))); let on_beside = taken(store.offer(testfold::put(&[beside], "c", "1"))); // Built on the heads, but naming the root as well. let naming = taken(store.offer(testfold::put(&[here, root], "d", "1"))); let cut = taken(store.offer(testfold::cut(&[here], 1, &[here]))); assert_eq!(store.taken(), &[cut]); assert_eq!(store.refusal(&beside), Some(&Refusal::NotAbove)); assert_eq!(store.refusal(&on_beside), Some(&Refusal::NotAbove)); assert_eq!(store.refusal(&naming), Some(&Refusal::NotAbove)); assert!(!store.state().counts().contains_key("b")); } #[test] fn a_node_starts_from_a_pinned_checkpoint() { let (mut store, cut, _, _) = cut_at_a_lock(); let later = testfold::put(&[cut], "c", "1"); assert!(matches!(store.offer(later.clone()), Offered::Taken(_))); let mut pinned: Store = Store::pinned(store.id(), store.checkpoint().to_vec(), store.kept()).expect("pinned"); assert_eq!(pinned.offer(later.clone()), Offered::Waiting); let cut_bytes = store.get(&cut).expect("held").to_vec(); assert_eq!( pinned.offer(cut_bytes), Offered::Taken(vec![cut, Id::of(&later)]) ); assert_eq!(pinned.state().counts(), store.state().counts()); assert_eq!(pinned.checkpoint(), store.checkpoint()); assert!( Store::::pinned(store.id(), store.checkpoint().to_vec(), Vec::new()).is_err() ); } #[test] fn a_fork_and_the_store_it_left_take_nothing_of_each_other() { let mut store = store(); let root = store.id(); let here = taken(store.offer(testfold::put(&[root], "a", "1"))); let spec = testfold::fork_spec(1, "fork"); let (fork_root, kept) = Store::fork(&[(&store, &[here])], &spec).expect("a fork"); let mut fork: Store = Store::new(fork_root.clone(), kept).expect("its root"); assert!(Store::checks_fork(&[(&store, &[here])], &spec, &fork_root)); assert!(!Store::checks_fork( &[(&store, &[here])], &testfold::fork_spec(2, "fork"), &fork_root )); assert_eq!(fork.state().counts()["a"], "1"); assert_eq!(fork.state().era(), (1, Some(&"fork".to_owned()))); let stayed = testfold::put(&[here], "a", "2"); let went = testfold::put(&[fork.id()], "a", "3"); assert!(matches!(store.offer(stayed.clone()), Offered::Taken(_))); assert_eq!(store.offer(went.clone()), Offered::Waiting); assert!(matches!(fork.offer(went), Offered::Taken(_))); assert_eq!(fork.offer(stayed), Offered::Waiting); assert_eq!(fork.state().counts()["a"], "3"); assert_eq!(store.state().counts()["a"], "2"); } #[test] fn a_merge_keeps_each_sides_values_the_lower_id_across() { let mut left = store(); let mut right: Store = Store::new(testfold::root("other"), Vec::new()).expect("a root"); let l = taken(left.offer(testfold::put(&[left.id()], "a", "left"))); let only = taken(left.offer(testfold::put(&[l], "b", "left"))); let r = taken(right.offer(testfold::put(&[right.id()], "a", "right"))); let spec = testfold::fork_spec(1, "merge"); let (merge_root, kept) = Store::fork(&[(&left, &[only]), (&right, &[r])], &spec).expect("a merge"); let merged: Store = Store::new(merge_root, kept).expect("its root"); let lower = if l < r { "left" } else { "right" }; assert_eq!(merged.state().counts()["a"], lower); assert_eq!(merged.state().counts()["b"], "left"); assert!(Store::fork(&[(&left, &[r])], &spec).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)]); } }