diff options
| -rw-r--r-- | src/federation/store/memory.rs | 236 | ||||
| -rw-r--r-- | src/federation/store/testfold.rs | 7 |
2 files changed, 235 insertions, 8 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index 85fac7f..6d265f4 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -65,19 +65,42 @@ pub(crate) struct Store<F: Fold> { waits_for: HashMap<Id, BTreeSet<Id>>, /// The events refused, and why. refused: HashMap<Id, Refusal>, + /// 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<Id>, } impl<F: Fold> Store<F> { - /// A store starting from its root, with the events the root keeps. + /// 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<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"))?; + 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<u8>, kept: Vec<Vec<u8>>) -> Result<Self, Refused> { + 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<u8>, + heads: BTreeSet<Id>, + kept: Vec<Vec<u8>>, + ) -> Result<Self, Refused> { + let (_, keeps) = F::parts(&checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?; let kept = matched(&keeps, kept)?; - let start = F::start(&root, &kept.clone().into_iter().collect::<Vec<_>>())?; + let start = F::start(&checkpoint, &kept.clone().into_iter().collect::<Vec<_>>())?; Ok(Self { id, - checkpoint: root, - heads: BTreeSet::from([id]), + checkpoint, + heads, kept, state: start.clone(), start, @@ -86,6 +109,7 @@ impl<F: Fold> Store<F> { waiting: HashMap::new(), waits_for: HashMap::new(), refused: HashMap::new(), + forgotten: HashSet::new(), }) } @@ -99,6 +123,11 @@ impl<F: Fold> Store<F> { &self.checkpoint } + /// The events the checkpoint keeps, as bytes, in the order of their IDs. + pub(crate) fn kept(&self) -> Vec<Vec<u8>> { + self.kept.values().cloned().collect() + } + /// What everything the store holds reads as. pub(crate) fn state(&self) -> &F::State { &self.state @@ -152,7 +181,10 @@ impl<F: Fold> Store<F> { /// 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) + if self.events.contains_key(&id) + || self.kept.contains_key(&id) + || self.heads.contains(&id) + || self.forgotten.contains(&id) { return Offered::Held; } @@ -209,12 +241,118 @@ impl<F: Fold> Store<F> { } 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<Id> = 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<Id> = 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::<Option<Vec<_>>>() + else { + return false; + }; + let Ok(kept) = matched(&keeps, kept) else { + return false; + }; + let Ok(start) = F::start(&checkpoint, &kept.clone().into_iter().collect::<Vec<_>>()) else { + return false; + }; + let before = self.history(&ids); + let mut above: HashSet<Id> = 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<Id> = 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 { @@ -243,7 +381,8 @@ impl<F: Fold> Store<F> { return self.refuse(id, Refusal::BuiltOn(refused)); } let before = |dependency: &Id| { - self.kept.contains_key(dependency) && !self.heads.contains(dependency) + (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); @@ -536,6 +675,89 @@ mod tests { 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<TestFold>, 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) + ); + 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"))); + 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!(!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<TestFold> = + 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::<TestFold>::pinned(store.id(), store.checkpoint().to_vec(), Vec::new()).is_err() + ); + } + #[test] fn an_event_waits_until_all_it_builds_on_is_held() { let mut store = store(); diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs index 4b7e1b2..68397e7 100644 --- a/src/federation/store/testfold.rs +++ b/src/federation/store/testfold.rs @@ -176,7 +176,12 @@ impl State { /// Whether `heads` may be a checkpoint's here, and the state is above them. fn above(&self, heads: &[Id]) -> bool { - let after = |id: &Id| self.graph.contains_key(id) && !self.before.contains(id); + // The heads of the checkpoint the state starts from count as after the checkpoint + // current at them, so that a node starting from it judges the cut naming it as + // every node does. + let after = |id: &Id| { + (self.graph.contains_key(id) && !self.before.contains(id)) || self.at.contains(id) + }; if heads.is_empty() || !heads.iter().all(after) { return false; } |
