diff options
| -rw-r--r-- | src/document/bench.rs | 37 | ||||
| -rw-r--r-- | src/document/inspect.rs | 263 | ||||
| -rw-r--r-- | src/document/mod.rs | 1 |
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(¬es, 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(¬es, 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; |