Auto merge of #55305 - nikomatsakis:universes-refactor-3, r=scalexm

universes refactor 3

Some more refactorings from my universe branch. These are getting a bit more "invasive" -- they start to plumb the universe information through the canonicalization process. As of yet though I don't **believe** this branch changes our behavior in any notable way, though I'm marking the branch as `WIP` to give myself a chance to verify this.

r? @scalexm

13 files changed, 285 insertions, 377 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 8f837327ddb..0c93b86ee4d 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -1229,7 +1229,7 @@ for traits::VtableGeneratorData<'gcx, N> where N: HashStable<StableHashingContex
 
 impl_stable_hash_for!(
     impl<'tcx, V> for struct infer::canonical::Canonical<'tcx, V> {
-        variables, value
+        max_universe, variables, value
     }
 );
 
@@ -1245,7 +1245,8 @@ impl_stable_hash_for!(struct infer::canonical::CanonicalVarInfo {
 
 impl_stable_hash_for!(enum infer::canonical::CanonicalVarKind {
     Ty(k),
-    Region
+    Region(ui),
+    PlaceholderRegion(placeholder),
 });
 
 impl_stable_hash_for!(enum infer::canonical::CanonicalTyVarKind {
diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
index 2b085a3407c..cc6e4df0710 100644
--- a/src/librustc/infer/canonical/canonicalizer.rs
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -107,6 +107,20 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
         )
     }
 
+    pub fn canonicalize_user_type_annotation<V>(&self, value: &V) -> Canonicalized<'gcx, V>
+    where
+        V: TypeFoldable<'tcx> + Lift<'gcx>,
+    {
+        let mut query_state = OriginalQueryValues::default();
+        Canonicalizer::canonicalize(
+            value,
+            Some(self),
+            self.tcx,
+            &CanonicalizeUserTypeAnnotation,
+            &mut query_state,
+        )
+    }
+
     /// A hacky variant of `canonicalize_query` that does not
     /// canonicalize `'static`.  Unfortunately, the existing leak
     /// check treaks `'static` differently in some cases (see also
@@ -162,11 +176,26 @@ struct CanonicalizeQueryResponse;
 impl CanonicalizeRegionMode for CanonicalizeQueryResponse {
     fn canonicalize_free_region(
         &self,
-        _canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
+        canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
         r: ty::Region<'tcx>,
     ) -> ty::Region<'tcx> {
         match r {
             ty::ReFree(_) | ty::ReEmpty | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r,
+            ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region(
+                CanonicalVarInfo {
+                    kind: CanonicalVarKind::PlaceholderRegion(*placeholder),
+                },
+                r,
+            ),
+            ty::ReVar(vid) => {
+                let universe = canonicalizer.region_var_universe(*vid);
+                canonicalizer.canonical_var_for_region(
+                    CanonicalVarInfo {
+                        kind: CanonicalVarKind::Region(universe),
+                    },
+                    r,
+                )
+            }
             _ => {
                 // Other than `'static` or `'empty`, the query
                 // response should be executing in a fully
@@ -182,6 +211,29 @@ impl CanonicalizeRegionMode for CanonicalizeQueryResponse {
     }
 }
 
+struct CanonicalizeUserTypeAnnotation;
+
+impl CanonicalizeRegionMode for CanonicalizeUserTypeAnnotation {
+    fn canonicalize_free_region(
+        &self,
+        canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
+        r: ty::Region<'tcx>,
+    ) -> ty::Region<'tcx> {
+        match r {
+            ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReEmpty | ty::ReStatic => r,
+            ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
+            _ => {
+                // We only expect region names that the user can type.
+                bug!("unexpected region in query response: `{:?}`", r)
+            }
+        }
+    }
+
+    fn any(&self) -> bool {
+        false
+    }
+}
+
 struct CanonicalizeAllFreeRegions;
 
 impl CanonicalizeRegionMode for CanonicalizeAllFreeRegions {
@@ -190,7 +242,7 @@ impl CanonicalizeRegionMode for CanonicalizeAllFreeRegions {
         canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
         r: ty::Region<'tcx>,
     ) -> ty::Region<'tcx> {
-        canonicalizer.canonical_var_for_region(r)
+        canonicalizer.canonical_var_for_region_in_root_universe(r)
     }
 
     fn any(&self) -> bool {
@@ -209,7 +261,7 @@ impl CanonicalizeRegionMode for CanonicalizeFreeRegionsOtherThanStatic {
         if let ty::ReStatic = r {
             r
         } else {
-            canonicalizer.canonical_var_for_region(r)
+            canonicalizer.canonical_var_for_region_in_root_universe(r)
         }
     }
 
@@ -252,7 +304,8 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx>
                      opportunistically resolved to {:?}",
                     vid, r
                 );
-                self.canonical_var_for_region(r)
+                self.canonicalize_region_mode
+                    .canonicalize_free_region(self, r)
             }
 
             ty::ReStatic
@@ -261,7 +314,8 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx>
             | ty::ReScope(_)
             | ty::RePlaceholder(..)
             | ty::ReEmpty
-            | ty::ReErased => self.canonicalize_region_mode.canonicalize_free_region(self, r),
+            | ty::ReErased => self.canonicalize_region_mode
+                .canonicalize_free_region(self, r),
 
             ty::ReClosureBound(..) | ty::ReCanonical(_) => {
                 bug!("canonical region encountered during canonicalization")
@@ -353,6 +407,7 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
         if !value.has_type_flags(needs_canonical_flags) {
             let out_value = gcx.lift(value).unwrap();
             let canon_value = Canonical {
+                max_universe: ty::UniverseIndex::ROOT,
                 variables: List::empty(),
                 value: out_value,
             };
@@ -383,7 +438,14 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
 
         let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables);
 
+        let max_universe = canonical_variables
+            .iter()
+            .map(|cvar| cvar.universe())
+            .max()
+            .unwrap_or(ty::UniverseIndex::ROOT);
+
         Canonical {
+            max_universe,
             variables: canonical_variables,
             value: out_value,
         }
@@ -450,10 +512,46 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
         }
     }
 
-    fn canonical_var_for_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
-        let info = CanonicalVarInfo {
-            kind: CanonicalVarKind::Region,
-        };
+    /// Shorthand helper that creates a canonical region variable for
+    /// `r` (always in the root universe). The reason that we always
+    /// put these variables into the root universe is because this
+    /// method is used during **query construction:** in that case, we
+    /// are taking all the regions and just putting them into the most
+    /// generic context we can. This may generate solutions that don't
+    /// fit (e.g., that equate some region variable with a placeholder
+    /// it can't name) on the caller side, but that's ok, the caller
+    /// can figure that out. In the meantime, it maximizes our
+    /// caching.
+    ///
+    /// (This works because unification never fails -- and hence trait
+    /// selection is never affected -- due to a universe mismatch.)
+    fn canonical_var_for_region_in_root_universe(
+        &mut self,
+        r: ty::Region<'tcx>,
+    ) -> ty::Region<'tcx> {
+        self.canonical_var_for_region(
+            CanonicalVarInfo {
+                kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
+            },
+            r,
+        )
+    }
+
+    /// Returns the universe in which `vid` is defined.
+    fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex {
+        self.infcx
+            .unwrap()
+            .borrow_region_constraints()
+            .var_universe(vid)
+    }
+
+    /// Create a canonical variable (with the given `info`)
+    /// representing the region `r`; return a region referencing it.
+    fn canonical_var_for_region(
+        &mut self,
+        info: CanonicalVarInfo,
+        r: ty::Region<'tcx>,
+    ) -> ty::Region<'tcx> {
         let b = self.canonical_var(info, r.into());
         debug_assert_eq!(ty::INNERMOST, b.level);
         self.tcx().mk_region(ty::ReCanonical(b.var))
diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs
index e3bd407d17a..f2b7c6e0d0d 100644
--- a/src/librustc/infer/canonical/mod.rs
+++ b/src/librustc/infer/canonical/mod.rs
@@ -33,14 +33,14 @@
 
 use infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin};
 use rustc_data_structures::indexed_vec::IndexVec;
-use smallvec::SmallVec;
 use rustc_data_structures::sync::Lrc;
 use serialize::UseSpecializedDecodable;
+use smallvec::SmallVec;
 use std::ops::Index;
 use syntax::source_map::Span;
 use ty::fold::TypeFoldable;
 use ty::subst::Kind;
-use ty::{self, BoundTyIndex, Lift, Region, List, TyCtxt};
+use ty::{self, BoundTyIndex, Lift, List, Region, TyCtxt};
 
 mod canonicalizer;
 
@@ -53,6 +53,7 @@ mod substitute;
 /// numbered starting from 0 in order of first appearance.
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 pub struct Canonical<'gcx, V> {
+    pub max_universe: ty::UniverseIndex,
     pub variables: CanonicalVarInfos<'gcx>,
     pub value: V,
 }
@@ -79,13 +80,31 @@ pub struct CanonicalVarValues<'tcx> {
 /// various parts of it with canonical variables. This struct stores
 /// those replaced bits to remember for when we process the query
 /// result.
-#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 pub struct OriginalQueryValues<'tcx> {
+    /// Map from the universes that appear in the query to the
+    /// universes in the caller context. For the time being, we only
+    /// ever put ROOT values into the query, so this map is very
+    /// simple.
+    pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
+
     /// This is equivalent to `CanonicalVarValues`, but using a
     /// `SmallVec` yields a significant performance win.
     pub var_values: SmallVec<[Kind<'tcx>; 8]>,
 }
 
+impl Default for OriginalQueryValues<'tcx> {
+    fn default() -> Self {
+        let mut universe_map = SmallVec::default();
+        universe_map.push(ty::UniverseIndex::ROOT);
+
+        Self {
+            universe_map,
+            var_values: SmallVec::default(),
+        }
+    }
+}
+
 /// Information about a canonical variable that is included with the
 /// canonical value. This is sufficient information for code to create
 /// a copy of the canonical value in some other inference context,
