]>
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 | |
9cc50fc6 | 16 | use middle::cstore; |
7453a54e | 17 | use middle::def_id::DefId; |
9cc50fc6 | 18 | use middle::ty::{self, Ty}; |
e9174d1e | 19 | use middle::ty::fold::{TypeFoldable, TypeFolder}; |
970d7e83 | 20 | |
9cc50fc6 | 21 | use serialize::{Encodable, Encoder, Decodable, Decoder}; |
1a4d82fc | 22 | use std::fmt; |
85aaf69f | 23 | use std::iter::IntoIterator; |
1a4d82fc | 24 | use std::slice::Iter; |
85aaf69f | 25 | use std::vec::{Vec, IntoIter}; |
1a4d82fc JJ |
26 | use syntax::codemap::{Span, DUMMY_SP}; |
27 | ||
970d7e83 | 28 | /////////////////////////////////////////////////////////////////////////// |
970d7e83 | 29 | |
1a4d82fc JJ |
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 | |
33 | /// `ParamSpace`). | |
62682a34 | 34 | #[derive(Clone, PartialEq, Eq, Hash)] |
1a4d82fc JJ |
35 | pub struct Substs<'tcx> { |
36 | pub types: VecPerParamSpace<Ty<'tcx>>, | |
37 | pub regions: RegionSubsts, | |
970d7e83 LB |
38 | } |
39 | ||
1a4d82fc JJ |
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`. | |
62682a34 | 43 | #[derive(Clone, PartialEq, Eq, Hash)] |
1a4d82fc JJ |
44 | pub enum RegionSubsts { |
45 | ErasedRegions, | |
46 | NonerasedRegions(VecPerParamSpace<ty::Region>) | |
970d7e83 LB |
47 | } |
48 | ||
1a4d82fc JJ |
49 | impl<'tcx> Substs<'tcx> { |
50 | pub fn new(t: VecPerParamSpace<Ty<'tcx>>, | |
51 | r: VecPerParamSpace<ty::Region>) | |
52 | -> Substs<'tcx> | |
53 | { | |
54 | Substs { types: t, regions: NonerasedRegions(r) } | |
55 | } | |
56 | ||
57 | pub fn new_type(t: Vec<Ty<'tcx>>, | |
58 | r: Vec<ty::Region>) | |
59 | -> Substs<'tcx> | |
60 | { | |
61 | Substs::new(VecPerParamSpace::new(t, Vec::new(), Vec::new()), | |
62 | VecPerParamSpace::new(r, Vec::new(), Vec::new())) | |
63 | } | |
64 | ||
65 | pub fn new_trait(t: Vec<Ty<'tcx>>, | |
66 | r: Vec<ty::Region>, | |
67 | s: Ty<'tcx>) | |
68 | -> Substs<'tcx> | |
69 | { | |
70 | Substs::new(VecPerParamSpace::new(t, vec!(s), Vec::new()), | |
71 | VecPerParamSpace::new(r, Vec::new(), Vec::new())) | |
72 | } | |
73 | ||
74 | pub fn erased(t: VecPerParamSpace<Ty<'tcx>>) -> Substs<'tcx> | |
75 | { | |
76 | Substs { types: t, regions: ErasedRegions } | |
77 | } | |
78 | ||
79 | pub fn empty() -> Substs<'tcx> { | |
80 | Substs { | |
81 | types: VecPerParamSpace::empty(), | |
82 | regions: NonerasedRegions(VecPerParamSpace::empty()), | |
970d7e83 LB |
83 | } |
84 | } | |
970d7e83 | 85 | |
1a4d82fc JJ |
86 | pub fn trans_empty() -> Substs<'tcx> { |
87 | Substs { | |
88 | types: VecPerParamSpace::empty(), | |
89 | regions: ErasedRegions | |
970d7e83 | 90 | } |
1a4d82fc | 91 | } |
970d7e83 | 92 | |
1a4d82fc JJ |
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(), | |
97 | }; | |
98 | ||
99 | regions_is_noop && self.types.is_empty() | |
100 | } | |
101 | ||
102 | pub fn type_for_def(&self, ty_param_def: &ty::TypeParameterDef) -> Ty<'tcx> { | |
c34b1796 | 103 | *self.types.get(ty_param_def.space, ty_param_def.index as usize) |
1a4d82fc JJ |
104 | } |
105 | ||
1a4d82fc | 106 | pub fn self_ty(&self) -> Option<Ty<'tcx>> { |
85aaf69f | 107 | self.types.get_self().cloned() |
1a4d82fc | 108 | } |
970d7e83 | 109 | |
1a4d82fc JJ |
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); | |
114 | s | |
115 | } | |
116 | ||
117 | pub fn erase_regions(self) -> Substs<'tcx> { | |
118 | let Substs { types, regions: _ } = self; | |
119 | Substs { types: types, regions: ErasedRegions } | |
120 | } | |
121 | ||
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> { | |
125 | match self.regions { | |
126 | ErasedRegions => panic!("Erased regions only expected in trans"), | |
127 | NonerasedRegions(ref r) => r | |
128 | } | |
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 mut_regions<'a>(&'a mut self) -> &'a mut VecPerParamSpace<ty::Region> { | |
134 | match self.regions { | |
135 | ErasedRegions => panic!("Erased regions only expected in trans"), | |
136 | NonerasedRegions(ref mut r) => r | |
137 | } | |
138 | } | |
139 | ||
140 | pub fn with_method(self, | |
141 | m_types: Vec<Ty<'tcx>>, | |
142 | m_regions: Vec<ty::Region>) | |
143 | -> Substs<'tcx> | |
144 | { | |
145 | let Substs { types, regions } = self; | |
7453a54e SL |
146 | let types = types.with_slice(FnSpace, &m_types); |
147 | let regions = regions.map(|r| r.with_slice(FnSpace, &m_regions)); | |
c1a9b12d SL |
148 | Substs { types: types, regions: regions } |
149 | } | |
150 | ||
7453a54e SL |
151 | pub fn with_method_from(self, |
152 | meth_substs: &Substs<'tcx>) | |
153 | -> Substs<'tcx> | |
154 | { | |
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)) | |
159 | }); | |
160 | Substs { types: types, regions: regions } | |
161 | } | |
162 | ||
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(); | |
c1a9b12d SL |
167 | types.truncate(FnSpace, 0); |
168 | let regions = regions.map(|mut r| { r.truncate(FnSpace, 0); r }); | |
7453a54e SL |
169 | |
170 | ty::TraitRef { | |
171 | def_id: trait_id, | |
172 | substs: tcx.mk_substs(Substs { types: types, regions: regions }) | |
173 | } | |
970d7e83 LB |
174 | } |
175 | } | |
176 | ||
9cc50fc6 SL |
177 | impl<'tcx> Encodable for Substs<'tcx> { |
178 | ||
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); | |
182 | Ok(()) | |
183 | }) | |
184 | } | |
185 | } | |
186 | ||
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)) | |
191 | }) | |
192 | } | |
193 | } | |
194 | ||
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) | |
200 | }); | |
201 | ||
202 | Ok(substs) | |
203 | } | |
204 | } | |
205 | ||
1a4d82fc | 206 | impl RegionSubsts { |
c1a9b12d SL |
207 | pub fn map<F>(self, op: F) -> RegionSubsts where |
208 | F: FnOnce(VecPerParamSpace<ty::Region>) -> VecPerParamSpace<ty::Region>, | |
1a4d82fc | 209 | { |
970d7e83 | 210 | match self { |
1a4d82fc | 211 | ErasedRegions => ErasedRegions, |
c1a9b12d | 212 | NonerasedRegions(r) => NonerasedRegions(op(r)) |
970d7e83 LB |
213 | } |
214 | } | |
970d7e83 | 215 | |
1a4d82fc JJ |
216 | pub fn is_erased(&self) -> bool { |
217 | match *self { | |
218 | ErasedRegions => true, | |
219 | NonerasedRegions(_) => false, | |
220 | } | |
970d7e83 LB |
221 | } |
222 | } | |
223 | ||
1a4d82fc JJ |
224 | /////////////////////////////////////////////////////////////////////////// |
225 | // ParamSpace | |
226 | ||
227 | #[derive(PartialOrd, Ord, PartialEq, Eq, Copy, | |
85aaf69f | 228 | Clone, Hash, RustcEncodable, RustcDecodable, Debug)] |
1a4d82fc JJ |
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 | |
233 | } | |
234 | ||
235 | impl ParamSpace { | |
236 | pub fn all() -> [ParamSpace; 3] { | |
237 | [TypeSpace, SelfSpace, FnSpace] | |
238 | } | |
239 | ||
c34b1796 | 240 | pub fn to_uint(self) -> usize { |
1a4d82fc JJ |
241 | match self { |
242 | TypeSpace => 0, | |
243 | SelfSpace => 1, | |
244 | FnSpace => 2, | |
970d7e83 LB |
245 | } |
246 | } | |
970d7e83 | 247 | |
c34b1796 | 248 | pub fn from_uint(u: usize) -> ParamSpace { |
1a4d82fc JJ |
249 | match u { |
250 | 0 => TypeSpace, | |
251 | 1 => SelfSpace, | |
252 | 2 => FnSpace, | |
253 | _ => panic!("Invalid ParamSpace: {}", u) | |
970d7e83 LB |
254 | } |
255 | } | |
256 | } | |
257 | ||
1a4d82fc JJ |
258 | /// Vector of things sorted by param space. Used to keep |
259 | /// the set of things declared on the type, self, or method | |
260 | /// distinct. | |
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. | |
266 | // | |
267 | // Here is how the representation corresponds to the abstraction | |
268 | // i.e. the "abstraction function" AF: | |
269 | // | |
270 | // AF(self) = (self.content[..self.type_limit], | |
271 | // self.content[self.type_limit..self.self_limit], | |
272 | // self.content[self.self_limit..]) | |
c34b1796 AL |
273 | type_limit: usize, |
274 | self_limit: usize, | |
1a4d82fc JJ |
275 | content: Vec<T>, |
276 | } | |
277 | ||
278 | /// The `split` function converts one `VecPerParamSpace` into this | |
279 | /// `SeparateVecsPerParamSpace` structure. | |
280 | pub struct SeparateVecsPerParamSpace<T> { | |
281 | pub types: Vec<T>, | |
282 | pub selfs: Vec<T>, | |
283 | pub fns: Vec<T>, | |
284 | } | |
285 | ||
85aaf69f | 286 | impl<T: fmt::Debug> fmt::Debug for VecPerParamSpace<T> { |
62682a34 SL |
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)) | |
970d7e83 LB |
292 | } |
293 | } | |
294 | ||
1a4d82fc | 295 | impl<T> VecPerParamSpace<T> { |
c34b1796 | 296 | fn limits(&self, space: ParamSpace) -> (usize, usize) { |
1a4d82fc JJ |
297 | match space { |
298 | TypeSpace => (0, self.type_limit), | |
299 | SelfSpace => (self.type_limit, self.self_limit), | |
300 | FnSpace => (self.self_limit, self.content.len()), | |
301 | } | |
302 | } | |
303 | ||
304 | pub fn empty() -> VecPerParamSpace<T> { | |
305 | VecPerParamSpace { | |
306 | type_limit: 0, | |
307 | self_limit: 0, | |
308 | content: Vec::new() | |
309 | } | |
310 | } | |
311 | ||
1a4d82fc JJ |
312 | /// `t` is the type space. |
313 | /// `s` is the self space. | |
1a4d82fc JJ |
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(); | |
318 | ||
319 | let mut content = t; | |
62682a34 SL |
320 | content.extend(s); |
321 | content.extend(f); | |
1a4d82fc JJ |
322 | |
323 | VecPerParamSpace { | |
324 | type_limit: type_limit, | |
325 | self_limit: self_limit, | |
326 | content: content, | |
327 | } | |
328 | } | |
329 | ||
c34b1796 | 330 | fn new_internal(content: Vec<T>, type_limit: usize, self_limit: usize) |
1a4d82fc JJ |
331 | -> VecPerParamSpace<T> |
332 | { | |
333 | VecPerParamSpace { | |
334 | type_limit: type_limit, | |
335 | self_limit: self_limit, | |
336 | content: content, | |
337 | } | |
338 | } | |
339 | ||
340 | /// Appends `value` to the vector associated with `space`. | |
341 | /// | |
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); | |
346 | match space { | |
347 | TypeSpace => { self.type_limit += 1; self.self_limit += 1; } | |
348 | SelfSpace => { self.self_limit += 1; } | |
349 | FnSpace => { } | |
350 | } | |
351 | self.content.insert(limit, value); | |
352 | } | |
353 | ||
354 | /// Appends `values` to the vector associated with `space`. | |
355 | /// | |
356 | /// Unlike the `extend` method in `Vec`, this should not be assumed | |
357 | /// to be a cheap operation (even when amortized over many calls). | |
85aaf69f | 358 | pub fn extend<I:Iterator<Item=T>>(&mut self, space: ParamSpace, values: I) { |
1a4d82fc JJ |
359 | // This could be made more efficient, obviously. |
360 | for item in values { | |
361 | self.push(space, item); | |
362 | } | |
363 | } | |
364 | ||
365 | pub fn pop(&mut self, space: ParamSpace) -> Option<T> { | |
366 | let (start, limit) = self.limits(space); | |
367 | if start == limit { | |
368 | None | |
369 | } else { | |
370 | match space { | |
371 | TypeSpace => { self.type_limit -= 1; self.self_limit -= 1; } | |
372 | SelfSpace => { self.self_limit -= 1; } | |
373 | FnSpace => {} | |
374 | } | |
375 | if self.content.is_empty() { | |
376 | None | |
377 | } else { | |
378 | Some(self.content.remove(limit - 1)) | |
379 | } | |
380 | } | |
381 | } | |
382 | ||
c34b1796 | 383 | pub fn truncate(&mut self, space: ParamSpace, len: usize) { |
1a4d82fc JJ |
384 | // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n). |
385 | while self.len(space) > len { | |
386 | self.pop(space); | |
387 | } | |
388 | } | |
389 | ||
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); | |
85aaf69f | 393 | for t in elems { |
1a4d82fc JJ |
394 | self.push(space, t); |
395 | } | |
396 | } | |
397 | ||
398 | pub fn get_self<'a>(&'a self) -> Option<&'a T> { | |
399 | let v = self.get_slice(SelfSpace); | |
400 | assert!(v.len() <= 1); | |
9346a6ac | 401 | if v.is_empty() { None } else { Some(&v[0]) } |
1a4d82fc JJ |
402 | } |
403 | ||
c34b1796 | 404 | pub fn len(&self, space: ParamSpace) -> usize { |
1a4d82fc JJ |
405 | self.get_slice(space).len() |
406 | } | |
407 | ||
408 | pub fn is_empty_in(&self, space: ParamSpace) -> bool { | |
409 | self.len(space) == 0 | |
410 | } | |
411 | ||
412 | pub fn get_slice<'a>(&'a self, space: ParamSpace) -> &'a [T] { | |
413 | let (start, limit) = self.limits(space); | |
85aaf69f | 414 | &self.content[start.. limit] |
1a4d82fc JJ |
415 | } |
416 | ||
417 | pub fn get_mut_slice<'a>(&'a mut self, space: ParamSpace) -> &'a mut [T] { | |
418 | let (start, limit) = self.limits(space); | |
85aaf69f | 419 | &mut self.content[start.. limit] |
1a4d82fc JJ |
420 | } |
421 | ||
422 | pub fn opt_get<'a>(&'a self, | |
423 | space: ParamSpace, | |
c34b1796 | 424 | index: usize) |
1a4d82fc JJ |
425 | -> Option<&'a T> { |
426 | let v = self.get_slice(space); | |
427 | if index < v.len() { Some(&v[index]) } else { None } | |
428 | } | |
429 | ||
c34b1796 | 430 | pub fn get<'a>(&'a self, space: ParamSpace, index: usize) -> &'a T { |
1a4d82fc JJ |
431 | &self.get_slice(space)[index] |
432 | } | |
433 | ||
434 | pub fn iter<'a>(&'a self) -> Iter<'a,T> { | |
435 | self.content.iter() | |
436 | } | |
437 | ||
85aaf69f SL |
438 | pub fn into_iter(self) -> IntoIter<T> { |
439 | self.content.into_iter() | |
440 | } | |
441 | ||
1a4d82fc JJ |
442 | pub fn iter_enumerated<'a>(&'a self) -> EnumeratedItems<'a,T> { |
443 | EnumeratedItems::new(self) | |
444 | } | |
445 | ||
446 | pub fn as_slice(&self) -> &[T] { | |
85aaf69f | 447 | &self.content |
1a4d82fc JJ |
448 | } |
449 | ||
450 | pub fn into_vec(self) -> Vec<T> { | |
451 | self.content | |
452 | } | |
453 | ||
454 | pub fn all_vecs<P>(&self, mut pred: P) -> bool where | |
455 | P: FnMut(&[T]) -> bool, | |
456 | { | |
457 | let spaces = [TypeSpace, SelfSpace, FnSpace]; | |
458 | spaces.iter().all(|&space| { pred(self.get_slice(space)) }) | |
459 | } | |
460 | ||
461 | pub fn all<P>(&self, pred: P) -> bool where P: FnMut(&T) -> bool { | |
462 | self.iter().all(pred) | |
463 | } | |
464 | ||
465 | pub fn any<P>(&self, pred: P) -> bool where P: FnMut(&T) -> bool { | |
466 | self.iter().any(pred) | |
467 | } | |
468 | ||
469 | pub fn is_empty(&self) -> bool { | |
470 | self.all_vecs(|v| v.is_empty()) | |
471 | } | |
472 | ||
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, | |
476 | self.type_limit, | |
477 | self.self_limit) | |
478 | } | |
479 | ||
480 | pub fn map_enumerated<U, P>(&self, pred: P) -> VecPerParamSpace<U> where | |
c34b1796 | 481 | P: FnMut((ParamSpace, usize, &T)) -> U, |
1a4d82fc JJ |
482 | { |
483 | let result = self.iter_enumerated().map(pred).collect(); | |
484 | VecPerParamSpace::new_internal(result, | |
485 | self.type_limit, | |
486 | self.self_limit) | |
487 | } | |
488 | ||
1a4d82fc JJ |
489 | pub fn split(self) -> SeparateVecsPerParamSpace<T> { |
490 | let VecPerParamSpace { type_limit, self_limit, content } = self; | |
491 | ||
492 | let mut content_iter = content.into_iter(); | |
493 | ||
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() | |
970d7e83 LB |
498 | } |
499 | } | |
1a4d82fc | 500 | |
7453a54e | 501 | pub fn with_slice(mut self, space: ParamSpace, slice: &[T]) |
1a4d82fc | 502 | -> VecPerParamSpace<T> |
7453a54e | 503 | where T: Clone |
1a4d82fc JJ |
504 | { |
505 | assert!(self.is_empty_in(space)); | |
7453a54e SL |
506 | for t in slice { |
507 | self.push(space, t.clone()); | |
508 | } | |
509 | ||
1a4d82fc JJ |
510 | self |
511 | } | |
512 | } | |
513 | ||
514 | #[derive(Clone)] | |
515 | pub struct EnumeratedItems<'a,T:'a> { | |
516 | vec: &'a VecPerParamSpace<T>, | |
c34b1796 AL |
517 | space_index: usize, |
518 | elem_index: usize | |
970d7e83 LB |
519 | } |
520 | ||
1a4d82fc JJ |
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(); | |
525 | result | |
526 | } | |
527 | ||
528 | fn adjust_space(&mut self) { | |
529 | let spaces = ParamSpace::all(); | |
530 | while | |
531 | self.space_index < spaces.len() && | |
532 | self.elem_index >= self.vec.len(spaces[self.space_index]) | |
533 | { | |
534 | self.space_index += 1; | |
535 | self.elem_index = 0; | |
970d7e83 LB |
536 | } |
537 | } | |
538 | } | |
539 | ||
1a4d82fc | 540 | impl<'a,T> Iterator for EnumeratedItems<'a,T> { |
c34b1796 | 541 | type Item = (ParamSpace, usize, &'a T); |
1a4d82fc | 542 | |
c34b1796 | 543 | fn next(&mut self) -> Option<(ParamSpace, usize, &'a T)> { |
1a4d82fc JJ |
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); | |
549 | ||
550 | self.elem_index += 1; | |
551 | self.adjust_space(); | |
552 | ||
553 | Some((space, index, item)) | |
554 | } else { | |
555 | None | |
970d7e83 LB |
556 | } |
557 | } | |
7453a54e SL |
558 | |
559 | fn size_hint(&self) -> (usize, Option<usize>) { | |
560 | let size = self.vec.as_slice().len(); | |
561 | (size, Some(size)) | |
562 | } | |
970d7e83 LB |
563 | } |
564 | ||
85aaf69f SL |
565 | impl<T> IntoIterator for VecPerParamSpace<T> { |
566 | type Item = T; | |
567 | type IntoIter = IntoIter<T>; | |
568 | ||
569 | fn into_iter(self) -> IntoIter<T> { | |
570 | self.into_vec().into_iter() | |
571 | } | |
572 | } | |
573 | ||
574 | impl<'a,T> IntoIterator for &'a VecPerParamSpace<T> { | |
575 | type Item = &'a T; | |
576 | type IntoIter = Iter<'a, T>; | |
577 | ||
578 | fn into_iter(self) -> Iter<'a, T> { | |
579 | self.as_slice().into_iter() | |
580 | } | |
581 | } | |
582 | ||
583 | ||
1a4d82fc JJ |
584 | /////////////////////////////////////////////////////////////////////////// |
585 | // Public trait `Subst` | |
586 | // | |
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). | |
590 | ||
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) | |
594 | } | |
595 | ||
596 | fn subst_spanned(&self, tcx: &ty::ctxt<'tcx>, | |
597 | substs: &Substs<'tcx>, | |
598 | span: Option<Span>) | |
599 | -> Self; | |
600 | } | |
601 | ||
602 | impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T { | |
603 | fn subst_spanned(&self, | |
604 | tcx: &ty::ctxt<'tcx>, | |
605 | substs: &Substs<'tcx>, | |
606 | span: Option<Span>) | |
607 | -> T | |
608 | { | |
609 | let mut folder = SubstFolder { tcx: tcx, | |
610 | substs: substs, | |
611 | span: span, | |
612 | root_ty: None, | |
613 | ty_stack_depth: 0, | |
614 | region_binders_passed: 0 }; | |
615 | (*self).fold_with(&mut folder) | |
616 | } | |
617 | } | |
618 | ||
619 | /////////////////////////////////////////////////////////////////////////// | |
620 | // The actual substitution engine itself is a type folder. | |
621 | ||
622 | struct SubstFolder<'a, 'tcx: 'a> { | |
623 | tcx: &'a ty::ctxt<'tcx>, | |
624 | substs: &'a Substs<'tcx>, | |
625 | ||
626 | // The location for which the substitution is performed, if available. | |
627 | span: Option<Span>, | |
628 | ||
629 | // The root type that is being substituted, if available. | |
630 | root_ty: Option<Ty<'tcx>>, | |
631 | ||
632 | // Depth of type stack | |
c34b1796 | 633 | ty_stack_depth: usize, |
1a4d82fc JJ |
634 | |
635 | // Number of region binders we have passed through while doing the substitution | |
636 | region_binders_passed: u32, | |
637 | } | |
638 | ||
639 | impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> { | |
640 | fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx } | |
641 | ||
642 | fn enter_region_binder(&mut self) { | |
643 | self.region_binders_passed += 1; | |
644 | } | |
645 | ||
646 | fn exit_region_binder(&mut self) { | |
647 | self.region_binders_passed -= 1; | |
648 | } | |
649 | ||
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()`. | |
656 | match r { | |
9346a6ac | 657 | ty::ReEarlyBound(data) => { |
1a4d82fc JJ |
658 | match self.substs.regions { |
659 | ErasedRegions => ty::ReStatic, | |
660 | NonerasedRegions(ref regions) => | |
9346a6ac | 661 | match regions.opt_get(data.space, data.index as usize) { |
1a4d82fc JJ |
662 | Some(&r) => { |
663 | self.shift_region_through_binders(r) | |
664 | } | |
665 | None => { | |
666 | let span = self.span.unwrap_or(DUMMY_SP); | |
667 | self.tcx().sess.span_bug( | |
668 | span, | |
669 | &format!("Type parameter out of range \ | |
62682a34 | 670 | when substituting in region {} (root type={:?}) \ |
9346a6ac | 671 | (space={:?}, index={})", |
62682a34 SL |
672 | data.name, |
673 | self.root_ty, | |
9346a6ac AL |
674 | data.space, |
675 | data.index)); | |
1a4d82fc JJ |
676 | } |
677 | } | |
970d7e83 LB |
678 | } |
679 | } | |
1a4d82fc | 680 | _ => r |
970d7e83 LB |
681 | } |
682 | } | |
1a4d82fc JJ |
683 | |
684 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
c1a9b12d | 685 | if !t.needs_subst() { |
1a4d82fc JJ |
686 | return t; |
687 | } | |
688 | ||
689 | // track the root type we were asked to substitute | |
690 | let depth = self.ty_stack_depth; | |
691 | if depth == 0 { | |
692 | self.root_ty = Some(t); | |
693 | } | |
694 | self.ty_stack_depth += 1; | |
695 | ||
696 | let t1 = match t.sty { | |
62682a34 | 697 | ty::TyParam(p) => { |
1a4d82fc JJ |
698 | self.ty_for_param(p, t) |
699 | } | |
700 | _ => { | |
9cc50fc6 | 701 | t.super_fold_with(self) |
1a4d82fc JJ |
702 | } |
703 | }; | |
704 | ||
705 | assert_eq!(depth + 1, self.ty_stack_depth); | |
706 | self.ty_stack_depth -= 1; | |
707 | if depth == 0 { | |
708 | self.root_ty = None; | |
709 | } | |
710 | ||
711 | return t1; | |
712 | } | |
970d7e83 LB |
713 | } |
714 | ||
1a4d82fc JJ |
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. | |
c34b1796 | 718 | let opt_ty = self.substs.types.opt_get(p.space, p.idx as usize); |
1a4d82fc JJ |
719 | let ty = match opt_ty { |
720 | Some(t) => *t, | |
721 | None => { | |
722 | let span = self.span.unwrap_or(DUMMY_SP); | |
723 | self.tcx().sess.span_bug( | |
724 | span, | |
62682a34 SL |
725 | &format!("Type parameter `{:?}` ({:?}/{:?}/{}) out of range \ |
726 | when substituting (root type={:?}) substs={:?}", | |
727 | p, | |
728 | source_ty, | |
1a4d82fc JJ |
729 | p.space, |
730 | p.idx, | |
62682a34 SL |
731 | self.root_ty, |
732 | self.substs)); | |
1a4d82fc JJ |
733 | } |
734 | }; | |
735 | ||
736 | self.shift_regions_through_binders(ty) | |
737 | } | |
738 | ||
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: | |
742 | /// | |
743 | /// ``` | |
744 | /// type Func<A> = fn(A); | |
745 | /// type MetaFunc = for<'a> fn(Func<&'a int>) | |
746 | /// ``` | |
747 | /// | |
748 | /// The type `MetaFunc`, when fully expanded, will be | |
749 | /// | |
750 | /// for<'a> fn(fn(&'a int)) | |
751 | /// ^~ ^~ ^~~ | |
752 | /// | | | | |
753 | /// | | DebruijnIndex of 2 | |
754 | /// Binders | |
755 | /// | |
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. | |
762 | /// | |
763 | /// As a second example, consider this twist: | |
764 | /// | |
765 | /// ``` | |
766 | /// type FuncTuple<A> = (A,fn(A)); | |
767 | /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>) | |
768 | /// ``` | |
769 | /// | |
770 | /// Here the final type will be: | |
771 | /// | |
772 | /// for<'a> fn((&'a int, fn(&'a int))) | |
773 | /// ^~~ ^~~ | |
774 | /// | | | |
775 | /// DebruijnIndex of 1 | | |
776 | /// DebruijnIndex of 2 | |
777 | /// | |
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> { | |
c1a9b12d SL |
782 | debug!("shift_regions(ty={:?}, region_binders_passed={:?}, has_escaping_regions={:?})", |
783 | ty, self.region_binders_passed, ty.has_escaping_regions()); | |
1a4d82fc | 784 | |
c1a9b12d | 785 | if self.region_binders_passed == 0 || !ty.has_escaping_regions() { |
1a4d82fc | 786 | return ty; |
970d7e83 | 787 | } |
1a4d82fc | 788 | |
e9174d1e | 789 | let result = ty::fold::shift_regions(self.tcx(), self.region_binders_passed, &ty); |
62682a34 | 790 | debug!("shift_regions: shifted result = {:?}", result); |
1a4d82fc JJ |
791 | |
792 | result | |
793 | } | |
794 | ||
795 | fn shift_region_through_binders(&self, region: ty::Region) -> ty::Region { | |
e9174d1e | 796 | ty::fold::shift_region(region, self.region_binders_passed) |
970d7e83 LB |
797 | } |
798 | } |