aboutsummaryrefslogtreecommitdiffstats
path: root/src/document
diff options
context:
space:
mode:
Diffstat (limited to 'src/document')
-rw-r--r--src/document/changes.rs494
1 files changed, 439 insertions, 55 deletions
diff --git a/src/document/changes.rs b/src/document/changes.rs
index 6e3fb51..d4256c3 100644
--- a/src/document/changes.rs
+++ b/src/document/changes.rs
@@ -283,14 +283,81 @@ pub(crate) fn changes_in(mut data: &[u8]) -> Option<Vec<Change>> {
Some(changes)
}
+/// `change`, decoded; without operations where Automerge panics decoding it (an
+/// operation naming an actor its change doesn't list), which [`Written::check`] then
+/// refuses: encoded again, it isn't the change that came.
+pub(crate) fn decode(change: &Change) -> ExpandedChange {
+ std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| change.decode())).unwrap_or_else(
+ |_| ExpandedChange {
+ operations: Vec::new(),
+ actor_id: change.actor_id().clone(),
+ hash: None,
+ seq: change.seq(),
+ start_op: change.start_op(),
+ time: change.timestamp(),
+ message: change.message().map(str::to_owned),
+ author: None,
+ deps: change.deps().to_vec(),
+ extra_bytes: change.extra_bytes().to_vec(),
+ },
+ )
+}
+
+/// What an operation is, as the operations after it may name it.
+#[derive(Clone)]
+struct Made {
+ /// The change it is of.
+ change: ChangeHash,
+ obj: automerge::legacy::ObjectId,
+ key: automerge::legacy::Key,
+ /// It put an element into a list.
+ insert: bool,
+ /// The object it made, if it made one.
+ makes: Option<automerge::ObjType>,
+}
+
+impl Made {
+ fn of(change: ChangeHash, op: &automerge::legacy::Op) -> Self {
+ Made {
+ change,
+ obj: op.obj.clone(),
+ key: op.key.clone(),
+ insert: op.insert,
+ makes: match &op.action {
+ automerge::legacy::OpType::Make(kind) => Some(*kind),
+ _ => None,
+ },
+ }
+ }
+}
+
+/// A change of a batch that passed [`Written::check`].
+struct Passed {
+ deps: Vec<ChangeHash>,
+ actor: ActorId,
+ seq: u64,
+ max_op: u64,
+ /// The changes of the document its history reaches first: its own dependencies
+ /// there, and those of the batch's changes it builds on.
+ doc_heads: Vec<ChangeHash>,
+}
+
+/// The history of a change being checked, walked back from its dependencies as far as
+/// a question needs: newest first, by the operations' counters.
+struct History {
+ queue: std::collections::BinaryHeap<(u64, ChangeHash)>,
+ seen: std::collections::HashSet<ChangeHash>,
+}
+
/// What the changes of a batch made that passed [`Written::check`]: those after them
/// in the batch build on them before the document holds them.
#[derive(Default)]
pub(crate) struct Written {
- /// The highest operation counter of each.
- max_ops: HashMap<ChangeHash, u64>,
- /// The operation counters each made, by its actor: first and last.
- ops: HashMap<ActorId, Vec<(u64, u64)>>,
+ passed: HashMap<ChangeHash, Passed>,
+ /// The operations they made.
+ ops: HashMap<(ActorId, u64), Made>,
+ /// Changes of the document, decoded to see what an operation of theirs is.
+ decoded: HashMap<ChangeHash, Option<ExpandedChange>>,
}
impl Written {
@@ -299,7 +366,11 @@ impl Written {
/// among those. Automerge 0.12 applies changes that aren't, and is broken by them:
/// it then gives back another change than the one it was given and saves a
/// document that doesn't load, or panics. No honest node makes such a change, so
- /// each from elsewhere is looked at first:
+ /// each from elsewhere is looked at first.
+ ///
+ /// Everything asked is asked of the change and its own history, never of what
+ /// else the document holds: two nodes that hold a change's history come to the
+ /// same, whatever reached them besides and in whatever order.
///
/// * Its bytes are the ones Automerge encodes for it. (One listing an actor none
/// of its operations names loads, with another hash than its own encoding has.)
@@ -307,9 +378,14 @@ impl Written {
/// without any: what a transaction at the document's heads gives it. (One
/// numbered below them saves to a document that doesn't load; one numbered
/// near 2^32 makes the next write panic.)
- /// * Every operation it names (an object written into, an element of a list, an
- /// operation replaced) is one of its own, or one made before it, in `doc` or by
- /// a change checked before.
+ /// * It is its actor's first, or builds on the one before it: a transaction names
+ /// its actor's last change among its dependencies. (A gap in an actor's numbers
+ /// makes Automerge panic.)
+ /// * Every operation it names was made in its history, or before in the change
+ /// itself, and is what it is named as: the object written into an object of
+ /// 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.)
pub(crate) fn check(
&mut self,
doc: &Document,
@@ -318,76 +394,234 @@ impl Written {
) -> Option<String> {
use automerge::legacy::{ElementId, Key, ObjectId, OpId};
let hash = change.hash();
- if Change::from(expanded.clone()).hash() != hash {
+ let again = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
+ Change::from(expanded.clone()).hash()
+ }));
+ if again.ok() != Some(hash) {
return Some("its bytes aren't the ones Automerge encodes for it".to_owned());
}
let start = change.start_op().get();
let last = change.max_op();
- let before: Option<u64> = change
- .deps()
- .iter()
- .map(|dep| {
- self.max_ops
- .get(dep)
- .copied()
- .or_else(|| doc.get_change_meta_by_hash(dep).map(|meta| meta.max_op))
- })
- .try_fold(0, |highest, max_op| {
- max_op.map(|max_op| highest.max(max_op))
- });
- // A dependency neither here nor there: not ready, and Automerge doesn't apply
- // it (callers judge those whose dependencies they hold).
- if let Some(before) = before
- && start != before + 1
- {
+ let actor = change.actor_id();
+
+ // Its dependencies: those of the batch, and those the document holds. One
+ // that is neither isn't ready, and Automerge doesn't apply the change (callers
+ // judge those whose dependencies they hold): nothing is asked of it.
+ let mut before = 0;
+ let mut follows = change.seq() == 1;
+ let mut doc_heads: Vec<ChangeHash> = Vec::new();
+ for dep in change.deps() {
+ let (dep_actor, seq, max_op) = if let Some(passed) = self.passed.get(dep) {
+ doc_heads.extend(&passed.doc_heads);
+ (passed.actor.clone(), passed.seq, passed.max_op)
+ } else {
+ let meta = doc.get_change_meta_by_hash(dep)?;
+ doc_heads.push(*dep);
+ (meta.actor.into_owned(), meta.seq, meta.max_op)
+ };
+ before = before.max(max_op);
+ follows |= &dep_actor == actor && seq + 1 == change.seq();
+ }
+ doc_heads.sort_unstable();
+ doc_heads.dedup();
+ if start != before + 1 {
return Some(format!(
"its first operation is numbered {start}, not {}, one after the highest of its dependencies",
before + 1
));
}
- let actor = change.actor_id();
- let made = |OpId(counter, by): &OpId| {
- if by == actor && (start..=last).contains(counter) {
- return true;
- }
- *counter < start
- && (self.ops.get(by).is_some_and(|ranges| {
- ranges
- .iter()
- .any(|(first, last)| (*first..=*last).contains(counter))
- }) || doc
- .hash_for_opid(&automerge::ObjId::Id(*counter, by.clone(), 0))
- .is_some())
+ if !follows {
+ return Some(format!(
+ "it is its actor's change {}, and doesn't build on the one before",
+ change.seq()
+ ));
+ }
+
+ let mut history = History {
+ queue: Default::default(),
+ seen: change.deps().iter().copied().collect(),
};
- for op in &expanded.operations {
- let object = match &op.obj {
- ObjectId::Id(id) => Some(id),
- ObjectId::Root => None,
+ for dep in change.deps() {
+ if let Some(max_op) = self.max_op(doc, dep) {
+ history.queue.push((max_op, *dep));
+ }
+ }
+ let exid = |OpId(counter, by): &OpId| automerge::ObjId::Id(*counter, by.clone(), 0);
+ for (index, op) in expanded.operations.iter().enumerate() {
+ let this = start + index as u64;
+ // What `id` is, if it was made before this operation: in the change
+ // itself, or in its history.
+ let mut made = |written: &mut Self, id: &OpId| -> Option<Made> {
+ let OpId(counter, by) = id;
+ if by == actor && (start..this).contains(counter) {
+ let op = &expanded.operations[(counter - start) as usize];
+ return Some(Made::of(hash, op));
+ }
+ if *counter >= start {
+ return None;
+ }
+ let made = written.made(doc, id)?;
+ written
+ .reaches(doc, &mut history, made.change, *counter)
+ .then_some(made)
+ };
+ // The object written into: one, of the kind the key is for.
+ let in_list = matches!(op.key, Key::Seq(_));
+ let fits = |kind: automerge::ObjType| {
+ 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 {
+ ObjectId::Root => {
+ if in_list {
+ return Some("it writes a list's element into the root".to_owned());
+ }
+ held = true;
+ }
+ 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)
+ .ok()
+ .and_then(|mut parents| parents.next())
+ .is_some_and(|parent| match parent.prop {
+ automerge::Prop::Map(key) => doc
+ .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"
+ ));
+ }
+ }
+ }
+ // The element of a list: one 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(OpId(counter, by)) = object
- .into_iter()
- .chain(element)
- .chain(op.pred.iter())
- .find(|id| !made(id))
+ if let Some(id) = element
+ && !made(self, id).is_some_and(|made| made.insert && made.obj == op.obj)
{
+ let OpId(counter, by) = id;
return Some(format!(
- "it names an operation nobody made before it ({counter}@{by})"
+ "it names {counter}@{by}, no element of that list put there before it"
));
}
+ // What it replaces: operations at its place.
+ let there: Vec<automerge::ObjId> = match (&op.key, held, op.pred.is_empty()) {
+ // Those the document holds there, at the changes this one builds on:
+ // in its history, with nothing walked.
+ (Key::Map(key), true, false) if !doc_heads.is_empty() => {
+ let object = match &op.obj {
+ ObjectId::Root => automerge::ROOT,
+ ObjectId::Id(id) => exid(id),
+ };
+ doc.get_all_at(&object, key.as_str(), &doc_heads)
+ .map(|held| held.into_iter().map(|(_, id)| id).collect())
+ .unwrap_or_default()
+ }
+ _ => Vec::new(),
+ };
+ 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);
+ if !at_its_place {
+ let OpId(counter, by) = id;
+ return Some(format!(
+ "it replaces {counter}@{by}, no operation at that place made before it"
+ ));
+ }
+ }
}
- self.max_ops.insert(hash, last);
- if last >= start {
+
+ for (index, op) in expanded.operations.iter().enumerate() {
self.ops
- .entry(actor.clone())
- .or_default()
- .push((start, last));
+ .insert((actor.clone(), start + index as u64), Made::of(hash, op));
}
+ self.passed.insert(
+ hash,
+ Passed {
+ deps: change.deps().to_vec(),
+ actor: actor.clone(),
+ seq: change.seq(),
+ max_op: last,
+ doc_heads,
+ },
+ );
None
}
+
+ /// The highest operation counter of a change of the batch or the document.
+ fn max_op(&self, doc: &Document, hash: &ChangeHash) -> Option<u64> {
+ self.passed
+ .get(hash)
+ .map(|passed| passed.max_op)
+ .or_else(|| doc.get_change_meta_by_hash(hash).map(|meta| meta.max_op))
+ }
+
+ /// What the operation `id` is, made by a change of the batch or the document.
+ fn made(&mut self, doc: &Document, id: &automerge::legacy::OpId) -> Option<Made> {
+ let automerge::legacy::OpId(counter, by) = id;
+ if let Some(made) = self.ops.get(&(by.clone(), *counter)) {
+ return Some(made.clone());
+ }
+ let hash = doc.hash_for_opid(&automerge::ObjId::Id(*counter, by.clone(), 0))?;
+ let change = self
+ .decoded
+ .entry(hash)
+ .or_insert_with(|| doc.get_change_by_hash(&hash).map(|change| change.decode()))
+ .as_ref()?;
+ let index = counter.checked_sub(change.start_op.get())?;
+ let op = change.operations.get(usize::try_from(index).ok()?)?;
+ Some(Made::of(hash, op))
+ }
+
+ /// Whether `target`, a change with an operation numbered `counter`, is in the
+ /// history `history` walks. A change's operations are numbered above those of
+ /// all it builds on, so the walk goes no further back than `counter`.
+ fn reaches(
+ &self,
+ doc: &Document,
+ history: &mut History,
+ target: ChangeHash,
+ counter: u64,
+ ) -> bool {
+ while let Some((max_op, _)) = history.queue.peek()
+ && *max_op >= counter
+ && !history.seen.contains(&target)
+ {
+ let (_, hash) = history.queue.pop().expect("peeked");
+ let deps = match self.passed.get(&hash) {
+ Some(passed) => passed.deps.clone(),
+ None => doc
+ .get_change_meta_by_hash(&hash)
+ .map(|meta| meta.deps)
+ .unwrap_or_default(),
+ };
+ for dep in deps {
+ if history.seen.insert(dep)
+ && let Some(max_op) = self.max_op(doc, &dep)
+ {
+ history.queue.push((max_op, dep));
+ }
+ }
+ }
+ history.seen.contains(&target)
+ }
}
/// `change`, if it names an author but isn't its actor's first (`misplaced_author`).
@@ -788,7 +1022,157 @@ mod tests {
let why = Written::default()
.check(&ours, &crafted, &crafted.decode())
.expect("refused");
- assert!(why.contains("nobody made"), "{object:?}: {why}");
+ assert!(why.contains("no object"), "{object:?}: {why}");
}
}
+
+ /// `honest` with `edit` made to it, as a change of its own.
+ fn crafted(honest: &Change, edit: impl FnOnce(&mut ExpandedChange)) -> Change {
+ let mut expanded = honest.decode();
+ edit(&mut expanded);
+ expanded.hash = None;
+ Change::from(expanded)
+ }
+
+ /// An operation named as replaced that is elsewhere, or that put no object where
+ /// one is written into: refused, though it was made before.
+ #[test]
+ fn operations_named_at_the_wrong_place_are_refused() {
+ use automerge::legacy::{ObjectId, OpId};
+ let mut theirs = Document::new();
+ change(&mut theirs, |doc| doc.put(ROOT, "a", 1).unwrap());
+ change(&mut theirs, |doc| doc.put(ROOT, "b", 2).unwrap());
+ let mut ours = Document::new();
+ ours.apply_changes(theirs.get_changes(&[])).unwrap();
+ let actor = theirs.get_actor().clone();
+ change(&mut theirs, |doc| doc.put(ROOT, "b", 3).unwrap());
+ let honest = theirs.get_last_local_change().unwrap();
+ assert_eq!(
+ Written::default().check(&ours, &honest, &honest.decode()),
+ None
+ );
+ // It replaces what wrote `a`.
+ let elsewhere = crafted(&honest, |change| {
+ change.operations[0].pred = vec![OpId(1, actor.clone())].into();
+ });
+ let why = Written::default()
+ .check(&ours, &elsewhere, &elsewhere.decode())
+ .expect("refused");
+ assert!(why.contains("at that place"), "{why}");
+ // It writes into what put a number.
+ let no_object = crafted(&honest, |change| {
+ change.operations[0].obj = ObjectId::Id(OpId(1, actor.clone()));
+ change.operations[0].pred = Vec::new().into();
+ });
+ let why = Written::default()
+ .check(&ours, &no_object, &no_object.decode())
+ .expect("refused");
+ assert!(why.contains("no object"), "{why}");
+ }
+
+ /// An operation named that the document holds, made by a change this one doesn't
+ /// build on: refused, as by a node that doesn't hold it yet.
+ #[test]
+ fn operations_outside_a_changes_history_are_refused() {
+ use automerge::legacy::OpId;
+ let mut theirs = Document::new();
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap());
+ let mut other = theirs.fork();
+ change(&mut other, |doc| doc.put(ROOT, "k", 2).unwrap());
+ let aside = other.get_last_local_change().unwrap();
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 3).unwrap());
+ let honest = theirs.get_last_local_change().unwrap();
+ // It also replaces what the other wrote, which it never saw.
+ let reaching = crafted(&honest, |change| {
+ let mut pred: Vec<OpId> = change.operations[0].pred.iter().cloned().collect();
+ pred.push(OpId(aside.start_op().get(), aside.actor_id().clone()));
+ change.operations[0].pred = pred.into();
+ });
+ // Whether we hold the other's change or not.
+ let mut without = Document::new();
+ without
+ .apply_changes(theirs.get_changes(&[]).into_iter().take(1))
+ .unwrap();
+ let mut with = without.clone();
+ with.apply_changes([aside.clone()]).unwrap();
+ for ours in [&without, &with] {
+ assert_eq!(
+ Written::default().check(ours, &honest, &honest.decode()),
+ None
+ );
+ let why = Written::default()
+ .check(ours, &reaching, &reaching.decode())
+ .expect("refused");
+ assert!(why.contains("at that place"), "{why}");
+ }
+ }
+
+ /// A change that isn't its actor's first and doesn't build on the one before it:
+ /// refused.
+ #[test]
+ fn a_gap_in_an_actors_changes_is_refused() {
+ let mut theirs = Document::new();
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap());
+ let mut ours = Document::new();
+ ours.apply_changes(theirs.get_changes(&[])).unwrap();
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 2).unwrap());
+ let honest = theirs.get_last_local_change().unwrap();
+ assert_eq!(honest.seq(), 2);
+ assert_eq!(
+ Written::default().check(&ours, &honest, &honest.decode()),
+ None
+ );
+ for seq in [3, 7] {
+ let gap = crafted(&honest, |change| change.seq = seq);
+ let why = Written::default()
+ .check(&ours, &gap, &gap.decode())
+ .expect("refused");
+ assert!(why.contains("the one before"), "{seq}: {why}");
+ }
+ // A first change of another actor numbered 2.
+ let mut stranger = ours.fork().with_actor(ActorId::from([0xcd; 16]));
+ change(&mut stranger, |doc| doc.put(ROOT, "k", 9).unwrap());
+ let first = stranger.get_last_local_change().unwrap();
+ let second = crafted(&first, |change| change.seq = 2);
+ assert!(
+ Written::default()
+ .check(&ours, &second, &second.decode())
+ .is_some()
+ );
+ }
+
+ /// Changes of one batch building on each other pass, each checked against those
+ /// before it; one naming what a change of the batch wrote elsewhere doesn't.
+ #[test]
+ fn a_batch_is_checked_against_itself() {
+ use automerge::legacy::OpId;
+ let theirs = written();
+ let changes = theirs.get_changes(&[]);
+ let half = changes.len() / 2;
+ let mut ours = Document::new();
+ ours.apply_changes(changes[..half].iter().cloned()).unwrap();
+ let mut written = Written::default();
+ for change in &changes[half..] {
+ assert_eq!(written.check(&ours, change, &change.decode()), None);
+ }
+ // The last put `k` in the map: have it replace what made the map.
+ let last = changes.last().unwrap();
+ let first = &changes[0];
+ let elsewhere = crafted(last, |change| {
+ change.operations[0].pred =
+ vec![OpId(first.start_op().get(), first.actor_id().clone())].into();
+ });
+ let mut written = Written::default();
+ for change in &changes[..changes.len() - 1] {
+ assert_eq!(
+ written.check(&Document::new(), change, &change.decode()),
+ None
+ );
+ }
+ assert!(
+ written
+ .check(&Document::new(), &elsewhere, &elsewhere.decode())
+ .is_some()
+ );
+ }
}