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