@@ -95,6 +114,20 @@ pub struct CanonicalVarInfo {
     pub kind: CanonicalVarKind,
 }
 
+impl CanonicalVarInfo {
+    pub fn universe(&self) -> ty::UniverseIndex {
+        self.kind.universe()
+    }
+
+    pub fn is_existential(&self) -> bool {
+        match self.kind {
+            CanonicalVarKind::Ty(_) => true,
+            CanonicalVarKind::Region(_) => true,
+            CanonicalVarKind::PlaceholderRegion(..) => false,
+        }
+    }
+}
+
 /// Describes the "kind" of the canonical variable. This is a "kind"
 /// in the type-theory sense of the term -- i.e., a "meta" type system
 /// that analyzes type-like values.
@@ -104,7 +137,27 @@ pub enum CanonicalVarKind {
     Ty(CanonicalTyVarKind),
 
     /// Region variable `'?R`.
-    Region,
+    Region(ty::UniverseIndex),
+
+    /// A "placeholder" that represents "any region". Created when you
+    /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
+    /// bound region `'a`.
+    PlaceholderRegion(ty::Placeholder),
+}
+
+impl CanonicalVarKind {
+    pub fn universe(self) -> ty::UniverseIndex {
+        match self {
+            // At present, we don't support higher-ranked
+            // quantification over types, so all type variables are in
+            // the root universe.
+            CanonicalVarKind::Ty(_) => ty::UniverseIndex::ROOT,
+
+            // Region variables can be created in sub-universes.
+            CanonicalVarKind::Region(ui) => ui,
+            CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
+        }
+    }
 }
 
 /// Rust actually has more than one category of type variables;
@@ -220,8 +273,16 @@ impl<'gcx, V> Canonical<'gcx, V> {
     /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
     /// ```
     pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'gcx, W> {
-        let Canonical { variables, value } = self;
-        Canonical { variables, value: map_op(value) }
+        let Canonical {
+            max_universe,
+            variables,
+            value,
+        } = self;
+        Canonical {
+            max_universe,
+            variables,
+            value: map_op(value),
+        }
     }
 }
 
@@ -249,35 +310,50 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
     where
         T: TypeFoldable<'tcx>,
     {
+        // For each universe that is referred to in the incoming
+        // query, create a universe in our local inference context. In
+        // practice, as of this writing, all queries have no universes
+        // in them, so this code has no effect, but it is looking
+        // forward to the day when we *do* want to carry universes
+        // through into queries.
+        let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT)
+            .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
+            .collect();
+
         let canonical_inference_vars =
-            self.fresh_inference_vars_for_canonical_vars(span, canonical.variables);
+            self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]);
         let result = canonical.substitute(self.tcx, &canonical_inference_vars);
         (result, canonical_inference_vars)
     }
 
     /// Given the "infos" about the canonical variables from some
-    /// canonical, creates fresh inference variables with the same
-    /// characteristics. You can then use `substitute` to instantiate
-    /// the canonical variable with these inference variables.
-    fn fresh_inference_vars_for_canonical_vars(
+    /// canonical, creates fresh variables with the same
+    /// characteristics (see `instantiate_canonical_var` for
+    /// details). You can then use `substitute` to instantiate the
+    /// canonical variable with these inference variables.
+    fn instantiate_canonical_vars(
         &self,
         span: Span,
         variables: &List<CanonicalVarInfo>,
+        universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
     ) -> CanonicalVarValues<'tcx> {
         let var_values: IndexVec<BoundTyIndex, Kind<'tcx>> = variables
             .iter()
-            .map(|info| self.fresh_inference_var_for_canonical_var(span, *info))
+            .map(|info| self.instantiate_canonical_var(span, *info, &universe_map))
             .collect();
 
         CanonicalVarValues { var_values }
     }
 
     /// Given the "info" about a canonical variable, creates a fresh
-    /// inference variable with the same characteristics.
-    fn fresh_inference_var_for_canonical_var(
+    /// variable for it. If this is an existentially quantified
+    /// variable, then you'll get a new inference variable; if it is a
+    /// universally quantified variable, you get a placeholder.
+    fn instantiate_canonical_var(
         &self,
         span: Span,
         cv_info: CanonicalVarInfo,
+        universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
     ) -> Kind<'tcx> {
         match cv_info.kind {
             CanonicalVarKind::Ty(ty_kind) => {
@@ -293,9 +369,21 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
                 ty.into()
             }
 
-            CanonicalVarKind::Region => self
-                .next_region_var(RegionVariableOrigin::MiscVariable(span))
-                .into(),
+            CanonicalVarKind::Region(ui) => self.next_region_var_in_universe(
+                RegionVariableOrigin::MiscVariable(span),
+                universe_map(ui),
+            ).into(),
+
+            CanonicalVarKind::PlaceholderRegion(ty::Placeholder { universe, name }) => {
+                let universe_mapped = universe_map(universe);
+                let placeholder_mapped = ty::Placeholder {
+                    universe: universe_mapped,
+                    name,
+                };
+                self.tcx
+                    .mk_region(ty::RePlaceholder(placeholder_mapped))
+                    .into()
+            }
         }
     }
 }
