aboutsummaryrefslogtreecommitdiffstats
path: root/src/document/changes.rs
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-12 22:23:15 +0000
committertv <tv@krebsco.de>2026-11-12 22:23:15 +0000
commite519ade32a87811f287bb851e3e1dfcde6b064c9 (patch)
tree9fff94327105957f3a958d55a668cc3a5cf6bf9a /src/document/changes.rs
parentbfe93eea9b707b29b78e1f9a7a425e6f891701a0 (diff)
screen: refuse changes Automerge wouldn't have written
Automerge 0.12.0 applies a change that lists an actor none of its operations names, or whose first operation is numbered below its dependencies' or near 2^32. It then gives back another change than the one it was given and saves a document that doesn't load, or panics at the next write. A member sending one stops the nodes that take it. Every change from elsewhere is looked at before Automerge sees it (`document::changes::Written`, from `access::screen::apply`, with or without a policy), and refused like one breaking a rule unless: * encoded again, it has the hash it came with; * its first operation is numbered one after the highest of its dependencies, 1 without any, as a transaction at the document's heads numbers it; * every operation it names (an object, a list's element, an operation replaced) is its own, or was made before it, in the document or by a change of the batch looked at before.
Diffstat (limited to 'src/document/changes.rs')
-rw-r--r--src/document/changes.rs254
1 files changed, 253 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}");
+ }
+ }
}