Repository: automerge/automerge (language: rust)

Issue:
Error inflating document chunk ops: an operation referenced a missing actor id
Hello!

I've run across an issue where automerge 0.5.9 generates invalid saves that give `error inflating document chunk ops: an operation referenced a missing actor id` when attempting to load them. I've managed to reproduce this in a minimized test case:

```rust
use anyhow::Result;
use automerge::{ActorId, AutoCommit, ReadDoc, ROOT};
use automerge::transaction::Transactable;

// error inflating document chunk ops: an operation referenced a missing actor id
fn main() -> Result<()> {
    let actor0 = ActorId::from(&[0]);
    let actor1 = ActorId::from(&[1]);
    let actor2 = ActorId::from(&[2]);

    let mut doc0 = AutoCommit::new().with_actor(actor0);
    doc0.put(ROOT, "a", 1)?;

    // swap these actors and no error occurs
    let mut doc1 = doc0.fork().with_actor(actor2);
    let mut doc2 = doc0.fork().with_actor(actor1);

    doc1.put(ROOT, "b", 2)?;
    doc2.merge(&mut doc1)?;
    doc2.delete(ROOT, "c")?;

    // error occurs here
    doc2.save_and_verify()?;

    println!("{:?}", doc2.get(ROOT, "a"));
    println!("{:?}", doc2.get(ROOT, "b"));
    println!("{:?}", doc2.get(ROOT, "c"));

    Ok(())
}
```

Interestingly it seems to depend on the ordering of ActorIDs as if you swap `actor1` and `actor2` the error doesn't occur. With random ActorIDs the problem is not 100% reproducible.

It also seems to be related to the `doc2.delete(ROOT, "c")` operation which has no effect since the key `"c"` isn't set in the document.

Anyhow, is this a bug or am I misusing the API somehow? The behavior doesn't seem to be present in 0.5.6. Thank you! 


Discussion / hints:
This is definitely a bug, I'll take a look
We hit this bug fairly consistently today. I think we have the document in question, and it was a development document so no sensitive data is in it. 

Fix patch:
diff --git a/rust/Cargo.toml b/rust/Cargo.toml
index 5d29fc9f35..75cb5955a0 100644
--- a/rust/Cargo.toml
+++ b/rust/Cargo.toml
@@ -14,4 +14,4 @@ lto = true
 codegen-units = 1
 
 [profile.bench]
-debug = true
\ No newline at end of file
+debug = true
diff --git a/rust/automerge-cli/Cargo.toml b/rust/automerge-cli/Cargo.toml
index d4a36c803a..cc763e5b8a 100644
--- a/rust/automerge-cli/Cargo.toml
+++ b/rust/automerge-cli/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.1.0"
 authors = ["Alex Good <alex@memoryandthought.me>"]
 edition = "2018"
 license = "MIT"
-rust-version = "1.57.0"
+rust-version = "1.70"
 
 [[bin]]
 name = "automerge"
diff --git a/rust/automerge/Cargo.toml b/rust/automerge/Cargo.toml
index 3d4b89f4f3..b0902968a0 100644
--- a/rust/automerge/Cargo.toml
+++ b/rust/automerge/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.5.10"
 edition = "2021"
 license = "MIT"
 repository = "https://github.com/automerge/automerge"
-rust-version = "1.57.0"
+rust-version = "1.70.0"
 description = "A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically"
 readme = "./README.md"
 
diff --git a/rust/automerge/src/hydrate/text.rs b/rust/automerge/src/hydrate/text.rs
index 59430323fd..7075c8d50d 100644
--- a/rust/automerge/src/hydrate/text.rs
+++ b/rust/automerge/src/hydrate/text.rs
@@ -1,4 +1,4 @@
-use std::collections::HashMap;
+use std::{collections::HashMap, fmt::Display};
 
 use crate::{text_value::TextValue, PatchAction, ScalarValue};
 
