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.
15 use middle::ty_fold::{TypeFoldable, TypeFolder};
16 use util::ppaux::Repr;
21 use std::slice::{Items, MutItems};
23 use syntax::codemap::{Span, DUMMY_SP};
25 ///////////////////////////////////////////////////////////////////////////
26 // HomogeneousTuple3 trait
28 // This could be moved into standard library at some point.
30 trait HomogeneousTuple3<T> {
31 fn len(&self) -> uint;
32 fn as_slice<'a>(&'a self) -> &'a [T];
33 fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T];
34 fn iter<'a>(&'a self) -> Items<'a, T>;
35 fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T>;
36 fn get<'a>(&'a self, index: uint) -> Option<&'a T>;
37 fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T>;
40 impl<T> HomogeneousTuple3<T> for (T, T, T) {
41 fn len(&self) -> uint {
45 fn as_slice<'a>(&'a self) -> &'a [T] {
47 let ptr: *const T = mem::transmute(self);
48 let slice = raw::Slice { data: ptr, len: 3 };
53 fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
55 let ptr: *const T = mem::transmute(self);
56 let slice = raw::Slice { data: ptr, len: 3 };
61 fn iter<'a>(&'a self) -> Items<'a, T> {
62 let slice: &'a [T] = self.as_slice();
66 fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
67 self.as_mut_slice().mut_iter()
70 fn get<'a>(&'a self, index: uint) -> Option<&'a T> {
71 self.as_slice().get(index)
74 fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T> {
75 Some(&mut self.as_mut_slice()[index]) // wrong: fallible
79 ///////////////////////////////////////////////////////////////////////////
82 * A substitution mapping type/region parameters to new values. We
83 * identify each in-scope parameter by an *index* and a *parameter
84 * space* (which indices where the parameter is defined; see
87 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
89 pub types: VecPerParamSpace<ty::t>,
90 pub regions: RegionSubsts,
94 * Represents the values to use when substituting lifetime parameters.
95 * If the value is `ErasedRegions`, then this subst is occurring during
96 * trans, and all region parameters will be replaced with `ty::ReStatic`. */
97 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
98 pub enum RegionSubsts {
100 NonerasedRegions(VecPerParamSpace<ty::Region>)
104 pub fn new(t: VecPerParamSpace<ty::t>,
105 r: VecPerParamSpace<ty::Region>)
108 Substs { types: t, regions: NonerasedRegions(r) }
111 pub fn new_type(t: Vec<ty::t>,
115 Substs::new(VecPerParamSpace::new(t, Vec::new(), Vec::new()),
116 VecPerParamSpace::new(r, Vec::new(), Vec::new()))
119 pub fn new_trait(t: Vec<ty::t>,
124 Substs::new(VecPerParamSpace::new(t, vec!(s), Vec::new()),
125 VecPerParamSpace::new(r, Vec::new(), Vec::new()))
128 pub fn erased(t: VecPerParamSpace<ty::t>) -> Substs
130 Substs { types: t, regions: ErasedRegions }
133 pub fn empty() -> Substs {
135 types: VecPerParamSpace::empty(),
136 regions: NonerasedRegions(VecPerParamSpace::empty()),
140 pub fn trans_empty() -> Substs {
142 types: VecPerParamSpace::empty(),
143 regions: ErasedRegions
147 pub fn is_noop(&self) -> bool {
148 let regions_is_noop = match self.regions {
149 ErasedRegions => false, // may be used to canonicalize
150 NonerasedRegions(ref regions) => regions.is_empty(),
153 regions_is_noop && self.types.is_empty()
156 pub fn self_ty(&self) -> Option<ty::t> {
157 self.types.get_self().map(|&t| t)
160 pub fn with_self_ty(&self, self_ty: ty::t) -> Substs {
161 assert!(self.self_ty().is_none());
162 let mut s = (*self).clone();
163 s.types.push(SelfSpace, self_ty);
167 pub fn erase_regions(self) -> Substs {
168 let Substs { types: types, regions: _ } = self;
169 Substs { types: types, regions: ErasedRegions }
172 pub fn regions<'a>(&'a self) -> &'a VecPerParamSpace<ty::Region> {
174 * Since ErasedRegions are only to be used in trans, most of
175 * the compiler can use this method to easily access the set
176 * of region substitutions.
180 ErasedRegions => fail!("Erased regions only expected in trans"),
181 NonerasedRegions(ref r) => r
185 pub fn mut_regions<'a>(&'a mut self) -> &'a mut VecPerParamSpace<ty::Region> {
187 * Since ErasedRegions are only to be used in trans, most of
188 * the compiler can use this method to easily access the set
189 * of region substitutions.
193 ErasedRegions => fail!("Erased regions only expected in trans"),
194 NonerasedRegions(ref mut r) => r
198 pub fn with_method_from(self, substs: &Substs) -> Substs {
199 self.with_method(Vec::from_slice(substs.types.get_slice(FnSpace)),
200 Vec::from_slice(substs.regions().get_slice(FnSpace)))
203 pub fn with_method(self,
205 m_regions: Vec<ty::Region>)
208 let Substs { types, regions } = self;
209 let types = types.with_vec(FnSpace, m_types);
210 let regions = regions.map(m_regions,
211 |r, m_regions| r.with_vec(FnSpace, m_regions));
212 Substs { types: types, regions: regions }
219 op: |VecPerParamSpace<ty::Region>, A| -> VecPerParamSpace<ty::Region>)
222 ErasedRegions => ErasedRegions,
223 NonerasedRegions(r) => NonerasedRegions(op(r, a))
228 ///////////////////////////////////////////////////////////////////////////
231 #[deriving(PartialOrd, Ord, PartialEq, Eq,
232 Clone, Hash, Encodable, Decodable, Show)]
233 pub enum ParamSpace {
234 TypeSpace, // Type parameters attached to a type definition, trait, or impl
235 SelfSpace, // Self parameter on a trait
236 FnSpace, // Type parameters attached to a method or fn
240 pub fn all() -> [ParamSpace, ..3] {
241 [TypeSpace, SelfSpace, FnSpace]
244 pub fn to_uint(self) -> uint {
252 pub fn from_uint(u: uint) -> ParamSpace {
257 _ => fail!("Invalid ParamSpace: {}", u)
263 * Vector of things sorted by param space. Used to keep
264 * the set of things declared on the type, self, or method
267 #[deriving(PartialEq, Eq, Clone, Hash, Encodable, Decodable)]
268 pub struct VecPerParamSpace<T> {
269 // This was originally represented as a tuple with one Vec<T> for
270 // each variant of ParamSpace, and that remains the abstraction
271 // that it provides to its clients.
273 // Here is how the representation corresponds to the abstraction
274 // i.e. the "abstraction function" AF:
276 // AF(self) = (self.content.slice_to(self.type_limit),
277 // self.content.slice(self.type_limit, self.self_limit),
278 // self.content.slice_from(self.self_limit))
284 impl<T:fmt::Show> fmt::Show for VecPerParamSpace<T> {
285 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
286 try!(write!(fmt, "VecPerParamSpace {{"));
287 for space in ParamSpace::all().iter() {
288 try!(write!(fmt, "{}: {}, ", *space, self.get_slice(*space)));
290 try!(write!(fmt, "}}"));
295 impl<T:Clone> VecPerParamSpace<T> {
296 pub fn push_all(&mut self, space: ParamSpace, values: &[T]) {
297 // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
298 for t in values.iter() {
299 self.push(space, t.clone());
304 impl<T> VecPerParamSpace<T> {
305 fn limits(&self, space: ParamSpace) -> (uint, uint) {
307 TypeSpace => (0, self.type_limit),
308 SelfSpace => (self.type_limit, self.self_limit),
309 FnSpace => (self.self_limit, self.content.len()),
313 pub fn empty() -> VecPerParamSpace<T> {
321 pub fn params_from_type(types: Vec<T>) -> VecPerParamSpace<T> {
322 VecPerParamSpace::empty().with_vec(TypeSpace, types)
325 /// `t` is the type space.
326 /// `s` is the self space.
327 /// `f` is the fn space.
328 pub fn new(t: Vec<T>, s: Vec<T>, f: Vec<T>) -> VecPerParamSpace<T> {
329 let type_limit = t.len();
330 let self_limit = t.len() + s.len();
332 content.push_all_move(s);
333 content.push_all_move(f);
335 type_limit: type_limit,
336 self_limit: self_limit,
341 fn new_internal(content: Vec<T>, type_limit: uint, self_limit: uint)
342 -> VecPerParamSpace<T>
345 type_limit: type_limit,
346 self_limit: self_limit,
351 pub fn sort(t: Vec<T>, space: |&T| -> ParamSpace) -> VecPerParamSpace<T> {
352 let mut result = VecPerParamSpace::empty();
353 for t in t.move_iter() {
354 result.push(space(&t), t);
359 /// Appends `value` to the vector associated with `space`.
361 /// Unlike the `push` method in `Vec`, this should not be assumed
362 /// to be a cheap operation (even when amortized over many calls).
363 pub fn push(&mut self, space: ParamSpace, value: T) {
364 let (_, limit) = self.limits(space);
366 TypeSpace => { self.type_limit += 1; self.self_limit += 1; }
367 SelfSpace => { self.self_limit += 1; }
370 self.content.insert(limit, value);
373 pub fn pop(&mut self, space: ParamSpace) -> Option<T> {
374 let (start, limit) = self.limits(space);
379 TypeSpace => { self.type_limit -= 1; self.self_limit -= 1; }
380 SelfSpace => { self.self_limit -= 1; }
383 self.content.remove(limit - 1)
387 pub fn truncate(&mut self, space: ParamSpace, len: uint) {
388 // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
389 while self.len(space) > len {
394 pub fn replace(&mut self, space: ParamSpace, elems: Vec<T>) {
395 // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
396 self.truncate(space, 0);
397 for t in elems.move_iter() {
402 pub fn get_self<'a>(&'a self) -> Option<&'a T> {
403 let v = self.get_slice(SelfSpace);
404 assert!(v.len() <= 1);
405 if v.len() == 0 { None } else { Some(&v[0]) }
408 pub fn len(&self, space: ParamSpace) -> uint {
409 self.get_slice(space).len()
412 pub fn is_empty_in(&self, space: ParamSpace) -> bool {
416 pub fn get_slice<'a>(&'a self, space: ParamSpace) -> &'a [T] {
417 let (start, limit) = self.limits(space);
418 self.content.slice(start, limit)
421 pub fn get_mut_slice<'a>(&'a mut self, space: ParamSpace) -> &'a mut [T] {
422 let (start, limit) = self.limits(space);
423 self.content.mut_slice(start, limit)
426 pub fn opt_get<'a>(&'a self,
430 let v = self.get_slice(space);
431 if index < v.len() { Some(&v[index]) } else { None }
434 pub fn get<'a>(&'a self, space: ParamSpace, index: uint) -> &'a T {
435 &self.get_slice(space)[index]
438 pub fn get_mut<'a>(&'a mut self,
440 index: uint) -> &'a mut T {
441 &mut self.get_mut_slice(space)[index]
444 pub fn iter<'a>(&'a self) -> Items<'a,T> {
448 pub fn all_vecs(&self, pred: |&[T]| -> bool) -> bool {
449 let spaces = [TypeSpace, SelfSpace, FnSpace];
450 spaces.iter().all(|&space| { pred(self.get_slice(space)) })
453 pub fn all(&self, pred: |&T| -> bool) -> bool {
454 self.iter().all(pred)
457 pub fn any(&self, pred: |&T| -> bool) -> bool {
458 self.iter().any(pred)
461 pub fn is_empty(&self) -> bool {
462 self.all_vecs(|v| v.is_empty())
465 pub fn map<U>(&self, pred: |&T| -> U) -> VecPerParamSpace<U> {
466 let result = self.iter().map(pred).collect();
467 VecPerParamSpace::new_internal(result,
472 pub fn map_move<U>(self, pred: |T| -> U) -> VecPerParamSpace<U> {
473 let (t, s, f) = self.split();
474 VecPerParamSpace::new(t.move_iter().map(|p| pred(p)).collect(),
475 s.move_iter().map(|p| pred(p)).collect(),
476 f.move_iter().map(|p| pred(p)).collect())
479 pub fn map_rev<U>(&self, pred: |&T| -> U) -> VecPerParamSpace<U> {
481 * Executes the map but in reverse order. For hacky reasons, we rely
484 * FIXME(#5527) -- order of eval becomes irrelevant with newer
485 * trait reform, which features an idempotent algorithm that
486 * can be run to a fixed point
489 let mut fns: Vec<U> = self.get_slice(FnSpace).iter().rev().map(|p| pred(p)).collect();
491 // NB: Calling foo.rev().map().rev() causes the calls to map
492 // to occur in the wrong order. This was somewhat surprising
493 // to me, though it makes total sense.
496 let mut selfs: Vec<U> = self.get_slice(SelfSpace).iter().rev().map(|p| pred(p)).collect();
498 let mut tys: Vec<U> = self.get_slice(TypeSpace).iter().rev().map(|p| pred(p)).collect();
500 VecPerParamSpace::new(tys, selfs, fns)
503 pub fn split(self) -> (Vec<T>, Vec<T>, Vec<T>) {
504 // FIXME (#15418): this does two traversals when in principle
505 // one would suffice. i.e. change to use `move_iter`.
506 let VecPerParamSpace { type_limit, self_limit, content } = self;
508 let (prefix, fn_vec) = content.partition(|_| {
509 let on_left = i < self_limit;
515 let (type_vec, self_vec) = prefix.partition(|_| {
516 let on_left = i < type_limit;
521 (type_vec, self_vec, fn_vec)
524 pub fn with_vec(mut self, space: ParamSpace, vec: Vec<T>)
525 -> VecPerParamSpace<T>
527 assert!(self.is_empty_in(space));
528 self.replace(space, vec);
533 ///////////////////////////////////////////////////////////////////////////
534 // Public trait `Subst`
536 // Just call `foo.subst(tcx, substs)` to perform a substitution across
537 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
538 // there is more information available (for better errors).
541 fn subst(&self, tcx: &ty::ctxt, substs: &Substs) -> Self {
542 self.subst_spanned(tcx, substs, None)
545 fn subst_spanned(&self, tcx: &ty::ctxt,
551 impl<T:TypeFoldable> Subst for T {
552 fn subst_spanned(&self,
558 let mut folder = SubstFolder { tcx: tcx,
563 (*self).fold_with(&mut folder)
567 ///////////////////////////////////////////////////////////////////////////
568 // The actual substitution engine itself is a type folder.
570 struct SubstFolder<'a, 'tcx: 'a> {
571 tcx: &'a ty::ctxt<'tcx>,
574 // The location for which the substitution is performed, if available.
577 // The root type that is being substituted, if available.
578 root_ty: Option<ty::t>,
580 // Depth of type stack
581 ty_stack_depth: uint,
584 impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
585 fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
587 fn fold_region(&mut self, r: ty::Region) -> ty::Region {
588 // Note: This routine only handles regions that are bound on
589 // type declarations and other outer declarations, not those
590 // bound in *fn types*. Region substitution of the bound
591 // regions that appear in a function signature is done using
592 // the specialized routine
593 // `middle::typeck::check::regionmanip::replace_late_regions_in_fn_sig()`.
595 ty::ReEarlyBound(_, space, i, region_name) => {
596 match self.substs.regions {
597 ErasedRegions => ty::ReStatic,
598 NonerasedRegions(ref regions) =>
599 match regions.opt_get(space, i) {
602 let span = self.span.unwrap_or(DUMMY_SP);
603 self.tcx().sess.span_bug(
605 format!("Type parameter out of range \
606 when substituting in region {} (root type={}) \
607 (space={}, index={})",
608 region_name.as_str(),
609 self.root_ty.repr(self.tcx()),
610 space, i).as_slice());
619 fn fold_ty(&mut self, t: ty::t) -> ty::t {
620 if !ty::type_needs_subst(t) {
624 // track the root type we were asked to substitute
625 let depth = self.ty_stack_depth;
627 self.root_ty = Some(t);
629 self.ty_stack_depth += 1;
631 let t1 = match ty::get(t).sty {
633 check(self, p, t, self.substs.types.opt_get(p.space, p.idx))
636 ty_fold::super_fold_ty(self, t)
640 assert_eq!(depth + 1, self.ty_stack_depth);
641 self.ty_stack_depth -= 1;
648 fn check(this: &SubstFolder,
651 opt_ty: Option<&ty::t>)
656 let span = this.span.unwrap_or(DUMMY_SP);
657 this.tcx().sess.span_bug(
659 format!("Type parameter `{}` ({}) out of range \
660 when substituting (root type={})",
662 source_ty.repr(this.tcx()),
663 this.root_ty.repr(this.tcx())).as_slice());