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
//! (`access::rules`).
//!
//! 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.

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>;

/// An operation, as rules see it (`Inspector::ops`): where, and what it does there.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct Op {
    /// What it touches.
    pub(crate) path: Path,
    pub(crate) action: Action,
}

/// What an operation does at its path.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Action {
    /// Makes a map there.
    MakeMap,
    /// Puts a string there.
    PutString(String),
    /// Deletes what is there.
    Delete,
    /// Changes what is there, a list or text it is in (`Place::in_list`).
    Within,
    /// In an object nowhere to be found (`Inspector::known`).
    Nowhere,
    /// Anything else there: makes another object, puts another scalar, increments.
    Other,
}

/// 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,
            },
        }
    }
}

/// Whether any of `changes` does anything at a map key `key`: a cheap look, without
/// placing anything, for whether they may write the policy (`access::screen`).
pub(crate) fn touch_key(changes: &[ExpandedChange], key: &str) -> bool {
    changes.iter().any(|change| {
        change
            .operations
            .iter()
            .any(|op| matches!(&op.key, Key::Map(name) if name.as_str() == key))
    })
}

/// Where a write at `path` in `doc` is, as rules see it (`Inspector`): placed by the
/// same rule (`Place::child`), so cut after the first list or text on the way, which
/// what is inside one touches. Where `doc` holds nothing (or a scalar) on the way, the
/// rest is as asked: the write makes maps there. For the API's checks, so they and the
/// rules judge the same path.
pub(crate) fn placed(doc: &Document, path: &[String]) -> Path {
    let mut place = Place::root();
    let mut object = automerge::ROOT;
    for (index, key) in path.iter().enumerate() {
        if place.in_list {
            break;
        }
        place = place.child(&Key::Map(key.as_str().into()));
        match doc.get(&object, key.as_str()) {
            Ok(Some((automerge::Value::Object(kind), id))) => {
                place.in_list = matches!(kind, automerge::ObjType::List | automerge::ObjType::Text);
                object = id;
            }
            _ => {
                place.path.extend(path[index + 1..].iter().cloned());
                break;
            }
        }
    }
    place.path
}

/// 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 (`ops`): for the benchmark
    /// and tests.
    #[cfg_attr(not(test), allow(dead_code))]
    pub(crate) fn paths(&mut self, changes: &[ExpandedChange]) -> Vec<BTreeSet<Path>> {
        self.ops(changes)
            .into_iter()
            .map(|ops| ops.into_iter().map(|op| op.path).collect())
            .collect()
    }

    /// The operations of each of `changes`, in their order, as rules see them. The
    /// objects they make are placed first, whatever their order, so a change is judged
    /// the same however the changes came.
    pub(crate) fn ops(&mut self, changes: &[ExpandedChange]) -> Vec<Vec<Op>> {
        // 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) => Op {
                            path: place.touched(&op.key),
                            action: match &op.action {
                                _ if place.in_list || op.insert => Action::Within,
                                OpType::Make(automerge::ObjType::Map) => Action::MakeMap,
                                OpType::Put(automerge::ScalarValue::Str(text)) => {
                                    Action::PutString(text.to_string())
                                }
                                OpType::Delete => Action::Delete,
                                _ => Action::Other,
                            },
                        },
                        // Nowhere to be found: within every path's reach.
                        None => Op {
                            path: Vec::new(),
                            action: Action::Nowhere,
                        },
                    })
                    .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);
    }

    /// What each operation does where: a map made, a string put, a deletion, what is
    /// inside a list, anything else.
    #[test]
    fn what_operations_do() {
        let mut doc = Document::new();
        change(&mut doc, |doc| {
            let config = doc.put_object(ROOT, "config", ObjType::Map).unwrap();
            doc.put(&config, "mode", "fast").unwrap();
            doc.put(&config, "level", 3).unwrap();
            doc.delete(&config, "mode").unwrap();
            let queue = doc.put_object(ROOT, "queue", ObjType::List).unwrap();
            doc.insert(&queue, 0, "job").unwrap();
        });
        let empty = Document::new();
        let ops = Inspector::new(&empty).ops(&decoded(&doc, &[]));
        let actions: Vec<(Path, Action)> = ops[0]
            .iter()
            .map(|op| (op.path.clone(), op.action.clone()))
            .collect();
        assert_eq!(
            actions,
            vec![
                (path(&["config"]), Action::MakeMap),
                (
                    path(&["config", "mode"]),
                    Action::PutString("fast".to_owned())
                ),
                (path(&["config", "level"]), Action::Other),
                (path(&["config", "mode"]), Action::Delete),
                (path(&["queue"]), Action::Other),
                (path(&["queue"]), Action::Within),
            ]
        );
    }

    /// Inside a list or text, a path stops at it: items move.
    /// A write's place in the document, as the rules see the change it makes: cut after
    /// a list or text; as asked where nothing is yet.
    #[test]
    fn writes_placed_as_rules_see_them() {
        let mut doc = Document::new();
        change(&mut doc, |doc| {
            store::write_path(
                doc,
                &path(&["servers", "list"]),
                &serde_json::json!([{"name": "a"}]),
            )
            .unwrap();
            store::write_path(doc, &path(&["config", "mode"]), &serde_json::json!("fast")).unwrap();
        });
        let placed = |at: &[&str]| super::placed(&doc, &path(at));
        assert_eq!(
            placed(&["servers", "list", "0", "name"]),
            path(&["servers", "list"])
        );
        assert_eq!(placed(&["servers", "list"]), path(&["servers", "list"]));
        assert_eq!(placed(&["config", "mode"]), path(&["config", "mode"]));
        assert_eq!(
            placed(&["config", "new", "deep"]),
            path(&["config", "new", "deep"])
        );
        assert_eq!(placed(&["nothing", "here"]), path(&["nothing", "here"]));
        // As the change of such a write touches it.
        let before = doc.get_heads();
        change(&mut doc, |doc| {
            store::write_path(
                doc,
                &path(&["servers", "list", "0", "name"]),
                &serde_json::json!("b"),
            )
            .unwrap();
        });
        let touched = Inspector::new(&doc.fork_at(&before).unwrap()).paths(&decoded(&doc, &before));
        assert_eq!(touched, vec![[path(&["servers", "list"])].into()]);
    }

    #[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()));
    }
}