From 79614926332977718956f35e1adf80ae67e219f1 Mon Sep 17 00:00:00 2001 From: tv Date: Wed, 18 Nov 2026 20:08:28 +0000 Subject: store: a stopped node leaves out none of what it holds back A store that stopped can't tell which of what it holds back will be taken, nor which of what waits: `Store::held_back` gives both, each after what it builds on. A node leaves out none of it: it puts it again where its document lacks it (`Holding::lacking`), a remake's snapshot holds it (`Holding::at_base`), and after a switch or a rejoin it puts again what of it the document it left held (`Holding::left`). A remake while nodes are stopped no longer drops what was put since the stop, nor the event they stopped at. Tested: a node keeps what it holds back, what waited among it, through a snapshot, and a store read anew from that stops there again; and a simulation: a swarm stopped at a version compacts, a node away meanwhile rejoins and one started again with nothing reads the new epoch, each stopping there, holding back what came after, until their operators have them drop that event. --- src/federation/store/memory.rs | 48 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) (limited to 'src/federation/store') diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index f721b47..8493735 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -222,6 +222,47 @@ impl Store { .map(|(id, why)| (id, why.as_str(), self.held_back.len())) } + /// What the store holds back, stopped (`Fold::stops`): the events offered since, and + /// those waiting for events it doesn't hold, as it can't tell which will be taken; each + /// after those of its dependencies among them, by ID otherwise. Nothing while it isn't + /// stopped. + pub(crate) fn held_back(&self) -> Vec<(Id, &[u8])> { + if self.stopped.is_none() { + return Vec::new(); + } + let all: BTreeMap = self + .held_back + .iter() + .map(|(id, event)| (*id, event)) + .chain(self.waiting.iter().map(|(id, event)| (*id, event))) + .collect(); + let mut placed: HashSet = HashSet::new(); + let mut ordered = Vec::new(); + for first in all.keys() { + let mut todo = vec![(*first, false)]; + while let Some((id, ready)) = todo.pop() { + if placed.contains(&id) { + continue; + } + let event = all[&id]; + if ready { + placed.insert(id); + ordered.push((id, event.bytes.as_slice())); + continue; + } + todo.push((id, true)); + todo.extend( + event + .dependencies + .iter() + .filter(|dependency| all.contains_key(dependency)) + .map(|dependency| (*dependency, false)), + ); + } + } + ordered + } + /// What a new event builds on: the events nothing else held builds on, or the /// checkpoint's heads where nothing came after it. pub(crate) fn heads(&self) -> Vec { @@ -971,10 +1012,17 @@ mod tests { assert_eq!(store.taken(), &[mark]); assert_eq!(store.refused().count(), 0); assert_eq!(store.stopped().map(|(_, _, held)| held), Some(3)); + // What it holds back, what waits among it, each after what it builds on. + let held: Vec = store.held_back().iter().map(|(id, _)| *id).collect(); + let place = |id: Id| held.iter().position(|held| *held == id); + assert_eq!(held.len(), 4); + assert!(place(at) < place(Id::of(&on))); + assert!(place(Id::of(&later)).is_some() && place(Id::of(&junk)).is_some()); assert!(store.drop_taken(&[Id::of(&later)]).is_err()); // Dropped: what it held back is taken, or refused, and what waited for it refused. assert_eq!(store.drop_taken(&[at]), Ok(vec![at])); assert!(store.stopped().is_none()); + assert!(store.held_back().is_empty()); assert_eq!(store.taken(), &[mark, Id::of(&later)]); assert!(matches!( store.refusal(&Id::of(&junk)), -- cgit v1.3.1