add `canonicalize` method to `InferCtxt` [VIC]

28 files changed, 1121 insertions, 16 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index d927a151610..ae67d592ba3 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -19,6 +19,7 @@ use std::cell::RefCell;
 use std::hash as std_hash;
 use std::mem;
 use middle::region;
+use infer;
 use traits;
 use ty;
 use mir;
@@ -85,6 +86,9 @@ for ty::RegionKind {
             ty::ReEmpty => {
                 // No variant fields to hash for these ...
             }
+            ty::ReCanonical(c) => {
+                c.hash_stable(hcx, hasher);
+            }
             ty::ReLateBound(db, ty::BrAnon(i)) => {
                 db.depth.hash_stable(hcx, hasher);
                 i.hash_stable(hcx, hasher);
@@ -130,6 +134,16 @@ impl<'a> HashStable<StableHashingContext<'a>> for ty::RegionVid {
     }
 }
 
+impl<'gcx> HashStable<StableHashingContext<'gcx>> for ty::CanonicalVar {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'gcx>,
+                                          hasher: &mut StableHasher<W>) {
+        use rustc_data_structures::indexed_vec::Idx;
+        self.index().hash_stable(hcx, hasher);
+    }
+}
+
 impl<'a, 'gcx> HashStable<StableHashingContext<'a>>
 for ty::adjustment::AutoBorrow<'gcx> {
     fn hash_stable<W: StableHasherResult>(&self,
@@ -1229,11 +1243,52 @@ for traits::VtableGeneratorData<'gcx, N> where N: HashStable<StableHashingContex
     }
 }
 
-impl<'gcx> HashStable<StableHashingContext<'gcx>>
+impl<'a> HashStable<StableHashingContext<'a>>
 for ty::UniverseIndex {
     fn hash_stable<W: StableHasherResult>(&self,
-                                          hcx: &mut StableHashingContext<'gcx>,
+                                          hcx: &mut StableHashingContext<'a>,
                                           hasher: &mut StableHasher<W>) {
         self.depth().hash_stable(hcx, hasher);
     }
 }
