screen: changes put in order in one pass

bench_screening showed screening growing quadratically: 1 000 changes
took 29 ms on top of applying them, 10 000 took 2.8 s, and 100 000
didn't finish in minutes. in_order placed changes in rounds, each
taking those, in hash order, whose dependencies were placed: a chain
received in one delta, its hashes in no order of their own, took about
as many rounds as changes, each over all of them.

It now counts, for each change, its dependencies among those received
not placed yet, and places the smallest hash of those with none left,
then those building on it as their counts reach zero (Kahn's
algorithm): n log n, and still the same order on every node, whatever
order the changes came in. One with a dependency neither in the
document nor among them, and what builds on it, still wait.

1 files changed, 37 insertions, 19 deletions

diff --git a/src/access/screen.rs b/src/access/screen.rs
index d7c9389..162528b 100644
--- a/src/access/screen.rs
+++ b/src/access/screen.rs
@@ -689,27 +689,45 @@ fn in_order(doc: &Document, candidates: Vec<Change>) -> (Vec<Change>, Vec<Change
         .into_iter()
         .map(|change| (change.hash(), change))
         .collect();
-    let mut ready = Vec::new();
-    let mut placed: HashSet<ChangeHash> = HashSet::new();
-    loop {
-        let mut progress = false;
-        let mut hashes: Vec<ChangeHash> = by_hash.keys().copied().collect();
-        // The same order on every node, whatever order they came in.
-        hashes.sort_unstable();
-        for hash in hashes {
-            let change = &by_hash[&hash];
-            if change
-                .deps()
-                .iter()
-                .all(|dep| placed.contains(dep) || doc.get_change_by_hash(dep).is_some())
-            {
-                placed.insert(hash);
-                ready.push(by_hash.remove(&hash).expect("there"));
-                progress = true;
+    // Each one's dependencies among these not placed yet, and those building on each;
+    // one with a dependency neither in the document nor among these is never placed,
+    // nor anything building on it.
+    let mut unplaced: HashMap<ChangeHash, usize> = HashMap::new();
+    let mut building: HashMap<ChangeHash, Vec<ChangeHash>> = HashMap::new();
+    let mut next: std::collections::BTreeSet<ChangeHash> = std::collections::BTreeSet::new();
+    for (hash, change) in &by_hash {
+        let mut among = 0;
+        let mut missing = false;
+        for dep in change.deps() {
+            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() {
+                missing = true;
             }
         }
-        if !progress {
-            break;
+        if missing {
+            continue;
+        }
+        if among == 0 {
+            next.insert(*hash);
+        } else {
+            unplaced.insert(*hash, among);
+        }
+    }
+    // The smallest hash of those ready first: the same order on every node, whatever
+    // order they came in.
+    let mut ready = Vec::new();
+    while let Some(hash) = next.pop_first() {
+        ready.push(by_hash.remove(&hash).expect("there"));
+        for child in building.remove(&hash).unwrap_or_default() {
+            if let Some(left) = unplaced.get_mut(&child) {
+                *left -= 1;
+                if *left == 0 {
+                    unplaced.remove(&child);
+                    next.insert(child);
+                }
+            }
         }
     }
     (ready, by_hash.into_values().collect())