src/librustc/ty/subst.rs

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