+
+impl_stable_hash_for!(
+    impl<'tcx, V> for struct infer::canonical::Canonical<'tcx, V> {
+        variables, value
+    }
+);
+
+impl_stable_hash_for!(
+    impl<'tcx> for struct infer::canonical::CanonicalVarValues<'tcx> {
+        var_values
+    }
+);
+
+impl_stable_hash_for!(struct infer::canonical::CanonicalVarInfo {
+    kind
+});
+
+impl_stable_hash_for!(enum infer::canonical::CanonicalVarKind {
+    Ty(k),
+    Region
+});
+
+impl_stable_hash_for!(enum infer::canonical::CanonicalTyVarKind {
+    General,
+    Int,
+    Float
+});
+
+impl_stable_hash_for!(
+    impl<'tcx, R> for struct infer::canonical::QueryResult<'tcx, R> {
+        var_values, region_constraints, certainty, value
+    }
+);
+
+impl_stable_hash_for!(struct infer::canonical::QueryRegionConstraints<'tcx> {
+    region_outlives, ty_outlives
+});
+
+impl_stable_hash_for!(enum infer::canonical::Certainty {
+    Proven, Ambiguous
+});
diff --git a/src/librustc/infer/canonical.rs b/src/librustc/infer/canonical.rs
new file mode 100644
index 00000000000..c1c7337860e
--- /dev/null
+++ b/src/librustc/infer/canonical.rs
@@ -0,0 +1,928 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! **Canonicalization** is the key to constructing a query in the
+//! middle of type inference. Ordinarily, it is not possible to store
+//! types from type inference in query keys, because they contain
+//! references to inference variables whose lifetimes are too short
+//! and so forth. Canonicalizing a value T1 using `canonicalize_query`
+//! produces two things:
+//!
+//! - a value T2 where each unbound inference variable has been
+//!   replaced with a **canonical variable**;
+//! - a map M (of type `CanonicalVarValues`) from those canonical
+//!   variables back to the original.
+//!
+//! We can then do queries using T2. These will give back constriants
+//! on the canonical variables which can be translated, using the map
+//! M, into constraints in our source context. This process of
+//! translating the results back is done by the
+//! `instantiate_query_result` method.
+
+use infer::{InferCtxt, InferOk, InferResult, RegionVariableOrigin, TypeVariableOrigin};
+use rustc_data_structures::indexed_vec::Idx;
+use std::fmt::Debug;
+use syntax::codemap::Span;
+use traits::{Obligation, ObligationCause, PredicateObligation};
+use ty::{self, CanonicalVar, Lift, Region, Slice, Ty, TyCtxt, TypeFlags};
+use ty::subst::{Kind, UnpackedKind};
+use ty::fold::{TypeFoldable, TypeFolder};
+use util::common::CellUsizeExt;
+
+use rustc_data_structures::indexed_vec::IndexVec;
+use rustc_data_structures::fx::FxHashMap;
+
+/// A "canonicalized" type `V` is one where all free inference
+/// variables have been rewriten to "canonical vars". These are
+/// numbered starting from 0 in order of first appearance.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub struct Canonical<'gcx, V> {
+    pub variables: CanonicalVarInfos<'gcx>,
+    pub value: V,
+}
+
+pub type CanonicalVarInfos<'gcx> = &'gcx Slice<CanonicalVarInfo>;
+
+/// A set of values corresponding to the canonical variables from some
+/// `Canonical`. You can give these values to
+/// `canonical_value.substitute` to substitute them into the canonical
+/// value at the right places.
+///
+/// When you canonicalize a value `V`, you get back one of these
+/// vectors with the original values that were replaced by canonical
+/// variables.
+///
+/// You can also use `infcx.fresh_inference_vars_for_canonical_vars`
+/// to get back a `CanonicalVarValues` containing fresh inference
+/// variables.
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct CanonicalVarValues<'tcx> {
+    pub var_values: IndexVec<CanonicalVar, Kind<'tcx>>,
+}
+
+/// 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,
+/// with fresh inference variables replacing the canonical values.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub struct CanonicalVarInfo {
+    pub kind: CanonicalVarKind,
+}
+
+/// 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.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum CanonicalVarKind {
+    /// Some kind of type inference variable.
+    Ty(CanonicalTyVarKind),
+
+    /// Region variable `'?R`.
+    Region,
+}
+
+/// Rust actually has more than one category of type variables;
+/// notably, the type variables we create for literals (e.g., 22 or
+/// 22.) can only be instantiated with integral/float types (e.g.,
+/// usize or f32). In order to faithfully reproduce a type, we need to
+/// know what set of types a given type variable can be unified with.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum CanonicalTyVarKind {
+    /// General type variable `?T` that can be unified with arbitrary types.
+    General,
+
+    /// Integral type variable `?I` (that can only be unified with integral types).
+    Int,
+
+    /// Floating-point type variable `?F` (that can only be unified with float types).
+    Float,
+}
+
+/// After we execute a query with a canonicalized key, we get back a
+/// `Canonical<QueryResult<..>>`. You can use
+/// `instantiate_query_result` to access the data in this result.
+#[derive(Clone, Debug)]
+pub struct QueryResult<'tcx, R> {
+    pub var_values: CanonicalVarValues<'tcx>,
+    pub region_constraints: QueryRegionConstraints<'tcx>,
+    pub certainty: Certainty,
+    pub value: R,
+}
+
+/// Indicates whether or not we were able to prove the query to be
+/// true.
+#[derive(Copy, Clone, Debug)]
+pub enum Certainty {
+    /// The query is known to be true, presuming that you apply the
+    /// given `var_values` and the region-constraints are satisfied.
+    Proven,
+
+    /// The query is not known to be true, but also not known to be
+    /// false. The `var_values` represent *either* values that must
+    /// hold in order for the query to be true, or helpful tips that
+    /// *might* make it true. Currently rustc's trait solver cannot
+    /// distinguish the two (e.g., due to our preference for where
+    /// clauses over impls).
+    ///
+    /// After some unifiations and things have been done, it makes
+    /// sense to try and prove again -- of course, at that point, the
+    /// canonical form will be different, making this a distinct
+    /// query.
+    Ambiguous,
+}
+
+impl Certainty {
+    pub fn is_proven(&self) -> bool {
+        match self {
+            Certainty::Proven => true,
+            Certainty::Ambiguous => false,
+        }
+    }
+
+    pub fn is_ambiguous(&self) -> bool {
+        !self.is_proven()
+    }
+}
+
+impl<'tcx, R> QueryResult<'tcx, R> {
+    pub fn is_proven(&self) -> bool {
+        self.certainty.is_proven()
+    }
+
+    pub fn is_ambiguous(&self) -> bool {
+        !self.is_proven()
+    }
+}
+
+impl<'tcx, R> Canonical<'tcx, QueryResult<'tcx, R>> {
+    pub fn is_proven(&self) -> bool {
+        self.value.is_proven()
+    }
+
+    pub fn is_ambiguous(&self) -> bool {
+        !self.is_proven()
+    }
+}
+
+/// Subset of `RegionConstraintData` produced by trait query.
+#[derive(Clone, Debug, Default)]
+pub struct QueryRegionConstraints<'tcx> {
+    pub region_outlives: Vec<(Region<'tcx>, Region<'tcx>)>,
+    pub ty_outlives: Vec<(Ty<'tcx>, Region<'tcx>)>,
+}
+
+/// Trait implemented by values that can be canonicalized. It mainly
+/// serves to identify the interning table we will use.
+pub trait Canonicalize<'gcx: 'tcx, 'tcx>: TypeFoldable<'tcx> + Lift<'gcx> {
+    type Canonicalized: 'gcx + Debug;
+
+    /// After a value has been fully canonicalized and lifted, this
+    /// method will allocate it in a global arena.
+    fn intern(
+        gcx: TyCtxt<'_, 'gcx, 'gcx>,
+        value: Canonical<'gcx, Self::Lifted>,
+    ) -> Self::Canonicalized;
+}
+
+impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
+    /// Creates a substitution S for the canonical value with fresh
+    /// inference variables and applies it to the canonical value.
+    /// Returns both the instantiated result *and* the substitution S.
+    ///
+    /// This is useful at the start of a query: it basically brings
+    /// the canonical value "into scope" within your new infcx. At the
+    /// end of processing, the substitution S (once canonicalized)
+    /// then represents the values that you computed for each of the
+    /// canonical inputs to your query.
+    pub fn instantiate_canonical_with_fresh_inference_vars<T>(
+        &self,
+        span: Span,
+        canonical: &Canonical<'tcx, T>,
+    ) -> (T, CanonicalVarValues<'tcx>)
+    where
+        T: TypeFoldable<'tcx>,
+    {
+        let canonical_inference_vars =
+            self.fresh_inference_vars_for_canonical_vars(span, canonical.variables);
+        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.
+    pub fn fresh_inference_vars_for_canonical_vars(
+        &self,
+        span: Span,
+        variables: &Slice<CanonicalVarInfo>,
+    ) -> CanonicalVarValues<'tcx> {
+        let var_values: IndexVec<CanonicalVar, Kind<'tcx>> = variables
+            .iter()
+            .map(|info| self.fresh_inference_var_for_canonical_var(span, *info))
+            .collect();
+
+        CanonicalVarValues { var_values }
+    }
+
+    /// Given the "info" about a canonical variable, creates a fresh
+    /// inference variable with the same characteristics.
+    pub fn fresh_inference_var_for_canonical_var(
+        &self,
+        span: Span,
+        cv_info: CanonicalVarInfo,
+    ) -> Kind<'tcx> {
+        match cv_info.kind {
+            CanonicalVarKind::Ty(ty_kind) => {
+                let ty = match ty_kind {
+                    CanonicalTyVarKind::General => {
+                        self.next_ty_var(
+                            // FIXME(#48696) this handling of universes is not right.
+                            ty::UniverseIndex::ROOT,
+                            TypeVariableOrigin::MiscVariable(span),
+                        )
+                    }
+
+                    CanonicalTyVarKind::Int => self.tcx.mk_int_var(self.next_int_var_id()),
+
+                    CanonicalTyVarKind::Float => self.tcx.mk_float_var(self.next_float_var_id()),
+                };
+                Kind::from(ty)
+            }
+
+            CanonicalVarKind::Region => {
+                Kind::from(self.next_region_var(RegionVariableOrigin::MiscVariable(span)))
+            }
+        }
+    }
+
+    /// Given the (canonicalized) result to a canonical query,
+    /// instantiates the result so it can be used, plugging in the
+    /// values from the canonical query. (Note that the result may
+    /// have been ambiguous; you should check the certainty level of
+    /// the query before applying this function.)
+    ///
+    /// It's easiest to explain what is happening here by
+    /// example. Imagine we start out with the query `?A: Foo<'static,
+    /// ?B>`. We would canonicalize that by introducing two variables:
+    ///
+    ///     ?0: Foo<'?1, ?2>
+    ///
+    /// (Note that all regions get replaced with variables always,
+    /// even "known" regions like `'static`.) After canonicalization,
+    /// we also get back an array with the "original values" for each
+    /// canonicalized variable:
+    ///
+    ///     [?A, 'static, ?B]
+    ///
+    /// Now we do the query and get back some result R. As part of that
+    /// result, we'll have an array of values for the canonical inputs.
+    /// For example, the canonical result might be:
+    ///
+    /// ```
+    /// for<2> {
+    ///     values = [ Vec<?0>, '1, ?0 ]
+    ///                    ^^   ^^  ^^ these are variables in the result!
+    ///     ...
+    /// }
+    /// ```
+    ///
+    /// Note that this result is itself canonical and may include some
+    /// variables (in this case, `?0`).
+    ///
+    /// What we want to do conceptually is to (a) instantiate each of the
+    /// canonical variables in the result with a fresh inference variable
+    /// and then (b) unify the values in the result with the original values.
+    /// Doing step (a) would yield a result of
+    ///
+    /// ```
+    /// {
+    ///     values = [ Vec<?C>, '?X, ?C ]
+    ///                    ^^   ^^^ fresh inference variables in `self`
+    ///     ..
+    /// }
+    /// ```
+    ///
+    /// Step (b) would then unify:
+    ///
+    /// ```
+    /// ?A with Vec<?C>
+    /// 'static with '?X
+    /// ?B with ?C
+    /// ```
+    ///
+    /// But what we actually do is a mildly optimized variant of
+    /// that. Rather than eagerly instantiating all of the canonical
+    /// values in the result with variables, we instead walk the
+    /// vector of values, looking for cases where the value is just a
+    /// canonical variable. In our example, `values[2]` is `?C`, so
+    /// that we means we can deduce that `?C := ?B and `'?X :=
+    /// 'static`. This gives us a partial set of values. Anything for
+    /// which we do not find a value, we create an inference variable
+    /// for. **Then** we unify.
+    pub fn instantiate_query_result<R>(
+        &self,
+        cause: &ObligationCause<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        original_values: &CanonicalVarValues<'tcx>,
+        query_result: &Canonical<'tcx, QueryResult<'tcx, R>>,
+    ) -> InferResult<'tcx, R>
+    where
+        R: Debug + TypeFoldable<'tcx>,
+    {
+        debug!(
+            "instantiate_query_result(original_values={:#?}, query_result={:#?})",
+            original_values, query_result,
+        );
+
+        // 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
+        // canonicalized.
+        let result_values = &query_result.value.var_values;
+        assert_eq!(original_values.len(), result_values.len());
+
+        // Quickly try to find initial values for the canonical
+        // variables in the result in terms of the query. We do this
+        // by iterating down the values that the query gave to each of
+        // the canonical inputs. If we find that one of those values
+        // is directly equal to one of the canonical variables in the
+        // result, then we can type the corresponding value from the
+        // input. See the example above.
+        let mut opt_values: IndexVec<CanonicalVar, Option<Kind<'tcx>>> =
+            IndexVec::from_elem_n(None, query_result.variables.len());
+
+        // In terms of our example above, we are iterating over pairs like:
+        // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)]
+        for (original_value, result_value) in original_values.iter().zip(result_values) {
+            match result_value.unpack() {
+                UnpackedKind::Type(result_value) => {
+                    // e.g., here `result_value` might be `?0` in the example above...
+                    if let ty::TyInfer(ty::InferTy::CanonicalTy(index)) = result_value.sty {
+                        // in which case we would set `canonical_vars[0]` to `Some(?U)`.
+                        opt_values[index] = Some(original_value);
+                    }
+                }
+                UnpackedKind::Lifetime(result_value) => {
+                    // e.g., here `result_value` might be `'?1` in the example above...
+                    if let &ty::RegionKind::ReCanonical(index) = result_value {
+                        // in which case we would set `canonical_vars[0]` to `Some('static)`.
+                        opt_values[index] = Some(original_value);
+                    }
+                }
+            }
+        }
+
+        // Create a result substitution: if we found a value for a
+        // given variable in the loop above, use that. Otherwise, use
+        // a fresh inference variable.
+        let result_subst = &CanonicalVarValues {
+            var_values: query_result
+                .variables
+                .iter()
+                .enumerate()
+                .map(|(index, info)| match opt_values[CanonicalVar::new(index)] {
+                    Some(k) => k,
+                    None => self.fresh_inference_var_for_canonical_var(cause.span, *info),
+                })
+                .collect(),
+        };
+
+        // Apply the result substitution to the query.
+        let QueryResult {
+            var_values: query_values,
+            region_constraints: query_region_constraints,
+            certainty: _,
+            value: user_result,
+        } = query_result.substitute(self.tcx, result_subst);
+
+        // Unify the original values for the canonical variables in
+        // the input with the value found in the query
+        // post-substitution. Often, but not always, this is a no-op,
+        // because we already found the mapping in the first step.
+        let mut obligations =
+            self.unify_canonical_vars(cause, param_env, original_values, &query_values)?
+                .into_obligations();
+
+        obligations.extend(self.query_region_constraints_into_obligations(
+            cause,
+            param_env,
+            query_region_constraints,
+        ));
+
+        Ok(InferOk {
+            value: user_result,
+            obligations,
+        })
+    }
+
+    /// Converts the region constraints resulting from a query into an
+    /// iterator of obligations.
+    fn query_region_constraints_into_obligations<'a>(
+        &self,
+        cause: &'a ObligationCause<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        query_region_constraints: QueryRegionConstraints<'tcx>,
+    ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a {
+        let QueryRegionConstraints {
+            region_outlives,
+            ty_outlives,
+        } = query_region_constraints;
+
+        let region_obligations = region_outlives.into_iter().map(move |(r1, r2)| {
+            Obligation::new(
+                cause.clone(),
+                param_env,
+                ty::Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r1, r2))),
+            )
+        });
+
+        let ty_obligations = ty_outlives.into_iter().map(move |(t1, r2)| {
+            Obligation::new(
+                cause.clone(),
+                param_env,
+                ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(t1, r2))),
+            )
+        });
+
+        region_obligations.chain(ty_obligations)
+    }
+
+    /// Given two sets of values for the same set of canonical variables, unify them.
+    pub fn unify_canonical_vars(
+        &self,
+        cause: &ObligationCause<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        variables1: &CanonicalVarValues<'tcx>,
+        variables2: &CanonicalVarValues<'tcx>,
+    ) -> InferResult<'tcx, ()> {
+        assert_eq!(variables1.var_values.len(), variables2.var_values.len());
+        self.commit_if_ok(|_| {
+            let mut obligations = vec![];
+            for (value1, value2) in variables1.var_values.iter().zip(&variables2.var_values) {
+                match (value1.unpack(), value2.unpack()) {
+                    (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => {
+                        obligations
+                            .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
+                    }
+                    (
+                        UnpackedKind::Lifetime(ty::ReErased),
+                        UnpackedKind::Lifetime(ty::ReErased),
+                    ) => {
+                        // no action needed
+                    }
+                    (UnpackedKind::Lifetime(v1), UnpackedKind::Lifetime(v2)) => {
+                        obligations
+                            .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
+                    }
+                    _ => {
+                        bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,);
+                    }
+                }
+            }
+            Ok(InferOk {
+                value: (),
+                obligations,
+            })
+        })
+    }
+
+    /// Canonicalizes a query value `V`. When we canonicalize a query,
+    /// we not only canonicalize unbound inference variables, but we
+    /// *also* replace all free regions whatsoever. So for example a
+    /// query like `T: Trait<'static>` would be canonicalized to
+    ///
+    ///     T: Trait<'?0>
+    ///
+    /// with a mapping M that maps `'?0` to `'static`.
+    pub fn canonicalize_query<V>(&self, value: &V) -> (V::Canonicalized, CanonicalVarValues<'tcx>)
+    where
+        V: Canonicalize<'gcx, 'tcx>,
+    {
+        self.tcx.sess.perf_stats.queries_canonicalized.increment();
+
+        Canonicalizer::canonicalize(
+            value,
+            Some(self),
+            self.tcx,
+            CanonicalizeAllFreeRegions(true),
+        )
+    }
+
+    /// Canonicalizes a query *response* `V`. When we canonicalize a
+    /// query response, we only canonicalize unbound inference
+    /// variables, and we leave other free regions alone. So,
+    /// continuing with the example from `canonicalize_query`, if
+    /// there was an input query `T: Trait<'static>`, it would have
+    /// been canonicalized to
+    ///
+    ///     T: Trait<'?0>
+    ///
+    /// with a mapping M that maps `'?0` to `'static`. But if we found that there
+    /// exists only one possible impl of `Trait`, and it looks like
+    ///
+    ///     impl<T> Trait<'static> for T { .. }
+    ///
+    /// then we would prepare a query result R that (among other
+    /// things) includes a mapping to `'?0 := 'static`. When
+    /// canonicalizing this query result R, we would leave this
+    /// reference to `'static` alone.
+    pub fn canonicalize_response<V>(
+        &self,
+        value: &V,
+    ) -> (V::Canonicalized, CanonicalVarValues<'tcx>)
+    where
+        V: Canonicalize<'gcx, 'tcx>,
+    {
+        Canonicalizer::canonicalize(
+            value,
+            Some(self),
+            self.tcx,
+            CanonicalizeAllFreeRegions(false),
+        )
+    }
+}
+
+impl<'cx, 'gcx> TyCtxt<'cx, 'gcx, 'gcx> {
+    /// Canonicalize a value that doesn't have any inference variables
+    /// or other things (and we know it).
+    pub fn canonicalize_global<V>(self, value: &V) -> (V::Canonicalized, CanonicalVarValues<'gcx>)
+    where
+        V: Canonicalize<'gcx, 'gcx>,
+    {
+        Canonicalizer::canonicalize(value, None, self, CanonicalizeAllFreeRegions(false))
+    }
+}
+
+/// If this flag is true, then all free regions will be replaced with
+/// a canonical var. This is used to make queries as generic as
+/// possible. For example, the query `F: Foo<'static>` would be
+/// canonicalized to `F: Foo<'0>`.
+struct CanonicalizeAllFreeRegions(bool);
+
+struct Canonicalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
+    infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>,
+    tcx: TyCtxt<'cx, 'gcx, 'tcx>,
+    variables: IndexVec<CanonicalVar, CanonicalVarInfo>,
+    indices: FxHashMap<Kind<'tcx>, CanonicalVar>,
+    var_values: IndexVec<CanonicalVar, Kind<'tcx>>,
+    canonicalize_all_free_regions: CanonicalizeAllFreeRegions,
+    needs_canonical_flags: TypeFlags,
+}
+
+impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> {
+    fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
+        self.tcx
+    }
+
+    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
+        match *r {
+            ty::ReLateBound(..) => {
+                // leave bound regions alone
+                r
+            }
+
+            ty::ReVar(vid) => {
+                let r = self.infcx
+                    .unwrap()
+                    .borrow_region_constraints()
+                    .opportunistic_resolve_var(self.tcx, vid);
+                let info = CanonicalVarInfo {
+                    kind: CanonicalVarKind::Region,
+                };
+                debug!(
+                    "canonical: region var found with vid {:?}, \
+                     opportunistically resolved to {:?}",
+                    vid, r
+                );
+                let cvar = self.canonical_var(info, Kind::from(r));
+                self.tcx().mk_region(ty::ReCanonical(cvar))
+            }
+
+            ty::ReStatic
+            | ty::ReEarlyBound(..)
+            | ty::ReFree(_)
+            | ty::ReScope(_)
+            | ty::ReSkolemized(..)
+            | ty::ReEmpty
+            | ty::ReErased => {
+                if self.canonicalize_all_free_regions.0 {
+                    let info = CanonicalVarInfo {
+                        kind: CanonicalVarKind::Region,
+                    };
+                    let cvar = self.canonical_var(info, Kind::from(r));
+                    self.tcx().mk_region(ty::ReCanonical(cvar))
+                } else {
+                    r
+                }
+            }
+
+            ty::ReClosureBound(..) | ty::ReCanonical(_) => {
+                bug!("canonical region encountered during canonicalization")
+            }
+        }
+    }
+
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        match t.sty {
+            ty::TyInfer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t),
+
+            ty::TyInfer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t),
+
+            ty::TyInfer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t),
+
+            ty::TyInfer(ty::FreshTy(_))
+            | ty::TyInfer(ty::FreshIntTy(_))
+            | ty::TyInfer(ty::FreshFloatTy(_)) => {
+                bug!("encountered a fresh type during canonicalization")
+            }
+
+            ty::TyInfer(ty::CanonicalTy(_)) => {
+                bug!("encountered a canonical type during canonicalization")
+            }
+
+            // Replace a `()` that "would've fallen back" to `!` with just `()`.
+            ty::TyTuple(ref tys, true) => {
+                assert!(tys.is_empty());
+                self.tcx().mk_nil()
+            }
+
+            ty::TyClosure(..)
+            | ty::TyGenerator(..)
+            | ty::TyGeneratorWitness(..)
+            | ty::TyBool
+            | ty::TyChar
+            | ty::TyInt(..)
+            | ty::TyUint(..)
+            | ty::TyFloat(..)
+            | ty::TyAdt(..)
+            | ty::TyStr
+            | ty::TyError
+            | ty::TyArray(..)
+            | ty::TySlice(..)
+            | ty::TyRawPtr(..)
+            | ty::TyRef(..)
+            | ty::TyFnDef(..)
+            | ty::TyFnPtr(_)
+            | ty::TyDynamic(..)
+            | ty::TyNever
+            | ty::TyTuple(_, false)
+            | ty::TyProjection(..)
+            | ty::TyForeign(..)
+            | ty::TyParam(..)
+            | ty::TyAnon(..) => {
+                if t.flags.intersects(self.needs_canonical_flags) {
+                    t.super_fold_with(self)
+                } else {
+                    t
+                }
+            }
+        }
+    }
+}
+
+impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
+    /// The main `canonicalize` method, shared impl of
+    /// `canonicalize_query` and `canonicalize_response`.
+    fn canonicalize<V>(
+        value: &V,
+        infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>,
+        tcx: TyCtxt<'cx, 'gcx, 'tcx>,
+        canonicalize_all_free_regions: CanonicalizeAllFreeRegions,
+    ) -> (V::Canonicalized, CanonicalVarValues<'tcx>)
+    where
+        V: Canonicalize<'gcx, 'tcx>,
+    {
+        debug_assert!(
+            !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS),
+            "canonicalizing a canonical value: {:?}",
+            value,
+        );
+
+        let needs_canonical_flags = if canonicalize_all_free_regions.0 {
+            TypeFlags::HAS_FREE_REGIONS | TypeFlags::KEEP_IN_LOCAL_TCX
+        } else {
+            TypeFlags::KEEP_IN_LOCAL_TCX
+        };
+
+        let gcx = tcx.global_tcx();
+
+        // Fast path: nothing that needs to be canonicalized.
+        if !value.has_type_flags(needs_canonical_flags) {
+            let out_value = gcx.lift(value).unwrap();
+            let canon_value = V::intern(
+                gcx,
+                Canonical {
+                    variables: Slice::empty(),
+                    value: out_value,
+                },
+            );
+            let values = CanonicalVarValues { var_values: IndexVec::default() };
+            return (canon_value, values);
+        }
+
+        let mut canonicalizer = Canonicalizer {
+            infcx,
+            tcx,
+            canonicalize_all_free_regions,
+            needs_canonical_flags,
+            variables: IndexVec::default(),
+            indices: FxHashMap::default(),
+            var_values: IndexVec::default(),
+        };
+        let out_value = value.fold_with(&mut canonicalizer);
+
+        // Once we have canonicalized `out_value`, it should not
+        // contain anything that ties it to this inference context
+        // anymore, so it should live in the global arena.
+        let out_value = gcx.lift(&out_value).unwrap_or_else(|| {
+            bug!(
+                "failed to lift `{:?}`, canonicalized from `{:?}`",
+                out_value,
+                value
+            )
+        });
+
+        let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables.raw);
+
+        let canonical_value = V::intern(
+            gcx,
+            Canonical {
+                variables: canonical_variables,
+                value: out_value,
+            },
+        );
+        let canonical_var_values = CanonicalVarValues {
+            var_values: canonicalizer.var_values,
+        };
+        (canonical_value, canonical_var_values)
+    }
+
+    /// Creates a canonical variable replacing `kind` from the input,
+    /// or returns an existing variable if `kind` has already been
+    /// seen. `kind` is expected to be an unbound variable (or
+    /// potentially a free region).
+    fn canonical_var(&mut self, info: CanonicalVarInfo, kind: Kind<'tcx>) -> CanonicalVar {
+        let Canonicalizer {
+            indices,
+            variables,
+            var_values,
+            ..
+        } = self;
+
+        indices
+            .entry(kind)
+            .or_insert_with(|| {
+                let cvar1 = variables.push(info);
+                let cvar2 = var_values.push(kind);
+                assert_eq!(cvar1, cvar2);
+                cvar1
+            })
+            .clone()
+    }
+
+    /// Given a type variable `ty_var` of the given kind, first check
+    /// if `ty_var` is bound to anything; if so, canonicalize
+    /// *that*. Otherwise, create a new canonical variable for
+    /// `ty_var`.
+    fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> {
+        let infcx = self.infcx.expect("encountered ty-var without infcx");
+        let bound_to = infcx.shallow_resolve(ty_var);
+        if bound_to != ty_var {
+            self.fold_ty(bound_to)
+        } else {
+            let info = CanonicalVarInfo {
+                kind: CanonicalVarKind::Ty(ty_kind),
+            };
+            let cvar = self.canonical_var(info, Kind::from(ty_var));
+            self.tcx().mk_infer(ty::InferTy::CanonicalTy(cvar))
+        }
+    }
+}
+
+impl<'tcx, V> Canonical<'tcx, V> {
+    /// Instantiate the wrapped value, replacing each canonical value
+    /// with the value given in `var_values`.
+    pub fn substitute(&self, tcx: TyCtxt<'_, '_, 'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V
+    where
+        V: TypeFoldable<'tcx>,
+    {
+        assert_eq!(self.variables.len(), var_values.var_values.len());
+        self.value
+            .fold_with(&mut CanonicalVarValuesSubst { tcx, var_values })
+    }
+}
+
+struct CanonicalVarValuesSubst<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
+    tcx: TyCtxt<'cx, 'gcx, 'tcx>,
+    var_values: &'cx CanonicalVarValues<'tcx>,
+}
+
+impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for CanonicalVarValuesSubst<'cx, 'gcx, 'tcx> {
+    fn tcx(&self) -> TyCtxt<'_, 'gcx, 'tcx> {
+        self.tcx
+    }
+
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        match t.sty {
+            ty::TyInfer(ty::InferTy::CanonicalTy(c)) => {
+                match self.var_values.var_values[c].unpack() {
+                    UnpackedKind::Type(ty) => ty,
+                    r => bug!("{:?} is a type but value is {:?}", c, r),
+                }
+            }
+            _ => t.super_fold_with(self),
+        }
+    }
+
+    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
+        match r {
+            ty::RegionKind::ReCanonical(c) => match self.var_values.var_values[*c].unpack() {
+                UnpackedKind::Lifetime(l) => l,
+                r => bug!("{:?} is a region but value is {:?}", c, r),
+            },
+            _ => r.super_fold_with(self),
+        }
+    }
+}
+
+CloneTypeFoldableAndLiftImpls! {
+    for <'tcx> {
+        ::infer::canonical::Certainty,
+        ::infer::canonical::CanonicalVarInfo,
+        ::infer::canonical::CanonicalVarInfos<'tcx>,
+        ::infer::canonical::CanonicalVarKind,
+    }
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx, C> TypeFoldable<'tcx> for Canonical<'tcx, C> {
+        variables,
+        value,
+    } where C: TypeFoldable<'tcx>
+}
+
+impl<'tcx> CanonicalVarValues<'tcx> {
+    fn iter<'a>(&'a self) -> impl Iterator<Item = Kind<'tcx>> + 'a {
+        self.var_values.iter().cloned()
+    }
+
+    fn len(&self) -> usize {
+        self.var_values.len()
+    }
+}
+
+impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
+    type Item = Kind<'tcx>;
+    type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, Kind<'tcx>>>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.var_values.iter().cloned()
+    }
+}
+
+BraceStructLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for CanonicalVarValues<'a> {
+        type Lifted = CanonicalVarValues<'tcx>;
+        var_values,
+    }
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx> TypeFoldable<'tcx> for CanonicalVarValues<'tcx> {
+        var_values,
+    }
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx> TypeFoldable<'tcx> for QueryRegionConstraints<'tcx> {
+        region_outlives, ty_outlives
+    }
+}
+
+BraceStructLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for QueryRegionConstraints<'a> {
+        type Lifted = QueryRegionConstraints<'tcx>;
+        region_outlives, ty_outlives
+    }
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx, R> TypeFoldable<'tcx> for QueryResult<'tcx, R> {
+        var_values, region_constraints, certainty, value
+    } where R: TypeFoldable<'tcx>,
+}
+
+BraceStructLiftImpl! {
+    impl<'a, 'tcx, R> Lift<'tcx> for QueryResult<'a, R> {
+        type Lifted = QueryResult<'tcx, R::Lifted>;
+        var_values, region_constraints, certainty, value
+    } where R: Lift<'tcx>
+}
diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index 469cb459112..1c581c44464 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -476,6 +476,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                 }
             }
 
