aboutsummaryrefslogtreecommitdiffstats
path: root/src/document/store.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/document/store.rs')
-rw-r--r--src/document/store.rs1438
1 files changed, 1253 insertions, 185 deletions
diff --git a/src/document/store.rs b/src/document/store.rs
index e742edb..f18f2fa 100644
--- a/src/document/store.rs
+++ b/src/document/store.rs
@@ -2,19 +2,168 @@
use anyhow::anyhow;
use automerge::{
- ActorId, AutoCommit, ObjId, ObjType, ReadDoc, ScalarValue, Value, transaction::Transactable,
+ ActorId, Automerge, ObjId, ObjType, Prop, ReadDoc, ScalarValue, Value,
+ transaction::Transactable,
};
-use base64::{Engine, engine::general_purpose::STANDARD as BASE64};
use serde::Serialize;
use serde_json::Value as JsonValue;
use std::collections::BTreeSet;
+use super::typed::{self, JsonForm, Kind, TimestampFormat, Val};
+
+/// Store paths touched by one batch of document changes (`AppState::change_events`).
+#[derive(Debug)]
+pub(crate) struct ChangeSet {
+ pub(crate) paths: Vec<Vec<String>>,
+}
+
+/// How `changed` names a change inside a list.
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub(crate) enum InLists {
+ /// By the item's index: `servers/0/name` (the change publisher).
+ Index,
+ /// By the list: `servers` (remakes replay a list whole).
+ Whole,
+}
+
+/// A store path changes touched, and whether concurrent writes left a conflict there.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) struct Changed {
+ pub(crate) path: Vec<String>,
+ pub(crate) conflict: bool,
+}
+
+/// The store paths the changes from `before` to `after` touched, as the document
+/// reports them (a path may come more than once). A map entry by its key, a counter
+/// incremented in a map by its key, and list and text edits by the containing object;
+/// inside a list as `lists` says.
+pub(crate) fn changed(
+ doc: &Automerge,
+ before: &[automerge::ChangeHash],
+ after: &[automerge::ChangeHash],
+ lists: InLists,
+) -> Vec<Changed> {
+ changed_in(&doc.diff(before, after), lists)
+}
+
+/// The store paths `patches` touched, as [`changed`] has them.
+pub(crate) fn changed_in(patches: &[automerge::Patch], lists: InLists) -> Vec<Changed> {
+ patches
+ .iter()
+ .map(|patch| Changed {
+ path: patch_path(patch, lists),
+ conflict: matches!(
+ patch.action,
+ automerge::PatchAction::PutMap { conflict: true, .. }
+ ),
+ })
+ .collect()
+}
+
+fn patch_path(patch: &automerge::Patch, lists: InLists) -> Vec<String> {
+ use automerge::PatchAction;
+ let mut path = Vec::new();
+ for (_, prop) in &patch.path {
+ match (prop, lists) {
+ (Prop::Map(key), _) => path.push(key.clone()),
+ (Prop::Seq(index), InLists::Index) => path.push(index.to_string()),
+ (Prop::Seq(_), InLists::Whole) => return path,
+ }
+ }
+ match &patch.action {
+ PatchAction::PutMap { key, .. }
+ | PatchAction::DeleteMap { key, .. }
+ | PatchAction::Increment {
+ prop: Prop::Map(key),
+ ..
+ } => path.push(key.clone()),
+ // List and text edits: the containing object.
+ _ => {}
+ }
+ 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)
+}
+
#[derive(Debug, thiserror::Error)]
pub(crate) enum StoreError {
#[error("path crosses a non-map value")]
Conflict,
#[error("value does not exist")]
NotFound,
+ /// An insert where there is no list.
+ #[error("not a list")]
+ NotAList,
+ /// 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 },
+ /// An increment of something that isn't a counter (`increment_path`).
+ #[error("not a counter")]
+ NotACounter,
+ /// A write that would change the type of what it writes over, where that isn't
+ /// wanted (`Writing::retype`).
+ #[error("would change {0}")]
+ Retyping(Retyped),
+ /// A cast that isn't possible (`cast_path`, `typed::cast`), and why.
+ #[error("can't cast {} to {}: {why}", .from.name(), .to.name())]
+ NotCastable { from: Kind, to: Kind, why: String },
+ /// A read at heads the document doesn't have (`at::At`).
+ #[error("this node doesn't have these heads (yet)")]
+ UnknownHeads,
+ /// The node is rejoining a newer epoch: no writes until it is done
+ /// (`Replica::writable`).
+ #[error("the node is rejoining a newer epoch; writes are refused until it is done")]
+ Rejoining,
#[error(transparent)]
Doc(#[from] automerge::AutomergeError),
#[error(transparent)]
@@ -39,13 +188,13 @@ enum Resolved {
/// All concurrent values of `key` across a merged set of parent maps, newest first.
fn candidates(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
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));
}
}
@@ -54,12 +203,109 @@ fn candidates(
}
fn resolve(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
parents: &[ObjId],
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: &impl ReadDoc,
+ 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: &impl ReadDoc,
+ 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: &impl ReadDoc,
+ 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: &impl ReadDoc,
+ 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);
}
@@ -85,21 +331,22 @@ fn resolve(
}
}
-fn merged_keys(doc: &AutoCommit, maps: &[ObjId]) -> BTreeSet<String> {
+fn merged_keys(doc: &impl ReadDoc, maps: &[ObjId]) -> BTreeSet<String> {
maps.iter().flat_map(|map| doc.keys(map)).collect()
}
fn resolved_to_json(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
resolved: &Resolved,
+ form: JsonForm,
mut log: Option<&mut ConflictLog>,
) -> Result<JsonValue, StoreError> {
let maps = match resolved {
Resolved::Maps(maps) => maps,
Resolved::Other(Value::Scalar(scalar), _) => {
- return scalar_to_json(scalar.clone().into_owned());
+ return scalar_to_json(scalar.clone().into_owned(), form);
}
- Resolved::Other(Value::Object(_), id) => return object_to_json(doc, id, log),
+ Resolved::Other(Value::Object(_), id) => return object_to_json(doc, id, form, log),
};
let mut out = serde_json::Map::new();
@@ -122,7 +369,9 @@ fn resolved_to_json(
}
};
- let json = nested(&mut log, &key, |log| resolved_to_json(doc, &child, log))?;
+ let json = nested(&mut log, &key, |log| {
+ resolved_to_json(doc, &child, form, log)
+ })?;
out.insert(key, json);
}
} else {
@@ -131,40 +380,43 @@ fn resolved_to_json(
let Some(child) = resolve(doc, maps, &key, log.as_deref_mut())? else {
continue;
};
- let json = nested(&mut log, &key, |log| resolved_to_json(doc, &child, log))?;
+ let json = nested(&mut log, &key, |log| {
+ resolved_to_json(doc, &child, form, log)
+ })?;
out.insert(key, json);
}
}
- Ok(JsonValue::Object(out))
+ Ok(typed::map_to_json(out, form))
}
fn object_to_json(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
id: &ObjId,
+ form: JsonForm,
mut log: Option<&mut ConflictLog>,
) -> Result<JsonValue, StoreError> {
match doc.object_type(id)? {
- ObjType::Map => resolved_to_json(doc, &Resolved::Maps(vec![id.clone()]), log),
+ ObjType::Map => resolved_to_json(doc, &Resolved::Maps(vec![id.clone()]), form, log),
ObjType::List => {
let mut out = Vec::new();
for (index, item) in doc.list_range(id, ..).enumerate() {
let child_id = item.id();
out.push(match Value::from(item.value) {
Value::Object(_) => nested(&mut log, &index.to_string(), |log| {
- object_to_json(doc, &child_id, log)
+ object_to_json(doc, &child_id, form, log)
})?,
- Value::Scalar(scalar) => scalar_to_json(scalar.into_owned())?,
+ Value::Scalar(scalar) => scalar_to_json(scalar.into_owned(), form)?,
});
}
Ok(JsonValue::Array(out))
}
- ObjType::Text => Ok(JsonValue::String(doc.text(id)?)),
+ ObjType::Text => Ok(typed::text_to_json(doc.text(id)?, form)),
ObjType::Table => Err(anyhow!("Automerge tables are not supported").into()),
}
}
-fn delete_in_all(doc: &mut AutoCommit, maps: &[ObjId], key: &str) -> Result<(), StoreError> {
+fn delete_in_all(doc: &mut impl Transactable, maps: &[ObjId], key: &str) -> Result<(), StoreError> {
for map in maps {
if doc.get(map, key)?.is_some() {
doc.delete(map, key)?;
@@ -174,152 +426,779 @@ fn delete_in_all(doc: &mut AutoCommit, maps: &[ObjId], key: &str) -> Result<(),
}
fn read_path_inner(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
path: &[String],
+ form: JsonForm,
mut log: Option<&mut ConflictLog>,
) -> Result<Option<JsonValue>, StoreError> {
- 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())? {
- Some(next) => current = next,
- None => return Ok(None),
- }
- if let Some(log) = log.as_deref_mut() {
- log.path.push(segment.clone());
- }
- }
-
- if let Some(log) = log.as_deref_mut() {
- log.in_ancestors = false;
- }
- Ok(Some(resolved_to_json(doc, &current, log)?))
+ let Some(current) = resolve_logged(doc, path, log.as_deref_mut())? else {
+ return Ok(None);
+ };
+ Ok(Some(resolved_to_json(doc, &current, form, log)?))
}
/// Reads a path; the empty path is the whole store.
pub(crate) fn read_path(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
path: &[String],
) -> Result<Option<JsonValue>, StoreError> {
- read_path_inner(doc, path, None)
+ read_path_as(doc, path, JsonForm::default())
}
+/// [`read_path`], in JSON of `form`.
+pub(crate) fn read_path_as(
+ doc: &impl ReadDoc,
+ path: &[String],
+ form: JsonForm,
+) -> Result<Option<JsonValue>, StoreError> {
+ read_path_inner(doc, path, form, None)
+}
+
+#[cfg(test)]
pub(crate) fn read_path_with_conflicts(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
+ path: &[String],
+) -> Result<Option<(JsonValue, Vec<ConflictReport>)>, StoreError> {
+ read_path_with_conflicts_as(doc, path, JsonForm::default())
+}
+
+/// [`read_path_with_conflicts`], in JSON of `form`.
+pub(crate) fn read_path_with_conflicts_as(
+ doc: &impl ReadDoc,
path: &[String],
+ form: JsonForm,
) -> Result<Option<(JsonValue, Vec<ConflictReport>)>, StoreError> {
let mut log = ConflictLog {
want_values: true,
+ form,
..Default::default()
};
- let value = read_path_inner(doc, path, Some(&mut log))?;
+ let value = read_path_inner(doc, path, form, Some(&mut log))?;
Ok(value.map(|value| (value, log.reports)))
}
+/// What is stored at `path` (the empty path: the root map), and, where it is a scalar
+/// or a text, the value itself, to show natively (`typed::native`); None if nothing is
+/// there.
+pub(crate) fn read_held(doc: &impl ReadDoc, path: &[String]) -> Result<Option<Held>, StoreError> {
+ let Some(resolved) = resolve_through(doc, path)? else {
+ return Ok(None);
+ };
+ Ok(Some(match resolved {
+ Resolved::Maps(_) | Resolved::Other(Value::Object(ObjType::Map), _) => Held {
+ kind: Kind::Map,
+ value: None,
+ },
+ Resolved::Other(Value::Object(ObjType::List), _) => Held {
+ kind: Kind::List,
+ value: None,
+ },
+ Resolved::Other(Value::Object(ObjType::Text), id) => Held {
+ kind: Kind::Text,
+ value: Some(ScalarValue::Str(doc.text(&id)?.into())),
+ },
+ Resolved::Other(Value::Object(ObjType::Table), _) => {
+ return Err(anyhow!("Automerge tables are not supported").into());
+ }
+ Resolved::Other(Value::Scalar(scalar), _) => {
+ let scalar = scalar.into_owned();
+ Held {
+ kind: Kind::of(&scalar),
+ value: Some(scalar),
+ }
+ }
+ }))
+}
+
+/// What a path holds (`read_held`).
+#[derive(Debug, Clone)]
+pub(crate) struct Held {
+ pub(crate) kind: Kind,
+ /// A scalar, or a text's characters as a string.
+ pub(crate) value: Option<ScalarValue>,
+}
+
/// For streams: the value, plus whether the path or subtree involves any conflict.
/// Reports are collected without values, so this costs little more than read_path.
pub(crate) fn read_path_traced(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
path: &[String],
) -> Result<(Option<JsonValue>, bool), StoreError> {
let mut log = ConflictLog::default();
- let value = read_path_inner(doc, path, Some(&mut log))?;
+ let value = read_path_inner(doc, path, JsonForm::default(), Some(&mut log))?;
Ok((value, !log.reports.is_empty()))
}
-/// Keys of the merged map at `path`; empty if it doesn't exist or isn't a map.
-pub(crate) fn keys_at(doc: &AutoCommit, path: &[String]) -> Result<Vec<String>, StoreError> {
- let mut maps = vec![automerge::ROOT];
- for segment in path {
- maps = match resolve(doc, &maps, segment, None)? {
- Some(Resolved::Maps(next)) => next,
- _ => return Ok(Vec::new()),
- };
+/// Strings and bytes up to this long are in a shallow read's summaries.
+const SHALLOW_INLINE: usize = 256;
+
+/// What's at `path` (the empty path is the whole store), one level deep: a summary of
+/// it, `type` (`map`, `list`, `text`, `string`, `bytes`, `number`, `boolean`, `null`,
+/// or `unknown`, an Automerge scalar of a later version)
+/// and `size` (keys, items, characters or bytes), and its `value` where it's a short
+/// scalar; a map's has its keys' summaries too, under `entries`. Concurrent values
+/// resolved as a read resolves them; conflicts not reported.
+pub(crate) fn read_shallow(
+ doc: &impl ReadDoc,
+ path: &[String],
+) -> Result<Option<JsonValue>, StoreError> {
+ let Some(resolved) = resolve_through(doc, path)? else {
+ return Ok(None);
+ };
+ summary(doc, &resolved, true).map(Some)
+}
+
+/// The resolved value at `path` (the empty path is the root map), through maps and
+/// lists (`step`).
+fn resolve_through(doc: &impl ReadDoc, path: &[String]) -> Result<Option<Resolved>, StoreError> {
+ resolve_logged(doc, path, None)
+}
+
+/// `resolve_through`, noting the conflicts on the way in `log` (as ancestors, but the
+/// last segment's: the requested value's), its path left at `path`.
+fn resolve_logged(
+ doc: &impl ReadDoc,
+ path: &[String],
+ mut log: Option<&mut ConflictLog>,
+) -> Result<Option<Resolved>, StoreError> {
+ let mut current = Resolved::Maps(vec![automerge::ROOT]);
+ for (index, segment) in path.iter().enumerate() {
+ 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 step(doc, &current, segment, log.as_deref_mut())? {
+ Some(next) => current = next,
+ None => return Ok(None),
+ }
+ if let Some(log) = log.as_deref_mut() {
+ log.path.push(segment.clone());
+ }
+ }
+ if let Some(log) = log {
+ log.in_ancestors = false;
}
- Ok(merged_keys(doc, &maps).into_iter().collect())
+ 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: &impl ReadDoc,
+ resolved: &Resolved,
+ entries: bool,
+) -> Result<JsonValue, StoreError> {
+ let mut out = serde_json::Map::new();
+ match resolved {
+ Resolved::Maps(maps) => {
+ let keys = merged_keys(doc, maps);
+ out.insert("type".into(), "map".into());
+ out.insert("size".into(), keys.len().into());
+ if entries {
+ let mut listed = serde_json::Map::new();
+ for key in keys {
+ if let Some(child) = resolve(doc, maps, &key, None)? {
+ listed.insert(key, summary(doc, &child, false)?);
+ }
+ }
+ out.insert("entries".into(), JsonValue::Object(listed));
+ }
+ }
+ Resolved::Other(Value::Object(ObjType::Map), id) => {
+ 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(), 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());
+ out.insert("size".into(), doc.length(id).into());
+ }
+ Resolved::Other(Value::Object(ObjType::Table), _) => {
+ return Err(anyhow!("Automerge tables are not supported").into());
+ }
+ Resolved::Other(Value::Scalar(scalar), _) => {
+ let kind = Kind::of(scalar);
+ let size = match &**scalar {
+ ScalarValue::Str(text) => Some(text.len()),
+ ScalarValue::Bytes(bytes) => Some(bytes.len()),
+ _ => None,
+ };
+ out.insert("type".into(), kind.name().into());
+ if let Some(size) = size {
+ out.insert("size".into(), size.into());
+ }
+ if kind != Kind::Unknown && size.is_none_or(|size| size <= SHALLOW_INLINE) {
+ out.insert(
+ "value".into(),
+ scalar_to_json(scalar.clone().into_owned(), JsonForm::default())?,
+ );
+ }
+ }
+ }
+ Ok(JsonValue::Object(out))
+}
+
+/// Keys of the merged map at `path`; empty if it doesn't exist or isn't a map.
+pub(crate) fn keys_at(doc: &impl ReadDoc, path: &[String]) -> Result<Vec<String>, StoreError> {
+ Ok(match resolve_through(doc, path)? {
+ Some(Resolved::Maps(maps)) => merged_keys(doc, &maps).into_iter().collect(),
+ _ => Vec::new(),
+ })
}
/// Every concurrent value at `path`, newest first; empty if there is none. Where
/// `read_path` picks one (or merges concurrent maps into one), this keeps them apart.
pub(crate) fn read_candidates(
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
path: &[String],
) -> Result<Vec<JsonValue>, StoreError> {
let (leaf, parents) = path.split_last().ok_or(StoreError::NotFound)?;
- let mut maps = vec![automerge::ROOT];
- for segment in parents {
- maps = match resolve(doc, &maps, segment, None)? {
- Some(Resolved::Maps(next)) => next,
- _ => return Ok(Vec::new()),
- };
- }
- candidates(doc, &maps, leaf)?
+ let Some(Resolved::Maps(maps)) = resolve_through(doc, parents)? else {
+ return Ok(Vec::new());
+ };
+ candidates(doc, &maps, leaf.as_str())?
.into_iter()
.map(|(value, id)| match value {
- Value::Scalar(scalar) => scalar_to_json(scalar.into_owned()),
- Value::Object(_) => object_to_json(doc, &id, None),
+ Value::Scalar(scalar) => scalar_to_json(scalar.into_owned(), JsonForm::default()),
+ Value::Object(_) => object_to_json(doc, &id, JsonForm::default(), None),
})
.collect()
}
-/// Writes (replaces) the value at `path`, creating intermediate maps.
+/// Writes the value at `path`, creating intermediate maps: afterwards it reads as
+/// `value`, what was there changed only where it differs (`update_key`). Within a list,
+/// the segment is an index (`list_index`): an item there is overwritten, one at the end
+/// appended; past the end, or anything but an index, names nothing (`NotFound`).
pub(crate) fn write_path(
- doc: &mut AutoCommit,
+ doc: &mut impl Transactable,
path: &[String],
value: &JsonValue,
) -> Result<(), StoreError> {
+ write_val_path(
+ doc,
+ path,
+ &from_json(value)?,
+ Writing::sticky(TimestampFormat::default()),
+ )
+ .map(|_| ())
+}
+
+/// [`write_path`] for a value of any type (`typed::Val`): from typed JSON, or a scalar
+/// of a type JSON doesn't have. Returns the places whose type the write changed.
+pub(crate) fn write_val_path(
+ doc: &mut impl Transactable,
+ path: &[String],
+ value: &Val,
+ mut writing: Writing,
+) -> Result<Vec<Retyped>, StoreError> {
let (leaf, parents) = path.split_last().ok_or(StoreError::NotFound)?;
- let maps = ensure_maps(doc, parents)?;
+ writing.path = parents.to_vec();
+ match parent_for_write(doc, parents)? {
+ Parent::Maps(maps) => update_key(doc, &maps, leaf, value, &mut writing)?,
+ 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 {
+ update_item(doc, &list, index, value, &mut writing)?;
+ } else {
+ write_value(doc, &list, Slot::Index(index), value)?;
+ }
+ }
+ }
+ Ok(writing.retyped)
+}
- // 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)?;
- Ok(())
+/// Which values a write writes as the type of what they are written over (`stuck`).
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub(crate) enum Sticky {
+ /// None: the value says its type (a type's own media type, a cast).
+ No,
+ /// A number without a fraction over a float: typed JSON says every other type
+ /// itself, but not a float's, as JSON numbers don't keep `2.0` apart from `2` in
+ /// every language.
+ Floats,
+ /// Plain JSON, which has fewer types than Automerge: where it is the JSON form of a
+ /// value of the type there (a string that reads as a timestamp, as base64, a number
+ /// without a fraction over a float, an unsigned integer or a counter, a string over
+ /// a text).
+ All,
+}
+
+/// How a write treats the types of what it writes over.
+pub(crate) struct Writing {
+ /// Types are sticky: what the value is written as where it is the JSON form of a
+ /// value of the type there.
+ pub(crate) sticky: Sticky,
+ /// How sticky timestamps are written in JSON (`typed::TimestampFormat::json`).
+ pub(crate) timestamps: TimestampFormat,
+ /// Whether the write may change the type of what it writes over; if not, one that
+ /// would is refused (`Retyping`).
+ pub(crate) retype: bool,
+ path: Vec<String>,
+ retyped: Vec<Retyped>,
}
-/// The merged maps at `path`, creating missing maps on the way.
-fn ensure_maps(doc: &mut AutoCommit, path: &[String]) -> Result<Vec<ObjId>, StoreError> {
- let mut maps = vec![automerge::ROOT];
- for segment in path {
- maps = match resolve(doc, &maps, segment, None)? {
- Some(Resolved::Maps(next)) => next,
- Some(Resolved::Other(..)) => return Err(StoreError::Conflict),
- // A concurrent creation elsewhere is merged on read.
- None => vec![doc.put_object(&maps[0], segment.as_str(), ObjType::Map)?],
+impl Writing {
+ pub(crate) fn sticky(timestamps: TimestampFormat) -> Self {
+ Self::new(Sticky::All, timestamps, true)
+ }
+
+ pub(crate) fn new(sticky: Sticky, timestamps: TimestampFormat, retype: bool) -> Self {
+ Self {
+ sticky,
+ timestamps,
+ retype,
+ path: Vec::new(),
+ retyped: Vec::new(),
+ }
+ }
+
+ /// `kind` is written over `held` at the place at `segment`, if `held` is another
+ /// kind: noted, or with `retype` off, refused.
+ fn retyping(&mut self, segment: &str, held: Kind, kind: Kind) -> Result<(), StoreError> {
+ if held == kind {
+ return Ok(());
+ }
+ let mut path = self.path.clone();
+ path.push(segment.to_owned());
+ let retyped = Retyped {
+ path,
+ from: held,
+ to: kind,
};
+ if !self.retype {
+ return Err(StoreError::Retyping(retyped));
+ }
+ self.retyped.push(retyped);
+ Ok(())
}
- Ok(maps)
}
-/// The resolved value at `path` (the empty path is the root map).
-fn resolve_at(doc: &AutoCommit, path: &[String]) -> Result<Option<Resolved>, StoreError> {
- let mut current = Resolved::Maps(vec![automerge::ROOT]);
- for segment in path {
- let Resolved::Maps(maps) = &current else {
- return Ok(None);
+/// A place whose type a write changed.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) struct Retyped {
+ pub(crate) path: Vec<String>,
+ pub(crate) from: Kind,
+ pub(crate) to: Kind,
+}
+
+impl std::fmt::Display for Retyped {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(
+ f,
+ "{}: {} -> {}",
+ self.path.join("/"),
+ self.from.name(),
+ self.to.name()
+ )
+ }
+}
+
+/// What a value held is stored as.
+fn kind_of(held: &Value<'_>) -> Kind {
+ match held {
+ Value::Object(ObjType::Map | ObjType::Table) => Kind::Map,
+ Value::Object(ObjType::List) => Kind::List,
+ Value::Object(ObjType::Text) => Kind::Text,
+ Value::Scalar(scalar) => Kind::of(scalar),
+ }
+}
+
+/// `value` written as the type of `held`, where it is a JSON form of a value of it
+/// as `sticky` says (`Writing::sticky`); None where it isn't (it is written as it is).
+fn stuck(
+ held: &Value<'_>,
+ value: &Val,
+ sticky: Sticky,
+ timestamps: TimestampFormat,
+) -> Option<Val> {
+ let Val::Scalar(scalar) = value else {
+ return None;
+ };
+ let over_float = matches!(held, Value::Scalar(held) if matches!(held.as_ref(), ScalarValue::F64(_)))
+ && matches!(scalar, ScalarValue::Int(_) | ScalarValue::Uint(_));
+ match sticky {
+ Sticky::No => return None,
+ Sticky::Floats if !over_float => return None,
+ Sticky::Floats | Sticky::All => {}
+ }
+ let held = match held {
+ Value::Object(ObjType::Text) => {
+ return match scalar {
+ ScalarValue::Str(text) => Some(Val::Text(text.to_string())),
+ _ => None,
+ };
+ }
+ Value::Object(_) => return None,
+ Value::Scalar(held) => held.as_ref(),
+ };
+ let stuck = match (held, scalar) {
+ (ScalarValue::Timestamp(_), ScalarValue::Str(text)) => {
+ ScalarValue::Timestamp(timestamps.read(text)?)
+ }
+ (ScalarValue::Timestamp(_), ScalarValue::Int(_) | ScalarValue::F64(_))
+ if matches!(timestamps, TimestampFormat::Unix | TimestampFormat::UnixMs) =>
+ {
+ let number = match scalar {
+ ScalarValue::Int(i) => i.to_string(),
+ ScalarValue::F64(f) => f.to_string(),
+ _ => return None,
+ };
+ ScalarValue::Timestamp(timestamps.read(&number)?)
+ }
+ (ScalarValue::Bytes(_), ScalarValue::Str(text)) => {
+ use base64::{Engine, engine::general_purpose::STANDARD as BASE64};
+ ScalarValue::Bytes(BASE64.decode(text.as_bytes()).ok()?)
+ }
+ (ScalarValue::Uint(_), ScalarValue::Int(i)) => ScalarValue::Uint(u64::try_from(*i).ok()?),
+ (ScalarValue::F64(_), ScalarValue::Int(i)) => ScalarValue::F64(*i as f64),
+ (ScalarValue::F64(_), ScalarValue::Uint(u)) => ScalarValue::F64(*u as f64),
+ (ScalarValue::Counter(_), ScalarValue::Int(i)) => ScalarValue::counter(*i),
+ _ => return None,
+ };
+ Some(Val::Scalar(stuck))
+}
+
+fn from_json(value: &JsonValue) -> Result<Val, StoreError> {
+ Val::from_json(value).map_err(|error| anyhow!(error).into())
+}
+
+// A write makes its path read as the value written, changing only what differs: a map
+// written over a map keeps its keys that stay (and what is inside them), and gets
+// those it lacks and loses those the value doesn't have; a list written over a list
+// does the same item by item, by position; a text written over a text is changed
+// where it differs (a diff, as splices); a scalar equal to the one there isn't written
+// again. So a write of a whole map, concurrent with one inside it elsewhere, keeps the
+// other unless it changes the same key. Where the path holds concurrent values (a
+// conflict), or one of another kind, it is written anew: the write ends the conflict.
+
+/// What updating a place to a value comes to, given what it holds (all its concurrent
+/// values).
+enum Update {
+ /// Nothing: the same scalar is there.
+ Same,
+ /// A map there, the only value: its keys updated.
+ Map(ObjId),
+ /// A list there, the only value: its items updated.
+ List(ObjId),
+ /// A text there, the only value: changed where it differs.
+ Text(ObjId),
+ /// Written anew.
+ Anew,
+}
+
+/// What updating the place at `segment`, holding `holds`, to `value` comes to, with the
+/// value to write there: `value`, or as the type there (`stuck`). A change of type is
+/// noted (`Writing::retyping`).
+fn update_of<'v>(
+ holds: &[(Value<'static>, ObjId)],
+ value: &'v Val,
+ segment: &str,
+ writing: &mut Writing,
+) -> Result<(Update, std::borrow::Cow<'v, Val>), StoreError> {
+ use std::borrow::Cow;
+ let Some((held, _)) = holds.first() else {
+ return Ok((Update::Anew, Cow::Borrowed(value)));
+ };
+ let value = match stuck(held, value, writing.sticky, writing.timestamps) {
+ Some(stuck) => Cow::Owned(stuck),
+ None => Cow::Borrowed(value),
+ };
+ let update = match (holds, &*value) {
+ ([(Value::Object(ObjType::Map), id)], Val::Map(_)) => Update::Map(id.clone()),
+ ([(Value::Object(ObjType::List), id)], Val::List(_)) => Update::List(id.clone()),
+ ([(Value::Object(ObjType::Text), id)], Val::Text(_)) => Update::Text(id.clone()),
+ ([(Value::Scalar(held), _)], Val::Scalar(scalar)) if held.as_ref() == scalar => {
+ Update::Same
+ }
+ _ => {
+ writing.retyping(segment, kind_of(held), value.kind())?;
+ Update::Anew
+ }
+ };
+ Ok((update, value))
+}
+
+/// Updates `key` of the merged maps `maps` to `value`.
+fn update_key(
+ doc: &mut impl Transactable,
+ maps: &[ObjId],
+ key: &str,
+ value: &Val,
+ writing: &mut Writing,
+) -> Result<(), StoreError> {
+ let (update, value) = update_of(&candidates(doc, maps, key)?, value, key, writing)?;
+ writing.path.push(key.to_owned());
+ let done = match update {
+ Update::Same => Ok(()),
+ Update::Map(map) => update_map(doc, &map, &value, writing),
+ Update::List(list) => update_list(doc, &list, &value, writing),
+ Update::Text(text) => update_text(doc, &text, &value),
+ Update::Anew => {
+ // Cleared in every merged map, or an old map would merge into the new value.
+ delete_in_all(doc, maps, key)?;
+ write_value(doc, &maps[0], Slot::Key(key), &value)
+ }
+ };
+ writing.path.pop();
+ done
+}
+
+/// Updates the item at `index` of `list` (which has it) to `value`.
+fn update_item(
+ doc: &mut impl Transactable,
+ list: &ObjId,
+ index: usize,
+ value: &Val,
+ writing: &mut Writing,
+) -> Result<(), StoreError> {
+ let segment = index.to_string();
+ let holds = candidates(doc, std::slice::from_ref(list), index)?;
+ let (update, value) = update_of(&holds, value, &segment, writing)?;
+ writing.path.push(segment);
+ let done = match update {
+ Update::Same => Ok(()),
+ Update::Map(map) => update_map(doc, &map, &value, writing),
+ Update::List(inner) => update_list(doc, &inner, &value, writing),
+ Update::Text(text) => update_text(doc, &text, &value),
+ Update::Anew => write_value(doc, list, Slot::At(index), &value),
+ };
+ writing.path.pop();
+ done
+}
+
+fn update_map(
+ doc: &mut impl Transactable,
+ map: &ObjId,
+ value: &Val,
+ writing: &mut Writing,
+) -> Result<(), StoreError> {
+ let Val::Map(entries) = value else {
+ unreachable!("a map is updated to a map");
+ };
+ let maps = std::slice::from_ref(map);
+ // The keys it loses first, then those it keeps or gets, each in key order.
+ for key in doc.keys(map).collect::<Vec<_>>() {
+ if !entries.iter().any(|(kept, _)| *kept == key) {
+ doc.delete(map, key.as_str())?;
+ }
+ }
+ for (key, value) in entries {
+ update_key(doc, maps, key, value, writing)?;
+ }
+ Ok(())
+}
+
+fn update_list(
+ doc: &mut impl Transactable,
+ list: &ObjId,
+ value: &Val,
+ writing: &mut Writing,
+) -> Result<(), StoreError> {
+ let Val::List(items) = value else {
+ unreachable!("a list is updated to a list");
+ };
+ let length = doc.length(list);
+ for (index, item) in items.iter().enumerate() {
+ if index < length {
+ update_item(doc, list, index, item, writing)?;
+ } else {
+ write_value(doc, list, Slot::Index(index), item)?;
+ }
+ }
+ for index in (items.len()..length).rev() {
+ doc.delete(list, index)?;
+ }
+ Ok(())
+}
+
+fn update_text(doc: &mut impl Transactable, text: &ObjId, value: &Val) -> Result<(), StoreError> {
+ let Val::Text(new) = value else {
+ unreachable!("a text is updated to a text");
+ };
+ doc.update_text(text, new)?;
+ Ok(())
+}
+
+/// 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 impl Transactable, 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)?
+ }
};
- match resolve(doc, maps, segment, None)? {
- Some(next) => current = next,
- None => return Ok(None),
+ 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)
+}
+
+/// Adds `by` to the counter at `path`, creating one with `by` where there is nothing
+/// (in a map: a list's items are only incremented); returns its value then. Increments
+/// of one counter on several nodes add up, where writes of numbers would leave one.
+/// Anything else there (the newest of concurrent values, as a read resolves them) is
+/// `NotACounter`.
+pub(crate) fn increment_path(
+ doc: &mut impl Transactable,
+ path: &[String],
+ by: i64,
+) -> Result<i64, StoreError> {
+ let (leaf, parents) = path.split_last().ok_or(StoreError::NotFound)?;
+ let (parent, prop): (ObjId, Prop) = match parent_for_write(doc, parents)? {
+ Parent::Maps(maps) => {
+ let holds = candidates(doc, &maps, leaf)?;
+ if holds.is_empty() {
+ doc.put(&maps[0], leaf.as_str(), ScalarValue::counter(by))?;
+ return Ok(by);
+ }
+ // The map that holds the newest value.
+ let newest = &holds[0].1;
+ let map = maps
+ .iter()
+ .find(|map| {
+ doc.get_all(*map, leaf.as_str())
+ .is_ok_and(|all| all.iter().any(|(_, id)| id == newest))
+ })
+ .cloned()
+ .ok_or(StoreError::NotFound)?;
+ (map, Prop::Map(leaf.clone()))
}
+ Parent::List(list) => {
+ let index = list_index(leaf).ok_or(StoreError::NotFound)?;
+ if index >= doc.length(&list) {
+ return Err(StoreError::NotFound);
+ }
+ (list, Prop::Seq(index))
+ }
+ };
+ counter_at(doc, &parent, prop.clone())?;
+ doc.increment(&parent, prop.clone(), by)?;
+ counter_at(doc, &parent, prop)
+}
+
+/// The value of the counter `prop` of `parent` holds (the newest of its values).
+fn counter_at(doc: &impl ReadDoc, parent: &ObjId, prop: Prop) -> Result<i64, StoreError> {
+ match doc.get(parent, prop)? {
+ Some((Value::Scalar(scalar), _)) => match scalar.as_ref() {
+ ScalarValue::Counter(counter) => Ok(i64::from(counter)),
+ _ => Err(StoreError::NotACounter),
+ },
+ _ => Err(StoreError::NotACounter),
}
- Ok(Some(current))
+}
+
+/// Casts what is at `path` (the newest of concurrent values, as a read resolves them) to
+/// `to` (`typed::cast`, timestamps to and from strings in `timestamps`), written as a
+/// write of the cast value would be (`write_val_path`); returns where that changed the
+/// type. Already `to`: nothing changes. Nothing there: `NotFound`; no cast possible:
+/// `NotCastable`.
+pub(crate) fn cast_path(
+ doc: &mut impl Transactable,
+ path: &[String],
+ to: Kind,
+ timestamps: TimestampFormat,
+) -> Result<Vec<Retyped>, StoreError> {
+ let held = read_held(doc, path)?.ok_or(StoreError::NotFound)?;
+ if held.kind == to {
+ return Ok(Vec::new());
+ }
+ let not_castable = |why: String| StoreError::NotCastable {
+ from: held.kind,
+ to,
+ why,
+ };
+ let value = held
+ .value
+ .as_ref()
+ .ok_or_else(|| not_castable(format!("{} is cast to nothing", held.kind.name())))?;
+ let cast = typed::cast(held.kind, value, to, timestamps).map_err(not_castable)?;
+ write_val_path(doc, path, &cast, Writing::new(Sticky::No, timestamps, true))
+}
+
+/// 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`.
+#[cfg(test)]
+pub(crate) fn insert_path(
+ doc: &mut impl Transactable,
+ path: &[String],
+ value: &JsonValue,
+) -> Result<(), StoreError> {
+ insert_val_path(doc, path, &from_json(value)?)
+}
+
+/// [`insert_path`] for a value of any type (`typed::Val`).
+pub(crate) fn insert_val_path(
+ doc: &mut impl Transactable,
+ path: &[String],
+ value: &Val,
+) -> Result<(), StoreError> {
+ let (list, index) = insertion(doc, path)?;
+ write_value(doc, &list, Slot::Index(index), value)
+}
+
+/// The list an insert at `path` goes into, and where (`insert_path`).
+fn insertion(doc: &impl ReadDoc, path: &[String]) -> Result<(ObjId, usize), 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);
+ if index > length {
+ return Err(StoreError::PastTheEnd { index, length });
+ }
+ Ok((list, index))
}
/// Makes `dst` hold at `path` what `src`'s merged view holds there: a type-preserving
/// copy (see `materialize_into`) if it exists, a delete otherwise. Replaces the whole
/// subtree at `path`; the path must not be empty.
pub(crate) fn copy_path(
- src: &AutoCommit,
- dst: &mut AutoCommit,
+ src: &impl ReadDoc,
+ dst: &mut impl Transactable,
path: &[String],
) -> Result<(), StoreError> {
copy_path_to(src, path, dst, path)
@@ -327,21 +1206,25 @@ pub(crate) fn copy_path(
/// Like [`copy_path`], but puts what `src` holds at `from` at `to` in `dst`.
pub(crate) fn copy_path_to(
- src: &AutoCommit,
+ src: &impl ReadDoc,
from: &[String],
- dst: &mut AutoCommit,
+ dst: &mut impl Transactable,
to: &[String],
) -> Result<(), StoreError> {
let (leaf, parents) = to.split_last().ok_or(StoreError::NotFound)?;
- let Some(resolved) = resolve_at(src, from)? else {
+ let Some(resolved) = resolve_through(src, from)? else {
return match delete_path(dst, to, false) {
Ok(()) | Err(StoreError::NotFound) => Ok(()),
Err(error) => Err(error),
};
};
- let maps = ensure_maps(dst, parents)?;
+ // Into a map: what is copied are map entries (delta replay names nothing inside a
+ // list: a list is copied whole).
+ let Parent::Maps(maps) = parent_for_write(dst, parents)? else {
+ return Err(StoreError::Conflict);
+ };
delete_in_all(dst, &maps, leaf)?;
let mut trace = from.to_vec();
copy_resolved(
@@ -355,37 +1238,54 @@ pub(crate) fn copy_path_to(
)
}
-/// Deletes the value at `path`, optionally pruning ancestors that become empty.
+/// Deletes the value at `path`, through lists too, where a segment is an index
+/// (`list_index`; the items after it move down one). With `prune`, the maps above it
+/// that it leaves empty go too, up to (not including) the root or a list.
pub(crate) fn delete_path(
- doc: &mut AutoCommit,
+ doc: &mut impl Transactable,
path: &[String],
prune: bool,
) -> Result<(), StoreError> {
let (leaf, parents) = path.split_last().ok_or(StoreError::NotFound)?;
- // levels[d] = merged maps at path[..d]
- let mut levels = vec![vec![automerge::ROOT]];
+ // levels[d] = what path[..d] resolves to
+ let mut levels = vec![Resolved::Maps(vec![automerge::ROOT])];
for segment in parents {
- let next = match resolve(doc, levels.last().expect("non-empty"), segment, None)? {
- Some(Resolved::Maps(maps)) => maps,
- _ => return Err(StoreError::NotFound),
- };
+ let next = step(doc, levels.last().expect("non-empty"), segment, None)?
+ .ok_or(StoreError::NotFound)?;
levels.push(next);
}
- let maps = levels.last().expect("non-empty");
- if resolve(doc, maps, leaf, None)?.is_none() {
- return Err(StoreError::NotFound);
+ match levels.last().expect("non-empty") {
+ Resolved::Maps(maps) => {
+ if resolve(doc, maps, leaf, None)?.is_none() {
+ return Err(StoreError::NotFound);
+ }
+ delete_in_all(doc, maps, leaf)?;
+ }
+ 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)?;
+ return Ok(());
+ }
+ Resolved::Other(..) => return Err(StoreError::NotFound),
}
- delete_in_all(doc, maps, leaf)?;
if prune {
- // Never prune the root (depth 0).
+ // Never prune the root (depth 0), nor through a list.
for depth in (1..levels.len()).rev() {
- if !merged_keys(doc, &levels[depth]).is_empty() {
+ let (Resolved::Maps(above), Resolved::Maps(maps)) =
+ (&levels[depth - 1], &levels[depth])
+ else {
+ break;
+ };
+ if !merged_keys(doc, maps).is_empty() {
break;
}
- delete_in_all(doc, &levels[depth - 1], &path[depth - 1])?;
+ delete_in_all(doc, above, &path[depth - 1])?;
}
}
@@ -406,8 +1306,8 @@ pub(crate) fn delete_path(
/// `skip` sees the path of every map entry and list element (list indices as decimal
/// strings); returning true leaves that subtree out.
pub(crate) fn materialize_into(
- src: &AutoCommit,
- dst: &mut AutoCommit,
+ src: &impl ReadDoc,
+ dst: &mut impl Transactable,
skip: &dyn Fn(&[String]) -> bool,
) -> Result<(), StoreError> {
let mut path = Vec::new();
@@ -422,9 +1322,9 @@ pub(crate) fn materialize_into(
}
fn copy_maps(
- src: &AutoCommit,
+ src: &impl ReadDoc,
maps: &[ObjId],
- dst: &mut AutoCommit,
+ dst: &mut impl Transactable,
target: &ObjId,
path: &mut Vec<String>,
skip: &dyn Fn(&[String]) -> bool,
@@ -443,9 +1343,9 @@ fn copy_maps(
}
fn copy_resolved(
- src: &AutoCommit,
+ src: &impl ReadDoc,
resolved: &Resolved,
- dst: &mut AutoCommit,
+ dst: &mut impl Transactable,
parent: &ObjId,
slot: Slot,
path: &mut Vec<String>,
@@ -473,10 +1373,10 @@ fn copy_resolved(
#[allow(clippy::too_many_arguments)]
fn copy_object(
- src: &AutoCommit,
+ src: &impl ReadDoc,
obj_type: ObjType,
id: &ObjId,
- dst: &mut AutoCommit,
+ dst: &mut impl Transactable,
parent: &ObjId,
slot: Slot,
path: &mut Vec<String>,
@@ -527,10 +1427,12 @@ enum Slot<'a> {
Key(&'a str),
/// An index in a list. The value is inserted here, not overwritten.
Index(usize),
+ /// An index in a list whose item is overwritten.
+ At(usize),
}
fn put_object(
- doc: &mut AutoCommit,
+ doc: &mut impl Transactable,
parent: &ObjId,
slot: Slot,
obj_type: ObjType,
@@ -538,11 +1440,12 @@ fn put_object(
Ok(match slot {
Slot::Key(key) => doc.put_object(parent, key, obj_type)?,
Slot::Index(index) => doc.insert_object(parent, index, obj_type)?,
+ Slot::At(index) => doc.put_object(parent, index, obj_type)?,
})
}
fn put_scalar(
- doc: &mut AutoCommit,
+ doc: &mut impl Transactable,
parent: &ObjId,
slot: Slot,
value: impl Into<ScalarValue>,
@@ -550,72 +1453,59 @@ fn put_scalar(
match slot {
Slot::Key(key) => doc.put(parent, key, value)?,
Slot::Index(index) => doc.insert(parent, index, value)?,
+ Slot::At(index) => doc.put(parent, index, value)?,
}
Ok(())
}
fn write_value(
- doc: &mut AutoCommit,
+ doc: &mut impl Transactable,
parent: &ObjId,
slot: Slot,
- value: &JsonValue,
+ value: &Val,
) -> Result<(), StoreError> {
match value {
- JsonValue::Object(object) => {
- let id = put_object(doc, parent, slot, ObjType::Map)?;
- for (child_key, child_value) in object {
- write_value(doc, &id, Slot::Key(child_key), child_value)?;
- }
- }
- JsonValue::Array(items) => {
- let id = put_object(doc, parent, slot, ObjType::List)?;
- for (index, item) in items.iter().enumerate() {
- write_value(doc, &id, Slot::Index(index), item)?;
- }
- }
- JsonValue::String(value) => put_scalar(doc, parent, slot, value.as_str())?,
- JsonValue::Bool(value) => put_scalar(doc, parent, slot, *value)?,
- JsonValue::Number(value) => {
- if let Some(value) = value.as_i64() {
- put_scalar(doc, parent, slot, value)?;
- } else if let Some(value) = value.as_u64() {
- put_scalar(doc, parent, slot, value)?;
- } else if let Some(value) = value.as_f64() {
- put_scalar(doc, parent, slot, value)?;
- } else {
- return Err(anyhow!("Unsupported JSON number").into());
- }
+ Val::Scalar(scalar) => put_scalar(doc, parent, slot, scalar.clone()),
+ tree => {
+ // A new tree in one go, not an operation at a time.
+ let tree = hydrated(tree, doc.text_encoding());
+ let (prop, insert): (Prop, bool) = match slot {
+ Slot::Key(key) => (key.into(), false),
+ Slot::Index(index) => (index.into(), true),
+ Slot::At(index) => (index.into(), false),
+ };
+ doc.batch_create_object(parent, prop, &tree, insert)?;
+ Ok(())
}
- JsonValue::Null => put_scalar(doc, parent, slot, ScalarValue::Null)?,
}
-
- Ok(())
}
-fn json_to_automerge(
- doc: &mut AutoCommit,
- parent: &ObjId,
- key: &str,
- value: &JsonValue,
-) -> Result<(), StoreError> {
- write_value(doc, parent, Slot::Key(key), value)
+/// `value` as Automerge holds it.
+fn hydrated(value: &Val, encoding: automerge::TextEncoding) -> automerge::hydrate::Value {
+ use automerge::hydrate;
+ match value {
+ Val::Map(entries) => hydrate::Value::Map(hydrate::Map::from(
+ entries
+ .iter()
+ .map(|(key, value)| (key.clone(), hydrated(value, encoding)))
+ .collect::<std::collections::HashMap<_, _>>(),
+ )),
+ Val::List(items) => hydrate::Value::from(
+ items
+ .iter()
+ .map(|item| hydrated(item, encoding))
+ .collect::<Vec<_>>(),
+ ),
+ Val::Text(text) => hydrate::Value::text(encoding, text),
+ Val::Scalar(scalar) => hydrate::Value::Scalar(scalar.clone()),
+ }
}
-fn scalar_to_json(scalar: ScalarValue) -> Result<JsonValue, StoreError> {
- match scalar {
- ScalarValue::Null => Ok(JsonValue::Null),
- ScalarValue::Boolean(b) => Ok(JsonValue::Bool(b)),
- ScalarValue::Int(i) => Ok(JsonValue::Number(i.into())),
- ScalarValue::Uint(u) => Ok(JsonValue::Number(u.into())),
- ScalarValue::F64(f) => serde_json::Number::from_f64(f)
- .map(JsonValue::Number)
- .ok_or(anyhow!("Non-finite float cannot be represented as JSON").into()),
- ScalarValue::Str(s) => Ok(JsonValue::String(s.to_string())),
- ScalarValue::Bytes(b) => Ok(JsonValue::String(BASE64.encode(b))),
- ScalarValue::Counter(c) => Ok(JsonValue::Number(i64::from(c).into())),
- ScalarValue::Timestamp(t) => Ok(JsonValue::Number(t.into())),
- ScalarValue::Unknown { .. } => Err(anyhow!("Unsupported Automerge scalar type").into()),
- }
+fn scalar_to_json(scalar: ScalarValue, form: JsonForm) -> Result<JsonValue, StoreError> {
+ typed::scalar_to_json(&scalar, form).ok_or_else(|| match scalar {
+ ScalarValue::F64(_) => anyhow!("Non-finite float cannot be represented as JSON").into(),
+ _ => anyhow!("Unsupported Automerge scalar type").into(),
+ })
}
// --- conflict log ------------------------------------------------------------
@@ -655,6 +1545,8 @@ struct ConflictLog {
want_values: bool,
/// Currently walking the ancestors of the requested path.
in_ancestors: bool,
+ /// How candidate values are shown.
+ form: JsonForm,
}
fn op_id_string(id: &ObjId) -> String {
@@ -664,17 +1556,22 @@ fn op_id_string(id: &ObjId) -> String {
}
}
-fn value_to_json(doc: &AutoCommit, value: &Value<'_>, id: &ObjId) -> Result<JsonValue, StoreError> {
+fn value_to_json(
+ doc: &impl ReadDoc,
+ value: &Value<'_>,
+ id: &ObjId,
+ form: JsonForm,
+) -> Result<JsonValue, StoreError> {
match value {
- Value::Scalar(scalar) => Ok(scalar_to_json(scalar.clone().into_owned())?),
- Value::Object(_) => object_to_json(doc, id, None),
+ Value::Scalar(scalar) => Ok(scalar_to_json(scalar.clone().into_owned(), form)?),
+ Value::Object(_) => object_to_json(doc, id, form, None),
}
}
impl ConflictLog {
fn record(
&mut self,
- doc: &AutoCommit,
+ doc: &impl ReadDoc,
key: &str,
all: &[(Value<'static>, ObjId)],
merged: bool,
@@ -694,7 +1591,7 @@ impl ConflictLog {
op_id: op_id_string(id),
selected,
value: if with_values {
- Some(value_to_json(doc, value, id)?)
+ Some(value_to_json(doc, value, id, self.form)?)
} else {
None
},
@@ -734,3 +1631,174 @@ fn nested<T>(
}
out
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use crate::document::testing::try_change;
+ use serde_json::json;
+
+ fn path(at: &str) -> Vec<String> {
+ at.split('/').map(str::to_owned).collect()
+ }
+
+ #[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| {
+ write_path(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.
+ try_change(&mut doc, |doc| {
+ write_path(doc, &path("list/0"), &json!("a"))
+ })
+ .unwrap();
+ try_change(&mut doc, |doc| {
+ write_path(doc, &path("list/3"), &json!("e"))
+ })
+ .unwrap();
+ try_change(&mut doc, |doc| {
+ write_path(doc, &path("list/1/k"), &json!(2))
+ })
+ .unwrap();
+ assert!(matches!(
+ try_change(&mut doc, |doc| write_path(doc, &path("list/9"), &json!(0))),
+ Err(StoreError::NotFound)
+ ));
+ assert_eq!(
+ read_path(&doc, &path("list")).unwrap(),
+ Some(json!(["a", {"k": 2}, "d", "e"]))
+ );
+ try_change(&mut doc, |doc| delete_path(doc, &path("list/2"), false)).unwrap();
+ assert_eq!(
+ read_path(&doc, &path("list")).unwrap(),
+ Some(json!(["a", {"k": 2}, "e"]))
+ );
+ assert_eq!(
+ read_shallow(&doc, &path("list")).unwrap().unwrap()["entries"]["1"]["type"],
+ json!("map")
+ );
+ }
+
+ #[test]
+ fn negative_indexes_count_from_the_end() {
+ let mut doc = Automerge::new();
+ try_change(&mut doc, |doc| {
+ write_path(doc, &path("list"), &json!(["a", "b"]))
+ })
+ .unwrap();
+ try_change(&mut doc, |doc| {
+ write_path(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 = Automerge::new();
+ try_change(&mut doc, |doc| {
+ write_path(doc, &path("list"), &json!(["b", "d"]))
+ })
+ .unwrap();
+ try_change(&mut doc, |doc| {
+ insert_path(doc, &path("list/0"), &json!("a"))
+ })
+ .unwrap();
+ try_change(&mut doc, |doc| {
+ insert_path(doc, &path("list/2"), &json!("c"))
+ })
+ .unwrap();
+ try_change(&mut doc, |doc| {
+ insert_path(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!(
+ try_change(&mut doc, |doc| insert_path(doc, &path("list/6"), &json!(1))),
+ Err(StoreError::PastTheEnd {
+ index: 6,
+ length: 5
+ })
+ ));
+ try_change(&mut doc, |doc| {
+ write_path(doc, &path("map"), &json!({"k": 1}))
+ })
+ .unwrap();
+ assert!(matches!(
+ try_change(&mut doc, |doc| insert_path(doc, &path("map/0"), &json!(1))),
+ Err(StoreError::NotAList)
+ ));
+ assert!(matches!(
+ try_change(&mut doc, |doc| insert_path(
+ doc,
+ &path("nothing/0"),
+ &json!(1)
+ )),
+ Err(StoreError::NotFound)
+ ));
+ }
+}