//! 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 { meta::path(&[meta::EVENTS, &id.to_string()]) } /// The map holding the events, if `doc` holds one. fn events_map(doc: &impl ReadDoc) -> Option { 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 { 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> { 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> { 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]) -> 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(&[]) } /// 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(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> { 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 { 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], ) -> bool { let kept: Vec> = 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> = (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())); 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 )); } }