@@ -314,6 +402,7 @@ CloneTypeFoldableImpls! {
 
 BraceStructTypeFoldableImpl! {
     impl<'tcx, C> TypeFoldable<'tcx> for Canonical<'tcx, C> {
+        max_universe,
         variables,
         value,
     } where C: TypeFoldable<'tcx>
@@ -322,7 +411,7 @@ BraceStructTypeFoldableImpl! {
 BraceStructLiftImpl! {
     impl<'a, 'tcx, T> Lift<'tcx> for Canonical<'a, T> {
         type Lifted = Canonical<'tcx, T::Lifted>;
-        variables, value
+        max_universe, variables, value
     } where T: Lift<'tcx>
 }
 
diff --git a/src/librustc/infer/canonical/query_response.rs b/src/librustc/infer/canonical/query_response.rs
index 38788186eb0..b3ce5eb7e56 100644
--- a/src/librustc/infer/canonical/query_response.rs
+++ b/src/librustc/infer/canonical/query_response.rs
@@ -394,6 +394,21 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
             original_values, query_response,
         );
 
+        // For each new universe created in the query result that did
+        // not appear in the original query, create a local
+        // superuniverse.
+        let mut universe_map = original_values.universe_map.clone();
+        let num_universes_in_query = original_values.universe_map.len();
+        let num_universes_in_response = query_response.max_universe.as_usize() + 1;
+        for _ in num_universes_in_query..num_universes_in_response {
+            universe_map.push(self.create_next_universe());
+        }
+        assert!(universe_map.len() >= 1); // always have the root universe
+        assert_eq!(
+            universe_map[ty::UniverseIndex::ROOT.as_usize()],
+            ty::UniverseIndex::ROOT
+        );
+
         // Every canonical query result includes values for each of
         // the inputs to the query. Therefore, we begin by unifying
         // these values with the original inputs that were
@@ -440,9 +455,20 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
                 .variables
                 .iter()
                 .enumerate()
-                .map(|(index, info)| opt_values[BoundTyIndex::new(index)].unwrap_or_else(||
-                    self.fresh_inference_var_for_canonical_var(cause.span, *info)
-                ))
+                .map(|(index, info)| {
+                    if info.is_existential() {
+                        match opt_values[BoundTyIndex::new(index)] {
+                            Some(k) => k,
+                            None => self.instantiate_canonical_var(cause.span, *info, |u| {
+                                universe_map[u.as_usize()]
+                            }),
+                        }
+                    } else {
+                        self.instantiate_canonical_var(cause.span, *info, |u| {
+                            universe_map[u.as_usize()]
+                        })
+                    }
+                })
                 .collect(),
         };
 
diff --git a/src/librustc/infer/glb.rs b/src/librustc/infer/glb.rs
index fd14e0e40e2..8968c5949b6 100644
--- a/src/librustc/infer/glb.rs
+++ b/src/librustc/infer/glb.rs
@@ -15,7 +15,6 @@ use super::Subtype;
 
 use traits::ObligationCause;
 use ty::{self, Ty, TyCtxt};
-use ty::error::TypeError;
 use ty::relate::{Relate, RelateResult, TypeRelation};
 
 /// "Greatest lower bound" (common subtype)
@@ -76,31 +75,12 @@ impl<'combine, 'infcx, 'gcx, 'tcx> TypeRelation<'infcx, 'gcx, 'tcx>
         where T: Relate<'tcx>
     {
         debug!("binders(a={:?}, b={:?})", a, b);
-        let was_error = self.infcx().probe(|_snapshot| {
-            // Subtle: use a fresh combine-fields here because we recover
-            // from Err. Doing otherwise could propagate obligations out
-            // through our `self.obligations` field.
-            self.infcx()
-                .combine_fields(self.fields.trace.clone(), self.fields.param_env)
-                .higher_ranked_glb(a, b, self.a_is_expected)
-                .is_err()
-        });
-        debug!("binders: was_error={:?}", was_error);
 
         // When higher-ranked types are involved, computing the LUB is
         // very challenging, switch to invariance. This is obviously
         // overly conservative but works ok in practice.
-        match self.relate_with_variance(ty::Variance::Invariant, a, b) {
-            Ok(_) => Ok(a.clone()),
-            Err(err) => {
-                debug!("binders: error occurred, was_error={:?}", was_error);
-                if !was_error {
-                    Err(TypeError::OldStyleLUB(Box::new(err)))
-                } else {
-                    Err(err)
-                }
-            }
-        }
+        self.relate_with_variance(ty::Variance::Invariant, a, b)?;
+        Ok(a.clone())
     }
 }
 
