From b40d3f7ca3f92373eca8dd0683d37183559c78e6 Mon Sep 17 00:00:00 2001 From: tv Date: Sun, 8 Nov 2026 19:48:45 +0000 Subject: document: tell whether a document holds a change without building it MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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. --- src/document/at.rs | 2 +- src/document/changes.rs | 47 ++++++++++++++++++++++++++++++++++++++++------ src/document/sync.rs | 23 ++++++++++++----------- src/document/sync/model.rs | 2 +- 4 files changed, 55 insertions(+), 19 deletions(-) (limited to 'src/document') 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 { 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 = 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 = 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 { - 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 = 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, BTreeMap