path: root/src/document/inspect.rs

//! 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()));
    }
}