src/librustc/middle/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 pub use self::ParamSpace::*;
  14 pub use self::RegionSubsts::*;
  15
  16 use middle::ty::{mod, Ty};
  17 use middle::ty_fold::{mod, TypeFoldable, TypeFolder};
  18 use util::ppaux::Repr;
  19
  20 use std::fmt;
  21 use std::slice::Items;
  22 use std::vec::Vec;
  23 use syntax::codemap::{Span, DUMMY_SP};
  24
  25 ///////////////////////////////////////////////////////////////////////////
  26
  27 /// A substitution mapping type/region parameters to new values. We
  28 /// identify each in-scope parameter by an *index* and a *parameter
  29 /// space* (which indices where the parameter is defined; see
  30 /// `ParamSpace`).
  31 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
  32 pub struct Substs<'tcx> {
  33     pub types: VecPerParamSpace<Ty<'tcx>>,
  34     pub regions: RegionSubsts,
  35 }
  36
  37 /// Represents the values to use when substituting lifetime parameters.
  38 /// If the value is `ErasedRegions`, then this subst is occurring during
  39 /// trans, and all region parameters will be replaced with `ty::ReStatic`.
  40 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
  41 pub enum RegionSubsts {
  42     ErasedRegions,
  43     NonerasedRegions(VecPerParamSpace<ty::Region>)
  44 }
  45
  46 impl<'tcx> Substs<'tcx> {
  47     pub fn new(t: VecPerParamSpace<Ty<'tcx>>,
  48                r: VecPerParamSpace<ty::Region>)
  49                -> Substs<'tcx>
  50     {
  51         Substs { types: t, regions: NonerasedRegions(r) }
  52     }
  53
  54     pub fn new_type(t: Vec<Ty<'tcx>>,
  55                     r: Vec<ty::Region>)
  56                     -> Substs<'tcx>
  57     {
  58         Substs::new(VecPerParamSpace::new(t, Vec::new(), Vec::new(), Vec::new()),
  59                     VecPerParamSpace::new(r, Vec::new(), Vec::new(), Vec::new()))
  60     }
  61
  62     pub fn new_trait(t: Vec<Ty<'tcx>>,
  63                      r: Vec<ty::Region>,
  64                      a: Vec<Ty<'tcx>>,
  65                      s: Ty<'tcx>)
  66                     -> Substs<'tcx>
  67     {
  68         Substs::new(VecPerParamSpace::new(t, vec!(s), a, Vec::new()),
  69                     VecPerParamSpace::new(r, Vec::new(), Vec::new(), Vec::new()))
  70     }
  71
  72     pub fn erased(t: VecPerParamSpace<Ty<'tcx>>) -> Substs<'tcx>
  73     {
  74         Substs { types: t, regions: ErasedRegions }
  75     }
  76
  77     pub fn empty() -> Substs<'tcx> {
  78         Substs {
  79             types: VecPerParamSpace::empty(),
  80             regions: NonerasedRegions(VecPerParamSpace::empty()),
  81         }
  82     }
  83
  84     pub fn trans_empty() -> Substs<'tcx> {
  85         Substs {
  86             types: VecPerParamSpace::empty(),
  87             regions: ErasedRegions
  88         }
  89     }
  90
  91     pub fn is_noop(&self) -> bool {
  92         let regions_is_noop = match self.regions {
  93             ErasedRegions => false, // may be used to canonicalize
  94             NonerasedRegions(ref regions) => regions.is_empty(),
  95         };
  96
  97         regions_is_noop && self.types.is_empty()
  98     }
  99
 100     pub fn type_for_def(&self, ty_param_def: &ty::TypeParameterDef) -> Ty<'tcx> {
 101         *self.types.get(ty_param_def.space, ty_param_def.index)
 102     }
 103
 104     pub fn has_regions_escaping_depth(&self, depth: uint) -> bool {
 105         self.types.iter().any(|&t| ty::type_escapes_depth(t, depth)) || {
 106             match self.regions {
 107                 ErasedRegions =>
 108                     false,
 109                 NonerasedRegions(ref regions) =>
 110                     regions.iter().any(|r| r.escapes_depth(depth)),
 111             }
 112         }
 113     }
 114
 115 pub fn self_ty(&self) -> Option<Ty<'tcx>> {
 116         self.types.get_self().map(|&t| t)
 117     }
 118
 119     pub fn with_self_ty(&self, self_ty: Ty<'tcx>) -> Substs<'tcx> {
 120         assert!(self.self_ty().is_none());
 121         let mut s = (*self).clone();
 122         s.types.push(SelfSpace, self_ty);
 123         s
 124     }
 125
 126     pub fn erase_regions(self) -> Substs<'tcx> {
 127         let Substs { types, regions: _ } = self;
 128         Substs { types: types, regions: ErasedRegions }
 129     }
 130
 131     /// Since ErasedRegions are only to be used in trans, most of the compiler can use this method
 132     /// to easily access the set of region substitutions.
 133     pub fn regions<'a>(&'a self) -> &'a VecPerParamSpace<ty::Region> {
 134         match self.regions {
 135             ErasedRegions => panic!("Erased regions only expected in trans"),
 136             NonerasedRegions(ref r) => r
 137         }
 138     }
 139
 140     /// Since ErasedRegions are only to be used in trans, most of the compiler can use this method
 141     /// to easily access the set of region substitutions.
 142     pub fn mut_regions<'a>(&'a mut self) -> &'a mut VecPerParamSpace<ty::Region> {
 143         match self.regions {
 144             ErasedRegions => panic!("Erased regions only expected in trans"),
 145             NonerasedRegions(ref mut r) => r
 146         }
 147     }
 148
 149     pub fn with_method(self,
 150                        m_types: Vec<Ty<'tcx>>,
 151                        m_regions: Vec<ty::Region>)
 152                        -> Substs<'tcx>
 153     {
 154         let Substs { types, regions } = self;
 155         let types = types.with_vec(FnSpace, m_types);
 156         let regions = regions.map(m_regions,
 157                                   |r, m_regions| r.with_vec(FnSpace, m_regions));
 158         Substs { types: types, regions: regions }
 159     }
 160 }
 161
 162 impl RegionSubsts {
 163     fn map<A>(self,
 164               a: A,
 165               op: |VecPerParamSpace<ty::Region>, A| -> VecPerParamSpace<ty::Region>)
 166               -> RegionSubsts {
 167         match self {
 168             ErasedRegions => ErasedRegions,
 169             NonerasedRegions(r) => NonerasedRegions(op(r, a))
 170         }
 171     }
 172
 173     pub fn is_erased(&self) -> bool {
 174         match *self {
 175             ErasedRegions => true,
 176             NonerasedRegions(_) => false,
 177         }
 178     }
 179 }
 180
 181 ///////////////////////////////////////////////////////////////////////////
 182 // ParamSpace
 183
 184 #[deriving(PartialOrd, Ord, PartialEq, Eq,
 185            Clone, Hash, Encodable, Decodable, Show)]
 186 pub enum ParamSpace {
 187     TypeSpace,  // Type parameters attached to a type definition, trait, or impl
 188     SelfSpace,  // Self parameter on a trait
 189     AssocSpace, // Assoc types defined in a trait/impl
 190     FnSpace,    // Type parameters attached to a method or fn
 191 }
 192
 193 impl ParamSpace {
 194     pub fn all() -> [ParamSpace, ..4] {
 195         [TypeSpace, SelfSpace, AssocSpace, FnSpace]
 196     }
 197
 198     pub fn to_uint(self) -> uint {
 199         match self {
 200             TypeSpace => 0,
 201             SelfSpace => 1,
 202             AssocSpace => 2,
 203             FnSpace => 3,
 204         }
 205     }
 206
 207     pub fn from_uint(u: uint) -> ParamSpace {
 208         match u {
 209             0 => TypeSpace,
 210             1 => SelfSpace,
 211             2 => AssocSpace,
 212             3 => FnSpace,
 213             _ => panic!("Invalid ParamSpace: {}", u)
 214         }
 215     }
 216 }
 217
 218 /// Vector of things sorted by param space. Used to keep
 219 /// the set of things declared on the type, self, or method
 220 /// distinct.
 221 #[deriving(PartialEq, Eq, Clone, Hash, Encodable, Decodable)]
 222 pub struct VecPerParamSpace<T> {
 223     // This was originally represented as a tuple with one Vec<T> for
 224     // each variant of ParamSpace, and that remains the abstraction
 225     // that it provides to its clients.
 226     //
 227     // Here is how the representation corresponds to the abstraction
 228     // i.e. the "abstraction function" AF:
 229     //
 230     // AF(self) = (self.content[..self.type_limit],
 231     //             self.content[self.type_limit..self.self_limit],
 232     //             self.content[self.self_limit..self.assoc_limit],
 233     //             self.content[self.assoc_limit..])
 234     type_limit: uint,
 235     self_limit: uint,
 236     assoc_limit: uint,
 237     content: Vec<T>,
 238 }
 239
 240 /// The `split` function converts one `VecPerParamSpace` into this
 241 /// `SeparateVecsPerParamSpace` structure.
 242 pub struct SeparateVecsPerParamSpace<T> {
 243     pub types: Vec<T>,
 244     pub selfs: Vec<T>,
 245     pub assocs: Vec<T>,
 246     pub fns: Vec<T>,
 247 }
 248
 249 impl<T:fmt::Show> fmt::Show for VecPerParamSpace<T> {
 250     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 251         try!(write!(fmt, "VecPerParamSpace {{"));
 252         for space in ParamSpace::all().iter() {
 253             try!(write!(fmt, "{}: {}, ", *space, self.get_slice(*space)));
 254         }
 255         try!(write!(fmt, "}}"));
 256         Ok(())
 257     }
 258 }
 259
 260 impl<T> VecPerParamSpace<T> {
 261     fn limits(&self, space: ParamSpace) -> (uint, uint) {
 262         match space {
 263             TypeSpace => (0, self.type_limit),
 264             SelfSpace => (self.type_limit, self.self_limit),
 265             AssocSpace => (self.self_limit, self.assoc_limit),
 266             FnSpace => (self.assoc_limit, self.content.len()),
 267         }
 268     }
 269
 270     pub fn empty() -> VecPerParamSpace<T> {
 271         VecPerParamSpace {
 272             type_limit: 0,
 273             self_limit: 0,
 274             assoc_limit: 0,
 275             content: Vec::new()
 276         }
 277     }
 278
 279     pub fn params_from_type(types: Vec<T>) -> VecPerParamSpace<T> {
 280         VecPerParamSpace::empty().with_vec(TypeSpace, types)
 281     }
 282
 283     /// `t` is the type space.
 284     /// `s` is the self space.
 285     /// `a` is the assoc space.
 286     /// `f` is the fn space.
 287     pub fn new(t: Vec<T>, s: Vec<T>, a: Vec<T>, f: Vec<T>) -> VecPerParamSpace<T> {
 288         let type_limit = t.len();
 289         let self_limit = type_limit + s.len();
 290         let assoc_limit = self_limit + a.len();
 291
 292         let mut content = t;
 293         content.extend(s.into_iter());
 294         content.extend(a.into_iter());
 295         content.extend(f.into_iter());
 296
 297         VecPerParamSpace {
 298             type_limit: type_limit,
 299             self_limit: self_limit,
 300             assoc_limit: assoc_limit,
 301             content: content,
 302         }
 303     }
 304
 305     fn new_internal(content: Vec<T>, type_limit: uint, self_limit: uint, assoc_limit: uint)
 306                     -> VecPerParamSpace<T>
 307     {
 308         VecPerParamSpace {
 309             type_limit: type_limit,
 310             self_limit: self_limit,
 311             assoc_limit: assoc_limit,
 312             content: content,
 313         }
 314     }
 315
 316     /// Appends `value` to the vector associated with `space`.
 317     ///
 318     /// Unlike the `push` method in `Vec`, this should not be assumed
 319     /// to be a cheap operation (even when amortized over many calls).
 320     pub fn push(&mut self, space: ParamSpace, value: T) {
 321         let (_, limit) = self.limits(space);
 322         match space {
 323             TypeSpace => { self.type_limit += 1; self.self_limit += 1; self.assoc_limit += 1; }
 324             SelfSpace => { self.self_limit += 1; self.assoc_limit += 1; }
 325             AssocSpace => { self.assoc_limit += 1; }
 326             FnSpace => { }
 327         }
 328         self.content.insert(limit, value);
 329     }
 330
 331     pub fn pop(&mut self, space: ParamSpace) -> Option<T> {
 332         let (start, limit) = self.limits(space);
 333         if start == limit {
 334             None
 335         } else {
 336             match space {
 337                 TypeSpace => { self.type_limit -= 1; self.self_limit -= 1; self.assoc_limit -= 1; }
 338                 SelfSpace => { self.self_limit -= 1; self.assoc_limit -= 1; }
 339                 AssocSpace => { self.assoc_limit -= 1; }
 340                 FnSpace => {}
 341             }
 342             self.content.remove(limit - 1)
 343         }
 344     }
 345
 346     pub fn truncate(&mut self, space: ParamSpace, len: uint) {
 347         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 348         while self.len(space) > len {
 349             self.pop(space);
 350         }
 351     }
 352
 353     pub fn replace(&mut self, space: ParamSpace, elems: Vec<T>) {
 354         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 355         self.truncate(space, 0);
 356         for t in elems.into_iter() {
 357             self.push(space, t);
 358         }
 359     }
 360
 361     pub fn get_self<'a>(&'a self) -> Option<&'a T> {
 362         let v = self.get_slice(SelfSpace);
 363         assert!(v.len() <= 1);
 364         if v.len() == 0 { None } else { Some(&v[0]) }
 365     }
 366
 367     pub fn len(&self, space: ParamSpace) -> uint {
 368         self.get_slice(space).len()
 369     }
 370
 371     pub fn is_empty_in(&self, space: ParamSpace) -> bool {
 372         self.len(space) == 0
 373     }
 374
 375     pub fn get_slice<'a>(&'a self, space: ParamSpace) -> &'a [T] {
 376         let (start, limit) = self.limits(space);
 377         self.content.slice(start, limit)
 378     }
 379
 380     pub fn get_mut_slice<'a>(&'a mut self, space: ParamSpace) -> &'a mut [T] {
 381         let (start, limit) = self.limits(space);
 382         self.content.slice_mut(start, limit)
 383     }
 384
 385     pub fn opt_get<'a>(&'a self,
 386                        space: ParamSpace,
 387                        index: uint)
 388                        -> Option<&'a T> {
 389         let v = self.get_slice(space);
 390         if index < v.len() { Some(&v[index]) } else { None }
 391     }
 392
 393     pub fn get<'a>(&'a self, space: ParamSpace, index: uint) -> &'a T {
 394         &self.get_slice(space)[index]
 395     }
 396
 397     pub fn iter<'a>(&'a self) -> Items<'a,T> {
 398         self.content.iter()
 399     }
 400
 401     pub fn iter_enumerated<'a>(&'a self) -> EnumeratedItems<'a,T> {
 402         EnumeratedItems::new(self)
 403     }
 404
 405     pub fn as_slice(&self) -> &[T] {
 406         self.content.as_slice()
 407     }
 408
 409     pub fn all_vecs(&self, pred: |&[T]| -> bool) -> bool {
 410         let spaces = [TypeSpace, SelfSpace, FnSpace];
 411         spaces.iter().all(|&space| { pred(self.get_slice(space)) })
 412     }
 413
 414     pub fn all(&self, pred: |&T| -> bool) -> bool {
 415         self.iter().all(pred)
 416     }
 417
 418     pub fn any(&self, pred: |&T| -> bool) -> bool {
 419         self.iter().any(pred)
 420     }
 421
 422     pub fn is_empty(&self) -> bool {
 423         self.all_vecs(|v| v.is_empty())
 424     }
 425
 426     pub fn map<U>(&self, pred: |&T| -> U) -> VecPerParamSpace<U> {
 427         let result = self.iter().map(pred).collect();
 428         VecPerParamSpace::new_internal(result,
 429                                        self.type_limit,
 430                                        self.self_limit,
 431                                        self.assoc_limit)
 432     }
 433
 434     pub fn map_enumerated<U>(&self, pred: |(ParamSpace, uint, &T)| -> U) -> VecPerParamSpace<U> {
 435         let result = self.iter_enumerated().map(pred).collect();
 436         VecPerParamSpace::new_internal(result,
 437                                        self.type_limit,
 438                                        self.self_limit,
 439                                        self.assoc_limit)
 440     }
 441
 442     pub fn map_move<U>(self, pred: |T| -> U) -> VecPerParamSpace<U> {
 443         let SeparateVecsPerParamSpace {
 444             types: t,
 445             selfs: s,
 446             assocs: a,
 447             fns: f
 448         } = self.split();
 449
 450         VecPerParamSpace::new(t.into_iter().map(|p| pred(p)).collect(),
 451                               s.into_iter().map(|p| pred(p)).collect(),
 452                               a.into_iter().map(|p| pred(p)).collect(),
 453                               f.into_iter().map(|p| pred(p)).collect())
 454     }
 455
 456     pub fn split(self) -> SeparateVecsPerParamSpace<T> {
 457         let VecPerParamSpace { type_limit, self_limit, assoc_limit, content } = self;
 458
 459         let mut content_iter = content.into_iter();
 460
 461         SeparateVecsPerParamSpace {
 462             types: content_iter.by_ref().take(type_limit).collect(),
 463             selfs: content_iter.by_ref().take(self_limit - type_limit).collect(),
 464             assocs: content_iter.by_ref().take(assoc_limit - self_limit).collect(),
 465             fns: content_iter.collect()
 466         }
 467     }
 468
 469     pub fn with_vec(mut self, space: ParamSpace, vec: Vec<T>)
 470                     -> VecPerParamSpace<T>
 471     {
 472         assert!(self.is_empty_in(space));
 473         self.replace(space, vec);
 474         self
 475     }
 476 }
 477
 478 pub struct EnumeratedItems<'a,T:'a> {
 479     vec: &'a VecPerParamSpace<T>,
 480     space_index: uint,
 481     elem_index: uint
 482 }
 483
 484 impl<'a,T> EnumeratedItems<'a,T> {
 485     fn new(v: &'a VecPerParamSpace<T>) -> EnumeratedItems<'a,T> {
 486         let mut result = EnumeratedItems { vec: v, space_index: 0, elem_index: 0 };
 487         result.adjust_space();
 488         result
 489     }
 490
 491     fn adjust_space(&mut self) {
 492         let spaces = ParamSpace::all();
 493         while
 494             self.space_index < spaces.len() &&
 495             self.elem_index >= self.vec.len(spaces[self.space_index])
 496         {
 497             self.space_index += 1;
 498             self.elem_index = 0;
 499         }
 500     }
 501 }
 502
 503 impl<'a,T> Iterator<(ParamSpace, uint, &'a T)> for EnumeratedItems<'a,T> {
 504     fn next(&mut self) -> Option<(ParamSpace, uint, &'a T)> {
 505         let spaces = ParamSpace::all();
 506         if self.space_index < spaces.len() {
 507             let space = spaces[self.space_index];
 508             let index = self.elem_index;
 509             let item = self.vec.get(space, index);
 510
 511             self.elem_index += 1;
 512             self.adjust_space();
 513
 514             Some((space, index, item))
 515         } else {
 516             None
 517         }
 518     }
 519 }
 520
 521 ///////////////////////////////////////////////////////////////////////////
 522 // Public trait `Subst`
 523 //
 524 // Just call `foo.subst(tcx, substs)` to perform a substitution across
 525 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
 526 // there is more information available (for better errors).
 527
 528 pub trait Subst<'tcx> {
 529     fn subst(&self, tcx: &ty::ctxt<'tcx>, substs: &Substs<'tcx>) -> Self {
 530         self.subst_spanned(tcx, substs, None)
 531     }
 532
 533     fn subst_spanned(&self, tcx: &ty::ctxt<'tcx>,
 534                      substs: &Substs<'tcx>,
 535                      span: Option<Span>)
 536                      -> Self;
 537 }
 538
 539 impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T {
 540     fn subst_spanned(&self,
 541                      tcx: &ty::ctxt<'tcx>,
 542                      substs: &Substs<'tcx>,
 543                      span: Option<Span>)
 544                      -> T
 545     {
 546         let mut folder = SubstFolder { tcx: tcx,
 547                                        substs: substs,
 548                                        span: span,
 549                                        root_ty: None,
 550                                        ty_stack_depth: 0,
 551                                        region_binders_passed: 0 };
 552         (*self).fold_with(&mut folder)
 553     }
 554 }
 555
 556 ///////////////////////////////////////////////////////////////////////////
 557 // The actual substitution engine itself is a type folder.
 558
 559 struct SubstFolder<'a, 'tcx: 'a> {
 560     tcx: &'a ty::ctxt<'tcx>,
 561     substs: &'a Substs<'tcx>,
 562
 563     // The location for which the substitution is performed, if available.
 564     span: Option<Span>,
 565
 566     // The root type that is being substituted, if available.
 567     root_ty: Option<Ty<'tcx>>,
 568
 569     // Depth of type stack
 570     ty_stack_depth: uint,
 571
 572     // Number of region binders we have passed through while doing the substitution
 573     region_binders_passed: uint,
 574 }
 575
 576 impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
 577     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 578
 579     fn enter_region_binder(&mut self) {
 580         self.region_binders_passed += 1;
 581     }
 582
 583     fn exit_region_binder(&mut self) {
 584         self.region_binders_passed -= 1;
 585     }
 586
 587     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 588         // Note: This routine only handles regions that are bound on
 589         // type declarations and other outer declarations, not those
 590         // bound in *fn types*. Region substitution of the bound
 591         // regions that appear in a function signature is done using
 592         // the specialized routine `ty::replace_late_regions()`.
 593         match r {
 594             ty::ReEarlyBound(_, space, i, region_name) => {
 595                 match self.substs.regions {
 596                     ErasedRegions => ty::ReStatic,
 597                     NonerasedRegions(ref regions) =>
 598                         match regions.opt_get(space, i) {
 599                             Some(&r) => {
 600                                 self.shift_region_through_binders(r)
 601                             }
 602                             None => {
 603                                 let span = self.span.unwrap_or(DUMMY_SP);
 604                                 self.tcx().sess.span_bug(
 605                                     span,
 606                                     format!("Type parameter out of range \
 607                                      when substituting in region {} (root type={}) \
 608                                      (space={}, index={})",
 609                                     region_name.as_str(),
 610                                     self.root_ty.repr(self.tcx()),
 611                                     space, i).as_slice());
 612                             }
 613                         }
 614                 }
 615             }
 616             _ => r
 617         }
 618     }
 619
 620     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 621         if !ty::type_needs_subst(t) {
 622             return t;
 623         }
 624
 625         // track the root type we were asked to substitute
 626         let depth = self.ty_stack_depth;
 627         if depth == 0 {
 628             self.root_ty = Some(t);
 629         }
 630         self.ty_stack_depth += 1;
 631
 632         let t1 = match t.sty {
 633             ty::ty_param(p) => {
 634                 self.ty_for_param(p, t)
 635             }
 636             _ => {
 637                 ty_fold::super_fold_ty(self, t)
 638             }
 639         };
 640
 641         assert_eq!(depth + 1, self.ty_stack_depth);
 642         self.ty_stack_depth -= 1;
 643         if depth == 0 {
 644             self.root_ty = None;
 645         }
 646
 647         return t1;
 648     }
 649 }
 650
 651 impl<'a,'tcx> SubstFolder<'a,'tcx> {
 652     fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> {
 653         // Look up the type in the substitutions. It really should be in there.
 654         let opt_ty = self.substs.types.opt_get(p.space, p.idx);
 655         let ty = match opt_ty {
 656             Some(t) => *t,
 657             None => {
 658                 let span = self.span.unwrap_or(DUMMY_SP);
 659                 self.tcx().sess.span_bug(
 660                     span,
 661                     format!("Type parameter `{}` ({}/{}/{}) out of range \
 662                                  when substituting (root type={}) substs={}",
 663                             p.repr(self.tcx()),
 664                             source_ty.repr(self.tcx()),
 665                             p.space,
 666                             p.idx,
 667                             self.root_ty.repr(self.tcx()),
 668                             self.substs.repr(self.tcx())).as_slice());
 669             }
 670         };
 671
 672         self.shift_regions_through_binders(ty)
 673     }
 674
 675     /// It is sometimes necessary to adjust the debruijn indices during substitution. This occurs
 676     /// when we are substituting a type with escaping regions into a context where we have passed
 677     /// through region binders. That's quite a mouthful. Let's see an example:
 678     ///
 679     /// ```
 680     /// type Func<A> = fn(A);
 681     /// type MetaFunc = for<'a> fn(Func<&'a int>)
 682     /// ```
 683     ///
 684     /// The type `MetaFunc`, when fully expanded, will be
 685     ///
 686     ///     for<'a> fn(fn(&'a int))
 687     ///             ^~ ^~ ^~~
 688     ///             |  |  |
 689     ///             |  |  DebruijnIndex of 2
 690     ///             Binders
 691     ///
 692     /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
 693     /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
 694     /// over the inner binder (remember that we count Debruijn indices from 1). However, in the
 695     /// definition of `MetaFunc`, the binder is not visible, so the type `&'a int` will have a
 696     /// debruijn index of 1. It's only during the substitution that we can see we must increase the
 697     /// depth by 1 to account for the binder that we passed through.
 698     ///
 699     /// As a second example, consider this twist:
 700     ///
 701     /// ```
 702     /// type FuncTuple<A> = (A,fn(A));
 703     /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>)
 704     /// ```
 705     ///
 706     /// Here the final type will be:
 707     ///
 708     ///     for<'a> fn((&'a int, fn(&'a int)))
 709     ///                 ^~~         ^~~
 710     ///                 |           |
 711     ///          DebruijnIndex of 1 |
 712     ///                      DebruijnIndex of 2
 713     ///
 714     /// As indicated in the diagram, here the same type `&'a int` is substituted once, but in the
 715     /// first case we do not increase the Debruijn index and in the second case we do. The reason
 716     /// is that only in the second case have we passed through a fn binder.
 717     fn shift_regions_through_binders(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
 718         debug!("shift_regions(ty={}, region_binders_passed={}, type_has_escaping_regions={})",
 719                ty.repr(self.tcx()), self.region_binders_passed, ty::type_has_escaping_regions(ty));
 720
 721         if self.region_binders_passed == 0 || !ty::type_has_escaping_regions(ty) {
 722             return ty;
 723         }
 724
 725         let result = ty_fold::shift_regions(self.tcx(), self.region_binders_passed, &ty);
 726         debug!("shift_regions: shifted result = {}", result.repr(self.tcx()));
 727
 728         result
 729     }
 730
 731     fn shift_region_through_binders(&self, region: ty::Region) -> ty::Region {
 732         ty_fold::shift_region(region, self.region_binders_passed)
 733     }
 734 }