Auto merge of #58056 - nikomatsakis:issue-57843-universe-leak, r=pnkfelix

make generalization code create new variables in correct universe

In our type inference system, when we "generalize" a type T to become
a suitable value for a type variable V, we sometimes wind up creating
new inference variables. So, for example, if we are making V be some
subtype of `&'X u32`, then we might instantiate V with `&'Y u32`.
This generalized type is then related `&'Y u32 <: &'X u32`, resulting
in a region constriant `'Y: 'X`. Previously, however, we were making
these fresh variables like `'Y` in the "current universe", but they
should be created in the universe of V. Moreover, we sometimes cheat
in an invariant context and avoid creating fresh variables if we know
the result must be equal -- we can only do that when the universes
work out.

Fixes #57843

r? @pnkfelix

16 files changed, 150 insertions, 50 deletions

diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index 361fbfea097..9cd5a844f15 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -255,10 +255,24 @@ impl<'infcx, 'gcx, 'tcx> CombineFields<'infcx, 'gcx, 'tcx> {
             RelationDir::SupertypeOf => ty::Contravariant,
         };
 
+        debug!("generalize: ambient_variance = {:?}", ambient_variance);
+
+        let for_universe = match self.infcx.type_variables.borrow_mut().probe(for_vid) {
+            v @ TypeVariableValue::Known { .. } => panic!(
+                "instantiating {:?} which has a known value {:?}",
+                for_vid,
+                v,
+            ),
+            TypeVariableValue::Unknown { universe } => universe,
+        };
+
+        debug!("generalize: for_universe = {:?}", for_universe);
+
         let mut generalize = Generalizer {
             infcx: self.infcx,
             span: self.trace.cause.span,
             for_vid_sub_root: self.infcx.type_variables.borrow_mut().sub_root_var(for_vid),
+            for_universe,
             ambient_variance,
             needs_wf: false,
             root_ty: ty,
@@ -288,6 +302,11 @@ struct Generalizer<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> {
     /// that means we would have created a cyclic type.
     for_vid_sub_root: ty::TyVid,
 
+    /// The universe of the type variable that is in the process of
+    /// being instantiated. Any fresh variables that we create in this
+    /// process should be in that same universe.
+    for_universe: ty::UniverseIndex,
+
     /// Track the variance as we descend into the type.
     ambient_variance: ty::Variance,
 
@@ -386,6 +405,8 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
     fn tys(&mut self, t: Ty<'tcx>, t2: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
         assert_eq!(t, t2); // we are abusing TypeRelation here; both LHS and RHS ought to be ==
 
+        debug!("generalize: t={:?}", t);
+
         // Check to see whether the type we are genealizing references
         // any other type variable related to `vid` via
         // subtyping. This is basically our "occurs check", preventing
@@ -403,12 +424,17 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                     match variables.probe(vid) {
                         TypeVariableValue::Known { value: u } => {
                             drop(variables);
+                            debug!("generalize: known value {:?}", u);
                             self.relate(&u, &u)
                         }
                         TypeVariableValue::Unknown { universe } => {
                             match self.ambient_variance {
                                 // Invariant: no need to make a fresh type variable.
-                                ty::Invariant => return Ok(t),
+                                ty::Invariant => {
+                                    if self.for_universe.can_name(universe) {
+                                        return Ok(t);
+                                    }
+                                }
 
                                 // Bivariant: make a fresh var, but we
                                 // may need a WF predicate. See
@@ -422,7 +448,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                             }
 
                             let origin = *variables.var_origin(vid);
-                            let new_var_id = variables.new_var(universe, false, origin);
+                            let new_var_id = variables.new_var(self.for_universe, false, origin);
                             let u = self.tcx().mk_var(new_var_id);
                             debug!("generalize: replacing original vid={:?} with new={:?}",
                                    vid, u);
@@ -448,6 +474,8 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                -> RelateResult<'tcx, ty::Region<'tcx>> {
         assert_eq!(r, r2); // we are abusing TypeRelation here; both LHS and RHS ought to be ==
 
+        debug!("generalize: regions r={:?}", r);
+
         match *r {
             // Never make variables for regions bound within the type itself,
             // nor for erased regions.
@@ -456,37 +484,40 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                 return Ok(r);
             }
 
-            // Always make a fresh region variable for placeholder
-            // regions; the higher-ranked decision procedures rely on
-            // this.
-            ty::RePlaceholder(..) => { }
+            ty::ReClosureBound(..) => {
+                span_bug!(
+                    self.span,
+                    "encountered unexpected ReClosureBound: {:?}",
+                    r,
+                );
+            }
 
-            // For anything else, we make a region variable, unless we
-            // are *equating*, in which case it's just wasteful.
+            ty::RePlaceholder(..) |
+            ty::ReVar(..) |
             ty::ReEmpty |
             ty::ReStatic |
             ty::ReScope(..) |
-            ty::ReVar(..) |
             ty::ReEarlyBound(..) |
             ty::ReFree(..) => {
-                match self.ambient_variance {
-                    ty::Invariant => return Ok(r),
-                    ty::Bivariant | ty::Covariant | ty::Contravariant => (),
-                }
+                // see common code below
             }
+        }
 
-            ty::ReClosureBound(..) => {
-                span_bug!(
-                    self.span,
-                    "encountered unexpected ReClosureBound: {:?}",
-                    r,
-                );
+        // If we are in an invariant context, we can re-use the region
+        // as is, unless it happens to be in some universe that we
+        // can't name. (In the case of a region *variable*, we could
+        // use it if we promoted it into our universe, but we don't
+        // bother.)
+        if let ty::Invariant = self.ambient_variance {
+            let r_universe = self.infcx.universe_of_region(r);
+            if self.for_universe.can_name(r_universe) {
+                return Ok(r);
             }
         }
 
         // FIXME: This is non-ideal because we don't give a
         // very descriptive origin for this region variable.
-        Ok(self.infcx.next_region_var(MiscVariable(self.span)))
+        Ok(self.infcx.next_region_var_in_universe(MiscVariable(self.span), self.for_universe))
     }
 }
 
diff --git a/src/librustc/infer/higher_ranked/mod.rs b/src/librustc/infer/higher_ranked/mod.rs
index 7f01078737d..c864349019b 100644
--- a/src/librustc/infer/higher_ranked/mod.rs
+++ b/src/librustc/infer/higher_ranked/mod.rs
@@ -96,10 +96,15 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         let (result, map) = self.tcx.replace_bound_vars(binder, fld_r, fld_t);
 
         debug!(
-            "replace_bound_vars_with_placeholders(binder={:?}, result={:?}, map={:?})",
+            "replace_bound_vars_with_placeholders(\
+                next_universe={:?}, \
+                binder={:?}, \
+                result={:?}, \
+                map={:?})",
+            next_universe,
             binder,
             result,
-            map
+            map,
         );
 
         (result, map)
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index a61771b2a4e..04d08c19980 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -1018,6 +1018,18 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         self.tcx.mk_region(ty::ReVar(region_var))
     }
 
+    /// Return the universe that the region `r` was created in.  For
+    /// most regions (e.g., `'static`, named regions from the user,
+    /// etc) this is the root universe U0. For inference variables or
+    /// placeholders, however, it will return the universe which which
+    /// they are associated.
+    fn universe_of_region(
+        &self,
+        r: ty::Region<'tcx>,
+    ) -> ty::UniverseIndex {
+        self.borrow_region_constraints().universe(r)
+    }
+
     /// Number of region variables created so far.
     pub fn num_region_vars(&self) -> usize {
         self.borrow_region_constraints().num_region_vars()
diff --git a/src/librustc/infer/region_constraints/mod.rs b/src/librustc/infer/region_constraints/mod.rs
index 65d25333c71..45d614167ea 100644
--- a/src/librustc/infer/region_constraints/mod.rs
+++ b/src/librustc/infer/region_constraints/mod.rs
@@ -514,8 +514,8 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
             self.undo_log.push(AddVar(vid));
         }
         debug!(
-            "created new region variable {:?} with origin {:?}",
-            vid, origin
+            "created new region variable {:?} in {:?} with origin {:?}",
+            vid, universe, origin
         );
         return vid;
     }
@@ -671,6 +671,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
             self.make_subregion(origin, sup, sub);
 
             if let (ty::ReVar(sub), ty::ReVar(sup)) = (*sub, *sup) {
+                debug!("make_eqregion: uniying {:?} with {:?}", sub, sup);
                 self.unification_table.union(sub, sup);
                 self.any_unifications = true;
             }
@@ -823,7 +824,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         new_r
     }
 
-    fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex {
+    pub fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex {
         match *region {
             ty::ReScope(..)
             | ty::ReStatic
diff --git a/src/librustc/infer/type_variable.rs b/src/librustc/infer/type_variable.rs
index 09a0a6ce9c9..4c76818346b 100644
--- a/src/librustc/infer/type_variable.rs
+++ b/src/librustc/infer/type_variable.rs
@@ -188,7 +188,13 @@ impl<'tcx> TypeVariableTable<'tcx> {
         });
         assert_eq!(eq_key.vid.index, index as u32);
 
-        debug!("new_var(index={:?}, diverging={:?}, origin={:?}", eq_key.vid, diverging, origin);
+        debug!(
+            "new_var(index={:?}, universe={:?}, diverging={:?}, origin={:?}",
+            eq_key.vid,
+            universe,
+            diverging,
+            origin,
+        );
 
         eq_key.vid
     }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 1cb9f47bb31..768fd02e823 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -1430,6 +1430,15 @@ define_print! {
                         }
                     }
 
+                    if cx.is_verbose {
+                        write!(
+                            f,
+                            " closure_kind_ty={:?} closure_sig_ty={:?}",
+                            substs.closure_kind_ty(did, tcx),
+                            substs.closure_sig_ty(did, tcx),
+                        )?;
+                    }
+
                     write!(f, "]")
                 }),
                 Array(ty, sz) => {
diff --git a/src/test/ui/associated-types/cache/project-fn-ret-invariant.krisskross.stderr b/src/test/ui/associated-types/cache/project-fn-ret-invariant.krisskross.stderr
index 46901b44c4b..fa831ea81dc 100644
--- a/src/test/ui/associated-types/cache/project-fn-ret-invariant.krisskross.stderr
+++ b/src/test/ui/associated-types/cache/project-fn-ret-invariant.krisskross.stderr
@@ -9,15 +9,15 @@ LL |    let a = bar(foo, y); //[krisskross]~ ERROR E0623
    |                     ^ ...but data from `x` is returned here
 
 error[E0623]: lifetime mismatch
-  --> $DIR/project-fn-ret-invariant.rs:55:8
+  --> $DIR/project-fn-ret-invariant.rs:54:21
    |
 LL | fn transmute<'a,'b>(x: Type<'a>, y: Type<'b>) -> (Type<'a>, Type<'b>) {
-   |                                     --------     --------------------
-   |                                     |
-   |                                     this parameter and the return type are declared with different lifetimes...
-...
-LL |    (a, b) //[krisskross]~ ERROR E0623
-   |        ^ ...but data from `x` is returned here
+   |                        --------                  --------------------
+   |                        |
+   |                        this parameter and the return type are declared with different lifetimes...
+LL |    let a = bar(foo, y); //[krisskross]~ ERROR E0623
+LL |    let b = bar(foo, x); //[krisskross]~ ERROR E0623
+   |                     ^ ...but data from `y` is returned here
 
 error: aborting due to 2 previous errors
 
diff --git a/src/test/ui/associated-types/cache/project-fn-ret-invariant.rs b/src/test/ui/associated-types/cache/project-fn-ret-invariant.rs
index dfcf31b3b1f..54b6e3642c2 100644
--- a/src/test/ui/associated-types/cache/project-fn-ret-invariant.rs
+++ b/src/test/ui/associated-types/cache/project-fn-ret-invariant.rs
@@ -51,8 +51,8 @@ fn baz<'a,'b>(x: Type<'a>) -> Type<'static> {
 #[cfg(krisskross)] // two instantiations, mixing and matching: BAD
 fn transmute<'a,'b>(x: Type<'a>, y: Type<'b>) -> (Type<'a>, Type<'b>) {
    let a = bar(foo, y); //[krisskross]~ ERROR E0623
-   let b = bar(foo, x);
-   (a, b) //[krisskross]~ ERROR E0623
+   let b = bar(foo, x); //[krisskross]~ ERROR E0623
+   (a, b)
 }
 
 #[rustc_error]
diff --git a/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr b/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr
index 947844c45c4..dd1212eaac9 100644
--- a/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr
+++ b/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr
@@ -1,4 +1,4 @@
-error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
+error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
   --> $DIR/project-fn-ret-invariant.rs:48:8
    |
 LL |    bar(foo, x) //[transmute]~ ERROR E0495
diff --git a/src/test/ui/associated-types/higher-ranked-projection.bad.stderr b/src/test/ui/associated-types/higher-ranked-projection.bad.stderr
index 3bbf48cb37f..811c9a8f5e1 100644
--- a/src/test/ui/associated-types/higher-ranked-projection.bad.stderr
+++ b/src/test/ui/associated-types/higher-ranked-projection.bad.stderr
@@ -1,12 +1,12 @@
-error: implementation of `Mirror` is not general enough
+error[E0308]: mismatched types
   --> $DIR/higher-ranked-projection.rs:25:5
    |
 LL |     foo(());
-   |     ^^^
+   |     ^^^ one type is more general than the other
    |
-   = note: Due to a where-clause on `foo`,
-   = note: `Mirror` would have to be implemented for the type `&'0 ()`, for any lifetime `'0`
-   = note: but `Mirror` is actually implemented for the type `&'1 ()`, for some specific lifetime `'1`
+   = note: expected type `&'a ()`
+              found type `&()`
 
 error: aborting due to previous error
 
+For more information about this error, try `rustc --explain E0308`.
diff --git a/src/test/ui/associated-types/higher-ranked-projection.good.stderr b/src/test/ui/associated-types/higher-ranked-projection.good.stderr
index c5c8451a5a9..92fd2562858 100644
--- a/src/test/ui/associated-types/higher-ranked-projection.good.stderr
+++ b/src/test/ui/associated-types/higher-ranked-projection.good.stderr
@@ -3,7 +3,7 @@ error: compilation successful
    |
 LL | / fn main() { //[good]~ ERROR compilation successful
 LL | |     foo(());
-LL | |     //[bad]~^ ERROR not general enough
+LL | |     //[bad]~^ ERROR mismatched types
 LL | | }
    | |_^
 
diff --git a/src/test/ui/associated-types/higher-ranked-projection.rs b/src/test/ui/associated-types/higher-ranked-projection.rs
index 1280c8cb4cb..fd7252f9e22 100644
--- a/src/test/ui/associated-types/higher-ranked-projection.rs
+++ b/src/test/ui/associated-types/higher-ranked-projection.rs
@@ -23,5 +23,5 @@ fn foo<U, T>(_t: T)
 #[rustc_error]
 fn main() { //[good]~ ERROR compilation successful
     foo(());
-    //[bad]~^ ERROR not general enough
+    //[bad]~^ ERROR mismatched types
 }
diff --git a/src/test/ui/hrtb/hrtb-perfect-forwarding.rs b/src/test/ui/hrtb/hrtb-perfect-forwarding.rs
index 0094091c6bd..63db695f7e6 100644
--- a/src/test/ui/hrtb/hrtb-perfect-forwarding.rs
+++ b/src/test/ui/hrtb/hrtb-perfect-forwarding.rs
@@ -43,7 +43,7 @@ fn foo_hrtb_bar_not<'b,T>(mut t: T)
     // be implemented. Thus to satisfy `&mut T : for<'a> Foo<&'a
     // isize>`, we require `T : for<'a> Bar<&'a isize>`, but the where
     // clause only specifies `T : Bar<&'b isize>`.
-    foo_hrtb_bar_not(&mut t); //~ ERROR not general enough
+    foo_hrtb_bar_not(&mut t); //~ ERROR mismatched types
 }
 
 fn foo_hrtb_bar_hrtb<T>(mut t: T)
diff --git a/src/test/ui/hrtb/hrtb-perfect-forwarding.stderr b/src/test/ui/hrtb/hrtb-perfect-forwarding.stderr
index c7be3790aa1..ea08af01640 100644
--- a/src/test/ui/hrtb/hrtb-perfect-forwarding.stderr
+++ b/src/test/ui/hrtb/hrtb-perfect-forwarding.stderr
@@ -1,12 +1,12 @@
-error: implementation of `Foo` is not general enough
+error[E0308]: mismatched types
   --> $DIR/hrtb-perfect-forwarding.rs:46:5
    |
-LL |     foo_hrtb_bar_not(&mut t); //~ ERROR not general enough
-   |     ^^^^^^^^^^^^^^^^
+LL |     foo_hrtb_bar_not(&mut t); //~ ERROR mismatched types
+   |     ^^^^^^^^^^^^^^^^ one type is more general than the other
    |
-   = note: Due to a where-clause on `foo_hrtb_bar_not`,
-   = note: `&mut T` must implement `Foo<&'0 isize>`, for any lifetime `'0`
-   = note: but `&mut T` actually implements `Foo<&'1 isize>`, for some specific lifetime `'1`
+   = note: expected type `Bar<&'a isize>`
+              found type `Bar<&'b isize>`
 
 error: aborting due to previous error
 
+For more information about this error, try `rustc --explain E0308`.
diff --git a/src/test/ui/issues/issue-57843.rs b/src/test/ui/issues/issue-57843.rs
new file mode 100644
index 00000000000..46608255266
--- /dev/null
+++ b/src/test/ui/issues/issue-57843.rs
@@ -0,0 +1,24 @@
+// Regression test for an ICE that occurred with the universes code:
+//
+// The signature of the closure `|_|` was being inferred to
+// `exists<'r> fn(&'r u8)`. This should result in a type error since
+// the signature `for<'r> fn(&'r u8)` is required. However, due to a
+// bug in the type variable generalization code, the placeholder for
+// `'r` was leaking out into the writeback phase, causing an ICE.
+
+trait ClonableFn<T> {
+    fn clone(&self) -> Box<dyn Fn(T)>;
+}
+
+impl<T, F: 'static> ClonableFn<T> for F
+where F: Fn(T) + Clone {
+    fn clone(&self) -> Box<dyn Fn(T)> {
+        Box::new(self.clone())
+    }
+}
+
+struct Foo(Box<dyn for<'a> ClonableFn<&'a bool>>);
+
+fn main() {
+    Foo(Box::new(|_| ())); //~ ERROR mismatched types
+}
diff --git a/src/test/ui/issues/issue-57843.stderr b/src/test/ui/issues/issue-57843.stderr
new file mode 100644
index 00000000000..4ef884cb3f5
--- /dev/null
+++ b/src/test/ui/issues/issue-57843.stderr
@@ -0,0 +1,12 @@
+error[E0308]: mismatched types
+  --> $DIR/issue-57843.rs:23:9
+   |
+LL |     Foo(Box::new(|_| ())); //~ ERROR mismatched types
+   |         ^^^^^^^^^^^^^^^^ one type is more general than the other
+   |
+   = note: expected type `std::ops::FnOnce<(&'a bool,)>`
+              found type `std::ops::FnOnce<(&bool,)>`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0308`.