Auto merge of #54624 - arielb1:evaluate-outlives, r=nikomatsakis

handle outlives predicates in trait evaluation

This handles higher-ranked outlives predicates in trait evaluation the same way they are handled in projection.

Fixes #54302. I think this is a more correct fix than #54401 because it fixes the root case in evaluation instead of making evaluation used in less cases. However, we might want to go to a direction closer to @nikomatsakis's solution with Chalk.

r? @nikomatsakis

7 files changed, 328 insertions, 5 deletions

diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 0f330504334..e6bf02cd73e 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -292,7 +292,7 @@ impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx,
             ty::Predicate::Trait(ref data) => {
                 let trait_obligation = obligation.with(data.clone());
 
-                if data.is_global() && !data.has_late_bound_regions() {
+                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) {
@@ -362,6 +362,7 @@ impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx,
                         match binder.no_late_bound_regions() {
                             // 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 is duplicate-implemented between here and fulfillment.
                             None => {
                                 ProcessResult::Error(CodeSelectionError(Unimplemented))
                             }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 268b8e0161b..860914d1984 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -690,10 +690,92 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 }
             }
 
-            ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
-                // we do not consider region relationships when
-                // evaluating trait matches
-                Ok(EvaluatedToOk)
+            ty::Predicate::TypeOutlives(ref binder) => {
+                assert!(!binder.has_escaping_regions());
+                // Check if the type has higher-ranked regions.
+                if binder.skip_binder().0.has_escaping_regions() {
+                    // 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 regions, 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::ObjectSafe(trait_def_id) => {
@@ -900,6 +982,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         {
             debug!("evaluate_stack({:?}) --> recursive",
                    stack.fresh_trait_ref);
+
             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) {
diff --git a/src/test/ui/issue-54302-cases.rs b/src/test/ui/issue-54302-cases.rs
new file mode 100644
index 00000000000..6d1c61c80f0
--- /dev/null
+++ b/src/test/ui/issue-54302-cases.rs
@@ -0,0 +1,95 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+trait Mirror {
+    type Image;
+    fn coerce(self) -> Self::Image;
+}
+
+impl<T> Mirror for T {
+    type Image = T;
+    fn coerce(self) -> Self { self }
+}
+
+trait Foo<'x, T> {
+    fn foo(self) -> &'x T;
+}
+
+impl<'s, 'x, T: 'x> Foo<'x, T> for &'s T where &'s T: Foo2<'x, T> {
+    fn foo(self) -> &'x T { self.foo2() }
+}
+
+trait Foo2<'x, T> {
+    fn foo2(self) -> &'x T;
+}
+
+// example 1 - fails leak check
+impl<'x> Foo2<'x, u32> for &'x u32
+{
+    fn foo2(self) -> &'x u32 { self }
+}
+
+// example 2 - OK with this issue
+impl<'x, 'a: 'x> Foo2<'x, i32> for &'a i32
+{
+    fn foo2(self) -> &'x i32 { self }
+}
+
+// example 3 - fails due to issue #XYZ + Leak-check
+impl<'x, T> Foo2<'x, u64> for T
+    where T: Mirror<Image=&'x u64>
+{
+    fn foo2(self) -> &'x u64 { self.coerce() }
+}
+
+// example 4 - fails due to issue #XYZ
+impl<'x, 'a: 'x, T> Foo2<'x, i64> for T
+    where T: Mirror<Image=&'a i64>
+{
+    fn foo2(self) -> &'x i64 { self.coerce() }
+}
+
+
+trait RefFoo<T> {
+    fn ref_foo(&self) -> &'static T;
+}
+
+impl<T> RefFoo<T> for T where for<'a> &'a T: Foo<'static, T> {
+    fn ref_foo(&self) -> &'static T {
+        self.foo()
+    }
+}
+
+
+fn coerce_lifetime1(a: &u32) -> &'static u32
+{
+    <u32 as RefFoo<u32>>::ref_foo(a)
+    //~^ ERROR the trait bound `for<'a> &'a u32: Foo2<'_, u32>` is not satisfied
+}
+
+fn coerce_lifetime2(a: &i32) -> &'static i32
+{
+    <i32 as RefFoo<i32>>::ref_foo(a)
+    //~^ ERROR the requirement `for<'a> 'a : ` is not satisfied
+}
+
+fn coerce_lifetime3(a: &u64) -> &'static u64
+{
+    <u64 as RefFoo<u64>>::ref_foo(a)
+    //~^ ERROR type mismatch resolving `for<'a> <&'a u64 as Mirror>::Image == &u64`
+}
+
+fn coerce_lifetime4(a: &i64) -> &'static i64
+{
+    <i64 as RefFoo<i64>>::ref_foo(a)
+    //~^ ERROR type mismatch resolving `for<'a> <&'a i64 as Mirror>::Image == &i64`
+}
+
+fn main() {}
diff --git a/src/test/ui/issue-54302-cases.stderr b/src/test/ui/issue-54302-cases.stderr
new file mode 100644
index 00000000000..9603f7a973c
--- /dev/null
+++ b/src/test/ui/issue-54302-cases.stderr
@@ -0,0 +1,65 @@
+error[E0277]: the trait bound `for<'a> &'a u32: Foo2<'_, u32>` is not satisfied
+  --> $DIR/issue-54302-cases.rs:73:5
+   |
+LL |     <u32 as RefFoo<u32>>::ref_foo(a)
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `for<'a> Foo2<'_, u32>` is not implemented for `&'a u32`
+   |
+   = help: the following implementations were found:
+             <&'x u32 as Foo2<'x, u32>>
+   = note: required because of the requirements on the impl of `for<'a> Foo<'static, u32>` for `&'a u32`
+   = note: required because of the requirements on the impl of `RefFoo<u32>` for `u32`
+note: required by `RefFoo::ref_foo`
+  --> $DIR/issue-54302-cases.rs:61:5
+   |
+LL |     fn ref_foo(&self) -> &'static T;
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error[E0279]: the requirement `for<'a> 'a : ` is not satisfied (`expected bound lifetime parameter 'a, found concrete lifetime`)
+  --> $DIR/issue-54302-cases.rs:79:5
+   |
+LL |     <i32 as RefFoo<i32>>::ref_foo(a)
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `for<'a> Foo2<'_, i32>` for `&'a i32`
+   = note: required because of the requirements on the impl of `for<'a> Foo<'static, i32>` for `&'a i32`
+   = note: required because of the requirements on the impl of `RefFoo<i32>` for `i32`
+note: required by `RefFoo::ref_foo`
+  --> $DIR/issue-54302-cases.rs:61:5
+   |
+LL |     fn ref_foo(&self) -> &'static T;
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error[E0271]: type mismatch resolving `for<'a> <&'a u64 as Mirror>::Image == &u64`
+  --> $DIR/issue-54302-cases.rs:85:5
+   |
+LL |     <u64 as RefFoo<u64>>::ref_foo(a)
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected bound lifetime parameter 'a, found concrete lifetime
+   |
+   = note: required because of the requirements on the impl of `for<'a> Foo2<'_, u64>` for `&'a u64`
+   = note: required because of the requirements on the impl of `for<'a> Foo<'static, u64>` for `&'a u64`
+   = note: required because of the requirements on the impl of `RefFoo<u64>` for `u64`
+note: required by `RefFoo::ref_foo`
+  --> $DIR/issue-54302-cases.rs:61:5
+   |
+LL |     fn ref_foo(&self) -> &'static T;
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error[E0271]: type mismatch resolving `for<'a> <&'a i64 as Mirror>::Image == &i64`
+  --> $DIR/issue-54302-cases.rs:91:5
+   |
+LL |     <i64 as RefFoo<i64>>::ref_foo(a)
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected bound lifetime parameter 'a, found concrete lifetime
+   |
+   = note: required because of the requirements on the impl of `for<'a> Foo2<'_, i64>` for `&'a i64`
+   = note: required because of the requirements on the impl of `for<'a> Foo<'static, i64>` for `&'a i64`
+   = note: required because of the requirements on the impl of `RefFoo<i64>` for `i64`
+note: required by `RefFoo::ref_foo`
+  --> $DIR/issue-54302-cases.rs:61:5
+   |
+LL |     fn ref_foo(&self) -> &'static T;
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to 4 previous errors
+
+Some errors occurred: E0271, E0277, E0279.
+For more information about an error, try `rustc --explain E0271`.
diff --git a/src/test/ui/issue-54302.rs b/src/test/ui/issue-54302.rs
new file mode 100644
index 00000000000..969d19cac2d
--- /dev/null
+++ b/src/test/ui/issue-54302.rs
@@ -0,0 +1,29 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+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() {
+    // Then why does it implement DeserializeOwned? This compiles.
+    fn assert_deserialize_owned<T: DeserializeOwned>() {}
+    assert_deserialize_owned::<&'static str>();
+    //~^ ERROR the requirement `for<'de> 'de : ` is not satisfied
+
+    // 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/issue-54302.stderr b/src/test/ui/issue-54302.stderr
new file mode 100644
index 00000000000..f122daeecf6
--- /dev/null
+++ b/src/test/ui/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/issue-54302.rs:23:5
+   |
+LL |     assert_deserialize_owned::<&'static str>();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = 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/issue-54302.rs:22:5
+   |
+LL |     fn assert_deserialize_owned<T: DeserializeOwned>() {}
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0279`.
diff --git a/src/test/ui/run-pass/traits/traits-static-outlives-a-where-clause.rs b/src/test/ui/run-pass/traits/traits-static-outlives-a-where-clause.rs
new file mode 100644
index 00000000000..1051bec6307
--- /dev/null
+++ b/src/test/ui/run-pass/traits/traits-static-outlives-a-where-clause.rs
@@ -0,0 +1,33 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// run-pass
+
+trait Foo<'a> {
+    fn xyz(self);
+}
+impl<'a, T> Foo<'a> for T where 'static: 'a {
+    fn xyz(self) {}
+}
+
+trait Bar {
+    fn uvw(self);
+}
+impl<T> Bar for T where for<'a> T: Foo<'a> {
+    fn uvw(self) { self.xyz(); }
+}
+
+fn foo<T>(t: T) where T: Bar {
+    t.uvw();
+}
+
+fn main() {
+    foo(0);
+}