signatures: look for arrived changes only where the document grew

Received signatures of changes the document doesn't hold yet wait for
them, up to 65536 (MAX_PENDING). Each Signatures::offer, one per
received sync message, looked up every waiting one's change to find
those that came meanwhile.

The pending signatures now remember the document's heads at the last
look (Pending::scanned, Pending::arrived): while they stand, the
document holds nothing more, as it only grows, and offer looks up none.

1 files changed, 18 insertions, 9 deletions

diff --git a/src/document/signatures.rs b/src/document/signatures.rs
index 8577619..4554420 100644
--- a/src/document/signatures.rs
+++ b/src/document/signatures.rs
@@ -210,6 +210,9 @@ struct Pending {
     by_change: HashMap<ChangeHash, [u8; 64]>,
     /// The changes, oldest first; some may have left `by_change` since.
     order: std::collections::VecDeque<ChangeHash>,
+    /// The document's heads when `offer` last looked for those whose changes came: as
+    /// long as they stand, none came (`arrived`).
+    scanned: Vec<ChangeHash>,
 }
 
 impl Pending {
@@ -235,8 +238,19 @@ impl Pending {
         self.by_change.remove(hash)
     }
 
-    fn keys(&self) -> impl Iterator<Item = &ChangeHash> {
-        self.by_change.keys()
+    /// Those whose changes `doc` holds now: none where its heads are those of the last
+    /// look, as a document only grows; else each looked up.
+    fn arrived(&mut self, doc: &Document) -> Vec<ChangeHash> {
+        let heads = doc.get_heads();
+        if heads == self.scanned {
+            return Vec::new();
+        }
+        self.scanned = heads;
+        self.by_change
+            .keys()
+            .filter(|hash| super::changes::holds(doc, hash))
+            .copied()
+            .collect()
     }
 }
 
@@ -376,12 +390,7 @@ impl Signatures {
                 Vouched::Nothing => {}
             }
         }
-        let arrived: Vec<ChangeHash> = self
-            .pending
-            .keys()
-            .filter(|hash| super::changes::holds(doc, hash))
-            .copied()
-            .collect();
+        let arrived = self.pending.arrived(doc);
         // Their own budget: what waited came from any peer, not only this one.
         let mut invalid_waiting = 0;
         for hash in arrived {
@@ -890,7 +899,7 @@ mod tests {
         for i in 0..=MAX_PENDING {
             pending.insert(hash(i), [0; 64]);
         }
-        assert_eq!(pending.keys().count(), MAX_PENDING);
+        assert_eq!(pending.by_change.len(), MAX_PENDING);
         assert!(pending.remove(&hash(0)).is_none());
         assert!(pending.remove(&hash(MAX_PENDING)).is_some());
     }