+            ty::ReCanonical(..) |
             ty::ReClosureBound(..) => {
                 span_bug!(
                     self.span,
diff --git a/src/librustc/infer/error_reporting/mod.rs b/src/librustc/infer/error_reporting/mod.rs
index 07551c4ebd3..96c23098821 100644
--- a/src/librustc/infer/error_reporting/mod.rs
+++ b/src/librustc/infer/error_reporting/mod.rs
@@ -154,6 +154,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             }
 
             // We shouldn't encounter an error message with ReClosureBound.
+            ty::ReCanonical(..) |
             ty::ReClosureBound(..) => {
                 bug!("encountered unexpected ReClosureBound: {:?}", region,);
             }
diff --git a/src/librustc/infer/freshen.rs b/src/librustc/infer/freshen.rs
index ee0921f4b07..6074bfd083d 100644
--- a/src/librustc/infer/freshen.rs
+++ b/src/librustc/infer/freshen.rs
@@ -114,9 +114,10 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
                 self.tcx().types.re_erased
             }
 
+            ty::ReCanonical(..) |
             ty::ReClosureBound(..) => {
                 bug!(
-                    "encountered unexpected ReClosureBound: {:?}",
+                    "encountered unexpected region: {:?}",
                     r,
                 );
             }
@@ -170,6 +171,9 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
                 t
             }
 