diff --git a/src/librustc/infer/higher_ranked/mod.rs b/src/librustc/infer/higher_ranked/mod.rs
index d85a3e84f85..3e08a4e021a 100644
--- a/src/librustc/infer/higher_ranked/mod.rs
+++ b/src/librustc/infer/higher_ranked/mod.rs
@@ -22,7 +22,6 @@ use super::region_constraints::{TaintDirections};
 use ty::{self, TyCtxt, Binder, TypeFoldable};
 use ty::error::TypeError;
 use ty::relate::{Relate, RelateResult, TypeRelation};
-use std::collections::BTreeMap;
 use syntax_pos::Span;
 use util::nodemap::{FxHashMap, FxHashSet};
 
@@ -202,261 +201,6 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
             Ok(HrMatchResult { value: a_value })
         });
     }
-
-    pub fn higher_ranked_lub<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool)
-                                -> RelateResult<'tcx, Binder<T>>
-        where T: Relate<'tcx>
-    {
-        // Start a snapshot so we can examine "all bindings that were
-        // created as part of this type comparison".
-        return self.infcx.commit_if_ok(|snapshot| {
-            // Instantiate each bound region with a fresh region variable.
-            let span = self.trace.cause.span;
-            let (a_with_fresh, a_map) =
-                self.infcx.replace_late_bound_regions_with_fresh_var(
-                    span, HigherRankedType, a);
-            let (b_with_fresh, _) =
-                self.infcx.replace_late_bound_regions_with_fresh_var(
-                    span, HigherRankedType, b);
-
-            // Collect constraints.
-            let result0 =
-                self.lub(a_is_expected).relate(&a_with_fresh, &b_with_fresh)?;
-            let result0 =
-                self.infcx.resolve_type_vars_if_possible(&result0);
-            debug!("lub result0 = {:?}", result0);
-
-            // Generalize the regions appearing in result0 if possible
-            let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
-            let span = self.trace.cause.span;
-            let result1 =
-                fold_regions_in(
-                    self.tcx(),
-                    &result0,
-                    |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
-                                                    &new_vars, &a_map, r));
-
-            debug!("lub({:?},{:?}) = {:?}",
-                   a,
-                   b,
-                   result1);
-
-            Ok(ty::Binder::bind(result1))
-        });
-
-        fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                             span: Span,
-                                             snapshot: &CombinedSnapshot<'a, 'tcx>,
-                                             debruijn: ty::DebruijnIndex,
-                                             new_vars: &[ty::RegionVid],
-                                             a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
-                                             r0: ty::Region<'tcx>)
-                                             -> ty::Region<'tcx> {
-            // Regions that pre-dated the LUB computation stay as they are.
-            if !is_var_in_set(new_vars, r0) {
-                assert!(!r0.is_late_bound());
-                debug!("generalize_region(r0={:?}): not new variable", r0);
-                return r0;
-            }
-
-            let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both());
-
-            // Variables created during LUB computation which are
-            // *related* to regions that pre-date the LUB computation
-            // stay as they are.
-            if !tainted.iter().all(|&r| is_var_in_set(new_vars, r)) {
-                debug!("generalize_region(r0={:?}): \
-                        non-new-variables found in {:?}",
-                       r0, tainted);
-                assert!(!r0.is_late_bound());
-                return r0;
-            }
-
-            // Otherwise, the variable must be associated with at
-            // least one of the variables representing bound regions
-            // in both A and B.  Replace the variable with the "first"
-            // bound region from A that we find it to be associated
-            // with.
-            for (a_br, a_r) in a_map {
-                if tainted.iter().any(|x| x == a_r) {
-                    debug!("generalize_region(r0={:?}): \
-                            replacing with {:?}, tainted={:?}",
-                           r0, *a_br, tainted);
-                    return infcx.tcx.mk_region(ty::ReLateBound(debruijn, *a_br));
-                }
-            }
-
-            span_bug!(
-                span,
-                "region {:?} is not associated with any bound region from A!",
-                r0)
-        }
-    }
-
-    pub fn higher_ranked_glb<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool)
-                                -> RelateResult<'tcx, Binder<T>>
-        where T: Relate<'tcx>
-    {
-        debug!("higher_ranked_glb({:?}, {:?})",
-               a, b);
-
-        // Make a snapshot so we can examine "all bindings that were
-        // created as part of this type comparison".
-        return self.infcx.commit_if_ok(|snapshot| {
-            // Instantiate each bound region with a fresh region variable.
-            let (a_with_fresh, a_map) =
-                self.infcx.replace_late_bound_regions_with_fresh_var(
-                    self.trace.cause.span, HigherRankedType, a);
-            let (b_with_fresh, b_map) =
-                self.infcx.replace_late_bound_regions_with_fresh_var(
-                    self.trace.cause.span, HigherRankedType, b);
-            let a_vars = var_ids(self, &a_map);
-            let b_vars = var_ids(self, &b_map);
-
-            // Collect constraints.
-            let result0 =
-                self.glb(a_is_expected).relate(&a_with_fresh, &b_with_fresh)?;
-            let result0 =
-                self.infcx.resolve_type_vars_if_possible(&result0);
-            debug!("glb result0 = {:?}", result0);
-
-            // Generalize the regions appearing in result0 if possible
-            let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
-            let span = self.trace.cause.span;
-            let result1 =
-                fold_regions_in(
-                    self.tcx(),
-                    &result0,
-                    |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
-                                                    &new_vars,
-                                                    &a_map, &a_vars, &b_vars,
-                                                    r));
-
-            debug!("glb({:?},{:?}) = {:?}",
-                   a,
-                   b,
-                   result1);
-
-            Ok(ty::Binder::bind(result1))
-        });
-
-        fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                             span: Span,
-                                             snapshot: &CombinedSnapshot<'a, 'tcx>,
-                                             debruijn: ty::DebruijnIndex,
-                                             new_vars: &[ty::RegionVid],
-                                             a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
-                                             a_vars: &[ty::RegionVid],
-                                             b_vars: &[ty::RegionVid],
-                                             r0: ty::Region<'tcx>)
-                                             -> ty::Region<'tcx> {
-            if !is_var_in_set(new_vars, r0) {
-                assert!(!r0.is_late_bound());
-                return r0;
-            }
-
-            let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both());
-
-            let mut a_r = None;
-            let mut b_r = None;
-            let mut only_new_vars = true;
-            for r in &tainted {
-                if is_var_in_set(a_vars, *r) {
-                    if a_r.is_some() {
-                        return fresh_bound_variable(infcx, debruijn);
-                    } else {
-                        a_r = Some(*r);
-                    }
-                } else if is_var_in_set(b_vars, *r) {
-                    if b_r.is_some() {
-                        return fresh_bound_variable(infcx, debruijn);
-                    } else {
-                        b_r = Some(*r);
-                    }
-                } else if !is_var_in_set(new_vars, *r) {
-                    only_new_vars = false;
-                }
-            }
-
-            // NB---I do not believe this algorithm computes
-            // (necessarily) the GLB.  As written it can
-            // spuriously fail. In particular, if there is a case
-            // like: |fn(&a)| and fn(fn(&b)), where a and b are
-            // free, it will return fn(&c) where c = GLB(a,b).  If
-            // however this GLB is not defined, then the result is
-            // an error, even though something like
-            // "fn<X>(fn(&X))" where X is bound would be a
-            // subtype of both of those.
-            //
-            // The problem is that if we were to return a bound
-            // variable, we'd be computing a lower-bound, but not
-            // necessarily the *greatest* lower-bound.
-            //
-            // Unfortunately, this problem is non-trivial to solve,
-            // because we do not know at the time of computing the GLB
-            // whether a GLB(a,b) exists or not, because we haven't
-            // run region inference (or indeed, even fully computed
-            // the region hierarchy!). The current algorithm seems to
-            // works ok in practice.
-
-            if a_r.is_some() && b_r.is_some() && only_new_vars {
-                // Related to exactly one bound variable from each fn:
-                return rev_lookup(infcx, span, a_map, a_r.unwrap());
-            } else if a_r.is_none() && b_r.is_none() {
-                // Not related to bound variables from either fn:
-                assert!(!r0.is_late_bound());
-                return r0;
-            } else {
-                // Other:
-                return fresh_bound_variable(infcx, debruijn);
-            }
-        }
-
-        fn rev_lookup<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                      span: Span,
-                                      a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
-                                      r: ty::Region<'tcx>) -> ty::Region<'tcx>
-        {
-            for (a_br, a_r) in a_map {
-                if *a_r == r {
-                    return infcx.tcx.mk_region(ty::ReLateBound(ty::INNERMOST, *a_br));
-                }
-            }
-            span_bug!(
-                span,
-                "could not find original bound region for {:?}",
-                r);
-        }
-
-        fn fresh_bound_variable<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                                debruijn: ty::DebruijnIndex)
-                                                -> ty::Region<'tcx> {
-            infcx.borrow_region_constraints().new_bound(infcx.tcx, debruijn)
-        }
-    }
-}
-
-fn var_ids<'a, 'gcx, 'tcx>(fields: &CombineFields<'a, 'gcx, 'tcx>,
-                           map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
-                           -> Vec<ty::RegionVid> {
-    map.iter()
-       .map(|(_, &r)| match *r {
-           ty::ReVar(r) => { r }
-           _ => {
-               span_bug!(
-                   fields.trace.cause.span,
-                   "found non-region-vid: {:?}",
-                   r);
-           }
-       })
-       .collect()
-}
-
-fn is_var_in_set(new_vars: &[ty::RegionVid], r: ty::Region<'_>) -> bool {
-    match *r {
-        ty::ReVar(ref v) => new_vars.iter().any(|x| x == v),
-        _ => false
-    }
 }
 
 fn fold_regions_in<'a, 'gcx, 'tcx, T, F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
