src/librustc_middle/infer/canonical.rs - third_party/rust - Git at Google

 //! **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 constraints
 //! 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.
 //!
 //! For a more detailed look at what is happening here, check
 //! out the [chapter in the rustc dev guide][c].
 //!
 //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html

 use crate::infer::MemberConstraint;
 use crate::ty::subst::GenericArg;
 use crate::ty::{self, BoundVar, List, Region, TyCtxt};
 use rustc_index::vec::IndexVec;
 use rustc_macros::HashStable;
 use rustc_serialize::UseSpecializedDecodable;
 use smallvec::SmallVec;
 use std::ops::Index;

 /// A "canonicalized" type `V` is one where all free inference
 /// variables have been rewritten to "canonical vars". These are
 /// numbered starting from 0 in order of first appearance.
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 #[derive(HashStable, TypeFoldable, Lift)]
 pub struct Canonical<'tcx, V> {
     pub max_universe: ty::UniverseIndex,
     pub variables: CanonicalVarInfos<'tcx>,
     pub value: V,
 }

 pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo>;

 impl<'tcx> UseSpecializedDecodable for CanonicalVarInfos<'tcx> {}

 /// 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 will need to supply it later to instantiate the
 /// canonicalized query response.
 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 #[derive(HashStable, TypeFoldable, Lift)]
 pub struct CanonicalVarValues<'tcx> {
     pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>,
 }

 /// When we canonicalize a value to form a query, we wind up replacing
 /// various parts of it with canonical variables. This struct stores
 /// those replaced bits to remember for when we process the query
 /// result.
 #[derive(Clone, Debug)]
 pub struct OriginalQueryValues<'tcx> {
     /// Map from the universes that appear in the query to the
     /// universes in the caller context. For the time being, we only
     /// ever put ROOT values into the query, so this map is very
     /// simple.
     pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,

     /// This is equivalent to `CanonicalVarValues`, but using a
     /// `SmallVec` yields a significant performance win.
     pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
 }

 impl Default for OriginalQueryValues<'tcx> {
     fn default() -> Self {
         let mut universe_map = SmallVec::default();
         universe_map.push(ty::UniverseIndex::ROOT);

         Self { universe_map, var_values: SmallVec::default() }
     }
 }

 /// Information about a canonical variable that is included with the
 /// canonical value. This is sufficient information for code to create
 /// a copy of the canonical value in some other inference context,
 /// with fresh inference variables replacing the canonical values.
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
 pub struct CanonicalVarInfo {
     pub kind: CanonicalVarKind,
 }

 impl CanonicalVarInfo {
     pub fn universe(&self) -> ty::UniverseIndex {
         self.kind.universe()
     }

     pub fn is_existential(&self) -> bool {
         match self.kind {
             CanonicalVarKind::Ty(_) => true,
             CanonicalVarKind::PlaceholderTy(_) => false,
             CanonicalVarKind::Region(_) => true,
             CanonicalVarKind::PlaceholderRegion(..) => false,
             CanonicalVarKind::Const(_) => true,
             CanonicalVarKind::PlaceholderConst(_) => false,
         }
     }
 }

 /// Describes the "kind" of the canonical variable. This is a "kind"
 /// in the type-theory sense of the term -- i.e., a "meta" type system
 /// that analyzes type-like values.
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
 pub enum CanonicalVarKind {
     /// Some kind of type inference variable.
     Ty(CanonicalTyVarKind),

     /// A "placeholder" that represents "any type".
     PlaceholderTy(ty::PlaceholderType),

     /// Region variable `'?R`.
     Region(ty::UniverseIndex),

     /// A "placeholder" that represents "any region". Created when you
     /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
     /// bound region `'a`.
     PlaceholderRegion(ty::PlaceholderRegion),

     /// Some kind of const inference variable.
     Const(ty::UniverseIndex),

     /// A "placeholder" that represents "any const".
     PlaceholderConst(ty::PlaceholderConst),
 }

 impl CanonicalVarKind {
     pub fn universe(self) -> ty::UniverseIndex {
         match self {
             CanonicalVarKind::Ty(kind) => match kind {
                 CanonicalTyVarKind::General(ui) => ui,
                 CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
             },

             CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
             CanonicalVarKind::Region(ui) => ui,
             CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
             CanonicalVarKind::Const(ui) => ui,
             CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe,
         }
     }
 }

 /// 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, RustcDecodable, RustcEncodable, HashStable)]
 pub enum CanonicalTyVarKind {
     /// General type variable `?T` that can be unified with arbitrary types.
     General(ty::UniverseIndex),

     /// 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<QueryResponse<..>>`. You can use
 /// `instantiate_query_result` to access the data in this result.
 #[derive(Clone, Debug, HashStable, TypeFoldable, Lift)]
 pub struct QueryResponse<'tcx, R> {
     pub var_values: CanonicalVarValues<'tcx>,
     pub region_constraints: QueryRegionConstraints<'tcx>,
     pub certainty: Certainty,
     pub value: R,
 }

 #[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)]
 pub struct QueryRegionConstraints<'tcx> {
     pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
     pub member_constraints: Vec<MemberConstraint<'tcx>>,
 }

 impl QueryRegionConstraints<'_> {
     /// Represents an empty (trivially true) set of region
     /// constraints.
     pub fn is_empty(&self) -> bool {
         self.outlives.is_empty() && self.member_constraints.is_empty()
     }
 }

 pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>;

 pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;

 /// Indicates whether or not we were able to prove the query to be
 /// true.
 #[derive(Copy, Clone, Debug, HashStable)]
 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> QueryResponse<'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, QueryResponse<'tcx, R>> {
     pub fn is_proven(&self) -> bool {
         self.value.is_proven()
     }

     pub fn is_ambiguous(&self) -> bool {
         !self.is_proven()
     }
 }

 impl<'tcx, V> Canonical<'tcx, V> {
     /// Allows you to map the `value` of a canonical while keeping the
     /// same set of bound variables.
     ///
     /// **WARNING:** This function is very easy to mis-use, hence the
     /// name!  In particular, the new value `W` must use all **the
     /// same type/region variables** in **precisely the same order**
     /// as the original! (The ordering is defined by the
     /// `TypeFoldable` implementation of the type in question.)
     ///
     /// An example of a **correct** use of this:
     ///
     /// ```rust,ignore (not real code)
     /// let a: Canonical<'_, T> = ...;
     /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
     /// ```
     ///
     /// An example of an **incorrect** use of this:
     ///
     /// ```rust,ignore (not real code)
     /// let a: Canonical<'tcx, T> = ...;
     /// let ty: Ty<'tcx> = ...;
     /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
     /// ```
     pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> {
         let Canonical { max_universe, variables, value } = self;
         Canonical { max_universe, variables, value: map_op(value) }
     }
 }

 pub type QueryOutlivesConstraint<'tcx> =
     ty::Binder<ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>;

 CloneTypeFoldableAndLiftImpls! {
     crate::infer::canonical::Certainty,
     crate::infer::canonical::CanonicalVarInfo,
     crate::infer::canonical::CanonicalVarKind,
 }

 CloneTypeFoldableImpls! {
     for <'tcx> {
         crate::infer::canonical::CanonicalVarInfos<'tcx>,
     }
 }

 impl<'tcx> CanonicalVarValues<'tcx> {
     pub fn len(&self) -> usize {
         self.var_values.len()
     }

     /// Makes an identity substitution from this one: each bound var
     /// is matched to the same bound var, preserving the original kinds.
     /// For example, if we have:
     /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
     /// we'll return a substitution `subst` with:
     /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
     pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self {
         use crate::ty::subst::GenericArgKind;

         CanonicalVarValues {
             var_values: self
                 .var_values
                 .iter()
                 .zip(0..)
                 .map(|(kind, i)| match kind.unpack() {
                     GenericArgKind::Type(..) => {
                         tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
                     }
                     GenericArgKind::Lifetime(..) => tcx
                         .mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion::BrAnon(i)))
                         .into(),
                     GenericArgKind::Const(ct) => tcx
                         .mk_const(ty::Const {
                             ty: ct.ty,
                             val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)),
                         })
                         .into(),
                 })
                 .collect(),
         }
     }
 }

 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
     type Item = GenericArg<'tcx>;
     type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>;

     fn into_iter(self) -> Self::IntoIter {
         self.var_values.iter().cloned()
     }
 }

 impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
     type Output = GenericArg<'tcx>;

     fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
         &self.var_values[value]
     }
 }
	//! 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 constraints
	//! 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.
	//!
	//! For a more detailed look at what is happening here, check
	//! out the [chapter in the rustc dev guide][c].
	//!
	//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html

	use crate::infer::MemberConstraint;
	use crate::ty::subst::GenericArg;
	use crate::ty::{self, BoundVar, List, Region, TyCtxt};
	use rustc_index::vec::IndexVec;
	use rustc_macros::HashStable;
	use rustc_serialize::UseSpecializedDecodable;
	use smallvec::SmallVec;
	use std::ops::Index;

	/// A "canonicalized" type `V` is one where all free inference
	/// variables have been rewritten to "canonical vars". These are
	/// numbered starting from 0 in order of first appearance.
	#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
	#[derive(HashStable, TypeFoldable, Lift)]
	pub struct Canonical<'tcx, V> {
	pub max_universe: ty::UniverseIndex,
	pub variables: CanonicalVarInfos<'tcx>,
	pub value: V,
	}

	pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo>;

	impl<'tcx> UseSpecializedDecodable for CanonicalVarInfos<'tcx> {}

	/// 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 will need to supply it later to instantiate the
	/// canonicalized query response.
	#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
	#[derive(HashStable, TypeFoldable, Lift)]
	pub struct CanonicalVarValues<'tcx> {
	pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>,
	}

	/// When we canonicalize a value to form a query, we wind up replacing
	/// various parts of it with canonical variables. This struct stores
	/// those replaced bits to remember for when we process the query
	/// result.
	#[derive(Clone, Debug)]
	pub struct OriginalQueryValues<'tcx> {
	/// Map from the universes that appear in the query to the
	/// universes in the caller context. For the time being, we only
	/// ever put ROOT values into the query, so this map is very
	/// simple.
	pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,

	/// This is equivalent to `CanonicalVarValues`, but using a
	/// `SmallVec` yields a significant performance win.
	pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
	}

	impl Default for OriginalQueryValues<'tcx> {
	fn default() -> Self {
	let mut universe_map = SmallVec::default();
	universe_map.push(ty::UniverseIndex::ROOT);

	Self { universe_map, var_values: SmallVec::default() }
	}
	}

	/// Information about a canonical variable that is included with the
	/// canonical value. This is sufficient information for code to create
	/// a copy of the canonical value in some other inference context,
	/// with fresh inference variables replacing the canonical values.
	#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
	pub struct CanonicalVarInfo {
	pub kind: CanonicalVarKind,
	}

	impl CanonicalVarInfo {
	pub fn universe(&self) -> ty::UniverseIndex {
	self.kind.universe()
	}

	pub fn is_existential(&self) -> bool {
	match self.kind {
	CanonicalVarKind::Ty(_) => true,
	CanonicalVarKind::PlaceholderTy(_) => false,
	CanonicalVarKind::Region(_) => true,
	CanonicalVarKind::PlaceholderRegion(..) => false,
	CanonicalVarKind::Const(_) => true,
	CanonicalVarKind::PlaceholderConst(_) => false,
	}
	}
	}

	/// Describes the "kind" of the canonical variable. This is a "kind"
	/// in the type-theory sense of the term -- i.e., a "meta" type system
	/// that analyzes type-like values.
	#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
	pub enum CanonicalVarKind {
	/// Some kind of type inference variable.
	Ty(CanonicalTyVarKind),

	/// A "placeholder" that represents "any type".
	PlaceholderTy(ty::PlaceholderType),

	/// Region variable `'?R`.
	Region(ty::UniverseIndex),

	/// A "placeholder" that represents "any region". Created when you
	/// are solving a goal like `for<'a> T: Foo<'a>` to represent the
	/// bound region `'a`.
	PlaceholderRegion(ty::PlaceholderRegion),

	/// Some kind of const inference variable.
	Const(ty::UniverseIndex),

	/// A "placeholder" that represents "any const".
	PlaceholderConst(ty::PlaceholderConst),
	}

	impl CanonicalVarKind {
	pub fn universe(self) -> ty::UniverseIndex {
	match self {
	CanonicalVarKind::Ty(kind) => match kind {
	CanonicalTyVarKind::General(ui) => ui,
	CanonicalTyVarKind::Float \| CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
	},

	CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
	CanonicalVarKind::Region(ui) => ui,
	CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
	CanonicalVarKind::Const(ui) => ui,
	CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe,
	}
	}
	}

	/// 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, RustcDecodable, RustcEncodable, HashStable)]
	pub enum CanonicalTyVarKind {
	/// General type variable `?T` that can be unified with arbitrary types.
	General(ty::UniverseIndex),

	/// 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<QueryResponse<..>>`. You can use
	/// `instantiate_query_result` to access the data in this result.
	#[derive(Clone, Debug, HashStable, TypeFoldable, Lift)]
	pub struct QueryResponse<'tcx, R> {
	pub var_values: CanonicalVarValues<'tcx>,
	pub region_constraints: QueryRegionConstraints<'tcx>,
	pub certainty: Certainty,
	pub value: R,
	}

	#[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)]
	pub struct QueryRegionConstraints<'tcx> {
	pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
	pub member_constraints: Vec<MemberConstraint<'tcx>>,
	}

	impl QueryRegionConstraints<'_> {
	/// Represents an empty (trivially true) set of region
	/// constraints.
	pub fn is_empty(&self) -> bool {
	self.outlives.is_empty() && self.member_constraints.is_empty()
	}
	}

	pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>;

	pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;

	/// Indicates whether or not we were able to prove the query to be
	/// true.
	#[derive(Copy, Clone, Debug, HashStable)]
	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> QueryResponse<'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, QueryResponse<'tcx, R>> {
	pub fn is_proven(&self) -> bool {
	self.value.is_proven()
	}

	pub fn is_ambiguous(&self) -> bool {
	!self.is_proven()
	}
	}

	impl<'tcx, V> Canonical<'tcx, V> {
	/// Allows you to map the `value` of a canonical while keeping the
	/// same set of bound variables.
	///
	/// WARNING: This function is very easy to mis-use, hence the
	/// name! In particular, the new value `W` must use all **the
	/// same type/region variables in precisely the same order**
	/// as the original! (The ordering is defined by the
	/// `TypeFoldable` implementation of the type in question.)
	///
	/// An example of a correct use of this:
	///
	/// ```rust,ignore (not real code)
	/// let a: Canonical<'_, T> = ...;
	/// let b: Canonical<'_, (T,)> = a.unchecked_map(\|v\| (v, ));
	/// ```
	///
	/// An example of an incorrect use of this:
	///
	/// ```rust,ignore (not real code)
	/// let a: Canonical<'tcx, T> = ...;
	/// let ty: Ty<'tcx> = ...;
	/// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(\|v\| (v, ty));
	/// ```
	pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> {
	let Canonical { max_universe, variables, value } = self;
	Canonical { max_universe, variables, value: map_op(value) }
	}
	}

	pub type QueryOutlivesConstraint<'tcx> =
	ty::Binder<ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>;

	CloneTypeFoldableAndLiftImpls! {
	crate::infer::canonical::Certainty,
	crate::infer::canonical::CanonicalVarInfo,
	crate::infer::canonical::CanonicalVarKind,
	}

	CloneTypeFoldableImpls! {
	for <'tcx> {
	crate::infer::canonical::CanonicalVarInfos<'tcx>,
	}
	}

	impl<'tcx> CanonicalVarValues<'tcx> {
	pub fn len(&self) -> usize {
	self.var_values.len()
	}

	/// Makes an identity substitution from this one: each bound var
	/// is matched to the same bound var, preserving the original kinds.
	/// For example, if we have:
	/// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
	/// we'll return a substitution `subst` with:
	/// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
	pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self {
	use crate::ty::subst::GenericArgKind;

	CanonicalVarValues {
	var_values: self
	.var_values
	.iter()
	.zip(0..)
	.map(\|(kind, i)\| match kind.unpack() {
	GenericArgKind::Type(..) => {
	tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
	}
	GenericArgKind::Lifetime(..) => tcx
	.mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion::BrAnon(i)))
	.into(),
	GenericArgKind::Const(ct) => tcx
	.mk_const(ty::Const {
	ty: ct.ty,
	val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)),
	})
	.into(),
	})
	.collect(),
	}
	}
	}

	impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
	type Item = GenericArg<'tcx>;
	type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>;

	fn into_iter(self) -> Self::IntoIter {
	self.var_values.iter().cloned()
	}
	}

	impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
	type Output = GenericArg<'tcx>;

	fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
	&self.var_values[value]
	}
	}