From ac95ca1d8d774e494f5719457a0bba64a3e690b7 Mon Sep 17 00:00:00 2001 From: tv Date: Tue, 17 Nov 2026 00:17:21 +0000 Subject: 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). --- src/access/holding.rs | 2 +- src/access/token.rs | 2 +- src/document/events.rs | 97 ++++++++++++++++++++++++++++++++++++++++---- src/federation/held.rs | 22 +++++----- src/federation/properties.rs | 2 +- src/simtest/holding.rs | 4 +- src/swarm/bootstrap.rs | 2 +- 7 files changed, 105 insertions(+), 26 deletions(-) (limited to 'src') diff --git a/src/access/holding.rs b/src/access/holding.rs index 9f01a0a..3c6fd13 100644 --- a/src/access/holding.rs +++ b/src/access/holding.rs @@ -124,7 +124,7 @@ mod tests { /// A swarm holding a store, from its genesis change. fn swarm() -> Document { - events::started("federation", ROOT).unwrap() + events::started("federation", ROOT, &[]).unwrap() } /// The change `node` writes to `doc` with `f`, judged as every node judges it. diff --git a/src/access/token.rs b/src/access/token.rs index 0b6521a..0920410 100644 --- a/src/access/token.rs +++ b/src/access/token.rs @@ -295,7 +295,7 @@ mod tests { fn store_attack_17() { let key = NodeKey::from_seed([1; 32]); let other = NodeKey::from_seed([2; 32]); - let mut doc = crate::document::events::started("federation", b"a root").unwrap(); + let mut doc = crate::document::events::started("federation", b"a root", &[]).unwrap(); member(&mut doc, &key); member(&mut doc, &other); let token = issue(&key, &claims(&key)); 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]) -> Vec { + 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 { +/// 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]) -> anyhow::Result { 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> = (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> = kept.iter().rev().cloned().collect(); + let hashes = |changes: &[Change]| changes.iter().map(Change::hash).collect::>(); + 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 = kept.iter().map(|event| Id::of(event)).collect(); + assert!(keeps.iter().all(|id| bytes(&doc, id).is_some())); + } } diff --git a/src/federation/held.rs b/src/federation/held.rs index ba7837b..29464ea 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -861,7 +861,7 @@ mod tests { lass.vote(&[Id::of(&proposal)], on, next.hash(), true), ]; let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], next.hash()); - let mut doc = events::started(Federation::NAME, &root).unwrap(); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); for event in [&gone, &kept, &head, &beside, &proposal] .into_iter() .chain(&votes) @@ -904,7 +904,7 @@ mod tests { let on = tv.write(&[Id::of(&write)], "home/tv/x", harness::str("2")); let holding = Holding::default(); assert_eq!(holding.offer(write.clone()), None); - let mut doc = events::started(Federation::NAME, &root).unwrap(); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); put(&mut doc, &write); read(&holding, &doc, 0); assert!(matches!(holding.offer(on.clone()), Some(Offered::Taken(_)))); @@ -932,12 +932,12 @@ mod tests { let root = first.root(); let write = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); let on = tv.write(&[Id::of(&write)], "home/tv/x", harness::str("2")); - let mut left = events::started(Federation::NAME, &root).unwrap(); + let mut left = events::started(Federation::NAME, &root, &[]).unwrap(); put(&mut left, &write); let holding = Holding::default(); read(&holding, &left, 0); // Another document, without it; and a refused change carrying what builds on it. - let doc = events::started(Federation::NAME, &root).unwrap(); + let doc = events::started(Federation::NAME, &root, &[]).unwrap(); let mut elsewhere = left.fork(); put(&mut elsewhere, &on); let carrying = elsewhere.get_last_local_change().unwrap().clone(); @@ -955,7 +955,7 @@ mod tests { let tv = Party::new("tv", 1); let first = Spec::first(&[&tv], &[]); let root = first.root(); - let mut doc = events::started(Federation::NAME, &root).unwrap(); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); let holding = Holding::default(); assert!(holding.unread(&Document::new(), 0).is_none()); read(&holding, &doc, 0); @@ -1015,7 +1015,7 @@ mod tests { let taken = |holding: &Holding| holding.with(|store| store.taken().to_vec()).unwrap(); // The one a store reading all of them at once takes, and the other, which a node // took as it came first. - let mut all = events::started(Federation::NAME, &root).unwrap(); + let mut all = events::started(Federation::NAME, &root, &[]).unwrap(); for event in before.iter().copied().chain([&v1, &v2]) { put(&mut all, event); } @@ -1031,7 +1031,7 @@ mod tests { let path = dir.join("store.json"); let files = Arc::new(Files::default()); let holding = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap(); - let mut doc = events::started(Federation::NAME, &root).unwrap(); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); for event in before.iter().copied().chain([&first_taken]) { put(&mut doc, event); } @@ -1057,7 +1057,7 @@ mod tests { fn tv_alone() -> (Party, Vec, Document) { let tv = Party::new("tv", 1); let root = Spec::first(&[&tv], &[]).root(); - let doc = events::started(Federation::NAME, &root).unwrap(); + let doc = events::started(Federation::NAME, &root, &[]).unwrap(); (tv, root, doc) } @@ -1150,7 +1150,7 @@ mod tests { read(&holding, &doc, 0); holding.drop_taken(&[Id::of(&write)]).unwrap().unwrap(); // Another document, the event in another change. - let mut again = events::started(Federation::NAME, &root).unwrap(); + let mut again = events::started(Federation::NAME, &root, &[]).unwrap(); events::put(&mut again, &[&write, &on]); read(&holding, &again, 1); assert_eq!(holding.with(|store| store.taken().len()), Some(0)); @@ -1177,7 +1177,7 @@ mod tests { lass.vote(&[Id::of(&proposal)], on, next.hash(), true), ]; let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], next.hash()); - let mut doc = events::started(Federation::NAME, &root).unwrap(); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); for event in [&head, &proposal] .into_iter() .chain(&votes) @@ -1218,7 +1218,7 @@ mod tests { two.rules.push(("names/x".to_owned(), harness::str("tv"))); let p1 = tv.propose(&[Id::of(&root)], &one.json()); let p2 = lass.propose(&[Id::of(&root)], &two.json()); - let mut doc = events::started(Federation::NAME, &root).unwrap(); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); for event in [ &p1, &p2, diff --git a/src/federation/properties.rs b/src/federation/properties.rs index 36724ff..db11251 100644 --- a/src/federation/properties.rs +++ b/src/federation/properties.rs @@ -403,7 +403,7 @@ fn a_store_read_from_its_document_holds_what_one_given_the_events_alone_holds() |history| { let alone = holds(&history.store(&history.written()).0); let mut rng = Rng::new(history.events.len() as u64); - let started = events::started(Federation::NAME, &history.root).expect("a root"); + let started = events::started(Federation::NAME, &history.root, &[]).expect("a root"); let mut docs = [started.fork(), started.fork()]; let holdings = [Holding::default(), Holding::default()]; let read = |holdings: &[Holding; 2], docs: &[_; 2]| { diff --git a/src/simtest/holding.rs b/src/simtest/holding.rs index f70ef0d..3e25f20 100644 --- a/src/simtest/holding.rs +++ b/src/simtest/holding.rs @@ -101,7 +101,7 @@ fn of_the_store(config: &mut NodeConfig, id: Id, root: Option<&[u8]>, holding: H config.store = Some(id); config.holding = holding; if let Some(root) = root { - config.initial_doc = events::started(Federation::NAME, root).expect("a root"); + config.initial_doc = events::started(Federation::NAME, root, &[]).expect("a root"); } } @@ -640,7 +640,7 @@ async fn store_attack_10() { vec![("a", holding("tv")), ("b", holding("lass"))], ) .await; - let one = events::started(Federation::NAME, &root).expect("a root"); + let one = events::started(Federation::NAME, &root, &[]).expect("a root"); for name in ["x1", "x2"] { sim.net.take_down(name); let doc = one.clone(); diff --git a/src/swarm/bootstrap.rs b/src/swarm/bootstrap.rs index e6d5d21..1deb390 100644 --- a/src/swarm/bootstrap.rs +++ b/src/swarm/bootstrap.rs @@ -333,7 +333,7 @@ impl StoreStart { return Ok(None); }; use crate::federation::store::Fold; - let doc = document::events::started(crate::federation::fold::Federation::NAME, root)?; + let doc = document::events::started(crate::federation::fold::Federation::NAME, root, &[])?; info!(swarm_id = %swarm_id, "Starting the swarm holding the store from its root (--store-root)"); Ok(Some(StartingDocument { doc, -- cgit v1.3.1