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