//! 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]) -> Vec { 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, Vec>) { 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, heads: &[Id], version: &Json, ) -> Result, 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, /// 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, /// 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, Vec)>, } /// 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, root: &[u8]) -> Result { 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| { 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::::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()); } }