+            ty::TyInfer(ty::CanonicalTy(..)) =>
+                bug!("encountered canonical ty during freshening"),
+
             ty::TyGenerator(..) |
             ty::TyBool |
             ty::TyChar |
diff --git a/src/librustc/infer/lexical_region_resolve/mod.rs b/src/librustc/infer/lexical_region_resolve/mod.rs
index 3ac4ec5bee4..00b2ac7449f 100644
--- a/src/librustc/infer/lexical_region_resolve/mod.rs
+++ b/src/librustc/infer/lexical_region_resolve/mod.rs
@@ -258,6 +258,8 @@ impl<'cx, 'gcx, 'tcx> LexicalResolver<'cx, 'gcx, 'tcx> {
     fn lub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> Region<'tcx> {
         let tcx = self.region_rels.tcx;
         match (a, b) {
+            (&ty::ReCanonical(..), _) |
+            (_, &ty::ReCanonical(..)) |
             (&ty::ReClosureBound(..), _) |
             (_, &ty::ReClosureBound(..)) |
             (&ReLateBound(..), _) |
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 5f0c2d1e76b..5127807bf70 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -50,6 +50,7 @@ use self::unify_key::ToType;
 
 pub mod anon_types;
 pub mod at;
+pub mod canonical;
 mod combine;
 mod equate;
 pub mod error_reporting;
@@ -473,6 +474,12 @@ impl<'tcx, T> InferOk<'tcx, T> {
     }
 }
 
+impl<'tcx> InferOk<'tcx, ()> {
+    pub fn into_obligations(self) -> PredicateObligations<'tcx> {
+        self.obligations
+    }
+}
+
 #[must_use = "once you start a snapshot, you should always consume it"]
 pub struct CombinedSnapshot<'a, 'tcx:'a> {
     projection_cache_snapshot: traits::ProjectionCacheSnapshot,
