make evaluation track whether outlives relationships mattered

Previously, evaluation ignored outlives relationships. Since we using
evaluation to skip the "normal" trait selection (which enforces
outlives relationships) this led to incorrect results in some cases.

10 files changed, 129 insertions, 126 deletions

diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index c000e3aa013..2eb9f1d6784 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -1455,7 +1455,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         // rightly refuses to work with inference variables, but
         // moves_by_default has a cache, which we want to use in other
         // cases.
-        !traits::type_known_to_meet_bound(self, param_env, ty, copy_def_id, span)
+        !traits::type_known_to_meet_bound_modulo_regions(self, param_env, ty, copy_def_id, span)
     }
 
     /// Obtains the latest type of the given closure; this may be a
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 556b97dc9bc..219e971b3c9 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -282,7 +282,7 @@ impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx,
                 if data.is_global() {
                     // no type variables present, can use evaluation for better caching.
                     // FIXME: consider caching errors too.
-                    if self.selcx.infcx().predicate_must_hold(&obligation) {
+                    if self.selcx.infcx().predicate_must_hold_considering_regions(&obligation) {
                         debug!("selecting trait `{:?}` at depth {} evaluated to holds",
                                data, obligation.recursion_depth);
                         return ProcessResult::Changed(vec![])
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 49bd04782b2..0377b98d3f8 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -628,14 +628,14 @@ pub fn predicates_for_generics<'tcx>(cause: ObligationCause<'tcx>,
 /// `bound` or is not known to meet bound (note that this is
 /// conservative towards *no impl*, which is the opposite of the
 /// `evaluate` methods).
-pub fn type_known_to_meet_bound<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                                param_env: ty::ParamEnv<'tcx>,
-                                                ty: Ty<'tcx>,
-                                                def_id: DefId,
-                                                span: Span)
--> bool
-{
-    debug!("type_known_to_meet_bound(ty={:?}, bound={:?})",
+pub fn type_known_to_meet_bound_modulo_regions<'a, 'gcx, 'tcx>(
+    infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    ty: Ty<'tcx>,
+    def_id: DefId,
+    span: Span,
+) -> bool {
+    debug!("type_known_to_meet_bound_modulo_regions(ty={:?}, bound={:?})",
            ty,
            infcx.tcx.item_path_str(def_id));
 
@@ -650,7 +650,7 @@ pub fn type_known_to_meet_bound<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx
         predicate: trait_ref.to_predicate(),
     };
 
-    let result = infcx.predicate_must_hold(&obligation);
+    let result = infcx.predicate_must_hold_modulo_regions(&obligation);
     debug!("type_known_to_meet_ty={:?} bound={} => {:?}",
            ty, infcx.tcx.item_path_str(def_id), result);
 
@@ -677,13 +677,13 @@ pub fn type_known_to_meet_bound<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx
         // assume it is move; linear is always ok.
         match fulfill_cx.select_all_or_error(infcx) {
             Ok(()) => {
-                debug!("type_known_to_meet_bound: ty={:?} bound={} success",
+                debug!("type_known_to_meet_bound_modulo_regions: ty={:?} bound={} success",
                        ty,
                        infcx.tcx.item_path_str(def_id));
                 true
             }
             Err(e) => {
-                debug!("type_known_to_meet_bound: ty={:?} bound={} errors={:?}",
+                debug!("type_known_to_meet_bound_modulo_regions: ty={:?} bound={} errors={:?}",
                        ty,
                        infcx.tcx.item_path_str(def_id),
                        e);
diff --git a/src/librustc/traits/object_safety.rs b/src/librustc/traits/object_safety.rs
index 1554afdeefd..31342c250e2 100644
--- a/src/librustc/traits/object_safety.rs
+++ b/src/librustc/traits/object_safety.rs
@@ -568,7 +568,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
 
         self.infer_ctxt().enter(|ref infcx| {
             // the receiver is dispatchable iff the obligation holds
-            infcx.predicate_must_hold(&obligation)
+            infcx.predicate_must_hold_modulo_regions(&obligation)
         })
     }
 
diff --git a/src/librustc/traits/query/evaluate_obligation.rs b/src/librustc/traits/query/evaluate_obligation.rs
index 4c1d65c46c5..fdae7d83373 100644
--- a/src/librustc/traits/query/evaluate_obligation.rs
+++ b/src/librustc/traits/query/evaluate_obligation.rs
@@ -16,11 +16,26 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
     /// Evaluates whether the predicate can be satisfied in the given
     /// `ParamEnv`, and returns `false` if not certain. However, this is
     /// not entirely accurate if inference variables are involved.
-    pub fn predicate_must_hold(
+    ///
+    /// This version may conservatively fail when outlives obligations
+    /// are required.
+    pub fn predicate_must_hold_considering_regions(
         &self,
         obligation: &PredicateObligation<'tcx>,
     ) -> bool {
-        self.evaluate_obligation_no_overflow(obligation) == EvaluationResult::EvaluatedToOk
+        self.evaluate_obligation_no_overflow(obligation).must_apply_considering_regions()
+    }
+
+    /// Evaluates whether the predicate can be satisfied in the given
+    /// `ParamEnv`, and returns `false` if not certain. However, this is
+    /// not entirely accurate if inference variables are involved.
+    ///
+    /// This version ignores all outlives constraints.
+    pub fn predicate_must_hold_modulo_regions(
+        &self,
+        obligation: &PredicateObligation<'tcx>,
+    ) -> bool {
+        self.evaluate_obligation_no_overflow(obligation).must_apply_modulo_regions()
     }
 
     /// Evaluate a given predicate, capturing overflow and propagating it back.
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index e7c01df3dca..6b4c3469acd 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -327,7 +327,8 @@ enum BuiltinImplConditions<'tcx> {
 /// evaluations.
 ///
 /// The evaluation results are ordered:
-///     - `EvaluatedToOk` implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
+///     - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
+///       implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
 ///     - `EvaluatedToErr` implies `EvaluatedToRecur`
 ///     - the "union" of evaluation results is equal to their maximum -
 ///     all the "potential success" candidates can potentially succeed,
@@ -336,6 +337,8 @@ enum BuiltinImplConditions<'tcx> {
 pub enum EvaluationResult {
     /// Evaluation successful
     EvaluatedToOk,
+    /// Evaluation successful, but there were unevaluated region obligations
+    EvaluatedToOkModuloRegions,
     /// Evaluation is known to be ambiguous - it *might* hold for some
     /// assignment of inference variables, but it might not.
     ///
@@ -399,9 +402,23 @@ pub enum EvaluationResult {
 }
 
 impl EvaluationResult {
+    /// True if this evaluation result is known to apply, even
+    /// considering outlives constraints.
+    pub fn must_apply_considering_regions(self) -> bool {
+        self == EvaluatedToOk
+    }
+
+    /// True if this evaluation result is known to apply, ignoring
+    /// outlives constraints.
+    pub fn must_apply_modulo_regions(self) -> bool {
+        self <= EvaluatedToOkModuloRegions
+    }
+
     pub fn may_apply(self) -> bool {
         match self {
-            EvaluatedToOk | EvaluatedToAmbig | EvaluatedToUnknown => true,
+            EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToUnknown => {
+                true
+            }
 
             EvaluatedToErr | EvaluatedToRecur => false,
         }
@@ -411,13 +428,14 @@ impl EvaluationResult {
         match self {
             EvaluatedToUnknown | EvaluatedToRecur => true,
 
-            EvaluatedToOk | EvaluatedToAmbig | EvaluatedToErr => false,
+            EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToErr => false,
         }
     }
 }
 
 impl_stable_hash_for!(enum self::EvaluationResult {
     EvaluatedToOk,
+    EvaluatedToOkModuloRegions,
     EvaluatedToAmbig,
     EvaluatedToUnknown,
     EvaluatedToRecur,
@@ -686,92 +704,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 None => Ok(EvaluatedToAmbig),
             },
 
-            ty::Predicate::TypeOutlives(ref binder) => {
-                assert!(!binder.has_escaping_bound_vars());
-                // Check if the type has higher-ranked vars.
-                if binder.skip_binder().0.has_escaping_bound_vars() {
-                    // 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`.
-
-                    // NOTE: this hack is implemented in both trait fulfillment and
-                    // evaluation. If you fix it in one place, make sure you fix it
-                    // in the other.
-
-                    // We don't want to allow this sort of reasoning in intercrate
-                    // mode, for backwards-compatibility reasons.
-                    if self.intercrate.is_some() {
-                        Ok(EvaluatedToAmbig)
-                    } else {
-                        Ok(EvaluatedToErr)
-                    }
-                } else {
-                    // If the type has no late bound vars, then if we assign all
-                    // the inference variables in it to be 'static, then the type
-                    // will be 'static itself.
-                    //
-                    // Therefore, `staticize(T): 'a` holds for any `'a`, so this
-                    // obligation is fulfilled. Because evaluation works with
-                    // staticized types (yes I know this is involved with #21974),
-                    // we are 100% OK here.
-                    Ok(EvaluatedToOk)
-                }
-            }
-
-            ty::Predicate::RegionOutlives(ref binder) => {
-                let ty::OutlivesPredicate(r_a, r_b) = binder.skip_binder();
-
-                if r_a == r_b {
-                    // for<'a> 'a: 'a. OK
-                    Ok(EvaluatedToOk)
-                } else if **r_a == ty::ReStatic {
-                    // 'static: 'x always holds.
-                    //
-                    // This special case is handled somewhat inconsistently - if we
-                    // have an inference variable that is supposed to be equal to
-                    // `'static`, then we don't allow it to be equated to an LBR,
-                    // but if we have a literal `'static`, then we *do*.
-                    //
-                    // This is actually consistent with how our region inference works.
-                    //
-                    // It would appear that this sort of inconsistency would
-                    // cause "instability" problems with evaluation caching. However,
-                    // evaluation caching is only for trait predicates, and when
-                    // trait predicates create nested obligations, they contain
-                    // inference variables for all the regions in the trait - the
-                    // only way this codepath can be reached from trait predicate
-                    // evaluation is when the user typed an explicit `where 'static: 'a`
-                    // lifetime bound (in which case we want to return EvaluatedToOk).
-                    //
-                    // If we ever want to handle inference variables that might be
-                    // equatable with ReStatic, we need to make sure we are not confused by
-                    // technically-allowed-by-RFC-447-but-probably-should-not-be
-                    // impls such as
-                    // ```Rust
-                    // impl<'a, 's, T> X<'s> for T where T: Debug + 'a, 'a: 's
-                    // ```
-                    Ok(EvaluatedToOk)
-                } else if r_a.is_late_bound() || r_b.is_late_bound() {
-                    // There is no current way to prove `for<'a> 'a: 'x`
-                    // unless `'a = 'x`, because there are no bounds involving
-                    // lifetimes.
-
-                    // It might be possible to prove `for<'a> 'x: 'a` by forcing `'x`
-                    // to be `'static`. However, this is not currently done by type
-                    // inference unless `'x` is literally ReStatic. See the comment
-                    // above.
-
-                    // We don't want to allow this sort of reasoning in intercrate
-                    // mode, for backwards-compatibility reasons.
-                    if self.intercrate.is_some() {
-                        Ok(EvaluatedToAmbig)
-                    } else {
-                        Ok(EvaluatedToErr)
-                    }
-                } else {
-                    // Relating 2 inference variable regions. These will
-                    // always hold if our query is "staticized".
-                    Ok(EvaluatedToOk)
-                }
+            ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
+                // we do not consider region relationships when
+                // evaluating trait matches
+                Ok(EvaluatedToOkModuloRegions)
             }
 
             ty::Predicate::ObjectSafe(trait_def_id) => {
@@ -985,6 +921,11 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         {
             debug!("evaluate_stack({:?}) --> recursive", stack.fresh_trait_ref);
 
+            // Subtle: when checking for a coinductive cycle, we do
+            // not compare using the "freshened trait refs" (which
+            // have erased regions) but rather the fully explicit
+            // trait refs. This is important because it's only a cycle
+            // if the regions match exactly.
             let cycle = stack.iter().skip(1).take(rec_index + 1);
             let cycle = cycle.map(|stack| ty::Predicate::Trait(stack.obligation.predicate));
             if self.coinductive_match(cycle) {
@@ -2324,7 +2265,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 // See if we can toss out `victim` based on specialization.
                 // This requires us to know *for sure* that the `other` impl applies
                 // i.e., EvaluatedToOk:
-                if other.evaluation == EvaluatedToOk {
+                if other.evaluation.must_apply_modulo_regions() {
                     match victim.candidate {
                         ImplCandidate(victim_def) => {
                             let tcx = self.tcx().global_tcx();
@@ -2351,7 +2292,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     ParamCandidate(ref cand) => {
                         // Prefer these to a global where-clause bound
                         // (see issue #50825)
-                        is_global(cand) && other.evaluation == EvaluatedToOk
+                        is_global(cand) && other.evaluation.must_apply_modulo_regions()
                     }
                     _ => false,
                 }
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index 1d30ccb87b5..0fa4c98be63 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -851,11 +851,13 @@ fn is_copy_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let (param_env, ty) = query.into_parts();
     let trait_def_id = tcx.require_lang_item(lang_items::CopyTraitLangItem);
     tcx.infer_ctxt()
-       .enter(|infcx| traits::type_known_to_meet_bound(&infcx,
-                                                       param_env,
-                                                       ty,
-                                                       trait_def_id,
-                                                       DUMMY_SP))
+        .enter(|infcx| traits::type_known_to_meet_bound_modulo_regions(
+            &infcx,
+            param_env,
+            ty,
+            trait_def_id,
+            DUMMY_SP,
+        ))
 }
 
 fn is_sized_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
@@ -865,11 +867,13 @@ fn is_sized_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let (param_env, ty) = query.into_parts();
     let trait_def_id = tcx.require_lang_item(lang_items::SizedTraitLangItem);
     tcx.infer_ctxt()
-       .enter(|infcx| traits::type_known_to_meet_bound(&infcx,
-                                                       param_env,
-                                                       ty,
-                                                       trait_def_id,
-                                                       DUMMY_SP))
+        .enter(|infcx| traits::type_known_to_meet_bound_modulo_regions(
+            &infcx,
+            param_env,
+            ty,
+            trait_def_id,
+            DUMMY_SP,
+        ))
 }
 
 fn is_freeze_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
@@ -879,11 +883,13 @@ fn is_freeze_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let (param_env, ty) = query.into_parts();
     let trait_def_id = tcx.require_lang_item(lang_items::FreezeTraitLangItem);
     tcx.infer_ctxt()
-       .enter(|infcx| traits::type_known_to_meet_bound(&infcx,
-                                                       param_env,
-                                                       ty,
-                                                       trait_def_id,
-                                                       DUMMY_SP))
+        .enter(|infcx| traits::type_known_to_meet_bound_modulo_regions(
+            &infcx,
+            param_env,
+            ty,
+            trait_def_id,
+            DUMMY_SP,
+        ))
 }
 
 fn needs_drop_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
diff --git a/src/librustc_typeck/check/cast.rs b/src/librustc_typeck/check/cast.rs
index 6ad707e3d2c..9d418704f48 100644
--- a/src/librustc_typeck/check/cast.rs
+++ b/src/librustc_typeck/check/cast.rs
@@ -88,7 +88,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             return Err(ErrorReported);
         }
 
-        if self.type_is_known_to_be_sized(t, span) {
+        if self.type_is_known_to_be_sized_modulo_regions(t, span) {
             return Ok(Some(PointerKind::Thin));
         }
 
@@ -397,7 +397,7 @@ impl<'a, 'gcx, 'tcx> CastCheck<'tcx> {
                self.expr_ty,
                self.cast_ty);
 
-        if !fcx.type_is_known_to_be_sized(self.cast_ty, self.span) {
+        if !fcx.type_is_known_to_be_sized_modulo_regions(self.cast_ty, self.span) {
             self.report_cast_to_unsized_type(fcx);
         } else if self.expr_ty.references_error() || self.cast_ty.references_error() {
             // No sense in giving duplicate error messages
@@ -618,8 +618,8 @@ impl<'a, 'gcx, 'tcx> CastCheck<'tcx> {
 }
 
 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
-    fn type_is_known_to_be_sized(&self, ty: Ty<'tcx>, span: Span) -> bool {
+    fn type_is_known_to_be_sized_modulo_regions(&self, ty: Ty<'tcx>, span: Span) -> bool {
         let lang_item = self.tcx.require_lang_item(lang_items::SizedTraitLangItem);
-        traits::type_known_to_meet_bound(self, self.param_env, ty, lang_item, span)
+        traits::type_known_to_meet_bound_modulo_regions(self, self.param_env, ty, lang_item, span)
     }
 }
diff --git a/src/test/ui/hrtb/hrtb-cache-issue-54302.rs b/src/test/ui/hrtb/hrtb-cache-issue-54302.rs
new file mode 100644
index 00000000000..a20d03c7747
--- /dev/null
+++ b/src/test/ui/hrtb/hrtb-cache-issue-54302.rs
@@ -0,0 +1,24 @@
+// Regression test for #54302.
+//
+// We were incorrectly using the "evaluation cache" (which ignored
+// region results) to conclude that `&'static str: Deserialize`, even
+// though it would require that `for<'de> 'de: 'static`, which is
+// clearly false.
+
+trait Deserialize<'de> {}
+
+trait DeserializeOwned: for<'de> Deserialize<'de> {}
+impl<T> DeserializeOwned for T where T: for<'de> Deserialize<'de> {}
+
+// Based on this impl, `&'static str` only implements Deserialize<'static>.
+// It does not implement for<'de> Deserialize<'de>.
+impl<'de: 'a, 'a> Deserialize<'de> for &'a str {}
+
+fn main() {
+    fn assert_deserialize_owned<T: DeserializeOwned>() {}
+    assert_deserialize_owned::<&'static str>(); //~ ERROR
+
+    // It correctly does not implement for<'de> Deserialize<'de>.
+    // fn assert_hrtb<T: for<'de> Deserialize<'de>>() {}
+    // assert_hrtb::<&'static str>();
+}
diff --git a/src/test/ui/hrtb/hrtb-cache-issue-54302.stderr b/src/test/ui/hrtb/hrtb-cache-issue-54302.stderr
new file mode 100644
index 00000000000..061d0e309c5
--- /dev/null
+++ b/src/test/ui/hrtb/hrtb-cache-issue-54302.stderr
@@ -0,0 +1,17 @@
+error[E0279]: the requirement `for<'de> 'de : ` is not satisfied (`expected bound lifetime parameter 'de, found concrete lifetime`)
+  --> $DIR/hrtb-cache-issue-54302.rs:19:5
+   |
+LL |     assert_deserialize_owned::<&'static str>(); //~ ERROR
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `for<'de> Deserialize<'de>` for `&'static str`
+   = note: required because of the requirements on the impl of `DeserializeOwned` for `&'static str`
+note: required by `main::assert_deserialize_owned`
+  --> $DIR/hrtb-cache-issue-54302.rs:18:5
+   |
+LL |     fn assert_deserialize_owned<T: DeserializeOwned>() {}
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0279`.