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
::*;
17 use middle
::def_id
::DefId
;
18 use middle
::ty
::{self, Ty}
;
19 use middle
::ty
::fold
::{TypeFoldable, TypeFolder}
;
21 use serialize
::{Encodable, Encoder, Decodable, Decoder}
;
23 use std
::iter
::IntoIterator
;
25 use std
::vec
::{Vec, IntoIter}
;
26 use syntax
::codemap
::{Span, DUMMY_SP}
;
28 ///////////////////////////////////////////////////////////////////////////
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
34 #[derive(Clone, PartialEq, Eq, Hash)]
35 pub struct Substs
<'tcx
> {
36 pub types
: VecPerParamSpace
<Ty
<'tcx
>>,
37 pub regions
: RegionSubsts
,
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 #[derive(Clone, PartialEq, Eq, Hash)]
44 pub enum RegionSubsts
{
46 NonerasedRegions(VecPerParamSpace
<ty
::Region
>)
49 impl<'tcx
> Substs
<'tcx
> {
50 pub fn new(t
: VecPerParamSpace
<Ty
<'tcx
>>,
51 r
: VecPerParamSpace
<ty
::Region
>)
54 Substs { types: t, regions: NonerasedRegions(r) }
57 pub fn new_type(t
: Vec
<Ty
<'tcx
>>,
61 Substs
::new(VecPerParamSpace
::new(t
, Vec
::new(), Vec
::new()),
62 VecPerParamSpace
::new(r
, Vec
::new(), Vec
::new()))
65 pub fn new_trait(t
: Vec
<Ty
<'tcx
>>,
70 Substs
::new(VecPerParamSpace
::new(t
, vec
!(s
), Vec
::new()),
71 VecPerParamSpace
::new(r
, Vec
::new(), Vec
::new()))
74 pub fn erased(t
: VecPerParamSpace
<Ty
<'tcx
>>) -> Substs
<'tcx
>
76 Substs { types: t, regions: ErasedRegions }
79 pub fn empty() -> Substs
<'tcx
> {
81 types
: VecPerParamSpace
::empty(),
82 regions
: NonerasedRegions(VecPerParamSpace
::empty()),
86 pub fn trans_empty() -> Substs
<'tcx
> {
88 types
: VecPerParamSpace
::empty(),
89 regions
: ErasedRegions
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(),
99 regions_is_noop
&& self.types
.is_empty()
102 pub fn type_for_def(&self, ty_param_def
: &ty
::TypeParameterDef
) -> Ty
<'tcx
> {
103 *self.types
.get(ty_param_def
.space
, ty_param_def
.index
as usize)
106 pub fn self_ty(&self) -> Option
<Ty
<'tcx
>> {
107 self.types
.get_self().cloned()
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
);
117 pub fn erase_regions(self) -> Substs
<'tcx
> {
118 let Substs { types, regions: _ }
= self;
119 Substs { types: types, regions: ErasedRegions }
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
> {
126 ErasedRegions
=> panic
!("Erased regions only expected in trans"),
127 NonerasedRegions(ref r
) => r
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
> {
135 ErasedRegions
=> panic
!("Erased regions only expected in trans"),
136 NonerasedRegions(ref mut r
) => r
140 pub fn with_method(self,
141 m_types
: Vec
<Ty
<'tcx
>>,
142 m_regions
: Vec
<ty
::Region
>)
145 let Substs { types, regions }
= self;
146 let types
= types
.with_slice(FnSpace
, &m_types
);
147 let regions
= regions
.map(|r
| r
.with_slice(FnSpace
, &m_regions
));
148 Substs { types: types, regions: regions }
151 pub fn with_method_from(self,
152 meth_substs
: &Substs
<'tcx
>)
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
))
160 Substs { types: types, regions: regions }
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();
167 types
.truncate(FnSpace
, 0);
168 let regions
= regions
.map(|mut r
| { r.truncate(FnSpace, 0); r }
);
172 substs
: tcx
.mk_substs(Substs { types: types, regions: regions }
)
177 impl<'tcx
> Encodable
for Substs
<'tcx
> {
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);
187 impl<'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
))
195 impl<'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
)
207 pub fn map
<F
>(self, op
: F
) -> RegionSubsts
where
208 F
: FnOnce(VecPerParamSpace
<ty
::Region
>) -> VecPerParamSpace
<ty
::Region
>,
211 ErasedRegions
=> ErasedRegions
,
212 NonerasedRegions(r
) => NonerasedRegions(op(r
))
216 pub fn is_erased(&self) -> bool
{
218 ErasedRegions
=> true,
219 NonerasedRegions(_
) => false,
224 ///////////////////////////////////////////////////////////////////////////
227 #[derive(PartialOrd, Ord, PartialEq, Eq, Copy,
228 Clone
, Hash
, RustcEncodable
, RustcDecodable
, Debug
)]
229 pub 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
236 pub fn all() -> [ParamSpace
; 3] {
237 [TypeSpace
, SelfSpace
, FnSpace
]
240 pub fn to_uint(self) -> usize {
248 pub fn from_uint(u
: usize) -> ParamSpace
{
253 _
=> panic
!("Invalid ParamSpace: {}", u
)
258 /// Vector of things sorted by param space. Used to keep
259 /// the set of things declared on the type, self, or method
261 #[derive(PartialEq, Eq, Clone, Hash, RustcEncodable, RustcDecodable)]
262 pub 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.
267 // Here is how the representation corresponds to the abstraction
268 // i.e. the "abstraction function" AF:
270 // AF(self) = (self.content[..self.type_limit],
271 // self.content[self.type_limit..self.self_limit],
272 // self.content[self.self_limit..])
278 /// The `split` function converts one `VecPerParamSpace` into this
279 /// `SeparateVecsPerParamSpace` structure.
280 pub struct SeparateVecsPerParamSpace
<T
> {
286 impl<T
: fmt
::Debug
> fmt
::Debug
for VecPerParamSpace
<T
> {
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
))
295 impl<T
> VecPerParamSpace
<T
> {
296 fn limits(&self, space
: ParamSpace
) -> (usize, usize) {
298 TypeSpace
=> (0, self.type_limit
),
299 SelfSpace
=> (self.type_limit
, self.self_limit
),
300 FnSpace
=> (self.self_limit
, self.content
.len()),
304 pub fn empty() -> VecPerParamSpace
<T
> {
312 /// `t` is the type space.
313 /// `s` is the self space.
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();
324 type_limit
: type_limit
,
325 self_limit
: self_limit
,
330 fn new_internal(content
: Vec
<T
>, type_limit
: usize, self_limit
: usize)
331 -> VecPerParamSpace
<T
>
334 type_limit
: type_limit
,
335 self_limit
: self_limit
,
340 /// Appends `value` to the vector associated with `space`.
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
);
347 TypeSpace
=> { self.type_limit += 1; self.self_limit += 1; }
348 SelfSpace
=> { self.self_limit += 1; }
351 self.content
.insert(limit
, value
);
354 /// Appends `values` to the vector associated with `space`.
356 /// Unlike the `extend` method in `Vec`, this should not be assumed
357 /// to be a cheap operation (even when amortized over many calls).
358 pub fn extend
<I
:Iterator
<Item
=T
>>(&mut self, space
: ParamSpace
, values
: I
) {
359 // This could be made more efficient, obviously.
361 self.push(space
, item
);
365 pub fn pop(&mut self, space
: ParamSpace
) -> Option
<T
> {
366 let (start
, limit
) = self.limits(space
);
371 TypeSpace
=> { self.type_limit -= 1; self.self_limit -= 1; }
372 SelfSpace
=> { self.self_limit -= 1; }
375 if self.content
.is_empty() {
378 Some(self.content
.remove(limit
- 1))
383 pub fn truncate(&mut self, space
: ParamSpace
, len
: usize) {
384 // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
385 while self.len(space
) > len
{
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);
398 pub fn get_self
<'a
>(&'a
self) -> Option
<&'a T
> {
399 let v
= self.get_slice(SelfSpace
);
400 assert
!(v
.len() <= 1);
401 if v
.is_empty() { None }
else { Some(&v[0]) }
404 pub fn len(&self, space
: ParamSpace
) -> usize {
405 self.get_slice(space
).len()
408 pub fn is_empty_in(&self, space
: ParamSpace
) -> bool
{
412 pub fn get_slice
<'a
>(&'a
self, space
: ParamSpace
) -> &'a
[T
] {
413 let (start
, limit
) = self.limits(space
);
414 &self.content
[start
.. limit
]
417 pub fn get_mut_slice
<'a
>(&'a
mut self, space
: ParamSpace
) -> &'a
mut [T
] {
418 let (start
, limit
) = self.limits(space
);
419 &mut self.content
[start
.. limit
]
422 pub fn opt_get
<'a
>(&'a
self,
426 let v
= self.get_slice(space
);
427 if index
< v
.len() { Some(&v[index]) }
else { None }
430 pub fn get
<'a
>(&'a
self, space
: ParamSpace
, index
: usize) -> &'a T
{
431 &self.get_slice(space
)[index
]
434 pub fn iter
<'a
>(&'a
self) -> Iter
<'a
,T
> {
438 pub fn into_iter(self) -> IntoIter
<T
> {
439 self.content
.into_iter()
442 pub fn iter_enumerated
<'a
>(&'a
self) -> EnumeratedItems
<'a
,T
> {
443 EnumeratedItems
::new(self)
446 pub fn as_slice(&self) -> &[T
] {
450 pub fn into_vec(self) -> Vec
<T
> {
454 pub fn all_vecs
<P
>(&self, mut pred
: P
) -> bool
where
455 P
: FnMut(&[T
]) -> bool
,
457 let spaces
= [TypeSpace
, SelfSpace
, FnSpace
];
458 spaces
.iter().all(|&space
| { pred(self.get_slice(space)) }
)
461 pub fn all
<P
>(&self, pred
: P
) -> bool
where P
: FnMut(&T
) -> bool
{
462 self.iter().all(pred
)
465 pub fn any
<P
>(&self, pred
: P
) -> bool
where P
: FnMut(&T
) -> bool
{
466 self.iter().any(pred
)
469 pub fn is_empty(&self) -> bool
{
470 self.all_vecs(|v
| v
.is_empty())
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
,
480 pub fn map_enumerated
<U
, P
>(&self, pred
: P
) -> VecPerParamSpace
<U
> where
481 P
: FnMut((ParamSpace
, usize, &T
)) -> U
,
483 let result
= self.iter_enumerated().map(pred
).collect();
484 VecPerParamSpace
::new_internal(result
,
489 pub fn split(self) -> SeparateVecsPerParamSpace
<T
> {
490 let VecPerParamSpace { type_limit, self_limit, content }
= self;
492 let mut content_iter
= content
.into_iter();
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()
501 pub fn with_slice(mut self, space
: ParamSpace
, slice
: &[T
])
502 -> VecPerParamSpace
<T
>
505 assert
!(self.is_empty_in(space
));
507 self.push(space
, t
.clone());
515 pub struct EnumeratedItems
<'a
,T
:'a
> {
516 vec
: &'a VecPerParamSpace
<T
>,
521 impl<'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();
528 fn adjust_space(&mut self) {
529 let spaces
= ParamSpace
::all();
531 self.space_index
< spaces
.len() &&
532 self.elem_index
>= self.vec
.len(spaces
[self.space_index
])
534 self.space_index
+= 1;
540 impl<'a
,T
> Iterator
for EnumeratedItems
<'a
,T
> {
541 type Item
= (ParamSpace
, usize, &'a T
);
543 fn next(&mut self) -> Option
<(ParamSpace
, usize, &'a T
)> {
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
);
550 self.elem_index
+= 1;
553 Some((space
, index
, item
))
559 fn size_hint(&self) -> (usize, Option
<usize>) {
560 let size
= self.vec
.as_slice().len();
565 impl<T
> IntoIterator
for VecPerParamSpace
<T
> {
567 type IntoIter
= IntoIter
<T
>;
569 fn into_iter(self) -> IntoIter
<T
> {
570 self.into_vec().into_iter()
574 impl<'a
,T
> IntoIterator
for &'a VecPerParamSpace
<T
> {
576 type IntoIter
= Iter
<'a
, T
>;
578 fn into_iter(self) -> Iter
<'a
, T
> {
579 self.as_slice().into_iter()
584 ///////////////////////////////////////////////////////////////////////////
585 // Public trait `Subst`
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).
591 pub trait Subst
<'tcx
> : Sized
{
592 fn subst(&self, tcx
: &ty
::ctxt
<'tcx
>, substs
: &Substs
<'tcx
>) -> Self {
593 self.subst_spanned(tcx
, substs
, None
)
596 fn subst_spanned(&self, tcx
: &ty
::ctxt
<'tcx
>,
597 substs
: &Substs
<'tcx
>,
602 impl<'tcx
, T
:TypeFoldable
<'tcx
>> Subst
<'tcx
> for T
{
603 fn subst_spanned(&self,
604 tcx
: &ty
::ctxt
<'tcx
>,
605 substs
: &Substs
<'tcx
>,
609 let mut folder
= SubstFolder
{ tcx
: tcx
,
614 region_binders_passed
: 0 };
615 (*self).fold_with(&mut folder
)
619 ///////////////////////////////////////////////////////////////////////////
620 // The actual substitution engine itself is a type folder.
622 struct SubstFolder
<'a
, 'tcx
: 'a
> {
623 tcx
: &'a ty
::ctxt
<'tcx
>,
624 substs
: &'a Substs
<'tcx
>,
626 // The location for which the substitution is performed, if available.
629 // The root type that is being substituted, if available.
630 root_ty
: Option
<Ty
<'tcx
>>,
632 // Depth of type stack
633 ty_stack_depth
: usize,
635 // Number of region binders we have passed through while doing the substitution
636 region_binders_passed
: u32,
639 impl<'a
, 'tcx
> TypeFolder
<'tcx
> for SubstFolder
<'a
, 'tcx
> {
640 fn tcx(&self) -> &ty
::ctxt
<'tcx
> { self.tcx }
642 fn enter_region_binder(&mut self) {
643 self.region_binders_passed
+= 1;
646 fn exit_region_binder(&mut self) {
647 self.region_binders_passed
-= 1;
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()`.
657 ty
::ReEarlyBound(data
) => {
658 match self.substs
.regions
{
659 ErasedRegions
=> ty
::ReStatic
,
660 NonerasedRegions(ref regions
) =>
661 match regions
.opt_get(data
.space
, data
.index
as usize) {
663 self.shift_region_through_binders(r
)
666 let span
= self.span
.unwrap_or(DUMMY_SP
);
667 self.tcx().sess
.span_bug(
669 &format
!("Type parameter out of range \
670 when substituting in region {} (root type={:?}) \
671 (space={:?}, index={})",
684 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
685 if !t
.needs_subst() {
689 // track the root type we were asked to substitute
690 let depth
= self.ty_stack_depth
;
692 self.root_ty
= Some(t
);
694 self.ty_stack_depth
+= 1;
696 let t1
= match t
.sty
{
698 self.ty_for_param(p
, t
)
701 t
.super_fold_with(self)
705 assert_eq
!(depth
+ 1, self.ty_stack_depth
);
706 self.ty_stack_depth
-= 1;
715 impl<'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.
718 let opt_ty
= self.substs
.types
.opt_get(p
.space
, p
.idx
as usize);
719 let ty
= match opt_ty
{
722 let span
= self.span
.unwrap_or(DUMMY_SP
);
723 self.tcx().sess
.span_bug(
725 &format
!("Type parameter `{:?}` ({:?}/{:?}/{}) out of range \
726 when substituting (root type={:?}) substs={:?}",
736 self.shift_regions_through_binders(ty
)
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:
744 /// type Func<A> = fn(A);
745 /// type MetaFunc = for<'a> fn(Func<&'a int>)
748 /// The type `MetaFunc`, when fully expanded, will be
750 /// for<'a> fn(fn(&'a int))
753 /// | | DebruijnIndex of 2
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.
763 /// As a second example, consider this twist:
766 /// type FuncTuple<A> = (A,fn(A));
767 /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>)
770 /// Here the final type will be:
772 /// for<'a> fn((&'a int, fn(&'a int)))
775 /// DebruijnIndex of 1 |
776 /// DebruijnIndex of 2
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
> {
782 debug
!("shift_regions(ty={:?}, region_binders_passed={:?}, has_escaping_regions={:?})",
783 ty
, self.region_binders_passed
, ty
.has_escaping_regions());
785 if self.region_binders_passed
== 0 || !ty
.has_escaping_regions() {
789 let result
= ty
::fold
::shift_regions(self.tcx(), self.region_binders_passed
, &ty
);
790 debug
!("shift_regions: shifted result = {:?}", result
);
795 fn shift_region_through_binders(&self, region
: ty
::Region
) -> ty
::Region
{
796 ty
::fold
::shift_region(region
, self.region_binders_passed
)