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.
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.
11 // Type substitutions.
13 pub use self::ParamSpace
::*;
14 pub use self::RegionSubsts
::*;
16 use middle
::ty
::{self, Ty}
;
17 use middle
::ty_fold
::{self, TypeFoldable, TypeFolder}
;
20 use std
::iter
::IntoIterator
;
22 use std
::vec
::{Vec, IntoIter}
;
23 use syntax
::codemap
::{Span, DUMMY_SP}
;
25 ///////////////////////////////////////////////////////////////////////////
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
31 #[derive(Clone, PartialEq, Eq, Hash)]
32 pub struct Substs
<'tcx
> {
33 pub types
: VecPerParamSpace
<Ty
<'tcx
>>,
34 pub regions
: RegionSubsts
,
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)]
41 pub enum RegionSubsts
{
43 NonerasedRegions(VecPerParamSpace
<ty
::Region
>)
46 impl<'tcx
> Substs
<'tcx
> {
47 pub fn new(t
: VecPerParamSpace
<Ty
<'tcx
>>,
48 r
: VecPerParamSpace
<ty
::Region
>)
51 Substs { types: t, regions: NonerasedRegions(r) }
54 pub fn new_type(t
: Vec
<Ty
<'tcx
>>,
58 Substs
::new(VecPerParamSpace
::new(t
, Vec
::new(), Vec
::new()),
59 VecPerParamSpace
::new(r
, Vec
::new(), Vec
::new()))
62 pub fn new_trait(t
: Vec
<Ty
<'tcx
>>,
67 Substs
::new(VecPerParamSpace
::new(t
, vec
!(s
), Vec
::new()),
68 VecPerParamSpace
::new(r
, Vec
::new(), Vec
::new()))
71 pub fn erased(t
: VecPerParamSpace
<Ty
<'tcx
>>) -> Substs
<'tcx
>
73 Substs { types: t, regions: ErasedRegions }
76 pub fn empty() -> Substs
<'tcx
> {
78 types
: VecPerParamSpace
::empty(),
79 regions
: NonerasedRegions(VecPerParamSpace
::empty()),
83 pub fn trans_empty() -> Substs
<'tcx
> {
85 types
: VecPerParamSpace
::empty(),
86 regions
: ErasedRegions
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(),
96 regions_is_noop
&& self.types
.is_empty()
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 usize)
103 pub fn has_regions_escaping_depth(&self, depth
: u32) -> bool
{
104 self.types
.iter().any(|&t
| ty
::type_escapes_depth(t
, depth
)) || {
108 NonerasedRegions(ref regions
) =>
109 regions
.iter().any(|r
| r
.escapes_depth(depth
)),
114 pub fn self_ty(&self) -> Option
<Ty
<'tcx
>> {
115 self.types
.get_self().cloned()
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
);
125 pub fn erase_regions(self) -> Substs
<'tcx
> {
126 let Substs { types, regions: _ }
= self;
127 Substs { types: types, regions: ErasedRegions }
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
> {
134 ErasedRegions
=> panic
!("Erased regions only expected in trans"),
135 NonerasedRegions(ref r
) => r
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
> {
143 ErasedRegions
=> panic
!("Erased regions only expected in trans"),
144 NonerasedRegions(ref mut r
) => r
148 pub fn with_method(self,
149 m_types
: Vec
<Ty
<'tcx
>>,
150 m_regions
: Vec
<ty
::Region
>)
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 }
162 fn map
<A
, F
>(self, a
: A
, op
: F
) -> RegionSubsts
where
163 F
: FnOnce(VecPerParamSpace
<ty
::Region
>, A
) -> VecPerParamSpace
<ty
::Region
>,
166 ErasedRegions
=> ErasedRegions
,
167 NonerasedRegions(r
) => NonerasedRegions(op(r
, a
))
171 pub fn is_erased(&self) -> bool
{
173 ErasedRegions
=> true,
174 NonerasedRegions(_
) => false,
179 ///////////////////////////////////////////////////////////////////////////
182 #[derive(PartialOrd, Ord, PartialEq, Eq, Copy,
183 Clone
, Hash
, RustcEncodable
, RustcDecodable
, Debug
)]
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
191 pub fn all() -> [ParamSpace
; 3] {
192 [TypeSpace
, SelfSpace
, FnSpace
]
195 pub fn to_uint(self) -> usize {
203 pub fn from_uint(u
: usize) -> ParamSpace
{
208 _
=> panic
!("Invalid ParamSpace: {}", u
)
213 /// Vector of things sorted by param space. Used to keep
214 /// the set of things declared on the type, self, or method
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.
222 // Here is how the representation corresponds to the abstraction
223 // i.e. the "abstraction function" AF:
225 // AF(self) = (self.content[..self.type_limit],
226 // self.content[self.type_limit..self.self_limit],
227 // self.content[self.self_limit..])
233 /// The `split` function converts one `VecPerParamSpace` into this
234 /// `SeparateVecsPerParamSpace` structure.
235 pub struct SeparateVecsPerParamSpace
<T
> {
241 impl<T
: fmt
::Debug
> fmt
::Debug
for VecPerParamSpace
<T
> {
242 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
243 write
!(f
, "[{:?};{:?};{:?}]",
244 self.get_slice(TypeSpace
),
245 self.get_slice(SelfSpace
),
246 self.get_slice(FnSpace
))
250 impl<T
> VecPerParamSpace
<T
> {
251 fn limits(&self, space
: ParamSpace
) -> (usize, usize) {
253 TypeSpace
=> (0, self.type_limit
),
254 SelfSpace
=> (self.type_limit
, self.self_limit
),
255 FnSpace
=> (self.self_limit
, self.content
.len()),
259 pub fn empty() -> VecPerParamSpace
<T
> {
267 pub fn params_from_type(types
: Vec
<T
>) -> VecPerParamSpace
<T
> {
268 VecPerParamSpace
::empty().with_vec(TypeSpace
, types
)
271 /// `t` is the type space.
272 /// `s` is the self space.
273 /// `f` is the fn space.
274 pub fn new(t
: Vec
<T
>, s
: Vec
<T
>, f
: Vec
<T
>) -> VecPerParamSpace
<T
> {
275 let type_limit
= t
.len();
276 let self_limit
= type_limit
+ s
.len();
283 type_limit
: type_limit
,
284 self_limit
: self_limit
,
289 fn new_internal(content
: Vec
<T
>, type_limit
: usize, self_limit
: usize)
290 -> VecPerParamSpace
<T
>
293 type_limit
: type_limit
,
294 self_limit
: self_limit
,
299 /// Appends `value` to the vector associated with `space`.
301 /// Unlike the `push` method in `Vec`, this should not be assumed
302 /// to be a cheap operation (even when amortized over many calls).
303 pub fn push(&mut self, space
: ParamSpace
, value
: T
) {
304 let (_
, limit
) = self.limits(space
);
306 TypeSpace
=> { self.type_limit += 1; self.self_limit += 1; }
307 SelfSpace
=> { self.self_limit += 1; }
310 self.content
.insert(limit
, value
);
313 /// Appends `values` to the vector associated with `space`.
315 /// Unlike the `extend` method in `Vec`, this should not be assumed
316 /// to be a cheap operation (even when amortized over many calls).
317 pub fn extend
<I
:Iterator
<Item
=T
>>(&mut self, space
: ParamSpace
, values
: I
) {
318 // This could be made more efficient, obviously.
320 self.push(space
, item
);
324 pub fn pop(&mut self, space
: ParamSpace
) -> Option
<T
> {
325 let (start
, limit
) = self.limits(space
);
330 TypeSpace
=> { self.type_limit -= 1; self.self_limit -= 1; }
331 SelfSpace
=> { self.self_limit -= 1; }
334 if self.content
.is_empty() {
337 Some(self.content
.remove(limit
- 1))
342 pub fn truncate(&mut self, space
: ParamSpace
, len
: usize) {
343 // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
344 while self.len(space
) > len
{
349 pub fn replace(&mut self, space
: ParamSpace
, elems
: Vec
<T
>) {
350 // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
351 self.truncate(space
, 0);
357 pub fn get_self
<'a
>(&'a
self) -> Option
<&'a T
> {
358 let v
= self.get_slice(SelfSpace
);
359 assert
!(v
.len() <= 1);
360 if v
.is_empty() { None }
else { Some(&v[0]) }
363 pub fn len(&self, space
: ParamSpace
) -> usize {
364 self.get_slice(space
).len()
367 pub fn is_empty_in(&self, space
: ParamSpace
) -> bool
{
371 pub fn get_slice
<'a
>(&'a
self, space
: ParamSpace
) -> &'a
[T
] {
372 let (start
, limit
) = self.limits(space
);
373 &self.content
[start
.. limit
]
376 pub fn get_mut_slice
<'a
>(&'a
mut self, space
: ParamSpace
) -> &'a
mut [T
] {
377 let (start
, limit
) = self.limits(space
);
378 &mut self.content
[start
.. limit
]
381 pub fn opt_get
<'a
>(&'a
self,
385 let v
= self.get_slice(space
);
386 if index
< v
.len() { Some(&v[index]) }
else { None }
389 pub fn get
<'a
>(&'a
self, space
: ParamSpace
, index
: usize) -> &'a T
{
390 &self.get_slice(space
)[index
]
393 pub fn iter
<'a
>(&'a
self) -> Iter
<'a
,T
> {
397 pub fn into_iter(self) -> IntoIter
<T
> {
398 self.content
.into_iter()
401 pub fn iter_enumerated
<'a
>(&'a
self) -> EnumeratedItems
<'a
,T
> {
402 EnumeratedItems
::new(self)
405 pub fn as_slice(&self) -> &[T
] {
409 pub fn into_vec(self) -> Vec
<T
> {
413 pub fn all_vecs
<P
>(&self, mut pred
: P
) -> bool
where
414 P
: FnMut(&[T
]) -> bool
,
416 let spaces
= [TypeSpace
, SelfSpace
, FnSpace
];
417 spaces
.iter().all(|&space
| { pred(self.get_slice(space)) }
)
420 pub fn all
<P
>(&self, pred
: P
) -> bool
where P
: FnMut(&T
) -> bool
{
421 self.iter().all(pred
)
424 pub fn any
<P
>(&self, pred
: P
) -> bool
where P
: FnMut(&T
) -> bool
{
425 self.iter().any(pred
)
428 pub fn is_empty(&self) -> bool
{
429 self.all_vecs(|v
| v
.is_empty())
432 pub fn map
<U
, P
>(&self, pred
: P
) -> VecPerParamSpace
<U
> where P
: FnMut(&T
) -> U
{
433 let result
= self.iter().map(pred
).collect();
434 VecPerParamSpace
::new_internal(result
,
439 pub fn map_enumerated
<U
, P
>(&self, pred
: P
) -> VecPerParamSpace
<U
> where
440 P
: FnMut((ParamSpace
, usize, &T
)) -> U
,
442 let result
= self.iter_enumerated().map(pred
).collect();
443 VecPerParamSpace
::new_internal(result
,
448 pub fn split(self) -> SeparateVecsPerParamSpace
<T
> {
449 let VecPerParamSpace { type_limit, self_limit, content }
= self;
451 let mut content_iter
= content
.into_iter();
453 SeparateVecsPerParamSpace
{
454 types
: content_iter
.by_ref().take(type_limit
).collect(),
455 selfs
: content_iter
.by_ref().take(self_limit
- type_limit
).collect(),
456 fns
: content_iter
.collect()
460 pub fn with_vec(mut self, space
: ParamSpace
, vec
: Vec
<T
>)
461 -> VecPerParamSpace
<T
>
463 assert
!(self.is_empty_in(space
));
464 self.replace(space
, vec
);
470 pub struct EnumeratedItems
<'a
,T
:'a
> {
471 vec
: &'a VecPerParamSpace
<T
>,
476 impl<'a
,T
> EnumeratedItems
<'a
,T
> {
477 fn new(v
: &'a VecPerParamSpace
<T
>) -> EnumeratedItems
<'a
,T
> {
478 let mut result
= EnumeratedItems { vec: v, space_index: 0, elem_index: 0 }
;
479 result
.adjust_space();
483 fn adjust_space(&mut self) {
484 let spaces
= ParamSpace
::all();
486 self.space_index
< spaces
.len() &&
487 self.elem_index
>= self.vec
.len(spaces
[self.space_index
])
489 self.space_index
+= 1;
495 impl<'a
,T
> Iterator
for EnumeratedItems
<'a
,T
> {
496 type Item
= (ParamSpace
, usize, &'a T
);
498 fn next(&mut self) -> Option
<(ParamSpace
, usize, &'a T
)> {
499 let spaces
= ParamSpace
::all();
500 if self.space_index
< spaces
.len() {
501 let space
= spaces
[self.space_index
];
502 let index
= self.elem_index
;
503 let item
= self.vec
.get(space
, index
);
505 self.elem_index
+= 1;
508 Some((space
, index
, item
))
515 impl<T
> IntoIterator
for VecPerParamSpace
<T
> {
517 type IntoIter
= IntoIter
<T
>;
519 fn into_iter(self) -> IntoIter
<T
> {
520 self.into_vec().into_iter()
524 impl<'a
,T
> IntoIterator
for &'a VecPerParamSpace
<T
> {
526 type IntoIter
= Iter
<'a
, T
>;
528 fn into_iter(self) -> Iter
<'a
, T
> {
529 self.as_slice().into_iter()
534 ///////////////////////////////////////////////////////////////////////////
535 // Public trait `Subst`
537 // Just call `foo.subst(tcx, substs)` to perform a substitution across
538 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
539 // there is more information available (for better errors).
541 pub trait Subst
<'tcx
> : Sized
{
542 fn subst(&self, tcx
: &ty
::ctxt
<'tcx
>, substs
: &Substs
<'tcx
>) -> Self {
543 self.subst_spanned(tcx
, substs
, None
)
546 fn subst_spanned(&self, tcx
: &ty
::ctxt
<'tcx
>,
547 substs
: &Substs
<'tcx
>,
552 impl<'tcx
, T
:TypeFoldable
<'tcx
>> Subst
<'tcx
> for T
{
553 fn subst_spanned(&self,
554 tcx
: &ty
::ctxt
<'tcx
>,
555 substs
: &Substs
<'tcx
>,
559 let mut folder
= SubstFolder
{ tcx
: tcx
,
564 region_binders_passed
: 0 };
565 (*self).fold_with(&mut folder
)
569 ///////////////////////////////////////////////////////////////////////////
570 // The actual substitution engine itself is a type folder.
572 struct SubstFolder
<'a
, 'tcx
: 'a
> {
573 tcx
: &'a ty
::ctxt
<'tcx
>,
574 substs
: &'a Substs
<'tcx
>,
576 // The location for which the substitution is performed, if available.
579 // The root type that is being substituted, if available.
580 root_ty
: Option
<Ty
<'tcx
>>,
582 // Depth of type stack
583 ty_stack_depth
: usize,
585 // Number of region binders we have passed through while doing the substitution
586 region_binders_passed
: u32,
589 impl<'a
, 'tcx
> TypeFolder
<'tcx
> for SubstFolder
<'a
, 'tcx
> {
590 fn tcx(&self) -> &ty
::ctxt
<'tcx
> { self.tcx }
592 fn enter_region_binder(&mut self) {
593 self.region_binders_passed
+= 1;
596 fn exit_region_binder(&mut self) {
597 self.region_binders_passed
-= 1;
600 fn fold_region(&mut self, r
: ty
::Region
) -> ty
::Region
{
601 // Note: This routine only handles regions that are bound on
602 // type declarations and other outer declarations, not those
603 // bound in *fn types*. Region substitution of the bound
604 // regions that appear in a function signature is done using
605 // the specialized routine `ty::replace_late_regions()`.
607 ty
::ReEarlyBound(data
) => {
608 match self.substs
.regions
{
609 ErasedRegions
=> ty
::ReStatic
,
610 NonerasedRegions(ref regions
) =>
611 match regions
.opt_get(data
.space
, data
.index
as usize) {
613 self.shift_region_through_binders(r
)
616 let span
= self.span
.unwrap_or(DUMMY_SP
);
617 self.tcx().sess
.span_bug(
619 &format
!("Type parameter out of range \
620 when substituting in region {} (root type={:?}) \
621 (space={:?}, index={})",
634 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
635 if !ty
::type_needs_subst(t
) {
639 // track the root type we were asked to substitute
640 let depth
= self.ty_stack_depth
;
642 self.root_ty
= Some(t
);
644 self.ty_stack_depth
+= 1;
646 let t1
= match t
.sty
{
648 self.ty_for_param(p
, t
)
651 ty_fold
::super_fold_ty(self, t
)
655 assert_eq
!(depth
+ 1, self.ty_stack_depth
);
656 self.ty_stack_depth
-= 1;
665 impl<'a
,'tcx
> SubstFolder
<'a
,'tcx
> {
666 fn ty_for_param(&self, p
: ty
::ParamTy
, source_ty
: Ty
<'tcx
>) -> Ty
<'tcx
> {
667 // Look up the type in the substitutions. It really should be in there.
668 let opt_ty
= self.substs
.types
.opt_get(p
.space
, p
.idx
as usize);
669 let ty
= match opt_ty
{
672 let span
= self.span
.unwrap_or(DUMMY_SP
);
673 self.tcx().sess
.span_bug(
675 &format
!("Type parameter `{:?}` ({:?}/{:?}/{}) out of range \
676 when substituting (root type={:?}) substs={:?}",
686 self.shift_regions_through_binders(ty
)
689 /// It is sometimes necessary to adjust the debruijn indices during substitution. This occurs
690 /// when we are substituting a type with escaping regions into a context where we have passed
691 /// through region binders. That's quite a mouthful. Let's see an example:
694 /// type Func<A> = fn(A);
695 /// type MetaFunc = for<'a> fn(Func<&'a int>)
698 /// The type `MetaFunc`, when fully expanded, will be
700 /// for<'a> fn(fn(&'a int))
703 /// | | DebruijnIndex of 2
706 /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
707 /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
708 /// over the inner binder (remember that we count Debruijn indices from 1). However, in the
709 /// definition of `MetaFunc`, the binder is not visible, so the type `&'a int` will have a
710 /// debruijn index of 1. It's only during the substitution that we can see we must increase the
711 /// depth by 1 to account for the binder that we passed through.
713 /// As a second example, consider this twist:
716 /// type FuncTuple<A> = (A,fn(A));
717 /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>)
720 /// Here the final type will be:
722 /// for<'a> fn((&'a int, fn(&'a int)))
725 /// DebruijnIndex of 1 |
726 /// DebruijnIndex of 2
728 /// As indicated in the diagram, here the same type `&'a int` is substituted once, but in the
729 /// first case we do not increase the Debruijn index and in the second case we do. The reason
730 /// is that only in the second case have we passed through a fn binder.
731 fn shift_regions_through_binders(&self, ty
: Ty
<'tcx
>) -> Ty
<'tcx
> {
732 debug
!("shift_regions(ty={:?}, region_binders_passed={:?}, type_has_escaping_regions={:?})",
733 ty
, self.region_binders_passed
, ty
::type_has_escaping_regions(ty
));
735 if self.region_binders_passed
== 0 || !ty
::type_has_escaping_regions(ty
) {
739 let result
= ty_fold
::shift_regions(self.tcx(), self.region_binders_passed
, &ty
);
740 debug
!("shift_regions: shifted result = {:?}", result
);
745 fn shift_region_through_binders(&self, region
: ty
::Region
) -> ty
::Region
{
746 ty_fold
::shift_region(region
, self.region_binders_passed
)