Refactor overflow handling in traits::select to propagate overflow instead of aborting eagerly

We store the obligation that caused the overflow as part of the OverflowError, and report it at the public API endpoints (rather than in the implementation internals).

4 files changed, 113 insertions, 69 deletions

diff --git a/src/librustc/traits/error_reporting.rs b/src/librustc/traits/error_reporting.rs
index 33abc0c7e15..686008cc1ef 100644
--- a/src/librustc/traits/error_reporting.rs
+++ b/src/librustc/traits/error_reporting.rs
@@ -24,6 +24,7 @@ use super::{
     SelectionContext,
     SelectionError,
     ObjectSafetyViolation,
+    Overflow,
 };
 
 use errors::DiagnosticBuilder;
@@ -830,6 +831,10 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                 }
                 err.struct_error(self.tcx, span, "constant expression")
             }
+
+            Overflow(_) => {
+                bug!("overflow should be handled before the `report_selection_error` path");
+            }
         };
         self.note_obligation_cause(&mut err, obligation);
         err.emit();
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 728d9f1a027..6101d37956a 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -349,6 +349,8 @@ pub enum SelectionError<'tcx> {
                                 ty::error::TypeError<'tcx>),
     TraitNotObjectSafe(DefId),
     ConstEvalFailure(ConstEvalErr<'tcx>),
+    // upon overflow, stores the obligation that hit the recursion limit
+    Overflow(TraitObligation<'tcx>),
 }
 
 pub struct FulfillmentError<'tcx> {
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index f43f5cf3e3f..e65bfa7a72e 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -22,7 +22,7 @@ use super::project;
 use super::project::{normalize_with_depth, Normalized, ProjectionCacheKey};
 use super::{PredicateObligation, TraitObligation, ObligationCause};
 use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation};
-use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch};
+use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch, Overflow};
 use super::{ObjectCastObligation, Obligation};
 use super::TraitNotObjectSafe;
 use super::Selection;
@@ -408,6 +408,17 @@ impl EvaluationResult {
     }
 }
 
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// Indicates that trait evaluation caused overflow. Stores the obligation
+/// that hit the recursion limit.
+pub struct OverflowError<'tcx>(TraitObligation<'tcx>);
+
+impl<'tcx> From<OverflowError<'tcx>> for SelectionError<'tcx> {
+    fn from(OverflowError(o): OverflowError<'tcx>) -> SelectionError<'tcx> {
+        SelectionError::Overflow(o)
+    }
+}
+
 #[derive(Clone)]
 pub struct EvaluationCache<'tcx> {
     hashmap: RefCell<FxHashMap<ty::PolyTraitRef<'tcx>, WithDepNode<EvaluationResult>>>
@@ -528,12 +539,21 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         assert!(!obligation.predicate.has_escaping_regions());
 
         let stack = self.push_stack(TraitObligationStackList::empty(), obligation);
-        let ret = match self.candidate_from_obligation(&stack)? {
-            None => None,
-            Some(candidate) => Some(self.confirm_candidate(obligation, candidate)?)
+
+        let candidate = match self.candidate_from_obligation(&stack) {
+            Err(SelectionError::Overflow(o)) =>
+                self.infcx().report_overflow_error(&o, true),
+            Err(e) => { return Err(e); },
+            Ok(None) => { return Ok(None); },
+            Ok(Some(candidate)) => candidate
         };
 
-        Ok(ret)
+        match self.confirm_candidate(obligation, candidate) {
+            Err(SelectionError::Overflow(o)) =>
+                self.infcx().report_overflow_error(&o, true),
+            Err(e) => Err(e),
+            Ok(candidate) => Ok(Some(candidate))
+        }
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -554,10 +574,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         debug!("evaluate_obligation({:?})",
                obligation);
 
-        self.probe(|this, _| {
+        match self.probe(|this, _| {
             this.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation)
-                .may_apply()
-        })
+        }) {
+            Ok(result) => result.may_apply(),
+            Err(OverflowError(o)) => self.infcx().report_overflow_error(&o, true)
+        }
     }
 
     /// Evaluates whether the obligation `obligation` can be satisfied,