@@ -1644,4 +1651,3 @@ impl<'tcx> fmt::Debug for RegionObligation<'tcx> {
                self.sup_type)
     }
 }
-
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 2cf17603629..77b3a87c0ed 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -57,9 +57,9 @@
 #![feature(inclusive_range)]
 #![feature(inclusive_range_syntax)]
 #![cfg_attr(windows, feature(libc))]
+#![feature(match_default_bindings)]
 #![feature(macro_lifetime_matcher)]
 #![feature(macro_vis_matcher)]
-#![feature(match_default_bindings)]
 #![feature(never_type)]
 #![feature(non_exhaustive)]
 #![feature(nonzero)]
diff --git a/src/librustc/macros.rs b/src/librustc/macros.rs
index 6013e3aef81..d8a723e184d 100644
--- a/src/librustc/macros.rs
+++ b/src/librustc/macros.rs
@@ -119,6 +119,25 @@ macro_rules! impl_stable_hash_for {
             }
         }
     };
+
+    (impl<$tcx:lifetime $(, $T:ident)*> for struct $struct_name:path {
+        $($field:ident),* $(,)*
+    }) => {
+        impl<'a, $tcx, $($T,)*> ::rustc_data_structures::stable_hasher::HashStable<$crate::ich::StableHashingContext<'a>> for $struct_name
+            where $($T: ::rustc_data_structures::stable_hasher::HashStable<$crate::ich::StableHashingContext<'a>>),*
+        {
+            #[inline]
+            fn hash_stable<W: ::rustc_data_structures::stable_hasher::StableHasherResult>(&self,
+                                                  __ctx: &mut $crate::ich::StableHashingContext<'a>,
+                                                  __hasher: &mut ::rustc_data_structures::stable_hasher::StableHasher<W>) {
+                let $struct_name {
+                    $(ref $field),*
+                } = *self;
+
+                $( $field.hash_stable(__ctx, __hasher));*
+            }
+        }
+    };
 }
 
 #[macro_export]
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index 01e1037b622..7b4211e487a 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -173,6 +173,8 @@ pub struct PerfStats {
     pub symbol_hash_time: Cell<Duration>,
     /// The accumulated time spent decoding def path tables from metadata
     pub decode_def_path_tables_time: Cell<Duration>,
+    /// Total number of values canonicalized queries constructed.
+    pub queries_canonicalized: Cell<usize>,
 }
 
 /// Enum to support dispatch of one-time diagnostics (in Session.diag_once)
