]>
Commit | Line | Data |
---|---|---|
970d7e83 LB |
1 | // Type substitutions. |
2 | ||
9fa01778 | 3 | use crate::infer::canonical::Canonical; |
9fa01778 | 4 | use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor}; |
e74abb32 | 5 | use crate::ty::sty::{ClosureSubsts, GeneratorSubsts}; |
dfeec247 | 6 | use crate::ty::{self, Lift, List, ParamConst, Ty, TyCtxt}; |
970d7e83 | 7 | |
dfeec247 | 8 | use rustc_hir::def_id::DefId; |
532ac7d7 | 9 | use rustc_macros::HashStable; |
dfeec247 XL |
10 | use rustc_serialize::{self, Decodable, Decoder, Encodable, Encoder}; |
11 | use rustc_span::{Span, DUMMY_SP}; | |
12 | use smallvec::SmallVec; | |
1a4d82fc | 13 | |
0531ce1d | 14 | use core::intrinsics; |
532ac7d7 | 15 | use std::cmp::Ordering; |
dfeec247 | 16 | use std::fmt; |
9e0c209e SL |
17 | use std::marker::PhantomData; |
18 | use std::mem; | |
0531ce1d | 19 | use std::num::NonZeroUsize; |
9e0c209e | 20 | |
a1dfa0c6 | 21 | /// An entity in the Rust type system, which can be one of |
532ac7d7 | 22 | /// several kinds (types, lifetimes, and consts). |
e74abb32 | 23 | /// To reduce memory usage, a `GenericArg` is a interned pointer, |
9e0c209e | 24 | /// with the lowest 2 bits being reserved for a tag to |
532ac7d7 | 25 | /// indicate the type (`Ty`, `Region`, or `Const`) it points to. |
0531ce1d | 26 | #[derive(Copy, Clone, PartialEq, Eq, Hash)] |
e74abb32 | 27 | pub struct GenericArg<'tcx> { |
0531ce1d | 28 | ptr: NonZeroUsize, |
dfeec247 | 29 | marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>, &'tcx ty::Const<'tcx>)>, |
970d7e83 LB |
30 | } |
31 | ||
9e0c209e SL |
32 | const TAG_MASK: usize = 0b11; |
33 | const TYPE_TAG: usize = 0b00; | |
34 | const REGION_TAG: usize = 0b01; | |
532ac7d7 | 35 | const CONST_TAG: usize = 0b10; |
9e0c209e | 36 | |
532ac7d7 | 37 | #[derive(Debug, RustcEncodable, RustcDecodable, PartialEq, Eq, PartialOrd, Ord, HashStable)] |
e74abb32 | 38 | pub enum GenericArgKind<'tcx> { |
0531ce1d XL |
39 | Lifetime(ty::Region<'tcx>), |
40 | Type(Ty<'tcx>), | |
532ac7d7 | 41 | Const(&'tcx ty::Const<'tcx>), |
0531ce1d XL |
42 | } |
43 | ||
e74abb32 XL |
44 | impl<'tcx> GenericArgKind<'tcx> { |
45 | fn pack(self) -> GenericArg<'tcx> { | |
0531ce1d | 46 | let (tag, ptr) = match self { |
e74abb32 | 47 | GenericArgKind::Lifetime(lt) => { |
0531ce1d XL |
48 | // Ensure we can use the tag bits. |
49 | assert_eq!(mem::align_of_val(lt) & TAG_MASK, 0); | |
50 | (REGION_TAG, lt as *const _ as usize) | |
51 | } | |
e74abb32 | 52 | GenericArgKind::Type(ty) => { |
0531ce1d XL |
53 | // Ensure we can use the tag bits. |
54 | assert_eq!(mem::align_of_val(ty) & TAG_MASK, 0); | |
55 | (TYPE_TAG, ty as *const _ as usize) | |
56 | } | |
e74abb32 | 57 | GenericArgKind::Const(ct) => { |
532ac7d7 XL |
58 | // Ensure we can use the tag bits. |
59 | assert_eq!(mem::align_of_val(ct) & TAG_MASK, 0); | |
60 | (CONST_TAG, ct as *const _ as usize) | |
61 | } | |
0531ce1d | 62 | }; |
9e0c209e | 63 | |
dfeec247 | 64 | GenericArg { ptr: unsafe { NonZeroUsize::new_unchecked(ptr | tag) }, marker: PhantomData } |
1a4d82fc | 65 | } |
9cc50fc6 SL |
66 | } |
67 | ||
e74abb32 | 68 | impl fmt::Debug for GenericArg<'tcx> { |
532ac7d7 XL |
69 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
70 | match self.unpack() { | |
e74abb32 XL |
71 | GenericArgKind::Lifetime(lt) => lt.fmt(f), |
72 | GenericArgKind::Type(ty) => ty.fmt(f), | |
73 | GenericArgKind::Const(ct) => ct.fmt(f), | |
532ac7d7 XL |
74 | } |
75 | } | |
76 | } | |
77 | ||
e74abb32 XL |
78 | impl<'tcx> Ord for GenericArg<'tcx> { |
79 | fn cmp(&self, other: &GenericArg<'_>) -> Ordering { | |
b7449926 | 80 | self.unpack().cmp(&other.unpack()) |
94b46f34 XL |
81 | } |
82 | } | |
83 | ||
e74abb32 XL |
84 | impl<'tcx> PartialOrd for GenericArg<'tcx> { |
85 | fn partial_cmp(&self, other: &GenericArg<'_>) -> Option<Ordering> { | |
94b46f34 XL |
86 | Some(self.cmp(&other)) |
87 | } | |
88 | } | |
89 | ||
e74abb32 XL |
90 | impl<'tcx> From<ty::Region<'tcx>> for GenericArg<'tcx> { |
91 | fn from(r: ty::Region<'tcx>) -> GenericArg<'tcx> { | |
92 | GenericArgKind::Lifetime(r).pack() | |
0531ce1d XL |
93 | } |
94 | } | |
9e0c209e | 95 | |
e74abb32 XL |
96 | impl<'tcx> From<Ty<'tcx>> for GenericArg<'tcx> { |
97 | fn from(ty: Ty<'tcx>) -> GenericArg<'tcx> { | |
98 | GenericArgKind::Type(ty).pack() | |
970d7e83 LB |
99 | } |
100 | } | |
101 | ||
e74abb32 XL |
102 | impl<'tcx> From<&'tcx ty::Const<'tcx>> for GenericArg<'tcx> { |
103 | fn from(c: &'tcx ty::Const<'tcx>) -> GenericArg<'tcx> { | |
104 | GenericArgKind::Const(c).pack() | |
532ac7d7 XL |
105 | } |
106 | } | |
107 | ||
e74abb32 | 108 | impl<'tcx> GenericArg<'tcx> { |
9e0c209e | 109 | #[inline] |
e74abb32 | 110 | pub fn unpack(self) -> GenericArgKind<'tcx> { |
7cac9316 | 111 | let ptr = self.ptr.get(); |
9e0c209e | 112 | unsafe { |
0531ce1d | 113 | match ptr & TAG_MASK { |
e74abb32 XL |
114 | REGION_TAG => GenericArgKind::Lifetime(&*((ptr & !TAG_MASK) as *const _)), |
115 | TYPE_TAG => GenericArgKind::Type(&*((ptr & !TAG_MASK) as *const _)), | |
116 | CONST_TAG => GenericArgKind::Const(&*((ptr & !TAG_MASK) as *const _)), | |
dfeec247 | 117 | _ => intrinsics::unreachable(), |
0531ce1d | 118 | } |
1a4d82fc JJ |
119 | } |
120 | } | |
48663c56 | 121 | |
e74abb32 | 122 | /// Unpack the `GenericArg` as a type when it is known certainly to be a type. |
48663c56 XL |
123 | /// This is true in cases where `Substs` is used in places where the kinds are known |
124 | /// to be limited (e.g. in tuples, where the only parameters are type parameters). | |
125 | pub fn expect_ty(self) -> Ty<'tcx> { | |
126 | match self.unpack() { | |
e74abb32 | 127 | GenericArgKind::Type(ty) => ty, |
48663c56 XL |
128 | _ => bug!("expected a type, but found another kind"), |
129 | } | |
130 | } | |
9e0c209e | 131 | } |
1a4d82fc | 132 | |
e74abb32 XL |
133 | impl<'a, 'tcx> Lift<'tcx> for GenericArg<'a> { |
134 | type Lifted = GenericArg<'tcx>; | |
0531ce1d | 135 | |
dc9dc135 | 136 | fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> { |
0531ce1d | 137 | match self.unpack() { |
e74abb32 XL |
138 | GenericArgKind::Lifetime(lt) => tcx.lift(<).map(|lt| lt.into()), |
139 | GenericArgKind::Type(ty) => tcx.lift(&ty).map(|ty| ty.into()), | |
140 | GenericArgKind::Const(ct) => tcx.lift(&ct).map(|ct| ct.into()), | |
abe05a73 XL |
141 | } |
142 | } | |
143 | } | |
144 | ||
e74abb32 | 145 | impl<'tcx> TypeFoldable<'tcx> for GenericArg<'tcx> { |
dc9dc135 | 146 | fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self { |
0531ce1d | 147 | match self.unpack() { |
e74abb32 XL |
148 | GenericArgKind::Lifetime(lt) => lt.fold_with(folder).into(), |
149 | GenericArgKind::Type(ty) => ty.fold_with(folder).into(), | |
150 | GenericArgKind::Const(ct) => ct.fold_with(folder).into(), | |
1a4d82fc | 151 | } |
1a4d82fc JJ |
152 | } |
153 | ||
9e0c209e | 154 | fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool { |
0531ce1d | 155 | match self.unpack() { |
e74abb32 XL |
156 | GenericArgKind::Lifetime(lt) => lt.visit_with(visitor), |
157 | GenericArgKind::Type(ty) => ty.visit_with(visitor), | |
158 | GenericArgKind::Const(ct) => ct.visit_with(visitor), | |
1a4d82fc JJ |
159 | } |
160 | } | |
9e0c209e | 161 | } |
1a4d82fc | 162 | |
e74abb32 | 163 | impl<'tcx> Encodable for GenericArg<'tcx> { |
9e0c209e | 164 | fn encode<E: Encoder>(&self, e: &mut E) -> Result<(), E::Error> { |
94b46f34 | 165 | self.unpack().encode(e) |
1a4d82fc | 166 | } |
9e0c209e | 167 | } |
1a4d82fc | 168 | |
e74abb32 XL |
169 | impl<'tcx> Decodable for GenericArg<'tcx> { |
170 | fn decode<D: Decoder>(d: &mut D) -> Result<GenericArg<'tcx>, D::Error> { | |
171 | Ok(GenericArgKind::decode(d)?.pack()) | |
1a4d82fc | 172 | } |
9e0c209e | 173 | } |
1a4d82fc | 174 | |
94b46f34 | 175 | /// A substitution mapping generic parameters to new values. |
e74abb32 | 176 | pub type InternalSubsts<'tcx> = List<GenericArg<'tcx>>; |
1a4d82fc | 177 | |
532ac7d7 XL |
178 | pub type SubstsRef<'tcx> = &'tcx InternalSubsts<'tcx>; |
179 | ||
dc9dc135 | 180 | impl<'a, 'tcx> InternalSubsts<'tcx> { |
e74abb32 XL |
181 | /// Interpret these substitutions as the substitutions of a closure type. |
182 | /// Closure substitutions have a particular structure controlled by the | |
183 | /// compiler that encodes information like the signature and closure kind; | |
184 | /// see `ty::ClosureSubsts` struct for more comments. | |
185 | pub fn as_closure(&'a self) -> ClosureSubsts<'a> { | |
dfeec247 | 186 | ClosureSubsts { substs: self } |
e74abb32 XL |
187 | } |
188 | ||
189 | /// Interpret these substitutions as the substitutions of a generator type. | |
190 | /// Closure substitutions have a particular structure controlled by the | |
191 | /// compiler that encodes information like the signature and generator kind; | |
192 | /// see `ty::GeneratorSubsts` struct for more comments. | |
193 | pub fn as_generator(&'tcx self) -> GeneratorSubsts<'tcx> { | |
194 | GeneratorSubsts { substs: self } | |
195 | } | |
196 | ||
532ac7d7 | 197 | /// Creates a `InternalSubsts` that maps each generic parameter to itself. |
dc9dc135 | 198 | pub fn identity_for_item(tcx: TyCtxt<'tcx>, def_id: DefId) -> SubstsRef<'tcx> { |
dfeec247 | 199 | Self::for_item(tcx, def_id, |param, _| tcx.mk_param_from_def(param)) |
476ff2be SL |
200 | } |
201 | ||
532ac7d7 | 202 | /// Creates a `InternalSubsts` that maps each generic parameter to a higher-ranked |
a1dfa0c6 XL |
203 | /// var bound at index `0`. For types, we use a `BoundVar` index equal to |
204 | /// the type parameter index. For regions, we use the `BoundRegion::BrNamed` | |
9fa01778 | 205 | /// variant (which has a `DefId`). |
dc9dc135 | 206 | pub fn bound_vars_for_item(tcx: TyCtxt<'tcx>, def_id: DefId) -> SubstsRef<'tcx> { |
dfeec247 XL |
207 | Self::for_item(tcx, def_id, |param, _| match param.kind { |
208 | ty::GenericParamDefKind::Type { .. } => tcx | |
209 | .mk_ty(ty::Bound( | |
210 | ty::INNERMOST, | |
211 | ty::BoundTy { | |
212 | var: ty::BoundVar::from(param.index), | |
213 | kind: ty::BoundTyKind::Param(param.name), | |
214 | }, | |
215 | )) | |
216 | .into(), | |
217 | ||
218 | ty::GenericParamDefKind::Lifetime => tcx | |
219 | .mk_region(ty::RegionKind::ReLateBound( | |
220 | ty::INNERMOST, | |
221 | ty::BoundRegion::BrNamed(param.def_id, param.name), | |
222 | )) | |
223 | .into(), | |
224 | ||
225 | ty::GenericParamDefKind::Const => tcx | |
226 | .mk_const(ty::Const { | |
227 | val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from(param.index)), | |
228 | ty: tcx.type_of(param.def_id), | |
229 | }) | |
230 | .into(), | |
a1dfa0c6 XL |
231 | }) |
232 | } | |
233 | ||
532ac7d7 | 234 | /// Creates a `InternalSubsts` for generic parameter definitions, |
94b46f34 | 235 | /// by calling closures to obtain each kind. |
532ac7d7 | 236 | /// The closures get to observe the `InternalSubsts` as they're |
9e0c209e | 237 | /// being built, which can be used to correctly |
94b46f34 | 238 | /// substitute defaults of generic parameters. |
dc9dc135 XL |
239 | pub fn for_item<F>(tcx: TyCtxt<'tcx>, def_id: DefId, mut mk_kind: F) -> SubstsRef<'tcx> |
240 | where | |
e74abb32 | 241 | F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, |
94b46f34 | 242 | { |
7cac9316 | 243 | let defs = tcx.generics_of(def_id); |
94b46f34 | 244 | let count = defs.count(); |
b7449926 | 245 | let mut substs = SmallVec::with_capacity(count); |
532ac7d7 | 246 | Self::fill_item(&mut substs, tcx, defs, &mut mk_kind); |
c30ab7b3 | 247 | tcx.intern_substs(&substs) |
1a4d82fc JJ |
248 | } |
249 | ||
dc9dc135 XL |
250 | pub fn extend_to<F>(&self, tcx: TyCtxt<'tcx>, def_id: DefId, mut mk_kind: F) -> SubstsRef<'tcx> |
251 | where | |
e74abb32 | 252 | F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, |
476ff2be | 253 | { |
532ac7d7 | 254 | Self::for_item(tcx, def_id, |param, substs| { |
dfeec247 | 255 | self.get(param.index as usize).cloned().unwrap_or_else(|| mk_kind(param, substs)) |
94b46f34 | 256 | }) |
476ff2be SL |
257 | } |
258 | ||
dc9dc135 | 259 | fn fill_item<F>( |
e74abb32 | 260 | substs: &mut SmallVec<[GenericArg<'tcx>; 8]>, |
dc9dc135 XL |
261 | tcx: TyCtxt<'tcx>, |
262 | defs: &ty::Generics, | |
263 | mk_kind: &mut F, | |
264 | ) where | |
e74abb32 | 265 | F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, |
94b46f34 | 266 | { |
9e0c209e | 267 | if let Some(def_id) = defs.parent { |
7cac9316 | 268 | let parent_defs = tcx.generics_of(def_id); |
532ac7d7 | 269 | Self::fill_item(substs, tcx, parent_defs, mk_kind); |
9e0c209e | 270 | } |
532ac7d7 | 271 | Self::fill_single(substs, defs, mk_kind) |
94b46f34 | 272 | } |
1a4d82fc | 273 | |
dfeec247 XL |
274 | fn fill_single<F>( |
275 | substs: &mut SmallVec<[GenericArg<'tcx>; 8]>, | |
276 | defs: &ty::Generics, | |
277 | mk_kind: &mut F, | |
278 | ) where | |
279 | F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, | |
94b46f34 | 280 | { |
0bf4aa26 | 281 | substs.reserve(defs.params.len()); |
94b46f34 XL |
282 | for param in &defs.params { |
283 | let kind = mk_kind(param, substs); | |
284 | assert_eq!(param.index as usize, substs.len()); | |
b7449926 | 285 | substs.push(kind); |
9e0c209e | 286 | } |
1a4d82fc JJ |
287 | } |
288 | ||
9e0c209e | 289 | pub fn is_noop(&self) -> bool { |
c30ab7b3 | 290 | self.is_empty() |
1a4d82fc JJ |
291 | } |
292 | ||
9e0c209e | 293 | #[inline] |
a1dfa0c6 | 294 | pub fn types(&'a self) -> impl DoubleEndedIterator<Item = Ty<'tcx>> + 'a { |
dfeec247 XL |
295 | self.iter() |
296 | .filter_map(|k| if let GenericArgKind::Type(ty) = k.unpack() { Some(ty) } else { None }) | |
1a4d82fc JJ |
297 | } |
298 | ||
9e0c209e | 299 | #[inline] |
a1dfa0c6 | 300 | pub fn regions(&'a self) -> impl DoubleEndedIterator<Item = ty::Region<'tcx>> + 'a { |
0531ce1d | 301 | self.iter().filter_map(|k| { |
dfeec247 | 302 | if let GenericArgKind::Lifetime(lt) = k.unpack() { Some(lt) } else { None } |
0531ce1d | 303 | }) |
970d7e83 | 304 | } |
1a4d82fc | 305 | |
532ac7d7 XL |
306 | #[inline] |
307 | pub fn consts(&'a self) -> impl DoubleEndedIterator<Item = &'tcx ty::Const<'tcx>> + 'a { | |
308 | self.iter().filter_map(|k| { | |
dfeec247 | 309 | if let GenericArgKind::Const(ct) = k.unpack() { Some(ct) } else { None } |
532ac7d7 XL |
310 | }) |
311 | } | |
312 | ||
313 | #[inline] | |
314 | pub fn non_erasable_generics( | |
dfeec247 | 315 | &'a self, |
e74abb32 | 316 | ) -> impl DoubleEndedIterator<Item = GenericArgKind<'tcx>> + 'a { |
dfeec247 XL |
317 | self.iter().filter_map(|k| match k.unpack() { |
318 | GenericArgKind::Lifetime(_) => None, | |
319 | generic => Some(generic), | |
532ac7d7 XL |
320 | }) |
321 | } | |
322 | ||
9e0c209e SL |
323 | #[inline] |
324 | pub fn type_at(&self, i: usize) -> Ty<'tcx> { | |
e74abb32 | 325 | if let GenericArgKind::Type(ty) = self[i].unpack() { |
0531ce1d XL |
326 | ty |
327 | } else { | |
c30ab7b3 | 328 | bug!("expected type for param #{} in {:?}", i, self); |
0531ce1d | 329 | } |
1a4d82fc | 330 | } |
1a4d82fc | 331 | |
9e0c209e | 332 | #[inline] |
7cac9316 | 333 | pub fn region_at(&self, i: usize) -> ty::Region<'tcx> { |
e74abb32 | 334 | if let GenericArgKind::Lifetime(lt) = self[i].unpack() { |
0531ce1d XL |
335 | lt |
336 | } else { | |
c30ab7b3 | 337 | bug!("expected region for param #{} in {:?}", i, self); |
0531ce1d | 338 | } |
1a4d82fc JJ |
339 | } |
340 | ||
532ac7d7 XL |
341 | #[inline] |
342 | pub fn const_at(&self, i: usize) -> &'tcx ty::Const<'tcx> { | |
e74abb32 | 343 | if let GenericArgKind::Const(ct) = self[i].unpack() { |
532ac7d7 XL |
344 | ct |
345 | } else { | |
346 | bug!("expected const for param #{} in {:?}", i, self); | |
347 | } | |
348 | } | |
349 | ||
9e0c209e | 350 | #[inline] |
e74abb32 | 351 | pub fn type_for_def(&self, def: &ty::GenericParamDef) -> GenericArg<'tcx> { |
94b46f34 | 352 | self.type_at(def.index as usize).into() |
9e0c209e SL |
353 | } |
354 | ||
355 | /// Transform from substitutions for a child of `source_ancestor` | |
0731742a | 356 | /// (e.g., a trait or impl) to substitutions for the same child |
9e0c209e SL |
357 | /// in a different item, with `target_substs` as the base for |
358 | /// the target impl/trait, with the source child-specific | |
0731742a | 359 | /// parameters (e.g., method parameters) on top of that base. |
dc9dc135 XL |
360 | pub fn rebase_onto( |
361 | &self, | |
362 | tcx: TyCtxt<'tcx>, | |
363 | source_ancestor: DefId, | |
364 | target_substs: SubstsRef<'tcx>, | |
365 | ) -> SubstsRef<'tcx> { | |
7cac9316 | 366 | let defs = tcx.generics_of(source_ancestor); |
94b46f34 | 367 | tcx.mk_substs(target_substs.iter().chain(&self[defs.params.len()..]).cloned()) |
970d7e83 | 368 | } |
476ff2be | 369 | |
dc9dc135 | 370 | pub fn truncate_to(&self, tcx: TyCtxt<'tcx>, generics: &ty::Generics) -> SubstsRef<'tcx> { |
476ff2be SL |
371 | tcx.mk_substs(self.iter().take(generics.count()).cloned()) |
372 | } | |
970d7e83 LB |
373 | } |
374 | ||
532ac7d7 | 375 | impl<'tcx> TypeFoldable<'tcx> for SubstsRef<'tcx> { |
dc9dc135 | 376 | fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self { |
e74abb32 XL |
377 | // This code is hot enough that it's worth specializing for the most |
378 | // common length lists, to avoid the overhead of `SmallVec` creation. | |
379 | // The match arms are in order of frequency. The 1, 2, and 0 cases are | |
380 | // typically hit in 90--99.99% of cases. When folding doesn't change | |
381 | // the substs, it's faster to reuse the existing substs rather than | |
382 | // calling `intern_substs`. | |
383 | match self.len() { | |
384 | 1 => { | |
385 | let param0 = self[0].fold_with(folder); | |
dfeec247 | 386 | if param0 == self[0] { self } else { folder.tcx().intern_substs(&[param0]) } |
e74abb32 XL |
387 | } |
388 | 2 => { | |
389 | let param0 = self[0].fold_with(folder); | |
390 | let param1 = self[1].fold_with(folder); | |
391 | if param0 == self[0] && param1 == self[1] { | |
392 | self | |
393 | } else { | |
394 | folder.tcx().intern_substs(&[param0, param1]) | |
395 | } | |
396 | } | |
dfeec247 | 397 | 0 => self, |
e74abb32 XL |
398 | _ => { |
399 | let params: SmallVec<[_; 8]> = self.iter().map(|k| k.fold_with(folder)).collect(); | |
dfeec247 | 400 | if params[..] == self[..] { self } else { folder.tcx().intern_substs(¶ms) } |
e74abb32 | 401 | } |
c30ab7b3 | 402 | } |
7453a54e | 403 | } |
85aaf69f | 404 | |
9e0c209e | 405 | fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool { |
c30ab7b3 | 406 | self.iter().any(|t| t.visit_with(visitor)) |
85aaf69f SL |
407 | } |
408 | } | |
409 | ||
416331ca | 410 | impl<'tcx> rustc_serialize::UseSpecializedDecodable for SubstsRef<'tcx> {} |
85aaf69f | 411 | |
1a4d82fc JJ |
412 | /////////////////////////////////////////////////////////////////////////// |
413 | // Public trait `Subst` | |
414 | // | |
415 | // Just call `foo.subst(tcx, substs)` to perform a substitution across | |
416 | // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when | |
417 | // there is more information available (for better errors). | |
418 | ||
a1dfa0c6 | 419 | pub trait Subst<'tcx>: Sized { |
e74abb32 | 420 | fn subst(&self, tcx: TyCtxt<'tcx>, substs: &[GenericArg<'tcx>]) -> Self { |
1a4d82fc JJ |
421 | self.subst_spanned(tcx, substs, None) |
422 | } | |
423 | ||
e74abb32 XL |
424 | fn subst_spanned( |
425 | &self, | |
426 | tcx: TyCtxt<'tcx>, | |
427 | substs: &[GenericArg<'tcx>], | |
428 | span: Option<Span>, | |
429 | ) -> Self; | |
1a4d82fc JJ |
430 | } |
431 | ||
dc9dc135 | 432 | impl<'tcx, T: TypeFoldable<'tcx>> Subst<'tcx> for T { |
e74abb32 XL |
433 | fn subst_spanned( |
434 | &self, | |
435 | tcx: TyCtxt<'tcx>, | |
436 | substs: &[GenericArg<'tcx>], | |
437 | span: Option<Span>, | |
438 | ) -> T { | |
dfeec247 XL |
439 | let mut folder = |
440 | SubstFolder { tcx, substs, span, root_ty: None, ty_stack_depth: 0, binders_passed: 0 }; | |
1a4d82fc JJ |
441 | (*self).fold_with(&mut folder) |
442 | } | |
443 | } | |
444 | ||
445 | /////////////////////////////////////////////////////////////////////////// | |
446 | // The actual substitution engine itself is a type folder. | |
447 | ||
dc9dc135 XL |
448 | struct SubstFolder<'a, 'tcx> { |
449 | tcx: TyCtxt<'tcx>, | |
e74abb32 | 450 | substs: &'a [GenericArg<'tcx>], |
1a4d82fc | 451 | |
48663c56 | 452 | /// The location for which the substitution is performed, if available. |
1a4d82fc JJ |
453 | span: Option<Span>, |
454 | ||
48663c56 | 455 | /// The root type that is being substituted, if available. |
1a4d82fc JJ |
456 | root_ty: Option<Ty<'tcx>>, |
457 | ||
48663c56 | 458 | /// Depth of type stack |
c34b1796 | 459 | ty_stack_depth: usize, |
1a4d82fc | 460 | |
48663c56 | 461 | /// Number of region binders we have passed through while doing the substitution |
a1dfa0c6 | 462 | binders_passed: u32, |
1a4d82fc JJ |
463 | } |
464 | ||
dc9dc135 | 465 | impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> { |
dfeec247 XL |
466 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { |
467 | self.tcx | |
468 | } | |
1a4d82fc | 469 | |
54a0048b | 470 | fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> { |
a1dfa0c6 | 471 | self.binders_passed += 1; |
54a0048b | 472 | let t = t.super_fold_with(self); |
a1dfa0c6 | 473 | self.binders_passed -= 1; |
54a0048b | 474 | t |
1a4d82fc JJ |
475 | } |
476 | ||
7cac9316 | 477 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
1a4d82fc JJ |
478 | // Note: This routine only handles regions that are bound on |
479 | // type declarations and other outer declarations, not those | |
480 | // bound in *fn types*. Region substitution of the bound | |
481 | // regions that appear in a function signature is done using | |
482 | // the specialized routine `ty::replace_late_regions()`. | |
9e0c209e | 483 | match *r { |
9346a6ac | 484 | ty::ReEarlyBound(data) => { |
48663c56 XL |
485 | let rk = self.substs.get(data.index as usize).map(|k| k.unpack()); |
486 | match rk { | |
dfeec247 | 487 | Some(GenericArgKind::Lifetime(lt)) => self.shift_region_through_binders(lt), |
0531ce1d | 488 | _ => { |
54a0048b | 489 | let span = self.span.unwrap_or(DUMMY_SP); |
48663c56 | 490 | let msg = format!( |
54a0048b SL |
491 | "Region parameter out of range \ |
492 | when substituting in region {} (root type={:?}) \ | |
9e0c209e | 493 | (index={})", |
dfeec247 XL |
494 | data.name, self.root_ty, data.index |
495 | ); | |
496 | span_bug!(span, "{}", msg); | |
54a0048b | 497 | } |
970d7e83 LB |
498 | } |
499 | } | |
dfeec247 | 500 | _ => r, |
970d7e83 LB |
501 | } |
502 | } | |
1a4d82fc JJ |
503 | |
504 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
c1a9b12d | 505 | if !t.needs_subst() { |
1a4d82fc JJ |
506 | return t; |
507 | } | |
508 | ||
509 | // track the root type we were asked to substitute | |
510 | let depth = self.ty_stack_depth; | |
511 | if depth == 0 { | |
512 | self.root_ty = Some(t); | |
513 | } | |
514 | self.ty_stack_depth += 1; | |
515 | ||
e74abb32 | 516 | let t1 = match t.kind { |
dfeec247 XL |
517 | ty::Param(p) => self.ty_for_param(p, t), |
518 | _ => t.super_fold_with(self), | |
1a4d82fc JJ |
519 | }; |
520 | ||
521 | assert_eq!(depth + 1, self.ty_stack_depth); | |
522 | self.ty_stack_depth -= 1; | |
523 | if depth == 0 { | |
524 | self.root_ty = None; | |
525 | } | |
526 | ||
527 | return t1; | |
528 | } | |
532ac7d7 XL |
529 | |
530 | fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { | |
531 | if !c.needs_subst() { | |
532 | return c; | |
533 | } | |
534 | ||
60c5eb7d | 535 | if let ty::ConstKind::Param(p) = c.val { |
532ac7d7 XL |
536 | self.const_for_param(p, c) |
537 | } else { | |
538 | c.super_fold_with(self) | |
539 | } | |
540 | } | |
970d7e83 LB |
541 | } |
542 | ||
dc9dc135 | 543 | impl<'a, 'tcx> SubstFolder<'a, 'tcx> { |
1a4d82fc JJ |
544 | fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> { |
545 | // Look up the type in the substitutions. It really should be in there. | |
48663c56 | 546 | let opt_ty = self.substs.get(p.index as usize).map(|k| k.unpack()); |
1a4d82fc | 547 | let ty = match opt_ty { |
e74abb32 | 548 | Some(GenericArgKind::Type(ty)) => ty, |
48663c56 XL |
549 | Some(kind) => { |
550 | let span = self.span.unwrap_or(DUMMY_SP); | |
551 | span_bug!( | |
552 | span, | |
553 | "expected type for `{:?}` ({:?}/{}) but found {:?} \ | |
554 | when substituting (root type={:?}) substs={:?}", | |
555 | p, | |
556 | source_ty, | |
557 | p.index, | |
558 | kind, | |
559 | self.root_ty, | |
560 | self.substs, | |
561 | ); | |
562 | } | |
563 | None => { | |
1a4d82fc | 564 | let span = self.span.unwrap_or(DUMMY_SP); |
54a0048b | 565 | span_bug!( |
1a4d82fc | 566 | span, |
48663c56 | 567 | "type parameter `{:?}` ({:?}/{}) out of range \ |
0bf4aa26 | 568 | when substituting (root type={:?}) substs={:?}", |
54a0048b SL |
569 | p, |
570 | source_ty, | |
48663c56 | 571 | p.index, |
54a0048b | 572 | self.root_ty, |
48663c56 XL |
573 | self.substs, |
574 | ); | |
1a4d82fc JJ |
575 | } |
576 | }; | |
577 | ||
a1dfa0c6 | 578 | self.shift_vars_through_binders(ty) |
1a4d82fc JJ |
579 | } |
580 | ||
532ac7d7 XL |
581 | fn const_for_param( |
582 | &self, | |
583 | p: ParamConst, | |
dfeec247 | 584 | source_ct: &'tcx ty::Const<'tcx>, |
532ac7d7 XL |
585 | ) -> &'tcx ty::Const<'tcx> { |
586 | // Look up the const in the substitutions. It really should be in there. | |
48663c56 XL |
587 | let opt_ct = self.substs.get(p.index as usize).map(|k| k.unpack()); |
588 | let ct = match opt_ct { | |
e74abb32 | 589 | Some(GenericArgKind::Const(ct)) => ct, |
48663c56 | 590 | Some(kind) => { |
532ac7d7 XL |
591 | let span = self.span.unwrap_or(DUMMY_SP); |
592 | span_bug!( | |
593 | span, | |
48663c56 XL |
594 | "expected const for `{:?}` ({:?}/{}) but found {:?} \ |
595 | when substituting substs={:?}", | |
532ac7d7 | 596 | p, |
48663c56 XL |
597 | source_ct, |
598 | p.index, | |
599 | kind, | |
600 | self.substs, | |
601 | ); | |
602 | } | |
603 | None => { | |
604 | let span = self.span.unwrap_or(DUMMY_SP); | |
605 | span_bug!( | |
606 | span, | |
607 | "const parameter `{:?}` ({:?}/{}) out of range \ | |
608 | when substituting substs={:?}", | |
609 | p, | |
610 | source_ct, | |
532ac7d7 | 611 | p.index, |
532ac7d7 XL |
612 | self.substs, |
613 | ); | |
614 | } | |
615 | }; | |
616 | ||
48663c56 | 617 | self.shift_vars_through_binders(ct) |
532ac7d7 XL |
618 | } |
619 | ||
9fa01778 | 620 | /// It is sometimes necessary to adjust the De Bruijn indices during substitution. This occurs |
a1dfa0c6 XL |
621 | /// when we are substituting a type with escaping bound vars into a context where we have |
622 | /// passed through binders. That's quite a mouthful. Let's see an example: | |
1a4d82fc JJ |
623 | /// |
624 | /// ``` | |
625 | /// type Func<A> = fn(A); | |
626 | /// type MetaFunc = for<'a> fn(Func<&'a int>) | |
627 | /// ``` | |
628 | /// | |
629 | /// The type `MetaFunc`, when fully expanded, will be | |
630 | /// | |
631 | /// for<'a> fn(fn(&'a int)) | |
632 | /// ^~ ^~ ^~~ | |
633 | /// | | | | |
634 | /// | | DebruijnIndex of 2 | |
635 | /// Binders | |
636 | /// | |
637 | /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the | |
638 | /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip | |
9fa01778 | 639 | /// over the inner binder (remember that we count De Bruijn indices from 1). However, in the |
1a4d82fc | 640 | /// definition of `MetaFunc`, the binder is not visible, so the type `&'a int` will have a |
9fa01778 | 641 | /// De Bruijn index of 1. It's only during the substitution that we can see we must increase the |
1a4d82fc JJ |
642 | /// depth by 1 to account for the binder that we passed through. |
643 | /// | |
644 | /// As a second example, consider this twist: | |
645 | /// | |
646 | /// ``` | |
647 | /// type FuncTuple<A> = (A,fn(A)); | |
648 | /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>) | |
649 | /// ``` | |
650 | /// | |
651 | /// Here the final type will be: | |
652 | /// | |
653 | /// for<'a> fn((&'a int, fn(&'a int))) | |
654 | /// ^~~ ^~~ | |
655 | /// | | | |
656 | /// DebruijnIndex of 1 | | |
657 | /// DebruijnIndex of 2 | |
658 | /// | |
659 | /// As indicated in the diagram, here the same type `&'a int` is substituted once, but in the | |
9fa01778 | 660 | /// first case we do not increase the De Bruijn index and in the second case we do. The reason |
1a4d82fc | 661 | /// is that only in the second case have we passed through a fn binder. |
48663c56 | 662 | fn shift_vars_through_binders<T: TypeFoldable<'tcx>>(&self, val: T) -> T { |
dfeec247 XL |
663 | debug!( |
664 | "shift_vars(val={:?}, binders_passed={:?}, has_escaping_bound_vars={:?})", | |
665 | val, | |
666 | self.binders_passed, | |
667 | val.has_escaping_bound_vars() | |
668 | ); | |
1a4d82fc | 669 | |
48663c56 XL |
670 | if self.binders_passed == 0 || !val.has_escaping_bound_vars() { |
671 | return val; | |
970d7e83 | 672 | } |
1a4d82fc | 673 | |
48663c56 | 674 | let result = ty::fold::shift_vars(self.tcx(), &val, self.binders_passed); |
a1dfa0c6 | 675 | debug!("shift_vars: shifted result = {:?}", result); |
1a4d82fc JJ |
676 | |
677 | result | |
678 | } | |
679 | ||
7cac9316 | 680 | fn shift_region_through_binders(&self, region: ty::Region<'tcx>) -> ty::Region<'tcx> { |
a1dfa0c6 | 681 | if self.binders_passed == 0 || !region.has_escaping_bound_vars() { |
cc61c64b XL |
682 | return region; |
683 | } | |
a1dfa0c6 | 684 | ty::fold::shift_region(self.tcx, region, self.binders_passed) |
9e0c209e SL |
685 | } |
686 | } | |
0bf4aa26 XL |
687 | |
688 | pub type CanonicalUserSubsts<'tcx> = Canonical<'tcx, UserSubsts<'tcx>>; | |
689 | ||
0bf4aa26 XL |
690 | /// Stores the user-given substs to reach some fully qualified path |
691 | /// (e.g., `<T>::Item` or `<T as Trait>::Item`). | |
60c5eb7d XL |
692 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)] |
693 | #[derive(HashStable, TypeFoldable, Lift)] | |
0bf4aa26 XL |
694 | pub struct UserSubsts<'tcx> { |
695 | /// The substitutions for the item as given by the user. | |
532ac7d7 | 696 | pub substs: SubstsRef<'tcx>, |
0bf4aa26 | 697 | |
9fa01778 | 698 | /// The self type, in the case of a `<T>::Item` path (when applied |
0bf4aa26 XL |
699 | /// to an inherent impl). See `UserSelfTy` below. |
700 | pub user_self_ty: Option<UserSelfTy<'tcx>>, | |
701 | } | |
702 | ||
9fa01778 XL |
703 | /// Specifies the user-given self type. In the case of a path that |
704 | /// refers to a member in an inherent impl, this self type is | |
0bf4aa26 XL |
705 | /// sometimes needed to constrain the type parameters on the impl. For |
706 | /// example, in this code: | |
707 | /// | |
708 | /// ``` | |
709 | /// struct Foo<T> { } | |
710 | /// impl<A> Foo<A> { fn method() { } } | |
711 | /// ``` | |
712 | /// | |
713 | /// when you then have a path like `<Foo<&'static u32>>::method`, | |
9fa01778 XL |
714 | /// this struct would carry the `DefId` of the impl along with the |
715 | /// self type `Foo<u32>`. Then we can instantiate the parameters of | |
0bf4aa26 | 716 | /// the impl (with the substs from `UserSubsts`) and apply those to |
9fa01778 XL |
717 | /// the self type, giving `Foo<?A>`. Finally, we unify that with |
718 | /// the self type here, which contains `?A` to be `&'static u32` | |
60c5eb7d XL |
719 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)] |
720 | #[derive(HashStable, TypeFoldable, Lift)] | |
0bf4aa26 XL |
721 | pub struct UserSelfTy<'tcx> { |
722 | pub impl_def_id: DefId, | |
723 | pub self_ty: Ty<'tcx>, | |
724 | } |