api: support list indexes in path

1 files changed, 294 insertions, 39 deletions

diff --git a/src/document/store.rs b/src/document/store.rs
index 13a3fc3..a55f95d 100644
--- a/src/document/store.rs
+++ b/src/document/store.rs
@@ -2,7 +2,8 @@
 
 use anyhow::anyhow;
 use automerge::{
-    ActorId, AutoCommit, ObjId, ObjType, ReadDoc, ScalarValue, Value, transaction::Transactable,
+    ActorId, AutoCommit, ObjId, ObjType, Prop, ReadDoc, ScalarValue, Value,
+    transaction::Transactable,
 };
 use base64::{Engine, engine::general_purpose::STANDARD as BASE64};
 use serde::Serialize;
@@ -18,7 +19,7 @@ pub(crate) enum StoreError {
     /// An insert where there is no list.
     #[error("not a list")]
     NotAList,
-    /// An insert past a list's end.
+    /// An index past a list's end (`length` items).
     #[error("index {index} is past the list's end ({length} items)")]
     PastTheEnd { index: usize, length: usize },
     #[error(transparent)]
@@ -47,11 +48,11 @@ enum Resolved {
 fn candidates(
     doc: &AutoCommit,
     parents: &[ObjId],
-    key: &str,
+    prop: impl Into<Prop> + Clone,
 ) -> Result<Vec<(Value<'static>, ObjId)>, StoreError> {
     let mut all = Vec::new();
     for parent in parents {
-        for (value, id) in doc.get_all(parent, key)? {
+        for (value, id) in doc.get_all(parent, prop.clone())? {
             all.push((value.into_owned(), id));
         }
     }
@@ -65,7 +66,104 @@ fn resolve(
     key: &str,
     log: Option<&mut ConflictLog>,
 ) -> Result<Option<Resolved>, StoreError> {
-    let mut all = candidates(doc, parents, key)?;
+    resolve_prop(doc, parents, key, key, log)
+}
+
+/// The item at `index` of `list` (concurrent writes there resolved as for a key).
+fn resolve_item(
+    doc: &AutoCommit,
+    list: &ObjId,
+    index: usize,
+    log: Option<&mut ConflictLog>,
+) -> Result<Option<Resolved>, StoreError> {
+    if index >= doc.length(list) {
+        return Ok(None);
+    }
+    resolve_prop(
+        doc,
+        std::slice::from_ref(list),
+        index,
+        &index.to_string(),
+        log,
+    )
+}
+
+/// What `segment` names within `current`: a key of merged maps, or the item of a list
+/// at the index it spells (`list_index`); None for anything else, and in a scalar.
+fn step(
+    doc: &AutoCommit,
+    current: &Resolved,
+    segment: &str,
+    log: Option<&mut ConflictLog>,
+) -> Result<Option<Resolved>, StoreError> {
+    match current {
+        Resolved::Maps(maps) => resolve(doc, maps, segment, log),
+        Resolved::Other(Value::Object(ObjType::List), list) => match list_index(segment) {
+            Some(index) => resolve_item(doc, list, index, log),
+            None => Ok(None),
+        },
+        Resolved::Other(..) => Ok(None),
+    }
+}
+
+/// A list index as a path names it: decimal digits, no sign, no leading zeros.
+pub(crate) fn list_index(segment: &str) -> Option<usize> {
+    let digits = !segment.is_empty() && segment.bytes().all(|byte| byte.is_ascii_digit());
+    if !digits || (segment.len() > 1 && segment.starts_with('0')) {
+        return None;
+    }
+    segment.parse().ok()
+}
+
+/// A negative list index (`-1` the last item): how far from the end.
+fn from_the_end(segment: &str) -> Option<usize> {
+    list_index(segment.strip_prefix('-')?).filter(|back| *back > 0)
+}
+
+/// `path` with its negative list indexes made positive (`-1` the last item; or, as the
+/// last segment with `insertion`, the end: where an insert appends), if it has any;
+/// None if it has none. An index before the start names nothing (`NotFound`). Only
+/// segments within a list count: in a map, `-1` is a key like any other.
+pub(crate) fn positive_path(
+    doc: &AutoCommit,
+    path: &[String],
+    insertion: bool,
+) -> Result<Option<Vec<String>>, StoreError> {
+    let mut current = Resolved::Maps(vec![automerge::ROOT]);
+    let mut positive = path.to_vec();
+    let mut changed = false;
+    for (depth, segment) in path.iter().enumerate() {
+        let mut segment = segment.clone();
+        if let Resolved::Other(Value::Object(ObjType::List), list) = &current
+            && let Some(back) = from_the_end(&segment)
+        {
+            let last = depth + 1 == path.len();
+            let length = doc.length(list) + usize::from(insertion && last);
+            let index = length.checked_sub(back).ok_or(StoreError::NotFound)?;
+            segment = index.to_string();
+            positive[depth] = segment.clone();
+            changed = true;
+        }
+        match step(doc, &current, &segment, None)? {
+            Some(next) => current = next,
+            // Nothing further to make positive.
+            None => break,
+        }
+    }
+    Ok(changed.then_some(positive))
+}
+
+/// Resolves `key` (a map key or a list index) in `parents`; `name` is how conflict
+/// reports name it.
+fn resolve_prop(
+    doc: &AutoCommit,
+    parents: &[ObjId],
+    prop: impl Into<Prop> + Clone,
+    name: &str,
+    log: Option<&mut ConflictLog>,
+) -> Result<Option<Resolved>, StoreError> {
+    let key = name;
+    let mut all = candidates(doc, parents, prop)?;
     if all.is_empty() {
         return Ok(None);
     }
@@ -187,14 +285,11 @@ fn read_path_inner(
     let mut current = Resolved::Maps(vec![automerge::ROOT]);
 
     for (index, segment) in path.iter().enumerate() {
-        let Resolved::Maps(maps) = &current else {
-            return Ok(None);
-        };
         if let Some(log) = log.as_deref_mut() {
             // The last segment is the requested value itself, not an ancestor.
             log.in_ancestors = index + 1 < path.len();
         }
-        match resolve(doc, maps, segment, log.as_deref_mut())? {
+        match step(doc, &current, segment, log.as_deref_mut())? {
             Some(next) => current = next,
             None => return Ok(None),
         }
@@ -253,13 +348,27 @@ pub(crate) fn read_shallow(
     doc: &AutoCommit,
     path: &[String],
 ) -> Result<Option<JsonValue>, StoreError> {
-    let Some(resolved) = resolve_at(doc, path)? else {
+    let Some(resolved) = resolve_through(doc, path)? else {
         return Ok(None);
     };
     summary(doc, &resolved, true).map(Some)
 }
 
-/// A summary of `resolved` (`read_shallow`); with `entries`, a map's keys' too.
+/// The resolved value at `path` (the empty path is the root map), through maps and
+/// lists (`step`). `resolve_at` goes through maps only.
+fn resolve_through(doc: &AutoCommit, path: &[String]) -> Result<Option<Resolved>, StoreError> {
+    let mut current = Resolved::Maps(vec![automerge::ROOT]);
+    for segment in path {
+        match step(doc, &current, segment, None)? {
+            Some(next) => current = next,
+            None => return Ok(None),
+        }
+    }
+    Ok(Some(current))
+}
+
+/// A summary of `resolved` (`read_shallow`); with `entries`, a map's keys' too, or a
+/// list's items' (by index).
 fn summary(doc: &AutoCommit, resolved: &Resolved, entries: bool) -> Result<JsonValue, StoreError> {
     let mut out = serde_json::Map::new();
     match resolved {
@@ -281,8 +390,18 @@ fn summary(doc: &AutoCommit, resolved: &Resolved, entries: bool) -> Result<JsonV
             return summary(doc, &Resolved::Maps(vec![id.clone()]), entries);
         }
         Resolved::Other(Value::Object(ObjType::List), id) => {
+            let length = doc.length(id);
             out.insert("type".into(), "list".into());
-            out.insert("size".into(), doc.length(id).into());
+            out.insert("size".into(), length.into());
+            if entries {
+                let mut listed = serde_json::Map::new();
+                for index in 0..length {
+                    if let Some(item) = resolve_item(doc, id, index, None)? {
+                        listed.insert(index.to_string(), summary(doc, &item, false)?);
+                    }
+                }
+                out.insert("entries".into(), JsonValue::Object(listed));
+            }
         }
         Resolved::Other(Value::Object(ObjType::Text), id) => {
             out.insert("type".into(), "text".into());
@@ -338,7 +457,7 @@ pub(crate) fn read_candidates(
             _ => return Ok(Vec::new()),
         };
     }
-    candidates(doc, &maps, leaf)?
+    candidates(doc, &maps, leaf.as_str())?
         .into_iter()
         .map(|(value, id)| match value {
             Value::Scalar(scalar) => scalar_to_json(scalar.into_owned()),
@@ -347,43 +466,96 @@ pub(crate) fn read_candidates(
         .collect()
 }
 
-/// Writes (replaces) the value at `path`, creating intermediate maps.
+/// Writes (replaces) the value at `path`, creating intermediate maps. Within a list,
+/// the segment is an index (`list_index`): an item there is replaced, one at the end
+/// appended; past the end, or anything but an index, names nothing (`NotFound`).
 pub(crate) fn write_path(
     doc: &mut AutoCommit,
     path: &[String],
     value: &JsonValue,
 ) -> Result<(), StoreError> {
     let (leaf, parents) = path.split_last().ok_or(StoreError::NotFound)?;
-    let maps = ensure_maps(doc, parents)?;
-
-    // Replace semantics: clear the key in every merged parent, or an old map
-    // would merge into the new value.
-    delete_in_all(doc, &maps, leaf)?;
-    json_to_automerge(doc, &maps[0], leaf, value)?;
+    match parent_for_write(doc, parents)? {
+        Parent::Maps(maps) => {
+            // Replace semantics: clear the key in every merged parent, or an old map
+            // would merge into the new value.
+            delete_in_all(doc, &maps, leaf)?;
+            json_to_automerge(doc, &maps[0], leaf, value)?;
+        }
+        Parent::List(list) => {
+            let index = list_index(leaf).ok_or(StoreError::NotFound)?;
+            let length = doc.length(&list);
+            if index > length {
+                return Err(StoreError::NotFound);
+            }
+            if index < length {
+                doc.delete(&list, index)?;
+            }
+            write_value(doc, &list, Slot::Index(index), value)?;
+        }
+    }
     Ok(())
 }
 
-/// Inserts `value` into the list at `path`: at `index` (the items from there on move
-/// up one), or at the end without one. Returns where it went. An index past the end is
-/// an error (`PastTheEnd`), as is a path without a list (`NotAList`, `NotFound`).
+/// What a write's last segment goes into.
+enum Parent {
+    /// Merged maps (`[0]` takes new keys).
+    Maps(Vec<ObjId>),
+    List(ObjId),
+}
+
+/// The parent of a write at `parents` + one more segment: missing maps are created on
+/// the way; through a list only by an index of an item it has. A scalar or text on the
+/// way is a `Conflict`.
+fn parent_for_write(doc: &mut AutoCommit, parents: &[String]) -> Result<Parent, StoreError> {
+    let mut current = Parent::Maps(vec![automerge::ROOT]);
+    for segment in parents {
+        let next = match &current {
+            Parent::Maps(maps) => match resolve(doc, maps, segment, None)? {
+                // A concurrent creation elsewhere is merged on read.
+                None => Resolved::Maps(vec![doc.put_object(
+                    &maps[0],
+                    segment.as_str(),
+                    ObjType::Map,
+                )?]),
+                Some(next) => next,
+            },
+            Parent::List(list) => {
+                let index = list_index(segment).ok_or(StoreError::NotFound)?;
+                resolve_item(doc, list, index, None)?.ok_or(StoreError::NotFound)?
+            }
+        };
+        current = match next {
+            Resolved::Maps(maps) => Parent::Maps(maps),
+            Resolved::Other(Value::Object(ObjType::List), list) => Parent::List(list),
+            Resolved::Other(..) => return Err(StoreError::Conflict),
+        };
+    }
+    Ok(current)
+}
+
+/// Inserts `value` into a list: `path` ends in the index it goes to (the items from
+/// there on move up one; the list's length appends). An index past the end is
+/// `PastTheEnd`; a parent that isn't a list `NotAList`; anything but an index there, or
+/// no parent, `NotFound`.
 pub(crate) fn insert_path(
     doc: &mut AutoCommit,
     path: &[String],
-    index: Option<usize>,
     value: &JsonValue,
-) -> Result<usize, StoreError> {
-    let list = match resolve_at(doc, path)? {
+) -> Result<(), StoreError> {
+    let (leaf, parents) = path.split_last().ok_or(StoreError::NotFound)?;
+    let list = match resolve_through(doc, parents)? {
         None => return Err(StoreError::NotFound),
         Some(Resolved::Other(Value::Object(ObjType::List), id)) => id,
         Some(_) => return Err(StoreError::NotAList),
     };
+    let index = list_index(leaf).ok_or(StoreError::NotFound)?;
     let length = doc.length(&list);
-    let index = index.unwrap_or(length);
     if index > length {
         return Err(StoreError::PastTheEnd { index, length });
     }
     write_value(doc, &list, Slot::Index(index), value)?;
-    Ok(index)
+    Ok(())
 }
 
 /// The merged maps at `path`, creating missing maps on the way.
@@ -456,6 +628,43 @@ pub(crate) fn copy_path_to(
     )
 }
 
+/// Deletes the value at `path` as the API names it: through lists too, where a segment
+/// is an index (`list_index`; the items after it move down one); `prune` doesn't reach
+/// through a list. Within maps only, as `delete_path`.
+pub(crate) fn delete_at(
+    doc: &mut AutoCommit,
+    path: &[String],
+    prune: bool,
+) -> Result<(), StoreError> {
+    let (leaf, parents) = path.split_last().ok_or(StoreError::NotFound)?;
+    let mut current = Resolved::Maps(vec![automerge::ROOT]);
+    let mut through_list = false;
+    for segment in parents {
+        if let Resolved::Other(Value::Object(ObjType::List), _) = current {
+            through_list = true;
+        }
+        current = step(doc, &current, segment, None)?.ok_or(StoreError::NotFound)?;
+    }
+    match (&current, through_list) {
+        (Resolved::Other(Value::Object(ObjType::List), list), _) => {
+            let index = list_index(leaf).ok_or(StoreError::NotFound)?;
+            if index >= doc.length(list) {
+                return Err(StoreError::NotFound);
+            }
+            doc.delete(list, index)?;
+            Ok(())
+        }
+        (Resolved::Maps(maps), true) => {
+            if resolve(doc, maps, leaf, None)?.is_none() {
+                return Err(StoreError::NotFound);
+            }
+            delete_in_all(doc, maps, leaf)
+        }
+        (Resolved::Maps(_), false) => delete_path(doc, path, prune),
+        (Resolved::Other(..), _) => Err(StoreError::NotFound),
+    }
+}
+
 /// Deletes the value at `path`, optionally pruning ancestors that become empty.
 pub(crate) fn delete_path(
     doc: &mut AutoCommit,
@@ -846,27 +1055,73 @@ mod tests {
     }
 
     #[test]
-    fn inserts_into_lists() {
+    fn paths_go_through_lists() {
         let mut doc = AutoCommit::new();
-        write_path(&mut doc, &path("list"), &json!(["b", "d"])).unwrap();
+        write_path(&mut doc, &path("list"), &json!(["b", {"k": 1}, "d"])).unwrap();
+        assert_eq!(read_path(&doc, &path("list/0")).unwrap(), Some(json!("b")));
+        assert_eq!(read_path(&doc, &path("list/1/k")).unwrap(), Some(json!(1)));
+        // Not an index, or past the end: nothing.
+        for missing in ["list/3", "list/x", "list/01", "list/-1", "list/1/k/0"] {
+            assert_eq!(read_path(&doc, &path(missing)).unwrap(), None, "{missing}");
+        }
+        // Replaced, and appended at the end; past it, nothing.
+        write_path(&mut doc, &path("list/0"), &json!("a")).unwrap();
+        write_path(&mut doc, &path("list/3"), &json!("e")).unwrap();
+        write_path(&mut doc, &path("list/1/k"), &json!(2)).unwrap();
+        assert!(matches!(
+            write_path(&mut doc, &path("list/9"), &json!(0)),
+            Err(StoreError::NotFound)
+        ));
         assert_eq!(
-            insert_path(&mut doc, &path("list"), Some(0), &json!("a")).unwrap(),
-            0
+            read_path(&doc, &path("list")).unwrap(),
+            Some(json!(["a", {"k": 2}, "d", "e"]))
         );
+        delete_at(&mut doc, &path("list/2"), false).unwrap();
         assert_eq!(
-            insert_path(&mut doc, &path("list"), Some(2), &json!("c")).unwrap(),
-            2
+            read_path(&doc, &path("list")).unwrap(),
+            Some(json!(["a", {"k": 2}, "e"]))
         );
         assert_eq!(
-            insert_path(&mut doc, &path("list"), None, &json!({"e": 5})).unwrap(),
-            4
+            read_shallow(&doc, &path("list")).unwrap().unwrap()["entries"]["1"]["type"],
+            json!("map")
         );
+    }
+
+    #[test]
+    fn negative_indexes_count_from_the_end() {
+        let mut doc = AutoCommit::new();
+        write_path(&mut doc, &path("list"), &json!(["a", "b"])).unwrap();
+        write_path(&mut doc, &path("map"), &json!({"-1": "a key"})).unwrap();
+        assert_eq!(
+            positive_path(&doc, &path("list/-1"), false).unwrap(),
+            Some(path("list/1"))
+        );
+        // Inserting: -1 is the end.
+        assert_eq!(
+            positive_path(&doc, &path("list/-1"), true).unwrap(),
+            Some(path("list/2"))
+        );
+        assert!(matches!(
+            positive_path(&doc, &path("list/-3"), false),
+            Err(StoreError::NotFound)
+        ));
+        assert_eq!(positive_path(&doc, &path("map/-1"), false).unwrap(), None);
+        assert_eq!(positive_path(&doc, &path("list/0"), false).unwrap(), None);
+    }
+
+    #[test]
+    fn inserts_into_lists() {
+        let mut doc = AutoCommit::new();
+        write_path(&mut doc, &path("list"), &json!(["b", "d"])).unwrap();
+        insert_path(&mut doc, &path("list/0"), &json!("a")).unwrap();
+        insert_path(&mut doc, &path("list/2"), &json!("c")).unwrap();
+        insert_path(&mut doc, &path("list/4"), &json!({"e": 5})).unwrap();
         assert_eq!(
             read_path(&doc, &path("list")).unwrap(),
             Some(json!(["a", "b", "c", "d", {"e": 5}]))
         );
         assert!(matches!(
-            insert_path(&mut doc, &path("list"), Some(6), &json!(1)),
+            insert_path(&mut doc, &path("list/6"), &json!(1)),
             Err(StoreError::PastTheEnd {
                 index: 6,
                 length: 5
@@ -874,11 +1129,11 @@ mod tests {
         ));
         write_path(&mut doc, &path("map"), &json!({"k": 1})).unwrap();
         assert!(matches!(
-            insert_path(&mut doc, &path("map"), None, &json!(1)),
+            insert_path(&mut doc, &path("map/0"), &json!(1)),
             Err(StoreError::NotAList)
         ));
         assert!(matches!(
-            insert_path(&mut doc, &path("nothing"), None, &json!(1)),
+            insert_path(&mut doc, &path("nothing/0"), &json!(1)),
             Err(StoreError::NotFound)
         ));
     }