aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-19 04:02:52 +0000
committertv <tv@krebsco.de>2026-11-19 05:13:51 +0100
commit2c9d42ed955705a0207b047918f58ef258dcfa4f (patch)
treeb8d50ee2fdce459a4b61fff4e8bddff6d308da8e
parent0d2467e15ec0c9c035b1074a2dd4eece6b24c599 (diff)
federation: a corpus per revision, judged alike by every later continuum
Nothing checked that judging under a revision stays what it was: a change to the fold that alters what an earlier revision takes, refuses or reads parts nodes running it from nodes that don't, and the tests regenerate their expectations with the code. For each revision this continuum knows, a file in `src/federation/corpus/` holds histories generated at that revision, of every kind the properties generate, each event's bytes with what became of it, by kind and never by a refusal's words, and what the store reads after; its first line names the revision by its ID. It is written once, as the revision is made (`write_the_corpus`, an ignored test run by hand), and never edited after; every later continuum judges it alike (`every_revision_judges_as_its_corpus_says`), which fails where a revision has no corpus yet, saying how to write it. The test plan describes it.
-rw-r--r--docs/federation-tests.md19
-rw-r--r--src/federation/corpus.rs238
-rw-r--r--src/federation/mod.rs2
-rw-r--r--src/federation/properties.rs33
4 files changed, 277 insertions, 15 deletions
diff --git a/docs/federation-tests.md b/docs/federation-tests.md
index 3aa1996..a39e749 100644
--- a/docs/federation-tests.md
+++ b/docs/federation-tests.md
@@ -120,10 +120,23 @@ UTF-16 units otherwise than by their bytes (one from U+E000 to U+FFFF beside one
U+FFFF); events at federation 1's sizes and just past them; a signature, a version and
its hash, a checkpoint and its ID, the genesis change of a federation's root and of a
fork's, a snapshot after a checkpoint, and a version naming an ECDSA key, with a write
-and a key set `ssh-keygen` signed with it. A vector that changes is a change of the
-federation, which takes its next number ([`federation.md`](federation.md),
+and a key set `ssh-keygen` signed with it. A vector that changes is a change to what
+every node must agree on ([`federation.md`](federation.md),
[Changing the federation](federation.md#changing-the-federation)).
+## The corpus
+
+What each revision takes, refuses and reads, as fixed bytes: for each revision this
+continuum knows, a file in `src/federation/corpus/` of histories generated at that
+revision (of every kind the properties generate, a few seeds each), each event's bytes
+with what became of it, by kind (taken, refused and why, by kind, waiting, held back, gone
+with a move), and what the store reads after. A revision's file is written once, as the
+revision is made (`write_the_corpus`, run by hand), and never edited after: every later
+continuum judges it alike (`every_revision_judges_as_its_corpus_says`), so that a change
+to judging that alters an earlier revision's comes as a later revision. Its first line
+names the revision by its ID: a feature renamed fails as a judgment changed does. It holds
+only what its histories exercise.
+
## Fuzzing and mutants
* **Fuzzing**, with `cargo fuzz` (a nightly compiler), outside `cargo quick`: the event
@@ -137,7 +150,7 @@ federation, which takes its next number ([`federation.md`](federation.md),
* `cargo quick`: the rules and attacks by example, the properties at small sizes and a
few hundred seeds, the store on Automerge by crafted changes and seeded runs, the
- vectors, and the check that every row has its test.
+ vectors, the corpus, and the check that every row has its test.
* `cargo sim`: the simulations.
* Longer runs, by hand or on a schedule: the properties and the store on Automerge with
many more seeds (a count from the environment), fuzzing, mutants.
diff --git a/src/federation/corpus.rs b/src/federation/corpus.rs
new file mode 100644
index 0000000..27c1ab7
--- /dev/null
+++ b/src/federation/corpus.rs
@@ -0,0 +1,238 @@
+//! What each revision of federation 1 takes, refuses and reads, as fixed bytes
+//! (`docs/federation-tests.md`, The corpus): for each revision this continuum knows, a file
+//! in `corpus/` of histories generated at that revision, each with what became of every
+//! event and what the store reads after, written once when the revision is made
+//! (`write_the_corpus`) and never edited after. Every later continuum judges them alike: a
+//! change to judging that alters what an earlier revision's corpus says comes as a later
+//! revision.
+
+use std::collections::BTreeMap;
+use std::fmt::Write as _;
+use std::path::PathBuf;
+
+use super::fold::Federation;
+use super::properties::{self, Kind};
+use super::revision::Revision;
+use super::store::Id;
+use super::store::memory::{Refusal, Store};
+use crate::testrand::Rng;
+
+/// The seeds each kind of history is generated from.
+const SEEDS: u64 = 4;
+
+/// The kinds of history generated: with an adversary or not, versions naming checkpoints
+/// or not, and versions this continuum doesn't read or not.
+fn kinds() -> Vec<Kind> {
+ let mut kinds = Vec::new();
+ for adversary in [false, true] {
+ for checkpoints in [false, true] {
+ for unread in [false, true] {
+ kinds.push(Kind {
+ adversary,
+ checkpoints,
+ unread,
+ });
+ }
+ }
+ }
+ kinds
+}
+
+fn dir() -> PathBuf {
+ PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("src/federation/corpus")
+}
+
+/// The file of `revision`'s corpus: by its number and the feature it adds, or `base`.
+fn file(revision: Revision) -> PathBuf {
+ let name = match revision.features().last() {
+ None => "0-base".to_owned(),
+ Some(feature) => format!("{}-{}", revision.0, feature.name()),
+ };
+ dir().join(format!("{name}.txt"))
+}
+
+/// The first line of `revision`'s corpus, naming it by its ID, so that a renamed feature
+/// fails as a changed judgment does.
+fn header(revision: Revision) -> String {
+ format!(
+ "continuum federation 1, {revision}, ID {}: never edited once released",
+ revision.id()
+ )
+}
+
+/// What became of `id` in `store`, by kind: never a refusal's words, which may change.
+fn became(store: &Store<Federation>, id: &Id) -> String {
+ if store.stopped().is_some_and(|(at, ..)| at == id) {
+ return "stopped at".to_owned();
+ }
+ if store.held_back().iter().any(|(held, _)| held == id) {
+ return "held back".to_owned();
+ }
+ if store.holds(id) {
+ return "taken".to_owned();
+ }
+ if store.get(id).is_some() {
+ return "kept".to_owned();
+ }
+ match store.refusal(id) {
+ Some(Refusal::None) => "refused: none".to_owned(),
+ Some(Refusal::Judged(_)) => "refused: judged".to_owned(),
+ Some(Refusal::BuiltOn(_)) => "refused: built on a refused one".to_owned(),
+ Some(Refusal::NotAbove) => "refused: not above the checkpoint".to_owned(),
+ Some(Refusal::Own) => "refused: its own".to_owned(),
+ Some(Refusal::Dropped) => "refused: dropped".to_owned(),
+ None if store.is_waiting(id) => "waiting".to_owned(),
+ None => "gone with a move".to_owned(),
+ }
+}
+
+/// What `store` reads: its checkpoint, the current version, the values at places, the
+/// members, and the event it stopped at; a line of JSON.
+fn reads(store: &Store<Federation>) -> String {
+ let state = store.state();
+ let values: BTreeMap<String, String> = state
+ .values()
+ .into_iter()
+ .map(|(path, value)| (path, String::from_utf8_lossy(&value.bytes()).into_owned()))
+ .collect();
+ serde_json::json!({
+ "checkpoint": Id::of(store.checkpoint()).to_string(),
+ "current": state.current().hash.to_string(),
+ "values": values,
+ "members": state.members(),
+ "stopped": store.stopped().map(|(id, ..)| id.to_string()),
+ })
+ .to_string()
+}
+
+/// A case: a root, and its events offered in the order written; what each became, and
+/// what the store reads after, as the corpus spells them.
+fn case(label: &str, root: &[u8], events: &[Vec<u8>]) -> String {
+ let mut store = Store::new(root.to_vec(), Vec::new()).expect("a root");
+ for event in events {
+ store.offer(event.clone());
+ }
+ let mut text = format!("case {label}\nroot {}\n", String::from_utf8_lossy(root));
+ for event in events {
+ let _ = writeln!(text, "event {}", String::from_utf8_lossy(event));
+ let _ = writeln!(text, "became {}", became(&store, &Id::of(event)));
+ }
+ let _ = writeln!(text, "reads {}", reads(&store));
+ text
+}
+
+/// `revision`'s corpus, generated: the histories of every kind and seed, the first
+/// version following `revision`.
+fn generated(revision: Revision) -> String {
+ let mut text = header(revision) + "\n";
+ for kind in kinds() {
+ for seed in 0..SEEDS {
+ let mut rng = Rng::new(seed);
+ let history = properties::generate_at(&mut rng, kind, Some(revision));
+ let label = format!("seed {seed}, {kind:?}");
+ text += &case(&label, &history.root, &history.events);
+ }
+ }
+ text
+}
+
+/// A corpus's cases, read: each its label, its root, and its events with what each
+/// became, and what the store reads after.
+struct Case {
+ label: String,
+ root: Vec<u8>,
+ events: Vec<(Vec<u8>, String)>,
+ reads: String,
+}
+
+fn parse(text: &str) -> Result<(String, Vec<Case>), String> {
+ let mut lines = text.lines();
+ let header = lines.next().ok_or("an empty corpus")?.to_owned();
+ let mut cases: Vec<Case> = Vec::new();
+ let mut event: Option<Vec<u8>> = None;
+ for line in lines {
+ let (word, rest) = line.split_once(' ').ok_or(format!("no line: {line:?}"))?;
+ let current = cases.last_mut();
+ match (word, current) {
+ ("case", _) => cases.push(Case {
+ label: rest.to_owned(),
+ root: Vec::new(),
+ events: Vec::new(),
+ reads: String::new(),
+ }),
+ ("root", Some(case)) => case.root = rest.as_bytes().to_vec(),
+ ("event", Some(_)) => event = Some(rest.as_bytes().to_vec()),
+ ("became", Some(case)) => {
+ let bytes = event.take().ok_or("`became` without its event")?;
+ case.events.push((bytes, rest.to_owned()));
+ }
+ ("reads", Some(case)) => case.reads = rest.to_owned(),
+ _ => return Err(format!("no line of a corpus: {line:?}")),
+ }
+ }
+ Ok((header, cases))
+}
+
+/// Writes the corpus of every revision this continuum knows that has none: once, when a
+/// revision is made, its file then committed and never edited. Run by hand:
+/// `cargo test --features federation write_the_corpus -- --ignored`.
+#[test]
+#[ignore = "writes into the source tree: run by hand when a revision is made"]
+fn write_the_corpus() {
+ std::fs::create_dir_all(dir()).expect("the corpus's directory");
+ for revision in Revision::known() {
+ let path = file(revision);
+ if !path.exists() {
+ std::fs::write(&path, generated(revision)).expect("the corpus written");
+ println!("wrote {}", path.display());
+ }
+ }
+}
+
+/// Every revision this continuum knows has its corpus, which it judges and reads as the
+/// corpus says.
+#[test]
+fn every_revision_judges_as_its_corpus_says() {
+ for revision in Revision::known() {
+ let path = file(revision);
+ let text = std::fs::read_to_string(&path).unwrap_or_else(|_| {
+ panic!(
+ "no corpus of {revision} ({}): write it once, as the revision is made, with \
+ `cargo test --features federation write_the_corpus -- --ignored`, and \
+ commit it",
+ path.display()
+ )
+ });
+ let (named, cases) = parse(&text).unwrap_or_else(|why| panic!("{}: {why}", path.display()));
+ assert_eq!(
+ named,
+ header(revision),
+ "{}: another revision",
+ path.display()
+ );
+ assert!(!cases.is_empty(), "{}: no case", path.display());
+ for case in cases {
+ let events: Vec<Vec<u8>> = case.events.iter().map(|(bytes, _)| bytes.clone()).collect();
+ let judged = self::case(&case.label, &case.root, &events);
+ let (_, again) = parse(&format!("{named}\n{judged}")).expect("as written");
+ let again = &again[0];
+ for ((bytes, was), (_, is)) in case.events.iter().zip(&again.events) {
+ assert_eq!(
+ was,
+ is,
+ "{}, {}: the event {} became otherwise",
+ path.display(),
+ case.label,
+ Id::of(bytes)
+ );
+ }
+ assert_eq!(
+ case.reads,
+ again.reads,
+ "{}, {}: the store reads otherwise",
+ path.display(),
+ case.label
+ );
+ }
+ }
+}
diff --git a/src/federation/mod.rs b/src/federation/mod.rs
index 2edc7c4..9444712 100644
--- a/src/federation/mod.rs
+++ b/src/federation/mod.rs
@@ -11,6 +11,8 @@ pub(crate) mod agent;
#[cfg(test)]
mod attacks;
pub(crate) mod client;
+#[cfg(test)]
+mod corpus;
pub(crate) mod event;
pub(crate) mod fold;
pub(crate) mod fork;
diff --git a/src/federation/properties.rs b/src/federation/properties.rs
index 214bb27..b45b664 100644
--- a/src/federation/properties.rs
+++ b/src/federation/properties.rs
@@ -17,7 +17,7 @@ use super::harness::{self, Party, Spec};
use super::held::Holding;
use super::jcs::Json;
use super::model::{Model, Verdict};
-use super::revision::Feature;
+use super::revision::{Feature, Revision};
use super::store::memory::{Offered, Refusal, Store};
use super::store::{Fold, Id};
use super::version::Version;
@@ -30,9 +30,9 @@ const MOST: usize = 30;
/// A root, and events in the order written.
#[derive(Clone)]
-struct History {
- root: Vec<u8>,
- events: Vec<Vec<u8>>,
+pub(super) struct History {
+ pub(super) root: Vec<u8>,
+ pub(super) events: Vec<Vec<u8>>,
}
impl History {
@@ -87,11 +87,11 @@ impl History {
/// 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,
+#[derive(Clone, Copy, Debug)]
+pub(super) struct Kind {
+ pub(super) adversary: bool,
+ pub(super) checkpoints: bool,
+ pub(super) unread: bool,
}
/// One of `ids`, of the latest five more often than not.
@@ -104,6 +104,12 @@ fn pick(rng: &mut Rng, ids: &[Id]) -> Id {
}
fn generate(rng: &mut Rng, kind: Kind) -> History {
+ generate_at(rng, kind, None)
+}
+
+/// A history of `kind`, its first version following `revision`, or, where none is given,
+/// the base revision or one with merge events alike.
+pub(super) fn generate_at(rng: &mut Rng, kind: Kind, revision: Option<Revision>) -> History {
let count = rng.between(3, 5);
let parties: Vec<Party> = (0..count)
.map(|i| Party::new(&format!("p{i}"), i as u8 + 1))
@@ -112,9 +118,12 @@ fn generate(rng: &mut Rng, kind: Kind) -> History {
let refs: Vec<&Party> = parties.iter().collect();
let mut first = Spec::first(&refs, &[("names/{party}", harness::str("{party}"))]);
// Half the federations begin at a revision with merge events, which nodes then sign.
- if rng.chance(0.5) {
- first.revision = Feature::MergeEvents.revision();
- }
+ let merging = rng.chance(0.5);
+ first.revision = revision.unwrap_or(if merging {
+ Feature::MergeEvents.revision()
+ } else {
+ Revision::default()
+ });
let root = first.root();
let root_id = Id::of(&root);
let mut world: Store<Federation> = Store::new(root.clone(), Vec::new()).expect("a root");