aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/store/mod.rs
blob: ec3fb567a11617297dff9dc3564c970c7af34772 (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
//! The store (`docs/store.md`): events, each named by the hash of its bytes and naming
//! the events it builds on, judged at that history, and read as one state by a fold the
//! store is generic over.

use std::fmt;

use sha2::{Digest, Sha256};

use crate::transport::Hex;

pub(crate) mod memory;
#[cfg(test)]
mod properties;
#[cfg(test)]
pub(crate) mod testfold;

/// An event's name: the SHA-256 of its bytes, written as 64 lower-case hex digits.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) struct Id(pub(crate) [u8; 32]);

impl Id {
    /// The ID of `bytes`.
    pub(crate) fn of(bytes: &[u8]) -> Self {
        Self(Sha256::digest(bytes).into())
    }

    /// From 64 lower-case hex digits, and nothing else spelled otherwise.
    pub(crate) fn from_hex(text: &str) -> Option<Self> {
        let digits = text.as_bytes();
        if digits.len() != 64 {
            return None;
        }
        let value = |digit: u8| match digit {
            b'0'..=b'9' => Some(digit - b'0'),
            b'a'..=b'f' => Some(digit - b'a' + 10),
            _ => None,
        };
        let mut id = [0; 32];
        for (byte, pair) in id.iter_mut().zip(digits.chunks(2)) {
            *byte = value(pair[0])? << 4 | value(pair[1])?;
        }
        Some(Self(id))
    }
}

impl fmt::Display for Id {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(&Hex(&self.0), f)
    }
}

impl fmt::Debug for Id {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}

/// Why a fold takes an event not, or a checkpoint not: in words, for reports.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Refused(pub(crate) String);

impl Refused {
    pub(crate) fn new(why: impl Into<String>) -> Self {
        Self(why.into())
    }
}

/// What the events of a store are, how one is judged, what they read as, and when the
/// store moves to a later checkpoint (`docs/store.md`, The fold).
pub(crate) trait Fold {
    /// What a checkpoint and the events after it read as. It carries what judging and
    /// reading need of the events' history.
    type State: Clone;

    /// Its name, by which a swarm holding a store names its fold (`docs/store.md`, On
    /// Automerge).
    const NAME: &'static str;

    /// The most bytes an event may have: larger ones are none.
    const LARGEST: usize;

    /// What the event builds on; `None` where its bytes are none of this fold's events.
    fn dependencies(event: &[u8]) -> Option<Vec<Id>>;

    /// Whether the event is taken where its history reads as `at`.
    fn judge(at: &Self::State, id: &Id, event: &[u8]) -> Result<(), Refused>;

    /// Adds the event, whose dependencies are added already. Events neither of which
    /// builds on the other may come in either order: the state is the same.
    fn add(state: &mut Self::State, id: &Id, event: &[u8]);

    /// Whether a node whose store reads as `now` takes an event its history takes.
    fn keeps(_now: &Self::State, _id: &Id, _event: &[u8]) -> bool {
        true
    }

    /// The checkpoint at `heads`, read as `at`: its bytes, and the events it keeps.
    fn checkpoint(at: &Self::State, heads: &[Id]) -> (Vec<u8>, Vec<Id>);

    /// The heads a checkpoint was built at, and the events it keeps; `None` where its
    /// bytes are no checkpoint.
    fn parts(checkpoint: &[u8]) -> Option<(Vec<Id>, Vec<Id>)>;

    /// The state a checkpoint reads as, with the events it keeps.
    fn start(checkpoint: &[u8], kept: &[(Id, Vec<u8>)]) -> Result<Self::State, Refused>;

    /// The root of a fork at `heads` of the store reading as `at`, made by `spec`: its
    /// bytes, and the events it keeps.
    fn fork(at: &Self::State, heads: &[Id], spec: &[u8]) -> Result<(Vec<u8>, Vec<Id>), Refused>;

    /// The heads of a later checkpoint, where a store reading as `now` moves to one.
    fn moves_to(now: &Self::State) -> Option<Vec<Id>>;

    /// The nodes that carry the store, each with its group.
    fn members(state: &Self::State) -> Vec<(String, String)>;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn an_id_reads_back_from_its_hex() {
        let id = Id::of(b"an event");
        assert_eq!(id.to_string().len(), 64);
        assert_eq!(Id::from_hex(&id.to_string()), Some(id));
        let upper = id.to_string().to_uppercase();
        if upper != id.to_string() {
            assert_eq!(Id::from_hex(&upper), None);
        }
        assert_eq!(Id::from_hex(&id.to_string()[1..]), None);
        assert_eq!(Id::from_hex(&format!("{id}0")), None);
    }
}