diff options
Diffstat (limited to 'src/document')
| -rw-r--r-- | src/document/changes.rs | 254 | ||||
| -rw-r--r-- | src/document/testing.rs | 64 |
2 files changed, 317 insertions, 1 deletions
diff --git a/src/document/changes.rs b/src/document/changes.rs index fd14a4e..6e3fb51 100644 --- a/src/document/changes.rs +++ b/src/document/changes.rs @@ -6,7 +6,7 @@ use std::collections::{HashMap, HashSet}; use anyhow::{Result, anyhow, bail}; -use super::{Change, ChangeHash, Document, ReadDoc}; +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 @@ -283,6 +283,113 @@ pub(crate) fn changes_in(mut data: &[u8]) -> Option<Vec<Change>> { Some(changes) } +/// What the changes of a batch made that passed [`Written::check`]: those after them +/// in the batch build on them before the document holds them. +#[derive(Default)] +pub(crate) struct Written { + /// The highest operation counter of each. + max_ops: HashMap<ChangeHash, u64>, + /// The operation counters each made, by its actor: first and last. + ops: HashMap<ActorId, Vec<(u64, u64)>>, +} + +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: + /// + /// * 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.) + /// * Every operation it names (an object written into, an element of a list, an + /// operation replaced) is one of its own, or one made before it, in `doc` or by + /// a change checked before. + pub(crate) fn check( + &mut self, + doc: &Document, + change: &Change, + expanded: &ExpandedChange, + ) -> Option<String> { + use automerge::legacy::{ElementId, Key, ObjectId, OpId}; + let hash = change.hash(); + if Change::from(expanded.clone()).hash() != 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 before: Option<u64> = change + .deps() + .iter() + .map(|dep| { + self.max_ops + .get(dep) + .copied() + .or_else(|| doc.get_change_meta_by_hash(dep).map(|meta| meta.max_op)) + }) + .try_fold(0, |highest, max_op| { + max_op.map(|max_op| highest.max(max_op)) + }); + // A dependency neither here nor there: not ready, and Automerge doesn't apply + // it (callers judge those whose dependencies they hold). + if let Some(before) = before + && start != before + 1 + { + return Some(format!( + "its first operation is numbered {start}, not {}, one after the highest of its dependencies", + before + 1 + )); + } + let actor = change.actor_id(); + let made = |OpId(counter, by): &OpId| { + if by == actor && (start..=last).contains(counter) { + return true; + } + *counter < start + && (self.ops.get(by).is_some_and(|ranges| { + ranges + .iter() + .any(|(first, last)| (*first..=*last).contains(counter)) + }) || doc + .hash_for_opid(&automerge::ObjId::Id(*counter, by.clone(), 0)) + .is_some()) + }; + for op in &expanded.operations { + let object = match &op.obj { + ObjectId::Id(id) => Some(id), + ObjectId::Root => None, + }; + let element = match &op.key { + Key::Seq(ElementId::Id(id)) => Some(id), + Key::Seq(ElementId::Head) | Key::Map(_) => None, + }; + if let Some(OpId(counter, by)) = object + .into_iter() + .chain(element) + .chain(op.pred.iter()) + .find(|id| !made(id)) + { + return Some(format!( + "it names an operation nobody made before it ({counter}@{by})" + )); + } + } + self.max_ops.insert(hash, last); + if last >= start { + self.ops + .entry(actor.clone()) + .or_default() + .push((start, last)); + } + None + } +} + /// `change`, if it names an author but isn't its actor's first (`misplaced_author`). fn misplaced_in(change: &Change) -> Option<MisplacedAuthor> { let author = change.author()?; @@ -539,4 +646,149 @@ mod tests { // 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; + 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) + }); + 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(); + }); + let mut other = doc.fork(); + 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 { + assert_eq!(written.check(&empty, change, &change.decode()), None); + } + } + + /// 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("nobody made"), "{object:?}: {why}"); + } + } } diff --git a/src/document/testing.rs b/src/document/testing.rs index cd6c15b..1e83db2 100644 --- a/src/document/testing.rs +++ b/src/document/testing.rs @@ -74,3 +74,67 @@ pub(crate) fn with_author_footer(raw: &[u8], author: &[u8]) -> Vec<u8> { out.extend(body); out } + +/// `raw` (an uncompressed change chunk whose operations name no actor but its own) +/// listing `spare` among its other actors, its checksum made right again: bytes that +/// load as a change and aren't the ones Automerge encodes for it (`changes::Written`). +pub(crate) fn with_spare_actor(raw: &[u8], spare: &[u8]) -> Vec<u8> { + use sha2::{Digest, Sha256}; + fn leb(mut n: usize, out: &mut Vec<u8>) { + loop { + let byte = (n & 0x7f) as u8; + n >>= 7; + if n == 0 { + out.push(byte); + return; + } + out.push(byte | 0x80); + } + } + // A number (LEB128) at `at`, and how many bytes it takes. + fn read(bytes: &[u8], at: usize) -> (usize, usize) { + let (mut n, mut read, mut shift) = (0usize, 0, 0); + loop { + let byte = bytes[at + read]; + n |= usize::from(byte & 0x7f) << shift; + read += 1; + if byte & 0x80 == 0 { + return (n, read); + } + shift += 7; + } + } + assert_eq!(raw[8], 1, "an uncompressed change chunk"); + let (length, taken) = read(raw, 9); + let body = &raw[9 + taken..9 + taken + length]; + // Its dependencies, its actor, its seq and first operation, its time, its message: + // then the other actors. + let (deps, taken) = read(body, 0); + let mut at = taken + 32 * deps; + let (actor, taken) = read(body, at); + at += taken + actor; + for _ in 0..3 { + at += read(body, at).1; + } + let (message, taken) = read(body, at); + at += taken + message; + let (others, taken) = read(body, at); + assert_eq!(others, 0, "a change naming no other actor"); + let mut crafted = body[..at].to_vec(); + crafted.push(1); + leb(spare.len(), &mut crafted); + crafted.extend_from_slice(spare); + crafted.extend_from_slice(&body[at + taken..]); + let mut header = Vec::new(); + leb(crafted.len(), &mut header); + let mut summed = vec![1u8]; + summed.extend(&header); + summed.extend(&crafted); + let sum = Sha256::digest(&summed); + let mut out = raw[..4].to_vec(); + out.extend(&sum[..4]); + out.push(1); + out.extend(header); + out.extend(crafted); + out +} |
