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