Make `process_obligations()` greedier.

`process_obligations()` adds new nodes, but it does not process these
new nodes until the next time it is called.

This commit changes it so that it does process these new nodes within
the same call. This change reduces the number of calls to
`process_obligations()` required to complete processing, sometimes
giving significant speed-ups.

The change required some changes to tests.
- The output of `cycle-cache-err-60010.rs` is slightly different.
- The unit tests required extra cases to handle the earlier processing
  of the added nodes. I mostly did these in the simplest possible way,
  by making the added nodes be ignored, thus giving outcomes the same as
  with the old behaviour. But I changed `success_in_grandchildren()`
  more extensively so that some obligations are completed earlier than
  they used to be.

3 files changed, 36 insertions, 11 deletions

diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index 958ab617cb3..8a5badd0afc 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -395,7 +395,16 @@ impl<O: ForestObligation> ObligationForest<O> {
         let mut errors = vec![];
         let mut stalled = true;
 
-        for index in 0..self.nodes.len() {
+        // Note that the loop body can append new nodes, and those new nodes
+        // will then be processed by subsequent iterations of the loop.
+        //
+        // We can't use an iterator for the loop because `self.nodes` is
+        // appended to and the borrow checker would complain. We also can't use
+        // `for index in 0..self.nodes.len() { ... }` because the range would
+        // be computed with the initial length, and we would miss the appended
+        // nodes. Therefore we use a `while` loop.
+        let mut index = 0;
+        while index < self.nodes.len() {
             let node = &mut self.nodes[index];
 
             debug!("process_obligations: node {} == {:?}", index, node);
@@ -406,6 +415,7 @@ impl<O: ForestObligation> ObligationForest<O> {
             // out of sync with `nodes`. It's not very common, but it does
             // happen, and code in `compress` has to allow for it.
             if node.state.get() != NodeState::Pending {
+                index += 1;
                 continue;
             }
             let result = processor.process_obligation(&mut node.obligation);
@@ -441,6 +451,7 @@ impl<O: ForestObligation> ObligationForest<O> {
                     });
                 }
             }
+            index += 1;
         }
 
         if stalled {
diff --git a/src/librustc_data_structures/obligation_forest/tests.rs b/src/librustc_data_structures/obligation_forest/tests.rs
index 54b6f6d0adc..995c99bfec3 100644
--- a/src/librustc_data_structures/obligation_forest/tests.rs
+++ b/src/librustc_data_structures/obligation_forest/tests.rs
@@ -70,6 +70,7 @@ fn push_pop() {
                 "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
                 "B" => ProcessResult::Error("B is for broken"),
                 "C" => ProcessResult::Changed(vec![]),
+                "A.1" | "A.2" | "A.3" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_| {}), DoCompleted::Yes);
@@ -94,6 +95,7 @@ fn push_pop() {
                 "A.2" => ProcessResult::Unchanged,
                 "A.3" => ProcessResult::Changed(vec!["A.3.i"]),
                 "D" => ProcessResult::Changed(vec!["D.1", "D.2"]),
+                "A.3.i" | "D.1" | "D.2" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_| {}), DoCompleted::Yes);
@@ -113,6 +115,7 @@ fn push_pop() {
                 "A.3.i" => ProcessResult::Changed(vec![]),
                 "D.1" => ProcessResult::Changed(vec!["D.1.i"]),
                 "D.2" => ProcessResult::Changed(vec!["D.2.i"]),
+                "D.1.i" | "D.2.i" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_| {}), DoCompleted::Yes);
@@ -161,35 +164,38 @@ fn success_in_grandchildren() {
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
                 "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
+                "A.1" => ProcessResult::Changed(vec![]),
+                "A.2" => ProcessResult::Changed(vec!["A.2.i", "A.2.ii"]),
+                "A.3" => ProcessResult::Changed(vec![]),
+                "A.2.i" | "A.2.ii" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_| {}), DoCompleted::Yes);
-    assert!(ok.unwrap().is_empty());
+    let mut ok = ok.unwrap();
+    ok.sort();
+    assert_eq!(ok, vec!["A.1", "A.3"]);
     assert!(err.is_empty());
 
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => ProcessResult::Changed(vec![]),
-                "A.2" => ProcessResult::Changed(vec!["A.2.i", "A.2.ii"]),
-                "A.3" => ProcessResult::Changed(vec![]),
+                "A.2.i" => ProcessResult::Unchanged,
+                "A.2.ii" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}), DoCompleted::Yes);
-    let mut ok = ok.unwrap();
-    ok.sort();
-    assert_eq!(ok, vec!["A.1", "A.3"]);
+    assert_eq!(ok.unwrap(), vec!["A.2.ii"]);
     assert!(err.is_empty());
 
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
                 "A.2.i" => ProcessResult::Changed(vec!["A.2.i.a"]),
