document: tell whether a document holds a change without building it

With the policy's reads kept, judging a change still costs about one
read (some 3.5 µs), and so does judging without a policy: what is left
is At::new, which asks get_change_by_hash for each head. Automerge
builds the change again from the document's operations to answer, at
a cost growing with its history. Screening asks it again for every
candidate and every dependency, and sync for heads.

Ask by the missing dependencies instead (changes::holds), which look
the hash up: one the document holds is not among them. A change queued
in the document, waiting for its dependencies, isn't either; but then
some are missing, and only then is it asked the slow way. Every check
of whether a document holds a change goes through it.

1 files changed, 41 insertions, 6 deletions

diff --git a/src/document/changes.rs b/src/document/changes.rs
index 44d30bd..031dd0c 100644
--- a/src/document/changes.rs
+++ b/src/document/changes.rs
@@ -8,11 +8,24 @@ use anyhow::{Context, Result, anyhow, bail};
 
 use super::{Change, ChangeHash, Document, ReadDoc};
 
+/// Whether `doc` has applied the change `hash`. Without `get_change_by_hash`, which
+/// builds the change again from the document's operations, at a cost growing with its
+/// history: by its missing dependencies, which look the hash up. One `doc` holds is
+/// none of them; nor is one it has queued, waiting for its own, which are: with none
+/// missing, nothing is queued, and `hash` is applied; with some, it is asked the slow
+/// way (rarely: changes wait in the document only as a sync message or a file brought
+/// them, `sync`, `file`).
+pub(crate) fn holds(doc: &impl ReadDoc, hash: &ChangeHash) -> bool {
+    let missing = doc.get_missing_deps(std::slice::from_ref(hash));
+    if missing.contains(hash) {
+        return false;
+    }
+    missing.is_empty() || doc.get_change_by_hash(hash).is_some()
+}
+
 /// Whether `doc` has every change of `heads`.
-pub(crate) fn holds_all(doc: &Document, heads: &[ChangeHash]) -> bool {
-    heads
-        .iter()
-        .all(|head| doc.get_change_by_hash(head).is_some())
+pub(crate) fn holds_all(doc: &impl ReadDoc, heads: &[ChangeHash]) -> bool {
+    heads.iter().all(|head| holds(doc, head))
 }
 
 /// Whether the history of `theirs` (of them, those `doc` has) holds all of `ours`
@@ -21,7 +34,7 @@ pub(crate) fn covers(doc: &Document, theirs: &[ChangeHash], ours: &[ChangeHash])
     let known: Vec<ChangeHash> = theirs
         .iter()
         .copied()
-        .filter(|head| doc.get_change_by_hash(head).is_some())
+        .filter(|head| holds(doc, head))
         .collect();
     if known.is_empty() {
         return ours.is_empty();
@@ -39,7 +52,7 @@ pub(crate) fn missing(doc: &impl ReadDoc, heads: &[ChangeHash]) -> Vec<ChangeHas
     heads
         .iter()
         .copied()
-        .filter(|head| doc.get_change_by_hash(head).is_none())
+        .filter(|head| !holds(doc, head))
         .collect()
 }
 
@@ -325,6 +338,28 @@ mod tests {
         heads
     }
 
+    /// Held: a change applied; not one never seen, nor one queued, waiting for the one
+    /// before it, until that comes.
+    #[test]
+    fn holds_applied_changes_only() {
+        let mut theirs = Document::new();
+        change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap());
+        let first = theirs.get_heads()[0];
+        change(&mut theirs, |doc| doc.put(ROOT, "k", 2).unwrap());
+        let second = theirs.get_heads()[0];
+        let mut ours = Document::new();
+        assert!(!holds(&ours, &first));
+        ours.apply_changes([theirs.get_change_by_hash(&second).unwrap()])
+            .unwrap();
+        assert!(!holds(&ours, &second), "queued");
+        assert!(!holds(&ours, &first));
+        ours.apply_changes([theirs.get_change_by_hash(&first).unwrap()])
+            .unwrap();
+        assert!(holds(&ours, &first));
+        assert!(holds(&ours, &second));
+        assert!(holds_all(&ours, &[first, second]));
+    }
+
     /// Over random histories: two nodes that reached the same heads through different
     /// merge orders, one with more on top, produce the same bytes for a delta to those
     /// heads; a document at `from` that loads them is at `to`.