diff options
| -rw-r--r-- | src/librustc/traits/error_reporting.rs | 5 | ||||
| -rw-r--r-- | src/librustc/traits/mod.rs | 2 | ||||
| -rw-r--r-- | src/librustc/traits/select.rs | 174 | ||||
| -rw-r--r-- | src/librustc/traits/structural_impls.rs | 1 |
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? } } } |