break canonicalizer into submodules to make it easier to comprehend

4 files changed, 689 insertions, 594 deletions

diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
new file mode 100644
index 00000000000..677063fcf88
--- /dev/null
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -0,0 +1,347 @@
+// 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.
+
+//! This module contains the "canonicalizer" itself.
+//!
+//! For an overview of what canonicaliation is and how it fits into
+//! rustc, check out the [chapter in the rustc guide][c].
+//!
+//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
+
+use infer::canonical::{
+    Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, CanonicalVarValues,
+    Canonicalize,
+};
+use infer::InferCtxt;
+use std::sync::atomic::Ordering;
+use ty::fold::{TypeFoldable, TypeFolder};
+use ty::subst::Kind;
+use ty::{self, CanonicalVar, Slice, Ty, TyCtxt, TypeFlags};
+
+use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::indexed_vec::IndexVec;
+
+impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
+    /// 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
+    ///
+    /// ```text
+    /// T: Trait<'?0>
+    /// ```
+    ///
+    /// with a mapping M that maps `'?0` to `'static`.
+    ///
+    /// To get a good understanding of what is happening here, check
+    /// out the [chapter in the rustc guide][c].
+    ///
+    /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query
+    pub fn canonicalize_query<V>(&self, value: &V) -> (V::Canonicalized, CanonicalVarValues<'tcx>)
+    where
+        V: Canonicalize<'gcx, 'tcx>,
+    {
+        self.tcx
+            .sess
+            .perf_stats
+            .queries_canonicalized
+            .fetch_add(1, Ordering::Relaxed);
+
+        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
+    ///
+    /// ```text
+    /// 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.
+    ///
+    /// To get a good understanding of what is happening here, check
+    /// out the [chapter in the rustc guide][c].
+    ///
+    /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query-result
+    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),
+        )
+    }
+}
+
+/// 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(pub 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, r.into());
+                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, r.into());
+                    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")
+            }
+
+            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(..)
+            | 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, ty_var.into());
+            self.tcx().mk_infer(ty::InferTy::CanonicalTy(cvar))
+        }
+    }
+}
diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs
index ef11cc0f493..037fc637ec9 100644
--- a/src/librustc/infer/canonical/mod.rs
+++ b/src/librustc/infer/canonical/mod.rs
@@ -31,20 +31,22 @@
 //!
 //! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
 
-use infer::{InferCtxt, InferOk, InferResult, RegionVariableOrigin, TypeVariableOrigin};
-use rustc_data_structures::indexed_vec::Idx;
+use infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin};
 use serialize::UseSpecializedDecodable;
 use std::fmt::Debug;
 use std::ops::Index;
-use std::sync::atomic::Ordering;
 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 ty::{self, CanonicalVar, Lift, Region, Slice, TyCtxt};
+use ty::subst::Kind;
+use ty::fold::TypeFoldable;
 
 use rustc_data_structures::indexed_vec::IndexVec;
-use rustc_data_structures::fx::FxHashMap;
+
+mod canonicalizer;
+
+mod query_result;
+
+mod substitute;
 
 /// A "canonicalized" type `V` is one where all free inference
 /// variables have been rewriten to "canonical vars". These are
@@ -66,11 +68,8 @@ impl<'gcx> UseSpecializedDecodable for CanonicalVarInfos<'gcx> { }
 ///
 /// 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.
+/// variables. You will need to supply it later to instantiate the
+/// canonicalized query response.
 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 pub struct CanonicalVarValues<'tcx> {
     pub var_values: IndexVec<CanonicalVar, Kind<'tcx>>,
@@ -223,7 +222,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
     /// 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(
+    fn fresh_inference_vars_for_canonical_vars(
         &self,
         span: Span,
         variables: &Slice<CanonicalVarInfo>,
@@ -238,7 +237,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
 
     /// Given the "info" about a canonical variable, creates a fresh
     /// inference variable with the same characteristics.
-    pub fn fresh_inference_var_for_canonical_var(
+    fn fresh_inference_var_for_canonical_var(
         &self,
         span: Span,
         cv_info: CanonicalVarInfo,
@@ -264,585 +263,6 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
             }
         }
     }
