aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/fork.rs
blob: 59b744f7935d668720779908ea4eaef94392c447 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
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());
    }
}