rustc_middle/ty/
generic_args.rs

1// Generic arguments.
2
3use core::intrinsics;
4use std::marker::PhantomData;
5use std::mem;
6use std::num::NonZero;
7use std::ptr::NonNull;
8
9use rustc_data_structures::intern::Interned;
10use rustc_errors::{DiagArgValue, IntoDiagArg};
11use rustc_hir::def_id::DefId;
12use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable, extension};
13use rustc_serialize::{Decodable, Encodable};
14use rustc_type_ir::WithCachedTypeInfo;
15use smallvec::SmallVec;
16
17use crate::ty::codec::{TyDecoder, TyEncoder};
18use crate::ty::fold::{FallibleTypeFolder, TypeFoldable};
19use crate::ty::visit::{TypeVisitable, TypeVisitor, VisitorResult, walk_visitable_list};
20use crate::ty::{
21    self, ClosureArgs, CoroutineArgs, CoroutineClosureArgs, InlineConstArgs, Lift, List, Ty, TyCtxt,
22};
23
24pub type GenericArgKind<'tcx> = rustc_type_ir::GenericArgKind<TyCtxt<'tcx>>;
25pub type TermKind<'tcx> = rustc_type_ir::TermKind<TyCtxt<'tcx>>;
26
27/// An entity in the Rust type system, which can be one of
28/// several kinds (types, lifetimes, and consts).
29/// To reduce memory usage, a `GenericArg` is an interned pointer,
30/// with the lowest 2 bits being reserved for a tag to
31/// indicate the type (`Ty`, `Region`, or `Const`) it points to.
32///
33/// Note: the `PartialEq`, `Eq` and `Hash` derives are only valid because `Ty`,
34/// `Region` and `Const` are all interned.
35#[derive(Copy, Clone, PartialEq, Eq, Hash)]
36pub struct GenericArg<'tcx> {
37    ptr: NonNull<()>,
38    marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>, ty::Const<'tcx>)>,
39}
40
41impl<'tcx> rustc_type_ir::inherent::GenericArg<TyCtxt<'tcx>> for GenericArg<'tcx> {}
42
43impl<'tcx> rustc_type_ir::inherent::GenericArgs<TyCtxt<'tcx>> for ty::GenericArgsRef<'tcx> {
44    fn rebase_onto(
45        self,
46        tcx: TyCtxt<'tcx>,
47        source_ancestor: DefId,
48        target_args: GenericArgsRef<'tcx>,
49    ) -> GenericArgsRef<'tcx> {
50        self.rebase_onto(tcx, source_ancestor, target_args)
51    }
52
53    fn type_at(self, i: usize) -> Ty<'tcx> {
54        self.type_at(i)
55    }
56
57    fn region_at(self, i: usize) -> ty::Region<'tcx> {
58        self.region_at(i)
59    }
60
61    fn const_at(self, i: usize) -> ty::Const<'tcx> {
62        self.const_at(i)
63    }
64
65    fn identity_for_item(tcx: TyCtxt<'tcx>, def_id: DefId) -> ty::GenericArgsRef<'tcx> {
66        GenericArgs::identity_for_item(tcx, def_id)
67    }
68
69    fn extend_with_error(
70        tcx: TyCtxt<'tcx>,
71        def_id: DefId,
72        original_args: &[ty::GenericArg<'tcx>],
73    ) -> ty::GenericArgsRef<'tcx> {
74        ty::GenericArgs::extend_with_error(tcx, def_id, original_args)
75    }
76
77    fn split_closure_args(self) -> ty::ClosureArgsParts<TyCtxt<'tcx>> {
78        match self[..] {
79            [ref parent_args @ .., closure_kind_ty, closure_sig_as_fn_ptr_ty, tupled_upvars_ty] => {
80                ty::ClosureArgsParts {
81                    parent_args,
82                    closure_kind_ty: closure_kind_ty.expect_ty(),
83                    closure_sig_as_fn_ptr_ty: closure_sig_as_fn_ptr_ty.expect_ty(),
84                    tupled_upvars_ty: tupled_upvars_ty.expect_ty(),
85                }
86            }
87            _ => bug!("closure args missing synthetics"),
88        }
89    }
90
91    fn split_coroutine_closure_args(self) -> ty::CoroutineClosureArgsParts<TyCtxt<'tcx>> {
92        match self[..] {
93            [
94                ref parent_args @ ..,
95                closure_kind_ty,
96                signature_parts_ty,
97                tupled_upvars_ty,
98                coroutine_captures_by_ref_ty,
99                coroutine_witness_ty,
100            ] => ty::CoroutineClosureArgsParts {
101                parent_args,
102                closure_kind_ty: closure_kind_ty.expect_ty(),
103                signature_parts_ty: signature_parts_ty.expect_ty(),
104                tupled_upvars_ty: tupled_upvars_ty.expect_ty(),
105                coroutine_captures_by_ref_ty: coroutine_captures_by_ref_ty.expect_ty(),
106                coroutine_witness_ty: coroutine_witness_ty.expect_ty(),
107            },
108            _ => bug!("closure args missing synthetics"),
109        }
110    }
111
112    fn split_coroutine_args(self) -> ty::CoroutineArgsParts<TyCtxt<'tcx>> {
113        match self[..] {
114            [
115                ref parent_args @ ..,
116                kind_ty,
117                resume_ty,
118                yield_ty,
119                return_ty,
120                witness,
121                tupled_upvars_ty,
122            ] => ty::CoroutineArgsParts {
123                parent_args,
124                kind_ty: kind_ty.expect_ty(),
125                resume_ty: resume_ty.expect_ty(),
126                yield_ty: yield_ty.expect_ty(),
127                return_ty: return_ty.expect_ty(),
128                witness: witness.expect_ty(),
129                tupled_upvars_ty: tupled_upvars_ty.expect_ty(),
130            },
131            _ => bug!("coroutine args missing synthetics"),
132        }
133    }
134}
135
136impl<'tcx> rustc_type_ir::inherent::IntoKind for GenericArg<'tcx> {
137    type Kind = GenericArgKind<'tcx>;
138
139    fn kind(self) -> Self::Kind {
140        self.unpack()
141    }
142}
143
144unsafe impl<'tcx> rustc_data_structures::sync::DynSend for GenericArg<'tcx> where
145    &'tcx (Ty<'tcx>, ty::Region<'tcx>, ty::Const<'tcx>): rustc_data_structures::sync::DynSend
146{
147}
148unsafe impl<'tcx> rustc_data_structures::sync::DynSync for GenericArg<'tcx> where
149    &'tcx (Ty<'tcx>, ty::Region<'tcx>, ty::Const<'tcx>): rustc_data_structures::sync::DynSync
150{
151}
152unsafe impl<'tcx> Send for GenericArg<'tcx> where
153    &'tcx (Ty<'tcx>, ty::Region<'tcx>, ty::Const<'tcx>): Send
154{
155}
156unsafe impl<'tcx> Sync for GenericArg<'tcx> where
157    &'tcx (Ty<'tcx>, ty::Region<'tcx>, ty::Const<'tcx>): Sync
158{
159}
160
161impl<'tcx> IntoDiagArg for GenericArg<'tcx> {
162    fn into_diag_arg(self) -> DiagArgValue {
163        self.to_string().into_diag_arg()
164    }
165}
166
167const TAG_MASK: usize = 0b11;
168const TYPE_TAG: usize = 0b00;
169const REGION_TAG: usize = 0b01;
170const CONST_TAG: usize = 0b10;
171
172#[extension(trait GenericArgPackExt<'tcx>)]
173impl<'tcx> GenericArgKind<'tcx> {
174    #[inline]
175    fn pack(self) -> GenericArg<'tcx> {
176        let (tag, ptr) = match self {
177            GenericArgKind::Lifetime(lt) => {
178                // Ensure we can use the tag bits.
179                assert_eq!(mem::align_of_val(&*lt.0.0) & TAG_MASK, 0);
180                (REGION_TAG, NonNull::from(lt.0.0).cast())
181            }
182            GenericArgKind::Type(ty) => {
183                // Ensure we can use the tag bits.
184                assert_eq!(mem::align_of_val(&*ty.0.0) & TAG_MASK, 0);
185                (TYPE_TAG, NonNull::from(ty.0.0).cast())
186            }
187            GenericArgKind::Const(ct) => {
188                // Ensure we can use the tag bits.
189                assert_eq!(mem::align_of_val(&*ct.0.0) & TAG_MASK, 0);
190                (CONST_TAG, NonNull::from(ct.0.0).cast())
191            }
192        };
193
194        GenericArg { ptr: ptr.map_addr(|addr| addr | tag), marker: PhantomData }
195    }
196}
197
198impl<'tcx> From<ty::Region<'tcx>> for GenericArg<'tcx> {
199    #[inline]
200    fn from(r: ty::Region<'tcx>) -> GenericArg<'tcx> {
201        GenericArgKind::Lifetime(r).pack()
202    }
203}
204
205impl<'tcx> From<Ty<'tcx>> for GenericArg<'tcx> {
206    #[inline]
207    fn from(ty: Ty<'tcx>) -> GenericArg<'tcx> {
208        GenericArgKind::Type(ty).pack()
209    }
210}
211
212impl<'tcx> From<ty::Const<'tcx>> for GenericArg<'tcx> {
213    #[inline]
214    fn from(c: ty::Const<'tcx>) -> GenericArg<'tcx> {
215        GenericArgKind::Const(c).pack()
216    }
217}
218
219impl<'tcx> From<ty::Term<'tcx>> for GenericArg<'tcx> {
220    fn from(value: ty::Term<'tcx>) -> Self {
221        match value.unpack() {
222            ty::TermKind::Ty(t) => t.into(),
223            ty::TermKind::Const(c) => c.into(),
224        }
225    }
226}
227
228impl<'tcx> GenericArg<'tcx> {
229    #[inline]
230    pub fn unpack(self) -> GenericArgKind<'tcx> {
231        let ptr =
232            unsafe { self.ptr.map_addr(|addr| NonZero::new_unchecked(addr.get() & !TAG_MASK)) };
233        // SAFETY: use of `Interned::new_unchecked` here is ok because these
234        // pointers were originally created from `Interned` types in `pack()`,
235        // and this is just going in the other direction.
236        unsafe {
237            match self.ptr.addr().get() & TAG_MASK {
238                REGION_TAG => GenericArgKind::Lifetime(ty::Region(Interned::new_unchecked(
239                    ptr.cast::<ty::RegionKind<'tcx>>().as_ref(),
240                ))),
241                TYPE_TAG => GenericArgKind::Type(Ty(Interned::new_unchecked(
242                    ptr.cast::<WithCachedTypeInfo<ty::TyKind<'tcx>>>().as_ref(),
243                ))),
244                CONST_TAG => GenericArgKind::Const(ty::Const(Interned::new_unchecked(
245                    ptr.cast::<WithCachedTypeInfo<ty::ConstKind<'tcx>>>().as_ref(),
246                ))),
247                _ => intrinsics::unreachable(),
248            }
249        }
250    }
251
252    #[inline]
253    pub fn as_type(self) -> Option<Ty<'tcx>> {
254        match self.unpack() {
255            GenericArgKind::Type(ty) => Some(ty),
256            _ => None,
257        }
258    }
259
260    #[inline]
261    pub fn as_region(self) -> Option<ty::Region<'tcx>> {
262        match self.unpack() {
263            GenericArgKind::Lifetime(re) => Some(re),
264            _ => None,
265        }
266    }
267
268    #[inline]
269    pub fn as_const(self) -> Option<ty::Const<'tcx>> {
270        match self.unpack() {
271            GenericArgKind::Const(ct) => Some(ct),
272            _ => None,
273        }
274    }
275
276    /// Unpack the `GenericArg` as a region when it is known certainly to be a region.
277    pub fn expect_region(self) -> ty::Region<'tcx> {
278        self.as_region().unwrap_or_else(|| bug!("expected a region, but found another kind"))
279    }
280
281    /// Unpack the `GenericArg` as a type when it is known certainly to be a type.
282    /// This is true in cases where `GenericArgs` is used in places where the kinds are known
283    /// to be limited (e.g. in tuples, where the only parameters are type parameters).
284    pub fn expect_ty(self) -> Ty<'tcx> {
285        self.as_type().unwrap_or_else(|| bug!("expected a type, but found another kind"))
286    }
287
288    /// Unpack the `GenericArg` as a const when it is known certainly to be a const.
289    pub fn expect_const(self) -> ty::Const<'tcx> {
290        self.as_const().unwrap_or_else(|| bug!("expected a const, but found another kind"))
291    }
292
293    pub fn is_non_region_infer(self) -> bool {
294        match self.unpack() {
295            GenericArgKind::Lifetime(_) => false,
296            // FIXME: This shouldn't return numerical/float.
297            GenericArgKind::Type(ty) => ty.is_ty_or_numeric_infer(),
298            GenericArgKind::Const(ct) => ct.is_ct_infer(),
299        }
300    }
301}
302
303impl<'a, 'tcx> Lift<TyCtxt<'tcx>> for GenericArg<'a> {
304    type Lifted = GenericArg<'tcx>;
305
306    fn lift_to_interner(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
307        match self.unpack() {
308            GenericArgKind::Lifetime(lt) => tcx.lift(lt).map(|lt| lt.into()),
309            GenericArgKind::Type(ty) => tcx.lift(ty).map(|ty| ty.into()),
310            GenericArgKind::Const(ct) => tcx.lift(ct).map(|ct| ct.into()),
311        }
312    }
313}
314
315impl<'tcx> TypeFoldable<TyCtxt<'tcx>> for GenericArg<'tcx> {
316    fn try_fold_with<F: FallibleTypeFolder<TyCtxt<'tcx>>>(
317        self,
318        folder: &mut F,
319    ) -> Result<Self, F::Error> {
320        match self.unpack() {
321            GenericArgKind::Lifetime(lt) => lt.try_fold_with(folder).map(Into::into),
322            GenericArgKind::Type(ty) => ty.try_fold_with(folder).map(Into::into),
323            GenericArgKind::Const(ct) => ct.try_fold_with(folder).map(Into::into),
324        }
325    }
326}
327
328impl<'tcx> TypeVisitable<TyCtxt<'tcx>> for GenericArg<'tcx> {
329    fn visit_with<V: TypeVisitor<TyCtxt<'tcx>>>(&self, visitor: &mut V) -> V::Result {
330        match self.unpack() {
331            GenericArgKind::Lifetime(lt) => lt.visit_with(visitor),
332            GenericArgKind::Type(ty) => ty.visit_with(visitor),
333            GenericArgKind::Const(ct) => ct.visit_with(visitor),
334        }
335    }
336}
337
338impl<'tcx, E: TyEncoder<I = TyCtxt<'tcx>>> Encodable<E> for GenericArg<'tcx> {
339    fn encode(&self, e: &mut E) {
340        self.unpack().encode(e)
341    }
342}
343
344impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> Decodable<D> for GenericArg<'tcx> {
345    fn decode(d: &mut D) -> GenericArg<'tcx> {
346        GenericArgKind::decode(d).pack()
347    }
348}
349
350/// List of generic arguments that are gonna be used to replace generic parameters.
351pub type GenericArgs<'tcx> = List<GenericArg<'tcx>>;
352
353pub type GenericArgsRef<'tcx> = &'tcx GenericArgs<'tcx>;
354
355impl<'tcx> GenericArgs<'tcx> {
356    /// Converts generic args to a type list.
357    ///
358    /// # Panics
359    ///
360    /// If any of the generic arguments are not types.
361    pub fn into_type_list(&self, tcx: TyCtxt<'tcx>) -> &'tcx List<Ty<'tcx>> {
362        tcx.mk_type_list_from_iter(self.iter().map(|arg| match arg.unpack() {
363            GenericArgKind::Type(ty) => ty,
364            _ => bug!("`into_type_list` called on generic arg with non-types"),
365        }))
366    }
367
368    /// Interpret these generic args as the args of a closure type.
369    /// Closure args have a particular structure controlled by the
370    /// compiler that encodes information like the signature and closure kind;
371    /// see `ty::ClosureArgs` struct for more comments.
372    pub fn as_closure(&'tcx self) -> ClosureArgs<TyCtxt<'tcx>> {
373        ClosureArgs { args: self }
374    }
375
376    /// Interpret these generic args as the args of a coroutine-closure type.
377    /// Coroutine-closure args have a particular structure controlled by the
378    /// compiler that encodes information like the signature and closure kind;
379    /// see `ty::CoroutineClosureArgs` struct for more comments.
380    pub fn as_coroutine_closure(&'tcx self) -> CoroutineClosureArgs<TyCtxt<'tcx>> {
381        CoroutineClosureArgs { args: self }
382    }
383
384    /// Interpret these generic args as the args of a coroutine type.
385    /// Coroutine args have a particular structure controlled by the
386    /// compiler that encodes information like the signature and coroutine kind;
387    /// see `ty::CoroutineArgs` struct for more comments.
388    pub fn as_coroutine(&'tcx self) -> CoroutineArgs<TyCtxt<'tcx>> {
389        CoroutineArgs { args: self }
390    }
391
392    /// Interpret these generic args as the args of an inline const.
393    /// Inline const args have a particular structure controlled by the
394    /// compiler that encodes information like the inferred type;
395    /// see `ty::InlineConstArgs` struct for more comments.
396    pub fn as_inline_const(&'tcx self) -> InlineConstArgs<'tcx> {
397        InlineConstArgs { args: self }
398    }
399
400    /// Creates an `GenericArgs` that maps each generic parameter to itself.
401    pub fn identity_for_item(tcx: TyCtxt<'tcx>, def_id: impl Into<DefId>) -> GenericArgsRef<'tcx> {
402        Self::for_item(tcx, def_id.into(), |param, _| tcx.mk_param_from_def(param))
403    }
404
405    /// Creates an `GenericArgs` for generic parameter definitions,
406    /// by calling closures to obtain each kind.
407    /// The closures get to observe the `GenericArgs` as they're
408    /// being built, which can be used to correctly
409    /// replace defaults of generic parameters.
410    pub fn for_item<F>(tcx: TyCtxt<'tcx>, def_id: DefId, mut mk_kind: F) -> GenericArgsRef<'tcx>
411    where
412        F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,
413    {
414        let defs = tcx.generics_of(def_id);
415        let count = defs.count();
416        let mut args = SmallVec::with_capacity(count);
417        Self::fill_item(&mut args, tcx, defs, &mut mk_kind);
418        tcx.mk_args(&args)
419    }
420
421    pub fn extend_to<F>(
422        &self,
423        tcx: TyCtxt<'tcx>,
424        def_id: DefId,
425        mut mk_kind: F,
426    ) -> GenericArgsRef<'tcx>
427    where
428        F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,
429    {
430        Self::for_item(tcx, def_id, |param, args| {
431            self.get(param.index as usize).cloned().unwrap_or_else(|| mk_kind(param, args))
432        })
433    }
434
435    pub fn fill_item<F>(
436        args: &mut SmallVec<[GenericArg<'tcx>; 8]>,
437        tcx: TyCtxt<'tcx>,
438        defs: &ty::Generics,
439        mk_kind: &mut F,
440    ) where
441        F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,
442    {
443        if let Some(def_id) = defs.parent {
444            let parent_defs = tcx.generics_of(def_id);
445            Self::fill_item(args, tcx, parent_defs, mk_kind);
446        }
447        Self::fill_single(args, defs, mk_kind)
448    }
449
450    pub fn fill_single<F>(
451        args: &mut SmallVec<[GenericArg<'tcx>; 8]>,
452        defs: &ty::Generics,
453        mk_kind: &mut F,
454    ) where
455        F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,
456    {
457        args.reserve(defs.own_params.len());
458        for param in &defs.own_params {
459            let kind = mk_kind(param, args);
460            assert_eq!(param.index as usize, args.len(), "{args:#?}, {defs:#?}");
461            args.push(kind);
462        }
463    }
464
465    // Extend an `original_args` list to the full number of args expected by `def_id`,
466    // filling in the missing parameters with error ty/ct or 'static regions.
467    pub fn extend_with_error(
468        tcx: TyCtxt<'tcx>,
469        def_id: DefId,
470        original_args: &[GenericArg<'tcx>],
471    ) -> GenericArgsRef<'tcx> {
472        ty::GenericArgs::for_item(tcx, def_id, |def, _| {
473            if let Some(arg) = original_args.get(def.index as usize) {
474                *arg
475            } else {
476                def.to_error(tcx)
477            }
478        })
479    }
480
481    #[inline]
482    pub fn types(&'tcx self) -> impl DoubleEndedIterator<Item = Ty<'tcx>> + 'tcx {
483        self.iter().filter_map(|k| k.as_type())
484    }
485
486    #[inline]
487    pub fn regions(&'tcx self) -> impl DoubleEndedIterator<Item = ty::Region<'tcx>> + 'tcx {
488        self.iter().filter_map(|k| k.as_region())
489    }
490
491    #[inline]
492    pub fn consts(&'tcx self) -> impl DoubleEndedIterator<Item = ty::Const<'tcx>> + 'tcx {
493        self.iter().filter_map(|k| k.as_const())
494    }
495
496    /// Returns generic arguments that are not lifetimes.
497    #[inline]
498    pub fn non_erasable_generics(
499        &'tcx self,
500    ) -> impl DoubleEndedIterator<Item = GenericArgKind<'tcx>> + 'tcx {
501        self.iter().filter_map(|k| match k.unpack() {
502            ty::GenericArgKind::Lifetime(_) => None,
503            generic => Some(generic),
504        })
505    }
506
507    #[inline]
508    #[track_caller]
509    pub fn type_at(&self, i: usize) -> Ty<'tcx> {
510        self[i].as_type().unwrap_or_else(|| bug!("expected type for param #{} in {:?}", i, self))
511    }
512
513    #[inline]
514    #[track_caller]
515    pub fn region_at(&self, i: usize) -> ty::Region<'tcx> {
516        self[i]
517            .as_region()
518            .unwrap_or_else(|| bug!("expected region for param #{} in {:?}", i, self))
519    }
520
521    #[inline]
522    #[track_caller]
523    pub fn const_at(&self, i: usize) -> ty::Const<'tcx> {
524        self[i].as_const().unwrap_or_else(|| bug!("expected const for param #{} in {:?}", i, self))
525    }
526
527    #[inline]
528    #[track_caller]
529    pub fn type_for_def(&self, def: &ty::GenericParamDef) -> GenericArg<'tcx> {
530        self.type_at(def.index as usize).into()
531    }
532
533    /// Transform from generic args for a child of `source_ancestor`
534    /// (e.g., a trait or impl) to args for the same child
535    /// in a different item, with `target_args` as the base for
536    /// the target impl/trait, with the source child-specific
537    /// parameters (e.g., method parameters) on top of that base.
538    ///
539    /// For example given:
540    ///
541    /// ```no_run
542    /// trait X<S> { fn f<T>(); }
543    /// impl<U> X<U> for U { fn f<V>() {} }
544    /// ```
545    ///
546    /// * If `self` is `[Self, S, T]`: the identity args of `f` in the trait.
547    /// * If `source_ancestor` is the def_id of the trait.
548    /// * If `target_args` is `[U]`, the args for the impl.
549    /// * Then we will return `[U, T]`, the arg for `f` in the impl that
550    ///   are needed for it to match the trait.
551    pub fn rebase_onto(
552        &self,
553        tcx: TyCtxt<'tcx>,
554        source_ancestor: DefId,
555        target_args: GenericArgsRef<'tcx>,
556    ) -> GenericArgsRef<'tcx> {
557        let defs = tcx.generics_of(source_ancestor);
558        tcx.mk_args_from_iter(target_args.iter().chain(self.iter().skip(defs.count())))
559    }
560
561    pub fn truncate_to(&self, tcx: TyCtxt<'tcx>, generics: &ty::Generics) -> GenericArgsRef<'tcx> {
562        tcx.mk_args_from_iter(self.iter().take(generics.count()))
563    }
564
565    pub fn print_as_list(&self) -> String {
566        let v = self.iter().map(|arg| arg.to_string()).collect::<Vec<_>>();
567        format!("[{}]", v.join(", "))
568    }
569}
570
571impl<'tcx> TypeFoldable<TyCtxt<'tcx>> for GenericArgsRef<'tcx> {
572    fn try_fold_with<F: FallibleTypeFolder<TyCtxt<'tcx>>>(
573        self,
574        folder: &mut F,
575    ) -> Result<Self, F::Error> {
576        // This code is hot enough that it's worth specializing for the most
577        // common length lists, to avoid the overhead of `SmallVec` creation.
578        // The match arms are in order of frequency. The 1, 2, and 0 cases are
579        // typically hit in 90--99.99% of cases. When folding doesn't change
580        // the args, it's faster to reuse the existing args rather than
581        // calling `mk_args`.
582        match self.len() {
583            1 => {
584                let param0 = self[0].try_fold_with(folder)?;
585                if param0 == self[0] { Ok(self) } else { Ok(folder.cx().mk_args(&[param0])) }
586            }
587            2 => {
588                let param0 = self[0].try_fold_with(folder)?;
589                let param1 = self[1].try_fold_with(folder)?;
590                if param0 == self[0] && param1 == self[1] {
591                    Ok(self)
592                } else {
593                    Ok(folder.cx().mk_args(&[param0, param1]))
594                }
595            }
596            0 => Ok(self),
597            _ => ty::util::fold_list(self, folder, |tcx, v| tcx.mk_args(v)),
598        }
599    }
600}
601
602impl<'tcx> TypeFoldable<TyCtxt<'tcx>> for &'tcx ty::List<Ty<'tcx>> {
603    fn try_fold_with<F: FallibleTypeFolder<TyCtxt<'tcx>>>(
604        self,
605        folder: &mut F,
606    ) -> Result<Self, F::Error> {
607        // This code is fairly hot, though not as hot as `GenericArgsRef`.
608        //
609        // When compiling stage 2, I get the following results:
610        //
611        // len |   total   |   %
612        // --- | --------- | -----
613        //  2  |  15083590 |  48.1
614        //  3  |   7540067 |  24.0
615        //  1  |   5300377 |  16.9
616        //  4  |   1351897 |   4.3
617        //  0  |   1256849 |   4.0
618        //
619        // I've tried it with some private repositories and got
620        // close to the same result, with 4 and 0 swapping places
621        // sometimes.
622        match self.len() {
623            2 => {
624                let param0 = self[0].try_fold_with(folder)?;
625                let param1 = self[1].try_fold_with(folder)?;
626                if param0 == self[0] && param1 == self[1] {
627                    Ok(self)
628                } else {
629                    Ok(folder.cx().mk_type_list(&[param0, param1]))
630                }
631            }
632            _ => ty::util::fold_list(self, folder, |tcx, v| tcx.mk_type_list(v)),
633        }
634    }
635}
636
637impl<'tcx, T: TypeVisitable<TyCtxt<'tcx>>> TypeVisitable<TyCtxt<'tcx>> for &'tcx ty::List<T> {
638    #[inline]
639    fn visit_with<V: TypeVisitor<TyCtxt<'tcx>>>(&self, visitor: &mut V) -> V::Result {
640        walk_visitable_list!(visitor, self.iter());
641        V::Result::output()
642    }
643}
644
645/// Stores the user-given args to reach some fully qualified path
646/// (e.g., `<T>::Item` or `<T as Trait>::Item`).
647#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
648#[derive(HashStable, TypeFoldable, TypeVisitable)]
649pub struct UserArgs<'tcx> {
650    /// The args for the item as given by the user.
651    pub args: GenericArgsRef<'tcx>,
652
653    /// The self type, in the case of a `<T>::Item` path (when applied
654    /// to an inherent impl). See `UserSelfTy` below.
655    pub user_self_ty: Option<UserSelfTy<'tcx>>,
656}
657
658/// Specifies the user-given self type. In the case of a path that
659/// refers to a member in an inherent impl, this self type is
660/// sometimes needed to constrain the type parameters on the impl. For
661/// example, in this code:
662///
663/// ```ignore (illustrative)
664/// struct Foo<T> { }
665/// impl<A> Foo<A> { fn method() { } }
666/// ```
667///
668/// when you then have a path like `<Foo<&'static u32>>::method`,
669/// this struct would carry the `DefId` of the impl along with the
670/// self type `Foo<u32>`. Then we can instantiate the parameters of
671/// the impl (with the args from `UserArgs`) and apply those to
672/// the self type, giving `Foo<?A>`. Finally, we unify that with
673/// the self type here, which contains `?A` to be `&'static u32`
674#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
675#[derive(HashStable, TypeFoldable, TypeVisitable)]
676pub struct UserSelfTy<'tcx> {
677    pub impl_def_id: DefId,
678    pub self_ty: Ty<'tcx>,
679}