aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/federation/store/memory.rs41
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) {