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.

7 files changed, 60 insertions, 24 deletions

diff --git a/src/access/rules.rs b/src/access/rules.rs
index 3aba0ba..bef9a13 100644
--- a/src/access/rules.rs
+++ b/src/access/rules.rs
@@ -125,7 +125,7 @@ pub(crate) fn judge_reading(
         // The first epoch's: the first change a document holds, as it comes to an empty
         // one, or as it is in one (judged again, `swarm::refusals`).
         let root = if epoch.generation == 0 {
-            doc.get_heads().is_empty() || doc.get_change_by_hash(&change.hash).is_some()
+            doc.get_heads().is_empty() || crate::document::changes::holds(doc, &change.hash)
         } else {
             change.hash.0 == epoch.id
         };
diff --git a/src/access/screen.rs b/src/access/screen.rs
index 1c6c8c7..793e8bb 100644
--- a/src/access/screen.rs
+++ b/src/access/screen.rs
@@ -40,7 +40,7 @@ use crate::document::inspect::{Action, Inspector, Op, Path};
 use crate::document::meta;
 use crate::document::replica::{Epoch, user_of};
 use crate::document::signatures::Signatures;
-use crate::document::{Change, ChangeHash, Document, ReadDoc};
+use crate::document::{Change, ChangeHash, Document};
 
 /// Changes waiting for their dependencies, kept at most: the oldest go.
 const MAX_WAITING: usize = 10_000;
@@ -289,7 +289,7 @@ pub(crate) fn apply(
         .into_iter()
         .chain(received)
         .filter(|change| seen.insert(change.hash()))
-        .filter(|change| doc.get_change_by_hash(&change.hash()).is_none())
+        .filter(|change| !crate::document::changes::holds(doc, &change.hash()))
         .filter(|change| match refusals.root(&change.hash()) {
             Some(root) => {
                 screened.refused_again += 1;
@@ -780,7 +780,7 @@ fn in_order(doc: &Document, candidates: Vec<Change>) -> (Vec<Change>, Vec<Change
             if by_hash.contains_key(dep) {
                 among += 1;
                 building.entry(*dep).or_default().push(*hash);
-            } else if doc.get_change_by_hash(dep).is_none() {
+            } else if !crate::document::changes::holds(doc, dep) {
                 missing = true;
             }
         }
diff --git a/src/document/at.rs b/src/document/at.rs
index d318f17..2d35736 100644
--- a/src/document/at.rs
+++ b/src/document/at.rs
@@ -23,7 +23,7 @@ impl<'a> At<'a> {
     pub(crate) fn new(doc: &'a Document, heads: &[ChangeHash]) -> Option<Self> {
         heads
             .iter()
-            .all(|head| doc.get_change_by_hash(head).is_some())
+            .all(|head| crate::document::changes::holds(doc, head))
             .then(|| Self {
                 doc,
                 heads: heads.to_vec(),
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`.
diff --git a/src/document/sync.rs b/src/document/sync.rs
index b172dd1..394b10a 100644
--- a/src/document/sync.rs
+++ b/src/document/sync.rs
@@ -403,14 +403,14 @@ impl SyncSession {
             if have
                 .last_sync
                 .iter()
-                .all(|hash| doc.get_change_by_hash(hash).is_some())
+                .all(|hash| crate::document::changes::holds(doc, hash))
             {
                 continue;
             }
             let mut known: Vec<crate::document::ChangeHash> = have
                 .last_sync
                 .iter()
-                .filter(|hash| doc.get_change_by_hash(hash).is_some())
+                .filter(|hash| crate::document::changes::holds(doc, hash))
                 .chain(self.state.shared_heads.iter())
                 .copied()
                 .collect();
@@ -435,7 +435,7 @@ impl SyncSession {
         let theirs = self.state.their_heads.as_ref()?;
         if theirs
             .iter()
-            .any(|hash| doc.get_change_by_hash(hash).is_none())
+            .any(|hash| !crate::document::changes::holds(doc, hash))
         {
             return None;
         }
@@ -514,7 +514,8 @@ impl SyncSession {
     /// place of heads we lack (changes it has and we don't), the heads we share: the
     /// delta may then carry some it has, but nothing it lacks.
     fn delta_from(&self, doc: &Document) -> Vec<crate::document::ChangeHash> {
-        let known = |hash: &&crate::document::ChangeHash| doc.get_change_by_hash(hash).is_some();
+        let known =
+            |hash: &&crate::document::ChangeHash| crate::document::changes::holds(doc, hash);
         let theirs = self.state.their_heads.as_deref().unwrap_or_default();
         let mut from: Vec<_> = theirs.iter().filter(known).copied().collect();
         if from.len() < theirs.len() {
@@ -587,7 +588,7 @@ impl SyncSession {
             !heads.is_empty()
                 && heads
                     .iter()
-                    .all(|head| doc.get_change_by_hash(head).is_some())
+                    .all(|head| crate::document::changes::holds(doc, head))
         })
     }
 
@@ -711,7 +712,7 @@ impl SyncSession {
         let from: Vec<crate::document::ChangeHash> = from
             .iter()
             .copied()
-            .filter(|hash| doc.get_change_by_hash(hash).is_some())
+            .filter(|hash| crate::document::changes::holds(doc, hash))
             .collect();
         let beyond: std::collections::HashMap<_, _> = doc
             .get_changes_meta(&from)
@@ -796,7 +797,7 @@ impl SyncSession {
         self.state.their_heads.as_ref().is_some_and(|theirs| {
             theirs
                 .iter()
-                .all(|hash| doc.get_change_by_hash(hash).is_some())
+                .all(|hash| crate::document::changes::holds(doc, hash))
                 && heads.iter().any(|hash| !theirs.contains(hash))
         })
     }
@@ -831,7 +832,7 @@ impl SyncSession {
             let older = self.state.their_heads.as_ref().is_some_and(|theirs| {
                 theirs
                     .iter()
-                    .all(|hash| doc.get_change_by_hash(hash).is_some())
+                    .all(|hash| crate::document::changes::holds(doc, hash))
             });
             if !before.is_some_and(|before| older && level(&before.their_heads)) {
                 return false;
@@ -892,7 +893,7 @@ impl SyncSession {
         let before = self.state.sent_hashes.len();
         self.state
             .sent_hashes
-            .retain(|hash| beyond.contains(hash) || doc.get_change_by_hash(hash).is_none());
+            .retain(|hash| beyond.contains(hash) || !crate::document::changes::holds(doc, hash));
         self.state.their_heads = Some(heads.to_vec());
         self.state.shared_heads = heads.to_vec();
         self.state.their_have = Some(vec![sync::Have {
@@ -1541,7 +1542,7 @@ mod tests {
             Received::pushed(heads, changes).expect("decodes"),
         )
         .unwrap();
-        assert!(theirs.get_change_by_hash(&lost).is_none());
+        assert!(!crate::document::changes::holds(&theirs, &lost));
         let ask = b.generate(&theirs, now, bytes).expect("an ask");
         assert_eq!(decode(&ask).unwrap().0.need, vec![lost]);
     }
@@ -2056,7 +2057,7 @@ mod tests {
         let answer = decode(&answer).unwrap();
         assert!(answer.carries_changes(), "with what the pusher lacks");
         a.receive(&mut ours, answer).unwrap();
-        assert!(ours.get_change_by_hash(&only_theirs[0]).is_some());
+        assert!(crate::document::changes::holds(&ours, &only_theirs[0]));
         assert_eq!(ours.get_heads(), theirs.get_heads());
     }
 
diff --git a/src/document/sync/model.rs b/src/document/sync/model.rs
index ad8c6c3..b3bb703 100644
--- a/src/document/sync/model.rs
+++ b/src/document/sync/model.rs
@@ -170,7 +170,7 @@ fn run(seed: u64, push_below: usize) -> (BTreeMap<String, String>, BTreeMap<Stri
                     // Behind the peer: pull (`relay::pull_if_behind`).
                     if heads
                         .iter()
-                        .any(|head| side.doc.get_change_by_hash(head).is_none())
+                        .any(|head| !crate::document::changes::holds(&side.doc, head))
                     {
                         side.session.pull_from(heads);
                     } else if side.session.reply.is_some() && heads == side.doc.get_heads() {
diff --git a/src/remake/snapshot.rs b/src/remake/snapshot.rs
index ee0a2cd..dc61810 100644
--- a/src/remake/snapshot.rs
+++ b/src/remake/snapshot.rs
@@ -274,7 +274,7 @@ pub(crate) fn build(
 ) -> Result<Snapshot, SnapshotError> {
     // fork_at with unknown heads would quietly build something else.
     for head in params.base_heads {
-        if source.get_change_by_hash(head).is_none() {
+        if !crate::document::changes::holds(source, head) {
             return Err(SnapshotError::MissingBase(*head));
         }
     }