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