aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/model.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/model.rs')
-rw-r--r--src/federation/model.rs530
1 files changed, 530 insertions, 0 deletions
diff --git a/src/federation/model.rs b/src/federation/model.rs
new file mode 100644
index 0000000..404bdb4
--- /dev/null
+++ b/src/federation/model.rs
@@ -0,0 +1,530 @@
+//! 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<Id, Event>,
+ refused: BTreeSet<Id>,
+ /// Events offered whose dependencies aren't all taken yet.
+ waiting: Vec<Vec<u8>>,
+}
+
+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<Id> {
+ 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<Id> {
+ 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<Version> {
+ 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<Id>) -> Vec<Version> {
+ 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<Id>) -> Option<Version> {
+ let versions = self.versions(history);
+ let numbers: BTreeSet<u64> = 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<Version> {
+ 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<Id> {
+ 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<Id>) -> impl Iterator<Item = (Id, &'a Signed)> {
+ 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<Id>,
+ party: &str,
+ version: &Version,
+ keys: bool,
+ ) -> Option<Id> {
+ let given = version.parties.get(party)?;
+ let since = if keys {
+ given.keys_since
+ } else {
+ given.nodes_since
+ };
+ let ids: Vec<Id> = 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<Id>, party: &str, version: &Version) -> Vec<String> {
+ 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<Id>,
+ on: &Id,
+ proposal: &Id,
+ ) -> (BTreeSet<String>, BTreeSet<String>) {
+ 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<Id>, 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<Id>, 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, &current)
+ .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, &current.hash) {
+ return false;
+ }
+ let (yes, _) = self.votes(history, &current.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(&current)).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<Id>, 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, &current)) {
+ return false;
+ }
+ let writing: Vec<Id> = 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<String, Json> {
+ let all = self.taken();
+ let current = self.version();
+ let mut places: BTreeMap<Vec<String>, Vec<Id>> = 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, &current)
+ .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<String> {
+ 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 &current.parties {
+ let nodes = match self
+ .list(&all, party, &current, 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
+ );
+ }
+}