-                "A.2.ii" => ProcessResult::Changed(vec![]),
+                "A.2.i.a" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_| {}), DoCompleted::Yes);
-    assert_eq!(ok.unwrap(), vec!["A.2.ii"]);
+    assert!(ok.unwrap().is_empty());
     assert!(err.is_empty());
 
     let Outcome { completed: ok, errors: err, .. } =
@@ -222,6 +228,7 @@ fn to_errors_no_throw() {
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
                 "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
+                "A.1" | "A.2" | "A.3" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_|{}), DoCompleted::Yes);
@@ -243,6 +250,7 @@ fn diamond() {
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
                 "A" => ProcessResult::Changed(vec!["A.1", "A.2"]),
+                "A.1" | "A.2" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_|{}), DoCompleted::Yes);
@@ -254,6 +262,7 @@ fn diamond() {
             match *obligation {
                 "A.1" => ProcessResult::Changed(vec!["D"]),
                 "A.2" => ProcessResult::Changed(vec!["D"]),
+                "D" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_|{}), DoCompleted::Yes);
@@ -282,6 +291,7 @@ fn diamond() {
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
                 "A'" => ProcessResult::Changed(vec!["A'.1", "A'.2"]),
+                "A'.1" | "A'.2" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_|{}), DoCompleted::Yes);
@@ -293,6 +303,7 @@ fn diamond() {
             match *obligation {
                 "A'.1" => ProcessResult::Changed(vec!["D'", "A'"]),
                 "A'.2" => ProcessResult::Changed(vec!["D'"]),
+                "D'" | "A'" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_|{}), DoCompleted::Yes);
@@ -370,6 +381,7 @@ fn orphan() {
                 "B" => ProcessResult::Unchanged,
                 "C1" => ProcessResult::Changed(vec![]),
                 "C2" => ProcessResult::Changed(vec![]),
+                "D" | "E" => ProcessResult::Unchanged,
                 _ => unreachable!(),
             }
         }, |_|{}), DoCompleted::Yes);
diff --git a/src/test/ui/traits/cycle-cache-err-60010.stderr b/src/test/ui/traits/cycle-cache-err-60010.stderr
index f439de88261..295845b1146 100644
--- a/src/test/ui/traits/cycle-cache-err-60010.stderr
+++ b/src/test/ui/traits/cycle-cache-err-60010.stderr
@@ -6,7 +6,7 @@ LL |     _parse: <ParseQuery as Query<RootDatabase>>::Data,
    |
    = note: required because of the requirements on the impl of `Query<RootDatabase>` for `ParseQuery`
 
-error[E0275]: overflow evaluating the requirement `RootDatabase: SourceDatabase`
+error[E0275]: overflow evaluating the requirement `Runtime<RootDatabase>: std::panic::RefUnwindSafe`
   --> $DIR/cycle-cache-err-60010.rs:31:5
    |
 LL |     type Storage;
@@ -17,6 +17,8 @@ LL | impl Database for RootDatabase {
 LL |     type Storage = SalsaStorage;
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
+   = note: required because it appears within the type `RootDatabase`
+   = note: required because of the requirements on the impl of `SourceDatabase` for `RootDatabase`
    = note: required because of the requirements on the impl of `Query<RootDatabase>` for `ParseQuery`
    = note: required because it appears within the type `SalsaStorage`