aboutsummaryrefslogtreecommitdiffstats
path: root/src/document/changes.rs
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-13 04:49:38 +0000
committertv <tv@krebsco.de>2026-11-13 04:49:38 +0000
commit369cfb6a110ed384f18792ccd13a50f7cf27559a (patch)
tree3b792e3cbd40967cdf2ed011196d44ee6d16af05 /src/document/changes.rs
parent519e0a1019b9f74ce8a12773a47d613a05aecdf8 (diff)
screen: take only the operations transactions write
Screening asked what an operation isn't: a deletion replacing nothing, a value put at a list's head without inserting, a mark ended but right after its begin. Others pass that Automerge's transactions never write, and Automerge takes them and breaks: an element written over naming as replaced the element inserted after it (an inserted element's key is the element it follows, its place is itself), an insert replacing something, a deletion or an increment inserted, an increment at a list's head, a mark ended ahead of its begin or at the head, a mark in a list. Giving such a change back panics or gives another change under its hash, and the save doesn't load. Each operation is now asked to be one transactions write (`document::changes::unwritten`): inserted, a value, an object or a mark's begin or end into a list or a text, replacing nothing; at a list's element, never its head, without inserting, replacing what is at that element; at a map's key, never inserted, a deletion or an increment replacing something; a mark's begin with its end as the next operation, both inserted. A value replaced at a list's element is the element itself or written at it, not an element inserted after it. Marks are only in a text, and a mark's end is at its begin or at an element after the begin's: their places follow from the elements each is inserted after, back to the text's head, as the change's history holds them. The document the tests write now has counters in a list and a map, an element written over, and marks over a span, the whole text, none of it, and across what was deleted and inserted since; and each case above is a test.
Diffstat (limited to 'src/document/changes.rs')
-rw-r--r--src/document/changes.rs429
1 files changed, 344 insertions, 85 deletions
diff --git a/src/document/changes.rs b/src/document/changes.rs
index 1e674dc..426c5d2 100644
--- a/src/document/changes.rs
+++ b/src/document/changes.rs
@@ -390,10 +390,10 @@ 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.)
- /// * Nothing Automerge's transactions never write: a deletion that replaces
- /// nothing; a value put at a list's head without being inserted; a mark ended
- /// but by the operation after the one that began it. (Automerge takes those, and
- /// then can't give the change back: its save doesn't load.)
+ /// * Every operation is one Automerge's transactions write ([`unwritten`] says
+ /// which), and a mark ends at its begin or at an element after the begin's in
+ /// the text. (Automerge takes others, and then can't give the change back, or
+ /// panics giving it, and its save doesn't load.)
///
/// A change that passes is among those the next are checked against only once
/// it is [`Written::taken`].
@@ -479,29 +479,9 @@ impl Written {
.flatten()
.find(|made| written.reaches(doc, &mut history, made.change, *counter))
};
- // What Automerge's transactions never write.
- match &op.action {
- OpType::Delete if op.pred.is_empty() => {
- return Some("it deletes, replacing nothing".to_owned());
- }
- OpType::Put(_) | OpType::Make(_)
- if !op.insert && matches!(op.key, Key::Seq(ElementId::Head)) =>
- {
- return Some(
- "it puts a value at a list's head without inserting it".to_owned(),
- );
- }
- OpType::MarkEnd(_)
- if !(index > 0
- && matches!(
- expanded.operations[index - 1].action,
- OpType::MarkBegin(..)
- )
- && expanded.operations[index - 1].obj == op.obj) =>
- {
- return Some("it ends a mark but right after the one that began it".to_owned());
- }
- _ => {}
+ // What it is: one of what Automerge's transactions write.
+ if let Some(why) = unwritten(&expanded.operations, index) {
+ return Some(why.to_owned());
}
// The object written into: one, of the kind the key is for.
let in_list = matches!(op.key, Key::Seq(_));
@@ -509,24 +489,27 @@ impl Written {
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 {
+ // can then be read there, and its kind.
+ let held;
+ let kind = match &op.obj {
ObjectId::Root => {
if in_list {
return Some("it writes a list's element into the root".to_owned());
}
held = true;
+ automerge::ObjType::Map
}
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)
+ let seen = (!doc_heads.is_empty()
+ && !self.ops.contains_key(&(id.1.clone(), id.0)))
+ .then(|| doc.object_type(&object).ok())
+ .flatten()
+ .filter(|kind| fits(*kind))
+ .filter(|_| {
+ doc.parents(&object)
.ok()
.and_then(|mut parents| parents.next())
.is_some_and(|parent| match parent.prop {
@@ -534,16 +517,27 @@ impl Written {
.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"
- ));
+ })
+ });
+ held = seen.is_some();
+ match seen.or_else(|| {
+ made(self, id)
+ .and_then(|made| made.makes)
+ .filter(|kind| fits(*kind))
+ }) {
+ Some(kind) => kind,
+ None => {
+ let OpId(counter, by) = id;
+ return Some(format!(
+ "it writes into {counter}@{by}, no object of that kind made before it"
+ ));
+ }
}
}
+ };
+ let marks = matches!(op.action, OpType::MarkBegin(_) | OpType::MarkEnd(_));
+ if marks && kind != automerge::ObjType::Text {
+ return Some("it marks in a list, not a text".to_owned());
}
// The element of a list: one put into that list.
let element = match &op.key {
@@ -576,7 +570,9 @@ impl Written {
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);
+ || made(self, id).is_some_and(|made| {
+ !made.insert && made.obj == op.obj && made.key == op.key
+ });
if !at_its_place {
let OpId(counter, by) = id;
return Some(format!(
@@ -584,6 +580,42 @@ impl Written {
));
}
}
+ // A mark's end: at its begin, or at an element after the begin's in the text
+ // (`unwritten`: the operation before begins it). Each is inserted after an
+ // element, ahead of what else was inserted there before it, so their places
+ // follow from the elements each was inserted after, back to the text's head.
+ if let (OpType::MarkEnd(_), Key::Seq(end_at)) = (&op.action, &op.key)
+ && !matches!(end_at, ElementId::Id(OpId(counter, by)) if by == actor && *counter == this - 1)
+ {
+ let Key::Seq(begin_at) = &expanded.operations[index - 1].key else {
+ return Some("it ends a mark begun at a map's key".to_owned());
+ };
+ let mut places = Vec::new();
+ for at in [end_at, begin_at] {
+ // The elements `at` is inserted after, nearest first: each made
+ // before the one inserted after it.
+ let mut place = Vec::new();
+ let mut at = at.clone();
+ while let ElementId::Id(id) = at {
+ let Some(made) = made(self, &id).filter(|made| {
+ made.insert
+ && made.obj == op.obj
+ && place.last().is_none_or(|after: &OpId| after.0 > id.0)
+ }) else {
+ return Some("it ends a mark at an element not in the text".to_owned());
+ };
+ place.push(id);
+ let Key::Seq(next) = made.key else {
+ return Some("it ends a mark at an element not in the text".to_owned());
+ };
+ at = next;
+ }
+ places.push(place);
+ }
+ if !after(&places[0], &places[1]) {
+ return Some("it ends a mark ahead of its begin".to_owned());
+ }
+ }
}
self.checked = Some((
@@ -681,6 +713,81 @@ impl Written {
}
}
+/// Why the operation at `index` of `operations` is none Automerge's transactions write,
+/// by itself and the operations next to it; None if it may be one ([`Written::check`]
+/// asks the rest of its history). What they write:
+///
+/// * Inserted: a value put, an object made, or a mark's begin or end, into a list or a
+/// text, after one of its elements or at its head, replacing nothing.
+/// * At a list's element, not inserted (never at its head): a value put, an object made,
+/// a deletion or an increment, replacing what is at that element.
+/// * At a map's key, never inserted: a value put, an object made, or a deletion or an
+/// increment replacing something; no mark.
+/// * A mark: its begin, and its end as the operation right after, both inserted.
+fn unwritten(operations: &[automerge::legacy::Op], index: usize) -> Option<&'static str> {
+ use automerge::legacy::{ElementId, Key, OpType};
+ let op = &operations[index];
+ let next = operations.get(index + 1).filter(|next| next.obj == op.obj);
+ let previous = index
+ .checked_sub(1)
+ .map(|previous| &operations[previous])
+ .filter(|previous| previous.obj == op.obj);
+ let mark = matches!(op.action, OpType::MarkBegin(_) | OpType::MarkEnd(_));
+ let replaces = !op.pred.is_empty();
+ match (&op.key, op.insert, &op.action) {
+ (Key::Map(_), true, _) => Some("it inserts at a map's key"),
+ (Key::Seq(_), true, OpType::Delete | OpType::Increment(_)) => {
+ Some("it inserts a deletion or an increment")
+ }
+ (Key::Seq(_), true, _) if replaces => Some("it inserts, replacing something"),
+ (_, false, _) if mark => Some("it marks without inserting"),
+ (Key::Seq(ElementId::Head), false, _) => {
+ Some("it writes at a list's head without inserting")
+ }
+ (Key::Seq(_), false, _) if !replaces => Some("it writes at an element, replacing nothing"),
+ (Key::Map(_), false, OpType::Delete | OpType::Increment(_)) if !replaces => {
+ Some("it deletes or increments, replacing nothing")
+ }
+ (_, true, OpType::MarkBegin(_))
+ if !next
+ .is_some_and(|next| next.insert && matches!(next.action, OpType::MarkEnd(_))) =>
+ {
+ Some("it begins a mark the operation after doesn't end")
+ }
+ (_, true, OpType::MarkEnd(_))
+ if !previous.is_some_and(|previous| {
+ previous.insert && matches!(previous.action, OpType::MarkBegin(_))
+ }) =>
+ {
+ Some("it ends a mark but right after the one that began it")
+ }
+ _ => None,
+ }
+}
+
+/// Whether the element at `place` comes after the one at `other` in a list, each given
+/// by the elements it is inserted after, nearest first, back to the list's head: after
+/// what it is inserted after, and of two inserted after the same, the one made first
+/// comes later (the one made last is put right after it).
+fn after(place: &[automerge::legacy::OpId], other: &[automerge::legacy::OpId]) -> bool {
+ let shared = place
+ .iter()
+ .rev()
+ .zip(other.iter().rev())
+ .take_while(|(one, two)| one == two)
+ .count();
+ match (place.len() - shared, other.len() - shared) {
+ // `place` is `other`, or one `other` is inserted after.
+ (0, _) => false,
+ // One inserted after `other`.
+ (_, 0) => true,
+ (one, two) => {
+ let (one, two) = (&place[one - 1], &other[two - 1]);
+ (one.0, &one.1) < (two.0, &two.1)
+ }
+ }
+}
+
/// `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()?;
@@ -941,7 +1048,8 @@ mod tests {
/// 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;
+ use automerge::marks::{ExpandMark, Mark};
+ use automerge::{ObjType, ScalarValue};
let mut doc = Document::new();
let (map, list) = change(&mut doc, |doc| {
let map = doc.put_object(ROOT, "map", ObjType::Map).unwrap();
@@ -951,14 +1059,63 @@ mod tests {
doc.insert(&list, 1, "two").unwrap();
(map, list)
});
- change(&mut doc, |doc| {
+ let text = 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();
+ text
+ });
+ // Counters in a list and a map, an element written over, marks over a span,
+ // the whole text and none of it.
+ change(&mut doc, |doc| {
+ let counters = doc.put_object(&map, "counters", ObjType::List).unwrap();
+ doc.insert(&counters, 0, ScalarValue::counter(1)).unwrap();
+ doc.increment(&counters, 0, 2).unwrap();
+ doc.insert(&counters, 1, "under").unwrap();
+ doc.put(&counters, 1, "over").unwrap();
+ doc.insert(&counters, 0, "at the head").unwrap();
+ doc.put(&map, "count", ScalarValue::counter(0)).unwrap();
+ doc.increment(&map, "count", 1).unwrap();
+ doc.mark(
+ &text,
+ Mark::new("bold".into(), true, 1, 3),
+ ExpandMark::After,
+ )
+ .unwrap();
+ doc.mark(&text, Mark::new("all".into(), true, 0, 5), ExpandMark::Both)
+ .unwrap();
+ doc.mark(
+ &text,
+ Mark::new("here".into(), true, 2, 2),
+ ExpandMark::Both,
+ )
+ .unwrap();
+ });
+ // Marks across what was deleted and what was inserted since.
+ change(&mut doc, |doc| {
+ doc.splice_text(&text, 1, 2, "").unwrap();
+ doc.mark(
+ &text,
+ Mark::new("bold".into(), false, 0, 2),
+ ExpandMark::None,
+ )
+ .unwrap();
+ doc.unmark(&text, "all", 1, 3, ExpandMark::Before).unwrap();
+ doc.splice_text(&text, 3, 0, "!").unwrap();
+ doc.mark(
+ &text,
+ Mark::new("tail".into(), true, 2, 4),
+ ExpandMark::After,
+ )
+ .unwrap();
});
let mut other = doc.fork();
+ change(&mut other, |doc| {
+ doc.mark(&text, Mark::new("other".into(), 1, 0, 1), ExpandMark::None)
+ .unwrap();
+ });
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());
@@ -1236,54 +1393,156 @@ mod tests {
);
}
- /// What Automerge's transactions never write: a deletion replacing nothing, a value
- /// put at a list's head without inserting, a mark ended but right after its begin.
+ /// Only what Automerge's transactions write passes: each operation by what it is,
+ /// what it replaces at its place, and a mark's end at its begin or after it in the
+ /// text. Each crafted change Automerge takes, and then can't give back, panics
+ /// giving back, or saves a document that doesn't load.
#[test]
- fn what_transactions_never_write_is_refused() {
- use automerge::legacy::{ElementId, Key, OpType};
+ fn only_what_transactions_write_passes() {
+ use crate::document::Transaction;
+ use automerge::legacy::{ElementId, Key, ObjectId, OpId, OpType};
+ use automerge::marks::{ExpandMark, Mark};
+ use automerge::{ObjType, ScalarValue};
let mut theirs = Document::new();
- let list = change(&mut theirs, |doc| {
+ let (list, counters, text) = change(&mut theirs, |doc| {
doc.put(ROOT, "k", 1).unwrap();
- let list = doc
- .put_object(ROOT, "list", automerge::ObjType::List)
- .unwrap();
+ let list = doc.put_object(ROOT, "list", ObjType::List).unwrap();
doc.insert(&list, 0, "a").unwrap();
- list
+ doc.insert(&list, 1, "c").unwrap();
+ let counters = doc.put_object(ROOT, "counters", ObjType::List).unwrap();
+ doc.insert(&counters, 0, ScalarValue::counter(1)).unwrap();
+ // "abc", "b" and "c" both inserted after "a".
+ let text = doc.put_object(ROOT, "text", ObjType::Text).unwrap();
+ doc.splice_text(&text, 0, 0, "a").unwrap();
+ doc.splice_text(&text, 1, 0, "c").unwrap();
+ doc.splice_text(&text, 1, 0, "b").unwrap();
+ (list, counters, text)
});
+ let first = theirs.get_last_local_change().unwrap();
+ assert_eq!(first.decode().operations.len(), 10);
+ let actor = first.actor_id().clone();
+ // The first change's operations: 1 the list, 2 its "a", 3 its "c" (after "a"),
+ // 7 the text's "a", 8 its "c" and 9 its "b" (both after "a").
+ let id = |index: u64| OpId(first.start_op().get() + index, actor.clone());
+ let at = |index: u64| Key::Seq(ElementId::Id(id(index)));
let mut ours = Document::new();
- ours.apply_changes(theirs.get_changes(&[])).unwrap();
- change(&mut theirs, |doc| doc.delete(ROOT, "k").unwrap());
- let delete = theirs.get_last_local_change().unwrap();
- change(&mut theirs, |doc| doc.insert(&list, 0, "b").unwrap());
- let insert = theirs.get_last_local_change().unwrap();
- // The insert builds on the delete: checked against a document that holds it,
- // or it isn't ready, and nothing is asked of it.
- let mut with_delete = ours.clone();
- with_delete.apply_changes([delete.clone()]).unwrap();
- for (doc, honest) in [(&ours, &delete), (&with_delete, &insert)] {
+ ours.apply_changes([first.clone()]).unwrap();
+ fn on(doc: &Document, write: impl FnOnce(&mut Transaction<'_>)) -> Change {
+ let mut fork = doc.fork();
+ change(&mut fork, write);
+ fork.get_last_local_change().unwrap()
+ }
+ let put_over = on(&ours, |doc| doc.put(&list, 0, "A").unwrap());
+ let delete = on(&ours, |doc| doc.delete(&list, 0).unwrap());
+ let increment = on(&ours, |doc| doc.increment(&counters, 0, 1).unwrap());
+ let insert = on(&ours, |doc| doc.insert(&list, 1, "b").unwrap());
+ let map_delete = on(&ours, |doc| doc.delete(ROOT, "k").unwrap());
+ let mark = |start, end| {
+ on(&ours, |doc| {
+ doc.mark(
+ &text,
+ Mark::new("bold".into(), true, start, end),
+ ExpandMark::None,
+ )
+ .unwrap()
+ })
+ };
+ // Begun after "a", ended after "b"; begun after "b", ended after "c".
+ let (mark, sibling) = (mark(1, 2), mark(2, 3));
+ let keys = |change: &Change| -> Vec<Key> {
+ change
+ .decode()
+ .operations
+ .iter()
+ .map(|op| op.key.clone())
+ .collect()
+ };
+ assert_eq!(keys(&mark), [at(7), at(9)]);
+ assert_eq!(keys(&sibling), [at(9), at(8)]);
+ for honest in [
+ &put_over,
+ &delete,
+ &increment,
+ &insert,
+ &map_delete,
+ &mark,
+ &sibling,
+ ] {
assert_eq!(
- Written::default().check(doc, honest, &honest.decode()),
- None
+ Written::default().check(&ours, honest, &honest.decode()),
+ None,
+ "{:?}",
+ honest.decode().operations
);
}
- let nothing_replaced = crafted(&delete, |change| {
- change.operations[0].pred = Vec::new().into();
- });
- let at_head = crafted(&insert, |change| {
- change.operations[0].insert = false;
- change.operations[0].key = Key::Seq(ElementId::Head);
- });
- // In the list, where the insert was: a mark's end nothing began.
- let mark_end = crafted(&insert, |change| {
- change.operations[0].action = OpType::MarkEnd(false);
- });
- for (doc, crafted) in [
- (&ours, nothing_replaced),
- (&with_delete, at_head),
- (&with_delete, mark_end),
- ] {
- let why = Written::default().check(doc, &crafted, &crafted.decode());
- assert!(why.is_some(), "{:?}", crafted.decode().operations[0]);
+ let crafted = [
+ // An element written over, naming as replaced the element inserted after it.
+ crafted(&put_over, |change| {
+ change.operations[0].pred = vec![id(3)].into()
+ }),
+ crafted(&delete, |change| {
+ change.operations[0].pred = vec![id(3)].into()
+ }),
+ // The same at the list's head, naming its first element.
+ crafted(&delete, |change| {
+ change.operations[0].key = Key::Seq(ElementId::Head);
+ change.operations[0].pred = vec![id(2)].into();
+ }),
+ crafted(&increment, |change| {
+ change.operations[0].key = Key::Seq(ElementId::Head)
+ }),
+ crafted(&put_over, |change| {
+ change.operations[0].key = Key::Seq(ElementId::Head)
+ }),
+ // Written at an element, replacing nothing.
+ crafted(&put_over, |change| {
+ change.operations[0].pred = Vec::new().into()
+ }),
+ // Deleting at a map's key, replacing nothing.
+ crafted(&map_delete, |change| {
+ change.operations[0].pred = Vec::new().into()
+ }),
+ // An insert replacing something.
+ crafted(&insert, |change| {
+ change.operations[0].pred = vec![id(2)].into()
+ }),
+ // A deletion or an increment inserted, in a list or at a map's key.
+ crafted(&delete, |change| change.operations[0].insert = true),
+ crafted(&map_delete, |change| change.operations[0].insert = true),
+ crafted(&increment, |change| change.operations[0].insert = true),
+ // A mark ended ahead of its begin: begun after "b", ended after "a"; begun
+ // after "c", ended after "b"; ended at the text's head; ended after what
+ // its begin is inserted after.
+ crafted(&mark, |change| {
+ change.operations[0].key = at(9);
+ change.operations[1].key = at(7);
+ }),
+ crafted(&sibling, |change| {
+ change.operations[0].key = at(8);
+ change.operations[1].key = at(9);
+ }),
+ crafted(&mark, |change| {
+ change.operations[1].key = Key::Seq(ElementId::Head)
+ }),
+ crafted(&mark, |change| change.operations[1].key = at(7)),
+ // A mark in a list.
+ crafted(&mark, |change| {
+ for op in change.operations.iter_mut() {
+ op.obj = ObjectId::Id(id(1));
+ }
+ change.operations[0].key = at(2);
+ change.operations[1].key = at(3);
+ }),
+ // A mark not inserted; one never ended; one ended where nothing began.
+ crafted(&mark, |change| change.operations[0].insert = false),
+ crafted(&mark, |change| change.operations.truncate(1)),
+ crafted(&insert, |change| {
+ change.operations[0].action = OpType::MarkEnd(false)
+ }),
+ ];
+ for crafted in crafted {
+ let why = Written::default().check(&ours, &crafted, &crafted.decode());
+ assert!(why.is_some(), "{:?}", crafted.decode().operations);
}
}