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