diff options
| author | tv <tv@krebsco.de> | 2026-11-13 16:42:55 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-13 16:42:55 +0000 |
| commit | 29e70c16546f3f2b0134147a31ec335f82433289 (patch) | |
| tree | da7a92b2df848fcbe5d4741539db68a5677d516d /src/document/changes.rs | |
| parent | 0b04273db4b6b6a17dbc1b78c17c39e2f18dc0ff (diff) | |
changes: no mark
Screening took marks in a text, checking that a mark's end comes at its
begin or after it, by walking the elements each is inserted after back to
the text's head: up to 22 s for one change of 9 KB. And it took a value
put at a mark's begin or end, replacing it: sound until an honest node
edits that text, then the node panics at its next sync or append, and its
save doesn't load.
Continuum's store writes no marks. A change with a mark's begin or end is
now refused, and the walk is gone. An element written at is one a value
or an object was inserted as.
Diffstat (limited to 'src/document/changes.rs')
| -rw-r--r-- | src/document/changes.rs | 311 |
1 files changed, 81 insertions, 230 deletions
diff --git a/src/document/changes.rs b/src/document/changes.rs index 575b83e..cc04c7f 100644 --- a/src/document/changes.rs +++ b/src/document/changes.rs @@ -398,10 +398,9 @@ impl Written { /// marks an unrelated value gone, and the document then gives back another /// change under this one's hash; one naming a deletion or an increment does the /// same, or panics as it is given back.) - /// * 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.) + /// * Every operation is one Automerge's transactions write, but for tables and + /// marks ([`unwritten`] says which). (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`]. @@ -411,7 +410,7 @@ impl Written { change: &Change, expanded: &ExpandedChange, ) -> Option<String> { - use automerge::legacy::{ElementId, Key, ObjectId, OpId, OpType}; + use automerge::legacy::{ElementId, Key, ObjectId, OpId}; self.checked = None; let hash = change.hash(); let again = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| { @@ -488,7 +487,7 @@ impl Written { .find(|made| written.reaches(doc, &mut history, made.change, *counter)) }; // What it is: one of what Automerge's transactions write. - if let Some(why) = unwritten(&expanded.operations, index) { + if let Some(why) = unwritten(op) { return Some(why.to_owned()); } // The object written into: one, of the kind the key is for. @@ -500,15 +499,14 @@ impl Written { automerge::ObjType::Table => false, }; // Whether the object is one the document held at `doc_heads`, for what - // can then be read there, and its kind. + // can then be read there. let held; - let kind = match &op.obj { + 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); @@ -531,32 +529,22 @@ impl Written { }) }); 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" - )); - } + if !held && !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" + )); } } - }; - 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. + // The element of a list: a value or an object 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(id) = element - && !made(self, id).is_some_and(|made| made.insert && made.obj == op.obj) + && !made(self, id) + .is_some_and(|made| made.insert && made.holds && made.obj == op.obj) { let OpId(counter, by) = id; return Some(format!( @@ -591,42 +579,6 @@ 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(( @@ -724,38 +676,31 @@ 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: +/// Why `op` is none Automerge's transactions write, or one continuum doesn't take; 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. +/// * Inserted: a value put or an object made, 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. +/// increment replacing something. /// -/// And no table made: transactions make one but can't write into it, and Automerge -/// panics applying a change that does; continuum's store makes none. -fn unwritten(operations: &[automerge::legacy::Op], index: usize) -> Option<&'static str> { +/// Not taken, though transactions write them: a table, which they make but can't write +/// into (Automerge panics applying a change that does); a mark's begin or end (Automerge +/// takes some, and then breaks: a value written at one, once the text is edited; a mark +/// ended ahead of its begin). Continuum's store writes neither. +fn unwritten(op: &automerge::legacy::Op) -> 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) { (_, _, OpType::Make(automerge::ObjType::Table)) => Some("it makes a table"), + (_, _, OpType::MarkBegin(_) | OpType::MarkEnd(_)) => Some("it marks a text"), (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") } @@ -763,46 +708,10 @@ fn unwritten(operations: &[automerge::legacy::Op], index: usize) -> Option<&'sta (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()?; @@ -1063,7 +972,6 @@ 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::marks::{ExpandMark, Mark}; use automerge::{ObjType, ScalarValue}; let mut doc = Document::new(); let (map, list) = change(&mut doc, |doc| { @@ -1082,8 +990,8 @@ mod tests { 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. + // Counters in a list and a map, an element written over; the text typed in, + // partly deleted. change(&mut doc, |doc| { let counters = doc.put_object(&map, "counters", ObjType::List).unwrap(); doc.insert(&counters, 0, ScalarValue::counter(1)).unwrap(); @@ -1093,44 +1001,11 @@ mod tests { 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.increment(&map, "count", 2).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()); @@ -1409,37 +1284,28 @@ mod tests { } /// 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. + /// and what it replaces at its place. Each crafted change Automerge takes, and then + /// can't give back, panics giving back, or saves a document that doesn't load. #[test] 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::legacy::{ElementId, Key, OpId}; use automerge::{ObjType, ScalarValue}; let mut theirs = Document::new(); - let (list, counters, text) = change(&mut theirs, |doc| { + let (list, counters) = change(&mut theirs, |doc| { doc.put(ROOT, "k", 1).unwrap(); let list = doc.put_object(ROOT, "list", ObjType::List).unwrap(); doc.insert(&list, 0, "a").unwrap(); 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) + (list, counters) }); let first = theirs.get_last_local_change().unwrap(); - assert_eq!(first.decode().operations.len(), 10); + assert_eq!(first.decode().operations.len(), 6); 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"). + // The first change's operations: 1 the list, 2 its "a", 3 its "c" (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([first.clone()]).unwrap(); fn on(doc: &Document, write: impl FnOnce(&mut Transaction<'_>)) -> Change { @@ -1452,37 +1318,7 @@ mod tests { 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, - ] { + for honest in [&put_over, &delete, &increment, &insert, &map_delete] { assert_eq!( Written::default().check(&ours, honest, &honest.decode()), None, @@ -1525,35 +1361,6 @@ mod tests { 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()); @@ -1561,6 +1368,50 @@ mod tests { } } + /// No mark: one a transaction writes, or one ended where nothing began. Automerge + /// takes some marks and then breaks (a value written at a mark's begin or end, once + /// the text is edited; a mark ended ahead of its begin); continuum writes none. + #[test] + fn no_mark() { + use crate::document::Transaction; + use automerge::ObjType; + use automerge::legacy::OpType; + use automerge::marks::{ExpandMark, Mark}; + let mut theirs = Document::new(); + let text = change(&mut theirs, |doc| { + let text = doc.put_object(ROOT, "text", ObjType::Text).unwrap(); + doc.splice_text(&text, 0, 0, "abc").unwrap(); + text + }); + let mut ours = Document::new(); + ours.apply_changes(theirs.get_changes(&[])).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 typed = on(&ours, |doc| doc.splice_text(&text, 3, 0, "d").unwrap()); + assert_eq!( + Written::default().check(&ours, &typed, &typed.decode()), + None + ); + let marked = on(&ours, |doc| { + doc.mark( + &text, + Mark::new("bold".into(), true, 1, 2), + ExpandMark::None, + ) + .unwrap() + }); + let ended = crafted(&typed, |change| { + change.operations[0].action = OpType::MarkEnd(false) + }); + for crafted in [marked, ended] { + let why = Written::default().check(&ours, &crafted, &crafted.decode()); + assert!(why.is_some(), "{:?}", crafted.decode().operations); + } + } + /// No table: made, by itself or with what is written into it, or written into /// where the document holds one. Automerge panics applying a change that writes /// into one; transactions can't, and continuum's store makes none. |
