Fix bugs in evaluating WellFormed predicates

- List the nestsed obligations in an order that works with the
  single pass used by evaluation
- Propagate recursion depth correctly

8 files changed, 117 insertions, 42 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs
index 8586a550230..289e0e0ba63 100644
--- a/compiler/rustc_trait_selection/src/traits/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs
@@ -449,6 +449,7 @@ impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> {
                         self.selcx.infcx(),
                         obligation.param_env,
                         obligation.cause.body_id,
+                        obligation.recursion_depth + 1,
                         arg,
                         obligation.cause.span,
                     ) {
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index 59399133dff..ced99b3eb64 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -139,9 +139,18 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     );
                 });
             // Require that the projection is well-formed.
-            let self_ty = obligation.predicate.skip_binder().self_ty();
-            obligations.push(Obligation::new(
+            let self_ty = self.infcx.replace_bound_vars_with_placeholders(&obligation.self_ty());
+            let self_ty = normalize_with_depth_to(
+                self,
+                obligation.param_env,
                 obligation.cause.clone(),
+                obligation.recursion_depth + 1,
+                &self_ty,
+                &mut obligations,
+            );
+            obligations.push(Obligation::with_depth(
+                obligation.cause.clone(),
+                obligation.recursion_depth + 1,
                 obligation.param_env,
                 ty::PredicateKind::WellFormed(self_ty.into()).to_predicate(self.tcx()),
             ));
@@ -333,9 +342,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // relying on projections in the impl-trait-ref.
         //
         // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
-        impl_obligations.append(&mut substs.obligations);
+        substs.obligations.append(&mut impl_obligations);
 
-        ImplSourceUserDefinedData { impl_def_id, substs: substs.value, nested: impl_obligations }
+        ImplSourceUserDefinedData { impl_def_id, substs: substs.value, nested: substs.obligations }
     }
 
     fn confirm_object_candidate(
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index af90bc80d4d..0537e94cc1c 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -343,7 +343,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 Err(SelectionError::Overflow)
             }
             Err(e) => Err(e),
-            Ok(candidate) => Ok(Some(candidate)),
+            Ok(candidate) => {
+                debug!("select: candidate = {:?}", candidate);
+                Ok(Some(candidate))
+            }
         }
     }
 
@@ -413,9 +416,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         predicates: I,
     ) -> Result<EvaluationResult, OverflowError>
     where
