aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/fork.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/fork.rs')
-rw-r--r--src/federation/fork.rs162
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());
+ }
+}