Instead of checking for exact bounds, try to prove them

7 files changed, 213 insertions, 77 deletions

diff --git a/compiler/rustc_infer/src/infer/free_regions.rs b/compiler/rustc_infer/src/infer/free_regions.rs
index 4814b65e320..e93cdf79421 100644
--- a/compiler/rustc_infer/src/infer/free_regions.rs
+++ b/compiler/rustc_infer/src/infer/free_regions.rs
@@ -11,7 +11,7 @@ use rustc_middle::ty::{self, Lift, Region, TyCtxt};
 ///
 /// This stuff is a bit convoluted and should be refactored, but as we
 /// transition to NLL, it'll all go away anyhow.
-pub struct RegionRelations<'a, 'tcx> {
+pub(crate) struct RegionRelations<'a, 'tcx> {
     pub tcx: TyCtxt<'tcx>,
 
     /// The context used for debug messages
diff --git a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs
index 85ee6d2cdc2..a5ec84a4f14 100644
--- a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs
+++ b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs
@@ -28,7 +28,7 @@ use std::fmt;
 /// assuming such values can be found. It returns the final values of
 /// all the variables as well as a set of errors that must be reported.
 #[instrument(level = "debug", skip(region_rels, var_infos, data))]
-pub fn resolve<'tcx>(
+pub(crate) fn resolve<'tcx>(
     region_rels: &RegionRelations<'_, 'tcx>,
     var_infos: VarInfos,
     data: RegionConstraintData<'tcx>,
diff --git a/compiler/rustc_typeck/src/check/wfcheck.rs b/compiler/rustc_typeck/src/check/wfcheck.rs
index 3fd3284d8b1..6fba3d3ad08 100644
--- a/compiler/rustc_typeck/src/check/wfcheck.rs
+++ b/compiler/rustc_typeck/src/check/wfcheck.rs
@@ -14,8 +14,9 @@ use rustc_hir::lang_items::LangItem;
 use rustc_hir::ItemKind;
 use rustc_infer::infer::outlives::env::OutlivesEnvironment;
 use rustc_infer::infer::outlives::obligations::TypeOutlives;
-use rustc_infer::infer::TyCtxtInferExt;
 use rustc_infer::infer::{self, RegionckMode, SubregionOrigin};
+use rustc_infer::infer::{RegionResolutionError, TyCtxtInferExt};
+use rustc_infer::traits::TraitEngine;
 use rustc_middle::hir::map as hir_map;
 use rustc_middle::ty::subst::{GenericArgKind, InternalSubsts, Subst};
 use rustc_middle::ty::trait_def::TraitSpecializationKind;
@@ -26,7 +27,9 @@ use rustc_session::parse::feature_err;
 use rustc_span::symbol::{sym, Ident, Symbol};
 use rustc_span::{Span, DUMMY_SP};
 use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt as _;
-use rustc_trait_selection::traits::{self, ObligationCause, ObligationCauseCode, WellFormedLoc};
+use rustc_trait_selection::traits::{
+    self, ObligationCause, ObligationCauseCode, TraitEngineExt, WellFormedLoc,
+};
 
 use std::convert::TryInto;
 use std::iter;
@@ -426,42 +429,105 @@ fn check_gat_where_clauses(
         }
     }
 
-    // If there are any missing clauses, emit an error
-    let mut clauses = clauses.unwrap_or_default();
+    // If there are any clauses that aren't provable, emit an error
+    let clauses = clauses.unwrap_or_default();
     debug!(?clauses);
     if !clauses.is_empty() {
-        let written_predicates: ty::GenericPredicates<'_> =
-            tcx.explicit_predicates_of(trait_item.def_id);
-        let mut clauses: Vec<_> = clauses
-            .drain_filter(|clause| !written_predicates.predicates.iter().any(|p| &p.0 == clause))
-            .map(|clause| format!("{}", clause))
-            .collect();
-        // We sort so that order is predictable
-        clauses.sort();
-        if !clauses.is_empty() {
-            let mut err = tcx.sess.struct_span_err(
-                trait_item.span,
-                &format!("Missing required bounds on {}", trait_item.ident),
-            );
+        let param_env = tcx.param_env(trait_item.def_id);
 
-            let suggestion = format!(
-                "{} {}",
-                if !trait_item.generics.where_clause.predicates.is_empty() {
-                    ","
-                } else {
-                    " where"
-                },
-                clauses.join(", "),
-            );
-            err.span_suggestion(
-                trait_item.generics.where_clause.tail_span_for_suggestion(),
-                "add the required where clauses",
-                suggestion,
-                Applicability::MachineApplicable,
-            );
+        // This shouldn't really matter, but we need it
+        let cause = traits::ObligationCause::new(
+            trait_item.span,
+            trait_item.hir_id(),
+            ObligationCauseCode::MiscObligation,
+        );
+        // Create an `InferCtxt` to try to prove the clauses we require
+        tcx.infer_ctxt().enter(|infcx| {
+            let mut fulfillment_cx = <dyn TraitEngine<'_>>::new(tcx);
+
+            // Register all the clauses as obligations
+            clauses
+                .clone()
+                .into_iter()
+                .map(|predicate| {
+                    traits::Obligation::new(
+                        cause.clone(),
+                        param_env,
+                        predicate,
+                    )
+                })
+                .for_each(|obligation| {
+                    fulfillment_cx.register_predicate_obligation(&infcx, obligation)
+                });
+
+            // Convert these obligations into constraints by selecting
+            let errors = fulfillment_cx.select_all_or_error(&infcx);
+            if !errors.is_empty() {
+                bug!("should have only registered region obligations, which get registerd as constraints");
+            }
 
-            err.emit()
-        }
+            // FIXME(jackh726): some of this code is shared with `regionctxt`, but in a different
+            // flow; we could probably better extract the shared logic
+
+            // Process the region obligations
+            let body_id_map = infcx
+                .inner
+                .borrow()
+                .region_obligations()
+                .iter()
+                .map(|&(id, _)| (id, vec![]))
+                .collect();
+
+            infcx.process_registered_region_obligations(&body_id_map, None, param_env);
+
+            // Resolve the region constraints to find any constraints that we're provable
+            let outlives_env = OutlivesEnvironment::new(param_env);
+            let errors = infcx.resolve_regions(trait_item.def_id.to_def_id(), &outlives_env, RegionckMode::default());
+
+            // Emit an error if there are non-provable constriants
+            if !errors.is_empty() {
+                let mut clauses: Vec<_> = errors.into_iter().map(|error| match error {
+                    RegionResolutionError::ConcreteFailure(_, sup, sub) => format!("{}: {}", sub, sup),
+                    RegionResolutionError::GenericBoundFailure(_, sub, sup) => format!("{}: {}", sub, sup),
+                    _ => bug!("Unexpected region resolution error when resolving outlives lint"),
+                }).collect();
+                clauses.sort();
+
+                let plural = if clauses.len() > 1 { "s" } else { "" };
+                let mut err = tcx.sess.struct_span_err(
+                    trait_item.span,
+                    &format!("missing required bound{} on `{}`", plural, trait_item.ident),
+                );
+
+                let suggestion = format!(
+                    "{} {}",
+                    if !trait_item.generics.where_clause.predicates.is_empty() {
+                        ","
+                    } else {
+                        " where"
+                    },
+                    clauses.join(", "),
+                );
+                err.span_suggestion(
+                    trait_item.generics.where_clause.tail_span_for_suggestion(),
+                    &format!("add the required where clause{}", plural),
+                    suggestion,
+                    Applicability::MachineApplicable,
+                );
+
+                let bound = if clauses.len() > 1 { "these bounds are" } else { "this bound is" };
+                err.note(
+                    &format!("{} required to ensure that impls have maximum flexibility", bound)
+                );
+                err.note(
+                    "see issue #87479 \
+                     <https://github.com/rust-lang/rust/issues/87479> \
+                     for more information",
+                );
+
+                err.emit()
+            }
+        });
     }
 }
 