@@ -570,10 +592,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         debug!("evaluate_obligation_conservatively({:?})",
                obligation);
 
-        self.probe(|this, _| {
+        match self.probe(|this, _| {
             this.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation)
-                == EvaluatedToOk
-        })
+        }) {
+            Ok(result) => result == EvaluatedToOk,
+            Err(OverflowError(o)) => self.infcx().report_overflow_error(&o, true)
+        }
     }
 
     /// Evaluates the predicates in `predicates` recursively. Note that
@@ -582,29 +606,29 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_predicates_recursively<'a,'o,I>(&mut self,
                                                 stack: TraitObligationStackList<'o, 'tcx>,
                                                 predicates: I)
-                                                -> EvaluationResult
+                                                -> Result<EvaluationResult, OverflowError<'tcx>>
         where I : IntoIterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a
     {
         let mut result = EvaluatedToOk;
         for obligation in predicates {
-            let eval = self.evaluate_predicate_recursively(stack, obligation);
+            let eval = self.evaluate_predicate_recursively(stack, obligation)?;
             debug!("evaluate_predicate_recursively({:?}) = {:?}",
                    obligation, eval);
             if let EvaluatedToErr = eval {
                 // fast-path - EvaluatedToErr is the top of the lattice,
                 // so we don't need to look on the other predicates.
-                return EvaluatedToErr;
+                return Ok(EvaluatedToErr);
             } else {
                 result = cmp::max(result, eval);
             }
         }
-        result
+        Ok(result)
     }
 
     fn evaluate_predicate_recursively<'o>(&mut self,
                                           previous_stack: TraitObligationStackList<'o, 'tcx>,
                                           obligation: &PredicateObligation<'tcx>)
-                                           -> EvaluationResult
+                                           -> Result<EvaluationResult, OverflowError<'tcx>>
     {
         debug!("evaluate_predicate_recursively({:?})",
                obligation);
@@ -620,11 +644,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 // does this code ever run?
                 match self.infcx.subtype_predicate(&obligation.cause, obligation.param_env, p) {
                     Some(Ok(InferOk { obligations, .. })) => {
-                        self.evaluate_predicates_recursively(previous_stack, &obligations);
-                        EvaluatedToOk
+                        self.evaluate_predicates_recursively(previous_stack, &obligations)
                     },
-                    Some(Err(_)) => EvaluatedToErr,
-                    None => EvaluatedToAmbig,
+                    Some(Err(_)) => Ok(EvaluatedToErr),
+                    None => Ok(EvaluatedToAmbig),
                 }
             }
 
@@ -636,21 +659,21 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     Some(obligations) =>
                         self.evaluate_predicates_recursively(previous_stack, obligations.iter()),
                     None =>
-                        EvaluatedToAmbig,
+                        Ok(EvaluatedToAmbig),
                 }
             }
 
             ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
                 // we do not consider region relationships when
                 // evaluating trait matches
-                EvaluatedToOk
+                Ok(EvaluatedToOk)
             }
 
             ty::Predicate::ObjectSafe(trait_def_id) => {
                 if self.tcx().is_object_safe(trait_def_id) {
-                    EvaluatedToOk
+                    Ok(EvaluatedToOk)
                 } else {
-                    EvaluatedToErr
+                    Ok(EvaluatedToErr)
                 }
             }
 
@@ -668,10 +691,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                         result
                     }
                     Ok(None) => {
-                        EvaluatedToAmbig
+                        Ok(EvaluatedToAmbig)
                     }
                     Err(_) => {
-                        EvaluatedToErr
+                        Ok(EvaluatedToErr)
                     }
                 }
             }
@@ -680,13 +703,13 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 match self.infcx.closure_kind(closure_def_id, closure_substs) {
                     Some(closure_kind) => {
                         if closure_kind.extends(kind) {
-                            EvaluatedToOk
+                            Ok(EvaluatedToOk)
                         } else {
-                            EvaluatedToErr
+                            Ok(EvaluatedToErr)
                         }
                     }
                     None => {
-                        EvaluatedToAmbig
+                        Ok(EvaluatedToAmbig)
                     }
                 }
             }
