3 use crate::ty
::codec
::{TyDecoder, TyEncoder}
;
4 use crate::ty
::fold
::{FallibleTypeFolder, TypeFoldable, TypeFolder, TypeSuperFoldable}
;
5 use crate::ty
::sty
::{ClosureArgs, GeneratorArgs, InlineConstArgs}
;
6 use crate::ty
::visit
::{TypeVisitable, TypeVisitableExt, TypeVisitor}
;
7 use crate::ty
::{self, Lift, List, ParamConst, Ty, TyCtxt}
;
9 use rustc_data_structures
::intern
::Interned
;
10 use rustc_errors
::{DiagnosticArgValue, IntoDiagnosticArg}
;
11 use rustc_hir
::def_id
::DefId
;
12 use rustc_macros
::HashStable
;
13 use rustc_serialize
::{self, Decodable, Encodable}
;
15 use rustc_type_ir
::WithCachedTypeInfo
;
16 use smallvec
::SmallVec
;
19 use std
::cmp
::Ordering
;
20 use std
::marker
::PhantomData
;
22 use std
::num
::NonZeroUsize
;
23 use std
::ops
::{ControlFlow, Deref}
;
25 /// An entity in the Rust type system, which can be one of
26 /// several kinds (types, lifetimes, and consts).
27 /// To reduce memory usage, a `GenericArg` is an interned pointer,
28 /// with the lowest 2 bits being reserved for a tag to
29 /// indicate the type (`Ty`, `Region`, or `Const`) it points to.
31 /// Note: the `PartialEq`, `Eq` and `Hash` derives are only valid because `Ty`,
32 /// `Region` and `Const` are all interned.
33 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
34 pub struct GenericArg
<'tcx
> {
36 marker
: PhantomData
<(Ty
<'tcx
>, ty
::Region
<'tcx
>, ty
::Const
<'tcx
>)>,
39 impl<'tcx
> IntoDiagnosticArg
for GenericArg
<'tcx
> {
40 fn into_diagnostic_arg(self) -> DiagnosticArgValue
<'
static> {
41 self.to_string().into_diagnostic_arg()
45 const TAG_MASK
: usize = 0b11;
46 const TYPE_TAG
: usize = 0b00;
47 const REGION_TAG
: usize = 0b01;
48 const CONST_TAG
: usize = 0b10;
50 #[derive(Debug, TyEncodable, TyDecodable, PartialEq, Eq, PartialOrd, Ord, HashStable)]
51 pub enum GenericArgKind
<'tcx
> {
52 Lifetime(ty
::Region
<'tcx
>),
54 Const(ty
::Const
<'tcx
>),
57 impl<'tcx
> GenericArgKind
<'tcx
> {
59 fn pack(self) -> GenericArg
<'tcx
> {
60 let (tag
, ptr
) = match self {
61 GenericArgKind
::Lifetime(lt
) => {
62 // Ensure we can use the tag bits.
63 assert_eq
!(mem
::align_of_val(&*lt
.0.0) & TAG_MASK
, 0);
64 (REGION_TAG
, lt
.0.0 as *const ty
::RegionKind
<'tcx
> as usize)
66 GenericArgKind
::Type(ty
) => {
67 // Ensure we can use the tag bits.
68 assert_eq
!(mem
::align_of_val(&*ty
.0.0) & TAG_MASK
, 0);
69 (TYPE_TAG
, ty
.0.0 as *const WithCachedTypeInfo
<ty
::TyKind
<'tcx
>> as usize)
71 GenericArgKind
::Const(ct
) => {
72 // Ensure we can use the tag bits.
73 assert_eq
!(mem
::align_of_val(&*ct
.0.0) & TAG_MASK
, 0);
74 (CONST_TAG
, ct
.0.0 as *const ty
::ConstData
<'tcx
> as usize)
78 GenericArg { ptr: unsafe { NonZeroUsize::new_unchecked(ptr | tag) }
, marker
: PhantomData
}
82 impl<'tcx
> Ord
for GenericArg
<'tcx
> {
83 fn cmp(&self, other
: &GenericArg
<'tcx
>) -> Ordering
{
84 self.unpack().cmp(&other
.unpack())
88 impl<'tcx
> PartialOrd
for GenericArg
<'tcx
> {
89 fn partial_cmp(&self, other
: &GenericArg
<'tcx
>) -> Option
<Ordering
> {
90 Some(self.cmp(&other
))
94 impl<'tcx
> From
<ty
::Region
<'tcx
>> for GenericArg
<'tcx
> {
96 fn from(r
: ty
::Region
<'tcx
>) -> GenericArg
<'tcx
> {
97 GenericArgKind
::Lifetime(r
).pack()
101 impl<'tcx
> From
<Ty
<'tcx
>> for GenericArg
<'tcx
> {
103 fn from(ty
: Ty
<'tcx
>) -> GenericArg
<'tcx
> {
104 GenericArgKind
::Type(ty
).pack()
108 impl<'tcx
> From
<ty
::Const
<'tcx
>> for GenericArg
<'tcx
> {
110 fn from(c
: ty
::Const
<'tcx
>) -> GenericArg
<'tcx
> {
111 GenericArgKind
::Const(c
).pack()
115 impl<'tcx
> From
<ty
::Term
<'tcx
>> for GenericArg
<'tcx
> {
116 fn from(value
: ty
::Term
<'tcx
>) -> Self {
117 match value
.unpack() {
118 ty
::TermKind
::Ty(t
) => t
.into(),
119 ty
::TermKind
::Const(c
) => c
.into(),
124 impl<'tcx
> GenericArg
<'tcx
> {
126 pub fn unpack(self) -> GenericArgKind
<'tcx
> {
127 let ptr
= self.ptr
.get();
128 // SAFETY: use of `Interned::new_unchecked` here is ok because these
129 // pointers were originally created from `Interned` types in `pack()`,
130 // and this is just going in the other direction.
132 match ptr
& TAG_MASK
{
133 REGION_TAG
=> GenericArgKind
::Lifetime(ty
::Region(Interned
::new_unchecked(
134 &*((ptr
& !TAG_MASK
) as *const ty
::RegionKind
<'tcx
>),
136 TYPE_TAG
=> GenericArgKind
::Type(Ty(Interned
::new_unchecked(
137 &*((ptr
& !TAG_MASK
) as *const WithCachedTypeInfo
<ty
::TyKind
<'tcx
>>),
139 CONST_TAG
=> GenericArgKind
::Const(ty
::Const(Interned
::new_unchecked(
140 &*((ptr
& !TAG_MASK
) as *const ty
::ConstData
<'tcx
>),
142 _
=> intrinsics
::unreachable(),
148 pub fn as_type(self) -> Option
<Ty
<'tcx
>> {
149 match self.unpack() {
150 GenericArgKind
::Type(ty
) => Some(ty
),
156 pub fn as_region(self) -> Option
<ty
::Region
<'tcx
>> {
157 match self.unpack() {
158 GenericArgKind
::Lifetime(re
) => Some(re
),
164 pub fn as_const(self) -> Option
<ty
::Const
<'tcx
>> {
165 match self.unpack() {
166 GenericArgKind
::Const(ct
) => Some(ct
),
171 /// Unpack the `GenericArg` as a region when it is known certainly to be a region.
172 pub fn expect_region(self) -> ty
::Region
<'tcx
> {
173 self.as_region().unwrap_or_else(|| bug
!("expected a region, but found another kind"))
176 /// Unpack the `GenericArg` as a type when it is known certainly to be a type.
177 /// This is true in cases where `GenericArgs` is used in places where the kinds are known
178 /// to be limited (e.g. in tuples, where the only parameters are type parameters).
179 pub fn expect_ty(self) -> Ty
<'tcx
> {
180 self.as_type().unwrap_or_else(|| bug
!("expected a type, but found another kind"))
183 /// Unpack the `GenericArg` as a const when it is known certainly to be a const.
184 pub fn expect_const(self) -> ty
::Const
<'tcx
> {
185 self.as_const().unwrap_or_else(|| bug
!("expected a const, but found another kind"))
188 pub fn is_non_region_infer(self) -> bool
{
189 match self.unpack() {
190 GenericArgKind
::Lifetime(_
) => false,
191 GenericArgKind
::Type(ty
) => ty
.is_ty_or_numeric_infer(),
192 GenericArgKind
::Const(ct
) => ct
.is_ct_infer(),
197 impl<'a
, 'tcx
> Lift
<'tcx
> for GenericArg
<'a
> {
198 type Lifted
= GenericArg
<'tcx
>;
200 fn lift_to_tcx(self, tcx
: TyCtxt
<'tcx
>) -> Option
<Self::Lifted
> {
201 match self.unpack() {
202 GenericArgKind
::Lifetime(lt
) => tcx
.lift(lt
).map(|lt
| lt
.into()),
203 GenericArgKind
::Type(ty
) => tcx
.lift(ty
).map(|ty
| ty
.into()),
204 GenericArgKind
::Const(ct
) => tcx
.lift(ct
).map(|ct
| ct
.into()),
209 impl<'tcx
> TypeFoldable
<TyCtxt
<'tcx
>> for GenericArg
<'tcx
> {
210 fn try_fold_with
<F
: FallibleTypeFolder
<TyCtxt
<'tcx
>>>(
213 ) -> Result
<Self, F
::Error
> {
214 match self.unpack() {
215 GenericArgKind
::Lifetime(lt
) => lt
.try_fold_with(folder
).map(Into
::into
),
216 GenericArgKind
::Type(ty
) => ty
.try_fold_with(folder
).map(Into
::into
),
217 GenericArgKind
::Const(ct
) => ct
.try_fold_with(folder
).map(Into
::into
),
222 impl<'tcx
> TypeVisitable
<TyCtxt
<'tcx
>> for GenericArg
<'tcx
> {
223 fn visit_with
<V
: TypeVisitor
<TyCtxt
<'tcx
>>>(&self, visitor
: &mut V
) -> ControlFlow
<V
::BreakTy
> {
224 match self.unpack() {
225 GenericArgKind
::Lifetime(lt
) => lt
.visit_with(visitor
),
226 GenericArgKind
::Type(ty
) => ty
.visit_with(visitor
),
227 GenericArgKind
::Const(ct
) => ct
.visit_with(visitor
),
232 impl<'tcx
, E
: TyEncoder
<I
= TyCtxt
<'tcx
>>> Encodable
<E
> for GenericArg
<'tcx
> {
233 fn encode(&self, e
: &mut E
) {
234 self.unpack().encode(e
)
238 impl<'tcx
, D
: TyDecoder
<I
= TyCtxt
<'tcx
>>> Decodable
<D
> for GenericArg
<'tcx
> {
239 fn decode(d
: &mut D
) -> GenericArg
<'tcx
> {
240 GenericArgKind
::decode(d
).pack()
244 /// List of generic arguments that are gonna be used to replace generic parameters.
245 pub type GenericArgs
<'tcx
> = List
<GenericArg
<'tcx
>>;
247 pub type GenericArgsRef
<'tcx
> = &'tcx GenericArgs
<'tcx
>;
249 impl<'tcx
> GenericArgs
<'tcx
> {
250 /// Converts generic args to a type list.
254 /// If any of the generic arguments are not types.
255 pub fn into_type_list(&self, tcx
: TyCtxt
<'tcx
>) -> &'tcx List
<Ty
<'tcx
>> {
256 tcx
.mk_type_list_from_iter(self.iter().map(|arg
| match arg
.unpack() {
257 GenericArgKind
::Type(ty
) => ty
,
258 _
=> bug
!("`into_type_list` called on generic arg with non-types"),
262 /// Interpret these generic args as the args of a closure type.
263 /// Closure args have a particular structure controlled by the
264 /// compiler that encodes information like the signature and closure kind;
265 /// see `ty::ClosureArgs` struct for more comments.
266 pub fn as_closure(&'tcx
self) -> ClosureArgs
<'tcx
> {
267 ClosureArgs { args: self }
270 /// Interpret these generic args as the args of a generator type.
271 /// Generator args have a particular structure controlled by the
272 /// compiler that encodes information like the signature and generator kind;
273 /// see `ty::GeneratorArgs` struct for more comments.
274 pub fn as_generator(&'tcx
self) -> GeneratorArgs
<'tcx
> {
275 GeneratorArgs { args: self }
278 /// Interpret these generic args as the args of an inline const.
279 /// Inline const args have a particular structure controlled by the
280 /// compiler that encodes information like the inferred type;
281 /// see `ty::InlineConstArgs` struct for more comments.
282 pub fn as_inline_const(&'tcx
self) -> InlineConstArgs
<'tcx
> {
283 InlineConstArgs { args: self }
286 /// Creates an `GenericArgs` that maps each generic parameter to itself.
287 pub fn identity_for_item(tcx
: TyCtxt
<'tcx
>, def_id
: impl Into
<DefId
>) -> GenericArgsRef
<'tcx
> {
288 Self::for_item(tcx
, def_id
.into(), |param
, _
| tcx
.mk_param_from_def(param
))
291 /// Creates an `GenericArgs` for generic parameter definitions,
292 /// by calling closures to obtain each kind.
293 /// The closures get to observe the `GenericArgs` as they're
294 /// being built, which can be used to correctly
295 /// replace defaults of generic parameters.
296 pub fn for_item
<F
>(tcx
: TyCtxt
<'tcx
>, def_id
: DefId
, mut mk_kind
: F
) -> GenericArgsRef
<'tcx
>
298 F
: FnMut(&ty
::GenericParamDef
, &[GenericArg
<'tcx
>]) -> GenericArg
<'tcx
>,
300 let defs
= tcx
.generics_of(def_id
);
301 let count
= defs
.count();
302 let mut args
= SmallVec
::with_capacity(count
);
303 Self::fill_item(&mut args
, tcx
, defs
, &mut mk_kind
);
312 ) -> GenericArgsRef
<'tcx
>
314 F
: FnMut(&ty
::GenericParamDef
, &[GenericArg
<'tcx
>]) -> GenericArg
<'tcx
>,
316 Self::for_item(tcx
, def_id
, |param
, args
| {
317 self.get(param
.index
as usize).cloned().unwrap_or_else(|| mk_kind(param
, args
))
322 args
: &mut SmallVec
<[GenericArg
<'tcx
>; 8]>,
327 F
: FnMut(&ty
::GenericParamDef
, &[GenericArg
<'tcx
>]) -> GenericArg
<'tcx
>,
329 if let Some(def_id
) = defs
.parent
{
330 let parent_defs
= tcx
.generics_of(def_id
);
331 Self::fill_item(args
, tcx
, parent_defs
, mk_kind
);
333 Self::fill_single(args
, defs
, mk_kind
)
336 pub fn fill_single
<F
>(
337 args
: &mut SmallVec
<[GenericArg
<'tcx
>; 8]>,
341 F
: FnMut(&ty
::GenericParamDef
, &[GenericArg
<'tcx
>]) -> GenericArg
<'tcx
>,
343 args
.reserve(defs
.params
.len());
344 for param
in &defs
.params
{
345 let kind
= mk_kind(param
, args
);
346 assert_eq
!(param
.index
as usize, args
.len(), "{args:#?}, {defs:#?}");
351 // Extend an `original_args` list to the full number of args expected by `def_id`,
352 // filling in the missing parameters with error ty/ct or 'static regions.
353 pub fn extend_with_error(
356 original_args
: &[GenericArg
<'tcx
>],
357 ) -> GenericArgsRef
<'tcx
> {
358 ty
::GenericArgs
::for_item(tcx
, def_id
, |def
, args
| {
359 if let Some(arg
) = original_args
.get(def
.index
as usize) {
362 def
.to_error(tcx
, args
)
368 pub fn types(&'tcx
self) -> impl DoubleEndedIterator
<Item
= Ty
<'tcx
>> + 'tcx
{
369 self.iter().filter_map(|k
| k
.as_type())
373 pub fn regions(&'tcx
self) -> impl DoubleEndedIterator
<Item
= ty
::Region
<'tcx
>> + 'tcx
{
374 self.iter().filter_map(|k
| k
.as_region())
378 pub fn consts(&'tcx
self) -> impl DoubleEndedIterator
<Item
= ty
::Const
<'tcx
>> + 'tcx
{
379 self.iter().filter_map(|k
| k
.as_const())
382 /// Returns generic arguments that are not lifetimes or host effect params.
384 pub fn non_erasable_generics(
388 ) -> impl DoubleEndedIterator
<Item
= GenericArgKind
<'tcx
>> + 'tcx
{
389 let generics
= tcx
.generics_of(def_id
);
390 self.iter().enumerate().filter_map(|(i
, k
)| match k
.unpack() {
391 _
if Some(i
) == generics
.host_effect_index
=> None
,
392 ty
::GenericArgKind
::Lifetime(_
) => None
,
393 generic
=> Some(generic
),
399 pub fn type_at(&self, i
: usize) -> Ty
<'tcx
> {
400 self[i
].as_type().unwrap_or_else(|| bug
!("expected type for param #{} in {:?}", i
, self))
405 pub fn region_at(&self, i
: usize) -> ty
::Region
<'tcx
> {
408 .unwrap_or_else(|| bug
!("expected region for param #{} in {:?}", i
, self))
413 pub fn const_at(&self, i
: usize) -> ty
::Const
<'tcx
> {
414 self[i
].as_const().unwrap_or_else(|| bug
!("expected const for param #{} in {:?}", i
, self))
419 pub fn type_for_def(&self, def
: &ty
::GenericParamDef
) -> GenericArg
<'tcx
> {
420 self.type_at(def
.index
as usize).into()
423 /// Transform from generic args for a child of `source_ancestor`
424 /// (e.g., a trait or impl) to args for the same child
425 /// in a different item, with `target_args` as the base for
426 /// the target impl/trait, with the source child-specific
427 /// parameters (e.g., method parameters) on top of that base.
429 /// For example given:
432 /// trait X<S> { fn f<T>(); }
433 /// impl<U> X<U> for U { fn f<V>() {} }
436 /// * If `self` is `[Self, S, T]`: the identity args of `f` in the trait.
437 /// * If `source_ancestor` is the def_id of the trait.
438 /// * If `target_args` is `[U]`, the args for the impl.
439 /// * Then we will return `[U, T]`, the arg for `f` in the impl that
440 /// are needed for it to match the trait.
444 source_ancestor
: DefId
,
445 target_args
: GenericArgsRef
<'tcx
>,
446 ) -> GenericArgsRef
<'tcx
> {
447 let defs
= tcx
.generics_of(source_ancestor
);
448 tcx
.mk_args_from_iter(target_args
.iter().chain(self.iter().skip(defs
.count())))
451 pub fn truncate_to(&self, tcx
: TyCtxt
<'tcx
>, generics
: &ty
::Generics
) -> GenericArgsRef
<'tcx
> {
452 tcx
.mk_args_from_iter(self.iter().take(generics
.count()))
455 pub fn host_effect_param(&'tcx
self) -> Option
<ty
::Const
<'tcx
>> {
456 self.consts().rfind(|x
| matches
!(x
.kind(), ty
::ConstKind
::Param(p
) if p
.name
== sym
::host
))
459 pub fn print_as_list(&self) -> String
{
460 let v
= self.iter().map(|arg
| arg
.to_string()).collect
::<Vec
<_
>>();
461 format
!("[{}]", v
.join(", "))
465 impl<'tcx
> TypeFoldable
<TyCtxt
<'tcx
>> for GenericArgsRef
<'tcx
> {
466 fn try_fold_with
<F
: FallibleTypeFolder
<TyCtxt
<'tcx
>>>(
469 ) -> Result
<Self, F
::Error
> {
470 // This code is hot enough that it's worth specializing for the most
471 // common length lists, to avoid the overhead of `SmallVec` creation.
472 // The match arms are in order of frequency. The 1, 2, and 0 cases are
473 // typically hit in 90--99.99% of cases. When folding doesn't change
474 // the args, it's faster to reuse the existing args rather than
475 // calling `mk_args`.
478 let param0
= self[0].try_fold_with(folder
)?
;
479 if param0
== self[0] { Ok(self) }
else { Ok(folder.interner().mk_args(&[param0])) }
482 let param0
= self[0].try_fold_with(folder
)?
;
483 let param1
= self[1].try_fold_with(folder
)?
;
484 if param0
== self[0] && param1
== self[1] {
487 Ok(folder
.interner().mk_args(&[param0
, param1
]))
491 _
=> ty
::util
::fold_list(self, folder
, |tcx
, v
| tcx
.mk_args(v
)),
496 impl<'tcx
> TypeFoldable
<TyCtxt
<'tcx
>> for &'tcx ty
::List
<Ty
<'tcx
>> {
497 fn try_fold_with
<F
: FallibleTypeFolder
<TyCtxt
<'tcx
>>>(
500 ) -> Result
<Self, F
::Error
> {
501 // This code is fairly hot, though not as hot as `GenericArgsRef`.
503 // When compiling stage 2, I get the following results:
506 // --- | --------- | -----
507 // 2 | 15083590 | 48.1
508 // 3 | 7540067 | 24.0
509 // 1 | 5300377 | 16.9
513 // I've tried it with some private repositories and got
514 // close to the same result, with 4 and 0 swapping places
518 let param0
= self[0].try_fold_with(folder
)?
;
519 let param1
= self[1].try_fold_with(folder
)?
;
520 if param0
== self[0] && param1
== self[1] {
523 Ok(folder
.interner().mk_type_list(&[param0
, param1
]))
526 _
=> ty
::util
::fold_list(self, folder
, |tcx
, v
| tcx
.mk_type_list(v
)),
531 impl<'tcx
, T
: TypeVisitable
<TyCtxt
<'tcx
>>> TypeVisitable
<TyCtxt
<'tcx
>> for &'tcx ty
::List
<T
> {
533 fn visit_with
<V
: TypeVisitor
<TyCtxt
<'tcx
>>>(&self, visitor
: &mut V
) -> ControlFlow
<V
::BreakTy
> {
534 self.iter().try_for_each(|t
| t
.visit_with(visitor
))
538 /// Similar to [`super::Binder`] except that it tracks early bound generics, i.e. `struct Foo<T>(T)`
539 /// needs `T` instantiated immediately. This type primarily exists to avoid forgetting to call
542 /// If you don't have anything to `instantiate`, you may be looking for
543 /// [`instantiate_identity`](EarlyBinder::instantiate_identity) or [`skip_binder`](EarlyBinder::skip_binder).
544 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
545 #[derive(Encodable, Decodable, HashStable)]
546 pub struct EarlyBinder
<T
> {
550 /// For early binders, you should first call `instantiate` before using any visitors.
551 impl<'tcx
, T
> !TypeFoldable
<TyCtxt
<'tcx
>> for ty
::EarlyBinder
<T
> {}
552 impl<'tcx
, T
> !TypeVisitable
<TyCtxt
<'tcx
>> for ty
::EarlyBinder
<T
> {}
554 impl<T
> EarlyBinder
<T
> {
555 pub fn bind(value
: T
) -> EarlyBinder
<T
> {
556 EarlyBinder { value }
559 pub fn as_ref(&self) -> EarlyBinder
<&T
> {
560 EarlyBinder { value: &self.value }
563 pub fn map_bound_ref
<F
, U
>(&self, f
: F
) -> EarlyBinder
<U
>
567 self.as_ref().map_bound(f
)
570 pub fn map_bound
<F
, U
>(self, f
: F
) -> EarlyBinder
<U
>
574 let value
= f(self.value
);
575 EarlyBinder { value }
578 pub fn try_map_bound
<F
, U
, E
>(self, f
: F
) -> Result
<EarlyBinder
<U
>, E
>
580 F
: FnOnce(T
) -> Result
<U
, E
>,
582 let value
= f(self.value
)?
;
583 Ok(EarlyBinder { value }
)
586 pub fn rebind
<U
>(&self, value
: U
) -> EarlyBinder
<U
> {
587 EarlyBinder { value }
590 /// Skips the binder and returns the "bound" value.
591 /// This can be used to extract data that does not depend on generic parameters
592 /// (e.g., getting the `DefId` of the inner value or getting the number of
593 /// arguments of an `FnSig`). Otherwise, consider using
594 /// [`instantiate_identity`](EarlyBinder::instantiate_identity).
596 /// To skip the binder on `x: &EarlyBinder<T>` to obtain `&T`, leverage
597 /// [`EarlyBinder::as_ref`](EarlyBinder::as_ref): `x.as_ref().skip_binder()`.
599 /// See also [`Binder::skip_binder`](super::Binder::skip_binder), which is
600 /// the analogous operation on [`super::Binder`].
601 pub fn skip_binder(self) -> T
{
606 impl<T
> EarlyBinder
<Option
<T
>> {
607 pub fn transpose(self) -> Option
<EarlyBinder
<T
>> {
608 self.value
.map(|value
| EarlyBinder { value }
)
612 impl<T
, U
> EarlyBinder
<(T
, U
)> {
613 pub fn transpose_tuple2(self) -> (EarlyBinder
<T
>, EarlyBinder
<U
>) {
614 let EarlyBinder { value: (lhs, rhs) }
= self;
615 (EarlyBinder { value: lhs }
, EarlyBinder { value: rhs }
)
619 impl<'tcx
, 's
, I
: IntoIterator
> EarlyBinder
<I
>
621 I
::Item
: TypeFoldable
<TyCtxt
<'tcx
>>,
623 pub fn iter_instantiated(
626 args
: &'s
[GenericArg
<'tcx
>],
627 ) -> IterInstantiated
<'s
, 'tcx
, I
> {
628 IterInstantiated { it: self.value.into_iter(), tcx, args }
631 /// Similar to [`instantiate_identity`](EarlyBinder::instantiate_identity),
632 /// but on an iterator of `TypeFoldable` values.
633 pub fn instantiate_identity_iter(self) -> I
::IntoIter
{
634 self.value
.into_iter()
638 pub struct IterInstantiated
<'s
, 'tcx
, I
: IntoIterator
> {
641 args
: &'s
[GenericArg
<'tcx
>],
644 impl<'tcx
, I
: IntoIterator
> Iterator
for IterInstantiated
<'_
, 'tcx
, I
>
646 I
::Item
: TypeFoldable
<TyCtxt
<'tcx
>>,
650 fn next(&mut self) -> Option
<Self::Item
> {
651 Some(EarlyBinder { value: self.it.next()? }
.instantiate(self.tcx
, self.args
))
654 fn size_hint(&self) -> (usize, Option
<usize>) {
659 impl<'tcx
, I
: IntoIterator
> DoubleEndedIterator
for IterInstantiated
<'_
, 'tcx
, I
>
661 I
::IntoIter
: DoubleEndedIterator
,
662 I
::Item
: TypeFoldable
<TyCtxt
<'tcx
>>,
664 fn next_back(&mut self) -> Option
<Self::Item
> {
665 Some(EarlyBinder { value: self.it.next_back()? }
.instantiate(self.tcx
, self.args
))
669 impl<'tcx
, I
: IntoIterator
> ExactSizeIterator
for IterInstantiated
<'_
, 'tcx
, I
>
671 I
::IntoIter
: ExactSizeIterator
,
672 I
::Item
: TypeFoldable
<TyCtxt
<'tcx
>>,
676 impl<'tcx
, 's
, I
: IntoIterator
> EarlyBinder
<I
>
679 <I
::Item
as Deref
>::Target
: Copy
+ TypeFoldable
<TyCtxt
<'tcx
>>,
681 pub fn iter_instantiated_copied(
684 args
: &'s
[GenericArg
<'tcx
>],
685 ) -> IterInstantiatedCopied
<'s
, 'tcx
, I
> {
686 IterInstantiatedCopied { it: self.value.into_iter(), tcx, args }
689 /// Similar to [`instantiate_identity`](EarlyBinder::instantiate_identity),
690 /// but on an iterator of values that deref to a `TypeFoldable`.
691 pub fn instantiate_identity_iter_copied(
693 ) -> impl Iterator
<Item
= <I
::Item
as Deref
>::Target
> {
694 self.value
.into_iter().map(|v
| *v
)
698 pub struct IterInstantiatedCopied
<'a
, 'tcx
, I
: IntoIterator
> {
701 args
: &'a
[GenericArg
<'tcx
>],
704 impl<'tcx
, I
: IntoIterator
> Iterator
for IterInstantiatedCopied
<'_
, 'tcx
, I
>
707 <I
::Item
as Deref
>::Target
: Copy
+ TypeFoldable
<TyCtxt
<'tcx
>>,
709 type Item
= <I
::Item
as Deref
>::Target
;
711 fn next(&mut self) -> Option
<Self::Item
> {
712 self.it
.next().map(|value
| EarlyBinder { value: *value }
.instantiate(self.tcx
, self.args
))
715 fn size_hint(&self) -> (usize, Option
<usize>) {
720 impl<'tcx
, I
: IntoIterator
> DoubleEndedIterator
for IterInstantiatedCopied
<'_
, 'tcx
, I
>
722 I
::IntoIter
: DoubleEndedIterator
,
724 <I
::Item
as Deref
>::Target
: Copy
+ TypeFoldable
<TyCtxt
<'tcx
>>,
726 fn next_back(&mut self) -> Option
<Self::Item
> {
729 .map(|value
| EarlyBinder { value: *value }
.instantiate(self.tcx
, self.args
))
733 impl<'tcx
, I
: IntoIterator
> ExactSizeIterator
for IterInstantiatedCopied
<'_
, 'tcx
, I
>
735 I
::IntoIter
: ExactSizeIterator
,
737 <I
::Item
as Deref
>::Target
: Copy
+ TypeFoldable
<TyCtxt
<'tcx
>>,
741 pub struct EarlyBinderIter
<T
> {
745 impl<T
: IntoIterator
> EarlyBinder
<T
> {
746 pub fn transpose_iter(self) -> EarlyBinderIter
<T
::IntoIter
> {
747 EarlyBinderIter { t: self.value.into_iter() }
751 impl<T
: Iterator
> Iterator
for EarlyBinderIter
<T
> {
752 type Item
= EarlyBinder
<T
::Item
>;
754 fn next(&mut self) -> Option
<Self::Item
> {
755 self.t
.next().map(|value
| EarlyBinder { value }
)
758 fn size_hint(&self) -> (usize, Option
<usize>) {
763 impl<'tcx
, T
: TypeFoldable
<TyCtxt
<'tcx
>>> ty
::EarlyBinder
<T
> {
764 pub fn instantiate(self, tcx
: TyCtxt
<'tcx
>, args
: &[GenericArg
<'tcx
>]) -> T
{
765 let mut folder
= ArgFolder { tcx, args, binders_passed: 0 }
;
766 self.value
.fold_with(&mut folder
)
769 /// Makes the identity replacement `T0 => T0, ..., TN => TN`.
770 /// Conceptually, this converts universally bound variables into placeholders
771 /// when inside of a given item.
773 /// For example, consider `for<T> fn foo<T>(){ .. }`:
774 /// - Outside of `foo`, `T` is bound (represented by the presence of `EarlyBinder`).
775 /// - Inside of the body of `foo`, we treat `T` as a placeholder by calling
776 /// `instantiate_identity` to discharge the `EarlyBinder`.
777 pub fn instantiate_identity(self) -> T
{
781 /// Returns the inner value, but only if it contains no bound vars.
782 pub fn no_bound_vars(self) -> Option
<T
> {
783 if !self.value
.has_param() { Some(self.value) }
else { None }
787 ///////////////////////////////////////////////////////////////////////////
788 // The actual substitution engine itself is a type folder.
790 struct ArgFolder
<'a
, 'tcx
> {
792 args
: &'a
[GenericArg
<'tcx
>],
794 /// Number of region binders we have passed through while doing the substitution
798 impl<'a
, 'tcx
> TypeFolder
<TyCtxt
<'tcx
>> for ArgFolder
<'a
, 'tcx
> {
800 fn interner(&self) -> TyCtxt
<'tcx
> {
804 fn fold_binder
<T
: TypeFoldable
<TyCtxt
<'tcx
>>>(
806 t
: ty
::Binder
<'tcx
, T
>,
807 ) -> ty
::Binder
<'tcx
, T
> {
808 self.binders_passed
+= 1;
809 let t
= t
.super_fold_with(self);
810 self.binders_passed
-= 1;
814 fn fold_region(&mut self, r
: ty
::Region
<'tcx
>) -> ty
::Region
<'tcx
> {
817 fn region_param_out_of_range(data
: ty
::EarlyBoundRegion
, args
: &[GenericArg
<'_
>]) -> ! {
819 "Region parameter out of range when substituting in region {} (index={}, args = {:?})",
828 fn region_param_invalid(data
: ty
::EarlyBoundRegion
, other
: GenericArgKind
<'_
>) -> ! {
830 "Unexpected parameter {:?} when substituting in region {} (index={})",
837 // Note: This routine only handles regions that are bound on
838 // type declarations and other outer declarations, not those
839 // bound in *fn types*. Region substitution of the bound
840 // regions that appear in a function signature is done using
841 // the specialized routine `ty::replace_late_regions()`.
843 ty
::ReEarlyBound(data
) => {
844 let rk
= self.args
.get(data
.index
as usize).map(|k
| k
.unpack());
846 Some(GenericArgKind
::Lifetime(lt
)) => self.shift_region_through_binders(lt
),
847 Some(other
) => region_param_invalid(data
, other
),
848 None
=> region_param_out_of_range(data
, self.args
),
854 | ty
::RePlaceholder(_
)
856 | ty
::ReError(_
) => r
,
857 ty
::ReVar(_
) => bug
!("unexpected region: {r:?}"),
861 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
867 ty
::Param(p
) => self.ty_for_param(p
, t
),
868 _
=> t
.super_fold_with(self),
872 fn fold_const(&mut self, c
: ty
::Const
<'tcx
>) -> ty
::Const
<'tcx
> {
873 if let ty
::ConstKind
::Param(p
) = c
.kind() {
874 self.const_for_param(p
, c
)
876 c
.super_fold_with(self)
881 impl<'a
, 'tcx
> ArgFolder
<'a
, 'tcx
> {
882 fn ty_for_param(&self, p
: ty
::ParamTy
, source_ty
: Ty
<'tcx
>) -> Ty
<'tcx
> {
883 // Look up the type in the args. It really should be in there.
884 let opt_ty
= self.args
.get(p
.index
as usize).map(|k
| k
.unpack());
885 let ty
= match opt_ty
{
886 Some(GenericArgKind
::Type(ty
)) => ty
,
887 Some(kind
) => self.type_param_expected(p
, source_ty
, kind
),
888 None
=> self.type_param_out_of_range(p
, source_ty
),
891 self.shift_vars_through_binders(ty
)
896 fn type_param_expected(&self, p
: ty
::ParamTy
, ty
: Ty
<'tcx
>, kind
: GenericArgKind
<'tcx
>) -> ! {
898 "expected type for `{:?}` ({:?}/{}) but found {:?} when substituting, args={:?}",
909 fn type_param_out_of_range(&self, p
: ty
::ParamTy
, ty
: Ty
<'tcx
>) -> ! {
911 "type parameter `{:?}` ({:?}/{}) out of range when substituting, args={:?}",
919 fn const_for_param(&self, p
: ParamConst
, source_ct
: ty
::Const
<'tcx
>) -> ty
::Const
<'tcx
> {
920 // Look up the const in the args. It really should be in there.
921 let opt_ct
= self.args
.get(p
.index
as usize).map(|k
| k
.unpack());
922 let ct
= match opt_ct
{
923 Some(GenericArgKind
::Const(ct
)) => ct
,
924 Some(kind
) => self.const_param_expected(p
, source_ct
, kind
),
925 None
=> self.const_param_out_of_range(p
, source_ct
),
928 self.shift_vars_through_binders(ct
)
933 fn const_param_expected(
937 kind
: GenericArgKind
<'tcx
>,
940 "expected const for `{:?}` ({:?}/{}) but found {:?} when substituting args={:?}",
951 fn const_param_out_of_range(&self, p
: ty
::ParamConst
, ct
: ty
::Const
<'tcx
>) -> ! {
953 "const parameter `{:?}` ({:?}/{}) out of range when substituting args={:?}",
961 /// It is sometimes necessary to adjust the De Bruijn indices during substitution. This occurs
962 /// when we are substituting a type with escaping bound vars into a context where we have
963 /// passed through binders. That's quite a mouthful. Let's see an example:
966 /// type Func<A> = fn(A);
967 /// type MetaFunc = for<'a> fn(Func<&'a i32>);
970 /// The type `MetaFunc`, when fully expanded, will be
971 /// ```ignore (illustrative)
972 /// for<'a> fn(fn(&'a i32))
975 /// // | | DebruijnIndex of 2
978 /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
979 /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
980 /// over the inner binder (remember that we count De Bruijn indices from 1). However, in the
981 /// definition of `MetaFunc`, the binder is not visible, so the type `&'a i32` will have a
982 /// De Bruijn index of 1. It's only during the substitution that we can see we must increase the
983 /// depth by 1 to account for the binder that we passed through.
985 /// As a second example, consider this twist:
988 /// type FuncTuple<A> = (A,fn(A));
989 /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a i32>);
992 /// Here the final type will be:
993 /// ```ignore (illustrative)
994 /// for<'a> fn((&'a i32, fn(&'a i32)))
997 /// // DebruijnIndex of 1 |
998 /// // DebruijnIndex of 2
1000 /// As indicated in the diagram, here the same type `&'a i32` is substituted once, but in the
1001 /// first case we do not increase the De Bruijn index and in the second case we do. The reason
1002 /// is that only in the second case have we passed through a fn binder.
1003 fn shift_vars_through_binders
<T
: TypeFoldable
<TyCtxt
<'tcx
>>>(&self, val
: T
) -> T
{
1005 "shift_vars(val={:?}, binders_passed={:?}, has_escaping_bound_vars={:?})",
1007 self.binders_passed
,
1008 val
.has_escaping_bound_vars()
1011 if self.binders_passed
== 0 || !val
.has_escaping_bound_vars() {
1015 let result
= ty
::fold
::shift_vars(TypeFolder
::interner(self), val
, self.binders_passed
);
1016 debug
!("shift_vars: shifted result = {:?}", result
);
1021 fn shift_region_through_binders(&self, region
: ty
::Region
<'tcx
>) -> ty
::Region
<'tcx
> {
1022 if self.binders_passed
== 0 || !region
.has_escaping_bound_vars() {
1025 ty
::fold
::shift_region(self.tcx
, region
, self.binders_passed
)
1029 /// Stores the user-given args to reach some fully qualified path
1030 /// (e.g., `<T>::Item` or `<T as Trait>::Item`).
1031 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
1032 #[derive(HashStable, TypeFoldable, TypeVisitable)]
1033 pub struct UserArgs
<'tcx
> {
1034 /// The args for the item as given by the user.
1035 pub args
: GenericArgsRef
<'tcx
>,
1037 /// The self type, in the case of a `<T>::Item` path (when applied
1038 /// to an inherent impl). See `UserSelfTy` below.
1039 pub user_self_ty
: Option
<UserSelfTy
<'tcx
>>,
1042 /// Specifies the user-given self type. In the case of a path that
1043 /// refers to a member in an inherent impl, this self type is
1044 /// sometimes needed to constrain the type parameters on the impl. For
1045 /// example, in this code:
1047 /// ```ignore (illustrative)
1048 /// struct Foo<T> { }
1049 /// impl<A> Foo<A> { fn method() { } }
1052 /// when you then have a path like `<Foo<&'static u32>>::method`,
1053 /// this struct would carry the `DefId` of the impl along with the
1054 /// self type `Foo<u32>`. Then we can instantiate the parameters of
1055 /// the impl (with the args from `UserArgs`) and apply those to
1056 /// the self type, giving `Foo<?A>`. Finally, we unify that with
1057 /// the self type here, which contains `?A` to be `&'static u32`
1058 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
1059 #[derive(HashStable, TypeFoldable, TypeVisitable)]
1060 pub struct UserSelfTy
<'tcx
> {
1061 pub impl_def_id
: DefId
,
1062 pub self_ty
: Ty
<'tcx
>,