aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation')
-rw-r--r--src/federation/held.rs102
-rw-r--r--src/federation/store/memory.rs48
2 files changed, 143 insertions, 7 deletions
diff --git a/src/federation/held.rs b/src/federation/held.rs
index 5155573..66f20e9 100644
--- a/src/federation/held.rs
+++ b/src/federation/held.rs
@@ -156,7 +156,8 @@ struct Inner {
pub(crate) struct AtBase {
/// The checkpoint the store reaches there, where it isn't the root.
pub(crate) checkpoint: Option<Vec<u8>>,
- /// The root, the events that checkpoint keeps, and those after it, by ID.
+ /// The root, the events that checkpoint keeps, and those after it, by ID: those it
+ /// holds back too, where it stops there.
pub(crate) events: BTreeMap<Id, Vec<u8>>,
/// The members there, by node ID.
pub(crate) members: BTreeSet<String>,
@@ -473,7 +474,8 @@ impl Holding {
/// The events the node has that `doc` lacks, each after its dependencies: of the
/// document it left, what a store starting at `doc`'s checkpoint takes (`left`); then
- /// what its store's checkpoint keeps, then what it took after it.
+ /// what its store's checkpoint keeps, then what it took after it, then what it holds
+ /// back, stopped (`Store::held_back`).
pub(crate) fn lacking(&self, doc: &impl ReadDoc) -> Vec<(Id, Vec<u8>)> {
let mut held: HashSet<Id> = events::ids(doc).into_iter().collect();
let mut inner = self.inner.lock_or_recover();
@@ -490,6 +492,12 @@ impl Holding {
.taken()
.iter()
.filter_map(|id| Some((*id, store.get(id)?.to_vec()))),
+ )
+ .chain(
+ store
+ .held_back()
+ .into_iter()
+ .map(|(id, bytes)| (id, bytes.to_vec())),
),
);
}
@@ -570,9 +578,10 @@ impl Holding {
/// What `left`, the document the node left at a switch or a rejoin, holds that a store
/// starting at `doc`'s checkpoint takes, by the node's own refusals and its operator's
- /// drops, and `doc` lacks (`docs/store.md`, Remakes): kept, to put again (`lacking`).
- /// So what the node held beyond the base goes again, and, where it moved to a later
- /// checkpoint since, what a store starting at the snapshot's takes to reach it.
+ /// drops, or holds back, stopped, and `doc` lacks (`docs/store.md`, Remakes): kept, to
+ /// put again (`lacking`). So what the node held beyond the base goes again, and, where
+ /// it moved to a later checkpoint since, what a store starting at the snapshot's takes
+ /// to reach it.
pub(crate) fn left(&self, doc: &impl ReadDoc, left: &impl ReadDoc) {
let reading = Holding {
pin: self.pin,
@@ -602,6 +611,13 @@ impl Holding {
);
}
}
+ put.extend(
+ store
+ .held_back()
+ .into_iter()
+ .filter(|(id, _)| events.contains_key(id))
+ .map(|(id, bytes)| (id, bytes.to_vec())),
+ );
}
if !put.is_empty() {
info!(
@@ -854,8 +870,9 @@ impl Holding {
/// What a remake's snapshot holds of the store: as this node reads it anew from
/// `base`, the document at the remake's base, by its own refusals and its operator's
- /// drops, as it reads its document whenever it starts. None where `base` holds no
- /// store, or none this node reads there.
+ /// drops, as it reads its document whenever it starts; and what it holds back there,
+ /// where it stops (`Store::held_back`). None where `base` holds no store, or none this
+ /// node reads there.
pub(crate) fn at_base(&self, base: &impl ReadDoc) -> Option<AtBase> {
let reading = Holding {
pin: self.pin,
@@ -880,6 +897,10 @@ impl Holding {
events.insert(*id, bytes.to_vec());
}
}
+ // Stopped, what it can't judge it doesn't leave out.
+ for (id, bytes) in store.held_back() {
+ events.insert(id, bytes.to_vec());
+ }
events.insert(swarm, root);
AtBase {
checkpoint: (Id::of(checkpoint) != swarm).then(|| checkpoint.to_vec()),
@@ -1804,6 +1825,73 @@ mod tests {
assert!(holding.with(|_| ()).is_none());
}
+ /// A node whose store stopped leaves out none of what it holds back, as it can't tell
+ /// which will be taken: what waited when it stopped among it, it puts again where its
+ /// document lacks it, each after what it builds on, and a remake's snapshot holds it, so
+ /// that a store read anew from that stops there again.
+ #[test]
+ fn a_node_that_stopped_keeps_what_it_holds_back_through_a_remake() {
+ let (tv, lass, makefu) = (
+ Party::new("tv", 1),
+ Party::new("lass", 2),
+ Party::new("makefu", 3),
+ );
+ let first = Spec::first(&[&tv, &lass, &makefu], &[]);
+ let root = first.root();
+ let on = first.hash();
+ let mut none = first.after(on);
+ none.rules
+ .push(("_continuum/x".to_owned(), harness::str("tv")));
+ let proposal = tv.propose(&[Id::of(&root)], &none.json());
+ let votes =
+ [&tv, &lass].map(|party| party.vote(&[Id::of(&proposal)], on, none.hash(), true));
+ let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], none.hash());
+ let after = tv.write(&[Id::of(&written)], "home/tv/a", harness::str("1"));
+ let beside = lass.write(&[Id::of(&votes[1])], "home/lass/b", harness::str("2"));
+ let on_beside = makefu.write(&[Id::of(&beside)], "home/makefu/c", harness::str("3"));
+ let mut doc = events::started(Federation::NAME, &root, &[]).unwrap();
+ for event in [&proposal].into_iter().chain(&votes) {
+ put(&mut doc, event);
+ }
+ let holding = Holding::default();
+ read(&holding, &doc, 0);
+ // Waiting for what it builds on when the store stops; that one comes after.
+ assert_eq!(holding.offer(on_beside.clone()), Some(Offered::Waiting));
+ put(&mut doc, &written);
+ put(&mut doc, &after);
+ read(&holding, &doc, 0);
+ assert_eq!(holding.offer(beside.clone()), Some(Offered::Stopped));
+ let lacking: Vec<Id> = holding
+ .lacking(&doc)
+ .into_iter()
+ .map(|(id, _)| id)
+ .collect();
+ assert_eq!(lacking, vec![Id::of(&beside), Id::of(&on_beside)]);
+
+ put(&mut doc, &on_beside);
+ put(&mut doc, &beside);
+ let snapshot = snapshot(&doc, &holding);
+ let held = events::ids(&snapshot);
+ for kept in [&written, &after, &beside, &on_beside] {
+ assert!(held.contains(&Id::of(kept)));
+ }
+ let anew = Holding::default();
+ read(&anew, &snapshot, 1);
+ assert_eq!(
+ anew.with(|store| store.stopped().map(|(id, ..)| *id)),
+ Some(Some(Id::of(&written)))
+ );
+ anew.drop_taken(&[Id::of(&written)]).unwrap().unwrap();
+ assert_eq!(
+ anew.with(|store| {
+ store.holds(&Id::of(&beside))
+ && store.holds(&Id::of(&on_beside))
+ && !store.holds(&Id::of(&after))
+ }),
+ Some(true)
+ );
+ }
+
/// A node voting by itself whose store stopped casts nothing, by itself or by hand:
/// what it reads is behind what passed.
#[test]
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<F: Fold> Store<F> {
.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<Id, &Event> = self
+ .held_back
+ .iter()
+ .map(|(id, event)| (*id, event))
+ .chain(self.waiting.iter().map(|(id, event)| (*id, event)))
+ .collect();
+ let mut placed: HashSet<Id> = 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<Id> {
@@ -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<Id> = 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)),