@@ -858,6 +860,8 @@ impl Session {
             "Total time spent decoding DefPath tables:      {}",
             duration_to_secs_str(self.perf_stats.decode_def_path_tables_time.get())
         );
+        println!("Total queries canonicalized:                   {}",
+                 self.perf_stats.queries_canonicalized.get());
     }
 
     /// We want to know if we're allowed to do an optimization for crate foo from -z fuel=foo=n.
@@ -1144,6 +1148,7 @@ pub fn build_session_(
             incr_comp_bytes_hashed: Cell::new(0),
             symbol_hash_time: Cell::new(Duration::from_secs(0)),
             decode_def_path_tables_time: Cell::new(Duration::from_secs(0)),
+            queries_canonicalized: Cell::new(0),
         },
         code_stats: RefCell::new(CodeStats::new()),
         optimization_fuel_crate,
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 728702ef61f..f2f54dcedfd 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -2083,9 +2083,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             ty::TyProjection(_) | ty::TyParam(_) | ty::TyAnon(..) => None,
             ty::TyInfer(ty::TyVar(_)) => Ambiguous,
 
-            ty::TyInfer(ty::FreshTy(_))
-            | ty::TyInfer(ty::FreshIntTy(_))
-            | ty::TyInfer(ty::FreshFloatTy(_)) => {
+            ty::TyInfer(ty::CanonicalTy(_)) |
+            ty::TyInfer(ty::FreshTy(_)) |
+            ty::TyInfer(ty::FreshIntTy(_)) |
+            ty::TyInfer(ty::FreshFloatTy(_)) => {
                 bug!("asked to assemble builtin bounds of unexpected type: {:?}",
                      self_ty);
             }
@@ -2154,9 +2155,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 Ambiguous
             }
 
-            ty::TyInfer(ty::FreshTy(_))
-            | ty::TyInfer(ty::FreshIntTy(_))
-            | ty::TyInfer(ty::FreshFloatTy(_)) => {
+            ty::TyInfer(ty::CanonicalTy(_)) |
+            ty::TyInfer(ty::FreshTy(_)) |
+            ty::TyInfer(ty::FreshIntTy(_)) |
+            ty::TyInfer(ty::FreshFloatTy(_)) => {
                 bug!("asked to assemble builtin bounds of unexpected type: {:?}",
                      self_ty);
             }
@@ -2195,6 +2197,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             ty::TyParam(..) |
             ty::TyForeign(..) |
             ty::TyProjection(..) |
+            ty::TyInfer(ty::CanonicalTy(_)) |
             ty::TyInfer(ty::TyVar(_)) |
             ty::TyInfer(ty::FreshTy(_)) |
             ty::TyInfer(ty::FreshIntTy(_)) |
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index e7d6bdd3383..24d3b37f804 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -23,6 +23,7 @@ use hir::map as hir_map;
 use hir::map::DefPathHash;
 use lint::{self, Lint};
 use ich::{StableHashingContext, NodeIdHashingMode};
+use infer::canonical::{CanonicalVarInfo, CanonicalVarInfos};
 use infer::outlives::free_region_map::FreeRegionMap;
 use middle::const_val::ConstVal;
 use middle::cstore::{CrateStore, LinkMeta};
@@ -131,6 +132,7 @@ pub struct CtxtInterners<'tcx> {
     type_: RefCell<FxHashSet<Interned<'tcx, TyS<'tcx>>>>,
     type_list: RefCell<FxHashSet<Interned<'tcx, Slice<Ty<'tcx>>>>>,
     substs: RefCell<FxHashSet<Interned<'tcx, Substs<'tcx>>>>,
+    canonical_var_infos: RefCell<FxHashSet<Interned<'tcx, Slice<CanonicalVarInfo>>>>,
     region: RefCell<FxHashSet<Interned<'tcx, RegionKind>>>,
     existential_predicates: RefCell<FxHashSet<Interned<'tcx, Slice<ExistentialPredicate<'tcx>>>>>,
     predicates: RefCell<FxHashSet<Interned<'tcx, Slice<Predicate<'tcx>>>>>,
@@ -146,6 +148,7 @@ impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
             substs: RefCell::new(FxHashSet()),
             region: RefCell::new(FxHashSet()),
             existential_predicates: RefCell::new(FxHashSet()),
+            canonical_var_infos: RefCell::new(FxHashSet()),
             predicates: RefCell::new(FxHashSet()),
             const_: RefCell::new(FxHashSet()),
         }
