src/librustc/ty/subst.rs

   1 // Type substitutions.
   2
   3 use crate::hir::def_id::DefId;
   4 use crate::infer::canonical::Canonical;
   5 use crate::ty::{self, Lift, List, Ty, TyCtxt};
   6 use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
   7
   8 use serialize::{self, Encodable, Encoder, Decodable, Decoder};
   9 use syntax_pos::{Span, DUMMY_SP};
  10 use smallvec::SmallVec;
  11
  12 use core::intrinsics;
  13 use std::cmp::Ordering;
  14 use std::fmt;
  15 use std::marker::PhantomData;
  16 use std::mem;
  17 use std::num::NonZeroUsize;
  18
  19 /// An entity in the Rust type system, which can be one of
  20 /// several kinds (only types and lifetimes for now).
  21 /// To reduce memory usage, a `Kind` is a interned pointer,
  22 /// with the lowest 2 bits being reserved for a tag to
  23 /// indicate the type (`Ty` or `Region`) it points to.
  24 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  25 pub struct Kind<'tcx> {
  26     ptr: NonZeroUsize,
  27     marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>)>
  28 }
  29
  30 const TAG_MASK: usize = 0b11;
  31 const TYPE_TAG: usize = 0b00;
  32 const REGION_TAG: usize = 0b01;
  33
  34 #[derive(Debug, RustcEncodable, RustcDecodable, PartialEq, Eq, PartialOrd, Ord)]
  35 pub enum UnpackedKind<'tcx> {
  36     Lifetime(ty::Region<'tcx>),
  37     Type(Ty<'tcx>),
  38 }
  39
  40 impl<'tcx> UnpackedKind<'tcx> {
  41     fn pack(self) -> Kind<'tcx> {
  42         let (tag, ptr) = match self {
  43             UnpackedKind::Lifetime(lt) => {
  44                 // Ensure we can use the tag bits.
  45                 assert_eq!(mem::align_of_val(lt) & TAG_MASK, 0);
  46                 (REGION_TAG, lt as *const _ as usize)
  47             }
  48             UnpackedKind::Type(ty) => {
  49                 // Ensure we can use the tag bits.
  50                 assert_eq!(mem::align_of_val(ty) & TAG_MASK, 0);
  51                 (TYPE_TAG, ty as *const _ as usize)
  52             }
  53         };
  54
  55         Kind {
  56             ptr: unsafe {
  57                 NonZeroUsize::new_unchecked(ptr | tag)
  58             },
  59             marker: PhantomData
  60         }
  61     }
  62 }
  63
  64 impl<'tcx> Ord for Kind<'tcx> {
  65     fn cmp(&self, other: &Kind<'_>) -> Ordering {
  66         self.unpack().cmp(&other.unpack())
  67     }
  68 }
  69
  70 impl<'tcx> PartialOrd for Kind<'tcx> {
  71     fn partial_cmp(&self, other: &Kind<'_>) -> Option<Ordering> {
  72         Some(self.cmp(&other))
  73     }
  74 }
  75
  76 impl<'tcx> From<ty::Region<'tcx>> for Kind<'tcx> {
  77     fn from(r: ty::Region<'tcx>) -> Kind<'tcx> {
  78         UnpackedKind::Lifetime(r).pack()
  79     }
  80 }
  81
  82 impl<'tcx> From<Ty<'tcx>> for Kind<'tcx> {
  83     fn from(ty: Ty<'tcx>) -> Kind<'tcx> {
  84         UnpackedKind::Type(ty).pack()
  85     }
  86 }
  87
  88 impl<'tcx> Kind<'tcx> {
  89     #[inline]
  90     pub fn unpack(self) -> UnpackedKind<'tcx> {
  91         let ptr = self.ptr.get();
  92         unsafe {
  93             match ptr & TAG_MASK {
  94                 REGION_TAG => UnpackedKind::Lifetime(&*((ptr & !TAG_MASK) as *const _)),
  95                 TYPE_TAG => UnpackedKind::Type(&*((ptr & !TAG_MASK) as *const _)),
  96                 _ => intrinsics::unreachable()
  97             }
  98         }
  99     }
 100 }
 101
 102 impl<'tcx> fmt::Debug for Kind<'tcx> {
 103     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 104         match self.unpack() {
 105             UnpackedKind::Lifetime(lt) => write!(f, "{:?}", lt),
 106             UnpackedKind::Type(ty) => write!(f, "{:?}", ty),
 107         }
 108     }
 109 }
 110
 111 impl<'tcx> fmt::Display for Kind<'tcx> {
 112     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 113         match self.unpack() {
 114             UnpackedKind::Lifetime(lt) => write!(f, "{}", lt),
 115             UnpackedKind::Type(ty) => write!(f, "{}", ty),
 116         }
 117     }
 118 }
 119
 120 impl<'a, 'tcx> Lift<'tcx> for Kind<'a> {
 121     type Lifted = Kind<'tcx>;
 122
 123     fn lift_to_tcx<'cx, 'gcx>(&self, tcx: TyCtxt<'cx, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 124         match self.unpack() {
 125             UnpackedKind::Lifetime(a) => a.lift_to_tcx(tcx).map(|a| a.into()),
 126             UnpackedKind::Type(a) => a.lift_to_tcx(tcx).map(|a| a.into()),
 127         }
 128     }
 129 }
 130
 131 impl<'tcx> TypeFoldable<'tcx> for Kind<'tcx> {
 132     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 133         match self.unpack() {
 134             UnpackedKind::Lifetime(lt) => lt.fold_with(folder).into(),
 135             UnpackedKind::Type(ty) => ty.fold_with(folder).into(),
 136         }
 137     }
 138
 139     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 140         match self.unpack() {
 141             UnpackedKind::Lifetime(lt) => lt.visit_with(visitor),
 142             UnpackedKind::Type(ty) => ty.visit_with(visitor),
 143         }
 144     }
 145 }
 146
 147 impl<'tcx> Encodable for Kind<'tcx> {
 148     fn encode<E: Encoder>(&self, e: &mut E) -> Result<(), E::Error> {
 149         self.unpack().encode(e)
 150     }
 151 }
 152
 153 impl<'tcx> Decodable for Kind<'tcx> {
 154     fn decode<D: Decoder>(d: &mut D) -> Result<Kind<'tcx>, D::Error> {
 155         Ok(UnpackedKind::decode(d)?.pack())
 156     }
 157 }
 158
 159 /// A substitution mapping generic parameters to new values.
 160 pub type InternalSubsts<'tcx> = List<Kind<'tcx>>;
 161
 162 pub type SubstsRef<'tcx> = &'tcx InternalSubsts<'tcx>;
 163
 164 impl<'a, 'gcx, 'tcx> InternalSubsts<'tcx> {
 165     /// Creates a `InternalSubsts` that maps each generic parameter to itself.
 166     pub fn identity_for_item(tcx: TyCtxt<'a, 'gcx, 'tcx>, def_id: DefId)
 167                              -> SubstsRef<'tcx> {
 168         Self::for_item(tcx, def_id, |param, _| {
 169             tcx.mk_param_from_def(param)
 170         })
 171     }
 172
 173     /// Creates a `InternalSubsts` that maps each generic parameter to a higher-ranked
 174     /// var bound at index `0`. For types, we use a `BoundVar` index equal to
 175     /// the type parameter index. For regions, we use the `BoundRegion::BrNamed`
 176     /// variant (which has a `DefId`).
 177     pub fn bound_vars_for_item(
 178         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 179         def_id: DefId
 180     ) -> SubstsRef<'tcx> {
 181         Self::for_item(tcx, def_id, |param, _| {
 182             match param.kind {
 183                 ty::GenericParamDefKind::Type { .. } => {
 184                     tcx.mk_ty(
 185                         ty::Bound(ty::INNERMOST, ty::BoundTy {
 186                             var: ty::BoundVar::from(param.index),
 187                             kind: ty::BoundTyKind::Param(param.name),
 188                         })
 189                     ).into()
 190                 }
 191
 192                 ty::GenericParamDefKind::Lifetime => {
 193                     tcx.mk_region(ty::RegionKind::ReLateBound(
 194                         ty::INNERMOST,
 195                         ty::BoundRegion::BrNamed(param.def_id, param.name)
 196                     )).into()
 197                 }
 198             }
 199         })
 200     }
 201
 202     /// Creates a `InternalSubsts` for generic parameter definitions,
 203     /// by calling closures to obtain each kind.
 204     /// The closures get to observe the `InternalSubsts` as they're
 205     /// being built, which can be used to correctly
 206     /// substitute defaults of generic parameters.
 207     pub fn for_item<F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 208                        def_id: DefId,
 209                        mut mk_kind: F)
 210                        -> SubstsRef<'tcx>
 211     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 212     {
 213         let defs = tcx.generics_of(def_id);
 214         let count = defs.count();
 215         let mut substs = SmallVec::with_capacity(count);
 216         Self::fill_item(&mut substs, tcx, defs, &mut mk_kind);
 217         tcx.intern_substs(&substs)
 218     }
 219
 220     pub fn extend_to<F>(&self,
 221                         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 222                         def_id: DefId,
 223                         mut mk_kind: F)
 224                         -> SubstsRef<'tcx>
 225     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 226     {
 227         Self::for_item(tcx, def_id, |param, substs| {
 228             self.get(param.index as usize)
 229                 .cloned()
 230                 .unwrap_or_else(|| mk_kind(param, substs))
 231         })
 232     }
 233
 234     fn fill_item<F>(substs: &mut SmallVec<[Kind<'tcx>; 8]>,
 235                     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 236                     defs: &ty::Generics,
 237                     mk_kind: &mut F)
 238     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 239     {
 240         if let Some(def_id) = defs.parent {
 241             let parent_defs = tcx.generics_of(def_id);
 242             Self::fill_item(substs, tcx, parent_defs, mk_kind);
 243         }
 244         Self::fill_single(substs, defs, mk_kind)
 245     }
 246
 247     fn fill_single<F>(substs: &mut SmallVec<[Kind<'tcx>; 8]>,
 248                       defs: &ty::Generics,
 249                       mk_kind: &mut F)
 250     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 251     {
 252         substs.reserve(defs.params.len());
 253         for param in &defs.params {
 254             let kind = mk_kind(param, substs);
 255             assert_eq!(param.index as usize, substs.len());
 256             substs.push(kind);
 257         }
 258     }
 259
 260     pub fn is_noop(&self) -> bool {
 261         self.is_empty()
 262     }
 263
 264     #[inline]
 265     pub fn types(&'a self) -> impl DoubleEndedIterator<Item = Ty<'tcx>> + 'a {
 266         self.iter().filter_map(|k| {
 267             if let UnpackedKind::Type(ty) = k.unpack() {
 268                 Some(ty)
 269             } else {
 270                 None
 271             }
 272         })
 273     }
 274
 275     #[inline]
 276     pub fn regions(&'a self) -> impl DoubleEndedIterator<Item = ty::Region<'tcx>> + 'a {
 277         self.iter().filter_map(|k| {
 278             if let UnpackedKind::Lifetime(lt) = k.unpack() {
 279                 Some(lt)
 280             } else {
 281                 None
 282             }
 283         })
 284     }
 285
 286     #[inline]
 287     pub fn type_at(&self, i: usize) -> Ty<'tcx> {
 288         if let UnpackedKind::Type(ty) = self[i].unpack() {
 289             ty
 290         } else {
 291             bug!("expected type for param #{} in {:?}", i, self);
 292         }
 293     }
 294
 295     #[inline]
 296     pub fn region_at(&self, i: usize) -> ty::Region<'tcx> {
 297         if let UnpackedKind::Lifetime(lt) = self[i].unpack() {
 298             lt
 299         } else {
 300             bug!("expected region for param #{} in {:?}", i, self);
 301         }
 302     }
 303
 304     #[inline]
 305     pub fn type_for_def(&self, def: &ty::GenericParamDef) -> Kind<'tcx> {
 306         self.type_at(def.index as usize).into()
 307     }
 308
 309     /// Transform from substitutions for a child of `source_ancestor`
 310     /// (e.g., a trait or impl) to substitutions for the same child
 311     /// in a different item, with `target_substs` as the base for
 312     /// the target impl/trait, with the source child-specific
 313     /// parameters (e.g., method parameters) on top of that base.
 314     pub fn rebase_onto(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 315                        source_ancestor: DefId,
 316                        target_substs: SubstsRef<'tcx>)
 317                        -> SubstsRef<'tcx> {
 318         let defs = tcx.generics_of(source_ancestor);
 319         tcx.mk_substs(target_substs.iter().chain(&self[defs.params.len()..]).cloned())
 320     }
 321
 322     pub fn truncate_to(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, generics: &ty::Generics)
 323                        -> SubstsRef<'tcx> {
 324         tcx.mk_substs(self.iter().take(generics.count()).cloned())
 325     }
 326 }
 327
 328 impl<'tcx> TypeFoldable<'tcx> for SubstsRef<'tcx> {
 329     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 330         let params: SmallVec<[_; 8]> = self.iter().map(|k| k.fold_with(folder)).collect();
 331
 332         // If folding doesn't change the substs, it's faster to avoid
 333         // calling `mk_substs` and instead reuse the existing substs.
 334         if params[..] == self[..] {
 335             self
 336         } else {
 337             folder.tcx().intern_substs(&params)
 338         }
 339     }
 340
 341     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 342         self.iter().any(|t| t.visit_with(visitor))
 343     }
 344 }
 345
 346 impl<'tcx> serialize::UseSpecializedDecodable for SubstsRef<'tcx> {}
 347
 348 ///////////////////////////////////////////////////////////////////////////
 349 // Public trait `Subst`
 350 //
 351 // Just call `foo.subst(tcx, substs)` to perform a substitution across
 352 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
 353 // there is more information available (for better errors).
 354
 355 pub trait Subst<'tcx>: Sized {
 356     fn subst<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 357                        substs: &[Kind<'tcx>]) -> Self {
 358         self.subst_spanned(tcx, substs, None)
 359     }
 360
 361     fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 362                                substs: &[Kind<'tcx>],
 363                                span: Option<Span>)
 364                                -> Self;
 365 }
 366
 367 impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T {
 368     fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 369                                substs: &[Kind<'tcx>],
 370                                span: Option<Span>)
 371                                -> T
 372     {
 373         let mut folder = SubstFolder { tcx,
 374                                        substs,
 375                                        span,
 376                                        root_ty: None,
 377                                        ty_stack_depth: 0,
 378                                        binders_passed: 0 };
 379         (*self).fold_with(&mut folder)
 380     }
 381 }
 382
 383 ///////////////////////////////////////////////////////////////////////////
 384 // The actual substitution engine itself is a type folder.
 385
 386 struct SubstFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 387     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 388     substs: &'a [Kind<'tcx>],
 389
 390     // The location for which the substitution is performed, if available.
 391     span: Option<Span>,
 392
 393     // The root type that is being substituted, if available.
 394     root_ty: Option<Ty<'tcx>>,
 395
 396     // Depth of type stack
 397     ty_stack_depth: usize,
 398
 399     // Number of region binders we have passed through while doing the substitution
 400     binders_passed: u32,
 401 }
 402
 403 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for SubstFolder<'a, 'gcx, 'tcx> {
 404     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 405
 406     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
 407         self.binders_passed += 1;
 408         let t = t.super_fold_with(self);
 409         self.binders_passed -= 1;
 410         t
 411     }
 412
 413     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 414         // Note: This routine only handles regions that are bound on
 415         // type declarations and other outer declarations, not those
 416         // bound in *fn types*. Region substitution of the bound
 417         // regions that appear in a function signature is done using
 418         // the specialized routine `ty::replace_late_regions()`.
 419         match *r {
 420             ty::ReEarlyBound(data) => {
 421                 let r = self.substs.get(data.index as usize).map(|k| k.unpack());
 422                 match r {
 423                     Some(UnpackedKind::Lifetime(lt)) => {
 424                         self.shift_region_through_binders(lt)
 425                     }
 426                     _ => {
 427                         let span = self.span.unwrap_or(DUMMY_SP);
 428                         span_bug!(
 429                             span,
 430                             "Region parameter out of range \
 431                              when substituting in region {} (root type={:?}) \
 432                              (index={})",
 433                             data.name,
 434                             self.root_ty,
 435                             data.index);
 436                     }
 437                 }
 438             }
 439             _ => r
 440         }
 441     }
 442
 443     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 444         if !t.needs_subst() {
 445             return t;
 446         }
 447
 448         // track the root type we were asked to substitute
 449         let depth = self.ty_stack_depth;
 450         if depth == 0 {
 451             self.root_ty = Some(t);
 452         }
 453         self.ty_stack_depth += 1;
 454
 455         let t1 = match t.sty {
 456             ty::Param(p) => {
 457                 self.ty_for_param(p, t)
 458             }
 459             _ => {
 460                 t.super_fold_with(self)
 461             }
 462         };
 463
 464         assert_eq!(depth + 1, self.ty_stack_depth);
 465         self.ty_stack_depth -= 1;
 466         if depth == 0 {
 467             self.root_ty = None;
 468         }
 469
 470         return t1;
 471     }
 472 }
 473
 474 impl<'a, 'gcx, 'tcx> SubstFolder<'a, 'gcx, 'tcx> {
 475     fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> {
 476         // Look up the type in the substitutions. It really should be in there.
 477         let opt_ty = self.substs.get(p.idx as usize).map(|k| k.unpack());
 478         let ty = match opt_ty {
 479             Some(UnpackedKind::Type(ty)) => ty,
 480             _ => {
 481                 let span = self.span.unwrap_or(DUMMY_SP);
 482                 span_bug!(
 483                     span,
 484                     "Type parameter `{:?}` ({:?}/{}) out of range \
 485                      when substituting (root type={:?}) substs={:?}",
 486                     p,
 487                     source_ty,
 488                     p.idx,
 489                     self.root_ty,
 490                     self.substs);
 491             }
 492         };
 493
 494         self.shift_vars_through_binders(ty)
 495     }
 496
 497     /// It is sometimes necessary to adjust the De Bruijn indices during substitution. This occurs
 498     /// when we are substituting a type with escaping bound vars into a context where we have
 499     /// passed through binders. That's quite a mouthful. Let's see an example:
 500     ///
 501     /// ```
 502     /// type Func<A> = fn(A);
 503     /// type MetaFunc = for<'a> fn(Func<&'a int>)
 504     /// ```
 505     ///
 506     /// The type `MetaFunc`, when fully expanded, will be
 507     ///
 508     ///     for<'a> fn(fn(&'a int))
 509     ///             ^~ ^~ ^~~
 510     ///             |  |  |
 511     ///             |  |  DebruijnIndex of 2
 512     ///             Binders
 513     ///
 514     /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
 515     /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
 516     /// over the inner binder (remember that we count De Bruijn indices from 1). However, in the
 517     /// definition of `MetaFunc`, the binder is not visible, so the type `&'a int` will have a
 518     /// De Bruijn index of 1. It's only during the substitution that we can see we must increase the
 519     /// depth by 1 to account for the binder that we passed through.
 520     ///
 521     /// As a second example, consider this twist:
 522     ///
 523     /// ```
 524     /// type FuncTuple<A> = (A,fn(A));
 525     /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>)
 526     /// ```
 527     ///
 528     /// Here the final type will be:
 529     ///
 530     ///     for<'a> fn((&'a int, fn(&'a int)))
 531     ///                 ^~~         ^~~
 532     ///                 |           |
 533     ///          DebruijnIndex of 1 |
 534     ///                      DebruijnIndex of 2
 535     ///
 536     /// As indicated in the diagram, here the same type `&'a int` is substituted once, but in the
 537     /// first case we do not increase the De Bruijn index and in the second case we do. The reason
 538     /// is that only in the second case have we passed through a fn binder.
 539     fn shift_vars_through_binders(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
 540         debug!("shift_vars(ty={:?}, binders_passed={:?}, has_escaping_bound_vars={:?})",
 541                ty, self.binders_passed, ty.has_escaping_bound_vars());
 542
 543         if self.binders_passed == 0 || !ty.has_escaping_bound_vars() {
 544             return ty;
 545         }
 546
 547         let result = ty::fold::shift_vars(self.tcx(), &ty, self.binders_passed);
 548         debug!("shift_vars: shifted result = {:?}", result);
 549
 550         result
 551     }
 552
 553     fn shift_region_through_binders(&self, region: ty::Region<'tcx>) -> ty::Region<'tcx> {
 554         if self.binders_passed == 0 || !region.has_escaping_bound_vars() {
 555             return region;
 556         }
 557         ty::fold::shift_region(self.tcx, region, self.binders_passed)
 558     }
 559 }
 560
 561 pub type CanonicalUserSubsts<'tcx> = Canonical<'tcx, UserSubsts<'tcx>>;
 562
 563 /// Stores the user-given substs to reach some fully qualified path
 564 /// (e.g., `<T>::Item` or `<T as Trait>::Item`).
 565 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 566 pub struct UserSubsts<'tcx> {
 567     /// The substitutions for the item as given by the user.
 568     pub substs: SubstsRef<'tcx>,
 569
 570     /// The self type, in the case of a `<T>::Item` path (when applied
 571     /// to an inherent impl). See `UserSelfTy` below.
 572     pub user_self_ty: Option<UserSelfTy<'tcx>>,
 573 }
 574
 575 BraceStructTypeFoldableImpl! {
 576     impl<'tcx> TypeFoldable<'tcx> for UserSubsts<'tcx> {
 577         substs,
 578         user_self_ty,
 579     }
 580 }
 581
 582 BraceStructLiftImpl! {
 583     impl<'a, 'tcx> Lift<'tcx> for UserSubsts<'a> {
 584         type Lifted = UserSubsts<'tcx>;
 585         substs,
 586         user_self_ty,
 587     }
 588 }
 589
 590 /// Specifies the user-given self type. In the case of a path that
 591 /// refers to a member in an inherent impl, this self type is
 592 /// sometimes needed to constrain the type parameters on the impl. For
 593 /// example, in this code:
 594 ///
 595 /// ```
 596 /// struct Foo<T> { }
 597 /// impl<A> Foo<A> { fn method() { } }
 598 /// ```
 599 ///
 600 /// when you then have a path like `<Foo<&'static u32>>::method`,
 601 /// this struct would carry the `DefId` of the impl along with the
 602 /// self type `Foo<u32>`. Then we can instantiate the parameters of
 603 /// the impl (with the substs from `UserSubsts`) and apply those to
 604 /// the self type, giving `Foo<?A>`. Finally, we unify that with
 605 /// the self type here, which contains `?A` to be `&'static u32`
 606 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 607 pub struct UserSelfTy<'tcx> {
 608     pub impl_def_id: DefId,
 609     pub self_ty: Ty<'tcx>,
 610 }
 611
 612 BraceStructTypeFoldableImpl! {
 613     impl<'tcx> TypeFoldable<'tcx> for UserSelfTy<'tcx> {
 614         impl_def_id,
 615         self_ty,
 616     }
 617 }
 618
 619 BraceStructLiftImpl! {
 620     impl<'a, 'tcx> Lift<'tcx> for UserSelfTy<'a> {
 621         type Lifted = UserSelfTy<'tcx>;
 622         impl_def_id,
 623         self_ty,
 624     }
 625 }