@@ -541,7 +607,8 @@ fn region_known_to_outlive<'tcx>(
         });
 
         use rustc_infer::infer::outlives::obligations::TypeOutlivesDelegate;
-        (&infcx).push_sub_region_constraint(origin, region_a, region_b);
+        // `region_a: region_b` -> `region_b <= region_a`
+        (&infcx).push_sub_region_constraint(origin, region_b, region_a);
 
         let errors = infcx.resolve_regions(
             id.expect_owner().to_def_id(),
diff --git a/src/test/ui/generic-associated-types/issue-86787.rs b/src/test/ui/generic-associated-types/issue-86787.rs
index 0f62f83e256..5863bac2f9d 100644
--- a/src/test/ui/generic-associated-types/issue-86787.rs
+++ b/src/test/ui/generic-associated-types/issue-86787.rs
@@ -9,7 +9,7 @@ enum Either<L, R> {
 pub trait HasChildrenOf {
     type T;
     type TRef<'a>;
-    //~^ Missing required bounds
+    //~^ missing required
 
     fn ref_children<'a>(&'a self) -> Vec<Self::TRef<'a>>;
     fn take_children(self) -> Vec<Self::T>;
diff --git a/src/test/ui/generic-associated-types/issue-86787.stderr b/src/test/ui/generic-associated-types/issue-86787.stderr
index 87dcd875de7..18b1c22685b 100644
--- a/src/test/ui/generic-associated-types/issue-86787.stderr
+++ b/src/test/ui/generic-associated-types/issue-86787.stderr
@@ -1,10 +1,13 @@
-error: Missing required bounds on TRef
+error: missing required bound on `TRef`
   --> $DIR/issue-86787.rs:11:5
    |
 LL |     type TRef<'a>;
    |     ^^^^^^^^^^^^^-
    |                  |
-   |                  help: add the required where clauses: `where Self: 'a`
+   |                  help: add the required where clause: `where Self: 'a`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
 error: aborting due to previous error
 
diff --git a/src/test/ui/generic-associated-types/self-outlives-lint.rs b/src/test/ui/generic-associated-types/self-outlives-lint.rs
index af90d158855..37b3a6155d5 100644
--- a/src/test/ui/generic-associated-types/self-outlives-lint.rs
+++ b/src/test/ui/generic-associated-types/self-outlives-lint.rs
@@ -7,7 +7,7 @@ use std::fmt::Debug;
 // We have a `&'a self`, so we need a `Self: 'a`
 trait Iterable {
     type Item<'x>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn iter<'a>(&'a self) -> Self::Item<'a>;
 }
 
@@ -23,7 +23,7 @@ impl<T> Iterable for T {
 // We have a `&'a T`, so we need a `T: 'x`
 trait Deserializer<T> {
     type Out<'x>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn deserialize<'a>(&self, input: &'a T) -> Self::Out<'a>;
 }
 
@@ -37,14 +37,14 @@ impl<T> Deserializer<T> for () {
 // We have a `&'b T` and a `'b: 'a`, so it is implied that `T: 'a`. Therefore, we need a `T: 'x`
 trait Deserializer2<T> {
     type Out<'x>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn deserialize2<'a, 'b: 'a>(&self, input1: &'b T) -> Self::Out<'a>;
 }
 
 // We have a `&'a T` and a `&'b U`, so we need a `T: 'x` and a `U: 'y`
 trait Deserializer3<T, U> {
     type Out<'x, 'y>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn deserialize2<'a, 'b>(&self, input: &'a T, input2: &'b U) -> Self::Out<'a, 'b>;
 }
 
@@ -59,7 +59,7 @@ struct Wrap<T>(T);
 // We pass `Wrap<T>` and we see `&'z Wrap<T>`, so we require `D: 'x`
 trait Des {
     type Out<'x, D>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn des<'z, T>(&self, data: &'z Wrap<T>) -> Self::Out<'z, Wrap<T>>;
 }
 /*
@@ -75,7 +75,7 @@ impl Des for () {
 // implied bound that `T: 'z`, so we require `D: 'x`
 trait Des2 {
     type Out<'x, D>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn des<'z, T>(&self, data: &'z Wrap<T>) -> Self::Out<'z, T>;
 }
 /*
@@ -90,7 +90,7 @@ impl Des2 for () {
 // We see `&'z T`, so we require `D: 'x`
 trait Des3 {
     type Out<'x, D>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn des<'z, T>(&self, data: &'z T) -> Self::Out<'z, T>;
 }
 /*
@@ -112,7 +112,7 @@ trait NoGat<'a> {
 // FIXME: we require two bounds (`where Self: 'a, Self: 'b`) when we should only require one
 trait TraitLifetime<'a> {
     type Bar<'b>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn method(&'a self) -> Self::Bar<'a>;
 }
 
@@ -120,14 +120,14 @@ trait TraitLifetime<'a> {
 // FIXME: we require two bounds (`where Self: 'a, Self: 'b`) when we should only require one
 trait TraitLifetimeWhere<'a> where Self: 'a {
     type Bar<'b>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn method(&'a self) -> Self::Bar<'a>;
 }
 
 // Explicit bound instead of implicit; we want to still error
 trait ExplicitBound {
     type Bar<'b>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn method<'b>(&self, token: &'b ()) -> Self::Bar<'b> where Self: 'b;
 }
 
@@ -141,14 +141,15 @@ trait NotInReturn {
 trait IterableTwo {
     type Item<'a>;
     type Iterator<'a>: Iterator<Item = Self::Item<'a>>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn iter<'a>(&'a self) -> Self::Iterator<'a>;
 }
 
-// We also should report region outlives clauses
+// We also should report region outlives clauses. Here, we know that `'y: 'x`,
+// because of `&'x &'y`, so we require that `'b: 'a`.
 trait RegionOutlives {
     type Bar<'a, 'b>;
-    //~^ Missing required bounds
+    //~^ missing required
     fn foo<'x, 'y>(&self, input: &'x &'y ()) -> Self::Bar<'x, 'y>;
 }
 
@@ -161,6 +162,17 @@ impl Foo for () {
 }
 */
 
+// Similar to the above, except with explicit bounds
+trait ExplicitRegionOutlives<'ctx> {
+    type Fut<'out>;
+    //~^ missing required
+
+    fn test<'out>(ctx: &'ctx i32) -> Self::Fut<'out>
+    where
+        'ctx: 'out;
+}
+
+
 // If there are multiple methods that return the GAT, require a set of clauses
 // that can be satisfied by *all* methods
 trait MultipleMethods {
@@ -170,4 +182,11 @@ trait MultipleMethods {
     fn gimme_default(&self) -> Self::Bar<'static>;
 }
 
+// We would normally require `Self: 'a`, but we can prove that `Self: 'static`
+// because of the the bounds on the trait, so the bound is proven
+trait Trait: 'static {
+    type Assoc<'a>;
+    fn make_assoc(_: &u32) -> Self::Assoc<'_>;
+}
+
 fn main() {}
diff --git a/src/test/ui/generic-associated-types/self-outlives-lint.stderr b/src/test/ui/generic-associated-types/self-outlives-lint.stderr
index bf85780f69f..c82dcdae204 100644
--- a/src/test/ui/generic-associated-types/self-outlives-lint.stderr
+++ b/src/test/ui/generic-associated-types/self-outlives-lint.stderr
@@ -1,98 +1,145 @@
-error: Missing required bounds on Item
+error: missing required bound on `Item`
   --> $DIR/self-outlives-lint.rs:9:5
    |
 LL |     type Item<'x>;
    |     ^^^^^^^^^^^^^-
    |                  |
-   |                  help: add the required where clauses: `where Self: 'x`
+   |                  help: add the required where clause: `where Self: 'x`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Out
+error: missing required bound on `Out`
   --> $DIR/self-outlives-lint.rs:25:5
    |
 LL |     type Out<'x>;
    |     ^^^^^^^^^^^^-
    |                 |
-   |                 help: add the required where clauses: `where T: 'x`
+   |                 help: add the required where clause: `where T: 'x`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Out
+error: missing required bound on `Out`
   --> $DIR/self-outlives-lint.rs:39:5
    |
 LL |     type Out<'x>;
    |     ^^^^^^^^^^^^-
    |                 |
-   |                 help: add the required where clauses: `where T: 'x`
+   |                 help: add the required where clause: `where T: 'x`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Out
+error: missing required bounds on `Out`
   --> $DIR/self-outlives-lint.rs:46:5
    |
 LL |     type Out<'x, 'y>;
    |     ^^^^^^^^^^^^^^^^-
    |                     |
    |                     help: add the required where clauses: `where T: 'x, U: 'y`
+   |
+   = note: these bounds are required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Out
+error: missing required bound on `Out`
   --> $DIR/self-outlives-lint.rs:61:5
    |
 LL |     type Out<'x, D>;
    |     ^^^^^^^^^^^^^^^-
    |                    |
-   |                    help: add the required where clauses: `where D: 'x`
+   |                    help: add the required where clause: `where D: 'x`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Out
+error: missing required bound on `Out`
   --> $DIR/self-outlives-lint.rs:77:5
    |
 LL |     type Out<'x, D>;
    |     ^^^^^^^^^^^^^^^-
    |                    |
-   |                    help: add the required where clauses: `where D: 'x`
+   |                    help: add the required where clause: `where D: 'x`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Out
+error: missing required bound on `Out`
   --> $DIR/self-outlives-lint.rs:92:5
    |
 LL |     type Out<'x, D>;
    |     ^^^^^^^^^^^^^^^-
    |                    |
-   |                    help: add the required where clauses: `where D: 'x`
+   |                    help: add the required where clause: `where D: 'x`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Bar
+error: missing required bounds on `Bar`
   --> $DIR/self-outlives-lint.rs:114:5
    |
 LL |     type Bar<'b>;
    |     ^^^^^^^^^^^^-
    |                 |
    |                 help: add the required where clauses: `where Self: 'a, Self: 'b`
+   |
+   = note: these bounds are required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Bar
+error: missing required bound on `Bar`
   --> $DIR/self-outlives-lint.rs:122:5
    |
 LL |     type Bar<'b>;
    |     ^^^^^^^^^^^^-
    |                 |
-   |                 help: add the required where clauses: `where Self: 'a, Self: 'b`
+   |                 help: add the required where clause: `where Self: 'b`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Bar
+error: missing required bound on `Bar`
   --> $DIR/self-outlives-lint.rs:129:5
    |
 LL |     type Bar<'b>;
    |     ^^^^^^^^^^^^-
    |                 |
-   |                 help: add the required where clauses: `where Self: 'b`
+   |                 help: add the required where clause: `where Self: 'b`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Iterator
+error: missing required bound on `Iterator`
   --> $DIR/self-outlives-lint.rs:143:5
    |
 LL |     type Iterator<'a>: Iterator<Item = Self::Item<'a>>;
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^-
    |                                                       |
-   |                                                       help: add the required where clauses: `where Self: 'a`
+   |                                                       help: add the required where clause: `where Self: 'a`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: Missing required bounds on Bar
-  --> $DIR/self-outlives-lint.rs:150:5
+error: missing required bound on `Bar`
+  --> $DIR/self-outlives-lint.rs:151:5
    |
 LL |     type Bar<'a, 'b>;
    |     ^^^^^^^^^^^^^^^^-
    |                     |
-   |                     help: add the required where clauses: `where 'a: 'b`
+   |                     help: add the required where clause: `where 'b: 'a`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
+
+error: missing required bound on `Fut`
+  --> $DIR/self-outlives-lint.rs:167:5
+   |
+LL |     type Fut<'out>;
+   |     ^^^^^^^^^^^^^^-
+   |                   |
+   |                   help: add the required where clause: `where 'ctx: 'out`
+   |
+   = note: this bound is required to ensure that impls have maximum flexibility
+   = note: see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information
 
-error: aborting due to 12 previous errors
+error: aborting due to 13 previous errors