src/librustc/middle/subst.rs

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