diff options
| author | tv <tv@krebsco.de> | 2026-11-17 00:17:21 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-17 01:46:02 +0100 |
| commit | ac95ca1d8d774e494f5719457a0bba64a3e690b7 (patch) | |
| tree | 3fb780320f044376308cf477a1005e630425925a /src/document/events.rs | |
| parent | 65b826f4a5bdd6f2ae2942df4a3975255e33c48f (diff) | |
document: the changes founding a fork's swarm, built from its root and what it keeps
A fork's root keeps events (`docs/store.md`, On Automerge): they follow its genesis
change in changes of the same writer, built the same way, filled in the order of their
IDs, events going into a change until their bytes there reach 1 MiB, the next event
beginning the next change (`events::founding`). A swarm holding a store starts from all
of them (`events::started`, given the events the root keeps; none for a federation's
root).
Diffstat (limited to 'src/document/events.rs')
| -rw-r--r-- | src/document/events.rs | 97 |
1 files changed, 88 insertions, 9 deletions
diff --git a/src/document/events.rs b/src/document/events.rs index ab8675b..81651f1 100644 --- a/src/document/events.rs +++ b/src/document/events.rs @@ -6,7 +6,10 @@ //! (`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. +//! 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; @@ -77,8 +80,20 @@ 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(); @@ -102,17 +117,49 @@ pub(crate) fn genesis(fold: &str, root: &[u8]) -> Change { 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(&[]) - .pop() - .expect("the genesis change was just made") } -/// A document holding the genesis change of a swarm holding a store of the fold `fold` -/// whose root is `root`, 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]) -> anyhow::Result<Document> { +/// 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([genesis(fold, root)])?; + doc.apply_changes(founding(fold, root, kept))?; Ok(doc.with_actor(ActorId::random())) } @@ -169,7 +216,7 @@ mod tests { #[test] fn the_genesis_change_writes_the_policy_the_swarm_and_the_root() { let id = Id::of(ROOT); - let doc = started("federation", ROOT).unwrap(); + 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(), @@ -205,4 +252,36 @@ mod tests { 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())); + } } |
