Handle equal regions in opaque type inference

4 files changed, 127 insertions, 18 deletions

diff --git a/src/librustc_mir/borrow_check/region_infer/opaque_types.rs b/src/librustc_mir/borrow_check/region_infer/opaque_types.rs
index e16a2c838eb..f3f392683f6 100644
--- a/src/librustc_mir/borrow_check/region_infer/opaque_types.rs
+++ b/src/librustc_mir/borrow_check/region_infer/opaque_types.rs
@@ -1,7 +1,7 @@
-use rustc::hir::def_id::DefId;
 use rustc::infer::InferCtxt;
 use rustc::ty;
 use rustc_data_structures::fx::FxHashMap;
+use rustc_hir::def_id::DefId;
 use rustc_span::Span;
 
 use super::RegionInferenceContext;
@@ -9,6 +9,42 @@ use super::RegionInferenceContext;
 impl<'tcx> RegionInferenceContext<'tcx> {
     /// Resolve any opaque types that were encountered while borrow checking
     /// this item. This is then used to get the type in the `type_of` query.
+    ///
+    /// For example consider `fn f<'a>(x: &'a i32) -> impl Sized + 'a { x }`.
+    /// This is lowered to give HIR something like
+    ///
+    /// type _Return<'_a> = impl Sized + '_a;
+    /// fn f<'a>(x: &'a i32) -> _Return<'a> { x }
+    ///
+    /// When checking the return type record the type from the return and the
+    /// type used in the return value. In this case they might be `_Return<'1>`
+    /// and `&'2 i32` respectively.
+    ///
+    /// Once we to this method, we have completed region inference and want to
+    /// call `infer_opaque_definition_from_instantiation` to get the inferred
+    /// type of `_Return<'_a>`. `infer_opaque_definition_from_instantiation`
+    /// compares lifetimes directly, so we need to map the inference variables
+    /// back to concrete lifetimes: `'static`, `ReEarlyBound` or `ReFree`.
+    ///
+    /// First we map all the lifetimes in the concrete type to an equal
+    /// universal region that occurs in the concrete type's substs, in this case
+    /// this would result in `&'1 i32`. We only consider regions in the substs
+    /// in case there is an equal region that does not. For example, this should
+    /// be allowed:
+    /// `fn f<'a: 'b, 'b: 'a>(x: *mut &'b i32) -> impl Sized + 'a { x }`
+    ///
+    /// Then we map the regions in both the type and the subst to their
+    /// `external_name` giving `concrete_type = &'a i32, substs = ['a]`. This
+    /// will then allow `infer_opaque_definition_from_instantiation` to
+    /// determine that `_Return<'_a> = &'_a i32`.
+    ///
+    /// There's a slight complication around closures. Given
+    /// `fn f<'a: 'a>() { || {} }` the closure's type is something like
+    /// `f::<'a>::{{closure}}`. The region parameter from f is essentially
+    /// ignored by type checking so ends up being inferred to an empty region.
+    /// Calling `universal_upper_bound` for such a region gives `fr_fn_body`,
+    /// which has no `external_name` in which case we use `'empty` as the
+    /// region to pass to `infer_opaque_definition_from_instantiation`.
     pub(in crate::borrow_check) fn infer_opaque_types(
         &self,
         infcx: &InferCtxt<'_, 'tcx>,
@@ -23,24 +59,12 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                     concrete_type, substs
                 );
 
-                // Map back to "concrete" regions so that errors in
-                // `infer_opaque_definition_from_instantiation` can show
-                // sensible region names.
-                let universal_concrete_type =
-                    infcx.tcx.fold_regions(&concrete_type, &mut false, |region, _| match region {
-                        &ty::ReVar(vid) => {
-                            let universal_bound = self.universal_upper_bound(vid);
-                            self.definitions[universal_bound]
-                                .external_name
-                                .filter(|_| self.eval_equal(universal_bound, vid))
-                                .unwrap_or(infcx.tcx.lifetimes.re_empty)
-                        }
-                        concrete => concrete,
-                    });
+                let mut subst_regions = vec![self.universal_regions.fr_static];
                 let universal_substs =
-                    infcx.tcx.fold_regions(&substs, &mut false, |region, _| match region {
+                    infcx.tcx.fold_regions(&substs, &mut false, |region, _| match *region {
                         ty::ReVar(vid) => {
-                            self.definitions[*vid].external_name.unwrap_or_else(|| {
+                            subst_regions.push(vid);
+                            self.definitions[vid].external_name.unwrap_or_else(|| {
                                 infcx.tcx.sess.delay_span_bug(
                                     span,
                                     "opaque type with non-universal region substs",
@@ -48,7 +72,33 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                                 infcx.tcx.lifetimes.re_static
                             })
                         }
-                        concrete => concrete,
+                        _ => {
+                            infcx.tcx.sess.delay_span_bug(
+                                span,
+                                &format!("unexpected concrete region in borrowck: {:?}", region),
+                            );
+                            region
+                        }
+                    });
+
+                subst_regions.sort();
+                subst_regions.dedup();
+
+                let universal_concrete_type =
+                    infcx.tcx.fold_regions(&concrete_type, &mut false, |region, _| match *region {
+                        ty::ReVar(vid) => subst_regions
+                            .iter()
+                            .find(|ur_vid| self.eval_equal(vid, **ur_vid))
+                            .and_then(|ur_vid| self.definitions[*ur_vid].external_name)
+                            .unwrap_or(infcx.tcx.lifetimes.re_root_empty),
+                        ty::ReLateBound(..) => region,
+                        _ => {
+                            infcx.tcx.sess.delay_span_bug(
+                                span,
+                                &format!("unexpected concrete region in borrowck: {:?}", region),
+                            );
+                            region
+                        }
                     });
 
                 debug!(
diff --git a/src/librustc_mir/borrow_check/type_check/mod.rs b/src/librustc_mir/borrow_check/type_check/mod.rs
index 6c073b3d2c8..85bc032606f 100644
--- a/src/librustc_mir/borrow_check/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/type_check/mod.rs
@@ -1275,6 +1275,8 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                         );
 
                         if !concrete_is_opaque {
+                            // Equate concrete_ty (an inference variable) with
+                            // the renumbered type from typeck.
                             obligations.add(
                                 infcx
                                     .at(&ObligationCause::dummy(), param_env)
diff --git a/src/test/ui/impl-trait/equal-hidden-lifetimes.rs b/src/test/ui/impl-trait/equal-hidden-lifetimes.rs
new file mode 100644
index 00000000000..79db88828b9
--- /dev/null
+++ b/src/test/ui/impl-trait/equal-hidden-lifetimes.rs
@@ -0,0 +1,49 @@
+// Test that we consider equal regions when checking for hidden regions in
+// opaque types
+
+// check-pass
+
+// `'a == 'static` so `&'a i32` is fine as the return type
+fn equal_regions_static<'a: 'static>(x: &'a i32) -> impl Sized {
+    //~^ WARNING unnecessary lifetime parameter `'a`
+    x
+}
+
+// `'a == 'b` so `&'b i32` is fine as the return type
+fn equal_regions<'a: 'b, 'b: 'a>(x: &'b i32) -> impl Sized + 'a {
+    let y: &'a i32 = x;
+    let z: &'b i32 = y;
+    x
+}
+
+// `'a == 'b` so `&'a i32` is fine as the return type
+fn equal_regions_rev<'a: 'b, 'b: 'a>(x: &'a i32) -> impl Sized + 'b {
+    let y: &'a i32 = x;
+    let z: &'b i32 = y;
+    x
+}
+
+// `'a == 'b` so `*mut &'b i32` is fine as the return type
+fn equal_regions_inv<'a: 'b, 'b: 'a>(x: *mut &'b i32) -> impl Sized + 'a {
+    let y: *mut &'a i32 = x;
+    let z: *mut &'b i32 = y;
+    x
+}
+
+// `'a == 'b` so `*mut &'a i32` is fine as the return type
+fn equal_regions_inv_rev<'a: 'b, 'b: 'a>(x: *mut &'a i32) -> impl Sized + 'b {
+    let y: *mut &'a i32 = x;
+    let z: *mut &'b i32 = y;
+    x
+}
+
+// Should be able to infer `fn(&'static ())` as the return type.
+fn contravariant_lub<'a, 'b: 'a, 'c: 'a, 'd: 'b + 'c>(
+    x: fn(&'b ()),
+    y: fn(&'c ()),
+    c: bool,
+) -> impl Sized + 'a {
+    if c { x } else { y }
+}
+
+fn main() {}
diff --git a/src/test/ui/impl-trait/equal-hidden-lifetimes.stderr b/src/test/ui/impl-trait/equal-hidden-lifetimes.stderr
new file mode 100644
index 00000000000..eb064b4e14a
--- /dev/null
+++ b/src/test/ui/impl-trait/equal-hidden-lifetimes.stderr
@@ -0,0 +1,8 @@
+warning: unnecessary lifetime parameter `'a`
+  --> $DIR/equal-hidden-lifetimes.rs:7:25
+   |
+LL | fn equal_regions_static<'a: 'static>(x: &'a i32) -> impl Sized {
+   |                         ^^^^^^^^^^^
+   |
+   = help: you can use the `'static` lifetime directly, in place of `'a`
+