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))
560 impl<T> IntoIterator for VecPerParamSpace<T> {
562 type IntoIter = IntoIter<T>;
564 fn into_iter(self) -> IntoIter<T> {
565 self.into_vec().into_iter()
569 impl<'a,T> IntoIterator for &'a VecPerParamSpace<T> {
571 type IntoIter = Iter<'a, T>;
573 fn into_iter(self) -> Iter<'a, T> {
574 self.as_slice().into_iter()
579 ///////////////////////////////////////////////////////////////////////////
580 // Public trait `Subst`
582 // Just call `foo.subst(tcx, substs)` to perform a substitution across
583 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
584 // there is more information available (for better errors).
586 pub trait Subst<'tcx> : Sized {
587 fn subst(&self, tcx: &ty::ctxt<'tcx>, substs: &Substs<'tcx>) -> Self {
588 self.subst_spanned(tcx, substs, None)
591 fn subst_spanned(&self, tcx: &ty::ctxt<'tcx>,
592 substs: &Substs<'tcx>,
597 impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T {
598 fn subst_spanned(&self,
599 tcx: &ty::ctxt<'tcx>,
600 substs: &Substs<'tcx>,
604 let mut folder = SubstFolder { tcx: tcx,
609 region_binders_passed: 0 };
610 (*self).fold_with(&mut folder)
614 ///////////////////////////////////////////////////////////////////////////
615 // The actual substitution engine itself is a type folder.
617 struct SubstFolder<'a, 'tcx: 'a> {
618 tcx: &'a ty::ctxt<'tcx>,
619 substs: &'a Substs<'tcx>,
621 // The location for which the substitution is performed, if available.
624 // The root type that is being substituted, if available.
625 root_ty: Option<Ty<'tcx>>,
627 // Depth of type stack
628 ty_stack_depth: usize,
630 // Number of region binders we have passed through while doing the substitution
631 region_binders_passed: u32,
634 impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
635 fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
637 fn enter_region_binder(&mut self) {
638 self.region_binders_passed += 1;
641 fn exit_region_binder(&mut self) {
642 self.region_binders_passed -= 1;
645 fn fold_region(&mut self, r: ty::Region) -> ty::Region {
646 // Note: This routine only handles regions that are bound on
647 // type declarations and other outer declarations, not those
648 // bound in *fn types*. Region substitution of the bound
649 // regions that appear in a function signature is done using
650 // the specialized routine `ty::replace_late_regions()`.
652 ty::ReEarlyBound(data) => {
653 match self.substs.regions {
654 ErasedRegions => ty::ReStatic,
655 NonerasedRegions(ref regions) =>
656 match regions.opt_get(data.space, data.index as usize) {
658 self.shift_region_through_binders(r)
661 let span = self.span.unwrap_or(DUMMY_SP);
662 self.tcx().sess.span_bug(
664 &format!("Type parameter out of range \
665 when substituting in region {} (root type={:?}) \
666 (space={:?}, index={})",
679 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
680 if !t.needs_subst() {
684 // track the root type we were asked to substitute
685 let depth = self.ty_stack_depth;
687 self.root_ty = Some(t);
689 self.ty_stack_depth += 1;
691 let t1 = match t.sty {
693 self.ty_for_param(p, t)
696 t.super_fold_with(self)
700 assert_eq!(depth + 1, self.ty_stack_depth);
701 self.ty_stack_depth -= 1;
710 impl<'a,'tcx> SubstFolder<'a,'tcx> {
711 fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> {
712 // Look up the type in the substitutions. It really should be in there.
713 let opt_ty = self.substs.types.opt_get(p.space, p.idx as usize);
714 let ty = match opt_ty {
717 let span = self.span.unwrap_or(DUMMY_SP);
718 self.tcx().sess.span_bug(
720 &format!("Type parameter `{:?}` ({:?}/{:?}/{}) out of range \
721 when substituting (root type={:?}) substs={:?}",
731 self.shift_regions_through_binders(ty)
734 /// It is sometimes necessary to adjust the debruijn indices during substitution. This occurs
735 /// when we are substituting a type with escaping regions into a context where we have passed
736 /// through region binders. That's quite a mouthful. Let's see an example:
739 /// type Func<A> = fn(A);
740 /// type MetaFunc = for<'a> fn(Func<&'a int>)
743 /// The type `MetaFunc`, when fully expanded, will be
745 /// for<'a> fn(fn(&'a int))
748 /// | | DebruijnIndex of 2
751 /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
752 /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
753 /// over the inner binder (remember that we count Debruijn indices from 1). However, in the
754 /// definition of `MetaFunc`, the binder is not visible, so the type `&'a int` will have a
755 /// debruijn index of 1. It's only during the substitution that we can see we must increase the
756 /// depth by 1 to account for the binder that we passed through.
758 /// As a second example, consider this twist:
761 /// type FuncTuple<A> = (A,fn(A));
762 /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>)
765 /// Here the final type will be:
767 /// for<'a> fn((&'a int, fn(&'a int)))
770 /// DebruijnIndex of 1 |
771 /// DebruijnIndex of 2
773 /// As indicated in the diagram, here the same type `&'a int` is substituted once, but in the
774 /// first case we do not increase the Debruijn index and in the second case we do. The reason
775 /// is that only in the second case have we passed through a fn binder.
776 fn shift_regions_through_binders(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
777 debug!("shift_regions(ty={:?}, region_binders_passed={:?}, has_escaping_regions={:?})",
778 ty, self.region_binders_passed, ty.has_escaping_regions());
780 if self.region_binders_passed == 0 || !ty.has_escaping_regions() {
784 let result = ty::fold::shift_regions(self.tcx(), self.region_binders_passed, &ty);
785 debug!("shift_regions: shifted result = {:?}", result);
790 fn shift_region_through_binders(&self, region: ty::Region) -> ty::Region {
791 ty::fold::shift_region(region, self.region_binders_passed)