-        I: IntoIterator<Item = PredicateObligation<'tcx>>,
+        I: IntoIterator<Item = PredicateObligation<'tcx>> + std::fmt::Debug,
     {
         let mut result = EvaluatedToOk;
+        debug!("evaluate_predicates_recursively({:?})", predicates);
         for obligation in predicates {
             let eval = self.evaluate_predicate_recursively(stack, obligation.clone())?;
             debug!("evaluate_predicate_recursively({:?}) = {:?}", obligation, eval);
@@ -436,7 +440,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         obligation: PredicateObligation<'tcx>,
     ) -> Result<EvaluationResult, OverflowError> {
         debug!(
-            "evaluate_predicate_recursively(previous_stack={:?}, obligation={:?})",
+            "evaluate_predicate_recursively(obligation={:?}, previous_stack={:?})",
             previous_stack.head(),
             obligation
         );
@@ -479,15 +483,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     self.infcx,
                     obligation.param_env,
                     obligation.cause.body_id,
+                    obligation.recursion_depth + 1,
                     arg,
                     obligation.cause.span,
                 ) {
                     Some(mut obligations) => {
                         self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
-                        self.evaluate_predicates_recursively(
-                            previous_stack,
-                            obligations.into_iter(),
-                        )
+                        self.evaluate_predicates_recursively(previous_stack, obligations)
                     }
                     None => Ok(EvaluatedToAmbig),
                 },
@@ -511,10 +513,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     match project::poly_project_and_unify_type(self, &project_obligation) {
                         Ok(Ok(Some(mut subobligations))) => {
                             self.add_depth(subobligations.iter_mut(), obligation.recursion_depth);
-                            let result = self.evaluate_predicates_recursively(
-                                previous_stack,
-                                subobligations.into_iter(),
-                            );
+                            let result = self
+                                .evaluate_predicates_recursively(previous_stack, subobligations);
                             if let Some(key) =
                                 ProjectionCacheKey::from_poly_projection_predicate(self, data)
                             {
@@ -879,10 +879,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let result = self.evaluation_probe(|this| {
             let candidate = (*candidate).clone();
             match this.confirm_candidate(stack.obligation, candidate) {
-                Ok(selection) => this.evaluate_predicates_recursively(
-                    stack.list(),
-                    selection.nested_obligations().into_iter(),
-                ),
+                Ok(selection) => {
+                    debug!("evaluate_candidate: selection = {:?}", selection);
+                    this.evaluate_predicates_recursively(
+                        stack.list(),
+                        selection.nested_obligations().into_iter(),
+                    )
+                }
                 Err(..) => Ok(EvaluatedToErr),
             }
         })?;
@@ -1231,9 +1234,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     ) -> Result<EvaluationResult, OverflowError> {
         self.evaluation_probe(|this| {
             match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
-                Ok(obligations) => {
-                    this.evaluate_predicates_recursively(stack.list(), obligations.into_iter())
-                }
+                Ok(obligations) => this.evaluate_predicates_recursively(stack.list(), obligations),
                 Err(()) => Ok(EvaluatedToErr),
             }
         })
diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs
index df816bbd348..0b4edf5e71b 100644
--- a/compiler/rustc_trait_selection/src/traits/wf.rs
+++ b/compiler/rustc_trait_selection/src/traits/wf.rs
@@ -20,6 +20,7 @@ pub fn obligations<'a, 'tcx>(
     infcx: &InferCtxt<'a, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     body_id: hir::HirId,
+    recursion_depth: usize,
     arg: GenericArg<'tcx>,
     span: Span,
 ) -> Option<Vec<traits::PredicateObligation<'tcx>>> {
@@ -59,7 +60,8 @@ pub fn obligations<'a, 'tcx>(
         GenericArgKind::Lifetime(..) => return Some(Vec::new()),
     };
 
-    let mut wf = WfPredicates { infcx, param_env, body_id, span, out: vec![], item: None };
+    let mut wf =
+        WfPredicates { infcx, param_env, body_id, span, out: vec![], recursion_depth, item: None };
     wf.compute(arg);
     debug!("wf::obligations({:?}, body_id={:?}) = {:?}", arg, body_id, wf.out);
 
@@ -80,7 +82,8 @@ pub fn trait_obligations<'a, 'tcx>(
     span: Span,
     item: Option<&'tcx hir::Item<'tcx>>,
 ) -> Vec<traits::PredicateObligation<'tcx>> {
-    let mut wf = WfPredicates { infcx, param_env, body_id, span, out: vec![], item };
+    let mut wf =
+        WfPredicates { infcx, param_env, body_id, span, out: vec![], recursion_depth: 0, item };
     wf.compute_trait_ref(trait_ref, Elaborate::All);
     wf.normalize()
 }
@@ -92,7 +95,15 @@ pub fn predicate_obligations<'a, 'tcx>(
     predicate: ty::Predicate<'tcx>,
     span: Span,
 ) -> Vec<traits::PredicateObligation<'tcx>> {
-    let mut wf = WfPredicates { infcx, param_env, body_id, span, out: vec![], item: None };
+    let mut wf = WfPredicates {
+        infcx,
+        param_env,
+        body_id,
+        span,
+        out: vec![],
+        recursion_depth: 0,
+        item: None,
+    };
 
     // It's ok to skip the binder here because wf code is prepared for it
     match predicate.skip_binders() {
@@ -142,6 +153,7 @@ struct WfPredicates<'a, 'tcx> {
     body_id: hir::HirId,
     span: Span,
     out: Vec<traits::PredicateObligation<'tcx>>,
+    recursion_depth: usize,
     item: Option<&'tcx hir::Item<'tcx>>,
 }
 
@@ -249,19 +261,19 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
         for mut obligation in self.out {
             assert!(!obligation.has_escaping_bound_vars());
             let mut selcx = traits::SelectionContext::new(infcx);
-            let i = obligations.len();
             // Don't normalize the whole obligation, the param env is either
             // already normalized, or we're currently normalizing the
             // param_env. Either way we should only normalize the predicate.
-            let normalized_predicate = traits::normalize_to(
+            let normalized_predicate = traits::project::normalize_with_depth_to(
                 &mut selcx,
                 param_env,
                 cause.clone(),
+                self.recursion_depth,
                 &obligation.predicate,
                 &mut obligations,
             );
             obligation.predicate = normalized_predicate;
-            obligations.insert(i, obligation);
+            obligations.push(obligation);
         }
         obligations
     }
@@ -274,6 +286,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
         debug!("compute_trait_ref obligations {:?}", obligations);
         let cause = self.cause(traits::MiscObligation);
         let param_env = self.param_env;
+        let depth = self.recursion_depth;
 
         let item = self.item;
 
@@ -295,7 +308,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 &obligation.predicate,
                 tcx.associated_items(trait_ref.def_id).in_definition_order(),
             );
-            traits::Obligation::new(cause, param_env, obligation.predicate)
+            traits::Obligation::with_depth(cause, depth, param_env, obligation.predicate)
         };
 
         if let Elaborate::All = elaborate {
@@ -324,8 +337,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                             new_cause.make_mut().span = self_ty.span;
                         }
                     }
