Auto merge of #51411 - nnethercote:process_predicate, r=nikomatsakis

Speed up obligation forest code

Here are the rustc-perf benchmarks that get at least a 1% speedup on one or more of their runs with these patches applied:
```
inflate-check
        avg: -8.7%      min: -12.1%     max: 0.0%
inflate
        avg: -5.9%      min: -8.6%      max: 1.1%
inflate-opt
        avg: -1.5%      min: -2.0%      max: -0.3%
clap-rs-check
        avg: -0.6%      min: -1.9%      max: 0.5%
coercions
        avg: -0.2%?     min: -1.3%?     max: 0.6%?
serde-opt
        avg: -0.6%      min: -1.0%      max: 0.1%
coercions-check
        avg: -0.4%?     min: -1.0%?     max: -0.0%?
```

2 files changed, 66 insertions, 58 deletions

diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index c3934c4e1b8..990dc66c66a 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -41,7 +41,7 @@ pub trait ObligationProcessor {
 
     fn process_obligation(&mut self,
                           obligation: &mut Self::Obligation)
-                          -> Result<Option<Vec<Self::Obligation>>, Self::Error>;
+                          -> ProcessResult<Self::Obligation, Self::Error>;
 
     /// As we do the cycle check, we invoke this callback when we
     /// encounter an actual cycle. `cycle` is an iterator that starts
@@ -57,6 +57,14 @@ pub trait ObligationProcessor {
         where I: Clone + Iterator<Item=&'c Self::Obligation>;
 }
 
+/// The result type used by `process_obligation`.
+#[derive(Debug)]
+pub enum ProcessResult<O, E> {
+    Unchanged,
+    Changed(Vec<O>),
+    Error(E),
+}
+
 pub struct ObligationForest<O: ForestObligation> {
     /// The list of obligations. In between calls to
     /// `process_obligations`, this list only contains nodes in the
@@ -136,8 +144,8 @@ pub struct Outcome<O, E> {
 
     /// If true, then we saw no successful obligations, which means
     /// there is no point in further iteration. This is based on the
-    /// assumption that when trait matching returns `Err` or
-    /// `Ok(None)`, those results do not affect environmental
+    /// assumption that when trait matching returns `Error` or
+    /// `Unchanged`, those results do not affect environmental
     /// inference state. (Note that if we invoke `process_obligations`
     /// with no pending obligations, stalled will be true.)
     pub stalled: bool,
@@ -270,11 +278,11 @@ impl<O: ForestObligation> ObligationForest<O> {
                    result);
 
             match result {
-                Ok(None) => {
-                    // no change in state
+                ProcessResult::Unchanged => {
+                    // No change in state.
                 }
-                Ok(Some(children)) => {
-                    // if we saw a Some(_) result, we are not (yet) stalled
+                ProcessResult::Changed(children) => {
+                    // We are not (yet) stalled.
                     stalled = false;
                     self.nodes[index].state.set(NodeState::Success);
 
@@ -290,7 +298,7 @@ impl<O: ForestObligation> ObligationForest<O> {
                         }
                     }
                 }
-                Err(err) => {
+                ProcessResult::Error(err) => {
                     stalled = false;
                     let backtrace = self.error_at(index);
                     errors.push(Error {
diff --git a/src/librustc_data_structures/obligation_forest/test.rs b/src/librustc_data_structures/obligation_forest/test.rs
index a95b2b84b34..527a1ef0ec4 100644
--- a/src/librustc_data_structures/obligation_forest/test.rs
+++ b/src/librustc_data_structures/obligation_forest/test.rs
@@ -10,7 +10,7 @@
 
 #![cfg(test)]
 
-use super::{ObligationForest, ObligationProcessor, Outcome, Error};
+use super::{Error, ObligationForest, ObligationProcessor, Outcome, ProcessResult};
 
 use std::fmt;
 use std::marker::PhantomData;
@@ -31,7 +31,7 @@ struct ClosureObligationProcessor<OF, BF, O, E> {
 
 #[allow(non_snake_case)]
 fn C<OF, BF, O>(of: OF, bf: BF) -> ClosureObligationProcessor<OF, BF, O, &'static str>
-    where OF: FnMut(&mut O) -> Result<Option<Vec<O>>, &'static str>,
+    where OF: FnMut(&mut O) -> ProcessResult<O, &'static str>,
           BF: FnMut(&[O])
 {
     ClosureObligationProcessor {
@@ -44,7 +44,7 @@ fn C<OF, BF, O>(of: OF, bf: BF) -> ClosureObligationProcessor<OF, BF, O, &'stati
 impl<OF, BF, O, E> ObligationProcessor for ClosureObligationProcessor<OF, BF, O, E>
     where O: super::ForestObligation + fmt::Debug,
           E: fmt::Debug,
-          OF: FnMut(&mut O) -> Result<Option<Vec<O>>, E>,
+          OF: FnMut(&mut O) -> ProcessResult<O, E>,
           BF: FnMut(&[O])
 {
     type Obligation = O;
@@ -52,7 +52,7 @@ impl<OF, BF, O, E> ObligationProcessor for ClosureObligationProcessor<OF, BF, O,
 
     fn process_obligation(&mut self,
                           obligation: &mut Self::Obligation)
-                          -> Result<Option<Vec<Self::Obligation>>, Self::Error>
+                          -> ProcessResult<Self::Obligation, Self::Error>
     {
         (self.process_obligation)(obligation)
     }
@@ -78,9 +78,9 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
-                "B" => Err("B is for broken"),
-                "C" => Ok(Some(vec![])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
+                "B" => ProcessResult::Error("B is for broken"),
+                "C" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -101,10 +101,10 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(None),
-                "A.2" => Ok(None),
-                "A.3" => Ok(Some(vec!["A.3.i"])),
-                "D" => Ok(Some(vec!["D.1", "D.2"])),
+                "A.1" => ProcessResult::Unchanged,
+                "A.2" => ProcessResult::Unchanged,
+                "A.3" => ProcessResult::Changed(vec!["A.3.i"]),
+                "D" => ProcessResult::Changed(vec!["D.1", "D.2"]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -119,11 +119,11 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(Some(vec![])),
-                "A.2" => Err("A is for apple"),
-                "A.3.i" => Ok(Some(vec![])),
-                "D.1" => Ok(Some(vec!["D.1.i"])),
-                "D.2" => Ok(Some(vec!["D.2.i"])),
+                "A.1" => ProcessResult::Changed(vec![]),
+                "A.2" => ProcessResult::Error("A is for apple"),
+                "A.3.i" => ProcessResult::Changed(vec![]),
+                "D.1" => ProcessResult::Changed(vec!["D.1.i"]),
+                "D.2" => ProcessResult::Changed(vec!["D.2.i"]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -138,8 +138,8 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D.1.i" => Err("D is for dumb"),
-                "D.2.i" => Ok(Some(vec![])),
+                "D.1.i" => ProcessResult::Error("D is for dumb"),
+                "D.2.i" => ProcessResult::Changed(vec![]),
                 _ => panic!("unexpected obligation {:?}", obligation),
             }
         }, |_| {}));
@@ -167,7 +167,7 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -177,9 +177,9 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(Some(vec![])),
-                "A.2" => Ok(Some(vec!["A.2.i", "A.2.ii"])),
-                "A.3" => Ok(Some(vec![])),
+                "A.1" => ProcessResult::Changed(vec![]),
+                "A.2" => ProcessResult::Changed(vec!["A.2.i", "A.2.ii"]),
+                "A.3" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -189,8 +189,8 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.2.i" => Ok(Some(vec!["A.2.i.a"])),
-                "A.2.ii" => Ok(Some(vec![])),
+                "A.2.i" => ProcessResult::Changed(vec!["A.2.i.a"]),
+                "A.2.ii" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -200,7 +200,7 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.2.i.a" => Ok(Some(vec![])),
+                "A.2.i.a" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -223,7 +223,7 @@ fn to_errors_no_throw() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -244,7 +244,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2"])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -254,8 +254,8 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(Some(vec!["D"])),
-                "A.2" => Ok(Some(vec!["D"])),
+                "A.1" => ProcessResult::Changed(vec!["D"]),
+                "A.2" => ProcessResult::Changed(vec!["D"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -266,7 +266,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" => { d_count += 1; Ok(Some(vec![])) },
+                "D" => { d_count += 1; ProcessResult::Changed(vec![]) },
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -281,7 +281,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A'" => Ok(Some(vec!["A'.1", "A'.2"])),
+                "A'" => ProcessResult::Changed(vec!["A'.1", "A'.2"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -291,8 +291,8 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A'.1" => Ok(Some(vec!["D'", "A'"])),
-                "A'.2" => Ok(Some(vec!["D'"])),
+                "A'.1" => ProcessResult::Changed(vec!["D'", "A'"]),
+                "A'.2" => ProcessResult::Changed(vec!["D'"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -303,7 +303,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D'" => { d_count += 1; Err("operation failed") },
+                "D'" => { d_count += 1; ProcessResult::Error("operation failed") },
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -329,7 +329,7 @@ fn done_dependency() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A: Sized" | "B: Sized" | "C: Sized" => Ok(Some(vec![])),
+                "A: Sized" | "B: Sized" | "C: Sized" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -340,11 +340,11 @@ fn done_dependency() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "(A,B,C): Sized" => Ok(Some(vec![
+                "(A,B,C): Sized" => ProcessResult::Changed(vec![
                     "A: Sized",
                     "B: Sized",
                     "C: Sized"
-                        ])),
+                        ]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -367,10 +367,10 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["D", "E"])),
-                "B" => Ok(None),
-                "C1" => Ok(Some(vec![])),
-                "C2" => Ok(Some(vec![])),
+                "A" => ProcessResult::Changed(vec!["D", "E"]),
+                "B" => ProcessResult::Unchanged,
+                "C1" => ProcessResult::Changed(vec![]),
+                "C2" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -380,8 +380,8 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" | "E" => Ok(None),
-                "B" => Ok(Some(vec!["D"])),
+                "D" | "E" => ProcessResult::Unchanged,
+                "B" => ProcessResult::Changed(vec!["D"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -391,8 +391,8 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" => Ok(None),
-                "E" => Err("E is for error"),
+                "D" => ProcessResult::Unchanged,
+                "E" => ProcessResult::Error("E is for error"),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -405,7 +405,7 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" => Err("D is dead"),
+                "D" => ProcessResult::Error("D is dead"),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -429,8 +429,8 @@ fn simultaneous_register_and_error() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Err("An error"),
-                "B" => Ok(Some(vec!["A"])),
+                "A" => ProcessResult::Error("An error"),
+                "B" => ProcessResult::Changed(vec!["A"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -447,8 +447,8 @@ fn simultaneous_register_and_error() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Err("An error"),
-                "B" => Ok(Some(vec!["A"])),
+                "A" => ProcessResult::Error("An error"),
+                "B" => ProcessResult::Changed(vec!["A"]),
                 _ => unreachable!(),
             }
         }, |_|{}));