diff options
| author | tv <tv@krebsco.de> | 2026-11-16 16:25:03 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 18:01:42 +0100 |
| commit | 906d920bebafb108efc5248b36559744b6ed764e (patch) | |
| tree | 9d89585fd45a97f2ff58d3a9deee808d8da0ed98 /src/federation/store/memory.rs | |
| parent | 169b6b0e573ecc2a3f8e5f78d54f2e5c484a1373 (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.rs | 87 |
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(); |
