aboutsummaryrefslogtreecommitdiffstats
path: root/src/document/changes.rs
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-13 01:05:49 +0000
committertv <tv@krebsco.de>2026-11-13 01:05:49 +0000
commit6cb4d3fd8f5024c340bd9321a434c8579cce81e7 (patch)
treea7b79b83acafd0f37ed9c0ed3f683488e4e32d66 /src/document/changes.rs
parente519ade32a87811f287bb851e3e1dfcde6b064c9 (diff)
screen: what is asked of a change, asked of its own history
A change is refused before Automerge sees it unless it is one Automerge writes (`document::changes::Written`). Three things about that, each of which let a crafted change through or parted nodes: * An operation a change names (the object written into, a list's element, an operation replaced) must be made in the change's own history, or before in the change itself, not anywhere in the document. Else a node that holds the operation takes the change and one that doesn't yet refuses it for good: nodes part by the order changes reach them. * And it must be what it is named as: an object of the kind written into, an element of that list, an operation at the place written. A change that replaces an operation elsewhere marks an unrelated value gone, and Automerge then gives back another change under its hash and saves a document that doesn't load; one that writes into an operation that made no object makes it panic. * A change that isn't its actor's first must have the one before it among its dependencies, as a transaction puts it there. A gap in an actor's numbers makes Automerge panic. What the document holds at the changes this one builds on is read there where it can be (a map's key, an object held by a map's key); else the operation's own change is decoded and the history walked back to it, no further than the operation's counter. So operations on a list's elements cost a walk each. Decoding a change can panic too (an operation naming an actor its change doesn't list): caught, and the change refused as one whose bytes aren't Automerge's.
Diffstat (limited to 'src/document/changes.rs')
-rw-r--r--src/document/changes.rs494
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()
+ );
+ }
}