diff options
Diffstat (limited to 'src/document')
| -rw-r--r-- | src/document/changes.rs | 494 |
1 files changed, 439 insertions, 55 deletions
diff --git a/src/document/changes.rs b/src/document/changes.rs index 6e3fb51..d4256c3 100644 --- a/src/document/changes.rs +++ b/src/document/changes.rs @@ -283,14 +283,81 @@ pub(crate) fn changes_in(mut data: &[u8]) -> Option<Vec<Change>> { 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<automerge::ObjType>, +} + +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, + }, + } + } +} + +/// A change of a batch that passed [`Written::check`]. +struct Passed { + deps: Vec<ChangeHash>, + 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<ChangeHash>, +} + +/// 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<ChangeHash>, +} + /// 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)>>, + passed: HashMap<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<ChangeHash, Option<ExpandedChange>>, } impl Written { @@ -299,7 +366,11 @@ impl Written { /// 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: + /// 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.) @@ -307,9 +378,14 @@ impl Written { /// 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. + /// * 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. (One naming an operation elsewhere marks an unrelated value gone, and + /// the document then gives back another change under this one's hash.) pub(crate) fn check( &mut self, doc: &Document, @@ -318,76 +394,234 @@ impl Written { ) -> Option<String> { use automerge::legacy::{ElementId, Key, ObjectId, OpId}; let hash = change.hash(); - if Change::from(expanded.clone()).hash() != 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 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 - { + 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<ChangeHash> = 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 )); } - 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()) + 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 op in &expanded.operations { - let object = match &op.obj { - ObjectId::Id(id) => Some(id), - ObjectId::Root => None, + 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<Made> { + 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; + } + let made = written.made(doc, id)?; + written + .reaches(doc, &mut history, made.change, *counter) + .then_some(made) + }; + // The object written into: one, of the kind the key is for. + let in_list = matches!(op.key, Key::Seq(_)); + let fits = |kind: automerge::ObjType| { + in_list == matches!(kind, automerge::ObjType::List | automerge::ObjType::Text) }; + // Whether the object is one the document held at `doc_heads`, for what + // can then be read there. + let mut held = false; + 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)) + && doc.object_type(&object).is_ok_and(fits) + && 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, + }); + if seen { + held = true; + } else if !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. 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)) + if let Some(id) = element + && !made(self, id).is_some_and(|made| made.insert && made.obj == op.obj) { + let OpId(counter, by) = id; return Some(format!( - "it names an operation nobody made before it ({counter}@{by})" + "it names {counter}@{by}, no element of that list put there before it" )); } + // What it replaces: operations at its place. + let there: Vec<automerge::ObjId> = 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.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.max_ops.insert(hash, last); - if last >= start { + + for (index, op) in expanded.operations.iter().enumerate() { self.ops - .entry(actor.clone()) - .or_default() - .push((start, last)); + .insert((actor.clone(), start + index as u64), Made::of(hash, op)); } + self.passed.insert( + hash, + Passed { + deps: change.deps().to_vec(), + actor: actor.clone(), + seq: change.seq(), + max_op: last, + doc_heads, + }, + ); None } + + /// The highest operation counter of a change of the batch or the document. + fn max_op(&self, doc: &Document, hash: &ChangeHash) -> Option<u64> { + 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 or the document. + fn made(&mut self, doc: &Document, id: &automerge::legacy::OpId) -> Option<Made> { + let automerge::legacy::OpId(counter, by) = id; + if let Some(made) = self.ops.get(&(by.clone(), *counter)) { + return Some(made.clone()); + } + 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| change.decode())) + .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) + } } /// `change`, if it names an author but isn't its actor's first (`misplaced_author`). @@ -788,7 +1022,157 @@ mod tests { let why = Written::default() .check(&ours, &crafted, &crafted.decode()) .expect("refused"); - assert!(why.contains("nobody made"), "{object:?}: {why}"); + 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<OpId> = 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..] { + assert_eq!(written.check(&ours, change, &change.decode()), None); + } + // 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] { + assert_eq!( + written.check(&Document::new(), change, &change.decode()), + None + ); + } + assert!( + written + .check(&Document::new(), &elsewhere, &elsewhere.decode()) + .is_some() + ); + } } |
