diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/federation/store/memory.rs | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index c8b5897..b8035d7 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -261,6 +261,27 @@ impl<F: Fold> Store<F> { state } + /// Of `ids`, events the store took, those not among `heads`, in their history, nor + /// above them (each with them all in its history): what a checkpoint at `heads` leaves + /// out, by the voters' rule (`docs/federation.md`, Checkpoints). + pub(crate) fn left_out<'a>( + &self, + heads: &[Id], + ids: impl IntoIterator<Item = &'a Id>, + ) -> Vec<Id> { + let covered = self.history(heads); + ids.into_iter() + .filter(|id| { + !heads.contains(id) + && !covered.contains(id) + && !heads + .iter() + .all(|head| self.history(std::slice::from_ref(id)).contains(head)) + }) + .copied() + .collect() + } + /// 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(); @@ -784,6 +805,26 @@ mod tests { assert_eq!(anew.own(), (own, drops)); } + /// Heads leave out what is neither among them, in their history, nor above them. + #[test] + fn heads_leave_out_what_is_beside_them() { + let mut store = store(); + let root = store.id(); + let first = taken(store.offer(testfold::put(&[root], "a", "1"))); + let head = taken(store.offer(testfold::put(&[first], "a", "2"))); + let beside = taken(store.offer(testfold::put(&[root], "b", "1"))); + let above = taken(store.offer(testfold::put(&[head], "c", "1"))); + assert_eq!( + store.left_out(&[head], &[first, head, beside, above]), + vec![beside] + ); + // Above one of two heads only: not above them. + assert_eq!( + store.left_out(&[head, beside], &[first, beside, above]), + vec![above] + ); + } + /// 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) { |
