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