]>
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 | ||
54a0048b | 13 | use hir::def_id::DefId; |
c30ab7b3 | 14 | use ty::{self, Slice, Ty, TyCtxt}; |
9e0c209e | 15 | use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor}; |
970d7e83 | 16 | |
9e0c209e | 17 | use serialize::{self, Encodable, Encoder, Decodable, Decoder}; |
3157f602 | 18 | use syntax_pos::{Span, DUMMY_SP}; |
c30ab7b3 | 19 | use rustc_data_structures::accumulate_vec::AccumulateVec; |
1a4d82fc | 20 | |
9e0c209e SL |
21 | use core::nonzero::NonZero; |
22 | use std::fmt; | |
23 | use std::iter; | |
24 | use std::marker::PhantomData; | |
25 | use std::mem; | |
26 | ||
27 | /// An entity in the Rust typesystem, which can be one of | |
28 | /// several kinds (only types and lifetimes for now). | |
29 | /// To reduce memory usage, a `Kind` is a interned pointer, | |
30 | /// with the lowest 2 bits being reserved for a tag to | |
31 | /// indicate the type (`Ty` or `Region`) it points to. | |
32 | #[derive(Copy, Clone, PartialEq, Eq, Hash)] | |
33 | pub struct Kind<'tcx> { | |
34 | ptr: NonZero<usize>, | |
35 | marker: PhantomData<(Ty<'tcx>, &'tcx ty::Region)> | |
970d7e83 LB |
36 | } |
37 | ||
9e0c209e SL |
38 | const TAG_MASK: usize = 0b11; |
39 | const TYPE_TAG: usize = 0b00; | |
40 | const REGION_TAG: usize = 0b01; | |
41 | ||
42 | impl<'tcx> From<Ty<'tcx>> for Kind<'tcx> { | |
43 | fn from(ty: Ty<'tcx>) -> Kind<'tcx> { | |
44 | // Ensure we can use the tag bits. | |
45 | assert_eq!(mem::align_of_val(ty) & TAG_MASK, 0); | |
46 | ||
47 | let ptr = ty as *const _ as usize; | |
48 | Kind { | |
49 | ptr: unsafe { | |
50 | NonZero::new(ptr | TYPE_TAG) | |
51 | }, | |
52 | marker: PhantomData | |
970d7e83 | 53 | } |
1a4d82fc | 54 | } |
9cc50fc6 SL |
55 | } |
56 | ||
9e0c209e SL |
57 | impl<'tcx> From<&'tcx ty::Region> for Kind<'tcx> { |
58 | fn from(r: &'tcx ty::Region) -> Kind<'tcx> { | |
59 | // Ensure we can use the tag bits. | |
60 | assert_eq!(mem::align_of_val(r) & TAG_MASK, 0); | |
61 | ||
62 | let ptr = r as *const _ as usize; | |
63 | Kind { | |
64 | ptr: unsafe { | |
65 | NonZero::new(ptr | REGION_TAG) | |
66 | }, | |
67 | marker: PhantomData | |
970d7e83 LB |
68 | } |
69 | } | |
70 | } | |
71 | ||
9e0c209e SL |
72 | impl<'tcx> Kind<'tcx> { |
73 | #[inline] | |
74 | unsafe fn downcast<T>(self, tag: usize) -> Option<&'tcx T> { | |
75 | let ptr = *self.ptr; | |
76 | if ptr & TAG_MASK == tag { | |
77 | Some(&*((ptr & !TAG_MASK) as *const _)) | |
78 | } else { | |
79 | None | |
1a4d82fc JJ |
80 | } |
81 | } | |
82 | ||
9e0c209e SL |
83 | #[inline] |
84 | pub fn as_type(self) -> Option<Ty<'tcx>> { | |
85 | unsafe { | |
86 | self.downcast(TYPE_TAG) | |
1a4d82fc JJ |
87 | } |
88 | } | |
89 | ||
9e0c209e SL |
90 | #[inline] |
91 | pub fn as_region(self) -> Option<&'tcx ty::Region> { | |
92 | unsafe { | |
93 | self.downcast(REGION_TAG) | |
1a4d82fc JJ |
94 | } |
95 | } | |
9e0c209e | 96 | } |
1a4d82fc | 97 | |
9e0c209e SL |
98 | impl<'tcx> fmt::Debug for Kind<'tcx> { |
99 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
100 | if let Some(ty) = self.as_type() { | |
101 | write!(f, "{:?}", ty) | |
102 | } else if let Some(r) = self.as_region() { | |
103 | write!(f, "{:?}", r) | |
104 | } else { | |
105 | write!(f, "<unknwon @ {:p}>", *self.ptr as *const ()) | |
1a4d82fc JJ |
106 | } |
107 | } | |
9e0c209e | 108 | } |
1a4d82fc | 109 | |
9e0c209e SL |
110 | impl<'tcx> TypeFoldable<'tcx> for Kind<'tcx> { |
111 | fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self { | |
112 | if let Some(ty) = self.as_type() { | |
113 | Kind::from(ty.fold_with(folder)) | |
114 | } else if let Some(r) = self.as_region() { | |
115 | Kind::from(r.fold_with(folder)) | |
116 | } else { | |
117 | bug!() | |
1a4d82fc | 118 | } |
1a4d82fc JJ |
119 | } |
120 | ||
9e0c209e SL |
121 | fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool { |
122 | if let Some(ty) = self.as_type() { | |
123 | ty.visit_with(visitor) | |
124 | } else if let Some(r) = self.as_region() { | |
125 | r.visit_with(visitor) | |
126 | } else { | |
127 | bug!() | |
1a4d82fc JJ |
128 | } |
129 | } | |
9e0c209e | 130 | } |
1a4d82fc | 131 | |
9e0c209e SL |
132 | impl<'tcx> Encodable for Kind<'tcx> { |
133 | fn encode<E: Encoder>(&self, e: &mut E) -> Result<(), E::Error> { | |
134 | e.emit_enum("Kind", |e| { | |
135 | if let Some(ty) = self.as_type() { | |
136 | e.emit_enum_variant("Ty", TYPE_TAG, 1, |e| { | |
137 | e.emit_enum_variant_arg(0, |e| ty.encode(e)) | |
138 | }) | |
139 | } else if let Some(r) = self.as_region() { | |
140 | e.emit_enum_variant("Region", REGION_TAG, 1, |e| { | |
141 | e.emit_enum_variant_arg(0, |e| r.encode(e)) | |
142 | }) | |
1a4d82fc | 143 | } else { |
9e0c209e | 144 | bug!() |
1a4d82fc | 145 | } |
9e0c209e | 146 | }) |
1a4d82fc | 147 | } |
9e0c209e | 148 | } |
1a4d82fc | 149 | |
9e0c209e SL |
150 | impl<'tcx> Decodable for Kind<'tcx> { |
151 | fn decode<D: Decoder>(d: &mut D) -> Result<Kind<'tcx>, D::Error> { | |
152 | d.read_enum("Kind", |d| { | |
153 | d.read_enum_variant(&["Ty", "Region"], |d, tag| { | |
154 | match tag { | |
155 | TYPE_TAG => Ty::decode(d).map(Kind::from), | |
156 | REGION_TAG => <&ty::Region>::decode(d).map(Kind::from), | |
157 | _ => Err(d.error("invalid Kind tag")) | |
158 | } | |
159 | }) | |
160 | }) | |
1a4d82fc | 161 | } |
9e0c209e | 162 | } |
1a4d82fc | 163 | |
9e0c209e | 164 | /// A substitution mapping type/region parameters to new values. |
c30ab7b3 | 165 | pub type Substs<'tcx> = Slice<Kind<'tcx>>; |
1a4d82fc | 166 | |
9e0c209e | 167 | impl<'a, 'gcx, 'tcx> Substs<'tcx> { |
9e0c209e SL |
168 | /// Creates a Substs for generic parameter definitions, |
169 | /// by calling closures to obtain each region and type. | |
170 | /// The closures get to observe the Substs as they're | |
171 | /// being built, which can be used to correctly | |
172 | /// substitute defaults of type parameters. | |
173 | pub fn for_item<FR, FT>(tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
174 | def_id: DefId, | |
175 | mut mk_region: FR, | |
176 | mut mk_type: FT) | |
177 | -> &'tcx Substs<'tcx> | |
c30ab7b3 SL |
178 | where FR: FnMut(&ty::RegionParameterDef, &[Kind<'tcx>]) -> &'tcx ty::Region, |
179 | FT: FnMut(&ty::TypeParameterDef<'tcx>, &[Kind<'tcx>]) -> Ty<'tcx> { | |
9e0c209e | 180 | let defs = tcx.lookup_generics(def_id); |
c30ab7b3 SL |
181 | let mut substs = Vec::with_capacity(defs.count()); |
182 | Substs::fill_item(&mut substs, tcx, defs, &mut mk_region, &mut mk_type); | |
183 | tcx.intern_substs(&substs) | |
1a4d82fc JJ |
184 | } |
185 | ||
c30ab7b3 | 186 | fn fill_item<FR, FT>(substs: &mut Vec<Kind<'tcx>>, |
9e0c209e SL |
187 | tcx: TyCtxt<'a, 'gcx, 'tcx>, |
188 | defs: &ty::Generics<'tcx>, | |
189 | mk_region: &mut FR, | |
190 | mk_type: &mut FT) | |
c30ab7b3 SL |
191 | where FR: FnMut(&ty::RegionParameterDef, &[Kind<'tcx>]) -> &'tcx ty::Region, |
192 | FT: FnMut(&ty::TypeParameterDef<'tcx>, &[Kind<'tcx>]) -> Ty<'tcx> { | |
193 | ||
9e0c209e SL |
194 | if let Some(def_id) = defs.parent { |
195 | let parent_defs = tcx.lookup_generics(def_id); | |
c30ab7b3 | 196 | Substs::fill_item(substs, tcx, parent_defs, mk_region, mk_type); |
9e0c209e | 197 | } |
1a4d82fc | 198 | |
9e0c209e SL |
199 | // Handle Self first, before all regions. |
200 | let mut types = defs.types.iter(); | |
201 | if defs.parent.is_none() && defs.has_self { | |
202 | let def = types.next().unwrap(); | |
c30ab7b3 SL |
203 | let ty = mk_type(def, substs); |
204 | assert_eq!(def.index as usize, substs.len()); | |
205 | substs.push(Kind::from(ty)); | |
9e0c209e | 206 | } |
1a4d82fc | 207 | |
9e0c209e | 208 | for def in &defs.regions { |
c30ab7b3 SL |
209 | let region = mk_region(def, substs); |
210 | assert_eq!(def.index as usize, substs.len()); | |
211 | substs.push(Kind::from(region)); | |
9e0c209e | 212 | } |
1a4d82fc | 213 | |
9e0c209e | 214 | for def in types { |
c30ab7b3 SL |
215 | let ty = mk_type(def, substs); |
216 | assert_eq!(def.index as usize, substs.len()); | |
217 | substs.push(Kind::from(ty)); | |
9e0c209e | 218 | } |
1a4d82fc JJ |
219 | } |
220 | ||
9e0c209e | 221 | pub fn is_noop(&self) -> bool { |
c30ab7b3 | 222 | self.is_empty() |
1a4d82fc JJ |
223 | } |
224 | ||
9e0c209e SL |
225 | #[inline] |
226 | pub fn params(&self) -> &[Kind<'tcx>] { | |
c30ab7b3 SL |
227 | // FIXME (dikaiosune) this should be removed, and corresponding compilation errors fixed |
228 | self | |
1a4d82fc JJ |
229 | } |
230 | ||
9e0c209e SL |
231 | #[inline] |
232 | pub fn types(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a { | |
c30ab7b3 | 233 | self.iter().filter_map(|k| k.as_type()) |
1a4d82fc JJ |
234 | } |
235 | ||
9e0c209e SL |
236 | #[inline] |
237 | pub fn regions(&'a self) -> impl DoubleEndedIterator<Item=&'tcx ty::Region> + 'a { | |
c30ab7b3 | 238 | self.iter().filter_map(|k| k.as_region()) |
970d7e83 | 239 | } |
1a4d82fc | 240 | |
9e0c209e SL |
241 | #[inline] |
242 | pub fn type_at(&self, i: usize) -> Ty<'tcx> { | |
c30ab7b3 SL |
243 | self[i].as_type().unwrap_or_else(|| { |
244 | bug!("expected type for param #{} in {:?}", i, self); | |
9e0c209e | 245 | }) |
1a4d82fc | 246 | } |
1a4d82fc | 247 | |
9e0c209e SL |
248 | #[inline] |
249 | pub fn region_at(&self, i: usize) -> &'tcx ty::Region { | |
c30ab7b3 SL |
250 | self[i].as_region().unwrap_or_else(|| { |
251 | bug!("expected region for param #{} in {:?}", i, self); | |
9e0c209e | 252 | }) |
1a4d82fc JJ |
253 | } |
254 | ||
9e0c209e SL |
255 | #[inline] |
256 | pub fn type_for_def(&self, ty_param_def: &ty::TypeParameterDef) -> Ty<'tcx> { | |
257 | self.type_at(ty_param_def.index as usize) | |
258 | } | |
259 | ||
260 | #[inline] | |
261 | pub fn region_for_def(&self, def: &ty::RegionParameterDef) -> &'tcx ty::Region { | |
262 | self.region_at(def.index as usize) | |
263 | } | |
264 | ||
265 | /// Transform from substitutions for a child of `source_ancestor` | |
266 | /// (e.g. a trait or impl) to substitutions for the same child | |
267 | /// in a different item, with `target_substs` as the base for | |
268 | /// the target impl/trait, with the source child-specific | |
269 | /// parameters (e.g. method parameters) on top of that base. | |
270 | pub fn rebase_onto(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
271 | source_ancestor: DefId, | |
272 | target_substs: &Substs<'tcx>) | |
273 | -> &'tcx Substs<'tcx> { | |
274 | let defs = tcx.lookup_generics(source_ancestor); | |
c30ab7b3 | 275 | tcx.mk_substs(target_substs.iter().chain(&self[defs.own_count()..]).cloned()) |
970d7e83 LB |
276 | } |
277 | } | |
278 | ||
9e0c209e SL |
279 | impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> { |
280 | fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self { | |
c30ab7b3 SL |
281 | let params: AccumulateVec<[_; 8]> = self.iter().map(|k| k.fold_with(folder)).collect(); |
282 | ||
283 | // If folding doesn't change the substs, it's faster to avoid | |
284 | // calling `mk_substs` and instead reuse the existing substs. | |
285 | if params[..] == self[..] { | |
286 | self | |
287 | } else { | |
288 | folder.tcx().intern_substs(¶ms) | |
289 | } | |
7453a54e | 290 | } |
85aaf69f | 291 | |
9e0c209e SL |
292 | fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self { |
293 | folder.fold_substs(self) | |
85aaf69f | 294 | } |
85aaf69f | 295 | |
9e0c209e | 296 | fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool { |
c30ab7b3 | 297 | self.iter().any(|t| t.visit_with(visitor)) |
85aaf69f SL |
298 | } |
299 | } | |
300 | ||
9e0c209e | 301 | impl<'tcx> serialize::UseSpecializedDecodable for &'tcx Substs<'tcx> {} |
85aaf69f | 302 | |
1a4d82fc JJ |
303 | /////////////////////////////////////////////////////////////////////////// |
304 | // Public trait `Subst` | |
305 | // | |
306 | // Just call `foo.subst(tcx, substs)` to perform a substitution across | |
307 | // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when | |
308 | // there is more information available (for better errors). | |
309 | ||
310 | pub trait Subst<'tcx> : Sized { | |
a7813a04 | 311 | fn subst<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, |
c30ab7b3 | 312 | substs: &[Kind<'tcx>]) -> Self { |
1a4d82fc JJ |
313 | self.subst_spanned(tcx, substs, None) |
314 | } | |
315 | ||
a7813a04 | 316 | fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, |
c30ab7b3 | 317 | substs: &[Kind<'tcx>], |
a7813a04 XL |
318 | span: Option<Span>) |
319 | -> Self; | |
1a4d82fc JJ |
320 | } |
321 | ||
322 | impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T { | |
a7813a04 | 323 | fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, |
c30ab7b3 | 324 | substs: &[Kind<'tcx>], |
a7813a04 XL |
325 | span: Option<Span>) |
326 | -> T | |
1a4d82fc JJ |
327 | { |
328 | let mut folder = SubstFolder { tcx: tcx, | |
329 | substs: substs, | |
330 | span: span, | |
331 | root_ty: None, | |
332 | ty_stack_depth: 0, | |
333 | region_binders_passed: 0 }; | |
334 | (*self).fold_with(&mut folder) | |
335 | } | |
336 | } | |
337 | ||
338 | /////////////////////////////////////////////////////////////////////////// | |
339 | // The actual substitution engine itself is a type folder. | |
340 | ||
a7813a04 XL |
341 | struct SubstFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> { |
342 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
c30ab7b3 | 343 | substs: &'a [Kind<'tcx>], |
1a4d82fc JJ |
344 | |
345 | // The location for which the substitution is performed, if available. | |
346 | span: Option<Span>, | |
347 | ||
348 | // The root type that is being substituted, if available. | |
349 | root_ty: Option<Ty<'tcx>>, | |
350 | ||
351 | // Depth of type stack | |
c34b1796 | 352 | ty_stack_depth: usize, |
1a4d82fc JJ |
353 | |
354 | // Number of region binders we have passed through while doing the substitution | |
355 | region_binders_passed: u32, | |
356 | } | |
357 | ||
a7813a04 XL |
358 | impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for SubstFolder<'a, 'gcx, 'tcx> { |
359 | fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx } | |
1a4d82fc | 360 | |
54a0048b | 361 | fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> { |
1a4d82fc | 362 | self.region_binders_passed += 1; |
54a0048b | 363 | let t = t.super_fold_with(self); |
1a4d82fc | 364 | self.region_binders_passed -= 1; |
54a0048b | 365 | t |
1a4d82fc JJ |
366 | } |
367 | ||
9e0c209e | 368 | fn fold_region(&mut self, r: &'tcx ty::Region) -> &'tcx ty::Region { |
1a4d82fc JJ |
369 | // Note: This routine only handles regions that are bound on |
370 | // type declarations and other outer declarations, not those | |
371 | // bound in *fn types*. Region substitution of the bound | |
372 | // regions that appear in a function signature is done using | |
373 | // the specialized routine `ty::replace_late_regions()`. | |
9e0c209e | 374 | match *r { |
9346a6ac | 375 | ty::ReEarlyBound(data) => { |
c30ab7b3 | 376 | let r = self.substs.get(data.index as usize) |
9e0c209e SL |
377 | .and_then(|k| k.as_region()); |
378 | match r { | |
379 | Some(r) => { | |
54a0048b SL |
380 | self.shift_region_through_binders(r) |
381 | } | |
382 | None => { | |
383 | let span = self.span.unwrap_or(DUMMY_SP); | |
384 | span_bug!( | |
385 | span, | |
386 | "Region parameter out of range \ | |
387 | when substituting in region {} (root type={:?}) \ | |
9e0c209e | 388 | (index={})", |
54a0048b SL |
389 | data.name, |
390 | self.root_ty, | |
54a0048b SL |
391 | data.index); |
392 | } | |
970d7e83 LB |
393 | } |
394 | } | |
1a4d82fc | 395 | _ => r |
970d7e83 LB |
396 | } |
397 | } | |
1a4d82fc JJ |
398 | |
399 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
c1a9b12d | 400 | if !t.needs_subst() { |
1a4d82fc JJ |
401 | return t; |
402 | } | |
403 | ||
404 | // track the root type we were asked to substitute | |
405 | let depth = self.ty_stack_depth; | |
406 | if depth == 0 { | |
407 | self.root_ty = Some(t); | |
408 | } | |
409 | self.ty_stack_depth += 1; | |
410 | ||
411 | let t1 = match t.sty { | |
62682a34 | 412 | ty::TyParam(p) => { |
1a4d82fc JJ |
413 | self.ty_for_param(p, t) |
414 | } | |
415 | _ => { | |
9cc50fc6 | 416 | t.super_fold_with(self) |
1a4d82fc JJ |
417 | } |
418 | }; | |
419 | ||
420 | assert_eq!(depth + 1, self.ty_stack_depth); | |
421 | self.ty_stack_depth -= 1; | |
422 | if depth == 0 { | |
423 | self.root_ty = None; | |
424 | } | |
425 | ||
426 | return t1; | |
427 | } | |
970d7e83 LB |
428 | } |
429 | ||
a7813a04 | 430 | impl<'a, 'gcx, 'tcx> SubstFolder<'a, 'gcx, 'tcx> { |
1a4d82fc JJ |
431 | fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> { |
432 | // Look up the type in the substitutions. It really should be in there. | |
c30ab7b3 | 433 | let opt_ty = self.substs.get(p.idx as usize) |
9e0c209e | 434 | .and_then(|k| k.as_type()); |
1a4d82fc | 435 | let ty = match opt_ty { |
9e0c209e | 436 | Some(t) => t, |
1a4d82fc JJ |
437 | None => { |
438 | let span = self.span.unwrap_or(DUMMY_SP); | |
54a0048b | 439 | span_bug!( |
1a4d82fc | 440 | span, |
9e0c209e | 441 | "Type parameter `{:?}` ({:?}/{}) out of range \ |
54a0048b SL |
442 | when substituting (root type={:?}) substs={:?}", |
443 | p, | |
444 | source_ty, | |
54a0048b SL |
445 | p.idx, |
446 | self.root_ty, | |
c30ab7b3 | 447 | self.substs); |
1a4d82fc JJ |
448 | } |
449 | }; | |
450 | ||
451 | self.shift_regions_through_binders(ty) | |
452 | } | |
453 | ||
454 | /// It is sometimes necessary to adjust the debruijn indices during substitution. This occurs | |
455 | /// when we are substituting a type with escaping regions into a context where we have passed | |
456 | /// through region binders. That's quite a mouthful. Let's see an example: | |
457 | /// | |
458 | /// ``` | |
459 | /// type Func<A> = fn(A); | |
460 | /// type MetaFunc = for<'a> fn(Func<&'a int>) | |
461 | /// ``` | |
462 | /// | |
463 | /// The type `MetaFunc`, when fully expanded, will be | |
464 | /// | |
465 | /// for<'a> fn(fn(&'a int)) | |
466 | /// ^~ ^~ ^~~ | |
467 | /// | | | | |
468 | /// | | DebruijnIndex of 2 | |
469 | /// Binders | |
470 | /// | |
471 | /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the | |
472 | /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip | |
473 | /// over the inner binder (remember that we count Debruijn indices from 1). However, in the | |
474 | /// definition of `MetaFunc`, the binder is not visible, so the type `&'a int` will have a | |
475 | /// debruijn index of 1. It's only during the substitution that we can see we must increase the | |
476 | /// depth by 1 to account for the binder that we passed through. | |
477 | /// | |
478 | /// As a second example, consider this twist: | |
479 | /// | |
480 | /// ``` | |
481 | /// type FuncTuple<A> = (A,fn(A)); | |
482 | /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>) | |
483 | /// ``` | |
484 | /// | |
485 | /// Here the final type will be: | |
486 | /// | |
487 | /// for<'a> fn((&'a int, fn(&'a int))) | |
488 | /// ^~~ ^~~ | |
489 | /// | | | |
490 | /// DebruijnIndex of 1 | | |
491 | /// DebruijnIndex of 2 | |
492 | /// | |
493 | /// As indicated in the diagram, here the same type `&'a int` is substituted once, but in the | |
494 | /// first case we do not increase the Debruijn index and in the second case we do. The reason | |
495 | /// is that only in the second case have we passed through a fn binder. | |
496 | fn shift_regions_through_binders(&self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
c1a9b12d SL |
497 | debug!("shift_regions(ty={:?}, region_binders_passed={:?}, has_escaping_regions={:?})", |
498 | ty, self.region_binders_passed, ty.has_escaping_regions()); | |
1a4d82fc | 499 | |
c1a9b12d | 500 | if self.region_binders_passed == 0 || !ty.has_escaping_regions() { |
1a4d82fc | 501 | return ty; |
970d7e83 | 502 | } |
1a4d82fc | 503 | |
e9174d1e | 504 | let result = ty::fold::shift_regions(self.tcx(), self.region_binders_passed, &ty); |
62682a34 | 505 | debug!("shift_regions: shifted result = {:?}", result); |
1a4d82fc JJ |
506 | |
507 | result | |
508 | } | |
509 | ||
9e0c209e SL |
510 | fn shift_region_through_binders(&self, region: &'tcx ty::Region) -> &'tcx ty::Region { |
511 | self.tcx().mk_region(ty::fold::shift_region(*region, self.region_binders_passed)) | |
512 | } | |
513 | } | |
514 | ||
515 | // Helper methods that modify substitutions. | |
516 | ||
517 | impl<'a, 'gcx, 'tcx> ty::TraitRef<'tcx> { | |
518 | pub fn from_method(tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
519 | trait_id: DefId, | |
520 | substs: &Substs<'tcx>) | |
521 | -> ty::TraitRef<'tcx> { | |
522 | let defs = tcx.lookup_generics(trait_id); | |
523 | ||
9e0c209e SL |
524 | ty::TraitRef { |
525 | def_id: trait_id, | |
c30ab7b3 | 526 | substs: tcx.intern_substs(&substs[..defs.own_count()]) |
9e0c209e SL |
527 | } |
528 | } | |
529 | } | |
530 | ||
531 | impl<'a, 'gcx, 'tcx> ty::ExistentialTraitRef<'tcx> { | |
532 | pub fn erase_self_ty(tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
533 | trait_ref: ty::TraitRef<'tcx>) | |
534 | -> ty::ExistentialTraitRef<'tcx> { | |
535 | // Assert there is a Self. | |
536 | trait_ref.substs.type_at(0); | |
537 | ||
9e0c209e SL |
538 | ty::ExistentialTraitRef { |
539 | def_id: trait_ref.def_id, | |
c30ab7b3 | 540 | substs: tcx.intern_substs(&trait_ref.substs[1..]) |
9e0c209e SL |
541 | } |
542 | } | |
543 | } | |
544 | ||
545 | impl<'a, 'gcx, 'tcx> ty::PolyExistentialTraitRef<'tcx> { | |
546 | /// Object types don't have a self-type specified. Therefore, when | |
547 | /// we convert the principal trait-ref into a normal trait-ref, | |
548 | /// you must give *some* self-type. A common choice is `mk_err()` | |
549 | /// or some skolemized type. | |
550 | pub fn with_self_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
551 | self_ty: Ty<'tcx>) | |
552 | -> ty::PolyTraitRef<'tcx> { | |
553 | // otherwise the escaping regions would be captured by the binder | |
554 | assert!(!self_ty.has_escaping_regions()); | |
555 | ||
556 | self.map_bound(|trait_ref| { | |
9e0c209e SL |
557 | ty::TraitRef { |
558 | def_id: trait_ref.def_id, | |
c30ab7b3 SL |
559 | substs: tcx.mk_substs( |
560 | iter::once(Kind::from(self_ty)).chain(trait_ref.substs.iter().cloned())) | |
9e0c209e SL |
561 | } |
562 | }) | |
970d7e83 LB |
563 | } |
564 | } |