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