stale delta offers

1 files changed, 60 insertions, 0 deletions

diff --git a/src/document/sync.rs b/src/document/sync.rs
index 2921bb9..e93fa17 100644
--- a/src/document/sync.rs
+++ b/src/document/sync.rs
@@ -366,6 +366,40 @@ impl SyncSession {
         }
     }
 
+    /// Of the changes in `doc` beyond `from`, how many the peer has too, as far as we
+    /// know (its heads' history, and what went either way since, `sent_hashes`). A delta
+    /// it offers from `from` brings those again: offered before it heard what we have
+    /// now (while we downloaded its last one, say, and it waited for our answer).
+    pub(crate) fn known_beyond(
+        &self,
+        doc: &Document,
+        from: &[crate::document::ChangeHash],
+    ) -> usize {
+        let from: Vec<crate::document::ChangeHash> = from
+            .iter()
+            .copied()
+            .filter(|hash| doc.get_change_by_hash(hash).is_some())
+            .collect();
+        let beyond: std::collections::HashMap<_, _> = doc
+            .get_changes_meta(&from)
+            .into_iter()
+            .map(|change| (change.hash, change.deps))
+            .collect();
+        // A change's predecessors outside `beyond` are in the history of `from`.
+        let mut known = std::collections::HashSet::new();
+        let mut pending: Vec<crate::document::ChangeHash> =
+            self.state.their_heads.iter().flatten().copied().collect();
+        pending.extend(self.state.sent_hashes.iter().copied());
+        while let Some(hash) = pending.pop() {
+            if let Some(deps) = beyond.get(&hash)
+                && known.insert(hash)
+            {
+                pending.extend(deps.iter().copied());
+            }
+        }
+        known.len()
+    }
+
     /// What the sync state knows of the peer (`PeerView`).
     fn peer_view(&self) -> PeerView {
         PeerView {
@@ -1037,6 +1071,32 @@ mod tests {
         }
     }
 
+    /// A delta offered from heads we since moved past, by changes from the offerer,
+    /// would bring those again; our own, which it lacks, don't count.
+    #[test]
+    fn offers_from_before_count_what_came_since() {
+        use crate::document::changes::{delta_bytes, load_delta};
+        use crate::document::testing::change;
+        use automerge::{ROOT, transaction::Transactable};
+        let (mut ours, mut theirs) = (Document::new(), Document::new());
+        change(&mut ours, |doc| doc.put(ROOT, "early", 1).unwrap());
+        let (_a, mut b) = in_step(&mut ours, &mut theirs);
+
+        let before = theirs.get_heads();
+        change(&mut ours, |doc| doc.put(ROOT, "news", 2).unwrap());
+        let delta = delta_bytes(&ours, &before, &ours.get_heads()).unwrap();
+        load_delta(&mut theirs, &delta).unwrap();
+        b.came_from_peer(&theirs, &before);
+        change(&mut theirs, |doc| doc.put(ROOT, "own", 3).unwrap());
+
+        assert_eq!(
+            b.known_beyond(&theirs, &before),
+            1,
+            "the delta's change again"
+        );
+        assert_eq!(b.known_beyond(&theirs, &theirs.get_heads()), 0);
+    }
+
     /// Our transport refused a message taken as delivered: the peer's heads are as
     /// before, so the next message carries the change again.
     #[test]