aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/fold.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/fold.rs')
-rw-r--r--src/federation/fold.rs935
1 files changed, 935 insertions, 0 deletions
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, &current.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(&current);
+ 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(&current, 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());
+ }
+}