//! Changes as bytes, to send and to load (`swarm::blob` moves them): one change by its //! hash, checked against it when it arrives, and a delta, the changes between two sets //! of heads, the same bytes on every node holding them. use std::collections::{HashMap, HashSet}; use anyhow::{Result, anyhow, bail}; use super::{ActorId, Change, ChangeHash, Document, ExpandedChange, ReadDoc}; /// Whether `doc` has applied the change `hash`. Without `get_change_by_hash`, which /// builds the change again from the document's operations, at a cost growing with its /// history: by its missing dependencies, which look the hash up. One `doc` holds is /// none of them; nor is one it has queued, waiting for its own, which are: with none /// missing, nothing is queued, and `hash` is applied; with some, it is asked the slow /// way (rarely: changes wait in the document only as a sync message or a file brought /// them, `sync`, `file`). pub(crate) fn holds(doc: &impl ReadDoc, hash: &ChangeHash) -> bool { let missing = doc.get_missing_deps(std::slice::from_ref(hash)); if missing.contains(hash) { return false; } missing.is_empty() || doc.get_change_by_hash(hash).is_some() } /// Whether `doc` has every change of `heads`. pub(crate) fn holds_all(doc: &impl ReadDoc, heads: &[ChangeHash]) -> bool { heads.iter().all(|head| holds(doc, head)) } /// Whether the history of `theirs` (of them, those `doc` has) holds all of `ours` /// (heads of `doc`): a peer at `theirs` has every change we have. pub(crate) fn covers(doc: &Document, theirs: &[ChangeHash], ours: &[ChangeHash]) -> bool { let known: Vec = theirs .iter() .copied() .filter(|head| holds(doc, head)) .collect(); if known.is_empty() { return ours.is_empty(); } let beyond: std::collections::HashSet = doc .get_changes_meta(&known) .into_iter() .map(|change| change.hash) .collect(); ours.iter().all(|head| !beyond.contains(head)) } /// Those of `heads` that `doc` doesn't have. pub(crate) fn missing(doc: &impl ReadDoc, heads: &[ChangeHash]) -> Vec { heads .iter() .copied() .filter(|head| !holds(doc, head)) .collect() } /// The changes after `since`, walked once: their hashes; who wrote them (the authors /// their writers set, a node's ID, `replica::authored`), each once, with the hashes of /// their changes, and whether any has none (a snapshot, or a change of a node that set /// none); and when they were committed, in Unix milliseconds by their writers' clocks /// (`Replica::transact`), changes without a time (snapshots) left out. pub(crate) struct Since { pub(crate) hashes: Vec, pub(crate) authors: Vec<(String, Vec)>, pub(crate) unauthored: bool, pub(crate) times: Vec, } pub(crate) fn since(doc: &Document, since: &[ChangeHash]) -> Since { let mut found = Since { hashes: Vec::new(), authors: Vec::new(), unauthored: false, times: Vec::new(), }; for change in doc.get_changes_meta(since) { found.hashes.push(change.hash); if change.timestamp > 0 { found.times.push(change.timestamp); } match change .author .as_ref() .and_then(|author| std::str::from_utf8(author.as_bytes()).ok()) { Some(author) => match found.authors.iter_mut().find(|(known, _)| known == author) { Some((_, hashes)) => hashes.push(change.hash), None => found.authors.push((author.to_owned(), vec![change.hash])), }, None => found.unauthored = true, } } found } /// When the changes after `since` were committed (`Since::times`). pub(crate) fn commit_times(doc: &Document, since: &[ChangeHash]) -> Vec { self::since(doc, since).times } /// Who wrote the changes after `since` (`Since::authors`, `Since::unauthored`). #[cfg(test)] pub(crate) fn authors_since( doc: &Document, since: &[ChangeHash], ) -> (Vec<(String, Vec)>, bool) { let found = self::since(doc, since); (found.authors, found.unauthored) } /// The change `hash` as the document encodes it; None if `doc` doesn't have it. pub(crate) fn change_bytes(doc: &Document, hash: &ChangeHash) -> Option> { doc.get_change_by_hash(hash) .map(|change| change.raw_bytes().to_vec()) } /// The change in `bytes`, if it is the change `hash`. pub(crate) fn change_from_bytes(bytes: Vec, hash: ChangeHash) -> Result { let change = Change::from_bytes(bytes) .map_err(|error| anyhow!("change {hash} doesn't load: {error}"))?; if change.hash() != hash { bail!("change has hash {}, not {hash}", change.hash()); } Ok(change) } /// The bytes of the delta from `from` to `to` in `doc`: the changes in the history of /// `to` but not of `from`, each as encoded, sorted by hash and concatenated /// (`load_delta` reads that). The same on every node holding `to` and `from`, whatever /// else it has. None if `doc` lacks part of either: without one of `from`, the delta /// would carry that one's history too, where `to` shares it, and differ from another /// node's (a download takes chunks from several, checked against one's manifest). pub(crate) fn delta_bytes( doc: &Document, from: &[ChangeHash], to: &[ChangeHash], ) -> Option> { if !missing(doc, to).is_empty() || !missing(doc, from).is_empty() { return None; } let since: HashMap, Vec)> = doc .get_changes(from) .iter() .map(|change| { ( change.hash(), (change.deps().to_vec(), change.raw_bytes().to_vec()), ) }) .collect(); // Of those, the ones `to` depends on: what we have beyond `to` stays out. let mut included: HashSet = HashSet::new(); let mut pending: Vec = to.to_vec(); while let Some(hash) = pending.pop() { if let Some((deps, _)) = since.get(&hash) && included.insert(hash) { pending.extend(deps.iter().copied()); } } let mut hashes: Vec = included.into_iter().collect(); hashes.sort_unstable(); let mut bytes = Vec::new(); for hash in hashes { bytes.extend_from_slice(&since[&hash].1); } Some(bytes) } /// Loads a delta (`delta_bytes`) into `doc`, unjudged: for tests; a node screens what it /// downloads (`access::screen::apply_bytes`). #[cfg(test)] pub(crate) fn load_delta(doc: &mut Document, bytes: &[u8]) -> Result<()> { use anyhow::Context as _; if let Some(misplaced) = misplaced_author(bytes) { bail!("Refused the downloaded changes: {misplaced}"); } doc.load_incremental(bytes) .context("Loading the downloaded changes")?; Ok(()) } /// A change that names an author although it isn't its actor's first (`misplaced_author`). #[derive(Debug, Clone, PartialEq, Eq)] pub(crate) struct MisplacedAuthor { pub(crate) author: Vec, pub(crate) actor: super::ActorId, pub(crate) seq: u64, } impl std::fmt::Display for MisplacedAuthor { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!( f, "change {} of actor {} names an author ({}), which only an actor's first change may", self.seq, self.actor, String::from_utf8_lossy(&self.author) ) } } /// The first change among those in `data` (chunks as `load_incremental` takes them: /// changes, compressed changes, bundles, documents) that names an author although it /// isn't its actor's first change. Automerge records an author on an actor's first change /// only, and applying a later one that carries an author trips an assertion in Automerge /// 0.12 (`ChangeGraph::add_changes`) halfway through updating the document: the task /// panics, and the document is left inconsistent. No honest node makes such a change, so /// whatever comes from elsewhere is looked at here first, until Automerge refuses such /// changes itself. Data that doesn't parse is left to Automerge, which refuses it. /// /// A document chunk is loaded on its own to read its changes (no assertion on that /// path): about as much work again as applying it, paid for documents in sync messages /// (Automerge sends one when a peer lacks a third of the history or more). pub(crate) fn misplaced_author(mut data: &[u8]) -> Option { const MAGIC: [u8; 4] = [0x85, 0x6f, 0x4a, 0x83]; // Magic bytes, checksum, chunk type, then the body's length (LEB128) and the body. const HEADER: usize = 9; while data.len() > HEADER && data[..4] == MAGIC { let kind = data[8]; let (length, read) = uleb128(&data[HEADER..])?; let end = HEADER .checked_add(read)? .checked_add(usize::try_from(length).ok()?)?; let chunk = data.get(..end)?; data = &data[end..]; let found = match kind { // A change, or a compressed one. 1 | 2 => Change::try_from(chunk) .ok() .and_then(|change| misplaced_in(&change)), 3 => automerge::Bundle::try_from(chunk) .ok() .and_then(|bundle| bundle.to_changes().ok()) .and_then(|changes| changes.iter().find_map(misplaced_in)), 0 => Document::load(chunk).ok().and_then(|doc| { doc.get_changes_meta(&[]).into_iter().find_map(|meta| { (meta.seq != 1) .then(|| author_footer(&meta.extra)) .flatten() .map(|author| MisplacedAuthor { author, actor: meta.actor.into_owned(), seq: meta.seq, }) }) }), _ => None, }; if found.is_some() { return found; } } None } /// The changes in `data`, chunks as sync messages and downloads carry them: changes, /// compressed or not, bundles, documents. None if a chunk doesn't load. pub(crate) fn changes_in(mut data: &[u8]) -> Option> { const MAGIC: [u8; 4] = [0x85, 0x6f, 0x4a, 0x83]; const HEADER: usize = 9; let mut changes = Vec::new(); while !data.is_empty() { if data.len() <= HEADER || data[..4] != MAGIC { return None; } let kind = data[8]; let (length, read) = uleb128(&data[HEADER..])?; let end = HEADER .checked_add(read)? .checked_add(usize::try_from(length).ok()?)?; let chunk = data.get(..end)?; data = &data[end..]; match kind { 1 | 2 => changes.push(Change::try_from(chunk).ok()?), 3 => changes.extend(automerge::Bundle::try_from(chunk).ok()?.to_changes().ok()?), 0 => changes.extend(Document::load(chunk).ok()?.get_changes(&[])), _ => return None, } } Some(changes) } /// `change`, decoded; without operations where Automerge panics decoding it (an /// operation naming an actor its change doesn't list), which [`Written::check`] then /// refuses: encoded again, it isn't the change that came. pub(crate) fn decode(change: &Change) -> ExpandedChange { std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| change.decode())).unwrap_or_else( |_| ExpandedChange { operations: Vec::new(), actor_id: change.actor_id().clone(), hash: None, seq: change.seq(), start_op: change.start_op(), time: change.timestamp(), message: change.message().map(str::to_owned), author: None, deps: change.deps().to_vec(), extra_bytes: change.extra_bytes().to_vec(), }, ) } /// What an operation is, as the operations after it may name it. #[derive(Clone)] struct Made { /// The change it is of. change: ChangeHash, obj: automerge::legacy::ObjectId, key: automerge::legacy::Key, /// It put an element into a list. insert: bool, /// The object it made, if it made one. makes: Option, /// It put a value or made an object: what a transaction names as replaced. holds: bool, } impl Made { fn of(change: ChangeHash, op: &automerge::legacy::Op) -> Self { Made { change, obj: op.obj.clone(), key: op.key.clone(), insert: op.insert, makes: match &op.action { automerge::legacy::OpType::Make(kind) => Some(*kind), _ => None, }, holds: matches!( op.action, automerge::legacy::OpType::Put(_) | automerge::legacy::OpType::Make(_) ), } } } /// A change of a batch that passed [`Written::check`]. struct Passed { deps: Vec, actor: ActorId, seq: u64, max_op: u64, /// The changes of the document its history reaches first: its own dependencies /// there, and those of the batch's changes it builds on. doc_heads: Vec, } /// The history of a change being checked, walked back from its dependencies as far as /// a question needs: newest first, by the operations' counters. struct History { queue: std::collections::BinaryHeap<(u64, ChangeHash)>, seen: std::collections::HashSet, } /// What the changes of a batch made that passed [`Written::check`] and were taken /// ([`Written::taken`]): those after them in the batch build on them before the /// document holds them. #[derive(Default)] pub(crate) struct Written { passed: HashMap, /// The last change that passed, until it is taken: one refused after (a fork, the /// rules) must not stand in for what the document holds. checked: Option<(ChangeHash, Passed)>, /// The operations they made. ops: HashMap<(ActorId, u64), Made>, /// Changes of the document, decoded to see what an operation of theirs is. decoded: HashMap>, } impl Written { /// Why `change` (`expanded`: it, decoded) is none that Automerge writes, building /// on `doc` and the changes checked before it; None if it is one, which is then /// among those. Automerge 0.12 applies changes that aren't, and is broken by them: /// it then gives back another change than the one it was given and saves a /// document that doesn't load, or panics. No honest node makes such a change, so /// each from elsewhere is looked at first. /// /// Everything asked is asked of the change and its own history, never of what /// else the document holds: two nodes that hold a change's history come to the /// same, whatever reached them besides and in whatever order. /// /// * Its bytes are the ones Automerge encodes for it. (One listing an actor none /// of its operations names loads, with another hash than its own encoding has.) /// * Its first operation is numbered one after the highest of its dependencies, 1 /// without any: what a transaction at the document's heads gives it. (One /// numbered below them saves to a document that doesn't load; one numbered /// near 2^32 makes the next write panic.) /// * It is its actor's first, or builds on the one before it: a transaction names /// its actor's last change among its dependencies. (A gap in an actor's numbers /// makes Automerge panic.) /// * Every operation it names was made in its history, or before in the change /// itself, and is what it is named as: the object written into an object of /// that kind, the element of that list, the operation replaced one at that /// place that put a value or made an object. (One naming an operation elsewhere /// marks an unrelated value gone, and the document then gives back another /// change under this one's hash; one naming a deletion or an increment does the /// same, or panics as it is given back.) /// * Every operation is one Automerge's transactions write, but for tables and /// marks ([`unwritten`] says which). (Automerge takes others, and then can't /// give the change back, or panics giving it, and its save doesn't load.) /// /// A change that passes is among those the next are checked against only once /// it is [`Written::taken`]. pub(crate) fn check( &mut self, doc: &Document, change: &Change, expanded: &ExpandedChange, ) -> Option { use automerge::legacy::{ElementId, Key, ObjectId, OpId}; self.checked = None; let hash = change.hash(); let again = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| { Change::from(expanded.clone()).hash() })); if again.ok() != Some(hash) { return Some("its bytes aren't the ones Automerge encodes for it".to_owned()); } let start = change.start_op().get(); let last = change.max_op(); let actor = change.actor_id(); // Its dependencies: those of the batch, and those the document holds. One // that is neither isn't ready, and Automerge doesn't apply the change (callers // judge those whose dependencies they hold): nothing is asked of it. let mut before = 0; let mut follows = change.seq() == 1; let mut doc_heads: Vec = Vec::new(); for dep in change.deps() { let (dep_actor, seq, max_op) = if let Some(passed) = self.passed.get(dep) { doc_heads.extend(&passed.doc_heads); (passed.actor.clone(), passed.seq, passed.max_op) } else { let meta = doc.get_change_meta_by_hash(dep)?; doc_heads.push(*dep); (meta.actor.into_owned(), meta.seq, meta.max_op) }; before = before.max(max_op); follows |= &dep_actor == actor && seq + 1 == change.seq(); } doc_heads.sort_unstable(); doc_heads.dedup(); if start != before + 1 { return Some(format!( "its first operation is numbered {start}, not {}, one after the highest of its dependencies", before + 1 )); } if !follows { return Some(format!( "it is its actor's change {}, and doesn't build on the one before", change.seq() )); } let mut history = History { queue: Default::default(), seen: change.deps().iter().copied().collect(), }; for dep in change.deps() { if let Some(max_op) = self.max_op(doc, dep) { history.queue.push((max_op, *dep)); } } let exid = |OpId(counter, by): &OpId| automerge::ObjId::Id(*counter, by.clone(), 0); for (index, op) in expanded.operations.iter().enumerate() { let this = start + index as u64; // What `id` is, if it was made before this operation: in the change // itself, or in its history. let mut made = |written: &mut Self, id: &OpId| -> Option { let OpId(counter, by) = id; if by == actor && (start..this).contains(counter) { let op = &expanded.operations[(counter - start) as usize]; return Some(Made::of(hash, op)); } if *counter >= start { return None; } // Made by a change of the batch taken before, or of the document: the // one this change's history holds. [written.made_in_batch(id), written.made_in_doc(doc, id)] .into_iter() .flatten() .find(|made| written.reaches(doc, &mut history, made.change, *counter)) }; // What it is: one of what Automerge's transactions write. if let Some(why) = unwritten(op) { return Some(why.to_owned()); } // The object written into: one, of the kind the key is for. let in_list = matches!(op.key, Key::Seq(_)); // No table: `unwritten` refuses making one. let fits = |kind: automerge::ObjType| match kind { automerge::ObjType::Map => !in_list, automerge::ObjType::List | automerge::ObjType::Text => in_list, automerge::ObjType::Table => false, }; // Whether the object is one the document held at `doc_heads`, for what // can then be read there. let held; match &op.obj { ObjectId::Root => { if in_list { return Some("it writes a list's element into the root".to_owned()); } held = true; } ObjectId::Id(id) => { let object = exid(id); // Seen where its parent holds it, at the document's changes this // one builds on: made in its history, with nothing walked. let seen = (!doc_heads.is_empty() && !self.ops.contains_key(&(id.1.clone(), id.0))) .then(|| doc.object_type(&object).ok()) .flatten() .filter(|kind| fits(*kind)) .filter(|_| { doc.parents(&object) .ok() .and_then(|mut parents| parents.next()) .is_some_and(|parent| match parent.prop { automerge::Prop::Map(key) => doc .get_all_at(&parent.obj, key, &doc_heads) .is_ok_and(|held| held.iter().any(|(_, id)| *id == object)), automerge::Prop::Seq(_) => false, }) }); held = seen.is_some(); if !held && !made(self, id).is_some_and(|made| made.makes.is_some_and(fits)) { let OpId(counter, by) = id; return Some(format!( "it writes into {counter}@{by}, no object of that kind made before it" )); } } } // The element of a list: one put into that list, and written at only where a // value or an object was put (an insert may follow a mark's begin or end, // in a document that holds one from before marks were refused). let element = match &op.key { Key::Seq(ElementId::Id(id)) => Some(id), Key::Seq(ElementId::Head) | Key::Map(_) => None, }; if let Some(id) = element && !made(self, id).is_some_and(|made| { made.insert && made.obj == op.obj && (op.insert || made.holds) }) { let OpId(counter, by) = id; return Some(format!( "it names {counter}@{by}, no element of that list put there before it" )); } // What it replaces: operations at its place. let there: Vec = match (&op.key, held, op.pred.is_empty()) { // Those the document holds there, at the changes this one builds on: // in its history, with nothing walked. (Key::Map(key), true, false) if !doc_heads.is_empty() => { let object = match &op.obj { ObjectId::Root => automerge::ROOT, ObjectId::Id(id) => exid(id), }; doc.get_all_at(&object, key.as_str(), &doc_heads) .map(|held| held.into_iter().map(|(_, id)| id).collect()) .unwrap_or_default() } _ => Vec::new(), }; for id in op.pred.iter() { let at_its_place = there.contains(&exid(id)) || (element == Some(id)) || made(self, id).is_some_and(|made| { made.holds && !made.insert && made.obj == op.obj && made.key == op.key }); if !at_its_place { let OpId(counter, by) = id; return Some(format!( "it replaces {counter}@{by}, no operation at that place made before it" )); } } } self.checked = Some(( hash, Passed { deps: change.deps().to_vec(), actor: actor.clone(), seq: change.seq(), max_op: last, doc_heads, }, )); None } /// `change` (`expanded`: it, decoded), the last that passed [`Written::check`], /// taken: those after it are checked against what it made. pub(crate) fn taken(&mut self, change: &Change, expanded: &ExpandedChange) { let hash = change.hash(); let Some((checked, passed)) = self.checked.take() else { return; }; if checked != hash { return; } let start = change.start_op().get(); for (index, op) in expanded.operations.iter().enumerate() { self.ops.insert( (change.actor_id().clone(), start + index as u64), Made::of(hash, op), ); } self.passed.insert(hash, passed); } /// The highest operation counter of a change of the batch or the document. fn max_op(&self, doc: &Document, hash: &ChangeHash) -> Option { self.passed .get(hash) .map(|passed| passed.max_op) .or_else(|| doc.get_change_meta_by_hash(hash).map(|meta| meta.max_op)) } /// What the operation `id` is, made by a change of the batch taken before. fn made_in_batch(&self, id: &automerge::legacy::OpId) -> Option { let automerge::legacy::OpId(counter, by) = id; self.ops.get(&(by.clone(), *counter)).cloned() } /// What the operation `id` is, made by a change of the document. fn made_in_doc(&mut self, doc: &Document, id: &automerge::legacy::OpId) -> Option { let automerge::legacy::OpId(counter, by) = id; let hash = doc.hash_for_opid(&automerge::ObjId::Id(*counter, by.clone(), 0))?; let change = self .decoded .entry(hash) .or_insert_with(|| doc.get_change_by_hash(&hash).map(|change| decode(&change))) .as_ref()?; let index = counter.checked_sub(change.start_op.get())?; let op = change.operations.get(usize::try_from(index).ok()?)?; Some(Made::of(hash, op)) } /// Whether `target`, a change with an operation numbered `counter`, is in the /// history `history` walks. A change's operations are numbered above those of /// all it builds on, so the walk goes no further back than `counter`. fn reaches( &self, doc: &Document, history: &mut History, target: ChangeHash, counter: u64, ) -> bool { while let Some((max_op, _)) = history.queue.peek() && *max_op >= counter && !history.seen.contains(&target) { let (_, hash) = history.queue.pop().expect("peeked"); let deps = match self.passed.get(&hash) { Some(passed) => passed.deps.clone(), None => doc .get_change_meta_by_hash(&hash) .map(|meta| meta.deps) .unwrap_or_default(), }; for dep in deps { if history.seen.insert(dep) && let Some(max_op) = self.max_op(doc, &dep) { history.queue.push((max_op, dep)); } } } history.seen.contains(&target) } } /// Why `op` is none Automerge's transactions write, or one continuum doesn't take; None /// if it may be one ([`Written::check`] asks the rest of its history). What they write: /// /// * Inserted: a value put or an object made, into a list or a text, after one of its /// elements or at its head, replacing nothing. /// * At a list's element, not inserted (never at its head): a value put, an object made, /// a deletion or an increment, replacing what is at that element. /// * At a map's key, never inserted: a value put, an object made, or a deletion or an /// increment replacing something. /// /// Not taken, though transactions write them: a table, which they make but can't write /// into (Automerge panics applying a change that does); a mark's begin or end (Automerge /// takes some, and then breaks: a value written at one, once the text is edited; a mark /// ended ahead of its begin). Continuum's store writes neither. fn unwritten(op: &automerge::legacy::Op) -> Option<&'static str> { use automerge::legacy::{ElementId, Key, OpType}; let replaces = !op.pred.is_empty(); match (&op.key, op.insert, &op.action) { (_, _, OpType::Make(automerge::ObjType::Table)) => Some("it makes a table"), (_, _, OpType::MarkBegin(_) | OpType::MarkEnd(_)) => Some("it marks a text"), (Key::Map(_), true, _) => Some("it inserts at a map's key"), (Key::Seq(_), true, OpType::Delete | OpType::Increment(_)) => { Some("it inserts a deletion or an increment") } (Key::Seq(_), true, _) if replaces => Some("it inserts, replacing something"), (Key::Seq(ElementId::Head), false, _) => { Some("it writes at a list's head without inserting") } (Key::Seq(_), false, _) if !replaces => Some("it writes at an element, replacing nothing"), (Key::Map(_), false, OpType::Delete | OpType::Increment(_)) if !replaces => { Some("it deletes or increments, replacing nothing") } _ => None, } } /// `change`, if it names an author but isn't its actor's first (`misplaced_author`). fn misplaced_in(change: &Change) -> Option { let author = change.author()?; (change.seq() != 1).then(|| MisplacedAuthor { author: author.as_bytes().to_vec(), actor: change.actor_id().clone(), seq: change.seq(), }) } /// The author in a change's extra bytes: footers, each its kind (LEB128; 1 is the /// author), its length (LEB128) and its bytes. fn author_footer(mut extra: &[u8]) -> Option> { while !extra.is_empty() { let (kind, read) = uleb128(extra)?; let (length, more) = uleb128(&extra[read..])?; let start = read + more; let end = start.checked_add(usize::try_from(length).ok()?)?; let bytes = extra.get(start..end)?; if kind == 1 { return Some(bytes.to_vec()); } extra = &extra[end..]; } None } /// An unsigned LEB128 number at the start of `bytes`, and how many bytes it took. fn uleb128(bytes: &[u8]) -> Option<(u64, usize)> { let mut value = 0u64; for (i, byte) in bytes.iter().enumerate().take(10) { value |= u64::from(byte & 0x7f) << (7 * i); if byte & 0x80 == 0 { return Some((value, i + 1)); } } None } #[cfg(test)] mod tests { use super::*; use crate::document::testing::change; use automerge::{ActorId, ROOT, transaction::Transactable}; fn random_write(rng: &mut crate::testrand::Rng, doc: &mut Document) { let key = format!("k{}", rng.below(6)); let value = rng.below(100) as i64; change(doc, |doc| doc.put(ROOT, key, value).unwrap()); } fn sorted(mut heads: Vec) -> Vec { heads.sort_unstable(); heads } /// Held: a change applied; not one never seen, nor one queued, waiting for the one /// before it, until that comes. #[test] fn holds_applied_changes_only() { let mut theirs = Document::new(); change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap()); let first = theirs.get_heads()[0]; change(&mut theirs, |doc| doc.put(ROOT, "k", 2).unwrap()); let second = theirs.get_heads()[0]; let mut ours = Document::new(); assert!(!holds(&ours, &first)); ours.apply_changes([theirs.get_change_by_hash(&second).unwrap()]) .unwrap(); assert!(!holds(&ours, &second), "queued"); assert!(!holds(&ours, &first)); ours.apply_changes([theirs.get_change_by_hash(&first).unwrap()]) .unwrap(); assert!(holds(&ours, &first)); assert!(holds(&ours, &second)); assert!(holds_all(&ours, &[first, second])); } /// Over random histories: two nodes that reached the same heads through different /// merge orders, one with more on top, produce the same bytes for a delta to those /// heads; a document at `from` that loads them is at `to`. #[test] fn delta_bytes_are_the_same_everywhere_and_complete() { crate::testrand::for_seeds(200, |rng| { let actor = |i: u8| ActorId::from(&[i; 16][..]); let mut base = Document::new().with_actor(actor(0)); for _ in 0..rng.between(0, 5) { random_write(rng, &mut base); } let from = base.get_heads(); let mut writers: Vec = (1..=rng.between(1, 3)) .map(|i| base.fork().with_actor(actor(i as u8))) .collect(); for _ in 0..rng.between(1, 15) { let writer = rng.below(writers.len()); random_write(rng, &mut writers[writer]); } let mut one = base.fork().with_actor(actor(10)); let mut two = base.fork().with_actor(actor(11)); for writer in writers.iter_mut() { one.merge(writer).unwrap(); } for writer in writers.iter_mut().rev() { two.merge(writer).unwrap(); } let to = one.get_heads(); assert_eq!(sorted(to.clone()), sorted(two.get_heads())); // Beyond `to`: must stay out of the delta. random_write(rng, &mut two); let bytes = delta_bytes(&one, &from, &to).unwrap(); assert_eq!(delta_bytes(&two, &from, &to).unwrap(), bytes); let mut behind = base.fork(); load_delta(&mut behind, &bytes).unwrap(); assert_eq!(sorted(behind.get_heads()), sorted(to)); }); } /// Heads cover ours when their history holds all of ours: as far as ours, or /// further; not when behind or beside; heads we don't know count for nothing. #[test] fn heads_that_cover_ours() { let mut doc = Document::new(); change(&mut doc, |doc| doc.put(ROOT, "a", 1_i64).unwrap()); let early = doc.get_heads(); change(&mut doc, |doc| doc.put(ROOT, "b", 2_i64).unwrap()); let ours = doc.get_heads(); let mut further = doc.fork(); change(&mut further, |doc| doc.put(ROOT, "c", 3_i64).unwrap()); doc.merge(&mut further.clone()).unwrap(); let unknown = ChangeHash([7; 32]); assert!(covers(&doc, &ours, &ours)); assert!(covers(&doc, &further.get_heads(), &ours), "further"); assert!(!covers(&doc, &early, &ours), "behind"); assert!(!covers(&doc, &[unknown], &ours), "unknown"); assert!( covers(&doc, &[unknown, ours[0]], &ours), "the known one does" ); } #[test] fn no_delta_without_its_heads() { let mut doc = Document::new(); change(&mut doc, |doc| doc.put(ROOT, "k", 1_i64).unwrap()); let heads = doc.get_heads(); assert!(delta_bytes(&doc, &[], &[ChangeHash([7; 32])]).is_none()); assert!( delta_bytes(&doc, &[ChangeHash([7; 32])], &heads).is_none(), "nor without where it starts" ); } /// A change loads from its bytes only as the change it was asked for. #[test] fn a_change_is_checked_against_its_hash() { let mut doc = Document::new(); change(&mut doc, |doc| doc.put(ROOT, "k", 1_i64).unwrap()); let hash = doc.get_heads()[0]; let bytes = change_bytes(&doc, &hash).unwrap(); assert_eq!(change_from_bytes(bytes.clone(), hash).unwrap().hash(), hash); assert!(change_from_bytes(bytes, ChangeHash([7; 32])).is_err()); assert!(change_bytes(&doc, &ChangeHash([7; 32])).is_none()); } /// The authors of the changes after some heads: each node that wrote some, once, /// however their changes were merged; a change without an author is told apart. #[test] fn authors_of_the_changes_since() { use crate::clock::UnixMillis; use crate::document::replica::{Writer, transact}; let write = |doc: &mut Document, node: &str, key: &str| { let writer = Writer { node, user: None }; transact(doc, UnixMillis(1), &writer, |doc| doc.put(ROOT, key, 1)).unwrap(); }; let mut base = Document::new(); write(&mut base, "node-a", "base"); let since = base.get_heads(); assert_eq!(authors_since(&base, &since), (Vec::new(), false)); let mut a = base.fork(); write(&mut a, "node-a", "a1"); write(&mut a, "node-a", "a2"); let mut b = base.fork(); write(&mut b, "node-b", "b1"); let mut merged = a.clone(); merged.merge(&mut b).unwrap(); let (mut authors, unknown) = authors_since(&merged, &since); authors.sort(); let counts: Vec<(&str, usize)> = authors .iter() .map(|(author, hashes)| (author.as_str(), hashes.len())) .collect(); assert_eq!(counts, [("node-a", 2), ("node-b", 1)]); assert!(!unknown); // A change no node authored (a snapshot's, say). let mut snapshot = Document::new(); snapshot.merge(&mut merged.clone()).unwrap(); change(&mut snapshot, |doc| doc.put(ROOT, "s", 1).unwrap()); let (_, unknown) = authors_since(&snapshot, &merged.get_heads()); assert!(unknown); } /// An actor without an author, and its two changes: the second as made, and with an /// author footer it mustn't carry. fn misplaced() -> (Vec, Vec, Vec) { let mut doc = Document::new().with_actor(ActorId::from(b"writer".to_vec())); change(&mut doc, |tx| tx.put(ROOT, "x", 1).unwrap()); change(&mut doc, |tx| tx.put(ROOT, "x", 2).unwrap()); let changes = doc.get_changes(&[]); let (first, second) = ( changes[0].raw_bytes().to_vec(), changes[1].raw_bytes().to_vec(), ); let crafted = crate::document::testing::with_author_footer(&second, b"mallory"); (first, second, crafted) } #[test] fn an_author_on_a_later_change_is_found() { let (first, second, crafted) = misplaced(); assert_eq!(misplaced_author(&[first.clone(), second].concat()), None); let found = misplaced_author(&[first.clone(), crafted.clone()].concat()).unwrap(); assert_eq!(found.seq, 2); assert_eq!(found.author, b"mallory"); assert_eq!(found.actor, ActorId::from(b"writer".to_vec())); // Honest authors (on first changes) and whole documents pass. let mut authored = Document::new(); authored.set_author(Some(automerge::Author::from(b"node".to_vec()))); change(&mut authored, |tx| tx.put(ROOT, "a", 1).unwrap()); change(&mut authored, |tx| tx.put(ROOT, "a", 2).unwrap()); assert_eq!(misplaced_author(&authored.save()), None); let bytes: Vec = authored .get_changes(&[]) .iter() .flat_map(|change| change.raw_bytes().to_vec()) .collect(); assert_eq!(misplaced_author(&bytes), None); // What isn't chunks is left to Automerge. assert_eq!(misplaced_author(b"not a chunk"), None); } #[test] fn a_delta_with_a_misplaced_author_is_refused_and_the_document_kept() { let (first, _, crafted) = misplaced(); let mut doc = Document::new(); load_delta(&mut doc, &first).unwrap(); let heads = doc.get_heads(); assert!(load_delta(&mut doc, &crafted).is_err()); assert_eq!(doc.get_heads(), heads); // Still whole: it saves and loads. crate::document::load(&doc.save()).unwrap(); } /// A document written the ways the store writes: maps within maps, lists, text, /// values replaced and deleted, by two nodes at once. fn written() -> Document { use automerge::{ObjType, ScalarValue}; let mut doc = Document::new(); let (map, list) = change(&mut doc, |doc| { let map = doc.put_object(ROOT, "map", ObjType::Map).unwrap(); doc.put(&map, "k", "v").unwrap(); let list = doc.put_object(&map, "list", ObjType::List).unwrap(); doc.insert(&list, 0, 1).unwrap(); doc.insert(&list, 1, "two").unwrap(); (map, list) }); let text = change(&mut doc, |doc| { doc.put(&map, "k", vec![1u8, 2, 3]).unwrap(); doc.delete(&list, 0).unwrap(); doc.insert(&list, 1, true).unwrap(); let text = doc.put_object(ROOT, "text", ObjType::Text).unwrap(); doc.splice_text(&text, 0, 0, "hello").unwrap(); text }); // Counters in a list and a map, an element written over; the text typed in, // partly deleted. change(&mut doc, |doc| { let counters = doc.put_object(&map, "counters", ObjType::List).unwrap(); doc.insert(&counters, 0, ScalarValue::counter(1)).unwrap(); doc.increment(&counters, 0, 2).unwrap(); doc.insert(&counters, 1, "under").unwrap(); doc.put(&counters, 1, "over").unwrap(); doc.insert(&counters, 0, "at the head").unwrap(); doc.put(&map, "count", ScalarValue::counter(0)).unwrap(); doc.increment(&map, "count", 1).unwrap(); doc.splice_text(&text, 1, 2, "").unwrap(); doc.splice_text(&text, 3, 0, "!").unwrap(); }); let mut other = doc.fork(); change(&mut other, |doc| doc.increment(&map, "count", 2).unwrap()); change(&mut other, |doc| doc.put(&map, "k", 2.5).unwrap()); change(&mut other, |doc| doc.delete(&map, "list").unwrap()); change(&mut doc, |doc| doc.put(&map, "k", ()).unwrap()); change(&mut doc, |doc| doc.delete(ROOT, "text").unwrap()); doc.merge(&mut other).unwrap(); change(&mut doc, |doc| doc.put(&map, "k", "merged").unwrap()); doc } /// What Automerge writes passes: checked against a document taking the changes /// one by one, and as one batch against an empty one. #[test] fn changes_automerge_writes_pass() { let theirs = written(); let changes = theirs.get_changes(&[]); let mut ours = Document::new(); for change in &changes { assert_eq!( Written::default().check(&ours, change, &change.decode()), None ); ours.apply_changes([change.clone()]).unwrap(); } let empty = Document::new(); let mut written = Written::default(); for change in &changes { let expanded = change.decode(); assert_eq!(written.check(&empty, change, &expanded), None); written.taken(change, &expanded); } } /// Bytes that load as a change and aren't Automerge's encoding of it: refused. #[test] fn bytes_automerge_wouldnt_encode_are_refused() { let mut theirs = Document::new(); change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap()); let honest = theirs.get_changes(&[]).remove(0); let ours = Document::new(); assert_eq!( Written::default().check(&ours, &honest, &honest.decode()), None ); let crafted = crate::document::testing::with_spare_actor(honest.raw_bytes(), &[0xab; 16]); let crafted = Change::try_from(&crafted[..]).expect("it loads"); assert_ne!(crafted.hash(), honest.hash()); let why = Written::default() .check(&ours, &crafted, &crafted.decode()) .expect("refused"); assert!(why.contains("encodes"), "{why}"); } /// A first operation numbered ahead of the dependencies', or below them: refused. #[test] fn operations_numbered_against_their_dependencies_are_refused() { let mut theirs = Document::new(); change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap()); change(&mut theirs, |doc| doc.put(ROOT, "k", 2).unwrap()); let mut ours = Document::new(); ours.apply_changes(theirs.get_changes(&[])).unwrap(); change(&mut theirs, |doc| doc.put(ROOT, "other", 3).unwrap()); let honest = theirs.get_last_local_change().unwrap(); assert_eq!(honest.start_op().get(), 3); for start in [1, 2, 4, (1 << 32) - 1] { let mut expanded = honest.decode(); expanded.start_op = std::num::NonZeroU64::new(start).unwrap(); expanded.hash = None; let crafted = Change::from(expanded); let why = Written::default() .check(&ours, &crafted, &crafted.decode()) .expect("refused"); assert!(why.contains("numbered"), "{start}: {why}"); } assert_eq!( Written::default().check(&ours, &honest, &honest.decode()), None ); // A root: numbered 1. let root = theirs.get_changes(&[]).remove(0); let mut expanded = root.decode(); expanded.start_op = std::num::NonZeroU64::new(7).unwrap(); expanded.hash = None; let crafted = Change::from(expanded); assert!( Written::default() .check(&Document::new(), &crafted, &crafted.decode()) .is_some() ); } /// An operation on an object nobody made, by an actor the document doesn't hold or /// at a counter its actor never reached: refused. #[test] fn operations_naming_what_nobody_made_are_refused() { use automerge::legacy::{ObjectId, OpId}; let mut theirs = Document::new(); let map = change(&mut theirs, |doc| { doc.put_object(ROOT, "map", automerge::ObjType::Map) .unwrap() }); change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap()); let mut ours = Document::new(); ours.apply_changes(theirs.get_changes(&[])).unwrap(); change(&mut theirs, |doc| doc.put(&map, "k", 2).unwrap()); let honest = theirs.get_last_local_change().unwrap(); assert_eq!( Written::default().check(&ours, &honest, &honest.decode()), None ); let known = theirs.get_actor().clone(); for object in [ OpId(1, ActorId::from([0xab; 16])), OpId(honest.start_op().get() + 5, known.clone()), OpId(honest.start_op().get(), ActorId::from([0xab; 16])), ] { let mut expanded = honest.decode(); expanded.operations[0].obj = ObjectId::Id(object.clone()); expanded.hash = None; let crafted = Change::from(expanded); let why = Written::default() .check(&ours, &crafted, &crafted.decode()) .expect("refused"); assert!(why.contains("no object"), "{object:?}: {why}"); } } /// `honest` with `edit` made to it, as a change of its own. fn crafted(honest: &Change, edit: impl FnOnce(&mut ExpandedChange)) -> Change { let mut expanded = honest.decode(); edit(&mut expanded); expanded.hash = None; Change::from(expanded) } /// An operation named as replaced that is elsewhere, or that put no object where /// one is written into: refused, though it was made before. #[test] fn operations_named_at_the_wrong_place_are_refused() { use automerge::legacy::{ObjectId, OpId}; let mut theirs = Document::new(); change(&mut theirs, |doc| doc.put(ROOT, "a", 1).unwrap()); change(&mut theirs, |doc| doc.put(ROOT, "b", 2).unwrap()); let mut ours = Document::new(); ours.apply_changes(theirs.get_changes(&[])).unwrap(); let actor = theirs.get_actor().clone(); change(&mut theirs, |doc| doc.put(ROOT, "b", 3).unwrap()); let honest = theirs.get_last_local_change().unwrap(); assert_eq!( Written::default().check(&ours, &honest, &honest.decode()), None ); // It replaces what wrote `a`. let elsewhere = crafted(&honest, |change| { change.operations[0].pred = vec![OpId(1, actor.clone())].into(); }); let why = Written::default() .check(&ours, &elsewhere, &elsewhere.decode()) .expect("refused"); assert!(why.contains("at that place"), "{why}"); // It writes into what put a number. let no_object = crafted(&honest, |change| { change.operations[0].obj = ObjectId::Id(OpId(1, actor.clone())); change.operations[0].pred = Vec::new().into(); }); let why = Written::default() .check(&ours, &no_object, &no_object.decode()) .expect("refused"); assert!(why.contains("no object"), "{why}"); } /// An operation named that the document holds, made by a change this one doesn't /// build on: refused, as by a node that doesn't hold it yet. #[test] fn operations_outside_a_changes_history_are_refused() { use automerge::legacy::OpId; let mut theirs = Document::new(); change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap()); let mut other = theirs.fork(); change(&mut other, |doc| doc.put(ROOT, "k", 2).unwrap()); let aside = other.get_last_local_change().unwrap(); change(&mut theirs, |doc| doc.put(ROOT, "k", 3).unwrap()); let honest = theirs.get_last_local_change().unwrap(); // It also replaces what the other wrote, which it never saw. let reaching = crafted(&honest, |change| { let mut pred: Vec = change.operations[0].pred.iter().cloned().collect(); pred.push(OpId(aside.start_op().get(), aside.actor_id().clone())); change.operations[0].pred = pred.into(); }); // Whether we hold the other's change or not. let mut without = Document::new(); without .apply_changes(theirs.get_changes(&[]).into_iter().take(1)) .unwrap(); let mut with = without.clone(); with.apply_changes([aside.clone()]).unwrap(); for ours in [&without, &with] { assert_eq!( Written::default().check(ours, &honest, &honest.decode()), None ); let why = Written::default() .check(ours, &reaching, &reaching.decode()) .expect("refused"); assert!(why.contains("at that place"), "{why}"); } } /// A change that isn't its actor's first and doesn't build on the one before it: /// refused. #[test] fn a_gap_in_an_actors_changes_is_refused() { let mut theirs = Document::new(); change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap()); let mut ours = Document::new(); ours.apply_changes(theirs.get_changes(&[])).unwrap(); change(&mut theirs, |doc| doc.put(ROOT, "k", 2).unwrap()); let honest = theirs.get_last_local_change().unwrap(); assert_eq!(honest.seq(), 2); assert_eq!( Written::default().check(&ours, &honest, &honest.decode()), None ); for seq in [3, 7] { let gap = crafted(&honest, |change| change.seq = seq); let why = Written::default() .check(&ours, &gap, &gap.decode()) .expect("refused"); assert!(why.contains("the one before"), "{seq}: {why}"); } // A first change of another actor numbered 2. let mut stranger = ours.fork().with_actor(ActorId::from([0xcd; 16])); change(&mut stranger, |doc| doc.put(ROOT, "k", 9).unwrap()); let first = stranger.get_last_local_change().unwrap(); let second = crafted(&first, |change| change.seq = 2); assert!( Written::default() .check(&ours, &second, &second.decode()) .is_some() ); } /// Changes of one batch building on each other pass, each checked against those /// before it; one naming what a change of the batch wrote elsewhere doesn't. #[test] fn a_batch_is_checked_against_itself() { use automerge::legacy::OpId; let theirs = written(); let changes = theirs.get_changes(&[]); let half = changes.len() / 2; let mut ours = Document::new(); ours.apply_changes(changes[..half].iter().cloned()).unwrap(); let mut written = Written::default(); for change in &changes[half..] { let expanded = change.decode(); assert_eq!(written.check(&ours, change, &expanded), None); written.taken(change, &expanded); } // The last put `k` in the map: have it replace what made the map. let last = changes.last().unwrap(); let first = &changes[0]; let elsewhere = crafted(last, |change| { change.operations[0].pred = vec![OpId(first.start_op().get(), first.actor_id().clone())].into(); }); let mut written = Written::default(); for change in &changes[..changes.len() - 1] { let expanded = change.decode(); assert_eq!(written.check(&Document::new(), change, &expanded), None); written.taken(change, &expanded); } assert!( written .check(&Document::new(), &elsewhere, &elsewhere.decode()) .is_some() ); } /// Only what Automerge's transactions write passes: each operation by what it is, /// and what it replaces at its place. Each crafted change Automerge takes, and then /// can't give back, panics giving back, or saves a document that doesn't load. #[test] fn only_what_transactions_write_passes() { use crate::document::Transaction; use automerge::legacy::{ElementId, Key, OpId}; use automerge::{ObjType, ScalarValue}; let mut theirs = Document::new(); let (list, counters) = change(&mut theirs, |doc| { doc.put(ROOT, "k", 1).unwrap(); let list = doc.put_object(ROOT, "list", ObjType::List).unwrap(); doc.insert(&list, 0, "a").unwrap(); doc.insert(&list, 1, "c").unwrap(); let counters = doc.put_object(ROOT, "counters", ObjType::List).unwrap(); doc.insert(&counters, 0, ScalarValue::counter(1)).unwrap(); (list, counters) }); let first = theirs.get_last_local_change().unwrap(); assert_eq!(first.decode().operations.len(), 6); let actor = first.actor_id().clone(); // The first change's operations: 1 the list, 2 its "a", 3 its "c" (after "a"). let id = |index: u64| OpId(first.start_op().get() + index, actor.clone()); let mut ours = Document::new(); ours.apply_changes([first.clone()]).unwrap(); fn on(doc: &Document, write: impl FnOnce(&mut Transaction<'_>)) -> Change { let mut fork = doc.fork(); change(&mut fork, write); fork.get_last_local_change().unwrap() } let put_over = on(&ours, |doc| doc.put(&list, 0, "A").unwrap()); let delete = on(&ours, |doc| doc.delete(&list, 0).unwrap()); let increment = on(&ours, |doc| doc.increment(&counters, 0, 1).unwrap()); let insert = on(&ours, |doc| doc.insert(&list, 1, "b").unwrap()); let map_delete = on(&ours, |doc| doc.delete(ROOT, "k").unwrap()); for honest in [&put_over, &delete, &increment, &insert, &map_delete] { assert_eq!( Written::default().check(&ours, honest, &honest.decode()), None, "{:?}", honest.decode().operations ); } let crafted = [ // An element written over, naming as replaced the element inserted after it. crafted(&put_over, |change| { change.operations[0].pred = vec![id(3)].into() }), crafted(&delete, |change| { change.operations[0].pred = vec![id(3)].into() }), // The same at the list's head, naming its first element. crafted(&delete, |change| { change.operations[0].key = Key::Seq(ElementId::Head); change.operations[0].pred = vec![id(2)].into(); }), crafted(&increment, |change| { change.operations[0].key = Key::Seq(ElementId::Head) }), crafted(&put_over, |change| { change.operations[0].key = Key::Seq(ElementId::Head) }), // Written at an element, replacing nothing. crafted(&put_over, |change| { change.operations[0].pred = Vec::new().into() }), // Deleting at a map's key, replacing nothing. crafted(&map_delete, |change| { change.operations[0].pred = Vec::new().into() }), // An insert replacing something. crafted(&insert, |change| { change.operations[0].pred = vec![id(2)].into() }), // A deletion or an increment inserted, in a list or at a map's key. crafted(&delete, |change| change.operations[0].insert = true), crafted(&map_delete, |change| change.operations[0].insert = true), crafted(&increment, |change| change.operations[0].insert = true), ]; for crafted in crafted { let why = Written::default().check(&ours, &crafted, &crafted.decode()); assert!(why.is_some(), "{:?}", crafted.decode().operations); } } /// No mark: one a transaction writes, or one ended where nothing began. Automerge /// takes some marks and then breaks (a value written at a mark's begin or end, once /// the text is edited; a mark ended ahead of its begin); continuum writes none. In /// a document that holds one from before, typing next to it passes, writing at it /// doesn't. #[test] fn no_mark() { use crate::document::Transaction; use automerge::ObjType; use automerge::legacy::OpType; use automerge::marks::{ExpandMark, Mark}; let mut theirs = Document::new(); let text = change(&mut theirs, |doc| { let text = doc.put_object(ROOT, "text", ObjType::Text).unwrap(); doc.splice_text(&text, 0, 0, "abc").unwrap(); text }); let mut ours = Document::new(); ours.apply_changes(theirs.get_changes(&[])).unwrap(); fn on(doc: &Document, write: impl FnOnce(&mut Transaction<'_>)) -> Change { let mut fork = doc.fork(); change(&mut fork, write); fork.get_last_local_change().unwrap() } let typed = on(&ours, |doc| doc.splice_text(&text, 3, 0, "d").unwrap()); assert_eq!( Written::default().check(&ours, &typed, &typed.decode()), None ); let marked = on(&ours, |doc| { doc.mark( &text, Mark::new("bold".into(), true, 1, 2), ExpandMark::None, ) .unwrap() }); let ended = crafted(&typed, |change| { change.operations[0].action = OpType::MarkEnd(false) }); for crafted in [marked.clone(), ended] { let why = Written::default().check(&ours, &crafted, &crafted.decode()); assert!(why.is_some(), "{:?}", crafted.decode().operations); } // Taken without screening: "a" marked, its begin after the head, its end after // "a". let mut held = ours.fork(); held.apply_changes([marked.clone()]).unwrap(); for at in 0..=3 { let typed = on(&held, |doc| doc.splice_text(&text, at, 0, "x").unwrap()); assert_eq!( Written::default().check(&held, &typed, &typed.decode()), None, "{:?}", typed.decode().operations ); } let begin = automerge::legacy::OpId(marked.start_op().get(), marked.actor_id().clone()); let deleted = on(&held, |doc| doc.splice_text(&text, 0, 1, "").unwrap()); let at_the_begin = crafted(&deleted, |change| { change.operations[0].key = automerge::legacy::Key::Seq(automerge::legacy::ElementId::Id(begin.clone())); change.operations[0].pred = vec![begin.clone()].into(); }); assert!( Written::default() .check(&held, &at_the_begin, &at_the_begin.decode()) .is_some() ); } /// No table: made, by itself or with what is written into it, or written into /// where the document holds one. Automerge panics applying a change that writes /// into one; transactions can't, and continuum's store makes none. #[test] fn no_table() { use crate::document::Transaction; use automerge::ObjType; use automerge::legacy::{ObjectId, OpId, OpType}; let mut theirs = Document::new(); let map = change(&mut theirs, |doc| { let map = doc.put_object(ROOT, "map", ObjType::Map).unwrap(); doc.put_object(ROOT, "table", ObjType::Table).unwrap(); map }); let first = theirs.get_last_local_change().unwrap(); assert!( Written::default() .check(&Document::new(), &first, &first.decode()) .is_some() ); // As if it was taken without screening. let table = ObjectId::Id(OpId(first.start_op().get() + 1, first.actor_id().clone())); let mut ours = Document::new(); ours.apply_changes([first]).unwrap(); fn on(doc: &Document, write: impl FnOnce(&mut Transaction<'_>)) -> Change { let mut fork = doc.fork(); change(&mut fork, write); fork.get_last_local_change().unwrap() } let put = on(&ours, |doc| doc.put(&map, "k", 1).unwrap()); let made = on(&ours, |doc| { let made = doc.put_object(ROOT, "made", ObjType::Map).unwrap(); doc.put(&made, "k", 1).unwrap(); }); for honest in [&put, &made] { assert_eq!( Written::default().check(&ours, honest, &honest.decode()), None ); } let crafted = [ crafted(&put, |change| change.operations[0].obj = table.clone()), crafted(&made, |change| { change.operations[0].action = OpType::Make(ObjType::Table) }), ]; for crafted in crafted { let why = Written::default().check(&ours, &crafted, &crafted.decode()); assert!(why.is_some(), "{:?}", crafted.decode().operations); } } /// What an operation replaces put a value or made an object, as a transaction names /// it: a counter incremented and put over names its put alone, a key put again /// after its deletion names nothing. One naming a deletion Automerge takes, and /// then gives back another change under its hash, or panics giving it back. #[test] fn only_what_holds_a_value_is_replaced() { use crate::document::Transaction; use automerge::legacy::{ElementId, Key, OpId}; use automerge::{ObjType, ScalarValue}; let mut theirs = Document::new(); let list = change(&mut theirs, |doc| { doc.put(ROOT, "k", 1).unwrap(); doc.put(ROOT, "count", ScalarValue::counter(0)).unwrap(); doc.put(ROOT, "other", ScalarValue::counter(0)).unwrap(); let list = doc.put_object(ROOT, "list", ObjType::List).unwrap(); doc.insert(&list, 0, "a").unwrap(); doc.insert(&list, 1, "b").unwrap(); list }); let first = theirs.get_last_local_change().unwrap(); change(&mut theirs, |doc| { doc.delete(ROOT, "k").unwrap(); doc.delete(ROOT, "count").unwrap(); doc.delete(&list, 0).unwrap(); }); let deleted = theirs.get_last_local_change().unwrap(); // The first change's operations: 4 the list's "a", 5 its "b"; the second's: 0 // the deletion of "k", 1 of "count", 2 of the list's "a". let actor = first.actor_id().clone(); let made = |change: &Change, index: u64| OpId(change.start_op().get() + index, actor.clone()); let mut ours = Document::new(); ours.apply_changes([first.clone(), deleted.clone()]) .unwrap(); fn on(doc: &Document, write: impl FnOnce(&mut Transaction<'_>)) -> Change { let mut fork = doc.fork(); change(&mut fork, write); fork.get_last_local_change().unwrap() } let put_again = on(&ours, |doc| doc.put(ROOT, "k", 2).unwrap()); let put_over = on(&ours, |doc| doc.put(&list, 0, "B").unwrap()); let delete = on(&ours, |doc| doc.delete(&list, 0).unwrap()); let increment = on(&ours, |doc| doc.increment(ROOT, "other", 1).unwrap()); let counted_over = on(&ours, |doc| { doc.increment(ROOT, "other", 1).unwrap(); doc.increment(ROOT, "other", 1).unwrap(); doc.put(ROOT, "other", 5).unwrap(); }); for honest in [&put_again, &put_over, &delete, &increment, &counted_over] { assert_eq!( Written::default().check(&ours, honest, &honest.decode()), None, "{:?}", honest.decode().operations ); } let at_a = Key::Seq(ElementId::Id(made(&first, 4))); let crafted = [ // A key put again, naming its deletion. crafted(&put_again, |change| { change.operations[0].pred = vec![made(&deleted, 0)].into() }), // The same at a list's element, put over and deleted. crafted(&put_over, |change| { change.operations[0].key = at_a.clone(); change.operations[0].pred = vec![made(&deleted, 2)].into(); }), crafted(&delete, |change| { change.operations[0].key = at_a.clone(); change.operations[0].pred = vec![made(&deleted, 2)].into(); }), // A counter incremented, naming its deletion. crafted(&increment, |change| { change.operations[0].key = Key::Map("count".into()); change.operations[0].pred = vec![made(&deleted, 1)].into(); }), // Put over, naming an increment. crafted(&counted_over, |change| { let increment = OpId(change.start_op.get(), change.actor_id.clone()); change.operations[2].pred = vec![increment].into(); }), ]; for crafted in crafted { let why = Written::default().check(&ours, &crafted, &crafted.decode()); assert!(why.is_some(), "{:?}", crafted.decode().operations); } } /// A fork of a change the document holds, checked before an honest change of the /// same batch and refused after (as forged): it doesn't stand in for the change the /// document holds, and the honest change passes. #[test] fn a_change_refused_after_its_check_stands_in_for_nothing() { let mut theirs = Document::new(); let map = change(&mut theirs, |doc| { doc.put_object(ROOT, "map", automerge::ObjType::Map) .unwrap() }); let made = theirs.get_last_local_change().unwrap(); let mut ours = Document::new(); ours.apply_changes([made.clone()]).unwrap(); change(&mut theirs, |doc| doc.put(&map, "k", 1).unwrap()); let honest = theirs.get_last_local_change().unwrap(); // The same actor and counters as the change that made the map, putting a // number where the map was made. let fork = crafted(&made, |change| { change.operations[0].action = automerge::legacy::OpType::Put(1.into()); }); assert_ne!(fork.hash(), made.hash()); let mut written = Written::default(); assert_eq!(written.check(&ours, &fork, &fork.decode()), None); // Not taken: screening refuses it as forged. assert_eq!(written.check(&ours, &honest, &honest.decode()), None); } /// Changes generated, not listed: on documents honest nodes wrote at once (maps, a /// list, a text, counters), changes of one to four operations of every kind, at /// random places, naming as replaced nothing, what is there, or any operation. /// Each that passes the checks is applied, given back by its hash, saved and /// loaded, taken by a peer that lacks it, written after by an honest node, and /// saved and loaded again: none of it may fail or panic. `CHANGES_GENERATED` /// sets how many documents (default 60); the seed is in what fails. #[test] fn what_passes_leaves_automerge_sound() { use crate::document::testing::try_change; use automerge::legacy::{ElementId, Key, ObjectId, OpId, OpType}; use automerge::{ObjType, ScalarValue}; /// SplitMix64: the same seed, the same run. struct Random(u64); impl Random { fn next(&mut self) -> u64 { self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15); let mut z = self.0; z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9); z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb); z ^ (z >> 31) } fn below(&mut self, n: usize) -> usize { (self.next() % n.max(1) as u64) as usize } fn one<'a, T>(&mut self, of: &'a [T]) -> Option<&'a T> { (!of.is_empty()).then(|| &of[self.below(of.len())]) } fn actor(&mut self) -> ActorId { ActorId::from(self.next().to_be_bytes().to_vec()) } } /// One honest write, at random; refused writes (a deletion of nothing) are /// dropped. fn honest_write(doc: &mut Document, random: &mut Random) { let pick = random.below(9); let key = format!("k{}", random.below(4)); let at = random.below(4); let value = random.next() as i64 % 100; let _ = try_change(doc, |tx| -> Result<(), automerge::AutomergeError> { let (_, map) = tx.get(ROOT, "map")?.expect("the map"); let (_, list) = tx.get(ROOT, "list")?.expect("the list"); let (_, text) = tx.get(ROOT, "text")?.expect("the text"); let len = tx.length(&list); let text_len = tx.length(&text); match pick { 0 => tx.put(&map, key, value)?, 1 => tx.delete(&map, key)?, 2 => tx.insert(&list, at.min(len), value)?, 3 if len > 0 => tx.put(&list, at % len, value)?, 4 if len > 0 => tx.delete(&list, at % len)?, 5 => tx.splice_text(&text, at.min(text_len), 0, "xy")?, 6 if text_len > 0 => tx.splice_text(&text, at % text_len, 1, "")?, 7 => tx.increment(ROOT, "count", 1)?, _ => { tx.put_object(&map, key, ObjType::List)?; } } Ok(()) }); } /// What a document is made of: every operation by its ID, the object it is in, /// its key, whether it inserted, and the object it made. type Made = Vec<(OpId, ObjectId, Key, bool, Option)>; fn made(doc: &Document) -> Made { let mut made = Vec::new(); for change in doc.get_changes(&[]) { let start = change.start_op().get(); let actor = change.actor_id().clone(); for (index, op) in change.decode().operations.into_iter().enumerate() { let makes = match op.action { OpType::Make(kind) => Some(kind), _ => None, }; made.push(( OpId(start + index as u64, actor.clone()), op.obj, op.key, op.insert, makes, )); } } made } /// `crafted`, applied to a copy of `doc`, and all the rest asked of it. fn sound(doc: &Document, crafted: &Change, random: &mut Random) -> Result<(), String> { let mut doc = doc.clone(); doc.apply_changes([crafted.clone()]) .map_err(|e| format!("applied: {e}"))?; let back = doc .get_change_by_hash(&crafted.hash()) .ok_or("not given back")?; if back.raw_bytes() != crafted.raw_bytes() { return Err("another change given back under its hash".to_owned()); } let loaded = Document::load(&doc.save()).map_err(|e| format!("loaded: {e}"))?; if loaded.get_heads() != doc.get_heads() { return Err("loaded with other heads".to_owned()); } let mut peer = Document::new(); peer.apply_changes(doc.get_changes(&[])) .map_err(|e| format!("taken by a peer: {e}"))?; if peer.get_heads() != doc.get_heads() { return Err("a peer came to other heads".to_owned()); } let mut after = loaded.with_actor(random.actor()); let before = after.get_heads(); for _ in 0..4 { honest_write(&mut after, random); } let _ = after.get_last_local_change(); let _ = after.save_after(&before); Document::load(&after.save()).map_err(|e| format!("written after, loaded: {e}"))?; Ok(()) } let documents: u64 = std::env::var("CHANGES_GENERATED") .ok() .and_then(|count| count.parse().ok()) .unwrap_or(60); let (mut passed, mut checked) = (0, 0); for seed in 0..documents { let mut random = Random(seed); let mut doc = Document::new().with_actor(random.actor()); change(&mut doc, |tx| { tx.put_object(ROOT, "map", ObjType::Map).unwrap(); let list = tx.put_object(ROOT, "list", ObjType::List).unwrap(); tx.insert(&list, 0, 0).unwrap(); let text = tx.put_object(ROOT, "text", ObjType::Text).unwrap(); tx.splice_text(&text, 0, 0, "ab").unwrap(); tx.put(ROOT, "count", ScalarValue::counter(0)).unwrap(); }); let mut writers: Vec = (0..3) .map(|_| doc.fork().with_actor(random.actor())) .collect(); for _ in 0..8 { let writer = random.below(writers.len()); honest_write(&mut writers[writer], &mut random); } for writer in &mut writers { doc.merge(writer).unwrap(); } let made = made(&doc); let objects: Vec<(ObjectId, ObjType)> = std::iter::once((ObjectId::Root, ObjType::Map)) .chain(made.iter().filter_map(|(id, _, _, _, makes)| { makes.map(|kind| (ObjectId::Id(id.clone()), kind)) })) .collect(); for _ in 0..40 { // Honest puts, as many as the operations crafted, then made over. let count = 1 + random.below(4); let mut fork = doc.fork().with_actor(random.actor()); change(&mut fork, |tx| { for index in 0..count { tx.put(ROOT, format!("z{index}"), 0).unwrap(); } }); let honest = fork.get_last_local_change().unwrap(); let crafted = crafted(&honest, |change| { for op in change.operations.iter_mut() { let (obj, kind) = random.one(&objects).unwrap().clone(); op.obj = obj.clone(); let elements: Vec = made .iter() .filter(|(_, in_obj, _, insert, _)| *insert && *in_obj == obj) .map(|(id, ..)| id.clone()) .collect(); let in_list = matches!(kind, ObjType::List | ObjType::Text); op.key = match (in_list != (random.below(8) == 0), random.below(3)) { (false, _) => Key::Map(format!("k{}", random.below(4)).into()), (true, 0) => Key::Seq(ElementId::Head), (true, _) => match random.one(&elements) { Some(id) => Key::Seq(ElementId::Id(id.clone())), None => Key::Seq(ElementId::Head), }, }; op.insert = in_list && random.below(2) == 0; op.action = match random.below(7) { 0 => OpType::Make(ObjType::Map), 1 => OpType::Make(ObjType::List), 2 => OpType::Delete, 3 => OpType::Increment(1), 4 => OpType::Put(ScalarValue::counter(1)), _ => OpType::Put(ScalarValue::Int(7)), }; // Named as replaced: nothing, what is at that place, or any. let there: Vec = made .iter() .filter(|(id, in_obj, key, insert, _)| { *in_obj == obj && (*key == op.key || (*insert && op.key == Key::Seq(ElementId::Id(id.clone())))) }) .map(|(id, ..)| id.clone()) .collect(); let any: Vec = made.iter().map(|(id, ..)| id.clone()).collect(); op.pred = match random.below(4) { 0 => Vec::new(), 1 | 2 => random.one(&there).into_iter().cloned().collect(), _ => random.one(&any).into_iter().cloned().collect(), } .into(); } }); checked += 1; let decoded = crafted.decode(); if Written::default().check(&doc, &crafted, &decoded).is_some() { continue; } passed += 1; let outcome = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| { sound(&doc, &crafted, &mut random) })) .unwrap_or_else(|_| Err("panicked".to_owned())); if let Err(what) = outcome { panic!( "seed {seed}: a change that passed broke Automerge ({what}): {:?}", decoded.operations ); } } } assert!( passed > 0 && passed < checked, "{passed} of {checked} passed" ); } }