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