auto merge of #19884 : nikomatsakis/rust/issue-19730-perfect-forwarding, r=pnkfelix

Rewrite how the HRTB algorithm matches impls against obligations. Instead of impls providing higher-ranked trait-references, impls now once again only have early-bound regions. The skolemization checks are thus moved out into trait matching itself. This allows to implement "perfect forwarding" impls like those described in #19730. This PR builds on a previous PR that was already reviewed by @pnkfelix.

r? @pnkfelix 

Fixes #19730 

1 files changed, 125 insertions, 2 deletions

diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 508af4c28e6..b2c661cc58a 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -25,6 +25,7 @@ use rustc_typeck::middle::infer::combine::Combine;
 use rustc_typeck::middle::infer;
 use rustc_typeck::middle::infer::lub::Lub;
 use rustc_typeck::middle::infer::glb::Glb;
+use rustc_typeck::middle::infer::sub::Sub;
 use rustc_typeck::util::ppaux::{ty_to_string, Repr, UserString};
 use rustc::session::{mod,config};
 use syntax::{abi, ast, ast_map, ast_util};
@@ -274,11 +275,11 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
             onceness: ast::Many,
             store: ty::RegionTraitStore(region_bound, ast::MutMutable),
             bounds: ty::region_existential_bound(region_bound),
-            sig: ty::FnSig {
+            sig: ty::Binder(ty::FnSig {
                 inputs: input_tys.to_vec(),
                 output: ty::FnConverging(output_ty),
                 variadic: false,
-            },
+            }),
             abi: abi::Rust,
         })
     }
@@ -341,6 +342,11 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
         infer::TypeTrace::dummy()
     }
 
+    pub fn sub(&self) -> Sub<'a, 'tcx> {
+        let trace = self.dummy_type_trace();
+        Sub(self.infcx.combine_fields(true, trace))
+    }
+
     pub fn lub(&self) -> Lub<'a, 'tcx> {
         let trace = self.dummy_type_trace();
         Lub(self.infcx.combine_fields(true, trace))
@@ -359,6 +365,33 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
         }
     }
 
+    /// Checks that `t1 <: t2` is true (this may register additional
+    /// region checks).
+    pub fn check_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
+        match self.sub().tys(t1, t2) {
+            Ok(_) => { }
+            Err(ref e) => {
+                panic!("unexpected error computing sub({},{}): {}",
+                       t1.repr(self.infcx.tcx),
+                       t2.repr(self.infcx.tcx),
+                       ty::type_err_to_str(self.infcx.tcx, e));
+            }
+        }
+    }
+
+    /// Checks that `t1 <: t2` is false (this may register additional
+    /// region checks).
+    pub fn check_not_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
+        match self.sub().tys(t1, t2) {
+            Err(_) => { }
+            Ok(_) => {
+                panic!("unexpected success computing sub({},{})",
+                       t1.repr(self.infcx.tcx),
+                       t2.repr(self.infcx.tcx));
+            }
+        }
+    }
+
     /// Checks that `LUB(t1,t2) == t_lub`
     pub fn check_lub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>, t_lub: Ty<'tcx>) {
         match self.lub().tys(t1, t2) {
@@ -422,6 +455,74 @@ fn contravariant_region_ptr_err() {
 }
 
 #[test]
+fn sub_free_bound_false() {
+    //! Test that:
+    //!
+    //!     fn(&'a int) <: for<'b> fn(&'b int)
+    //!
+    //! does NOT hold.
+
+    test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
+        let t_rptr_free1 = env.t_rptr_free(0, 1);
+        let t_rptr_bound1 = env.t_rptr_late_bound(1);
+        env.check_not_sub(env.t_fn(&[t_rptr_free1], ty::mk_int()),
+                          env.t_fn(&[t_rptr_bound1], ty::mk_int()));
+    })
+}
+
+#[test]
+fn sub_bound_free_true() {
+    //! Test that:
+    //!
+    //!     for<'a> fn(&'a int) <: fn(&'b int)
+    //!
+    //! DOES hold.
+
+    test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
+        let t_rptr_bound1 = env.t_rptr_late_bound(1);
+        let t_rptr_free1 = env.t_rptr_free(0, 1);
+        env.check_sub(env.t_fn(&[t_rptr_bound1], ty::mk_int()),
+                      env.t_fn(&[t_rptr_free1], ty::mk_int()));
+    })
+}
+
+#[test]
+fn sub_free_bound_false_infer() {
+    //! Test that:
+    //!
+    //!     fn(_#1) <: for<'b> fn(&'b int)
+    //!
+    //! does NOT hold for any instantiation of `_#1`.
+
+    test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
+        let t_infer1 = env.infcx.next_ty_var();
+        let t_rptr_bound1 = env.t_rptr_late_bound(1);
+        env.check_not_sub(env.t_fn(&[t_infer1], ty::mk_int()),
+                          env.t_fn(&[t_rptr_bound1], ty::mk_int()));
+    })
+}
+
+#[test]
+fn lub_free_bound_infer() {
+    //! Test result of:
+    //!
+    //!     LUB(fn(_#1), for<'b> fn(&'b int))
+    //!
+    //! This should yield `fn(&'_ int)`. We check
+    //! that it yields `fn(&'x int)` for some free `'x`,
+    //! anyhow.
+
+    test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
+        let t_infer1 = env.infcx.next_ty_var();
+        let t_rptr_bound1 = env.t_rptr_late_bound(1);
+        let t_rptr_free1 = env.t_rptr_free(0, 1);
+        env.check_lub(env.t_fn(&[t_infer1], ty::mk_int()),
+                      env.t_fn(&[t_rptr_bound1], ty::mk_int()),
+                      env.t_fn(&[t_rptr_free1], ty::mk_int()));
+    });
+}
+
+#[test]
 fn lub_bound_bound() {
     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
         let t_rptr_bound1 = env.t_rptr_late_bound(1);
@@ -525,6 +626,28 @@ fn glb_bound_free() {
 }
 
 #[test]
+fn glb_bound_free_infer() {
+    test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
+        let t_rptr_bound1 = env.t_rptr_late_bound(1);
+        let t_infer1 = env.infcx.next_ty_var();
+
+        // compute GLB(fn(_) -> int, for<'b> fn(&'b int) -> int),
+        // which should yield for<'b> fn(&'b int) -> int
+        env.check_glb(env.t_fn(&[t_rptr_bound1], ty::mk_int()),
+                      env.t_fn(&[t_infer1], ty::mk_int()),
+                      env.t_fn(&[t_rptr_bound1], ty::mk_int()));
+
+        // as a side-effect, computing GLB should unify `_` with
+        // `&'_ int`
+        let t_resolve1 = env.infcx.shallow_resolve(t_infer1);
+        match t_resolve1.sty {
+            ty::ty_rptr(..) => { }
+            _ => { panic!("t_resolve1={}", t_resolve1.repr(env.infcx.tcx)); }
+        }
+    })
+}
+
+#[test]
 fn glb_bound_static() {
     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
         let t_rptr_bound1 = env.t_rptr_late_bound(1);