diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/federation/model.rs | 36 | ||||
| -rw-r--r-- | src/federation/properties.rs | 60 |
2 files changed, 82 insertions, 14 deletions
diff --git a/src/federation/model.rs b/src/federation/model.rs index 404bdb4..2107d9f 100644 --- a/src/federation/model.rs +++ b/src/federation/model.rs @@ -1,7 +1,7 @@ //! The model (`docs/federation-tests.md`, The harness): the federation read as //! `docs/federation.md` says, as plainly as it can be. It reads every history anew from -//! the root, keeps nothing between events but which it took, and makes no checkpoint. -//! It is slow and short, and the fold is checked against it. +//! the root, keeps nothing between events but which it took and whether it stopped, and +//! makes no checkpoint. It is slow and short, and the fold is checked against it. use std::collections::{BTreeMap, BTreeSet}; @@ -19,6 +19,9 @@ pub(crate) enum Verdict { /// Some of its dependencies aren't taken yet. Waiting, Refused, + /// Neither taken nor refused: it stopped at a version it doesn't read, this event or + /// one before. + Stopped, } pub(crate) struct Model { @@ -29,6 +32,8 @@ pub(crate) struct Model { refused: BTreeSet<Id>, /// Events offered whose dependencies aren't all taken yet. waiting: Vec<Vec<u8>>, + /// Whether it stopped (`Changing the federation`): it takes and refuses nothing more. + stopped: bool, } impl Model { @@ -42,6 +47,7 @@ impl Model { taken: BTreeMap::new(), refused: BTreeSet::new(), waiting: Vec::new(), + stopped: false, } } @@ -81,6 +87,9 @@ impl Model { self.refused.insert(id); return Verdict::Refused; }; + if self.stopped { + return Verdict::Stopped; + } let deps = event.deps(); if deps.iter().any(|dep| self.refused.contains(dep)) { self.refused.insert(id); @@ -93,7 +102,15 @@ impl Model { return Verdict::Waiting; } let history = self.history(deps); - if self.judge(&history, &event, deps) && self.keeps(&event) { + if !self.judge(&history, &event, deps) { + self.refused.insert(id); + return Verdict::Refused; + } + if self.stops(&history, &event) { + self.stopped = true; + return Verdict::Stopped; + } + if self.keeps(&event) { self.taken.insert(id, event); Verdict::Taken } else { @@ -337,8 +354,9 @@ impl Model { if 3 * yes.len() < 2 * current.parties.len() { return false; } + // None here: whether it is a version, a later continuum may say. let Some(next) = self.written(version) else { - return false; + return true; }; if next.changes_validly(Some(¤t)).is_err() { return false; @@ -402,6 +420,16 @@ impl Model { .all(|dep| heads.contains(dep) || self.is_above(dep, heads)) } + /// Whether the node stops at `event`, at a history it judged: a version event whose + /// proposal is none here, changing the version the node reads, the one current there. + fn stops(&self, history: &BTreeSet<Id>, event: &Event) -> bool { + let Event::Version { version, .. } = event else { + return false; + }; + let reads = |history: &BTreeSet<Id>| self.current(history).map(|current| current.hash); + self.written(version).is_none() && reads(history) == reads(&self.taken()) + } + /// A node's own: a version event it takes only where its version changes the version /// it reads, or is one it took. fn keeps(&self, event: &Event) -> bool { diff --git a/src/federation/properties.rs b/src/federation/properties.rs index d42509b..02c7799 100644 --- a/src/federation/properties.rs +++ b/src/federation/properties.rs @@ -15,6 +15,7 @@ use super::event::{Checkpoint, Does, Event}; use super::fold::Federation; use super::harness::{self, Party, Spec}; use super::held::Holding; +use super::jcs::Json; use super::model::{Model, Verdict}; use super::store::memory::{Offered, Refusal, Store}; use super::store::{Fold, Id}; @@ -82,12 +83,14 @@ impl History { } } -/// How a history is written: whether an adversary takes part, and whether versions name -/// checkpoints. +/// How a history is written: whether an adversary takes part, whether versions name +/// checkpoints, and whether parties propose versions this continuum doesn't read, at +/// which a store stops, which events then take in the order they come. #[derive(Clone, Copy)] struct Kind { adversary: bool, checkpoints: bool, + unread: bool, } /// One of `ids`, of the latest five more often than not. @@ -169,10 +172,27 @@ fn generate(rng: &mut Rng, kind: Kind) -> History { next.rules .push((format!("names/x{step}"), harness::str(&party.name))); } - let bytes = party.propose(&deps, &next.json()); - proposals.push((Id::of(&bytes), next.hash(), current.hash, named)); - specs.insert(next.hash(), next); - bytes + if kind.unread && rng.chance(0.5) { + // A field this continuum doesn't know: none here. + let Json::Object(mut members) = next.json() else { + unreachable!("a version is an object") + }; + members.push(("later".to_owned(), Json::Bool(true))); + let later = Json::object(members).expect("names once each"); + let bytes = party.propose(&deps, &later); + proposals.push(( + Id::of(&bytes), + Id::of(&later.bytes()), + current.hash, + named, + )); + bytes + } else { + let bytes = party.propose(&deps, &next.json()); + proposals.push((Id::of(&bytes), next.hash(), current.hash, named)); + specs.insert(next.hash(), next); + bytes + } } } } else if roll < 85 { @@ -297,19 +317,28 @@ 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"), + Offered::Stopped => Verdict::Stopped, } } +/// Where parties propose versions this continuum doesn't read too, the store stops where +/// the model does: written in order, events come after what they build on, and both stop +/// at the same event, taking the same before it. #[test] fn the_store_judges_and_reads_as_the_model() { - for adversary in [false, true] { + let stopped = std::cell::Cell::new(0); + for (adversary, unread, cases) in [ + (false, false, 48), + (true, false, 48), + (false, true, 32), + (true, true, 32), + ] { check( - 48, + cases, Kind { adversary, checkpoints: false, + unread, }, |history| { let mut model = Model::new(&history.root); @@ -325,6 +354,9 @@ fn the_store_judges_and_reads_as_the_model() { )); } } + if store.stopped().is_some() { + stopped.set(stopped.get() + 1); + } if reads(&store) != model_reads(&model) { return Err(format!( "the store reads {:?}, the model {:?}", @@ -336,6 +368,7 @@ fn the_store_judges_and_reads_as_the_model() { }, ); } + assert!(stopped.get() > 0, "no history stopped a store"); } #[test] @@ -345,6 +378,7 @@ fn what_builds_on_a_refused_event_is_refused() { Kind { adversary: true, checkpoints: true, + unread: false, }, |history| { let (store, _) = history.store(&history.written()); @@ -369,6 +403,7 @@ fn honest_parties_read_the_same_whatever_order_events_come_in() { Kind { adversary: false, checkpoints: true, + unread: false, }, |history| { let held = holds(&history.store(&history.written()).0); @@ -401,6 +436,7 @@ fn a_store_read_from_its_document_holds_what_one_given_the_events_alone_holds() Kind { adversary: false, checkpoints: true, + unread: false, }, |history| { let alone = holds(&history.store(&history.written()).0); @@ -456,6 +492,7 @@ fn after_a_checkpoint_the_store_judges_and_reads_as_the_whole_history() { Kind { adversary: false, checkpoints: true, + unread: false, }, |history| { let (store, _) = history.store(&history.written()); @@ -533,6 +570,7 @@ fn every_version_a_store_takes_was_passed_by_two_thirds_in_its_history() { Kind { adversary: true, checkpoints: false, + unread: false, }, |history| { let (store, _) = history.store(&history.written()); @@ -610,6 +648,7 @@ fn without_a_party_voting_twice_no_two_versions_change_one() { Kind { adversary: false, checkpoints: true, + unread: false, }, |history| { let (store, _) = history.store(&history.written()); @@ -632,6 +671,7 @@ fn a_fork_keeps_what_counts_at_its_heads_and_takes_nothing_of_the_other() { Kind { adversary: false, checkpoints: false, + unread: false, }, |history| { let (mut whole, _) = history.store(&history.written()); |
