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

6 files changed, 247 insertions, 330 deletions

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())
     }
 }