@@ -707,16 +730,16 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                                 promoted: None
                             };
                             match self.tcx().const_eval(param_env.and(cid)) {
-                                Ok(_) => EvaluatedToOk,
-                                Err(_) => EvaluatedToErr
+                                Ok(_) => Ok(EvaluatedToOk),
+                                Err(_) => Ok(EvaluatedToErr)
                             }
                         } else {
-                            EvaluatedToErr
+                            Ok(EvaluatedToErr)
                         }
                     }
                     None => {
                         // Inference variables still left in param_env or substs.
-                        EvaluatedToAmbig
+                        Ok(EvaluatedToAmbig)
                     }
                 }
             }
@@ -726,7 +749,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_trait_predicate_recursively<'o>(&mut self,
                                                 previous_stack: TraitObligationStackList<'o, 'tcx>,
                                                 mut obligation: TraitObligation<'tcx>)
-                                                -> EvaluationResult
+                                                -> Result<EvaluationResult, OverflowError<'tcx>>
     {
         debug!("evaluate_trait_predicate_recursively({:?})",
                obligation);
@@ -745,22 +768,23 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             debug!("CACHE HIT: EVAL({:?})={:?}",
                    fresh_trait_ref,
                    result);
-            return result;
+            return Ok(result);
         }
 
         let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack));
+        let result = result?;
 
         debug!("CACHE MISS: EVAL({:?})={:?}",
                fresh_trait_ref,
                result);
         self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result);
 
-        result
+        Ok(result)
     }
 
     fn evaluate_stack<'o>(&mut self,
                           stack: &TraitObligationStack<'o, 'tcx>)
-                          -> EvaluationResult
+                          -> Result<EvaluationResult, OverflowError<'tcx>>
     {
         // In intercrate mode, whenever any of the types are unbound,
         // there can always be an impl. Even if there are no impls in
@@ -815,7 +839,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     }
                 }
             }
-            return EvaluatedToAmbig;
+            return Ok(EvaluatedToAmbig);
         }
         if unbound_input_types &&
               stack.iter().skip(1).any(
@@ -825,7 +849,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         {
             debug!("evaluate_stack({:?}) --> unbound argument, recursive --> giving up",
                    stack.fresh_trait_ref);
-            return EvaluatedToUnknown;
+            return Ok(EvaluatedToUnknown);
         }
 
         // If there is any previous entry on the stack that precisely
@@ -860,18 +884,19 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             if self.coinductive_match(cycle) {
                 debug!("evaluate_stack({:?}) --> recursive, coinductive",
                        stack.fresh_trait_ref);
-                return EvaluatedToOk;
+                return Ok(EvaluatedToOk);
             } else {
                 debug!("evaluate_stack({:?}) --> recursive, inductive",
                        stack.fresh_trait_ref);
-                return EvaluatedToRecur;
+                return Ok(EvaluatedToRecur);
             }
         }
 
         match self.candidate_from_obligation(stack) {
             Ok(Some(c)) => self.evaluate_candidate(stack, &c),
-            Ok(None) => EvaluatedToAmbig,
-            Err(..) => EvaluatedToErr
+            Ok(None) => Ok(EvaluatedToAmbig),
+            Err(Overflow(o)) => Err(OverflowError(o)),
+            Err(..) => Ok(EvaluatedToErr)
         }
     }
 
@@ -909,7 +934,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_candidate<'o>(&mut self,
                               stack: &TraitObligationStack<'o, 'tcx>,
                               candidate: &SelectionCandidate<'tcx>)
-                              -> EvaluationResult
+                              -> Result<EvaluationResult, OverflowError<'tcx>>
     {
         debug!("evaluate_candidate: depth={} candidate={:?}",
                stack.obligation.recursion_depth, candidate);
@@ -921,12 +946,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                         stack.list(),
                         selection.nested_obligations().iter())
                 }
-                Err(..) => EvaluatedToErr
+                Err(..) => Ok(EvaluatedToErr)
             }
-        });
+        })?;
         debug!("evaluate_candidate: depth={} result={:?}",
                stack.obligation.recursion_depth, result);
