diff options
Diffstat (limited to 'src/federation/fork.rs')
| -rw-r--r-- | src/federation/fork.rs | 162 |
1 files changed, 162 insertions, 0 deletions
diff --git a/src/federation/fork.rs b/src/federation/fork.rs new file mode 100644 index 0000000..59b744f --- /dev/null +++ b/src/federation/fork.rs @@ -0,0 +1,162 @@ +//! Forks (`docs/federation.md`, Forks): a node holding a federation's history makes the +//! root of a fork at heads it holds, by a version (`make`), and checks one it is given +//! (`check`): whether it builds that root at its heads, what it holds that those heads +//! lack, and, party by party, the keys the fork's version gives where they aren't the +//! keys the party had there. A node that doesn't hold that history takes a fork's root on +//! its operator's word, who names the fork by its root's ID (`--store-id`). +//! +//! A fork's founders start its swarm from a file holding its root on the first line, and +//! the events the root keeps, each on a line of its own (`--store-root`): JCS writes no +//! line break. + +use std::collections::BTreeSet; + +use super::event::Checkpoint; +use super::fold::Federation; +use super::jcs::Json; +use super::store::Id; +use super::store::memory::Store; + +/// The file a store's swarm starts from: its `root` on the first line, and each event of +/// `kept`, the events it keeps, on a line of its own. +pub(crate) fn root_file(root: &[u8], kept: &[Vec<u8>]) -> Vec<u8> { + let mut file = root.to_vec(); + file.push(b'\n'); + for event in kept { + file.extend_from_slice(event); + file.push(b'\n'); + } + file +} + +/// The root a file holds (`root_file`), and the events it keeps. +pub(crate) fn read_root_file(file: &[u8]) -> (Vec<u8>, Vec<Vec<u8>>) { + let mut lines = file + .split(|byte| *byte == b'\n') + .filter(|line| !line.is_empty()) + .map(<[u8]>::to_vec); + let root = lines.next().unwrap_or_default(); + (root, lines.collect()) +} + +/// The root of the fork at `heads` by `version`, as `store` builds it, with the events it +/// keeps: the file the fork's founders start its swarm from (`root_file`). +pub(crate) fn make( + store: &Store<Federation>, + heads: &[Id], + version: &Json, +) -> Result<Vec<u8>, String> { + let (root, kept) = store.fork(heads, &version.bytes()).map_err(|why| why.0)?; + Ok(root_file(&root, &kept)) +} + +/// What a node holding a federation's history finds of a fork's root. +#[derive(Debug, PartialEq, Eq)] +pub(crate) struct Check { + /// Whether it builds the root at its heads by its version, byte for byte; and why it + /// builds none, where it doesn't: heads it doesn't hold, or a version that is no fork. + pub(crate) builds: bool, + pub(crate) why: Option<String>, + /// What it holds that those heads lack: events it took that are neither among them, + /// nor in their history, nor above them. + pub(crate) lacking: Vec<Id>, + /// Each party whose keys the fork's version gives otherwise than the party had at + /// those heads, with its keys there and in the fork. + pub(crate) keys: Vec<(String, Vec<String>, Vec<String>)>, +} + +/// What `store` finds of the fork whose root is `root`: as a node holding the history up +/// to its heads builds it, says what it holds that those heads lack, and, party by party, +/// whether the fork's version gives it the keys it had there. +pub(crate) fn check(store: &Store<Federation>, root: &[u8]) -> Result<Check, String> { + let checkpoint = Checkpoint::read(root).ok_or("no checkpoint, so no fork's root")?; + if checkpoint.at.is_empty() { + return Err("a federation's root, at no heads: no fork's".to_owned()); + } + let heads = &checkpoint.at; + let version = &checkpoint.version; + let (builds, why) = match store.fork(heads, &version.json.bytes()) { + Ok((built, _)) => (built == root, None), + Err(why) => (false, Some(why.0)), + }; + if !heads.iter().all(|head| store.holds(head)) { + return Ok(Check { + builds, + why, + lacking: Vec::new(), + keys: Vec::new(), + }); + } + let lacking = store.left_out(heads, store.taken()); + let at = store.state_at(heads); + let current = at.current(); + let sorted = |mut keys: Vec<String>| { + keys.sort(); + keys + }; + let parties: BTreeSet<&String> = current + .parties + .keys() + .chain(version.parties.keys()) + .collect(); + let keys = parties + .into_iter() + .filter_map(|party| { + let there = if current.parties.contains_key(party) { + sorted(at.keys_of(party, current)) + } else { + Vec::new() + }; + let forked = sorted( + version + .parties + .get(party) + .map(|given| given.keys.clone()) + .unwrap_or_default(), + ); + (there != forked).then(|| (party.clone(), there, forked)) + }) + .collect(); + Ok(Check { + builds, + why, + lacking, + keys, + }) +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::federation::harness::{self, Party, Spec}; + + #[test] + fn a_fork_is_made_into_the_file_its_swarm_starts_from() { + let tv = Party::new("tv", 1); + let first = Spec::first(&[&tv], &[]); + let mut store = Store::<Federation>::new(first.root(), Vec::new()).unwrap(); + let write = tv.write(&[store.id()], "home/tv/x", harness::str("1")); + let head = Id::of(&write); + store.offer(write.clone()); + let mut spec = first.after(first.hash()); + spec.parties[0].nodes_since = 1; + let file = make(&store, &[head], &spec.json()).unwrap(); + let (root, kept) = read_root_file(&file); + assert_eq!(kept, vec![write]); + assert_eq!(root_file(&root, &kept), file); + assert!(store.checks_fork(&[head], &spec.json().bytes(), &root)); + assert_eq!(read_root_file(&first.root()), (first.root(), Vec::new())); + assert!(make(&store, &[Id::of(b"not held")], &spec.json()).is_err()); + let check = check(&store, &root).unwrap(); + assert_eq!( + check, + Check { + builds: true, + why: None, + lacking: Vec::new(), + keys: Vec::new(), + } + ); + assert!(super::check(&store, &first.root()).is_err()); + } +} |
