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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
|
//! A swarm holding a store (`docs/store.md`, On Automerge): where its document holds the
//! store, and its genesis change, built byte for byte from the store's root, so that one
//! root makes one swarm.
//!
//! The genesis change writes, in this order and nothing else: the policy at its place
//! (`access::policy`), naming the fold; the swarm's ID, the root's, at `_continuum/swarm`;
//! and the root at its ID, as bytes; each making the maps on its way
//! (`store::write_path`). Its writer is the first 16 bytes of the root's ID, its time 0,
//! and it has no message. A fork's root keeps events, which follow in changes of the same
//! writer, built the same way, filled in the order of their IDs: events go into a change
//! until their bytes there reach 1 MiB, and the next event begins the next change. These
//! changes found the swarm; every node builds them, and nobody signs them.
use automerge::legacy::{Key, OpType};
use automerge::transaction::CommitOptions;
use automerge::{ObjId, ObjType, ScalarValue, Value};
use serde_json::Value as JsonValue;
use super::typed::{TimestampFormat, Val};
use super::{ActorId, Change, Document, ReadDoc, meta, store};
use crate::federation::store::Id;
/// Where the event `id` is.
pub(crate) fn event(id: &Id) -> Vec<String> {
meta::path(&[meta::EVENTS, &id.to_string()])
}
/// The map holding the events, if `doc` holds one.
fn events_map(doc: &impl ReadDoc) -> Option<ObjId> {
let map = |parent: &ObjId, key: &str| match doc.get(parent, key) {
Ok(Some((Value::Object(ObjType::Map), id))) => Some(id),
_ => None,
};
map(&map(&automerge::ROOT, meta::ROOT)?, meta::EVENTS)
}
/// The IDs of the events `doc` holds.
pub(crate) fn ids(doc: &impl ReadDoc) -> Vec<Id> {
events_map(doc).map_or_else(Vec::new, |events| {
doc.keys(&events)
.filter_map(|key| Id::from_hex(&key))
.collect()
})
}
/// The bytes `doc` holds at the event `id`.
pub(crate) fn bytes(doc: &impl ReadDoc, id: &Id) -> Option<Vec<u8>> {
match doc.get(&events_map(doc)?, id.to_string()) {
Ok(Some((Value::Scalar(value), _))) => match value.as_ref() {
ScalarValue::Bytes(bytes) => Some(bytes.clone()),
_ => None,
},
_ => None,
}
}
/// The events `change` puts: bytes, each at a key that is its ID.
pub(crate) fn carried(change: &Change) -> Vec<Vec<u8>> {
super::changes::decode(change)
.operations
.into_iter()
.filter_map(|op| match (op.key, op.action) {
(Key::Map(key), OpType::Put(ScalarValue::Bytes(bytes)))
if Id::of(&bytes).to_string() == key.as_str() =>
{
Some(bytes)
}
_ => None,
})
.collect()
}
/// The policy of a swarm holding a store of the fold `fold`.
pub(crate) fn policy(fold: &str) -> JsonValue {
serde_json::json!({"version": 2, "store": fold})
}
/// The writer of the genesis change of the store whose root is `id`.
pub(crate) fn genesis_writer(id: &Id) -> ActorId {
ActorId::from(&id.0[..16])
}
/// The bytes of events, once a change founding a swarm puts them, after which the next
/// event begins the next change.
const FOUNDING_BYTES: usize = 1024 * 1024;
/// The genesis change of a swarm holding a store of the fold `fold` whose root is `root`.
pub(crate) fn genesis(fold: &str, root: &[u8]) -> Change {
genesis_written(fold, root)
.get_changes(&[])
.pop()
.expect("the genesis change was just made")
}
/// A document holding the genesis change alone, written to under its writer.
fn genesis_written(fold: &str, root: &[u8]) -> Document {
let id = Id::of(root);
let mut doc = Document::new().with_actor(genesis_writer(&id));
let mut write = doc.transaction();
let writes = [
store::write_path(&mut write, &crate::access::policy::path(), &policy(fold)),
store::write_path(
&mut write,
&meta::path(&[meta::SWARM]),
&JsonValue::String(id.to_string()),
),
store::write_val_path(
&mut write,
&event(&id),
&Val::Scalar(ScalarValue::Bytes(root.to_vec())),
store::Writing::sticky(TimestampFormat::default()),
)
.map(|_| ()),
];
for written in writes {
// Into an empty document, under paths of maps only: nothing to refuse them.
written.expect("an empty document takes the genesis change's writes");
}
write.commit_with(CommitOptions::default().with_time(0));
doc
}
/// The changes founding a swarm holding a store of the fold `fold` whose root is `root`:
/// its genesis change, then, for a fork, the events the root keeps among `kept`, in the
/// order of their IDs, in changes of the genesis change's writer, at time 0, without a
/// message: events go into a change until their bytes there reach `FOUNDING_BYTES`.
pub(crate) fn founding(fold: &str, root: &[u8], kept: &[Vec<u8>]) -> Vec<Change> {
let mut kept: Vec<(Id, &[u8])> = kept
.iter()
.map(|bytes| (Id::of(bytes), bytes.as_slice()))
.collect();
kept.sort_unstable_by_key(|(id, _)| *id);
kept.dedup_by_key(|(id, _)| *id);
let mut doc = genesis_written(fold, root);
let mut rest = kept.as_slice();
while !rest.is_empty() {
let mut bytes = 0;
let mut write = doc.transaction();
while let Some(((id, event), after)) = rest.split_first()
&& bytes < FOUNDING_BYTES
{
store::write_val_path(
&mut write,
&self::event(id),
&Val::Scalar(ScalarValue::Bytes(event.to_vec())),
store::Writing::sticky(TimestampFormat::default()),
)
.expect("the events map takes an event at its ID");
bytes += event.len();
rest = after;
}
write.commit_with(CommitOptions::default().with_time(0));
}
doc.get_changes(&[])
}
/// A document holding the changes founding a swarm holding a store of the fold `fold`
/// whose root is `root`, keeping `kept` (`founding`), written to under a writer of its
/// own: the genesis change's is every node's, and writes nothing else.
pub(crate) fn started(fold: &str, root: &[u8], kept: &[Vec<u8>]) -> anyhow::Result<Document> {
let mut doc = Document::new();
doc.apply_changes(founding(fold, root, kept))?;
Ok(doc.with_actor(ActorId::random()))
}
/// The checkpoint `doc` holds at `_continuum/checkpoint`, where a remake's snapshot holds
/// one other than the root (`snapshot`).
pub(crate) fn checkpoint(doc: &impl ReadDoc) -> Option<Vec<u8>> {
let continuum = match doc.get(automerge::ROOT, meta::ROOT) {
Ok(Some((Value::Object(ObjType::Map), id))) => id,
_ => return None,
};
match doc.get(&continuum, meta::CHECKPOINT) {
Ok(Some((Value::Scalar(value), _))) => match value.as_ref() {
ScalarValue::Bytes(bytes) => Some(bytes.clone()),
_ => None,
},
_ => None,
}
}
/// The ID of the store `doc` holds, its swarm's, where it holds one.
pub(crate) fn swarm(doc: &impl ReadDoc) -> Option<Id> {
match store::read_plain(doc, &meta::path(&[meta::SWARM])) {
Ok(Some(JsonValue::String(swarm))) => Id::from_hex(&swarm),
_ => None,
}
}
/// Whether the change of hash `hash`, putting the events `written`, is one founding the
/// swarm whose root `doc` holds, `root`, keeping `keeps`: built byte for byte from the root
/// and the kept events `doc` holds or it puts, as every node builds them (`founding`).
pub(crate) fn is_founding(
doc: &impl ReadDoc,
fold: &str,
(root, keeps): (&[u8], &[Id]),
hash: &super::ChangeHash,
written: &[Vec<u8>],
) -> bool {
let kept: Vec<Vec<u8>> = keeps
.iter()
.filter_map(|keep| {
bytes(doc, keep)
.or_else(|| written.iter().find(|event| Id::of(event) == *keep).cloned())
})
.collect();
founding(fold, root, &kept)
.iter()
.any(|change| change.hash() == *hash)
}
/// Whether `change` is the genesis change of the swarm holding a store of the fold `fold`
/// whose root's ID is `id`: built again from the root it holds, byte for byte the same.
pub(crate) fn is_genesis(change: &Change, fold: &str, id: &Id) -> bool {
if !change.deps().is_empty() || *change.actor_id() != genesis_writer(id) {
return false;
}
let root = super::changes::decode(change)
.operations
.into_iter()
.find_map(|op| match op.action {
OpType::Put(ScalarValue::Bytes(bytes)) if Id::of(&bytes) == *id => Some(bytes),
_ => None,
});
root.is_some_and(|root| genesis(fold, &root).hash() == change.hash())
}
/// `events`, each at its ID, put into `doc` by one change.
#[cfg(test)]
pub(crate) fn put(doc: &mut Document, events: &[&[u8]]) {
super::testing::change(doc, |doc| {
for bytes in events {
store::write_val_path(
doc,
&event(&Id::of(bytes)),
&Val::Scalar(ScalarValue::Bytes(bytes.to_vec())),
store::Writing::sticky(TimestampFormat::default()),
)
.expect("an event written");
}
});
}
#[cfg(test)]
mod tests {
use super::*;
const ROOT: &[u8] = b"{\"a root\":true}";
#[test]
fn one_root_makes_one_genesis_change() {
let change = genesis("federation", ROOT);
assert_eq!(change.hash(), genesis("federation", ROOT).hash());
assert_eq!(change.timestamp(), 0);
assert_eq!(change.message(), None);
assert!(change.deps().is_empty());
assert_eq!(*change.actor_id(), genesis_writer(&Id::of(ROOT)));
assert_ne!(change.hash(), genesis("test", ROOT).hash());
assert_ne!(change.hash(), genesis("federation", b"another root").hash());
}
#[test]
fn the_genesis_change_writes_the_policy_the_swarm_and_the_root() {
let id = Id::of(ROOT);
let doc = started("federation", ROOT, &[]).unwrap();
assert_ne!(doc.get_actor(), &genesis_writer(&id));
assert_eq!(
store::read_plain(&doc, &crate::access::policy::path()).unwrap(),
Some(serde_json::json!({"store": "federation", "version": 2}))
);
assert_eq!(
store::read_plain(&doc, &meta::path(&[meta::SWARM])).unwrap(),
Some(JsonValue::String(id.to_string()))
);
assert_eq!(ids(&doc), vec![id]);
assert_eq!(bytes(&doc, &id).as_deref(), Some(ROOT));
assert_eq!(carried(&genesis("federation", ROOT)), vec![ROOT.to_vec()]);
}
#[test]
fn a_genesis_change_is_known_by_its_root() {
let id = Id::of(ROOT);
let change = genesis("federation", ROOT);
assert!(is_genesis(&change, "federation", &id));
assert!(!is_genesis(&change, "test", &id));
assert!(!is_genesis(&change, "federation", &Id::of(b"another root")));
// Another time, or more written: not it.
let mut doc = Document::new().with_actor(genesis_writer(&id));
let mut write = doc.transaction();
store::write_val_path(
&mut write,
&event(&id),
&Val::Scalar(ScalarValue::Bytes(ROOT.to_vec())),
store::Writing::sticky(TimestampFormat::default()),
)
.unwrap();
write.commit_with(CommitOptions::default().with_time(0));
let other = doc.get_changes(&[]).pop().unwrap();
assert!(!is_genesis(&other, "federation", &id));
}
/// A fork's root keeping three events of 600 KiB: founded by its genesis change, one
/// change holding the first two by ID, whose bytes reach 1 MiB, and one the third;
/// whatever order they are given in, the same changes.
#[test]
fn a_fork_is_founded_by_changes_every_node_builds() {
let mut kept: Vec<Vec<u8>> = (0..3u8).map(|n| vec![n; 600 * 1024]).collect();
kept.sort_by_key(|event| Id::of(event));
let changes = founding("federation", ROOT, &kept);
assert_eq!(changes.len(), 3);
assert_eq!(changes[0].hash(), genesis("federation", ROOT).hash());
let writer = genesis_writer(&Id::of(ROOT));
for (n, change) in changes.iter().enumerate().skip(1) {
assert_eq!(*change.actor_id(), writer);
assert_eq!(change.timestamp(), 0);
assert_eq!(change.message(), None);
assert_eq!(change.deps(), vec![changes[n - 1].hash()]);
}
assert_eq!(carried(&changes[1]), kept[..2].to_vec());
assert_eq!(carried(&changes[2]), kept[2..].to_vec());
let reversed: Vec<Vec<u8>> = kept.iter().rev().cloned().collect();
let hashes = |changes: &[Change]| changes.iter().map(Change::hash).collect::<Vec<_>>();
assert_eq!(
hashes(&founding("federation", ROOT, &reversed)),
hashes(&changes)
);
assert_eq!(founding("federation", ROOT, &[]).len(), 1);
let doc = started("federation", ROOT, &kept).unwrap();
let keeps: Vec<Id> = kept.iter().map(|event| Id::of(event)).collect();
assert!(keeps.iter().all(|id| bytes(&doc, id).is_some()));
assert_eq!(swarm(&doc), Some(Id::of(ROOT)));
// Each known at its history, by what it puts.
let mut before = Document::new();
before.apply_changes(changes[..2].to_vec()).unwrap();
let last = &changes[2];
assert!(is_founding(
&before,
"federation",
(ROOT, &keeps),
&last.hash(),
&carried(last)
));
assert!(!is_founding(
&before,
"federation",
(ROOT, &keeps[..2]),
&last.hash(),
&carried(last)
));
// All three in one change of the writer: not one of them.
let mut one = Document::new();
one.apply_changes([changes[0].clone()]).unwrap();
let mut write = one.transaction();
for event in &kept {
store::write_val_path(
&mut write,
&self::event(&Id::of(event)),
&Val::Scalar(ScalarValue::Bytes(event.clone())),
store::Writing::sticky(TimestampFormat::default()),
)
.unwrap();
}
write.commit_with(CommitOptions::default().with_time(0));
let crafted = one.get_changes(&[]).pop().unwrap();
let mut root_only = Document::new();
root_only.apply_changes([changes[0].clone()]).unwrap();
assert!(!is_founding(
&root_only,
"federation",
(ROOT, &keeps),
&crafted.hash(),
&kept
));
}
}
|