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%?
```

3 files changed, 319 insertions, 307 deletions

diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 3896b1a25a2..04396d73df6 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -12,8 +12,8 @@ use infer::{RegionObligation, InferCtxt};
 use mir::interpret::GlobalId;
 use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, ToPredicate};
 use ty::error::ExpectedFound;
-use rustc_data_structures::obligation_forest::{ObligationForest, Error};
-use rustc_data_structures::obligation_forest::{ForestObligation, ObligationProcessor};
+use rustc_data_structures::obligation_forest::{Error, ForestObligation, ObligationForest};
+use rustc_data_structures::obligation_forest::{ObligationProcessor, ProcessResult};
 use std::marker::PhantomData;
 use hir::def_id::DefId;
 use middle::const_val::{ConstEvalErr, ErrKind};
@@ -251,302 +251,306 @@ struct FulfillProcessor<'a, 'b: 'a, 'gcx: 'tcx, 'tcx: 'b> {
     register_region_obligations: bool
 }
 
+fn mk_pending(os: Vec<PredicateObligation<'tcx>>) -> Vec<PendingPredicateObligation<'tcx>> {
+    os.into_iter().map(|o| PendingPredicateObligation {
+        obligation: o,
+        stalled_on: vec![]
+    }).collect()
+}
+
 impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx, 'tcx> {
     type Obligation = PendingPredicateObligation<'tcx>;
     type Error = FulfillmentErrorCode<'tcx>;
 
+    /// Processes a predicate obligation and returns either:
+    /// - `Changed(v)` if the predicate is true, presuming that `v` are also true
+    /// - `Unchanged` if we don't have enough info to be sure
+    /// - `Error(e)` if the predicate does not hold
+    ///
+    /// This is always inlined, despite its size, because it has a single
+    /// callsite and it is called *very* frequently.
+    #[inline(always)]
     fn process_obligation(&mut self,
-                          obligation: &mut Self::Obligation)
-                          -> Result<Option<Vec<Self::Obligation>>, Self::Error>
-    {
-        process_predicate(self.selcx, obligation, self.register_region_obligations)
-            .map(|os| os.map(|os| os.into_iter().map(|o| PendingPredicateObligation {
-                obligation: o,
-                stalled_on: vec![]
-            }).collect()))
-    }
-
-    fn process_backedge<'c, I>(&mut self, cycle: I,
-                               _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>)
-        where I: Clone + Iterator<Item=&'c PendingPredicateObligation<'tcx>>,
+                          pending_obligation: &mut Self::Obligation)
+                          -> ProcessResult<Self::Obligation, Self::Error>
     {
-        if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) {
-            debug!("process_child_obligations: coinductive match");
-        } else {
-            let cycle : Vec<_> = cycle.map(|c| c.obligation.clone()).collect();
-            self.selcx.infcx().report_overflow_error_cycle(&cycle);
+        // if we were stalled on some unresolved variables, first check
+        // whether any of them have been resolved; if not, don't bother
+        // doing more work yet
+        if !pending_obligation.stalled_on.is_empty() {
+            if pending_obligation.stalled_on.iter().all(|&ty| {
+                let resolved_ty = self.selcx.infcx().shallow_resolve(&ty);
+                resolved_ty == ty // nothing changed here
+            }) {
+                debug!("process_predicate: pending obligation {:?} still stalled on {:?}",
+                       self.selcx.infcx()
+                           .resolve_type_vars_if_possible(&pending_obligation.obligation),
+                       pending_obligation.stalled_on);
+                return ProcessResult::Unchanged;
+            }
+            pending_obligation.stalled_on = vec![];
         }
-    }
-}
 
-/// Return the set of type variables contained in a trait ref
-fn trait_ref_type_vars<'a, 'gcx, 'tcx>(selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
-                                       t: ty::PolyTraitRef<'tcx>) -> Vec<Ty<'tcx>>
-{
-    t.skip_binder() // ok b/c this check doesn't care about regions
-     .input_types()
-     .map(|t| selcx.infcx().resolve_type_vars_if_possible(&t))
-     .filter(|t| t.has_infer_types())
-     .flat_map(|t| t.walk())
-     .filter(|t| match t.sty { ty::TyInfer(_) => true, _ => false })
-     .collect()
-}
+        let obligation = &mut pending_obligation.obligation;
 
-/// Processes a predicate obligation and returns either:
-/// - `Ok(Some(v))` if the predicate is true, presuming that `v` are also true
-/// - `Ok(None)` if we don't have enough info to be sure
-/// - `Err` if the predicate does not hold
-fn process_predicate<'a, 'gcx, 'tcx>(
-    selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
-    pending_obligation: &mut PendingPredicateObligation<'tcx>,
-    register_region_obligations: bool)
-    -> Result<Option<Vec<PredicateObligation<'tcx>>>,
-              FulfillmentErrorCode<'tcx>>
-{
-    // if we were stalled on some unresolved variables, first check
-    // whether any of them have been resolved; if not, don't bother
-    // doing more work yet
-    if !pending_obligation.stalled_on.is_empty() {
-        if pending_obligation.stalled_on.iter().all(|&ty| {
-            let resolved_ty = selcx.infcx().shallow_resolve(&ty);
-            resolved_ty == ty // nothing changed here
-        }) {
-            debug!("process_predicate: pending obligation {:?} still stalled on {:?}",
-                   selcx.infcx().resolve_type_vars_if_possible(&pending_obligation.obligation),
-                   pending_obligation.stalled_on);
-            return Ok(None);
+        if obligation.predicate.has_infer_types() {
+            obligation.predicate =
+                self.selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate);
         }
-        pending_obligation.stalled_on = vec![];
-    }
-
-    let obligation = &mut pending_obligation.obligation;
-
-    if obligation.predicate.has_infer_types() {
-        obligation.predicate = selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate);
-    }
 
-    match obligation.predicate {
-        ty::Predicate::Trait(ref data) => {
-            let trait_obligation = obligation.with(data.clone());
-
-            if data.is_global() && !data.has_late_bound_regions() {
-                // no type variables present, can use evaluation for better caching.
-                // FIXME: consider caching errors too.
-                if selcx.infcx().predicate_must_hold(&obligation) {
-                    debug!("selecting trait `{:?}` at depth {} evaluated to holds",
-                           data, obligation.recursion_depth);
-                    return Ok(Some(vec![]))
+        match obligation.predicate {
+            ty::Predicate::Trait(ref data) => {
+                let trait_obligation = obligation.with(data.clone());
+
+                if data.is_global() && !data.has_late_bound_regions() {
+                    // no type variables present, can use evaluation for better caching.
+                    // FIXME: consider caching errors too.
+                    if self.selcx.infcx().predicate_must_hold(&obligation) {
+                        debug!("selecting trait `{:?}` at depth {} evaluated to holds",
+                               data, obligation.recursion_depth);
+                        return ProcessResult::Changed(vec![])
+                    }
                 }
-            }
 
-            match selcx.select(&trait_obligation) {
-                Ok(Some(vtable)) => {
-                    debug!("selecting trait `{:?}` at depth {} yielded Ok(Some)",
-                           data, obligation.recursion_depth);
-                    Ok(Some(vtable.nested_obligations()))
-                }
-                Ok(None) => {
-                    debug!("selecting trait `{:?}` at depth {} yielded Ok(None)",
-                           data, obligation.recursion_depth);
-
-                    // This is a bit subtle: for the most part, the
-                    // only reason we can fail to make progress on
-                    // trait selection is because we don't have enough
-                    // information about the types in the trait. One
-                    // exception is that we sometimes haven't decided
-                    // what kind of closure a closure is. *But*, in
-                    // that case, it turns out, the type of the
-                    // closure will also change, because the closure
-                    // also includes references to its upvars as part
-                    // of its type, and those types are resolved at
-                    // the same time.
-                    //
-                    // FIXME(#32286) logic seems false if no upvars
-                    pending_obligation.stalled_on =
-                        trait_ref_type_vars(selcx, data.to_poly_trait_ref());
-
-                    debug!("process_predicate: pending obligation {:?} now stalled on {:?}",
-                           selcx.infcx().resolve_type_vars_if_possible(obligation),
-                           pending_obligation.stalled_on);
-
-                    Ok(None)
-                }
-                Err(selection_err) => {
-                    info!("selecting trait `{:?}` at depth {} yielded Err",
-                          data, obligation.recursion_depth);
+                match self.selcx.select(&trait_obligation) {
+                    Ok(Some(vtable)) => {
+                        debug!("selecting trait `{:?}` at depth {} yielded Ok(Some)",
+                               data, obligation.recursion_depth);
+                        ProcessResult::Changed(mk_pending(vtable.nested_obligations()))
+                    }
+                    Ok(None) => {
+                        debug!("selecting trait `{:?}` at depth {} yielded Ok(None)",
+                               data, obligation.recursion_depth);
+
+                        // This is a bit subtle: for the most part, the
+                        // only reason we can fail to make progress on
+                        // trait selection is because we don't have enough
+                        // information about the types in the trait. One
+                        // exception is that we sometimes haven't decided
+                        // what kind of closure a closure is. *But*, in
+                        // that case, it turns out, the type of the
+                        // closure will also change, because the closure
+                        // also includes references to its upvars as part
+                        // of its type, and those types are resolved at
+                        // the same time.
+                        //
+                        // FIXME(#32286) logic seems false if no upvars
+                        pending_obligation.stalled_on =
+                            trait_ref_type_vars(self.selcx, data.to_poly_trait_ref());
+
+                        debug!("process_predicate: pending obligation {:?} now stalled on {:?}",
+                               self.selcx.infcx().resolve_type_vars_if_possible(obligation),
+                               pending_obligation.stalled_on);
+
+                        ProcessResult::Unchanged
+                    }
+                    Err(selection_err) => {
+                        info!("selecting trait `{:?}` at depth {} yielded Err",
+                              data, obligation.recursion_depth);
 
-                    Err(CodeSelectionError(selection_err))
+                        ProcessResult::Error(CodeSelectionError(selection_err))
+                    }
                 }
             }
-        }
 
-        ty::Predicate::RegionOutlives(ref binder) => {
-            match selcx.infcx().region_outlives_predicate(&obligation.cause, binder) {
-                Ok(()) => Ok(Some(Vec::new())),
-                Err(_) => Err(CodeSelectionError(Unimplemented)),
+            ty::Predicate::RegionOutlives(ref binder) => {
+                match self.selcx.infcx().region_outlives_predicate(&obligation.cause, binder) {
+                    Ok(()) => ProcessResult::Changed(vec![]),
+                    Err(_) => ProcessResult::Error(CodeSelectionError(Unimplemented)),
+                }
             }
-        }
 
-        ty::Predicate::TypeOutlives(ref binder) => {
-            // Check if there are higher-ranked regions.
-            match binder.no_late_bound_regions() {
-                // If there are, inspect the underlying type further.
-                None => {
-                    // Convert from `Binder<OutlivesPredicate<Ty, Region>>` to `Binder<Ty>`.
-                    let binder = binder.map_bound_ref(|pred| pred.0);
-
-                    // Check if the type has any bound regions.
-                    match binder.no_late_bound_regions() {
-                        // If so, this obligation is an error (for now). Eventually we should be
-                        // able to support additional cases here, like `for<'a> &'a str: 'a`.
-                        None => {
-                            Err(CodeSelectionError(Unimplemented))
-                        }
-                        // Otherwise, we have something of the form
-                        // `for<'a> T: 'a where 'a not in T`, which we can treat as `T: 'static`.
-                        Some(t_a) => {
-                            let r_static = selcx.tcx().types.re_static;
-                            if register_region_obligations {
-                                selcx.infcx().register_region_obligation(
-                                    obligation.cause.body_id,
-                                    RegionObligation {
-                                        sup_type: t_a,
-                                        sub_region: r_static,
-                                        cause: obligation.cause.clone(),
-                                    });
+            ty::Predicate::TypeOutlives(ref binder) => {
+                // Check if there are higher-ranked regions.
+                match binder.no_late_bound_regions() {
+                    // If there are, inspect the underlying type further.
+                    None => {
+                        // Convert from `Binder<OutlivesPredicate<Ty, Region>>` to `Binder<Ty>`.
+                        let binder = binder.map_bound_ref(|pred| pred.0);
+
+                        // Check if the type has any bound regions.
+                        match binder.no_late_bound_regions() {
+                            // If so, this obligation is an error (for now). Eventually we should be
+                            // able to support additional cases here, like `for<'a> &'a str: 'a`.
+                            None => {
+                                ProcessResult::Error(CodeSelectionError(Unimplemented))
+                            }
+                            // Otherwise, we have something of the form
+                            // `for<'a> T: 'a where 'a not in T`, which we can treat as
+                            // `T: 'static`.
+                            Some(t_a) => {
+                                let r_static = self.selcx.tcx().types.re_static;
+                                if self.register_region_obligations {
+                                    self.selcx.infcx().register_region_obligation(
+                                        obligation.cause.body_id,
+                                        RegionObligation {
+                                            sup_type: t_a,
+                                            sub_region: r_static,
+                                            cause: obligation.cause.clone(),
+                                        });
+                                }
+                                ProcessResult::Changed(vec![])
                             }
-                            Ok(Some(vec![]))
                         }
                     }
-                }
-                // If there aren't, register the obligation.
-                Some(ty::OutlivesPredicate(t_a, r_b)) => {
-                    if register_region_obligations {
-                        selcx.infcx().register_region_obligation(
-                            obligation.cause.body_id,
-                            RegionObligation {
-                                sup_type: t_a,
-                                sub_region: r_b,
-                                cause: obligation.cause.clone()
-                            });
+                    // If there aren't, register the obligation.
+                    Some(ty::OutlivesPredicate(t_a, r_b)) => {
+                        if self.register_region_obligations {
+                            self.selcx.infcx().register_region_obligation(
+                                obligation.cause.body_id,
+                                RegionObligation {
+                                    sup_type: t_a,
+                                    sub_region: r_b,
+                                    cause: obligation.cause.clone()
+                                });
+                        }
+                        ProcessResult::Changed(vec![])
                     }
-                    Ok(Some(vec![]))
                 }
             }
-        }
 
-        ty::Predicate::Projection(ref data) => {
-            let project_obligation = obligation.with(data.clone());
-            match project::poly_project_and_unify_type(selcx, &project_obligation) {
-                Ok(None) => {
-                    let tcx = selcx.tcx();
-                    pending_obligation.stalled_on =
-                        trait_ref_type_vars(selcx, data.to_poly_trait_ref(tcx));
-                    Ok(None)
+            ty::Predicate::Projection(ref data) => {
+                let project_obligation = obligation.with(data.clone());
+                match project::poly_project_and_unify_type(self.selcx, &project_obligation) {
+                    Ok(None) => {
+                        let tcx = self.selcx.tcx();
+                        pending_obligation.stalled_on =
+                            trait_ref_type_vars(self.selcx, data.to_poly_trait_ref(tcx));
+                        ProcessResult::Unchanged
+                    }
+                    Ok(Some(os)) => ProcessResult::Changed(mk_pending(os)),
+                    Err(e) => ProcessResult::Error(CodeProjectionError(e))
                 }
-                Ok(v) => Ok(v),
-                Err(e) => Err(CodeProjectionError(e))
             }
-        }
 
-        ty::Predicate::ObjectSafe(trait_def_id) => {
-            if !selcx.tcx().is_object_safe(trait_def_id) {
-                Err(CodeSelectionError(Unimplemented))
-            } else {
-                Ok(Some(Vec::new()))
+            ty::Predicate::ObjectSafe(trait_def_id) => {
+                if !self.selcx.tcx().is_object_safe(trait_def_id) {
+                    ProcessResult::Error(CodeSelectionError(Unimplemented))
+                } else {
+                    ProcessResult::Changed(vec![])
+                }
             }
-        }
 
-        ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => {
-            match selcx.infcx().closure_kind(closure_def_id, closure_substs) {
-                Some(closure_kind) => {
-                    if closure_kind.extends(kind) {
-                        Ok(Some(vec![]))
-                    } else {
-                        Err(CodeSelectionError(Unimplemented))
+            ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => {
+                match self.selcx.infcx().closure_kind(closure_def_id, closure_substs) {
+                    Some(closure_kind) => {
+                        if closure_kind.extends(kind) {
+                            ProcessResult::Changed(vec![])
+                        } else {
+                            ProcessResult::Error(CodeSelectionError(Unimplemented))
+                        }
+                    }
+                    None => {
+                        ProcessResult::Unchanged
                     }
-                }
-                None => {
-                    Ok(None)
                 }
             }
-        }
 
-        ty::Predicate::WellFormed(ty) => {
-            match ty::wf::obligations(selcx.infcx(),
-                                      obligation.param_env,
-                                      obligation.cause.body_id,
-                                      ty, obligation.cause.span) {
-                None => {
-                    pending_obligation.stalled_on = vec![ty];
-                    Ok(None)
+            ty::Predicate::WellFormed(ty) => {
+                match ty::wf::obligations(self.selcx.infcx(),
+                                          obligation.param_env,
+                                          obligation.cause.body_id,
+                                          ty, obligation.cause.span) {
+                    None => {
+                        pending_obligation.stalled_on = vec![ty];
+                        ProcessResult::Unchanged
+                    }
+                    Some(os) => ProcessResult::Changed(mk_pending(os))
                 }
-                s => Ok(s)
             }
-        }
 
-        ty::Predicate::Subtype(ref subtype) => {
-            match selcx.infcx().subtype_predicate(&obligation.cause,
-                                                  obligation.param_env,
-                                                  subtype) {
-                None => {
-                    // none means that both are unresolved
-                    pending_obligation.stalled_on = vec![subtype.skip_binder().a,
-                                                         subtype.skip_binder().b];
-                    Ok(None)
-                }
-                Some(Ok(ok)) => {
-                    Ok(Some(ok.obligations))
-                }
-                Some(Err(err)) => {
-                    let expected_found = ExpectedFound::new(subtype.skip_binder().a_is_expected,
-                                                            subtype.skip_binder().a,
-                                                            subtype.skip_binder().b);
-                    Err(FulfillmentErrorCode::CodeSubtypeError(expected_found, err))
+            ty::Predicate::Subtype(ref subtype) => {
+                match self.selcx.infcx().subtype_predicate(&obligation.cause,
+                                                           obligation.param_env,
+                                                           subtype) {
+                    None => {
+                        // None means that both are unresolved.
+                        pending_obligation.stalled_on = vec![subtype.skip_binder().a,
+                                                             subtype.skip_binder().b];
+                        ProcessResult::Unchanged
+                    }
+                    Some(Ok(ok)) => {
+                        ProcessResult::Changed(mk_pending(ok.obligations))
+                    }
+                    Some(Err(err)) => {
+                        let expected_found = ExpectedFound::new(subtype.skip_binder().a_is_expected,
+                                                                subtype.skip_binder().a,
+                                                                subtype.skip_binder().b);
+                        ProcessResult::Error(
+                            FulfillmentErrorCode::CodeSubtypeError(expected_found, err))
+                    }
                 }
             }
-        }
 
-        ty::Predicate::ConstEvaluatable(def_id, substs) => {
-            match selcx.tcx().lift_to_global(&obligation.param_env) {
-                None => {
-                    Ok(None)
-                }
-                Some(param_env) => {
-                    match selcx.tcx().lift_to_global(&substs) {
-                        Some(substs) => {
-                            let instance = ty::Instance::resolve(
-                                selcx.tcx().global_tcx(),
-                                param_env,
-                                def_id,
-                                substs,
-                            );
-                            if let Some(instance) = instance {
-                                let cid = GlobalId {
-                                    instance,
-                                    promoted: None,
-                                };
-                                match selcx.tcx().at(obligation.cause.span)
-                                                 .const_eval(param_env.and(cid)) {
-                                    Ok(_) => Ok(Some(vec![])),
-                                    Err(err) => Err(CodeSelectionError(ConstEvalFailure(err)))
+            ty::Predicate::ConstEvaluatable(def_id, substs) => {
+                match self.selcx.tcx().lift_to_global(&obligation.param_env) {
+                    None => {
+                        ProcessResult::Unchanged
+                    }
+                    Some(param_env) => {
+                        match self.selcx.tcx().lift_to_global(&substs) {
+                            Some(substs) => {
+                                let instance = ty::Instance::resolve(
+                                    self.selcx.tcx().global_tcx(),
+                                    param_env,
+                                    def_id,
+                                    substs,
+                                );
+                                if let Some(instance) = instance {
+                                    let cid = GlobalId {
+                                        instance,
+                                        promoted: None,
+                                    };
+                                    match self.selcx.tcx().at(obligation.cause.span)
+                                                          .const_eval(param_env.and(cid)) {
+                                        Ok(_) => ProcessResult::Changed(vec![]),
+                                        Err(err) => ProcessResult::Error(
+                                            CodeSelectionError(ConstEvalFailure(err)))
+                                    }
+                                } else {
+                                    ProcessResult::Error(
+                                        CodeSelectionError(ConstEvalFailure(ConstEvalErr {
+                                            span: obligation.cause.span,
+                                            kind: ErrKind::CouldNotResolve.into(),
+                                        }))
+                                    )
                                 }
-                            } else {
-                                Err(CodeSelectionError(ConstEvalFailure(ConstEvalErr {
-                                    span: obligation.cause.span,
-                                    kind: ErrKind::CouldNotResolve.into(),
-                                })))
+                            },
+                            None => {
+                                pending_obligation.stalled_on = substs.types().collect();
+                                ProcessResult::Unchanged
                             }
-                        },
-                        None => {
-                            pending_obligation.stalled_on = substs.types().collect();
-                            Ok(None)
                         }
                     }
                 }
             }
         }
     }
+
+    fn process_backedge<'c, I>(&mut self, cycle: I,
+                               _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>)
+        where I: Clone + Iterator<Item=&'c PendingPredicateObligation<'tcx>>,
+    {
+        if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) {
+            debug!("process_child_obligations: coinductive match");
+        } else {
+            let cycle : Vec<_> = cycle.map(|c| c.obligation.clone()).collect();
+            self.selcx.infcx().report_overflow_error_cycle(&cycle);
+        }
+    }
+}
+
+/// Return the set of type variables contained in a trait ref
+fn trait_ref_type_vars<'a, 'gcx, 'tcx>(selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
+                                       t: ty::PolyTraitRef<'tcx>) -> Vec<Ty<'tcx>>
+{
+    t.skip_binder() // ok b/c this check doesn't care about regions
+     .input_types()
+     .map(|t| selcx.infcx().resolve_type_vars_if_possible(&t))
+     .filter(|t| t.has_infer_types())
+     .flat_map(|t| t.walk())
+     .filter(|t| match t.sty { ty::TyInfer(_) => true, _ => false })
+     .collect()
 }
 
 fn to_fulfillment_error<'tcx>(
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!(),
             }
         }, |_|{}));