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())