diff --git a/src/librustc/infer/lub.rs b/src/librustc/infer/lub.rs
index 55c7eef607b..8875b4169dd 100644
--- a/src/librustc/infer/lub.rs
+++ b/src/librustc/infer/lub.rs
@@ -15,7 +15,6 @@ use super::Subtype;
 
 use traits::ObligationCause;
 use ty::{self, Ty, TyCtxt};
-use ty::error::TypeError;
 use ty::relate::{Relate, RelateResult, TypeRelation};
 
 /// "Least upper bound" (common supertype)
@@ -76,31 +75,12 @@ impl<'combine, 'infcx, 'gcx, 'tcx> TypeRelation<'infcx, 'gcx, 'tcx>
         where T: Relate<'tcx>
     {
         debug!("binders(a={:?}, b={:?})", a, b);
-        let was_error = self.infcx().probe(|_snapshot| {
-            // Subtle: use a fresh combine-fields here because we recover
-            // from Err. Doing otherwise could propagate obligations out
-            // through our `self.obligations` field.
-            self.infcx()
-                .combine_fields(self.fields.trace.clone(), self.fields.param_env)
-                .higher_ranked_lub(a, b, self.a_is_expected)
-                .is_err()
-        });
-        debug!("binders: was_error={:?}", was_error);
 
         // When higher-ranked types are involved, computing the LUB is
         // very challenging, switch to invariance. This is obviously
         // overly conservative but works ok in practice.
-        match self.relate_with_variance(ty::Variance::Invariant, a, b) {
-            Ok(_) => Ok(a.clone()),
-            Err(err) => {
-                debug!("binders: error occurred, was_error={:?}", was_error);
-                if !was_error {
-                    Err(TypeError::OldStyleLUB(Box::new(err)))
-                } else {
-                    Err(err)
-                }
-            }
-        }
+        self.relate_with_variance(ty::Variance::Invariant, a, b)?;
+        Ok(a.clone())
     }
 }
 