@@ -59,9 +59,9 @@ impl From<&Text> for String {
     }
 }
 
-impl ToString for Text {
-    fn to_string(&self) -> String {
-        self.value.make_string()
+impl Display for Text {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        write!(f, "{}", self.value.make_string())
     }
 }
 
diff --git a/rust/automerge/src/indexed_cache.rs b/rust/automerge/src/indexed_cache.rs
index 27371903e1..b61525e9c9 100644
--- a/rust/automerge/src/indexed_cache.rs
+++ b/rust/automerge/src/indexed_cache.rs
@@ -67,33 +67,6 @@ where
         });
         sorted
     }
-
-    /// Create a vector from positions in this index to positions in an equivalent sorted index
-    ///
-    /// This is useful primarily when encoding an `IndexedCache<ActorId>` in the document format.
-    /// In this case we encode the actors in sorted order in the document and all ops reference the
-    /// offset into this sorted actor array. But the `IndexedCache<ActorId>` we have in the
-    /// application does not contain actors in sorted order because we add them as we encounter
-    /// them, so we must map from the actor IDs in the application to the actor IDs in the document
-    /// format
-    ///
-    /// # Examples
-    ///
-    /// ```rust,ignore
-    /// let idx: IndexedCache<String> = IndexedCache::new();
-    /// let first_idx = idx.cache("b"); // first_idx is `0`
-    /// let second_idx = idx.cache("a"); // second_idx i `1`
-    /// let encoded = idx.encode_index();
-    /// // first_idx (0) maps to `1` whilst second_idx (1) maps to `0` because "a" < "b"
-    /// assert_eq!(encoded, vec![1,0])
-    /// ```
-    pub(crate) fn encode_index(&self) -> Vec<usize> {
-        let sorted: Vec<_> = self.cache.iter().sorted().cloned().collect();
-        self.cache
-            .iter()
-            .map(|a| sorted.iter().position(|r| r == a).unwrap())
-            .collect()
-    }
 }
 
 impl<T> IntoIterator for IndexedCache<T> {
diff --git a/rust/automerge/src/iter/top_ops.rs b/rust/automerge/src/iter/top_ops.rs
index d9571ff6c7..8a2045ecce 100644
--- a/rust/automerge/src/iter/top_ops.rs
+++ b/rust/automerge/src/iter/top_ops.rs
@@ -3,18 +3,13 @@ use crate::op_set::{Op, OpIter};
 use crate::types::{Clock, Key};
 use std::sync::Arc;
 
-#[derive(Clone)]
+#[derive(Default, Clone)]
 pub(crate) enum TopOps<'a> {
+    #[default]
     Empty,
     Ops(TopOpsInner<'a>),
 }
 
-impl<'a> Default for TopOps<'a> {
-    fn default() -> Self {
-        TopOps::Empty
-    }
-}
-
 impl<'a> TopOps<'a> {
     pub(crate) fn new(iter: OpIter<'a>, clock: Option<Clock>) -> Self {
         TopOps::Ops(TopOpsInner::new(iter, clock))
diff --git a/rust/automerge/src/op_tree.rs b/rust/automerge/src/op_tree.rs
index 96046c4b9b..b192afa3d8 100644
--- a/rust/automerge/src/op_tree.rs
+++ b/rust/automerge/src/op_tree.rs
@@ -546,7 +546,7 @@ impl OpTreeInternal {
                 let old_root = mem::replace(root, new_root);
 
                 root.length += old_root.len();
-                root.index = old_root.index.clone();
+                root.index.clone_from(&old_root.index);
                 root.children.push(old_root);
                 root.split_child(0, osd);
 
diff --git a/rust/automerge/src/patches.rs b/rust/automerge/src/patches.rs
index e9348c73ad..6c3fa1f735 100644
--- a/rust/automerge/src/patches.rs
+++ b/rust/automerge/src/patches.rs
@@ -7,9 +7,10 @@ pub use patch_log::PatchLog;
 
 use crate::{types::ListEncoding, ObjType};
 
-#[derive(Debug, Copy, Clone, PartialEq)]
+#[derive(Default, Debug, Copy, Clone, PartialEq)]
 pub enum TextRepresentation {
     Array,
+    #[default]
     String,
 }
 
@@ -29,9 +30,3 @@ impl TextRepresentation {
         matches!(self, TextRepresentation::String)
     }
 }
-
-impl std::default::Default for TextRepresentation {
-    fn default() -> Self {
-        TextRepresentation::String
-    }
-}
diff --git a/rust/automerge/src/query.rs b/rust/automerge/src/query.rs
index f384dd24f9..ad6e24fa83 100644
--- a/rust/automerge/src/query.rs
+++ b/rust/automerge/src/query.rs
@@ -1,7 +1,7 @@
 use crate::marks::MarkData;
 use crate::op_set::Op;
 use crate::op_tree::{OpSetData, OpTree, OpTreeNode};
-use crate::types::{Key, ListEncoding, OpBuilder, OpId, OpType};
+use crate::types::{Key, ListEncoding, OpId, OpType};
 use fxhash::FxBuildHasher;
 use std::collections::{HashMap, HashSet};
 use std::fmt::Debug;
@@ -26,19 +26,7 @@ pub(crate) struct ChangeVisibility<'a> {
     pub(crate) op: Op<'a>,
 }
 
-#[derive(Debug, Clone, PartialEq)]
-pub(crate) struct CounterData {
-    pos: usize,
-    val: i64,
-    succ: HashSet<OpId>,
-    op: OpBuilder,
-}
-
 pub(crate) trait TreeQuery<'a>: Clone + Debug {
-    fn equiv(&mut self, _other: &Self) -> bool {
-        false
-    }
-
     fn can_shortcut_search(&mut self, _tree: &'a OpTree, _osd: &'a OpSetData) -> bool {
         false
     }
diff --git a/rust/automerge/src/query/insert.rs b/rust/automerge/src/query/insert.rs
index 7b58b21e26..90fcb48725 100644
--- a/rust/automerge/src/query/insert.rs
+++ b/rust/automerge/src/query/insert.rs
@@ -148,10 +148,6 @@ impl<'a> InsertNth<'a> {
 }
 
 impl<'a> TreeQuery<'a> for InsertNth<'a> {
-    fn equiv(&mut self, other: &Self) -> bool {
-        self.pos() == other.pos() && self.key() == other.key()
-    }
-
     fn can_shortcut_search(&mut self, tree: &'a OpTree, _osd: &'a OpSetData) -> bool {
         if let Some(last) = &tree.last_insert {
             if last.index + last.width == self.list_state.target() {
diff --git a/rust/automerge/src/storage/change/change_actors.rs b/rust/automerge/src/storage/change/change_actors.rs
index 6835e5a986..785d54cda1 100644
--- a/rust/automerge/src/storage/change/change_actors.rs
+++ b/rust/automerge/src/storage/change/change_actors.rs
@@ -43,10 +43,6 @@ pub(crate) struct ChangeActors<'a, ActorId, I, O, C> {
     _phantom: std::marker::PhantomData<(&'a O, C)>,
 }
 
-#[derive(thiserror::Error, Debug)]
-#[error("actor index {0} referenced by an operation was not found in the changes")]
-pub(crate) struct MissingActor(usize);
-
 #[derive(Debug, thiserror::Error)]
 #[error("pred OpIds out of order")]
 pub(crate) struct PredOutOfOrder;
diff --git a/rust/automerge/src/storage/convert/op_as_docop.rs b/rust/automerge/src/storage/convert/op_as_docop.rs
index 7c12b131da..f20bf70611 100644
--- a/rust/automerge/src/storage/convert/op_as_docop.rs
+++ b/rust/automerge/src/storage/convert/op_as_docop.rs
@@ -1,4 +1,4 @@
-use std::borrow::Cow;
+use std::{borrow::Cow, collections::HashMap};
 
 use crate::{
     convert,
@@ -10,8 +10,9 @@ use crate::{
 /// Create an [`AsDocOp`] implementation for a [`crate::types::Op`]
 ///
 /// # Arguments
-/// * actors - A vector where the i'th element is the actor index of the document encoding of actor
-///            i, as returned by [`OpSetMetadata.actors.encode_index`]
+/// * actors - A hashmap where the key is the actor index in the automerge::Automerge
+///            we are saving and the value is the index of that same actor in the
+///            order the actors will be encoded in the saved document
 /// * props - An indexed cache containing the properties in this op_as_docop
 /// * obj - The object ID this op refers too
 /// * op - The op itself
@@ -21,7 +22,7 @@ use crate::{
 /// The methods of the resulting `AsDocOp` implementation will panic if any actor ID in the op
 /// references an index not in `actors` or a property not in `props`
 pub(crate) fn op_as_docop<'a>(
-    actors: &'a [usize],
+    actors: &'a HashMap<usize, usize>,
     props: &'a IndexedCache<String>,
     op: Op<'a>,
 ) -> OpAsDocOp<'a> {
@@ -34,7 +35,7 @@ pub(crate) fn op_as_docop<'a>(
 
 pub(crate) struct OpAsDocOp<'a> {
     op: Op<'a>,
-    actor_lookup: &'a [usize],
+    actor_lookup: &'a HashMap<usize, usize>,
     props: &'a IndexedCache<String>,
 }
 
@@ -128,7 +129,7 @@ impl<'a> AsDocOp<'a> for OpAsDocOp<'a> {
 pub(crate) struct OpAsDocOpSuccIter<'a> {
     op: Op<'a>,
     offset: usize,
-    actor_index: &'a [usize],
+    actor_index: &'a HashMap<usize, usize>,
 }
 
 impl<'a> Iterator for OpAsDocOpSuccIter<'a> {
@@ -151,8 +152,8 @@ impl<'a> ExactSizeIterator for OpAsDocOpSuccIter<'a> {
     }
 }
 
-fn translate<'a>(actor_lookup: &'a [usize], op: &'a OpId) -> DocOpId {
-    let index = actor_lookup[op.actor()];
+fn translate<'a>(actor_lookup: &'a HashMap<usize, usize>, op: &'a OpId) -> DocOpId {
+    let index = actor_lookup[&op.actor()];
     DocOpId {
         actor: index,
         counter: op.counter(),
diff --git a/rust/automerge/src/storage/save/document.rs b/rust/automerge/src/storage/save/document.rs
index 397018113d..b0d94cdc3e 100644
--- a/rust/automerge/src/storage/save/document.rs
+++ b/rust/automerge/src/storage/save/document.rs
@@ -31,13 +31,17 @@ where
     I: Iterator<Item = &'a Change> + Clone + 'a,
     O: Iterator<Item = (&'a ObjId, Op<'a>)> + Clone + ExactSizeIterator,
 {
-    let actor_ids = changes
+    let mut actor_lookup = HashMap::with_capacity(actors.len());
+    let mut actor_ids = changes
         .clone()
         .map(|c| c.actor_id().clone())
         .unique()
         .collect::<Vec<_>>();
+    actor_ids.sort();
+    for (index, actor_id) in actor_ids.iter().enumerate() {
+        actor_lookup.insert(actors.lookup(actor_id).unwrap(), index);
+    }
 
-    let actor_lookup = actors.encode_index();
     let doc_ops = ops
         .clone()
         .map(|(_obj, op)| op_as_docop(&actor_lookup, props, op));
@@ -91,7 +95,7 @@ impl HashGraph {
 struct ChangeWithGraph<'a> {
     change: &'a Change,
     graph: &'a HashGraph,
-    actor_lookup: &'a [usize],
+    actor_lookup: &'a HashMap<usize, usize>,
     actors: &'a IndexedCache<ActorId>,
 }
 
@@ -99,7 +103,7 @@ impl<'a> AsChangeMeta<'a> for ChangeWithGraph<'a> {
     type DepsIter = ChangeDepsIter<'a>;
 
     fn actor(&self) -> u64 {
-        self.actor_lookup[self.actors.lookup(self.change.actor_id()).unwrap()] as u64
+        self.actor_lookup[&self.actors.lookup(self.change.actor_id()).unwrap()] as u64
     }
 
     fn seq(&self) -> u64 {
diff --git a/rust/automerge/src/sync.rs b/rust/automerge/src/sync.rs
index b1b0ccd458..0f55d5d631 100644
--- a/rust/automerge/src/sync.rs
+++ b/rust/automerge/src/sync.rs
@@ -273,7 +273,7 @@ impl SyncDoc for Automerge {
         };
 
         sync_state.have_responded = true;
-        sync_state.last_sent_heads = our_heads.clone();
+        sync_state.last_sent_heads.clone_from(&our_heads);
         sync_state.sent_hashes.extend(sent_hashes);
 
         let sync_message = message_builder
@@ -425,7 +425,7 @@ impl Automerge {
         self.filter_changes(&message_heads, &mut sync_state.sent_hashes)?;
 
         if changes_is_empty && message_heads == before_heads {
-            sync_state.last_sent_heads = message_heads.clone();
+            sync_state.last_sent_heads.clone_from(&message_heads);
         }
 
         let known_heads = message_heads
@@ -433,7 +433,7 @@ impl Automerge {
             .filter(|head| self.get_change_by_hash(head).is_some())
             .collect::<Vec<_>>();
         if known_heads.len() == message_heads.len() {
-            sync_state.shared_heads = message_heads.clone();
+            sync_state.shared_heads.clone_from(&message_heads);
             // If the remote peer has lost all its data, reset our state to perform a full resync
             if message_heads.is_empty() {
                 sync_state.last_sent_heads = Default::default();
diff --git a/rust/automerge/src/text_diff/utils.rs b/rust/automerge/src/text_diff/utils.rs
index 3444244a0e..7157cd3b90 100644
--- a/rust/automerge/src/text_diff/utils.rs
+++ b/rust/automerge/src/text_diff/utils.rs
@@ -63,6 +63,7 @@ where
         .count()
 }
 
+#[allow(dead_code)]
 struct OffsetLookup<Int> {
     offset: usize,
     vec: Vec<Int>,
diff --git a/rust/automerge/src/types.rs b/rust/automerge/src/types.rs
index 943c190562..7af576441a 100644
--- a/rust/automerge/src/types.rs
+++ b/rust/automerge/src/types.rs
@@ -593,18 +593,13 @@ impl ObjMeta {
     }
 }
 
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+#[derive(Default, Debug, Copy, Clone, PartialEq, Eq)]
 pub(crate) enum ListEncoding {
+    #[default]
     List,
     Text,
 }
 
-impl Default for ListEncoding {
-    fn default() -> Self {
-        ListEncoding::List
-    }
-}
-
 impl From<Option<ObjType>> for ListEncoding {
     fn from(obj: Option<ObjType>) -> Self {
         if obj == Some(ObjType::Text) {
@@ -628,9 +623,6 @@ impl ElemId {
     }
 }
 
-#[derive(Debug, Clone)]
-pub(crate) struct Peer {}
-
 /// The number of bytes in a change hash.
 pub(crate) const HASH_SIZE: usize = 32; // 256 bits = 32 bytes
 


Test patch:
diff --git a/rust/automerge/src/sync/v1_compat_test/mod.rs b/rust/automerge/src/sync/v1_compat_test/mod.rs
index 2a8c5b58d4..aad0cab278 100644
--- a/rust/automerge/src/sync/v1_compat_test/mod.rs
+++ b/rust/automerge/src/sync/v1_compat_test/mod.rs
@@ -100,7 +100,7 @@ impl Automerge {
         }
 
         sync_state.have_responded = true;
-        sync_state.last_sent_heads = our_heads.clone();
+        sync_state.last_sent_heads.clone_from(&our_heads);
         sync_state
             .sent_hashes
             .extend(changes_to_send.iter().map(|c| c.hash()));
@@ -235,7 +235,7 @@ impl Automerge {
         self.filter_changes(&message_heads, &mut sync_state.sent_hashes)?;
 
         if changes_is_empty && message_heads == before_heads {
-            sync_state.last_sent_heads = message_heads.clone();
+            sync_state.last_sent_heads.clone_from(&message_heads);
         }
 
         let known_heads = message_heads
@@ -243,7 +243,7 @@ impl Automerge {
             .filter(|head| self.get_change_by_hash(head).is_some())
             .collect::<Vec<_>>();
         if known_heads.len() == message_heads.len() {
-            sync_state.shared_heads = message_heads.clone();
+            sync_state.shared_heads.clone_from(&message_heads);
             // If the remote peer has lost all its data, reset our state to perform a full resync
             if message_heads.is_empty() {
                 sync_state.last_sent_heads = Default::default();
diff --git a/rust/automerge/tests/test.rs b/rust/automerge/tests/test.rs
index add7c478a2..393d402cf2 100644
--- a/rust/automerge/tests/test.rs
+++ b/rust/automerge/tests/test.rs
@@ -2164,3 +2164,55 @@ fn diff_should_reverse_deletion_of_block_in_text_correctly() {
     };
     assert_eq!(s.as_ref(), &ScalarValue::Str("value".into()));
 }
+
+#[test]
+fn missing_actors_when_docs_are_forked() {
+    // Reproduces https://github.com/automerge/automerge/issues/897
+    //
+    // The problem was a result of these things interacting:
+    //
+    // 1. When we create a transaction we add the actor ID of the document
+    //    creating the transaction to the IndexedCache of actor IDs that
+    //    document stores
+    // 2. When we fork a document we copy the IndexedCache from the source
+    //    document to the forked document
+    // 3. When we save a document we must encode all the actor IDs in the saved
+    //    document in lexicographic order. To do this we first enumerate all
+    //    the actor IDs in the change graph and then encode this in the
+    //    document
+    // 4. We assume that the IndexedCache of actor IDs on the document only
+    //    contains actor IDs which are in the change graph
+    //
+    // What can happen is that we create a new actor ID somehow (by forking or
+    // loading). Then we create a transaction with the new actor ID but never
+    // actually make any changes. Then, we create another actor ID in the
+    // same document - by forking it typically. This means that this last
+    // document has an IndexedCache with an actor ID in it which will never
+    // be saved to the document, but which is followed by an actor ID which
+    // will be saved. This in turn means that the indexes we save to the
+    // document are off by one and so we get load errors.
+    //
+    // The solution was to create the lookup table from actor index to actor
+    // ID directly from the actor IDs in the change graph rather than from the
+    // IndexedCache.
+    let actor0 = ActorId::from(&[0]);
+    let actor1 = ActorId::from(&[1]);
+    let actor2 = ActorId::from(&[2]);
+
+    let mut doc0 = AutoCommit::new().with_actor(actor0);
+    doc0.put(ROOT, "a", 1).unwrap();
+
+    // swap these actors and no error occurs
+    let mut doc1 = doc0.fork().with_actor(actor2);
+    let mut doc2 = doc0.fork().with_actor(actor1);
+
+    doc1.put(ROOT, "b", 2).unwrap();
+    doc2.merge(&mut doc1).unwrap();
+    // This call creates a transaction which doesn't do anything (because the
+    // "c" key doesn't exist) and so the actor ID (actor1) gets added to the
+    // IndexedCache of doc2
+    doc2.delete(ROOT, "c").unwrap();
+
+    // error occurs here
+    doc2.save_and_verify().unwrap();
+}