aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/store/memory.rs
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-16 16:25:03 +0000
committertv <tv@krebsco.de>2026-11-16 18:01:42 +0100
commit906d920bebafb108efc5248b36559744b6ed764e (patch)
tree9d89585fd45a97f2ff58d3a9deee808d8da0ed98 /src/federation/store/memory.rs
parent169b6b0e573ecc2a3f8e5f78d54f2e5c484a1373 (diff)
store: forks and merges
The fold makes a fork's root from the states at heads of one store, or of several, which merges them, and what makes the fork; the store gives it the states, and the events the root keeps, from the stores holding them. A node holding those heads checks a root by building it. A fork and the stores it came from take nothing of each other: what each writes after builds on what the other doesn't hold.
Diffstat (limited to 'src/federation/store/memory.rs')
-rw-r--r--src/federation/store/memory.rs87
1 files changed, 87 insertions, 0 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs
index 6d265f4..33e895d 100644
--- a/src/federation/store/memory.rs
+++ b/src/federation/store/memory.rs
@@ -113,6 +113,49 @@ impl<F: Fold> Store<F> {
})
}
+ /// 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<u8>, Vec<Vec<u8>>), 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<Id> = 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::<Result<Vec<_>, _>>()?;
+ 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
@@ -759,6 +802,50 @@ mod tests {
}
#[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<TestFold> = 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<TestFold> =
+ 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<TestFold> = 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();