diff options
| author | tv <tv@krebsco.de> | 2026-11-13 04:49:38 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-13 04:49:38 +0000 |
| commit | 369cfb6a110ed384f18792ccd13a50f7cf27559a (patch) | |
| tree | 3b792e3cbd40967cdf2ed011196d44ee6d16af05 /src/document/changes.rs | |
| parent | 519e0a1019b9f74ce8a12773a47d613a05aecdf8 (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.rs | 429 |
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); } } |
