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 | |
| 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.
| -rw-r--r-- | docs/access.md | 12 | ||||
| -rw-r--r-- | src/document/changes.rs | 429 |
2 files changed, 352 insertions, 89 deletions
diff --git a/docs/access.md b/docs/access.md index 976197e..2b5f54c 100644 --- a/docs/access.md +++ b/docs/access.md @@ -314,10 +314,14 @@ wouldn't have written: bytes that aren't Automerge's encoding of the change; a f operation not numbered one after the highest of its dependencies; a change that isn't its actor's first and doesn't build on the one before; an operation naming one that wasn't made in the change's own history, or that isn't what it is named as (the -object written into, the element of that list, a value replaced at that place); and -anything Automerge's own transactions never write (a deletion replacing nothing, a -value put at a list's head without being inserted, a mark ended but right after its -begin). Automerge applies some of those, and then panics, saves a document that doesn't +object written into, the element of that list, a value replaced at that place); and an +operation other than those Automerge's own transactions write. Those insert a value, an +object or a mark's begin or end into a list or a text, replacing nothing; write at a +list's element, never its head, without inserting, replacing what is at that element +(the element itself, or what was written at it); write at a map's key, never inserting, +a deletion or an increment replacing something; and mark only in a text, the end +inserted right after the begin, at the begin or at an element after the one the begin +follows. Automerge applies some others, and then panics, saves a document that doesn't load, or holds another change than the one it was given. All of it is asked of the change and its history alone, so two nodes that hold a change's history come to the same, whatever else they hold: a change of the same batch refused after it passed 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); } } |
