screen: waiting changes building on a refused one refused at once

A change waiting for a dependency that hadn't come stayed waiting when
another of its dependencies was refused meanwhile, until the bound
pushed it out. Changes building on one refused before were refused one
generation per batch.

Building on a refused change is now followed through at once, before
judging and again after (refuse_building): whatever waits on a change
refused in the batch, or on one of those, is refused then and there.

1 files changed, 90 insertions, 25 deletions

diff --git a/src/access/screen.rs b/src/access/screen.rs
index ae61416..e15b407 100644
--- a/src/access/screen.rs
+++ b/src/access/screen.rs
@@ -21,6 +21,7 @@
 //!
 //! A change whose dependencies are neither in the document nor among those received
 //! waits (`Waiting`) until they come, a bounded number; Automerge never sees it before.
+//! One that builds on a change refused meanwhile is refused then, not left waiting.
 //! With signatures required (`access::policy`), so does one no signature by its
 //! committer vouches for yet, and whatever builds on it, until one comes, but an epoch's
 //! root, which no node signs: a signature vouches for its change and the changes of its
@@ -248,31 +249,7 @@ pub(crate) fn apply(
         .collect();
     // Building on one refused before: refused too, without waiting for it (it never
     // comes) or judging it.
-    let (building, candidates): (Vec<Change>, Vec<Change>) = candidates
-        .into_iter()
-        .partition(|change| change.deps().iter().any(|dep| refusals.contains(dep)));
-    for change in building {
-        let dep = change
-            .deps()
-            .iter()
-            .find(|dep| refusals.contains(dep))
-            .copied()
-            .expect("partitioned so");
-        let root = refusals.root(&dep).unwrap_or(dep);
-        refusals.insert(change.hash(), root);
-        screened.roots.insert(root);
-        screened.refused.push(Refused {
-            committer: change.author().and_then(|author| {
-                std::str::from_utf8(author.as_bytes())
-                    .ok()
-                    .map(str::to_owned)
-            }),
-            user: change.message().and_then(user_of).map(str::to_owned),
-            paths: BTreeSet::new(),
-            why: format!("it builds on refused change {dep}"),
-            change,
-        });
-    }
+    let candidates = refuse_building(candidates, refusals, &mut screened);
     let (ready, unready) = in_order(doc, candidates);
     waiting.0 = unready;
     if ready.is_empty() {
@@ -469,10 +446,55 @@ pub(crate) fn apply(
             screened.roots.insert(root);
         }
     }
+    // Waiting for one refused since (or building on such): refused now, not left to
+    // age out.
+    waiting.0 = refuse_building(std::mem::take(&mut waiting.0), refusals, &mut screened);
+    screened.roots.retain(|root| !forged.contains(root));
     waiting.keep_newest();
     Ok(screened)
 }
 
+/// Of `changes`, those building on a change `refusals` holds, or on one of these that
+/// does, and so on: refused, into `refusals` and `screened`, without being judged. The
+/// rest, as they were.
+fn refuse_building(
+    mut changes: Vec<Change>,
+    refusals: &mut Refusals,
+    screened: &mut Screened,
+) -> Vec<Change> {
+    loop {
+        let (building, rest): (Vec<Change>, Vec<Change>) = changes
+            .into_iter()
+            .partition(|change| change.deps().iter().any(|dep| refusals.contains(dep)));
+        changes = rest;
+        if building.is_empty() {
+            return changes;
+        }
+        for change in building {
+            let dep = change
+                .deps()
+                .iter()
+                .find(|dep| refusals.contains(dep))
+                .copied()
+                .expect("partitioned so");
+            let root = refusals.root(&dep).unwrap_or(dep);
+            refusals.insert(change.hash(), root);
+            screened.roots.insert(root);
+            screened.refused.push(Refused {
+                committer: change.author().and_then(|author| {
+                    std::str::from_utf8(author.as_bytes())
+                        .ok()
+                        .map(str::to_owned)
+                }),
+                user: change.message().and_then(user_of).map(str::to_owned),
+                paths: BTreeSet::new(),
+                why: format!("it builds on refused change {dep}"),
+                change,
+            });
+        }
+    }
+}
+
 /// `accepted` applied to `doc`. Automerge takes them all or none: one it won't take (a
 /// fork of an actor's changes, under a policy without signatures) fails the lot, so the
 /// error names them (the first few), with the node each says made it, for the log of
@@ -919,6 +941,49 @@ mod tests {
         );
     }
 
+    /// A change waiting for a dependency that hasn't come, building on another refused
+    /// meanwhile: refused at once, not left to wait.
+    #[test]
+    fn waiting_on_a_refused_change_refused_at_once() {
+        let mut theirs = genesis();
+        let mut other = theirs.fork();
+        write(&mut theirs, "a", Some("mallory"), "notes/x", json!(1));
+        write(&mut other, "a", Some("alice"), "notes/w", json!(2));
+        let missing = other.get_heads()[0];
+        theirs.merge(&mut other).unwrap();
+        write(&mut theirs, "a", Some("alice"), "notes/z", json!(3));
+        let last = theirs.get_heads()[0];
+        let mut ours = Document::new();
+        let mut waiting = Waiting::default();
+        let mut refusals = Refusals::default();
+        let mut screen_with = |ours: &mut Document, changes, waiting: &mut Waiting| {
+            apply(
+                ours,
+                Epoch::GENESIS,
+                changes,
+                waiting,
+                &mut refusals,
+                None,
+                &mut crate::document::PatchLog::inactive(),
+            )
+            .unwrap()
+        };
+        let all = received(&theirs, &[]);
+        let first: Vec<Change> = all.iter().filter(|c| c.hash() == last).cloned().collect();
+        let screened = screen_with(&mut ours, first, &mut waiting);
+        assert_eq!((screened.applied, waiting.len()), (0, 1));
+        // All but one it builds on: mallory's refused, and the waiting one with it.
+        let rest: Vec<Change> = all
+            .into_iter()
+            .filter(|c| c.hash() != missing && c.hash() != last)
+            .collect();
+        let screened = screen_with(&mut ours, rest, &mut waiting);
+        let refused: Vec<ChangeHash> = screened.refused.iter().map(|r| r.change.hash()).collect();
+        assert_eq!(refused.len(), 2);
+        assert!(refused.contains(&last));
+        assert_eq!(waiting.len(), 0);
+    }
+
     /// With signatures required, changes no signature vouches for wait, with what
     /// builds on them, until one comes; one signature vouches for its actor's earlier
     /// changes too.