diff --git a/src/librustc/traits/query/type_op/implied_outlives_bounds.rs b/src/librustc/traits/query/type_op/implied_outlives_bounds.rs
index b113a322d37..d5233851db8 100644
--- a/src/librustc/traits/query/type_op/implied_outlives_bounds.rs
+++ b/src/librustc/traits/query/type_op/implied_outlives_bounds.rs
@@ -38,19 +38,13 @@ impl<'gcx: 'tcx, 'tcx> super::QueryTypeOp<'gcx, 'tcx> for ImpliedOutlivesBounds<
         tcx: TyCtxt<'_, 'gcx, 'tcx>,
         canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>,
     ) -> Fallible<CanonicalizedQueryResponse<'gcx, Self::QueryResponse>> {
-        // FIXME the query should take a `ImpliedOutlivesBounds`
-        let Canonical {
-            variables,
-            value:
-                ParamEnvAnd {
-                    param_env,
-                    value: ImpliedOutlivesBounds { ty },
-                },
-        } = canonicalized;
-        let canonicalized = Canonical {
-            variables,
-            value: param_env.and(ty),
-        };
+        // FIXME this `unchecked_map` is only necessary because the
+        // query is defined as taking a `ParamEnvAnd<Ty>`; it should
+        // take a `ImpliedOutlivesBounds` instead
+        let canonicalized = canonicalized.unchecked_map(|ParamEnvAnd { param_env, value }| {
+            let ImpliedOutlivesBounds { ty } = value;
+            param_env.and(ty)
+        });
 
         tcx.implied_outlives_bounds(canonicalized)
     }
diff --git a/src/librustc/traits/query/type_op/outlives.rs b/src/librustc/traits/query/type_op/outlives.rs
index a36c5accd2a..cd7c6d76eab 100644
--- a/src/librustc/traits/query/type_op/outlives.rs
+++ b/src/librustc/traits/query/type_op/outlives.rs
@@ -59,18 +59,10 @@ where
         // FIXME convert to the type expected by the `dropck_outlives`
         // query. This should eventually be fixed by changing the
         // *underlying query*.
-        let Canonical {
-            variables,
-            value:
-                ParamEnvAnd {
-                    param_env,
-                    value: DropckOutlives { dropped_ty },
-                },
-        } = canonicalized;
-        let canonicalized = Canonical {
-            variables,
-            value: param_env.and(dropped_ty),
-        };
+        let canonicalized = canonicalized.unchecked_map(|ParamEnvAnd { param_env, value }| {
+            let DropckOutlives { dropped_ty } = value;
+            param_env.and(dropped_ty)
+        });
 
         tcx.dropck_outlives(canonicalized)
     }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 2ea16823cc6..e2a5fdd3622 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -1368,7 +1368,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
         // Winnow, but record the exact outcome of evaluation, which
         // is needed for specialization. Propagate overflow if it occurs.
