From 79f17df285e376892c691b7a27f90a89cf8a32ea Mon Sep 17 00:00:00 2001 From: tv Date: Fri, 13 Nov 2026 03:25:50 +0000 Subject: screen: a change refused after its checks stands in for nothing Screening checks that a change is one Automerge writes (`changes::Written`) before it looks for forks and judges the rules, and the checks recorded what a change made as soon as it passed them. A fork of a change the document holds has its actor and counters: if it was checked first in a batch, and refused as forged after, its record stood in for that change's operations, outside the history of the next. An honest change writing into what the real one made was then refused, for good. Anyone could make such a fork, its hash ground to sort first. What a change made is recorded once screening takes it (`Written::taken`), and an operation named is looked for in the batch and in the document, whichever the change's history holds. --- src/document/changes.rs | 107 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 83 insertions(+), 24 deletions(-) (limited to 'src/document/changes.rs') diff --git a/src/document/changes.rs b/src/document/changes.rs index d4256c3..11d0228 100644 --- a/src/document/changes.rs +++ b/src/document/changes.rs @@ -349,11 +349,15 @@ struct History { seen: std::collections::HashSet, } -/// 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. +/// 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. @@ -386,6 +390,9 @@ impl Written { /// 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.) + /// + /// 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, @@ -393,6 +400,7 @@ impl Written { 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() @@ -460,10 +468,12 @@ impl Written { if *counter >= start { return None; } - let made = written.made(doc, id)?; - written - .reaches(doc, &mut history, made.change, *counter) - .then_some(made) + // 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)) }; // The object written into: one, of the kind the key is for. let in_list = matches!(op.key, Key::Seq(_)); @@ -548,11 +558,7 @@ impl Written { } } - for (index, op) in expanded.operations.iter().enumerate() { - self.ops - .insert((actor.clone(), start + index as u64), Made::of(hash, op)); - } - self.passed.insert( + self.checked = Some(( hash, Passed { deps: change.deps().to_vec(), @@ -561,10 +567,30 @@ impl Written { 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 @@ -573,17 +599,20 @@ impl Written { .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 { + /// 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; - 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())) + .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()?)?; @@ -928,7 +957,9 @@ mod tests { let empty = Document::new(); let mut written = Written::default(); for change in &changes { - assert_eq!(written.check(&empty, change, &change.decode()), None); + let expanded = change.decode(); + assert_eq!(written.check(&empty, change, &expanded), None); + written.taken(change, &expanded); } } @@ -1153,7 +1184,9 @@ mod tests { 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); + 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(); @@ -1164,10 +1197,9 @@ mod tests { }); let mut written = Written::default(); for change in &changes[..changes.len() - 1] { - assert_eq!( - written.check(&Document::new(), change, &change.decode()), - None - ); + let expanded = change.decode(); + assert_eq!(written.check(&Document::new(), change, &expanded), None); + written.taken(change, &expanded); } assert!( written @@ -1175,4 +1207,31 @@ mod tests { .is_some() ); } + + /// 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); + } } -- cgit v1.3.1