//! 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. use std::collections::{BTreeMap, BTreeSet}; use super::event::{Checkpoint, Does, Event, Signed}; use super::jcs::Json; use super::store::Id; use super::version::Version; /// What became of an event offered to the model. #[derive(Clone, Debug, PartialEq, Eq)] pub(crate) enum Verdict { Taken, /// Taken already. Held, /// Some of its dependencies aren't taken yet. Waiting, Refused, } pub(crate) struct Model { root: Id, first: Version, /// The events taken, by ID. taken: BTreeMap, refused: BTreeSet, /// Events offered whose dependencies aren't all taken yet. waiting: Vec>, } impl Model { /// A model of the federation starting from `root`, a root without heads. pub(crate) fn new(root: &[u8]) -> Model { let checkpoint = Checkpoint::read(root).expect("a root"); assert!(checkpoint.at.is_empty() && checkpoint.keeps.is_empty()); Model { root: Id::of(root), first: checkpoint.version, taken: BTreeMap::new(), refused: BTreeSet::new(), waiting: Vec::new(), } } pub(crate) fn taken(&self) -> BTreeSet { self.taken.keys().copied().collect() } /// Offers an event; those waiting for it are taken or refused with it. pub(crate) fn offer(&mut self, bytes: &[u8]) -> Verdict { let verdict = self.consider(bytes); if verdict == Verdict::Waiting { self.waiting.push(bytes.to_vec()); } loop { let waiting = std::mem::take(&mut self.waiting); let before = waiting.len(); for event in waiting { if self.consider(&event) == Verdict::Waiting { self.waiting.push(event); } } if self.waiting.len() == before { return verdict; } } } fn consider(&mut self, bytes: &[u8]) -> Verdict { let id = Id::of(bytes); if self.taken.contains_key(&id) { return Verdict::Held; } if self.refused.contains(&id) { return Verdict::Refused; } let Some(event) = Event::read(bytes) else { self.refused.insert(id); return Verdict::Refused; }; let deps = event.deps(); if deps.iter().any(|dep| self.refused.contains(dep)) { self.refused.insert(id); return Verdict::Refused; } if !deps .iter() .all(|dep| *dep == self.root || self.taken.contains_key(dep)) { return Verdict::Waiting; } let history = self.history(deps); if self.judge(&history, &event, deps) && self.keeps(&event) { self.taken.insert(id, event); Verdict::Taken } else { self.refused.insert(id); Verdict::Refused } } /// The events taken among `ids` and all they build on. fn history(&self, ids: &[Id]) -> BTreeSet { let mut history = BTreeSet::new(); let mut todo = ids.to_vec(); while let Some(id) = todo.pop() { if let Some(event) = self.taken.get(&id) && history.insert(id) { todo.extend_from_slice(event.deps()); } } history } /// The version a version event writes: what the proposal of its hash holds. fn written(&self, hash: &Id) -> Option { self.taken.values().find_map(|event| match event { Event::Signed(Signed { does: Does::Proposal { hash: proposed, version, }, .. }) if proposed == hash => Version::read(version).ok(), _ => None, }) } /// The versions written in a history: the first, and those its version events write. fn versions(&self, history: &BTreeSet) -> Vec { let mut versions = vec![self.first.clone()]; for id in history { if let Some(Event::Version { version, .. }) = self.taken.get(id) && !versions.iter().any(|known| known.hash == *version) && let Some(written) = self.written(version) { versions.push(written); } } versions } /// The version current at a history: the written one with the highest number; none /// where two of one number are written there. fn current(&self, history: &BTreeSet) -> Option { let versions = self.versions(history); let numbers: BTreeSet = versions.iter().map(|version| version.number).collect(); if numbers.len() < versions.len() { return None; } versions.into_iter().max_by_key(|version| version.number) } /// The version an event is written under: the one current at its history. fn under(&self, id: &Id) -> Option { let event = self.taken.get(id)?; self.current(&self.history(event.deps())) } /// Whether `b` is in the history of `a`. fn builds_on(&self, a: &Id, b: &Id) -> bool { self.taken .get(a) .is_some_and(|event| self.history(event.deps()).contains(b)) } /// Of `ids`, those no other of them has in its history; of those, the lowest ID. fn latest(&self, ids: &[Id]) -> Option { ids.iter() .filter(|id| { !ids.iter() .any(|other| other != *id && self.builds_on(other, id)) }) .min() .copied() } /// The signed events of a history. fn signed<'a>(&'a self, history: &'a BTreeSet) -> impl Iterator { history.iter().filter_map(|id| match self.taken.get(id) { Some(Event::Signed(signed)) => Some((*id, signed)), _ => None, }) } /// The key set, or node list, of `party` that counts in a history by `version`. fn list( &self, history: &BTreeSet, party: &str, version: &Version, keys: bool, ) -> Option { let given = version.parties.get(party)?; let since = if keys { given.keys_since } else { given.nodes_since }; let ids: Vec = self .signed(history) .filter(|(id, signed)| { signed.party == party && match signed.does { Does::Keys(_) => keys, Does::Nodes(_) => !keys, _ => false, } && self.under(id).is_some_and(|under| under.number >= since) }) .map(|(id, _)| id) .collect(); self.latest(&ids) } /// The keys of `party` in a history by `version`. fn keys(&self, history: &BTreeSet, party: &str, version: &Version) -> Vec { let Some(given) = version.parties.get(party) else { return Vec::new(); }; match self .list(history, party, version, true) .map(|id| &self.taken[&id]) { Some(Event::Signed(Signed { does: Does::Keys(keys), .. })) => keys.clone(), _ => given.keys.clone(), } } /// The parties voting `true`, and `false`, on a proposal on `on` in a history. fn votes( &self, history: &BTreeSet, on: &Id, proposal: &Id, ) -> (BTreeSet, BTreeSet) { let mut yes = BTreeSet::new(); let mut no = BTreeSet::new(); for (_, signed) in self.signed(history) { if let Does::Vote { on: voted_on, proposal: voted, yes: vote, } = &signed.does && voted_on == on && voted == proposal { if *vote { yes.insert(signed.party.clone()); } else { no.insert(signed.party.clone()); } } } (yes, no) } fn proposed_on(&self, history: &BTreeSet, proposal: &Id, on: &Id) -> bool { self.signed(history).any(|(id, signed)| { matches!(&signed.does, Does::Proposal { hash, .. } if hash == proposal) && self.under(&id).is_some_and(|under| under.hash == *on) }) } /// The events taken above `heads`, by `store.md`'s Events: each with them all in its /// history, and each of its dependencies one of them or above them. fn is_above(&self, id: &Id, heads: &[Id]) -> bool { let Some(event) = self.taken.get(id) else { return false; }; if heads.contains(id) { return false; } let history = self.history(event.deps()); heads.iter().all(|head| history.contains(head)) && event .deps() .iter() .all(|dep| heads.contains(dep) || self.is_above(dep, heads)) } fn judge(&self, history: &BTreeSet, event: &Event, deps: &[Id]) -> bool { let Some(current) = self.current(history) else { return false; }; match event { Event::Signed(signed) => { let Some(given) = current.parties.get(&signed.party) else { return false; }; let by_version = given.keys.contains(&signed.key); match &signed.does { Does::Write { path, .. } => { self.keys(history, &signed.party, ¤t) .contains(&signed.key) && current.writer(path) == Some(signed.party.as_str()) } Does::Keys(_) | Does::Nodes(_) | Does::Proposal { .. } => by_version, Does::Vote { on, proposal, yes } => { by_version && *on == current.hash && self.proposed_on(history, proposal, on) && (!*yes || { // Every other proposal its party backs on that version is dead. self.signed(history).all(|(_, other)| match &other.does { Does::Vote { on: voted_on, proposal: voted, yes: true, } if other.party == signed.party && voted_on == on && voted != proposal => { let (_, no) = self.votes(history, on, voted); let parties = current.parties.len(); 3 * parties.saturating_sub(no.len()) < 2 * parties } _ => true, }) }) } } } Event::Version { version, .. } => { if !self.proposed_on(history, version, ¤t.hash) { return false; } let (yes, _) = self.votes(history, ¤t.hash, version); if 3 * yes.len() < 2 * current.parties.len() { return false; } let Some(next) = self.written(version) else { return false; }; if next.changes_validly(Some(¤t)).is_err() { return false; } match &next.checkpoint { None => true, Some(heads) => self.may_name(history, heads, deps), } } } } /// Whether a version event on `deps`, at a history, may name `heads` for a checkpoint. fn may_name(&self, history: &BTreeSet, heads: &[Id], deps: &[Id]) -> bool { // None in another's history. if heads .iter() .any(|a| heads.iter().any(|b| a != b && self.builds_on(a, b))) { return false; } // After the current checkpoint: that the last version of the history's chain // naming one names, or the root; and at which that one is current too. let latest = self .versions(history) .into_iter() .filter(|version| version.checkpoint.is_some()) .max_by_key(|version| version.number); if let Some(latest) = latest { let current = latest.checkpoint.clone().unwrap_or_default(); if !heads.iter().all(|head| self.is_above(head, ¤t)) { return false; } let writing: Vec = history .iter() .filter(|id| { matches!(self.taken.get(id), Some(Event::Version { version, .. }) if *version == latest.hash) }) .copied() .collect(); let holds = heads.iter().any(|head| { writing .iter() .any(|event| head == event || self.builds_on(head, event)) }); if !holds { return false; } } else if !heads.iter().all(|head| self.taken.contains_key(head)) { return false; } // The version event above them. let mut history_of_it = BTreeSet::new(); for dep in deps { history_of_it.insert(*dep); history_of_it.extend(self.history(&[*dep])); } heads.iter().all(|head| history_of_it.contains(head)) && deps .iter() .all(|dep| heads.contains(dep) || self.is_above(dep, heads)) } /// 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 { let Event::Version { version, .. } = event else { return true; }; let all = self.taken(); let versions = self.versions(&all); if versions.iter().any(|known| known.hash == *version) { return true; } let Some(current) = self.current(&all) else { return false; }; self.written(version) .is_some_and(|next| next.changes == Some(current.hash)) } /// The version current over everything taken. pub(crate) fn version(&self) -> Version { self.current(&self.taken()) .expect("one version of each number") } /// What counts: each place's value, unless `null`. pub(crate) fn values(&self) -> BTreeMap { let all = self.taken(); let current = self.version(); let mut places: BTreeMap, Vec> = BTreeMap::new(); for (id, signed) in self.signed(&all) { if let Does::Write { path, .. } = &signed.does && current.writer(path) == Some(signed.party.as_str()) && self .keys(&all, &signed.party, ¤t) .contains(&signed.key) { places.entry(path.clone()).or_default().push(id); } } places .into_iter() .filter_map(|(path, ids)| { let id = self.latest(&ids)?; match &self.taken[&id] { Event::Signed(Signed { does: Does::Write { value, .. }, .. }) if *value != Json::Null => Some((path.join("/"), value.clone())), _ => None, } }) .collect() } /// The keys of `party` over everything taken. pub(crate) fn keys_of(&self, party: &str) -> Vec { self.keys(&self.taken(), party, &self.version()) } /// The members: each node a party's node list names, with its party. pub(crate) fn members(&self) -> BTreeSet<(String, String)> { let all = self.taken(); let current = self.version(); let mut members = BTreeSet::new(); for (party, given) in ¤t.parties { let nodes = match self .list(&all, party, ¤t, false) .map(|id| &self.taken[&id]) { Some(Event::Signed(Signed { does: Does::Nodes(nodes), .. })) => nodes.clone(), _ => given.nodes.clone(), }; for node in nodes { members.insert((node, party.clone())); } } members } } #[cfg(test)] mod tests { use super::super::harness::{self, Party, Spec}; use super::*; #[test] fn the_model_reads_a_version_passing_and_a_write_after_it() { let (tv, lass) = (Party::new("tv", 1), Party::new("lass", 2)); let first = Spec::first(&[&tv, &lass], &[]); let root = Checkpoint { at: Vec::new(), keeps: Vec::new(), version: Version::read(&first.json()).expect("a version"), } .bytes(); let mut model = Model::new(&root); let root = Id::of(&root); let mut next = first.after(first.hash()); next.rules.push(("names/x".to_owned(), harness::str("tv"))); let proposal = tv.propose(&[root], &next.json()); let p = Id::of(&proposal); let votes = [ tv.vote(&[p], first.hash(), next.hash(), true), lass.vote(&[p], first.hash(), next.hash(), true), ]; let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], next.hash()); let write = tv.write(&[Id::of(&written)], "names/x", harness::str("1")); // Offered last first: each waits until what it builds on is taken. assert_eq!(model.offer(&write), Verdict::Waiting); assert_eq!(model.offer(&written), Verdict::Waiting); assert_eq!(model.offer(&votes[1]), Verdict::Waiting); assert_eq!(model.offer(&votes[0]), Verdict::Waiting); assert_eq!(model.offer(&proposal), Verdict::Taken); assert_eq!(model.taken().len(), 5); assert_eq!(model.version().number, 1); assert_eq!(model.values().get("names/x"), Some(&harness::str("1"))); // Too early: at the root's history nobody writes there. assert_eq!( model.offer(&tv.write(&[root], "names/x", harness::str("2"))), Verdict::Refused ); } }