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