//! The federation as the store's fold (`docs/federation.md`; `docs/store.md`, The fold): //! its events, how one is judged at its history, what they read as, its checkpoints, and //! when the store moves to one. //! //! The state judging reads is the state of an event's history: the store builds it from //! the checkpoint and the events of that history alone, so "in its history" is "in the //! state", and the version current there is the state's. use std::collections::{BTreeMap, BTreeSet}; use super::event::{self, Checkpoint, Does, Event, Signed}; use super::jcs::{self, Json}; use super::store::{Fold, Id, Refused}; use super::version::Version; /// The federation, as a fold. pub(crate) struct Federation; /// An event a state holds, with what it is written under: the version current at its /// history. #[derive(Clone, Debug, PartialEq, Eq)] struct Held { event: Event, under: Id, } #[derive(Clone, Debug, PartialEq, Eq)] pub(crate) struct State { /// What the checkpoint keeps, and every event after it, by ID. events: BTreeMap, /// What the checkpoint keeps: in the history of every event after it. before: BTreeSet, /// The heads the checkpoint is at. at: BTreeSet, /// The checkpoint's version, which counts as written. checkpoint: Id, /// Every version written: the checkpoint's, and those its version events write. versions: BTreeMap, /// The version events, by the version each writes. writing: BTreeMap>, /// What every proposal held proposes, by its hash. proposed: BTreeMap, } /// A proposal on a version: the events proposing it, and the votes on it, by ID. #[derive(Clone, Debug, Default, PartialEq, Eq)] pub(crate) struct Ballot { pub(crate) proposals: Vec, pub(crate) votes: Vec, } /// What the votes on a proposal on a version make of it, as a store reads them. #[derive(Debug, PartialEq, Eq)] pub(crate) struct Tally<'a> { /// The parties voting `true`. pub(crate) yes: BTreeSet<&'a str>, /// The parties voting `false`. pub(crate) no: BTreeSet<&'a str>, /// Whether it passed: two thirds of the parties of the version voted `true`. pub(crate) passed: bool, /// Whether it is dead: so many voted `false` that the rest can't pass it. pub(crate) dead: bool, } /// A party's key set or node list. #[derive(Clone, Copy, PartialEq, Eq)] enum List { Keys, Nodes, } impl State { /// The version current: the written one with the highest number. pub(crate) fn current(&self) -> &Version { self.versions .values() .max_by_key(|version| (version.number, version.hash)) .expect("the checkpoint's version is written") } /// Whether two versions of one number are written here: no version is current. fn parted(&self) -> bool { let numbers: BTreeSet = self .versions .values() .map(|version| version.number) .collect(); numbers.len() < self.versions.len() } /// The version current at the history of `id` and `id` itself. fn after(&self, id: &Id) -> &Version { let checkpoint = &self.versions[&self.checkpoint]; let Some(held) = self.events.get(id) else { return checkpoint; }; let under = self.versions.get(&held.under).unwrap_or(checkpoint); match &held.event { Event::Version { version, .. } => match self.versions.get(version) { Some(written) if written.number > under.number => written, _ => under, }, Event::Signed(_) => under, } } /// What an event built on `deps` is written under: the version current at its history. fn under(&self, deps: &[Id]) -> Id { deps.iter() .map(|dep| self.after(dep)) .max_by_key(|version| (version.number, version.hash)) .map_or(self.checkpoint, |version| version.hash) } /// Whether `b` is in the history of `a`. fn built_on(&self, a: &Id, b: &Id) -> bool { // What the checkpoint keeps is in the history of every event after it. Of the // checkpoint's heads the state holds no history: as it tells, none builds on what // the checkpoint keeps, nor on another head. if self.before.contains(b) { return self.events.contains_key(a) && !self.before.contains(a); } let mut seen = BTreeSet::new(); let mut todo: Vec = self.deps(a).to_vec(); while let Some(next) = todo.pop() { if next == *b { return true; } if seen.insert(next) { todo.extend_from_slice(self.deps(&next)); } } false } fn deps(&self, id: &Id) -> &[Id] { self.events.get(id).map_or(&[], |held| held.event.deps()) } /// The events here above `heads` (`docs/store.md`, Events): each with them all in its /// history, and each of its dependencies one of them or above them. fn above(&self, heads: &BTreeSet) -> BTreeSet { let mut above = BTreeSet::new(); loop { let more: Vec = self .events .iter() .filter(|(id, held)| { let deps = held.event.deps(); !above.contains(*id) && !heads.contains(*id) && !self.before.contains(*id) && deps .iter() .all(|dep| heads.contains(dep) || above.contains(dep)) && (deps.iter().any(|dep| above.contains(dep)) || heads.iter().all(|head| deps.contains(head))) }) .map(|(id, _)| *id) .collect(); if more.is_empty() { return above; } above.extend(more); } } fn signed(&self) -> impl Iterator { self.events .iter() .filter_map(|(id, held)| match &held.event { Event::Signed(signed) => Some((id, signed, &held.under)), Event::Version { .. } => None, }) } /// Of `ids`, those no other of them has in its history, then the lowest ID: what counts /// of a party's writes at one place, of its key sets, and of its node lists. fn latest(&self, ids: &[Id]) -> Option { ids.iter() .filter(|id| { !ids.iter() .any(|other| other != *id && self.built_on(other, id)) }) .min() .copied() } /// The key set, or node list, of `party` that counts by `current`: one written under a /// version numbered at least the `since` it gives the party's. fn list(&self, party: &str, current: &Version, list: List) -> Option { let given = current.parties.get(party)?; let since = match list { List::Keys => given.keys_since, List::Nodes => given.nodes_since, }; let candidates: Vec = self .signed() .filter(|(_, signed, under)| { signed.party == party && matches!( (&signed.does, list), (Does::Keys(_), List::Keys) | (Does::Nodes(_), List::Nodes) ) && self .versions .get(under) .is_some_and(|version| version.number >= since) }) .map(|(id, _, _)| *id) .collect(); self.latest(&candidates) } /// The keys of `party` by `current`: those of its key set, or those its version names. pub(crate) fn keys_of(&self, party: &str, current: &Version) -> Vec { let Some(given) = current.parties.get(party) else { return Vec::new(); }; match self .list(party, current, List::Keys) .map(|id| &self.events[&id].event) { Some(Event::Signed(Signed { does: Does::Keys(keys), .. })) => keys.clone(), _ => given.keys.clone(), } } /// The node list of `party` by `current`. pub(crate) fn nodes_of(&self, party: &str, current: &Version) -> Vec { let Some(given) = current.parties.get(party) else { return Vec::new(); }; match self .list(party, current, List::Nodes) .map(|id| &self.events[&id].event) { Some(Event::Signed(Signed { does: Does::Nodes(nodes), .. })) => nodes.clone(), _ => given.nodes.clone(), } } /// The writes that count by `current`, by place: of each party's writes at a place its /// party may write, signed by a key among its party's, the latest. fn writes(&self, current: &Version) -> BTreeMap, Id> { let mut keys: BTreeMap<&str, Vec> = BTreeMap::new(); let mut places: BTreeMap, Vec> = BTreeMap::new(); for (id, signed, _) in self.signed() { let Does::Write { path, .. } = &signed.does else { continue; }; if current.writer(path) != Some(signed.party.as_str()) { continue; } let party_keys = keys .entry(signed.party.as_str()) .or_insert_with(|| self.keys_of(&signed.party, current)); if party_keys.contains(&signed.key) { places.entry(path.clone()).or_default().push(*id); } } places .into_iter() .filter_map(|(path, ids)| Some((path, self.latest(&ids)?))) .collect() } /// What a place holds: the value the write that counts there wrote, unless `null`. pub(crate) fn value(&self, path: &str) -> Option<&Json> { let path: Vec = path.split('/').map(str::to_owned).collect(); let id = *self.writes(self.current()).get(&path)?; match &self.events[&id].event { Event::Signed(Signed { does: Does::Write { value, .. }, .. }) if *value != Json::Null => Some(value), _ => None, } } /// Every place that holds a value, with it. pub(crate) fn values(&self) -> BTreeMap { self.writes(self.current()) .into_iter() .filter_map(|(path, id)| match &self.events[&id].event { Event::Signed(Signed { does: Does::Write { value, .. }, .. }) if *value != Json::Null => Some((path.join("/"), value.clone())), _ => None, }) .collect() } /// The events that count with `current` the version: the writes, key sets and node /// lists that count, and, with `proposals`, the proposals on it and the votes on it. fn counting(&self, current: &Version, proposals: bool) -> Vec { let mut ids: BTreeSet = self.writes(current).into_values().collect(); for party in current.parties.keys() { ids.extend(self.list(party, current, List::Keys)); ids.extend(self.list(party, current, List::Nodes)); } if proposals { for (id, signed, under) in self.signed() { let on_current = match &signed.does { Does::Proposal { .. } => *under == current.hash, Does::Vote { on, .. } => *on == current.hash, _ => false, }; if on_current { ids.insert(*id); } } } ids.into_iter().collect() } /// The proposals on `on`, by their hash, each with the events proposing it and the /// votes on it, by ID: what a party's client reads the votes it keeps from. pub(crate) fn ballots(&self, on: &Id) -> BTreeMap { let mut ballots: BTreeMap = BTreeMap::new(); for (id, signed, under) in self.signed() { match &signed.does { Does::Proposal { hash, .. } if under == on => { ballots.entry(*hash).or_default().proposals.push(*id); } Does::Vote { on: voted_on, proposal, .. } if voted_on == on => ballots.entry(*proposal).or_default().votes.push(*id), _ => {} } } ballots } /// The version event writing the proposal of hash `proposal` on the current version, /// where it passed here: on the `true` votes of the first parties by name that pass it, /// each party's of the lowest ID, so that nodes holding those votes write the same. pub(crate) fn version_event(&self, proposal: &Id) -> Option> { let current = self.current(); let mut yes: BTreeMap<&str, Id> = BTreeMap::new(); for (id, signed, _) in self.signed() { if let Does::Vote { on, proposal: voted, yes: true, } = &signed.does && *on == current.hash && voted == proposal { let lowest = yes.entry(signed.party.as_str()).or_insert(*id); *lowest = (*lowest).min(*id); } } let needed = (2 * current.parties.len()).div_ceil(3); if yes.len() < needed { return None; } let mut deps: Vec = yes.into_values().take(needed).collect(); deps.sort_unstable(); Some(event::version_event(&deps, *proposal)) } /// Whether a proposal of hash `proposal` is proposed on `on` here. fn proposed_on(&self, proposal: &Id, on: &Id) -> bool { self.signed().any(|(_, signed, under)| { matches!(&signed.does, Does::Proposal { hash, .. } if hash == proposal) && under == on }) } /// The parties voting `true`, and those voting `false`, on a proposal on a version. fn votes(&self, on: &Id, proposal: &Id) -> (BTreeSet<&str>, BTreeSet<&str>) { let mut yes = BTreeSet::new(); let mut no = BTreeSet::new(); for (_, signed, _) in self.signed() { if let Does::Vote { on: voted_on, proposal: voted, yes: vote, } = &signed.does && voted_on == on && voted == proposal { if *vote { yes.insert(signed.party.as_str()); } else { no.insert(signed.party.as_str()); } } } (yes, no) } /// What the votes here make of the proposal of hash `proposal` on `on`: who voted what, /// whether it passed, and whether it is dead. pub(crate) fn tally(&self, on: &Version, proposal: &Id) -> Tally<'_> { let (yes, no) = self.votes(&on.hash, proposal); let parties = on.parties.len(); Tally { passed: 3 * yes.len() >= 2 * parties, dead: 3 * (parties - no.len().min(parties)) < 2 * parties, yes, no, } } /// Whether a signed event is taken here, at its history, `current` the version current /// there. fn judge_signed(&self, signed: &Signed, current: &Version) -> Result<(), Refused> { let Some(given) = current.parties.get(&signed.party) else { return Err(Refused::new(format!( "{} is no party of the version current at its history", signed.party ))); }; let by_version = || { if given.keys.contains(&signed.key) { Ok(()) } else { Err(Refused::new( "not signed by a key its version names for its party", )) } }; match &signed.does { Does::Write { path, .. } => { if !self.keys_of(&signed.party, current).contains(&signed.key) { return Err(Refused::new("signed by a key that isn't its party's")); } if current.writer(path) != Some(signed.party.as_str()) { return Err(Refused::new(format!( "{} may not write at {}", signed.party, path.join("/") ))); } Ok(()) } Does::Keys(_) | Does::Nodes(_) | Does::Proposal { .. } => by_version(), Does::Vote { on, proposal, yes } => { by_version()?; if *on != current.hash { return Err(Refused::new( "on a version that isn't current at its history", )); } if !self.proposed_on(proposal, on) { return Err(Refused::new("its proposal isn't proposed on that version")); } if *yes { let backed: BTreeSet = self .signed() .filter_map(|(_, other, _)| match &other.does { Does::Vote { on: voted_on, proposal: voted, yes: true, } if other.party == signed.party && voted_on == on && voted != proposal => { Some(*voted) } _ => None, }) .collect(); if backed.iter().any(|other| !self.tally(current, other).dead) { return Err(Refused::new( "its party backs another proposal on that version, not dead", )); } } Ok(()) } } } /// Whether a version event is taken here, at its history, `current` the version current /// there. fn judge_version(&self, deps: &[Id], hash: &Id, current: &Version) -> Result<(), Refused> { if !self.proposed_on(hash, ¤t.hash) { return Err(Refused::new( "its proposal isn't proposed on the version current at its history", )); } 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}")))?; next.changes_validly(Some(current)) .map_err(|why| Refused::new(format!("no version: {why}")))?; if let Some(heads) = &next.checkpoint { self.may_move(heads, deps)?; } Ok(()) } /// Whether a version event on `deps` may write a version naming `heads` for a /// checkpoint: after the checkpoint current at its history, at which that one is /// current too, none in another's history; and the version event above them. fn may_move(&self, heads: &[Id], deps: &[Id]) -> Result<(), Refused> { if heads .iter() .any(|a| heads.iter().any(|b| a != b && self.built_on(a, b))) { return Err(Refused::new("checkpoint heads, one in another's history")); } let named: BTreeSet = heads.iter().copied().collect(); let latest = self .versions .values() .filter(|version| version.checkpoint.is_some()) .max_by_key(|version| version.number); let after = match latest .and_then(|version| Some((version, self.writing.get(&version.hash)?))) { // The version naming the current checkpoint is written here: the heads are above // its heads, and hold one of the events writing it. Some((version, writing)) => { let current: BTreeSet = version.checkpoint.iter().flatten().copied().collect(); let above = self.above(¤t); heads.iter().all(|head| above.contains(head)) && heads.iter().any(|head| { writing .iter() .any(|event| head == event || self.built_on(head, event)) }) } // It is in the history of the checkpoint the state starts from: the heads are // after that checkpoint, or its own, which a node starting from it takes as // after the one current at them, and at which that one is current too. None => { named == self.at || heads .iter() .all(|head| self.events.contains_key(head) && !self.before.contains(head)) } }; if !after { return Err(Refused::new( "checkpoint heads not after the current checkpoint, or at which it isn't current", )); } let above = self.above(&named); let is_above = deps .iter() .all(|dep| named.contains(dep) || above.contains(dep)) && (deps.iter().any(|dep| above.contains(dep)) || named.iter().all(|head| deps.contains(head))); if !is_above { return Err(Refused::new( "not above the heads of the checkpoint it names", )); } Ok(()) } /// The nodes each party's node list names, each with its party: the store's members. pub(crate) fn members(&self) -> Vec<(String, String)> { let current = self.current(); let mut members = Vec::new(); for party in current.parties.keys() { for node in self.nodes_of(party, current) { members.push((node, party.clone())); } } members } } impl Fold for Federation { type State = State; const NAME: &'static str = "federation"; const LARGEST: usize = event::LARGEST; fn dependencies(event: &[u8]) -> Option> { Event::read(event).map(|event| event.deps().to_vec()) } fn judge(at: &State, _id: &Id, bytes: &[u8]) -> Result<(), Refused> { let event = Event::read(bytes).ok_or_else(|| Refused::new("no event"))?; if at.parted() { return Err(Refused::new("its history holds two versions changing one")); } let current = at.current(); match &event { Event::Signed(signed) => at.judge_signed(signed, current), Event::Version { deps, version } => at.judge_version(deps, version, current), } } fn add(state: &mut State, id: &Id, bytes: &[u8]) { let Some(event) = Event::read_taken(bytes) else { return; }; let under = state.under(event.deps()); match &event { Event::Signed(Signed { does: Does::Proposal { hash, version }, .. }) => { state.proposed.insert(*hash, version.clone()); } Event::Version { version, .. } => { if let Some(written) = state .proposed .get(version) .and_then(|json| Version::read(json).ok()) { state.versions.insert(*version, written); } state.writing.entry(*version).or_default().insert(*id); } Event::Signed(_) => {} } state.events.insert(*id, Held { event, under }); } fn keeps(now: &State, _id: &Id, bytes: &[u8]) -> bool { match Event::read_taken(bytes) { Some(Event::Version { version, .. }) => { // One it took, written again; or one changing the version it reads. now.versions.contains_key(&version) || now .proposed .get(&version) .and_then(|json| Version::read(json).ok()) .is_some_and(|next| next.changes == Some(now.current().hash)) } _ => true, } } fn checkpoint(at: &State, heads: &[Id]) -> (Vec, Vec) { let current = at.current().clone(); let keeps = at.counting(¤t, true); let mut heads = heads.to_vec(); heads.sort(); let checkpoint = Checkpoint { at: heads, keeps: keeps.clone(), version: current, }; (checkpoint.bytes(), keeps) } fn parts(checkpoint: &[u8]) -> Option<(Vec, Vec)> { let checkpoint = Checkpoint::read(checkpoint)?; Some((checkpoint.at, checkpoint.keeps)) } fn start(checkpoint: &[u8], kept: &[(Id, Vec)]) -> Result { let checkpoint = Checkpoint::read(checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?; if checkpoint.at.is_empty() { checkpoint.version.changes_validly(None).map_err(|why| { Refused::new(format!("a root whose version isn't a first: {why}")) })?; if !checkpoint.keeps.is_empty() { return Err(Refused::new("a root without heads that keeps events")); } } let version = checkpoint.version.hash; let mut state = State { events: BTreeMap::new(), before: kept.iter().map(|(id, _)| *id).collect(), at: checkpoint.at.into_iter().collect(), checkpoint: version, versions: BTreeMap::from([(version, checkpoint.version)]), writing: BTreeMap::new(), proposed: BTreeMap::new(), }; for (id, bytes) in kept { // What a checkpoint keeps is read as written under its version. match Event::read_taken(bytes) { Some(Event::Signed(signed)) => { if let Does::Proposal { hash, version } = &signed.does { state.proposed.insert(*hash, version.clone()); } state.events.insert( *id, Held { event: Event::Signed(signed), under: version, }, ); } _ => return Err(Refused::new("a checkpoint keeps signed events only")), } } Ok(state) } fn fork(at: &State, heads: &[Id], spec: &[u8]) -> Result<(Vec, Vec), Refused> { let json = jcs::read(spec).ok_or_else(|| Refused::new("a fork's version that is no JSON"))?; let version = Version::read(&json).map_err(|why| Refused::new(format!("no version: {why}")))?; version .changes_validly(Some(at.current())) .map_err(|why| Refused::new(format!("no fork: {why}")))?; let keeps = at.counting(&version, false); let mut heads = heads.to_vec(); heads.sort(); let root = Checkpoint { at: heads, keeps: keeps.clone(), version, }; Ok((root.bytes(), keeps)) } fn moves_to(now: &State) -> Option> { let heads = now.current().checkpoint.clone()?; (heads.iter().copied().collect::>() != now.at).then_some(heads) } fn members(state: &State) -> Vec<(String, String)> { state.members() } } #[cfg(test)] mod tests { use super::super::harness::{self, Party, Spec}; use super::super::store::memory::{Offered, Refusal, Store}; use super::*; fn tv() -> Party { Party::new("tv", 1) } fn lass() -> Party { Party::new("lass", 2) } fn makefu() -> Party { Party::new("makefu", 3) } /// A federation started from the first version `spec` spells. fn federation(spec: &Spec) -> Store { let root = Checkpoint { at: Vec::new(), keeps: Vec::new(), version: Version::read(&spec.json()).expect("a version"), }; Store::new(root.bytes(), Vec::new()).expect("a root") } fn taken(offered: Offered) -> Id { match offered { Offered::Taken(ids) => ids[0], other => panic!("not taken: {other:?}"), } } fn judged(offered: Offered) -> bool { matches!(offered, Offered::Refused(Refusal::Judged(_))) } /// The proposals on a version, each with the events proposing it and the votes on it. #[test] fn ballots_name_proposals_and_their_votes() { let (tv, lass, makefu) = (tv(), lass(), makefu()); let spec = Spec::first(&[&tv, &lass, &makefu], &[]); let mut store = federation(&spec); let root = store.id(); let on = spec.hash(); let next = spec.after(on); let proposal = taken(store.offer(tv.propose(&[root], &next.json()))); let yes = taken(store.offer(lass.vote(&[proposal], on, next.hash(), true))); let no = taken(store.offer(makefu.vote(&[proposal], on, next.hash(), false))); let ballots = store.state().ballots(&on); assert_eq!(ballots.len(), 1); let ballot = &ballots[&next.hash()]; assert_eq!(ballot.proposals, vec![proposal]); let mut votes = vec![yes, no]; votes.sort(); assert_eq!(ballot.votes, votes); assert!(store.state().ballots(&next.hash()).is_empty()); } /// Who voted what on a proposal, and whether it passed or is dead. #[test] fn a_tally_names_the_votes_and_whether_a_proposal_passed_or_is_dead() { let (tv, lass, makefu) = (tv(), lass(), makefu()); let spec = Spec::first(&[&tv, &lass, &makefu], &[]); let mut store = federation(&spec); let root = store.id(); let on = spec.hash(); let one = spec.after(on); let mut two = spec.after(on); two.rules.clear(); let first = taken(store.offer(tv.propose(&[root], &one.json()))); let second = taken(store.offer(tv.propose(&[root], &two.json()))); let tally = |store: &Store, proposal: Id| { let state = store.state(); let tally = state.tally(state.current(), &proposal); let parties = |set: BTreeSet<&str>| -> Vec { set.into_iter().map(str::to_owned).collect() }; ( parties(tally.yes), parties(tally.no), tally.passed, tally.dead, ) }; assert_eq!(tally(&store, one.hash()), (vec![], vec![], false, false)); for (party, proposal, hash, yes) in [ (&lass, first, one.hash(), true), (&makefu, first, one.hash(), true), (&lass, second, two.hash(), false), (&makefu, second, two.hash(), false), ] { taken(store.offer(party.vote(&[proposal], on, hash, yes))); } let (lass, makefu) = ("lass".to_owned(), "makefu".to_owned()); assert_eq!( tally(&store, one.hash()), (vec![lass.clone(), makefu.clone()], vec![], true, false) ); assert_eq!( tally(&store, two.hash()), (vec![], vec![lass, makefu], false, true) ); } #[test] fn a_party_writes_where_a_rule_gives_it_the_place() { let (tv, lass) = (tv(), lass()); let spec = Spec::first(&[&tv, &lass], &[("names/r/wiki", harness::str("lass"))]); let mut store = federation(&spec); let root = store.id(); taken(store.offer(tv.write(&[root], "home/tv/laptop", harness::str("10.0.0.1")))); assert_eq!( store.state().value("home/tv/laptop"), Some(&harness::str("10.0.0.1")) ); assert!(judged(store.offer(tv.write( &[root], "home/lass/x", harness::str("1") )))); assert!(judged(store.offer(tv.write( &[root], "names/r/wiki", harness::str("1") )))); assert!(judged(store.offer(tv.write( &[root], "elsewhere", Json::Null )))); taken(store.offer(lass.write(&[root], "names/r/wiki", harness::str("w")))); // Who isn't in the policy writes nothing. let stranger = Party::new("makefu", 3); assert!(judged(store.offer(stranger.write( &[root], "home/makefu/x", harness::str("1") )))); } #[test] fn a_later_write_replaces_an_earlier_and_of_two_at_once_the_lower_id_counts() { let tv = tv(); let mut store = federation(&Spec::first(&[&tv], &[])); let root = store.id(); let first = taken(store.offer(tv.write(&[root], "home/tv/a", harness::str("1")))); taken(store.offer(tv.write(&[first], "home/tv/a", harness::str("2")))); assert_eq!(store.state().value("home/tv/a"), Some(&harness::str("2"))); let left = taken(store.offer(tv.write(&[root], "home/tv/b", harness::str("l")))); let right = taken(store.offer(tv.write(&[root], "home/tv/b", harness::str("r")))); let lower = if left < right { "l" } else { "r" }; assert_eq!(store.state().value("home/tv/b"), Some(&harness::str(lower))); taken(store.offer(tv.write(&[left, right], "home/tv/b", Json::Null))); assert_eq!(store.state().value("home/tv/b"), None); } #[test] fn a_key_set_says_what_a_party_signs_with() { let tv = tv(); let other = Party::new("tv", 9); let mut store = federation(&Spec::first(&[&tv], &[])); let root = store.id(); let before = taken(store.offer(tv.write(&[root], "home/tv/a", harness::str("1")))); // Signed with a key its version doesn't name, nor its set: refused. assert!(judged(store.offer(other.write( &[root], "home/tv/b", harness::str("1") )))); let set = taken(store.offer(tv.keys(&[before], &[other.key_line()]))); taken(store.offer(other.write(&[set], "home/tv/b", harness::str("2")))); // The key it dropped: refused after the set, and what it signed counts no more. assert!(judged(store.offer(tv.write( &[set], "home/tv/c", harness::str("3") )))); assert_eq!(store.state().value("home/tv/a"), None); assert_eq!(store.state().value("home/tv/b"), Some(&harness::str("2"))); // A set is signed by a key its version names. assert!(judged(store.offer(other.keys(&[set], &[other.key_line()])))); } /// A federation of tv, lass and makefu, and version 1 giving tv `names/r/x` proposed /// by tv: the store, the first version, the next, and the proposal's ID. fn proposed() -> (Store, Spec, Spec, Id) { let (tv, lass, makefu) = (tv(), lass(), makefu()); let first = Spec::first(&[&tv, &lass, &makefu], &[]); let mut next = first.after(first.hash()); next.rules .push(("names/r/x".to_owned(), harness::str("tv"))); let mut store = federation(&first); let root = store.id(); let proposal = taken(store.offer(tv.propose(&[root], &next.json()))); (store, first, next, proposal) } #[test] fn a_proposal_passes_by_two_thirds_and_its_version_changes_the_policy() { let (tv, lass, makefu) = (tv(), lass(), makefu()); let (mut store, first, next, proposal) = proposed(); let yes = taken(store.offer(tv.vote(&[proposal], first.hash(), next.hash(), true))); assert_eq!(store.state().version_event(&next.hash()), None); assert!(judged( store.offer(harness::version_event(&[yes], next.hash())) )); let no = taken(store.offer(makefu.vote(&[proposal], first.hash(), next.hash(), false))); assert!(judged( store.offer(harness::version_event(&[yes, no], next.hash())) )); let also = taken(store.offer(lass.vote(&[proposal], first.hash(), next.hash(), true))); let root = store.id(); assert!(judged(store.offer(tv.write( &[root], "names/r/x", harness::str("1") )))); let written = store.state().version_event(&next.hash()).expect("passed"); let mut deps = [yes, also]; deps.sort_unstable(); assert_eq!(written, harness::version_event(&deps, next.hash())); let written = taken(store.offer(written)); assert_eq!(store.state().current().number, 1); assert_eq!(store.state().version_event(&next.hash()), None); taken(store.offer(tv.write(&[written], "names/r/x", harness::str("1")))); assert_eq!(store.state().value("names/r/x"), Some(&harness::str("1"))); // A vote on the version that was current lapses with it. assert!(judged(store.offer(makefu.vote( &[written], first.hash(), next.hash(), true )))); } #[test] fn a_party_backs_one_proposal_at_a_time() { let (tv, lass, makefu) = (tv(), lass(), makefu()); let (mut store, first, next, proposal) = proposed(); let mut other = first.after(first.hash()); other .rules .push(("names/r/y".to_owned(), harness::str("lass"))); let root = store.id(); let second = taken(store.offer(lass.propose(&[root], &other.json()))); let yes = taken(store.offer(tv.vote(&[proposal, second], first.hash(), next.hash(), true))); assert!(judged(store.offer(tv.vote( &[yes], first.hash(), other.hash(), true )))); // Once the first is dead, its backer is free. let no = taken(store.offer(lass.vote(&[yes], first.hash(), next.hash(), false))); let nay = taken(store.offer(makefu.vote(&[no], first.hash(), next.hash(), false))); taken(store.offer(tv.vote(&[nay], first.hash(), other.hash(), true))); } #[test] fn of_two_versions_changing_one_a_node_keeps_the_first_it_takes() { let (tv, lass, makefu) = (tv(), lass(), makefu()); let (mut store, first, next, proposal) = proposed(); let mut other = first.after(first.hash()); other .rules .push(("names/r/y".to_owned(), harness::str("lass"))); let root = store.id(); let second = taken(store.offer(lass.propose(&[root], &other.json()))); // tv votes twice: `true` on both, neither knowing the other. let one = taken(store.offer(tv.vote(&[proposal], first.hash(), next.hash(), true))); let two = taken(store.offer(tv.vote(&[second], first.hash(), other.hash(), true))); let a = taken(store.offer(lass.vote(&[proposal], first.hash(), next.hash(), true))); let b = taken(store.offer(makefu.vote(&[second], first.hash(), other.hash(), true))); taken(store.offer(harness::version_event(&[one, a], next.hash()))); assert_eq!( store.offer(harness::version_event(&[two, b], other.hash())), Offered::Refused(Refusal::Own) ); assert_eq!(store.state().current().hash, next.hash()); } #[test] fn a_version_naming_a_checkpoint_moves_the_store_there() { let (tv, lass, makefu) = (tv(), lass(), makefu()); let first = Spec::first(&[&tv, &lass, &makefu], &[]); let mut store = federation(&first); let root = store.id(); let gone = taken(store.offer(tv.write(&[root], "home/tv/a", harness::str("1")))); let kept = taken(store.offer(tv.write(&[gone], "home/tv/a", harness::str("2")))); let head = taken(store.offer(lass.write(&[kept], "home/lass/b", harness::str("3")))); let beside = taken(store.offer(makefu.write(&[root], "home/makefu/c", harness::str("4")))); let mut next = first.after(first.hash()); next.checkpoint = Some(vec![head]); let proposal = taken(store.offer(tv.propose(&[head], &next.json()))); let yes = taken(store.offer(tv.vote(&[proposal], first.hash(), next.hash(), true))); let also = taken(store.offer(lass.vote(&[proposal], first.hash(), next.hash(), true))); let written = taken(store.offer(harness::version_event(&[yes, also], next.hash()))); assert_eq!( Federation::parts(store.checkpoint()).map(|(at, _)| at), Some(vec![head]) ); assert_eq!(store.state().value("home/tv/a"), Some(&harness::str("2"))); assert_eq!(store.state().value("home/lass/b"), Some(&harness::str("3"))); assert_eq!(store.refusal(&beside), Some(&Refusal::NotAbove)); assert_eq!(store.state().value("home/makefu/c"), None); assert_eq!(store.state().current().hash, next.hash()); // After it: taken; on what it forgot: not above it. taken(store.offer(tv.write(&[written], "home/tv/d", harness::str("5")))); assert_eq!( store.offer(tv.write(&[gone], "home/tv/e", harness::str("6"))), Offered::Refused(Refusal::NotAbove) ); // A node starting from that checkpoint reads the same, once it holds the same. let mut pinned: Store = Store::pinned(store.id(), store.checkpoint().to_vec(), store.kept()).expect("pinned"); for id in store.taken().to_vec() { pinned.offer(store.get(&id).expect("held").to_vec()); } assert_eq!(pinned.state().values(), store.state().values()); assert_eq!(pinned.taken().len(), store.taken().len()); } #[test] fn a_fork_keeps_what_counts_at_its_heads() { let (tv, lass) = (tv(), lass()); let first = Spec::first(&[&tv, &lass], &[]); let mut store = federation(&first); let root = store.id(); let here = taken(store.offer(tv.write(&[root], "home/tv/a", harness::str("1")))); let mut fork = first.after(first.hash()); fork.parties.retain(|party| party.name == "tv"); fork.parties[0].nodes_since = 1; let spec = fork.json().bytes(); let (fork_root, kept) = store.fork(&[here], &spec).expect("a fork"); let forked: Store = Store::new(fork_root, kept).expect("its root"); assert_eq!(forked.state().value("home/tv/a"), Some(&harness::str("1"))); assert_eq!(forked.state().current().parties.len(), 1); // A fork whose version doesn't change the one current at its heads is none. assert!(store.fork(&[here], &first.json().bytes()).is_err()); } }