-                    traits::Obligation::new(
+                    traits::Obligation::with_depth(
                         new_cause,
+                        depth,
                         param_env,
                         ty::PredicateAtom::WellFormed(arg).to_predicate(tcx),
                     )
@@ -363,6 +377,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
         let tcx = self.tcx();
         let cause = self.cause(traits::MiscObligation);
         let param_env = self.param_env;
+        let depth = self.recursion_depth;
 
         self.out.extend(
             data.substs
@@ -372,8 +387,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 })
                 .filter(|arg| !arg.has_escaping_bound_vars())
                 .map(|arg| {
-                    traits::Obligation::new(
+                    traits::Obligation::with_depth(
                         cause.clone(),
+                        depth,
                         param_env,
                         ty::PredicateKind::WellFormed(arg).to_predicate(tcx),
                     )
@@ -388,8 +404,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 def_id: self.infcx.tcx.require_lang_item(LangItem::Sized, None),
                 substs: self.infcx.tcx.mk_substs_trait(subty, &[]),
             };
-            self.out.push(traits::Obligation::new(
+            self.out.push(traits::Obligation::with_depth(
                 cause,
+                self.recursion_depth,
                 self.param_env,
                 trait_ref.without_const().to_predicate(self.infcx.tcx),
             ));
@@ -400,6 +417,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
     fn compute(&mut self, arg: GenericArg<'tcx>) {
         let mut walker = arg.walk();
         let param_env = self.param_env;
+        let depth = self.recursion_depth;
         while let Some(arg) = walker.next() {
             let ty = match arg.unpack() {
                 GenericArgKind::Type(ty) => ty,
@@ -419,8 +437,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                             let predicate = ty::PredicateAtom::ConstEvaluatable(def, substs)
                                 .to_predicate(self.tcx());
                             let cause = self.cause(traits::MiscObligation);
-                            self.out.push(traits::Obligation::new(
+                            self.out.push(traits::Obligation::with_depth(
                                 cause,
+                                self.recursion_depth,
                                 self.param_env,
                                 predicate,
                             ));
@@ -435,8 +454,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                                     val: ty::ConstKind::Infer(resolved),
                                     ..*constant
                                 });
-                                self.out.push(traits::Obligation::new(
+                                self.out.push(traits::Obligation::with_depth(
                                     cause,
+                                    self.recursion_depth,
                                     self.param_env,
                                     ty::PredicateAtom::WellFormed(resolved_constant.into())
                                         .to_predicate(self.tcx()),
@@ -521,8 +541,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                     // WfReference
                     if !r.has_escaping_bound_vars() && !rty.has_escaping_bound_vars() {
                         let cause = self.cause(traits::ReferenceOutlivesReferent(ty));
-                        self.out.push(traits::Obligation::new(
+                        self.out.push(traits::Obligation::with_depth(
                             cause,
+                            depth,
                             param_env,
                             ty::PredicateAtom::TypeOutlives(ty::OutlivesPredicate(rty, r))
                                 .to_predicate(self.tcx()),
@@ -612,8 +633,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                         let component_traits = data.auto_traits().chain(data.principal_def_id());
                         let tcx = self.tcx();
                         self.out.extend(component_traits.map(|did| {
-                            traits::Obligation::new(
+                            traits::Obligation::with_depth(
                                 cause.clone(),
+                                depth,
                                 param_env,
                                 ty::PredicateAtom::ObjectSafe(did).to_predicate(tcx),
                             )
@@ -638,8 +660,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                     if let ty::Infer(ty::TyVar(_)) = ty.kind() {
                         // Not yet resolved, but we've made progress.
                         let cause = self.cause(traits::MiscObligation);
-                        self.out.push(traits::Obligation::new(
+                        self.out.push(traits::Obligation::with_depth(
                             cause,
+                            self.recursion_depth,
                             param_env,
                             ty::PredicateAtom::WellFormed(ty.into()).to_predicate(self.tcx()),
                         ));
@@ -676,7 +699,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
             .zip(origins.into_iter().rev())
             .map(|((pred, span), origin_def_id)| {
                 let cause = self.cause(traits::BindingObligation(origin_def_id, span));
-                traits::Obligation::new(cause, self.param_env, pred)
+                traits::Obligation::with_depth(cause, self.recursion_depth, self.param_env, pred)
             })
             .filter(|pred| !pred.has_escaping_bound_vars())
             .collect()
@@ -729,8 +752,9 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 let cause = self.cause(traits::ObjectTypeBound(ty, explicit_bound));
                 let outlives =
                     ty::Binder::dummy(ty::OutlivesPredicate(explicit_bound, implicit_bound));
-                self.out.push(traits::Obligation::new(
+                self.out.push(traits::Obligation::with_depth(
                     cause,
+                    self.recursion_depth,
                     self.param_env,
                     outlives.to_predicate(self.infcx.tcx),
                 ));
diff --git a/compiler/rustc_traits/src/implied_outlives_bounds.rs b/compiler/rustc_traits/src/implied_outlives_bounds.rs
index 79308b032ec..bc5c07fce04 100644
--- a/compiler/rustc_traits/src/implied_outlives_bounds.rs
+++ b/compiler/rustc_traits/src/implied_outlives_bounds.rs
@@ -61,8 +61,8 @@ fn compute_implied_outlives_bounds<'tcx>(
         // than the ultimate set. (Note: normally there won't be
         // unresolved inference variables here anyway, but there might be
         // during typeck under some circumstances.)
-        let obligations =
-            wf::obligations(infcx, param_env, hir::CRATE_HIR_ID, arg, DUMMY_SP).unwrap_or(vec![]);
+        let obligations = wf::obligations(infcx, param_env, hir::CRATE_HIR_ID, 0, arg, DUMMY_SP)
+            .unwrap_or(vec![]);
 
         // N.B., all of these predicates *ought* to be easily proven
         // true. In fact, their correctness is (mostly) implied by
diff --git a/compiler/rustc_typeck/src/check/check.rs b/compiler/rustc_typeck/src/check/check.rs
index fbb19617c7f..cfd75db61f7 100644
--- a/compiler/rustc_typeck/src/check/check.rs
+++ b/compiler/rustc_typeck/src/check/check.rs
@@ -561,7 +561,7 @@ fn check_opaque_meets_bounds<'tcx>(
         let misc_cause = traits::ObligationCause::misc(span, hir_id);
 
         let (_, opaque_type_map) = inh.register_infer_ok_obligations(
-            infcx.instantiate_opaque_types(def_id.to_def_id(), hir_id, param_env, &opaque_ty, span),
+            infcx.instantiate_opaque_types(def_id, hir_id, param_env, &opaque_ty, span),
         );
 
         for (def_id, opaque_defn) in opaque_type_map {
diff --git a/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs b/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs
index 60b9467fca8..4cf3efcf513 100644
--- a/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs
+++ b/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs
@@ -337,6 +337,7 @@ fn check_predicates<'tcx>(
             infcx,
             tcx.param_env(impl1_def_id),
             tcx.hir().local_def_id_to_hir_id(impl1_def_id),
+            0,
             arg,
             span,
         ) {
diff --git a/src/test/ui/impl-trait/wf-eval-order.rs b/src/test/ui/impl-trait/wf-eval-order.rs
new file mode 100644
index 00000000000..c7d6bb87096
--- /dev/null
+++ b/src/test/ui/impl-trait/wf-eval-order.rs
@@ -0,0 +1,39 @@
+// Check that we handle evaluating `wf` predicates correctly.
+
+// check-pass
+
+struct X<T: B>(T)
+where
+    T::V: Clone;
+
+fn hide<T>(t: T) -> impl Sized {
+    t
+}
+
+trait A {
+    type U;
+}
+
+impl<T> A for T {
+    type U = T;
+}
+
+trait B {
+    type V;
+}
+
+impl<S: A<U = T>, T> B for S {
+    type V = T;
+}
+
+fn main() {
+    // Evaluating `typeof(x): Sized` requires
+    //
+    // - `wf(typeof(x))` because we use a projection candidate.
+    // - `<i32 as B>::V: Clone` because that's a bound on the trait.
+    // - `<i32 as B>::V` normalizes to `_#1` where `<i32 as A>::U == _#1`
+    //
+    // This all works if we evaluate `<i32 as A>::U == _#1` before
+    // `<i32 as B>::V`, but we previously had the opposite order.
+    let x = hide(X(0));
+}