aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/document/bench.rs37
-rw-r--r--src/document/inspect.rs263
-rw-r--r--src/document/mod.rs1
3 files changed, 300 insertions, 1 deletions
diff --git a/src/document/bench.rs b/src/document/bench.rs
index 1bb13ee..bc1f6fa 100644
--- a/src/document/bench.rs
+++ b/src/document/bench.rs
@@ -25,7 +25,10 @@
//! the change left it (`store::changed_by`, so every node finds the same paths). Against
//! receiving a sync message of many changes and loading a document of many changes, as
//! above, each change writing a value three levels deep; and decoding alone, the part
-//! that grows with the change rather than with its objects.
+//! that grows with the change rather than with its objects. Decoded as the document
+//! rebuilds them, and from the bytes they came as; and inspected before they are
+//! applied (`inspect::Inspector`), their objects made among them or looked up in the
+//! document, each once.
use std::time::{Duration, Instant};
@@ -509,6 +512,36 @@ fn path_costs(workload: &str, base: Duration, doc: &Document) {
}
started.elapsed()
});
+ // Before they are applied (`inspect::Inspector`): those of a sync message to a node
+ // that has none of them, their objects made among them; those of a document loaded,
+ // looked up in it.
+ let inspected = median(3, || {
+ let empty = Document::new();
+ let started = Instant::now();
+ let changes: Vec<automerge::ExpandedChange> = raw
+ .iter()
+ .map(|(_, bytes)| {
+ automerge::Change::from_bytes(bytes.clone())
+ .expect("change")
+ .decode()
+ })
+ .collect();
+ std::hint::black_box(super::inspect::Inspector::new(&empty).paths(&changes));
+ started.elapsed()
+ });
+ let looked_up = median(3, || {
+ let started = Instant::now();
+ let changes: Vec<automerge::ExpandedChange> = raw
+ .iter()
+ .map(|(_, bytes)| {
+ automerge::Change::from_bytes(bytes.clone())
+ .expect("change")
+ .decode()
+ })
+ .collect();
+ std::hint::black_box(super::inspect::Inspector::new(doc).paths(&changes));
+ started.elapsed()
+ });
report_signatures(
workload,
base,
@@ -517,6 +550,8 @@ fn path_costs(workload: &str, base: Duration, doc: &Document) {
("paths", paths),
("from bytes: decoding", decode_bytes),
("paths", paths_bytes),
+ ("inspected, made among them", inspected),
+ ("looked up", looked_up),
],
);
}
diff --git a/src/document/inspect.rs b/src/document/inspect.rs
new file mode 100644
index 0000000..b39e938
--- /dev/null
+++ b/src/document/inspect.rs
@@ -0,0 +1,263 @@
+//! What changes touch, read from their operations before they are applied: the store
+//! paths each change writes, so a node can judge it by rules by path first
+//! (`future-work.md`, Write protection by checking changes).
+//!
+//! Every node must find the same paths for a change, whatever else it holds, or nodes
+//! would judge it differently. So a path is an object's place as it was made, which
+//! never changes: an Automerge object is made at a key of its parent and stays there.
+//! A list's items move as others are inserted before them, so a path stops at the
+//! first list or text on the way (`store::InLists::Whole`): anything inside one touches
+//! the list. An object neither in the document nor made by the changes inspected (the
+//! change lacks a dependency, and can't be applied anyway) is placed at the root, which
+//! is within every path's reach.
+
+// Judging changes on receipt is what uses it; until then, the benchmark and tests.
+#![cfg_attr(not(test), allow(dead_code))]
+
+use std::collections::{BTreeSet, HashMap};
+
+use automerge::legacy::{Key, ObjectId, OpId, OpType};
+use automerge::{ExpandedChange, Prop};
+
+use super::{Document, ReadDoc};
+
+/// A store path, by segments.
+pub(crate) type Path = Vec<String>;
+
+/// Where an object is: its path, cut at the first list or text on the way
+/// (`in_list`: it is inside one, or is one).
+#[derive(Debug, Clone, PartialEq, Eq)]
+struct Place {
+ path: Path,
+ in_list: bool,
+}
+
+impl Place {
+ fn root() -> Self {
+ Place {
+ path: Vec::new(),
+ in_list: false,
+ }
+ }
+
+ /// What an operation at `key` of this object touches.
+ fn touched(&self, key: &Key) -> Path {
+ let mut path = self.path.clone();
+ if let (Key::Map(key), false) = (key, self.in_list) {
+ path.push(key.to_string());
+ }
+ path
+ }
+
+ /// The place of an object made at `key` of this object.
+ fn child(&self, key: &Key) -> Place {
+ match key {
+ Key::Map(_) if !self.in_list => Place {
+ path: self.touched(key),
+ in_list: false,
+ },
+ _ => Place {
+ path: self.path.clone(),
+ in_list: true,
+ },
+ }
+ }
+}
+
+/// Finds the paths changes touch in `doc`, with the places of the objects it looked up
+/// kept for the next changes.
+pub(crate) struct Inspector<'a> {
+ doc: &'a Document,
+ places: HashMap<ObjectId, Place>,
+}
+
+impl<'a> Inspector<'a> {
+ pub(crate) fn new(doc: &'a Document) -> Self {
+ Self {
+ doc,
+ places: HashMap::new(),
+ }
+ }
+
+ /// The paths each of `changes` touches, in their order. The objects they make are
+ /// placed first, whatever their order, so a change is judged the same however the
+ /// changes came.
+ pub(crate) fn paths(&mut self, changes: &[ExpandedChange]) -> Vec<BTreeSet<Path>> {
+ // The objects made, by the operation that made them: placed as their parents
+ // are, until no more can be (a parent made later in the list, placed in a later
+ // round).
+ let mut made: Vec<(ObjectId, &ObjectId, &Key)> = Vec::new();
+ for change in changes {
+ for (index, op) in change.operations.iter().enumerate() {
+ if let OpType::Make(_) = op.action {
+ let id = OpId(
+ change.start_op.get() + index as u64,
+ change.actor_id.clone(),
+ );
+ made.push((ObjectId::Id(id), &op.obj, &op.key));
+ }
+ }
+ }
+ loop {
+ let before = made.len();
+ made.retain(|(id, parent, key)| match self.known(parent) {
+ Some(parent) => {
+ let child = parent.child(key);
+ self.places.insert(id.clone(), child);
+ false
+ }
+ None => true,
+ });
+ if made.is_empty() || made.len() == before {
+ break;
+ }
+ }
+ changes
+ .iter()
+ .map(|change| {
+ change
+ .operations
+ .iter()
+ .map(|op| match self.known(&op.obj) {
+ Some(place) => place.touched(&op.key),
+ // Nowhere to be found: within every path's reach.
+ None => Vec::new(),
+ })
+ .collect()
+ })
+ .collect()
+ }
+
+ /// Where `object` is: made by a change inspected, or in the document; None if
+ /// neither.
+ fn known(&mut self, object: &ObjectId) -> Option<Place> {
+ if let ObjectId::Root = object {
+ return Some(Place::root());
+ }
+ if let Some(place) = self.places.get(object) {
+ return Some(place.clone());
+ }
+ let ObjectId::Id(id) = object else {
+ return None;
+ };
+ let id = self.doc.import_obj(&format!("{}@{}", id.0, id.1)).ok()?;
+ let mut place = Place::root();
+ for (_, prop) in self.doc.parents(&id).ok()?.path() {
+ match prop {
+ Prop::Map(key) => place.path.push(key),
+ Prop::Seq(_) => {
+ place.in_list = true;
+ break;
+ }
+ }
+ }
+ // A list or text itself: what is in it is in a list.
+ if !place.in_list
+ && let Ok(kind) = self.doc.object_type(&id)
+ {
+ place.in_list = matches!(kind, automerge::ObjType::List | automerge::ObjType::Text);
+ }
+ self.places.insert(object.clone(), place.clone());
+ Some(place)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use crate::document::store;
+ use crate::document::testing::change;
+ use automerge::transaction::Transactable;
+ use automerge::{ObjType, ROOT};
+ use serde_json::json;
+
+ fn path(segments: &[&str]) -> Path {
+ segments.iter().map(|s| (*s).to_owned()).collect()
+ }
+
+ fn decoded(doc: &Document, since: &[automerge::ChangeHash]) -> Vec<ExpandedChange> {
+ doc.get_changes(since)
+ .iter()
+ .map(|change| change.decode())
+ .collect()
+ }
+
+ /// Paths of maps made in the changes inspected, and of objects in the document:
+ /// the same either way.
+ #[test]
+ fn maps_made_now_and_before() {
+ let mut theirs = Document::new();
+ change(&mut theirs, |doc| {
+ store::write_path(doc, &path(&["servers", "eu", "cpu"]), &json!(1)).unwrap();
+ });
+ let first = theirs.get_heads();
+ change(&mut theirs, |doc| {
+ store::write_path(doc, &path(&["servers", "eu", "mem"]), &json!(2)).unwrap();
+ store::write_path(doc, &path(&["config", "mode"]), &json!("fast")).unwrap();
+ });
+ // All made in the changes inspected.
+ let empty = Document::new();
+ let all = Inspector::new(&empty).paths(&decoded(&theirs, &[]));
+ assert!(all[0].contains(&path(&["servers", "eu", "cpu"])));
+ assert!(all[1].contains(&path(&["servers", "eu", "mem"])));
+ assert!(all[1].contains(&path(&["config", "mode"])));
+ // The first in the document already: its objects looked up there.
+ let mut ours = Document::new();
+ ours.load_incremental(&theirs.save_after(&[])).unwrap();
+ let later = Inspector::new(&ours).paths(&decoded(&theirs, &first));
+ assert_eq!(later[0], all[1]);
+ // In any order: the same.
+ let mut reversed = decoded(&theirs, &[]);
+ reversed.reverse();
+ let mut backwards = Inspector::new(&empty).paths(&reversed);
+ backwards.reverse();
+ assert_eq!(backwards, all);
+ }
+
+ /// Inside a list or text, a path stops at it: items move.
+ #[test]
+ fn lists_and_text_stop_paths() {
+ let mut doc = Document::new();
+ change(&mut doc, |doc| {
+ let queue = doc.put_object(ROOT, "queue", ObjType::List).unwrap();
+ let job = doc.insert_object(&queue, 0, ObjType::Map).unwrap();
+ doc.put(&job, "name", "first").unwrap();
+ let notes = doc.put_object(ROOT, "notes", ObjType::Text).unwrap();
+ doc.splice_text(&notes, 0, 0, "hello").unwrap();
+ });
+ let empty = Document::new();
+ let paths = Inspector::new(&empty).paths(&decoded(&doc, &[]));
+ let expected: BTreeSet<Path> = [path(&["queue"]), path(&["notes"])].into();
+ assert_eq!(paths[0], expected);
+ // Looked up in the document: the same.
+ let heads = doc.get_heads();
+ change(&mut doc, |doc| {
+ let (_, queue) = doc.get(ROOT, "queue").unwrap().unwrap();
+ let (_, job) = doc.get(&queue, 0).unwrap().unwrap();
+ doc.put(&job, "name", "second").unwrap();
+ let (_, notes) = doc.get(ROOT, "notes").unwrap().unwrap();
+ doc.splice_text(&notes, 5, 0, "!").unwrap();
+ });
+ let mut ours = Document::new();
+ ours.load_incremental(&doc.save_after(&[])).unwrap();
+ let paths = Inspector::new(&ours).paths(&decoded(&doc, &heads));
+ assert_eq!(paths[0], expected);
+ }
+
+ /// An object nowhere to be found: the root, within every path's reach.
+ #[test]
+ fn an_unknown_object_is_at_the_root() {
+ let mut theirs = Document::new();
+ change(&mut theirs, |doc| {
+ store::write_path(doc, &path(&["a", "b"]), &json!(1)).unwrap();
+ });
+ let heads = theirs.get_heads();
+ change(&mut theirs, |doc| {
+ store::write_path(doc, &path(&["a", "c"]), &json!(2)).unwrap();
+ });
+ // Without the first change: the map `a` is made there.
+ let empty = Document::new();
+ let paths = Inspector::new(&empty).paths(&decoded(&theirs, &heads));
+ assert!(paths[0].contains(&Vec::new()));
+ }
+}
diff --git a/src/document/mod.rs b/src/document/mod.rs
index 19d1110..7f59942 100644
--- a/src/document/mod.rs
+++ b/src/document/mod.rs
@@ -41,6 +41,7 @@ pub(crate) mod at;
pub(crate) mod bench;
pub(crate) mod changes;
pub(crate) mod file;
+pub(crate) mod inspect;
pub(crate) mod lock;
pub(crate) mod meta;
pub(crate) mod replica;