-        let mut candidates = candidates.into_iter()
+        let mut candidates = candidates
+            .into_iter()
             .map(|c| match self.evaluate_candidate(stack, &c) {
                 Ok(eval) if eval.may_apply() => Ok(Some(EvaluatedCandidate {
                     candidate: c,
@@ -1377,8 +1378,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 Ok(_) => Ok(None),
                 Err(OverflowError) => Err(Overflow),
             })
-           .flat_map(Result::transpose)
-           .collect::<Result<Vec<_>, _>>()?;
+            .flat_map(Result::transpose)
+            .collect::<Result<Vec<_>, _>>()?;
 
         debug!(
             "winnowed to {} candidates for {:?}: {:?}",
@@ -3004,9 +3005,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         let self_ty = self.infcx
             .shallow_resolve(*obligation.self_ty().skip_binder());
         let poly_trait_ref = match self_ty.sty {
-            ty::Dynamic(ref data, ..) => {
-                data.principal().with_self_ty(self.tcx(), self_ty)
-            }
+            ty::Dynamic(ref data, ..) => data.principal().with_self_ty(self.tcx(), self_ty),
             _ => span_bug!(obligation.cause.span, "object candidate with non-object"),
         };
 
@@ -3666,8 +3665,17 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         closure_def_id: DefId,
         substs: ty::ClosureSubsts<'tcx>,
     ) -> ty::PolyTraitRef<'tcx> {
+        debug!(
+            "closure_trait_ref_unnormalized(obligation={:?}, closure_def_id={:?}, substs={:?})",
+            obligation, closure_def_id, substs,
+        );
         let closure_type = self.infcx.closure_sig(closure_def_id, substs);
 
+        debug!(
+            "closure_trait_ref_unnormalized: closure_type = {:?}",
+            closure_type
+        );
+
         // (1) Feels icky to skip the binder here, but OTOH we know
         // that the self-type is an unboxed closure type and hence is
         // in fact unparameterized (or at least does not reference any
diff --git a/src/librustc/ty/error.rs b/src/librustc/ty/error.rs
index ed6e372fe76..855983042c0 100644
--- a/src/librustc/ty/error.rs
+++ b/src/librustc/ty/error.rs
@@ -53,8 +53,6 @@ pub enum TypeError<'tcx> {
     ProjectionMismatched(ExpectedFound<DefId>),
     ProjectionBoundsLength(ExpectedFound<usize>),
     ExistentialMismatch(ExpectedFound<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>),
-
-    OldStyleLUB(Box<TypeError<'tcx>>),
 }
 
 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Debug, Copy)]
@@ -166,9 +164,6 @@ impl<'tcx> fmt::Display for TypeError<'tcx> {
                 report_maybe_different(f, &format!("trait `{}`", values.expected),
                                        &format!("trait `{}`", values.found))
             }
-            OldStyleLUB(ref err) => {
-                write!(f, "{}", err)
-            }
         }
     }
 }
@@ -266,12 +261,6 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
                     }
                 }
             },
-            OldStyleLUB(err) => {
-                db.note("this was previously accepted by the compiler but has been phased out");
-                db.note("for more information, see https://github.com/rust-lang/rust/issues/45852");
-
-                self.note_and_explain_type_err(db, &err, sp);
-            }
             CyclicTy(ty) => {
                 // Watch out for various cases of cyclic types and try to explain.
                 if ty.is_closure() || ty.is_generator() {
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index f8fc2cc8303..ad26383df6a 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1522,10 +1522,17 @@ impl UniverseIndex {
 
     /// True if `self` can name a name from `other` -- in other words,
     /// if the set of names in `self` is a superset of those in
-    /// `other`.
+    /// `other` (`self >= other`).
     pub fn can_name(self, other: UniverseIndex) -> bool {
         self.private >= other.private
     }
+
+    /// True if `self` cannot name some names from `other` -- in other
+    /// words, if the set of names in `self` is a strict subset of
+    /// those in `other` (`self < other`).
+    pub fn cannot_name(self, other: UniverseIndex) -> bool {
+        self.private < other.private
+    }
 }
 
 /// The "placeholder index" fully defines a placeholder region.
@@ -1540,6 +1547,8 @@ pub struct Placeholder {
     pub name: BoundRegion,
 }
 
+impl_stable_hash_for!(struct Placeholder { universe, name });
+
 /// When type checking, we use the `ParamEnv` to track
 /// details about the set of where-clauses that are in scope at this
 /// particular point.
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index ba5b714a0e7..05f5f923557 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -455,7 +455,6 @@ impl<'a, 'tcx> Lift<'tcx> for ty::error::TypeError<'a> {
             ProjectionMismatched(x) => ProjectionMismatched(x),
             ProjectionBoundsLength(x) => ProjectionBoundsLength(x),
             Sorts(ref x) => return tcx.lift(x).map(Sorts),
-            OldStyleLUB(ref x) => return tcx.lift(x).map(OldStyleLUB),
             ExistentialMismatch(ref x) => return tcx.lift(x).map(ExistentialMismatch)
         })
     }
@@ -1003,7 +1002,6 @@ EnumTypeFoldableImpl! {
         (ty::error::TypeError::ProjectionBoundsLength)(x),
         (ty::error::TypeError::Sorts)(x),
         (ty::error::TypeError::ExistentialMismatch)(x),
-        (ty::error::TypeError::OldStyleLUB)(x),
     }
 }