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