-        result
+        Ok(result)
     }
 
     fn check_evaluation_cache(&self,
@@ -1000,7 +1025,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         // not update) the cache.
         let recursion_limit = *self.infcx.tcx.sess.recursion_limit.get();
         if stack.obligation.recursion_depth >= recursion_limit {
-            self.infcx().report_overflow_error(&stack.obligation, true);
+            return Err(Overflow(stack.obligation.clone()));
         }
 
         // Check the cache. Note that we skolemize the trait-ref
@@ -1081,9 +1106,15 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     debug!("evaluate_stack: intercrate_ambiguity_causes is some");
                     // Heuristics: show the diagnostics when there are no candidates in crate.
                     if let Ok(candidate_set) = self.assemble_candidates(stack) {
-                        if !candidate_set.ambiguous && candidate_set.vec.iter().all(|c| {
-                            !self.evaluate_candidate(stack, &c).may_apply()
-                        }) {
+                        let no_candidates_apply =
+                            candidate_set
+                            .vec
+                            .iter()
+                            .map(|c| self.evaluate_candidate(stack, &c))
+                            .collect::<Result<Vec<_>, OverflowError<'_>>>()?
+                            .iter()
+                            .all(|r| !r.may_apply());
+                        if !candidate_set.ambiguous && no_candidates_apply {
                             let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
                             let self_ty = trait_ref.self_ty();
                             let trait_desc = trait_ref.to_string();
@@ -1151,18 +1182,21 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
 
         // Winnow, but record the exact outcome of evaluation, which
-        // is needed for specialization.
-        let mut candidates: Vec<_> = candidates.into_iter().filter_map(|c| {
-            let eval = self.evaluate_candidate(stack, &c);
-            if eval.may_apply() {
-                Some(EvaluatedCandidate {
+        // is needed for specialization. Propagate overflow if it occurs.
+        let candidates: Result<Vec<Option<EvaluatedCandidate>>, _> = candidates
+            .into_iter()
+            .map(|c| match self.evaluate_candidate(stack, &c) {
+                Ok(eval) if eval.may_apply() => Ok(Some(EvaluatedCandidate {
                     candidate: c,
                     evaluation: eval,
-                })
-            } else {
-                None
-            }
-        }).collect();
+                })),
+                Ok(_) => Ok(None),
+                Err(OverflowError(o)) => Err(Overflow(o)),
+            })
+            .collect();
+
+        let mut candidates: Vec<EvaluatedCandidate> =
+            candidates?.into_iter().filter_map(|c| c).collect();
 
         // If there are STILL multiple candidate, we can further
         // reduce the list by dropping duplicates -- including
@@ -1537,12 +1571,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         let matching_bounds =
             all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
 
-        let matching_bounds =
-            matching_bounds.filter(
-                |bound| self.evaluate_where_clause(stack, bound.clone()).may_apply());
-
-        let param_candidates =
-            matching_bounds.map(|bound| ParamCandidate(bound));
+        // keep only those bounds which may apply, and propagate overflow if it occurs
+        let mut param_candidates = vec![];
+        for bound in matching_bounds {
+            let wc = self.evaluate_where_clause(stack, bound.clone())?;
+            if wc.may_apply() {
+                param_candidates.push(ParamCandidate(bound));
+            }
+        }
 
         candidates.vec.extend(param_candidates);
 
@@ -1552,14 +1588,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_where_clause<'o>(&mut self,
                                  stack: &TraitObligationStack<'o, 'tcx>,
                                  where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
-                                 -> EvaluationResult
+                                 -> Result<EvaluationResult, OverflowError<'tcx>>
     {
         self.probe(move |this, _| {
             match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
                 Ok(obligations) => {
                     this.evaluate_predicates_recursively(stack.list(), obligations.iter())
                 }
-                Err(()) => EvaluatedToErr
+                Err(()) => Ok(EvaluatedToErr)
             }
         })
     }
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index 1e3e4160de1..c124cd7942a 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -177,6 +177,7 @@ impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
             super::ConstEvalFailure(ref err) => {
                 tcx.lift(err).map(super::ConstEvalFailure)
             }
+            super::Overflow(_) => bug!() // FIXME: ape ConstEvalFailure?
         }
     }
 }