diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/federation/event.rs | 12 | ||||
| -rw-r--r-- | src/federation/fold.rs | 935 | ||||
| -rw-r--r-- | src/federation/mod.rs | 1 |
3 files changed, 947 insertions, 1 deletions
diff --git a/src/federation/event.rs b/src/federation/event.rs index b8e89f1..fc519d0 100644 --- a/src/federation/event.rs +++ b/src/federation/event.rs @@ -53,6 +53,16 @@ impl Event { /// back to itself, the signature doesn't hold, or it is larger than federation 1 /// allows. pub(crate) fn read(bytes: &[u8]) -> Option<Event> { + Self::parse(bytes, true) + } + + /// The event `bytes` are, as `read` reads them, but for its signature, which isn't + /// checked: for bytes a store took already, whose signature held then. + pub(crate) fn read_taken(bytes: &[u8]) -> Option<Event> { + Self::parse(bytes, false) + } + + fn parse(bytes: &[u8], verify: bool) -> Option<Event> { if bytes.len() > LARGEST { return None; } @@ -81,7 +91,7 @@ impl Event { return None; } let sig = json.get("sig")?.as_str()?; - if !keys::verifies(&public, sig, &json.without("sig").bytes()) { + if verify && !keys::verifies(&public, sig, &json.without("sig").bytes()) { return None; } let what = json.get(does)?; diff --git a/src/federation/fold.rs b/src/federation/fold.rs new file mode 100644 index 0000000..5f794e6 --- /dev/null +++ b/src/federation/fold.rs @@ -0,0 +1,935 @@ +//! 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<Id, Held>, + /// What the checkpoint keeps: in the history of every event after it. + before: BTreeSet<Id>, + /// The heads the checkpoint is at. + at: BTreeSet<Id>, + /// The checkpoint's version, which counts as written. + checkpoint: Id, + /// Every version written: the checkpoint's, and those its version events write. + versions: BTreeMap<Id, Version>, + /// The version events, by the version each writes. + writing: BTreeMap<Id, BTreeSet<Id>>, + /// What every proposal held proposes, by its hash. + proposed: BTreeMap<Id, Json>, +} + +/// 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<u64> = 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<Id> = 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<Id>) -> BTreeSet<Id> { + let mut above = BTreeSet::new(); + loop { + let more: Vec<Id> = 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<Item = (&Id, &Signed, &Id)> { + 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<Id> { + 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<Id> { + let given = current.parties.get(party)?; + let since = match list { + List::Keys => given.keys_since, + List::Nodes => given.nodes_since, + }; + let candidates: Vec<Id> = 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<String> { + 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`. + fn nodes_of(&self, party: &str, current: &Version) -> Vec<String> { + 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<Vec<String>, Id> { + let mut keys: BTreeMap<&str, Vec<String>> = BTreeMap::new(); + let mut places: BTreeMap<Vec<String>, Vec<Id>> = 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<String> = 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<String, Json> { + 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<Id> { + let mut ids: BTreeSet<Id> = 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() + } + + /// 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) + } + + /// Whether a proposal on `on` passed here: two thirds of the parties of `on` voted + /// `true`. + fn passed(&self, on: &Version, proposal: &Id) -> bool { + let (yes, _) = self.votes(&on.hash, proposal); + 3 * yes.len() >= 2 * on.parties.len() + } + + /// Whether a proposal on `on` is dead here: so many voted `false` that the rest can't + /// pass it. + fn dead(&self, on: &Version, proposal: &Id) -> bool { + let (_, no) = self.votes(&on.hash, proposal); + let parties = on.parties.len(); + 3 * (parties - no.len().min(parties)) < 2 * parties + } + + /// 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<Id> = 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.dead(current, other)) { + 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.passed(current, hash) { + 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<Id> = 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<Id> = 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 LARGEST: usize = event::LARGEST; + + fn dependencies(event: &[u8]) -> Option<Vec<Id>> { + 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<u8>, Vec<Id>) { + 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<Id>, Vec<Id>)> { + let checkpoint = Checkpoint::read(checkpoint)?; + Some((checkpoint.at, checkpoint.keeps)) + } + + fn start(checkpoint: &[u8], kept: &[(Id, Vec<u8>)]) -> Result<State, Refused> { + 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<u8>, Vec<Id>), 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<Vec<Id>> { + let heads = now.current().checkpoint.clone()?; + (heads.iter().copied().collect::<BTreeSet<Id>>() != 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<Federation> { + 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(_))) + } + + #[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<Federation>, 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!(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 = taken(store.offer(harness::version_event(&[yes, also], next.hash()))); + assert_eq!(store.state().current().number, 1); + 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<Federation> = + 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<Federation> = 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()); + } +} diff --git a/src/federation/mod.rs b/src/federation/mod.rs index 43f683a..2be6632 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -6,6 +6,7 @@ #![allow(dead_code)] pub(crate) mod event; +pub(crate) mod fold; #[cfg(test)] pub(crate) mod harness; pub(crate) mod jcs; |