-
-    /// 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.)
-    ///
-    /// To get a good understanding of what is happening here, check
-    /// out the [chapter in the rustc guide][c].
-    ///
-    /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#processing-the-canonicalized-query-result
-    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(),
-        };
-
-        // 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 substituted_values = |index: CanonicalVar| -> Kind<'tcx> {
-            query_result.substitute_projected(self.tcx, result_subst, |v| &v.var_values[index])
-        };
-        let mut obligations =
-            self.unify_canonical_vars(cause, param_env, original_values, substituted_values)?
-                .into_obligations();
-
-        obligations.extend(self.query_region_constraints_into_obligations(
-            cause,
-            param_env,
-            &query_result.value.region_constraints,
-            result_subst,
-        ));
-
-        let user_result: R =
-            query_result.substitute_projected(self.tcx, result_subst, |q_r| &q_r.value);
-
-        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>(
-        &'a self,
-        cause: &'a ObligationCause<'tcx>,
-        param_env: ty::ParamEnv<'tcx>,
-        unsubstituted_region_constraints: &'a [QueryRegionConstraint<'tcx>],
-        result_subst: &'a CanonicalVarValues<'tcx>,
-    ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a {
-        Box::new(unsubstituted_region_constraints.iter().map(move |constraint| {
-            let ty::OutlivesPredicate(k1, r2) = constraint.skip_binder(); // restored below
-            let k1 = substitute_value(self.tcx, result_subst, k1);
-            let r2 = substitute_value(self.tcx, result_subst, r2);
-            match k1.unpack() {
-                UnpackedKind::Lifetime(r1) =>
-                    Obligation::new(
-                        cause.clone(),
-                        param_env,
-                        ty::Predicate::RegionOutlives(
-                            ty::Binder::dummy(ty::OutlivesPredicate(r1, r2))),
-                    ),
-
-                UnpackedKind::Type(t1) =>
-                    Obligation::new(
-                        cause.clone(),
-                        param_env,
-                        ty::Predicate::TypeOutlives(
-                            ty::Binder::dummy(ty::OutlivesPredicate(t1, r2))),
-                    ),
-            }
-        })) as Box<dyn Iterator<Item = _>>
-    }
-
-    /// Given two sets of values for the same set of canonical variables, unify them.
-    /// The second set is produced lazilly by supplying indices from the first set.
-    fn unify_canonical_vars(
-        &self,
-        cause: &ObligationCause<'tcx>,
-        param_env: ty::ParamEnv<'tcx>,
-        variables1: &CanonicalVarValues<'tcx>,
-        variables2: impl Fn(CanonicalVar) -> Kind<'tcx>,
-    ) -> InferResult<'tcx, ()> {
-        self.commit_if_ok(|_| {
-            let mut obligations = vec![];
-            for (index, value1) in variables1.var_values.iter_enumerated() {
-                let value2 = variables2(index);
-
-                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
-    ///
-    /// ```text
-    /// T: Trait<'?0>
-    /// ```
-    ///
-    /// with a mapping M that maps `'?0` to `'static`.
-    ///
-    /// To get a good understanding of what is happening here, check
-    /// out the [chapter in the rustc guide][c].
-    ///
-    /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query
-    pub fn canonicalize_query<V>(&self, value: &V) -> (V::Canonicalized, CanonicalVarValues<'tcx>)
-    where
-        V: Canonicalize<'gcx, 'tcx>,
-    {
-        self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed);
-
-        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
-    ///
-    /// ```text
-    /// 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.
-    ///
-    /// To get a good understanding of what is happening here, check
-    /// out the [chapter in the rustc guide][c].
-    ///
-    /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query-result
-    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),
-        )
-    }
-}
-
-/// 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, r.into());
-                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, r.into());
-                    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")
-            }
-
-            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(..)
-            | 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, ty_var.into());
-            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`.
-    fn substitute(&self, tcx: TyCtxt<'_, '_, 'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V
-    where
-        V: TypeFoldable<'tcx>,
-    {
-        self.substitute_projected(tcx, var_values, |value| value)
-    }
-
-    /// Invoke `projection_fn` with `self.value` to get a value V that
-    /// is expressed in terms of the same canonical variables bound in
-    /// `self`. Apply the substitution `var_values` to this value V,
-    /// replacing each of the canonical variables.
-    fn substitute_projected<T>(
-        &self,
-        tcx: TyCtxt<'_, '_, 'tcx>,
-        var_values: &CanonicalVarValues<'tcx>,
-        projection_fn: impl FnOnce(&V) -> &T,
-    ) -> T
-    where
-        T: TypeFoldable<'tcx>,
-    {
-        assert_eq!(self.variables.len(), var_values.var_values.len());
-        let value = projection_fn(&self.value);
-        substitute_value(tcx, var_values, value)
-    }
-}
-
-/// Substitute the values from `var_values` into `value`. `var_values`
-/// must be values for the set of cnaonical variables that appear in
-/// `value`.
-fn substitute_value<'a, 'tcx, T>(
-    tcx: TyCtxt<'_, '_, 'tcx>,
-    var_values: &CanonicalVarValues<'tcx>,
-    value: &'a T,
-) -> T
-where
-    T: TypeFoldable<'tcx>,
-{
-    if var_values.var_values.is_empty() {
-        debug_assert!(!value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS));
-        value.clone()
-    } else if !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) {
-        value.clone()
-    } else {
-        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),
-                }
-            }
-            _ => {
-                if !t.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) {
-                    t
-                } else {
-                    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! {
diff --git a/src/librustc/infer/canonical/query_result.rs b/src/librustc/infer/canonical/query_result.rs
new file mode 100644
index 00000000000..b1eed05c2a2
--- /dev/null
+++ b/src/librustc/infer/canonical/query_result.rs
@@ -0,0 +1,215 @@
+// 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.
+
+//! This module contains the code to instantiate a "query result", and
+//! in particular to extract out the resulting region obligations and
+//! encode them therein.
+//!
+//! For an overview of what canonicaliation is and how it fits into
+//! rustc, check out the [chapter in the rustc guide][c].
+//!
+//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
+
+use infer::canonical::{Canonical, CanonicalVarValues, QueryRegionConstraint, QueryResult};
+use infer::canonical::substitute::substitute_value;
+use infer::{InferCtxt, InferOk, InferResult};
+use rustc_data_structures::indexed_vec::Idx;
+use std::fmt::Debug;
+use traits::{Obligation, ObligationCause, PredicateObligation};
+use ty::fold::TypeFoldable;
+use ty::subst::{Kind, UnpackedKind};
+use ty::{self, CanonicalVar};
+
+use rustc_data_structures::indexed_vec::IndexVec;
+
+impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
+    /// 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.)
+    ///
+    /// To get a good understanding of what is happening here, check
+    /// out the [chapter in the rustc guide][c].
+    ///
+    /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#processing-the-canonicalized-query-result
+    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(),
+        };
+
+        // 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 substituted_values = |index: CanonicalVar| -> Kind<'tcx> {
+            query_result.substitute_projected(self.tcx, result_subst, |v| &v.var_values[index])
+        };
+        let mut obligations = self
+            .unify_canonical_vars(cause, param_env, original_values, substituted_values)?
+            .into_obligations();
+
+        obligations.extend(self.query_region_constraints_into_obligations(
+            cause,
+            param_env,
+            &query_result.value.region_constraints,
+            result_subst,
+        ));
+
+        let user_result: R =
+            query_result.substitute_projected(self.tcx, result_subst, |q_r| &q_r.value);
+
+        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>(
+        &'a self,
+        cause: &'a ObligationCause<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        unsubstituted_region_constraints: &'a [QueryRegionConstraint<'tcx>],
+        result_subst: &'a CanonicalVarValues<'tcx>,
+    ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a {
+        Box::new(
+            unsubstituted_region_constraints
+                .iter()
+                .map(move |constraint| {
+                    let ty::OutlivesPredicate(k1, r2) = constraint.skip_binder(); // restored below
+                    let k1 = substitute_value(self.tcx, result_subst, k1);
+                    let r2 = substitute_value(self.tcx, result_subst, r2);
+                    match k1.unpack() {
+                        UnpackedKind::Lifetime(r1) => Obligation::new(
+                            cause.clone(),
+                            param_env,
+                            ty::Predicate::RegionOutlives(ty::Binder::dummy(
+                                ty::OutlivesPredicate(r1, r2),
+                            )),
+                        ),
+
+                        UnpackedKind::Type(t1) => Obligation::new(
+                            cause.clone(),
+                            param_env,
+                            ty::Predicate::TypeOutlives(ty::Binder::dummy(ty::OutlivesPredicate(
+                                t1, r2,
+                            ))),
+                        ),
+                    }
+                }),
+        ) as Box<dyn Iterator<Item = _>>
+    }
+
+    /// Given two sets of values for the same set of canonical variables, unify them.
+    /// The second set is produced lazilly by supplying indices from the first set.
+    fn unify_canonical_vars(
+        &self,
+        cause: &ObligationCause<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        variables1: &CanonicalVarValues<'tcx>,
+        variables2: impl Fn(CanonicalVar) -> Kind<'tcx>,
+    ) -> InferResult<'tcx, ()> {
+        self.commit_if_ok(|_| {
+            let mut obligations = vec![];
+            for (index, value1) in variables1.var_values.iter_enumerated() {
+                let value2 = variables2(index);
+
+                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,
+            })
+        })
+    }
+}
diff --git a/src/librustc/infer/canonical/substitute.rs b/src/librustc/infer/canonical/substitute.rs
new file mode 100644
index 00000000000..5bc1ae689a5
--- /dev/null
+++ b/src/librustc/infer/canonical/substitute.rs
@@ -0,0 +1,113 @@
+// 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.
+
+//! This module contains code to substitute new values into a
+//! `Canonical<'tcx, T>`.
+//!
+//! For an overview of what canonicaliation is and how it fits into
+//! rustc, check out the [chapter in the rustc guide][c].
+//!
+//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
+
+use infer::canonical::{Canonical, CanonicalVarValues};
+use ty::fold::{TypeFoldable, TypeFolder};
+use ty::subst::UnpackedKind;
+use ty::{self, Ty, TyCtxt, TypeFlags};
+
+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>,
+    {
+        self.substitute_projected(tcx, var_values, |value| value)
+    }
+
+    /// Allows one to apply a substitute to some subset of
+    /// `self.value`. Invoke `projection_fn` with `self.value` to get
+    /// a value V that is expressed in terms of the same canonical
+    /// variables bound in `self` (usually this extracts from subset
+    /// of `self`). Apply the substitution `var_values` to this value
+    /// V, replacing each of the canonical variables.
+    pub fn substitute_projected<T>(
+        &self,
+        tcx: TyCtxt<'_, '_, 'tcx>,
+        var_values: &CanonicalVarValues<'tcx>,
+        projection_fn: impl FnOnce(&V) -> &T,
+    ) -> T
+    where
+        T: TypeFoldable<'tcx>,
+    {
+        assert_eq!(self.variables.len(), var_values.var_values.len());
+        let value = projection_fn(&self.value);
+        substitute_value(tcx, var_values, value)
+    }
+}
+
+/// Substitute the values from `var_values` into `value`. `var_values`
+/// must be values for the set of canonical variables that appear in
+/// `value`.
+pub(super) fn substitute_value<'a, 'tcx, T>(
+    tcx: TyCtxt<'_, '_, 'tcx>,
+    var_values: &CanonicalVarValues<'tcx>,
+    value: &'a T,
+) -> T
+where
+    T: TypeFoldable<'tcx>,
+{
+    if var_values.var_values.is_empty() {
+        debug_assert!(!value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS));
+        value.clone()
+    } else if !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) {
+        value.clone()
+    } else {
+        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),
+                }
+            }
+            _ => {
+                if !t.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) {
+                    t
+                } else {
+                    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),
+        }
+    }
+}