From c64fcc05d8c53bee99ab039bd709039afb730cdd Mon Sep 17 00:00:00 2001 From: tv Date: Wed, 18 Nov 2026 18:49:50 +0000 Subject: federation: a node stops at a version it doesn't read A version event writing a proposal passed on the version a node reads, which doesn't read as a version there (of a later federation, using what a later continuum takes, or none at all), the node can't judge: `Fold::stops`. The store stops at it: it takes nothing and refuses nothing from then on, holding back whatever comes, that event first (`Offered::Stopped`), and keeps none of it across a restart, where it stops there again. One beside the version the node reads is refused of its own, as any other. Its operator has it drop that event (`POST /admin/events/drop`), or one it builds on: it is refused as dropped, or as built on what was, any version event writing that version with it, kept in the store file; the node judges what it held back and goes on under the version before. Allowed again, it stops there once more. The node logs the stop and its end; `GET /events` names the event, why, and how many it holds back (`stopped`); a put answers `stopped`, written into the document all the same; a node voting by itself casts nothing while stopped. The test fold's eras tagged `new` stop a store. Row 39 is tested (`federation_attack_39`); of rows 9, 10 and 48, a node stops at the version event. --- src/api/events.rs | 18 ++-- src/federation/attacks.rs | 17 +++- src/federation/fold.rs | 21 ++++- src/federation/held.rs | 195 ++++++++++++++++++++++++++++++++++++++- src/federation/properties.rs | 2 + src/federation/store/memory.rs | 189 +++++++++++++++++++++++++++++++++---- src/federation/store/mod.rs | 10 +- src/federation/store/testfold.rs | 12 ++- 8 files changed, 427 insertions(+), 37 deletions(-) (limited to 'src') diff --git a/src/api/events.rs b/src/api/events.rs index 04dc77e..bd6db70 100644 --- a/src/api/events.rs +++ b/src/api/events.rs @@ -81,16 +81,21 @@ fn why(refusal: &Refusal) -> String { } /// `GET /events`: the store's ID, its checkpoint's, its heads, how many events it took -/// after its checkpoint, the node's party, and whether the node votes for it by itself. +/// after its checkpoint, the event it stopped at, if any, the node's party, and whether +/// the node votes for it by itself. async fn summary(State(state): State) -> Response { let party = state.holding.party().map(str::to_owned); let votes = state.holding.votes_by_itself(); with_store(&state, |store| { + let stopped = store + .stopped() + .map(|(id, why, held)| json!({"id": id.to_string(), "why": why, "heldBack": held})); json!({ "store": store.id().to_string(), "checkpoint": Id::of(store.checkpoint()).to_string(), "heads": ids(store.heads()), "taken": store.taken().len(), + "stopped": stopped, "party": party, "votesByItself": votes, }) @@ -218,7 +223,7 @@ async fn refused(State(state): State) -> Response { /// `POST /events`: puts an event, the request's body, whoever signed it: offered to the /// store, and written into the document at its ID unless the store refuses it. Taken, -/// held already, or waiting for what it builds on. +/// held already, waiting for what it builds on, or held back, the store stopped. async fn put( State(state): State, Extension(AuthenticatedUser(user)): Extension, @@ -238,6 +243,7 @@ async fn put( Some(Offered::Taken(_)) => "taken", Some(Offered::Held) => "held", Some(Offered::Waiting) => "waiting", + Some(Offered::Stopped) => "stopped", }; match crate::federation::held::write(&state, Some(user), bytes).await { Ok(()) => Json(json!({"id": id.to_string(), "event": became})).into_response(), @@ -359,10 +365,10 @@ async fn check_fork(State(state): State, body: Bytes) -> Response { } } -/// `POST /admin/events/drop`: drops events the store took after its checkpoint, with -/// everything built on them, as the operator has the node do: it refuses them from then -/// on, from whoever brings them, and keeps so across restarts (`--store-file`). What it -/// dropped, in the order taken. +/// `POST /admin/events/drop`: drops events the store took after its checkpoint, or the +/// one it stopped at, with everything built on them, as the operator has the node do: it +/// refuses them from then on, from whoever brings them, and keeps so across restarts +/// (`--store-file`). What it dropped, in the order taken, then the one it stopped at. async fn drop_taken(State(state): State, Json(named): Json) -> Response { let named = match named.ids() { Ok(ids) => ids, diff --git a/src/federation/attacks.rs b/src/federation/attacks.rs index 316f5eb..db047c9 100644 --- a/src/federation/attacks.rs +++ b/src/federation/attacks.rs @@ -14,7 +14,7 @@ use super::store::{Fold, Id}; use super::version::Version; /// Rows whose tests wait: what a node or a party's client doesn't do yet, and flooding. -const LATER: &[u32] = &[30, 39, 63, 68]; +const LATER: &[u32] = &[30, 63, 68]; fn tv() -> Party { Party::new("tv", 1) @@ -71,6 +71,14 @@ impl Fed { assert!(matches!(why, Refusal::Judged(_)), "{why:?}"); } + /// An event the store stops at (`Fold::stops`), and its operator has it drop. + fn stops(&mut self, bytes: Vec) { + let id = Id::of(&bytes); + assert_eq!(self.store.offer(bytes), Offered::Stopped); + assert_eq!(self.store.stopped().map(|(at, ..)| *at), Some(id)); + assert_eq!(self.store.drop_taken(&[id]), Ok(vec![id])); + } + fn value(&self, path: &str) -> Option { self.store.state().value(path).cloned() } @@ -277,7 +285,8 @@ fn federation_attack_9() { let proposal = fed.take(tv.propose(&[root], &next.json())); let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true)); let also = fed.take(lass.vote(&[proposal], on, next.hash(), true)); - fed.judged(harness::version_event(&[yes, also], next.hash())); + // None to this continuum, as one it doesn't know: it stops at it. + fed.stops(harness::version_event(&[yes, also], next.hash())); // Free the backers for the next one: nays make it dead. let no = fed.take(makefu().vote(&[proposal], on, next.hash(), false)); fed.take(tv.vote(&[no], on, next.hash(), false)); @@ -299,7 +308,7 @@ fn federation_attack_10() { let hash = Id::of(&unknown.bytes()); let yes = fed.take(tv.vote(&[proposal], on, hash, true)); let also = fed.take(lass.vote(&[proposal], on, hash, true)); - fed.judged(harness::version_event(&[yes, also], hash)); + fed.stops(harness::version_event(&[yes, also], hash)); } #[test] @@ -921,7 +930,7 @@ fn federation_attack_48() { let proposal = fed.take(tv.propose(&[root], &bad.json())); let yes = fed.take(tv.vote(&[proposal], on, bad.hash(), true)); let also = fed.take(lass.vote(&[proposal], on, bad.hash(), true)); - fed.judged(harness::version_event(&[yes, also], bad.hash())); + fed.stops(harness::version_event(&[yes, also], bad.hash())); // It can't die either: its backers are bound. let next = fed.first.after(on); let other = fed.take(makefu().propose(&[root], &next.json())); diff --git a/src/federation/fold.rs b/src/federation/fold.rs index f37c213..fddedc0 100644 --- a/src/federation/fold.rs +++ b/src/federation/fold.rs @@ -484,7 +484,8 @@ impl State { } /// Whether a version event is taken here, at its history, `current` the version current - /// there. + /// there. One whose proposal passed but doesn't read as a version, it doesn't refuse: + /// a later continuum may read it (`Fold::stops`). fn judge_version(&self, deps: &[Id], hash: &Id, current: &Version) -> Result<(), Refused> { if !self.proposed_on(hash, ¤t.hash) { return Err(Refused::new( @@ -494,8 +495,9 @@ impl State { if !self.tally(current, hash).passed { return Err(Refused::new("its proposal hasn't passed at its history")); } - let next = Version::read(&self.proposed[hash]) - .map_err(|why| Refused::new(format!("no version: {why}")))?; + let Ok(next) = Version::read(&self.proposed[hash]) else { + return Ok(()); + }; next.changes_validly(Some(current)) .map_err(|why| Refused::new(format!("no version: {why}")))?; if let Some(heads) = &next.checkpoint { @@ -627,6 +629,19 @@ impl Fold for Federation { state.events.insert(*id, Held { event, under }); } + /// A version event whose proposal passed at its history but doesn't read as a version + /// here, changing the version the node reads: one a later continuum may read + /// (`docs/federation.md`, Changing the federation). Beside the version the node reads, + /// it is refused as any other (`keeps`). + fn stops(at: &State, now: &State, _id: &Id, bytes: &[u8]) -> Option { + let Some(Event::Version { version, .. }) = Event::read_taken(bytes) else { + return None; + }; + let why = Version::read(at.proposed.get(&version)?).err()?; + (at.current().hash == now.current().hash) + .then(|| format!("version {version} passed, and doesn't read as one here: {why}")) + } + fn keeps(now: &State, _id: &Id, bytes: &[u8]) -> bool { match Event::read_taken(bytes) { Some(Event::Version { version, .. }) => { diff --git a/src/federation/held.rs b/src/federation/held.rs index 200323e..5155573 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -135,6 +135,8 @@ struct Inner { none: Option, /// The pinned checkpoint not found in the document, logged once. unfound: bool, + /// The event the store stopped at, logged once (`Fold::stops`). + stopped: Option, /// The refused changes looked at, of those screening keeps (`look`). looked: HashSet, /// When, by its own clock, the node took each event its store took after its @@ -331,7 +333,7 @@ impl Holding { refused += 1; info!(event = %id, why = ?why, "The store refuses an event the document holds"); } - Offered::Held | Offered::Waiting => {} + Offered::Held | Offered::Waiting | Offered::Stopped => {} } } if taken > 0 || refused > 0 { @@ -341,11 +343,23 @@ impl Holding { } /// After the store changed: what the node keeps of its own, written to its file where - /// it changed, and the members, as the store reads now. + /// it changed, and the members, as the store reads now; whether it stopped, logged. fn settle(&self, inner: &mut Inner) { let Some(store) = &inner.store else { return; }; + let stopped = store.stopped().map(|(id, why, _)| (*id, why)); + if stopped.map(|(id, _)| id) != inner.stopped { + match stopped { + Some((id, why)) => error!( + event = %id, + why = %why, + "The store stopped at an event this continuum can't judge: it takes none until it runs one that does, or its operator has it drop that one" + ), + None => warn!("The store takes events again"), + } + inner.stopped = stopped.map(|(id, _)| id); + } let now = Instant::now(); let checkpoint = Id::of(store.checkpoint()); if inner.at_checkpoint.map(|(at, _)| at) != Some(checkpoint) { @@ -385,9 +399,10 @@ impl Holding { Some(offered) } - /// Drops `ids`, events the store took after its checkpoint, with everything built on - /// them, as its operator has the node do: it refuses them from then on, and keeps so - /// (`docs/store.md`, A node's own). What it dropped, in the order taken. + /// Drops `ids`, events the store took after its checkpoint or the one it stopped at, + /// with everything built on them, as its operator has the node do: it refuses them from + /// then on, and keeps so (`docs/store.md`, A node's own). What it dropped, in the order + /// taken, then the one it stopped at. pub(crate) fn drop_taken(&self, ids: &[Id]) -> Option, Refused>> { let mut inner = self.inner.lock_or_recover(); let dropped = inner.store.as_mut()?.drop_taken(ids); @@ -657,6 +672,7 @@ impl Holding { /// What it signs now, voting by itself by its operator's rules (`vote::decide`), or by /// hand (`hand`, `vote::by_hand`): recorded, the record written, and offered to the /// store; the events, to put into the document. By hand, why not where it isn't. + /// Nothing while its store is stopped. fn sign(&self, hand: Option<(Id, bool)>) -> Result>, String> { let (Some(voter), Some(party)) = (&self.voter, &self.party) else { return Err("this node doesn't vote for its party".to_owned()); @@ -668,6 +684,15 @@ impl Holding { let (Some(store), Some(record)) = (&inner.store, &inner.record) else { return Err("this node holds no store".to_owned()); }; + // What it reads is behind what passed: it casts nothing. + if let Some((id, ..)) = store.stopped() { + return match hand { + None => Ok(Vec::new()), + Some(_) => Err(format!( + "its store stopped at {id}: it votes once it takes events again" + )), + }; + } let now = Instant::now(); let held = |id: &Id| inner.taken_at.get(id).map(|at| now.duration_since(*at)); let seen = Seen { @@ -1676,6 +1701,166 @@ mod tests { assert_eq!(current(&restarted), Some(one.hash())); } + /// Row 39 (`docs/federation.md`): a version of a federation this continuum doesn't + /// know passed, and a version event writes it: the node stops there, taking nothing + /// and refusing nothing of what comes after, and writes none of it to its file, before + /// or after a restart. Its operator has it drop that event: it takes again, under the + /// version before, and keeps so; allowed again, it stops there once more. A root of a + /// federation it doesn't know, it holds no store of. + #[test] + fn federation_attack_39() { + 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 later = |json: &[u8]| { + String::from_utf8(json.to_vec()) + .unwrap() + .replace(r#""federation":1"#, r#""federation":2"#) + }; + let unknown = + crate::federation::jcs::read(later(&first.after(on).json().bytes()).as_bytes()) + .unwrap(); + let hash = Id::of(&unknown.bytes()); + let proposal = tv.propose(&[Id::of(&root)], &unknown); + let votes = [&tv, &lass].map(|party| party.vote(&[Id::of(&proposal)], on, hash, true)); + let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], hash); + let stopped_at = Id::of(&written); + let beside = tv.write(&[Id::of(&votes[0])], "home/tv/a", harness::str("1")); + let after = tv.write(&[stopped_at], "home/tv/b", harness::str("1")); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); + for event in [&proposal].into_iter().chain(&votes).chain([&written]) { + put(&mut doc, event); + } + let stopped = |holding: &Holding| { + holding.with(|store| store.stopped().map(|(id, _, held)| (*id, held))) + }; + let current = |holding: &Holding| holding.with(|store| store.state().current().hash); + let taken = |holding: &Holding, event: &[u8]| { + holding.with(|store| store.taken().contains(&Id::of(event))) + }; + let dir = crate::files::scratch_dir("held-attack-39"); + let path = dir.join("store.json"); + let files = Arc::new(Files::default()); + let holding = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap(); + read(&holding, &doc, 0); + assert_eq!(stopped(&holding), Some(Some((stopped_at, 1)))); + put(&mut doc, &beside); + put(&mut doc, &after); + read(&holding, &doc, 0); + assert_eq!(stopped(&holding), Some(Some((stopped_at, 3)))); + assert_eq!( + holding.offer(tv.write(&[Id::of(&root)], "home/tv/c", harness::str("1"))), + Some(Offered::Stopped) + ); + assert_eq!(holding.passed(), Vec::>::new()); + assert_eq!(holding.with(|store| store.refused().count()), Some(0)); + assert!(!path.exists()); + // Restarted: it stops there again. + let restarted = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap(); + read(&restarted, &doc, 0); + assert_eq!( + stopped(&restarted).flatten().map(|(id, _)| id), + Some(stopped_at) + ); + // Dropped: it takes again, under the version before, and refuses what is built on + // that event; it writes no version event naming that version. + assert_eq!( + restarted.drop_taken(&[stopped_at]), + Some(Ok(vec![stopped_at])) + ); + assert_eq!(stopped(&restarted), Some(None)); + assert_eq!(current(&restarted), Some(on)); + assert_eq!(taken(&restarted, &beside), Some(true)); + assert_eq!( + restarted.with(|store| store.refusal(&Id::of(&after)).cloned()), + Some(Some(Refusal::BuiltOn(stopped_at))) + ); + assert_eq!(restarted.passed(), Vec::>::new()); + // Kept so across a restart. + let again = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap(); + read(&again, &doc, 0); + assert_eq!(stopped(&again), Some(None)); + assert_eq!(current(&again), Some(on)); + assert_eq!(taken(&again, &beside), Some(true)); + // Allowed again: it stops there once more. + assert!(again.allow(&[stopped_at])); + read(&again, &doc, 0); + assert_eq!( + stopped(&again).flatten().map(|(id, _)| id), + Some(stopped_at) + ); + + // A root of a federation it doesn't know. + let unknown_root = later(&root).into_bytes(); + assert_ne!(unknown_root, root); + let doc = events::started(Federation::NAME, &unknown_root, &[]).unwrap(); + let holding = Holding::default(); + read(&holding, &doc, 0); + assert!(holding.with(|_| ()).is_none()); + } + + /// A node voting by itself whose store stopped casts nothing, by itself or by hand: + /// what it reads is behind what passed. + #[test] + fn a_node_whose_store_stopped_votes_nothing() { + 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 next = first.after(on); + let proposal = tv.propose(&[Id::of(&root)], &none.json()); + let other = lass.propose(&[Id::of(&root)], &next.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 mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); + for event in [&proposal, &other] + .into_iter() + .chain(&votes) + .chain([&written]) + { + put(&mut doc, event); + } + let dir = crate::files::scratch_dir("held-stopped-votes"); + let record = dir.join("makefu.json"); + let version = Version::read(&first.json()).unwrap(); + let mut begun = Record::begin(Id::of(&root), "makefu", &version); + begun.began = Id::of(b"before the federation").to_string(); + begun.save(&record).unwrap(); + let holding = Holding::open( + None, + Arc::new(Files::default()), + None, + Some("makefu".into()), + ) + .unwrap() + .voting(Some(Voter { + key: makefu.key.clone(), + record, + rules: Rules::default(), + })); + read(&holding, &doc, 0); + assert!(holding.with(|store| store.stopped().is_some()).unwrap()); + assert_eq!(holding.act(), Vec::>::new()); + let why = holding.vote_by_hand(next.hash(), true).unwrap_err(); + assert!(why.contains("stopped"), "{why}"); + // Dropped: it votes again. + holding.drop_taken(&[Id::of(&written)]).unwrap().unwrap(); + assert!(holding.vote_by_hand(next.hash(), true).is_ok()); + } + // The store's attack rows (`docs/store.md`, Attacks) read from a document. /// tv's federation, its root, and a document started from it. diff --git a/src/federation/properties.rs b/src/federation/properties.rs index 61d6adc..d42509b 100644 --- a/src/federation/properties.rs +++ b/src/federation/properties.rs @@ -297,6 +297,8 @@ fn verdict(offered: &Offered) -> Verdict { Offered::Held => Verdict::Held, Offered::Waiting => Verdict::Waiting, Offered::Refused(_) => Verdict::Refused, + // The harness proposes only versions this continuum reads: none stops the store. + Offered::Stopped => unreachable!("the store stopped"), } } diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index 7527a44..f721b47 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -34,6 +34,9 @@ pub(crate) enum Offered { Waiting, /// Refused, and why; what waited on it is refused with it. Refused(Refusal), + /// Held back, neither taken nor refused: the store stopped at an event it can't judge + /// (`Fold::stops`), this one or one before. + Stopped, } /// A checkpoint built: its bytes, and the events it keeps, by ID. @@ -74,6 +77,12 @@ pub(crate) struct Store { /// What a move to a checkpoint forgot that came before its heads: held as accounted /// for, and nothing after the checkpoint builds on it. forgotten: HashSet, + /// The event the store stopped at, and why (`Fold::stops`); and what it holds back + /// since, that one first, in the order offered: it takes nothing and refuses nothing + /// until its operator has it drop that one. + stopped: Option<(Id, String)>, + held_back: Vec<(Id, Event)>, + holding_back: HashSet, } impl Store { @@ -117,6 +126,9 @@ impl Store { refused: HashMap::new(), writes: HashMap::new(), forgotten: HashSet::new(), + stopped: None, + held_back: Vec::new(), + holding_back: HashSet::new(), }) } @@ -202,6 +214,14 @@ impl Store { self.waiting.contains_key(id) } + /// The event the store stopped at, and why, where it stopped (`Fold::stops`); and how + /// many events it holds back, that one among them. + pub(crate) fn stopped(&self) -> Option<(&Id, &str, usize)> { + self.stopped + .as_ref() + .map(|(id, why)| (id, why.as_str(), self.held_back.len())) + } + /// 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 { @@ -240,6 +260,9 @@ impl Store { if self.waiting.contains_key(&id) { return Offered::Waiting; } + if self.holding_back.contains(&id) { + return Offered::Stopped; + } if bytes.len() > F::LARGEST { return self.refuse(id, Refusal::None); } @@ -447,6 +470,9 @@ impl Store { } fn judged(&mut self, id: Id, event: Event, taken: &mut Vec) -> Offered { + if self.stopped.is_some() { + return self.hold_back(id, event); + } if let Some(writes) = F::writes(&event.bytes) && self.writes.values().any(|dropped| *dropped == writes) { @@ -498,6 +524,10 @@ impl Store { if let Err(why) = F::judge(&at, &id, &event.bytes) { return self.refuse(id, Refusal::Judged(why)); } + if let Some(why) = F::stops(&at, &self.state, &id, &event.bytes) { + self.stopped = Some((id, why)); + return self.hold_back(id, event); + } if !F::keeps(&self.state, &id, &event.bytes) { return self.refuse(id, Refusal::Own); } @@ -508,6 +538,14 @@ impl Store { Offered::Taken(vec![id]) } + /// Holds an event back, the store stopped. + fn hold_back(&mut self, id: Id, event: Event) -> Offered { + if self.holding_back.insert(id) { + self.held_back.push((id, event)); + } + Offered::Stopped + } + /// The events refused, and why: for reports. pub(crate) fn refused(&self) -> impl Iterator { self.refused.iter() @@ -517,19 +555,31 @@ impl Store { /// (`Fold::writes`), and everything built on them, as their operator has the node do: /// it refuses them from then on, and whatever writes what they write, until its /// operator allows them again. What the checkpoint keeps, or holds by ID, it drops not: - /// every event after it builds on that. Returns what it dropped, in the order taken. + /// every event after it builds on that. It drops the event it stopped at alike, or + /// refuses it for building on what it drops: then it takes again, and is offered what + /// it held back anew. Returns what it dropped, in the order taken, then the event it + /// stopped at, where it dropped that. pub(crate) fn drop_taken(&mut self, ids: &[Id]) -> Result, Refused> { - if let Some(id) = ids.iter().find(|id| !self.events.contains_key(id)) { + let stopped = self.stopped.as_ref().map(|(id, _)| *id); + if let Some(id) = ids + .iter() + .find(|id| !self.events.contains_key(id) && Some(**id) != stopped) + { return Err(Refused::new(format!( - "{id} isn't an event taken after the checkpoint" + "{id} isn't an event taken after the checkpoint, nor the one the store stopped at" ))); } - let named: HashSet = ids + let taken: Vec = ids + .iter() + .filter(|id| self.events.contains_key(id)) + .copied() + .collect(); + let named: HashSet = taken .iter() .filter_map(|id| F::writes(&self.events[id].bytes)) .collect(); let mut dropped: HashMap = - ids.iter().map(|id| (*id, Refusal::Dropped)).collect(); + taken.iter().map(|id| (*id, Refusal::Dropped)).collect(); for id in &self.order { if dropped.contains_key(id) { continue; @@ -547,26 +597,52 @@ impl Store { dropped.insert(*id, Refusal::BuiltOn(on)); } } - let order: Vec = self + let mut order: Vec = self .order .iter() .filter(|id| dropped.contains_key(id)) .copied() .collect(); - self.order.retain(|id| !dropped.contains_key(id)); - for id in &order { - if let Some(event) = self.events.remove(id) - && let Some(writes) = F::writes(&event.bytes) - { - self.writes.insert(*id, writes); + if !order.is_empty() { + self.order.retain(|id| !dropped.contains_key(id)); + for id in &order { + if let Some(event) = self.events.remove(id) + && let Some(writes) = F::writes(&event.bytes) + { + self.writes.insert(*id, writes); + } } + self.refused.extend(dropped); + let mut state = self.start.clone(); + for id in &self.order { + F::add(&mut state, id, &self.events[id].bytes); + } + self.state = state; } - self.refused.extend(dropped); - let mut state = self.start.clone(); - for id in &self.order { - F::add(&mut state, id, &self.events[id].bytes); + if let Some(stopped) = stopped { + let dropping = ids.contains(&stopped); + let on_dropped = self.held_back[0] + .1 + .dependencies + .iter() + .any(|dependency| self.refused.contains_key(dependency)); + if dropping || on_dropped { + self.stopped = None; + self.holding_back.clear(); + let mut held_back = std::mem::take(&mut self.held_back); + if dropping { + let (_, event) = held_back.remove(0); + if let Some(writes) = F::writes(&event.bytes) { + self.writes.insert(stopped, writes); + } + self.refuse(stopped, Refusal::Dropped); + order.push(stopped); + } + for (_, event) in held_back { + self.offer(event.bytes); + } + } } - self.state = state; Ok(order) } @@ -868,6 +944,85 @@ mod tests { assert!(matches!(store.offer(anew), Offered::Taken(_))); } + /// An event the store can't judge, that its node would take: it stops there, holding + /// back what comes after, taken or refused by nobody, until its operator has it drop + /// that one; then it takes them, as before the stop. Beside what it took, the event + /// is refused of its own. + #[test] + fn a_store_stops_at_what_it_cant_judge_until_its_operator_drops_it() { + let mut store = store(); + let root = store.id(); + let mark = taken(store.offer(testfold::put(&[root], "mark", "1"))); + let new = testfold::era(&[mark], 1, "new"); + let at = Id::of(&new); + let on = testfold::put(&[at], "a", "1"); + // Waiting for it before the stop: refused once it is dropped. + assert_eq!(store.offer(on.clone()), Offered::Waiting); + assert_eq!(store.offer(new.clone()), Offered::Stopped); + let (id, why, held) = store.stopped().expect("stopped"); + assert_eq!((*id, why, held), (at, "era 1, tagged new", 1)); + // Nothing taken, nothing refused, junk or not. + let later = testfold::put(&[mark], "b", "1"); + let junk = testfold::junk(&[mark]); + assert_eq!(store.offer(later.clone()), Offered::Stopped); + assert_eq!(store.offer(junk.clone()), Offered::Stopped); + assert_eq!(store.offer(later.clone()), Offered::Stopped); + assert_eq!(store.offer(new.clone()), Offered::Stopped); + assert_eq!(store.taken(), &[mark]); + assert_eq!(store.refused().count(), 0); + assert_eq!(store.stopped().map(|(_, _, held)| held), Some(3)); + 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_eq!(store.taken(), &[mark, Id::of(&later)]); + assert!(matches!( + store.refusal(&Id::of(&junk)), + Some(Refusal::Judged(_)) + )); + assert_eq!(store.refusal(&Id::of(&on)), Some(&Refusal::BuiltOn(at))); + assert_eq!(store.own(), (Vec::new(), vec![at])); + // Of what writes what it writes, whoever wrote it: dropped. + assert_eq!( + store.offer(testfold::era(&[root], 1, "new")), + Offered::Refused(Refusal::Dropped) + ); + // Allowed again: it stops there once more. + store.allow(&[at]); + assert_eq!(store.offer(new), Offered::Stopped); + assert_eq!(store.offer(on), Offered::Stopped); + // Beside an era it took, it is refused of its own, and nothing stops. + let mut beside = self::store(); + let one = taken(beside.offer(testfold::era(&[root], 1, "one"))); + let new = testfold::era(&[root], 1, "new"); + assert_eq!(beside.offer(new.clone()), Offered::Refused(Refusal::Own)); + assert!(beside.stopped().is_none()); + // Its operator drops the era it took and allows the other: it stops there. + beside.drop_taken(&[one]).unwrap(); + beside.allow(&[Id::of(&new)]); + assert_eq!(beside.offer(new), Offered::Stopped); + } + + /// The store stopped at an event built on one its operator has it drop: it refuses it + /// with the rest, and takes again. + #[test] + fn a_drop_under_the_event_a_store_stopped_at_takes_it_with_it() { + let mut store = store(); + let root = store.id(); + let mark = taken(store.offer(testfold::put(&[root], "mark", "1"))); + let new = Id::of(&testfold::era(&[mark], 1, "new")); + assert_eq!( + store.offer(testfold::era(&[mark], 1, "new")), + Offered::Stopped + ); + let later = testfold::put(&[root], "b", "1"); + assert_eq!(store.offer(later.clone()), Offered::Stopped); + assert_eq!(store.drop_taken(&[mark]), Ok(vec![mark])); + assert!(store.stopped().is_none()); + assert_eq!(store.refusal(&new), Some(&Refusal::BuiltOn(mark))); + assert_eq!(store.taken(), &[Id::of(&later)]); + } + #[test] fn a_store_read_anew_refuses_what_its_node_refused_of_its_own() { let mut store = store(); diff --git a/src/federation/store/mod.rs b/src/federation/store/mod.rs index 4027fb9..c80f5b8 100644 --- a/src/federation/store/mod.rs +++ b/src/federation/store/mod.rs @@ -82,13 +82,21 @@ pub(crate) trait Fold { /// What the event builds on; `None` where its bytes are none of this fold's events. fn dependencies(event: &[u8]) -> Option>; - /// Whether the event is taken where its history reads as `at`. + /// Whether the event is taken where its history reads as `at`, as far as the fold + /// reads it (`stops`). fn judge(at: &Self::State, id: &Id, event: &[u8]) -> Result<(), Refused>; /// Adds the event, whose dependencies are added already. Events neither of which /// builds on the other may come in either order: the state is the same. fn add(state: &mut Self::State, id: &Id, event: &[u8]); + /// Why a node whose store reads as `now` can't judge an event its history, read as + /// `at`, doesn't refuse, where it can't: one only a fold knowing more reads, that the + /// node would take. The store stops at it (`docs/store.md`, A node's own). + fn stops(_at: &Self::State, _now: &Self::State, _id: &Id, _event: &[u8]) -> Option { + None + } + /// Whether a node whose store reads as `now` takes an event its history takes. fn keeps(_now: &Self::State, _id: &Id, _event: &[u8]) -> bool { true diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs index 2478c0a..17e039b 100644 --- a/src/federation/store/testfold.rs +++ b/src/federation/store/testfold.rs @@ -7,7 +7,8 @@ //! * `lock`: a key locked for good. //! * `era`: era `n`, taken only where `n` is one past the era at its history; of two of one //! number, a node keeps the first it takes (as the federation's versions). Eras of one -//! number and tag write the same: a drop of one refuses them all. +//! number and tag write the same: a drop of one refuses them all. One tagged `new` is +//! of a fold knowing more: a node that would take it stops at it. //! * `cut`: cut `n`, naming heads to move the store to, as `era`: above the heads the latest //! cut of its history names, and holding that cut (or after the checkpoint the state //! starts from, where it holds none); none of them in another's history. It must be above @@ -347,6 +348,15 @@ impl Fold for TestFold { } } + fn stops(at: &State, now: &State, _id: &Id, event: &[u8]) -> Option { + match decode(event)? { + (_, Kind::Era { n, tag }) if tag == "new" && now.era == at.era => { + Some(format!("era {n}, tagged new")) + } + _ => None, + } + } + fn keeps(now: &State, _id: &Id, event: &[u8]) -> bool { match decode(event) { Some((_, Kind::Era { n, tag })) => { -- cgit v1.3.1