api: /admin/changes read ops, not diffs

The new store::changed_by reads each change's own operations instead of
diffing the document before and after it.  Each object's path is found
once per change, as it was right after that change.  So the cost now
grows with the size of the change, not the size of the map it touched.

- It names paths the same way the diff did: a map entry by its key, and
  list and text edits by the list or text.
- It relies on import_obj, which Automerge marks as hidden from its
  docs, to turn an operation's object ID back into an object.

2 files changed, 90 insertions, 10 deletions

diff --git a/src/api/changes.rs b/src/api/changes.rs
index 1dd1f91..ee6a74a 100644
--- a/src/api/changes.rs
+++ b/src/api/changes.rs
@@ -17,8 +17,8 @@ use crate::state::AppState;
 
 /// Changes listed at most.
 const MAX_LIMIT: usize = 1000;
-/// Changes looked at at most, newest first, for those touching `path`: each costs a
-/// diff, under the document's read lock.
+/// Changes looked at at most, newest first, for those touching `path`: each costs
+/// decoding it, under the document's read lock (`store::changed_by`).
 const MAX_SCANNED: usize = 10_000;
 
 #[derive(Debug, Deserialize)]
@@ -107,14 +107,8 @@ fn changes(
             break;
         }
         scanned += 1;
-        // What this change did: its history without it, to its history with it.
-        let mut paths: Vec<Vec<String>> =
-            store::changed(doc, &meta.deps, &[meta.hash], InLists::Index)
-                .into_iter()
-                .map(|changed| changed.path)
-                .collect();
-        paths.sort();
-        paths.dedup();
+        // What this change did, from its operations.
+        let paths = store::changed_by(doc, &meta.hash, InLists::Index).unwrap_or_default();
         if let Some(path) = path
             && !paths
                 .iter()
diff --git a/src/document/store.rs b/src/document/store.rs
index 1a235b2..f18f2fa 100644
--- a/src/document/store.rs
+++ b/src/document/store.rs
@@ -83,6 +83,53 @@ fn patch_path(patch: &automerge::Patch, lists: InLists) -> Vec<String> {
     path
 }
 
+/// The store paths the change `hash` touched (each once, in order), as [`changed`] has
+/// them, but from its operations rather than a diff: what a diff costs grows with the
+/// objects it looks into, what this costs with the change. An operation on an object
+/// that isn't reachable after the change (made and deleted in it) touches nothing.
+/// None if `doc` lacks the change.
+pub(crate) fn changed_by(
+    doc: &Automerge,
+    hash: &automerge::ChangeHash,
+    lists: InLists,
+) -> Option<Vec<Vec<String>>> {
+    use automerge::legacy::{Key, ObjectId};
+    let change = doc.get_change_by_hash(hash)?.decode();
+    let heads = [*hash];
+    // Each object's path as it was after the change, and whether that is a list's (as
+    // `InLists::Whole` names what is inside one).
+    let mut objects: std::collections::HashMap<ObjectId, Option<(Vec<String>, bool)>> =
+        std::collections::HashMap::new();
+    let mut paths = BTreeSet::new();
+    for op in change.operations {
+        let object = objects.entry(op.obj.clone()).or_insert_with(|| {
+            let id = match &op.obj {
+                ObjectId::Root => automerge::ROOT,
+                ObjectId::Id(id) => doc.import_obj(&id.to_string()).ok()?,
+            };
+            let mut path = Vec::new();
+            for (_, prop) in doc.parents_at(&id, &heads).ok()?.visible_path()? {
+                match (prop, lists) {
+                    (Prop::Map(key), _) => path.push(key),
+                    (Prop::Seq(index), InLists::Index) => path.push(index.to_string()),
+                    (Prop::Seq(_), InLists::Whole) => return Some((path, true)),
+                }
+            }
+            Some((path, false))
+        });
+        let Some((path, in_list)) = object else {
+            continue;
+        };
+        let mut path = path.clone();
+        // A map entry by its key; list and text edits by the containing object.
+        if let (Key::Map(key), false) = (op.key, *in_list) {
+            path.push(key.to_string());
+        }
+        paths.insert(path);
+    }
+    Some(paths.into_iter().collect())
+}
+
 /// Whether one path is within the other (a change at either touches both).
 pub(crate) fn paths_related(a: &[String], b: &[String]) -> bool {
     a.starts_with(b) || b.starts_with(a)
@@ -1596,6 +1643,45 @@ mod tests {
     }
 
     #[test]
+    fn changes_name_the_paths_their_operations_touch() {
+        fn touched(
+            doc: &mut Automerge,
+            lists: InLists,
+            write: impl FnOnce(&mut automerge::transaction::Transaction<'_>) -> Result<(), StoreError>,
+        ) -> Vec<Vec<String>> {
+            try_change(doc, write).unwrap();
+            let head = doc.get_heads()[0];
+            changed_by(doc, &head, lists).unwrap()
+        }
+        let mut doc = Automerge::new();
+        // An item by its list; what is inside it by its index.
+        assert_eq!(
+            touched(&mut doc, InLists::Index, |doc| {
+                write_path(doc, &path("a"), &json!({"b": 1, "list": [{"k": 1}]}))
+            }),
+            [path("a"), path("a/b"), path("a/list"), path("a/list/0/k")]
+        );
+        assert_eq!(
+            touched(&mut doc, InLists::Index, |doc| {
+                write_path(doc, &path("a/list/0/k"), &json!(2))
+            }),
+            [path("a/list/0/k")]
+        );
+        assert_eq!(
+            touched(&mut doc, InLists::Whole, |doc| {
+                write_path(doc, &path("a/list/0/k"), &json!(3))
+            }),
+            [path("a/list")]
+        );
+        assert_eq!(
+            touched(&mut doc, InLists::Index, |doc| {
+                delete_path(doc, &path("a/b"), false)
+            }),
+            [path("a/b")]
+        );
+    }
+
+    #[test]
     fn paths_go_through_lists() {
         let mut doc = Automerge::new();
         try_change(&mut doc, |doc| {