//! 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, what the fork's version changes of the one current there, and so who writes the //! places holding a value, 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, /// What the fork's version changes of the version current at those heads, a line each /// (`client::changes`): its rules among them, whose order says who writes where. pub(crate) changes: Vec, /// Of the places holding a value there, those whose writer the fork's version changes, /// a line each (`client::writers`). pub(crate) writers: 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, what the fork's /// version changes of the one current there, and, party by party, whether it gives the /// party 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(), changes: Vec::new(), writers: Vec::new(), keys: Vec::new(), }); } let lacking = store.left_out(heads, store.taken()); let at = store.state_at(heads); let current = at.current(); let changes = super::client::changes(¤t.json, &version.json); let writers = super::client::writers(current, version, at.values().keys().map(String::as_str)); 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, changes, writers, 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(); // What the fork's version changes: what it changes, tv's node list, its number. let [changes, nodes, number] = check.changes.as_slice() else { panic!("{:?}", check.changes); }; assert_eq!(*changes, format!("changes: null -> \"{}\"", first.hash())); assert!(nodes.starts_with("nodes.tv: ") && nodes.ends_with(r#""since":1}"#)); assert_eq!(number, "number: 0 -> 1"); assert_eq!( check, Check { builds: true, why: None, lacking: Vec::new(), changes: check.changes.clone(), writers: Vec::new(), keys: Vec::new(), } ); assert!(super::check(&store, &first.root()).is_err()); } }