aboutsummaryrefslogtreecommitdiffstats
path: root/src/document/changes.rs
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-13 16:42:55 +0000
committertv <tv@krebsco.de>2026-11-13 16:42:55 +0000
commit29e70c16546f3f2b0134147a31ec335f82433289 (patch)
treeda7a92b2df848fcbe5d4741539db68a5677d516d /src/document/changes.rs
parent0b04273db4b6b6a17dbc1b78c17c39e2f18dc0ff (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.rs311
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.