@@ -1838,6 +1841,12 @@ impl<'tcx: 'lcx, 'lcx> Borrow<[Ty<'lcx>]> for Interned<'tcx, Slice<Ty<'tcx>>> {
     }
 }
 
+impl<'tcx: 'lcx, 'lcx> Borrow<[CanonicalVarInfo]> for Interned<'tcx, Slice<CanonicalVarInfo>> {
+    fn borrow<'a>(&'a self) -> &'a [CanonicalVarInfo] {
+        &self.0[..]
+    }
+}
+
 impl<'tcx: 'lcx, 'lcx> Borrow<[Kind<'lcx>]> for Interned<'tcx, Substs<'tcx>> {
     fn borrow<'a>(&'a self) -> &'a [Kind<'lcx>] {
         &self.0[..]
@@ -1970,6 +1979,22 @@ slice_interners!(
     substs: _intern_substs(Kind)
 );
 
+// This isn't a perfect fit: CanonicalVarInfo slices are always
+// allocated in the global arena, so this `intern_method!` macro is
+// overly general.  But we just return false for the code that checks
+// whether they belong in the thread-local arena, so no harm done, and
+// seems better than open-coding the rest.
+intern_method! {
+    'tcx,
+    canonical_var_infos: _intern_canonical_var_infos(
+        &[CanonicalVarInfo],
+        alloc_slice,
+        Deref::deref,
+        |xs: &[CanonicalVarInfo]| -> &Slice<CanonicalVarInfo> { unsafe { mem::transmute(xs) } },
+        |_xs: &[CanonicalVarInfo]| -> bool { false }
+    ) -> Slice<CanonicalVarInfo>
+}
+
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     /// Given a `fn` type, returns an equivalent `unsafe fn` type;
     /// that is, a `fn` type that is equivalent in every way for being
@@ -2257,6 +2282,14 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
+    pub fn intern_canonical_var_infos(self, ts: &[CanonicalVarInfo]) -> CanonicalVarInfos<'gcx> {
+        if ts.len() == 0 {
+            Slice::empty()
+        } else {
+            self.global_tcx()._intern_canonical_var_infos(ts)
+        }
+    }
+
     pub fn mk_fn_sig<I>(self,
                         inputs: I,
                         output: I::Item,
diff --git a/src/librustc/ty/error.rs b/src/librustc/ty/error.rs
index dcb70a8f86a..8a0253ed2f1 100644
--- a/src/librustc/ty/error.rs
+++ b/src/librustc/ty/error.rs
@@ -220,6 +220,7 @@ impl<'a, 'gcx, 'lcx, 'tcx> ty::TyS<'tcx> {
             ty::TyInfer(ty::TyVar(_)) => "inferred type".to_string(),
             ty::TyInfer(ty::IntVar(_)) => "integral variable".to_string(),
             ty::TyInfer(ty::FloatVar(_)) => "floating-point variable".to_string(),
+            ty::TyInfer(ty::CanonicalTy(_)) |
             ty::TyInfer(ty::FreshTy(_)) => "skolemized type".to_string(),
             ty::TyInfer(ty::FreshIntTy(_)) => "skolemized integral type".to_string(),
             ty::TyInfer(ty::FreshFloatTy(_)) => "skolemized floating-point type".to_string(),
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index f067789771c..cae64fd4c95 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -112,8 +112,16 @@ impl FlagComputation {
                 match infer {
                     ty::FreshTy(_) |
                     ty::FreshIntTy(_) |
-                    ty::FreshFloatTy(_) => {}
-                    _ => self.add_flags(TypeFlags::KEEP_IN_LOCAL_TCX)
+                    ty::FreshFloatTy(_) |
+                    ty::CanonicalTy(_) => {
+                        self.add_flags(TypeFlags::HAS_CANONICAL_VARS);
+                    }
+
+                    ty::TyVar(_) |
+                    ty::IntVar(_) |
+                    ty::FloatVar(_) => {
+                        self.add_flags(TypeFlags::KEEP_IN_LOCAL_TCX)
+                    }
                 }
             }
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index e3405e0c3b3..93d1585cdc8 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -60,7 +60,7 @@ use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult,
 
 use hir;
 
-pub use self::sty::{Binder, DebruijnIndex};
+pub use self::sty::{Binder, CanonicalVar, DebruijnIndex};
 pub use self::sty::{FnSig, GenSig, PolyFnSig, PolyGenSig};
 pub use self::sty::{InferTy, ParamTy, ProjectionTy, ExistentialPredicate};
 pub use self::sty::{ClosureSubsts, GeneratorInterior, TypeAndMut};
@@ -452,6 +452,10 @@ bitflags! {
         // Currently we can't normalize projections w/ bound regions.
         const HAS_NORMALIZABLE_PROJECTION = 1 << 12;
 
+        // Set if this includes a "canonical" type or region var --
+        // ought to be true only for the results of canonicalization.
+        const HAS_CANONICAL_VARS = 1 << 13;
+
         const NEEDS_SUBST        = TypeFlags::HAS_PARAMS.bits |
                                    TypeFlags::HAS_SELF.bits |
                                    TypeFlags::HAS_RE_EARLY_BOUND.bits;
@@ -470,7 +474,8 @@ bitflags! {
                                   TypeFlags::HAS_PROJECTION.bits |
                                   TypeFlags::HAS_TY_CLOSURE.bits |
                                   TypeFlags::HAS_LOCAL_NAMES.bits |
-                                  TypeFlags::KEEP_IN_LOCAL_TCX.bits;
+                                  TypeFlags::KEEP_IN_LOCAL_TCX.bits |
+                                  TypeFlags::HAS_CANONICAL_VARS.bits;
     }
 }
 
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 7bcc816b5f0..109422564c8 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -1047,6 +1047,9 @@ pub enum RegionKind {
     /// `ClosureRegionRequirements` that are produced by MIR borrowck.
     /// See `ClosureRegionRequirements` for more details.
     ReClosureBound(RegionVid),
+
+    /// Canonicalized region, used only when preparing a trait query.
+    ReCanonical(CanonicalVar),
 }
 
 impl<'tcx> serialize::UseSpecializedDecodable for Region<'tcx> {}
@@ -1091,8 +1094,13 @@ pub enum InferTy {
     FreshTy(u32),
     FreshIntTy(u32),
     FreshFloatTy(u32),
+
+    /// Canonicalized type variable, used only when preparing a trait query.
+    CanonicalTy(CanonicalVar),
 }
 
+newtype_index!(CanonicalVar);
+
 /// A `ProjectionPredicate` for an `ExistentialTraitRef`.
 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
 pub struct ExistentialProjection<'tcx> {
@@ -1213,6 +1221,10 @@ impl RegionKind {
             }
             ty::ReErased => {
             }
+            ty::ReCanonical(..) => {
+                flags = flags | TypeFlags::HAS_FREE_REGIONS;
+                flags = flags | TypeFlags::HAS_CANONICAL_VARS;
+            }
             ty::ReClosureBound(..) => {
                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
             }
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index e70c72335aa..a301049fe1c 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -40,6 +40,7 @@ const TAG_MASK: usize = 0b11;
 const TYPE_TAG: usize = 0b00;
 const REGION_TAG: usize = 0b01;
 
+#[derive(Debug)]
 pub enum UnpackedKind<'tcx> {
     Lifetime(ty::Region<'tcx>),
     Type(Ty<'tcx>),
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index a7ee8579fb9..e8ce49d39d2 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -834,6 +834,9 @@ impl<'a, 'gcx, 'tcx, W> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx, W>
             ty::ReEmpty => {
                 // No variant fields to hash for these ...
             }
+            ty::ReCanonical(c) => {
+                self.hash(c);
+            }
             ty::ReLateBound(db, ty::BrAnon(i)) => {
                 self.hash(db.depth);
                 self.hash(i);
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 5e2792ee641..efa53c775ae 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -721,6 +721,9 @@ define_print! {
                 ty::ReEarlyBound(ref data) => {
                     write!(f, "{}", data.name)
                 }
+                ty::ReCanonical(_) => {
+                    write!(f, "'_")
+                }
                 ty::ReLateBound(_, br) |
                 ty::ReFree(ty::FreeRegion { bound_region: br, .. }) |
                 ty::ReSkolemized(_, br) => {
@@ -785,6 +788,10 @@ define_print! {
                     write!(f, "{:?}", vid)
                 }
 
+                ty::ReCanonical(c) => {
+                    write!(f, "'?{}", c.index())
+                }
+
                 ty::ReSkolemized(id, ref bound_region) => {
                     write!(f, "ReSkolemized({:?}, {:?})", id, bound_region)
                 }
@@ -888,6 +895,7 @@ define_print! {
                     ty::TyVar(_) => write!(f, "_"),
                     ty::IntVar(_) => write!(f, "{}", "{integer}"),
                     ty::FloatVar(_) => write!(f, "{}", "{float}"),
+                    ty::CanonicalTy(_) => write!(f, "_"),
                     ty::FreshTy(v) => write!(f, "FreshTy({})", v),
                     ty::FreshIntTy(v) => write!(f, "FreshIntTy({})", v),
                     ty::FreshFloatTy(v) => write!(f, "FreshFloatTy({})", v)
@@ -899,6 +907,7 @@ define_print! {
                 ty::TyVar(ref v) => write!(f, "{:?}", v),
                 ty::IntVar(ref v) => write!(f, "{:?}", v),
                 ty::FloatVar(ref v) => write!(f, "{:?}", v),
+                ty::CanonicalTy(v) => write!(f, "?{:?}", v.index()),
                 ty::FreshTy(v) => write!(f, "FreshTy({:?})", v),
                 ty::FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v),
                 ty::FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v)
diff --git a/src/librustc_borrowck/borrowck/check_loans.rs b/src/librustc_borrowck/borrowck/check_loans.rs
index 9888b2fffc7..a01b3cbf47b 100644
--- a/src/librustc_borrowck/borrowck/check_loans.rs
+++ b/src/librustc_borrowck/borrowck/check_loans.rs
@@ -427,6 +427,7 @@ impl<'a, 'tcx> CheckLoanCtxt<'a, 'tcx> {
 
             // These cannot exist in borrowck
             RegionKind::ReVar(..) |
+            RegionKind::ReCanonical(..) |
             RegionKind::ReSkolemized(..) |
             RegionKind::ReClosureBound(..) |
             RegionKind::ReErased => span_bug!(borrow_span,
diff --git a/src/librustc_borrowck/borrowck/gather_loans/mod.rs b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
index 5cbe2822e5c..49234f4ed7f 100644
--- a/src/librustc_borrowck/borrowck/gather_loans/mod.rs
+++ b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
@@ -366,6 +366,7 @@ impl<'a, 'tcx> GatherLoanCtxt<'a, 'tcx> {
 
                     ty::ReStatic => self.item_ub,
 
+                    ty::ReCanonical(_) |
                     ty::ReEmpty |
                     ty::ReClosureBound(..) |
                     ty::ReLateBound(..) |
diff --git a/src/librustc_const_eval/lib.rs b/src/librustc_const_eval/lib.rs
index 9d636b48bd0..459aa9ea488 100644
--- a/src/librustc_const_eval/lib.rs
+++ b/src/librustc_const_eval/lib.rs
@@ -23,6 +23,7 @@
 #![feature(slice_patterns)]
 #![feature(box_patterns)]
 #![feature(box_syntax)]
+#![feature(macro_lifetime_matcher)]
 #![feature(i128_type)]
 #![feature(from_ref)]
 
diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index 11c2bd73687..a5b1a7e57ab 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -330,7 +330,7 @@ macro_rules! newtype_index {
     );
 }
 
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone, PartialEq, Eq, Hash)]
 pub struct IndexVec<I: Idx, T> {
     pub raw: Vec<T>,
     _marker: PhantomData<fn(&I)>
diff --git a/src/librustc_metadata/lib.rs b/src/librustc_metadata/lib.rs
index da0da622d52..f77c22bd895 100644
--- a/src/librustc_metadata/lib.rs
+++ b/src/librustc_metadata/lib.rs
@@ -18,7 +18,9 @@
 #![feature(fs_read_write)]
 #![feature(i128_type)]
 #![feature(libc)]
+#![feature(macro_lifetime_matcher)]
 #![feature(proc_macro_internals)]
+#![feature(macro_lifetime_matcher)]
 #![feature(quote)]
 #![feature(rustc_diagnostic_macros)]
 #![feature(specialization)]
diff --git a/src/librustc_mir/borrow_check/error_reporting.rs b/src/librustc_mir/borrow_check/error_reporting.rs
index 7ab52e98a0e..84ba1367450 100644
--- a/src/librustc_mir/borrow_check/error_reporting.rs
+++ b/src/librustc_mir/borrow_check/error_reporting.rs
@@ -457,6 +457,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
             (RegionKind::ReLateBound(_, _), _)
             | (RegionKind::ReSkolemized(_, _), _)
             | (RegionKind::ReClosureBound(_), _)
+            | (RegionKind::ReCanonical(_), _)
             | (RegionKind::ReErased, _) => {
                 span_bug!(drop_span, "region does not make sense in this context");
             }
diff --git a/src/librustc_save_analysis/lib.rs b/src/librustc_save_analysis/lib.rs
index 490dc4e5ac4..95374775651 100644
--- a/src/librustc_save_analysis/lib.rs
+++ b/src/librustc_save_analysis/lib.rs
@@ -13,6 +13,7 @@
        html_root_url = "https://doc.rust-lang.org/nightly/")]
 #![deny(warnings)]
 #![feature(custom_attribute)]
+#![feature(macro_lifetime_matcher)]
 #![allow(unused_attributes)]
 
 #[macro_use]
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index 44ac7a10e82..2a4e92034de 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -423,6 +423,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                 // way early-bound regions do, so we skip them here.
             }
 
+            ty::ReCanonical(_) |
             ty::ReFree(..) |
             ty::ReClosureBound(..) |
             ty::ReScope(..) |
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 5d4addce2c4..ff281a53ab7 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -1490,6 +1490,7 @@ impl Clean<Option<Lifetime>> for ty::RegionKind {
             ty::ReSkolemized(..) |
             ty::ReEmpty |
             ty::ReClosureBound(_) |
+            ty::ReCanonical(_) |
             ty::ReErased => None
         }
     }