rustc_middle/ty/
util.rs

1//! Miscellaneous type-system utilities that are too small to deserve their own modules.
2
3use std::{fmt, iter};
4
5use rustc_abi::{Float, Integer, IntegerType, Size};
6use rustc_apfloat::Float as _;
7use rustc_data_structures::fx::{FxHashMap, FxHashSet};
8use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
9use rustc_data_structures::stack::ensure_sufficient_stack;
10use rustc_errors::ErrorGuaranteed;
11use rustc_hashes::Hash128;
12use rustc_hir as hir;
13use rustc_hir::def::{CtorOf, DefKind, Res};
14use rustc_hir::def_id::{CrateNum, DefId, LocalDefId};
15use rustc_index::bit_set::GrowableBitSet;
16use rustc_macros::{HashStable, TyDecodable, TyEncodable, extension};
17use rustc_session::Limit;
18use rustc_span::sym;
19use smallvec::{SmallVec, smallvec};
20use tracing::{debug, instrument};
21
22use super::TypingEnv;
23use crate::middle::codegen_fn_attrs::CodegenFnAttrFlags;
24use crate::mir;
25use crate::query::Providers;
26use crate::ty::layout::{FloatExt, IntegerExt};
27use crate::ty::{
28    self, Asyncness, FallibleTypeFolder, GenericArgKind, GenericArgsRef, Ty, TyCtxt, TypeFoldable,
29    TypeFolder, TypeSuperFoldable, TypeVisitableExt, Upcast,
30};
31
32#[derive(Copy, Clone, Debug)]
33pub struct Discr<'tcx> {
34    /// Bit representation of the discriminant (e.g., `-128i8` is `0xFF_u128`).
35    pub val: u128,
36    pub ty: Ty<'tcx>,
37}
38
39/// Used as an input to [`TyCtxt::uses_unique_generic_params`].
40#[derive(Copy, Clone, Debug, PartialEq, Eq)]
41pub enum CheckRegions {
42    No,
43    /// Only permit parameter regions. This should be used
44    /// for everything apart from functions, which may use
45    /// `ReBound` to represent late-bound regions.
46    OnlyParam,
47    /// Check region parameters from a function definition.
48    /// Allows `ReEarlyParam` and `ReBound` to handle early
49    /// and late-bound region parameters.
50    FromFunction,
51}
52
53#[derive(Copy, Clone, Debug)]
54pub enum NotUniqueParam<'tcx> {
55    DuplicateParam(ty::GenericArg<'tcx>),
56    NotParam(ty::GenericArg<'tcx>),
57}
58
59impl<'tcx> fmt::Display for Discr<'tcx> {
60    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
61        match *self.ty.kind() {
62            ty::Int(ity) => {
63                let size = ty::tls::with(|tcx| Integer::from_int_ty(&tcx, ity).size());
64                let x = self.val;
65                // sign extend the raw representation to be an i128
66                let x = size.sign_extend(x) as i128;
67                write!(fmt, "{x}")
68            }
69            _ => write!(fmt, "{}", self.val),
70        }
71    }
72}
73
74impl<'tcx> Discr<'tcx> {
75    /// Adds `1` to the value and wraps around if the maximum for the type is reached.
76    pub fn wrap_incr(self, tcx: TyCtxt<'tcx>) -> Self {
77        self.checked_add(tcx, 1).0
78    }
79    pub fn checked_add(self, tcx: TyCtxt<'tcx>, n: u128) -> (Self, bool) {
80        let (size, signed) = self.ty.int_size_and_signed(tcx);
81        let (val, oflo) = if signed {
82            let min = size.signed_int_min();
83            let max = size.signed_int_max();
84            let val = size.sign_extend(self.val);
85            assert!(n < (i128::MAX as u128));
86            let n = n as i128;
87            let oflo = val > max - n;
88            let val = if oflo { min + (n - (max - val) - 1) } else { val + n };
89            // zero the upper bits
90            let val = val as u128;
91            let val = size.truncate(val);
92            (val, oflo)
93        } else {
94            let max = size.unsigned_int_max();
95            let val = self.val;
96            let oflo = val > max - n;
97            let val = if oflo { n - (max - val) - 1 } else { val + n };
98            (val, oflo)
99        };
100        (Self { val, ty: self.ty }, oflo)
101    }
102}
103
104#[extension(pub trait IntTypeExt)]
105impl IntegerType {
106    fn to_ty<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
107        match self {
108            IntegerType::Pointer(true) => tcx.types.isize,
109            IntegerType::Pointer(false) => tcx.types.usize,
110            IntegerType::Fixed(i, s) => i.to_ty(tcx, *s),
111        }
112    }
113
114    fn initial_discriminant<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Discr<'tcx> {
115        Discr { val: 0, ty: self.to_ty(tcx) }
116    }
117
118    fn disr_incr<'tcx>(&self, tcx: TyCtxt<'tcx>, val: Option<Discr<'tcx>>) -> Option<Discr<'tcx>> {
119        if let Some(val) = val {
120            assert_eq!(self.to_ty(tcx), val.ty);
121            let (new, oflo) = val.checked_add(tcx, 1);
122            if oflo { None } else { Some(new) }
123        } else {
124            Some(self.initial_discriminant(tcx))
125        }
126    }
127}
128
129impl<'tcx> TyCtxt<'tcx> {
130    /// Creates a hash of the type `Ty` which will be the same no matter what crate
131    /// context it's calculated within. This is used by the `type_id` intrinsic.
132    pub fn type_id_hash(self, ty: Ty<'tcx>) -> Hash128 {
133        // We want the type_id be independent of the types free regions, so we
134        // erase them. The erase_regions() call will also anonymize bound
135        // regions, which is desirable too.
136        let ty = self.erase_regions(ty);
137
138        self.with_stable_hashing_context(|mut hcx| {
139            let mut hasher = StableHasher::new();
140            hcx.while_hashing_spans(false, |hcx| ty.hash_stable(hcx, &mut hasher));
141            hasher.finish()
142        })
143    }
144
145    pub fn res_generics_def_id(self, res: Res) -> Option<DefId> {
146        match res {
147            Res::Def(DefKind::Ctor(CtorOf::Variant, _), def_id) => {
148                Some(self.parent(self.parent(def_id)))
149            }
150            Res::Def(DefKind::Variant | DefKind::Ctor(CtorOf::Struct, _), def_id) => {
151                Some(self.parent(def_id))
152            }
153            // Other `DefKind`s don't have generics and would ICE when calling
154            // `generics_of`.
155            Res::Def(
156                DefKind::Struct
157                | DefKind::Union
158                | DefKind::Enum
159                | DefKind::Trait
160                | DefKind::OpaqueTy
161                | DefKind::TyAlias
162                | DefKind::ForeignTy
163                | DefKind::TraitAlias
164                | DefKind::AssocTy
165                | DefKind::Fn
166                | DefKind::AssocFn
167                | DefKind::AssocConst
168                | DefKind::Impl { .. },
169                def_id,
170            ) => Some(def_id),
171            Res::Err => None,
172            _ => None,
173        }
174    }
175
176    /// Checks whether `ty: Copy` holds while ignoring region constraints.
177    ///
178    /// This impacts whether values of `ty` are *moved* or *copied*
179    /// when referenced. This means that we may generate MIR which
180    /// does copies even when the type actually doesn't satisfy the
181    /// full requirements for the `Copy` trait (cc #29149) -- this
182    /// winds up being reported as an error during NLL borrow check.
183    ///
184    /// This function should not be used if there is an `InferCtxt` available.
185    /// Use `InferCtxt::type_is_copy_modulo_regions` instead.
186    pub fn type_is_copy_modulo_regions(
187        self,
188        typing_env: ty::TypingEnv<'tcx>,
189        ty: Ty<'tcx>,
190    ) -> bool {
191        ty.is_trivially_pure_clone_copy() || self.is_copy_raw(typing_env.as_query_input(ty))
192    }
193
194    /// Checks whether `ty: UseCloned` holds while ignoring region constraints.
195    ///
196    /// This function should not be used if there is an `InferCtxt` available.
197    /// Use `InferCtxt::type_is_copy_modulo_regions` instead.
198    pub fn type_is_use_cloned_modulo_regions(
199        self,
200        typing_env: ty::TypingEnv<'tcx>,
201        ty: Ty<'tcx>,
202    ) -> bool {
203        ty.is_trivially_pure_clone_copy() || self.is_use_cloned_raw(typing_env.as_query_input(ty))
204    }
205
206    /// Returns the deeply last field of nested structures, or the same type if
207    /// not a structure at all. Corresponds to the only possible unsized field,
208    /// and its type can be used to determine unsizing strategy.
209    ///
210    /// Should only be called if `ty` has no inference variables and does not
211    /// need its lifetimes preserved (e.g. as part of codegen); otherwise
212    /// normalization attempt may cause compiler bugs.
213    pub fn struct_tail_for_codegen(
214        self,
215        ty: Ty<'tcx>,
216        typing_env: ty::TypingEnv<'tcx>,
217    ) -> Ty<'tcx> {
218        let tcx = self;
219        tcx.struct_tail_raw(ty, |ty| tcx.normalize_erasing_regions(typing_env, ty), || {})
220    }
221
222    /// Returns true if a type has metadata.
223    pub fn type_has_metadata(self, ty: Ty<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
224        if ty.is_sized(self, typing_env) {
225            return false;
226        }
227
228        let tail = self.struct_tail_for_codegen(ty, typing_env);
229        match tail.kind() {
230            ty::Foreign(..) => false,
231            ty::Str | ty::Slice(..) | ty::Dynamic(..) => true,
232            _ => bug!("unexpected unsized tail: {:?}", tail),
233        }
234    }
235
236    /// Returns the deeply last field of nested structures, or the same type if
237    /// not a structure at all. Corresponds to the only possible unsized field,
238    /// and its type can be used to determine unsizing strategy.
239    ///
240    /// This is parameterized over the normalization strategy (i.e. how to
241    /// handle `<T as Trait>::Assoc` and `impl Trait`). You almost certainly do
242    /// **NOT** want to pass the identity function here, unless you know what
243    /// you're doing, or you're within normalization code itself and will handle
244    /// an unnormalized tail recursively.
245    ///
246    /// See also `struct_tail_for_codegen`, which is suitable for use
247    /// during codegen.
248    pub fn struct_tail_raw(
249        self,
250        mut ty: Ty<'tcx>,
251        mut normalize: impl FnMut(Ty<'tcx>) -> Ty<'tcx>,
252        // This is currently used to allow us to walk a ValTree
253        // in lockstep with the type in order to get the ValTree branch that
254        // corresponds to an unsized field.
255        mut f: impl FnMut() -> (),
256    ) -> Ty<'tcx> {
257        let recursion_limit = self.recursion_limit();
258        for iteration in 0.. {
259            if !recursion_limit.value_within_limit(iteration) {
260                let suggested_limit = match recursion_limit {
261                    Limit(0) => Limit(2),
262                    limit => limit * 2,
263                };
264                let reported = self
265                    .dcx()
266                    .emit_err(crate::error::RecursionLimitReached { ty, suggested_limit });
267                return Ty::new_error(self, reported);
268            }
269            match *ty.kind() {
270                ty::Adt(def, args) => {
271                    if !def.is_struct() {
272                        break;
273                    }
274                    match def.non_enum_variant().tail_opt() {
275                        Some(field) => {
276                            f();
277                            ty = field.ty(self, args);
278                        }
279                        None => break,
280                    }
281                }
282
283                ty::Tuple(tys) if let Some((&last_ty, _)) = tys.split_last() => {
284                    f();
285                    ty = last_ty;
286                }
287
288                ty::Tuple(_) => break,
289
290                ty::Pat(inner, _) => {
291                    f();
292                    ty = inner;
293                }
294
295                ty::Alias(..) => {
296                    let normalized = normalize(ty);
297                    if ty == normalized {
298                        return ty;
299                    } else {
300                        ty = normalized;
301                    }
302                }
303
304                _ => {
305                    break;
306                }
307            }
308        }
309        ty
310    }
311
312    /// Same as applying `struct_tail` on `source` and `target`, but only
313    /// keeps going as long as the two types are instances of the same
314    /// structure definitions.
315    /// For `(Foo<Foo<T>>, Foo<dyn Trait>)`, the result will be `(Foo<T>, dyn Trait)`,
316    /// whereas struct_tail produces `T`, and `Trait`, respectively.
317    ///
318    /// Should only be called if the types have no inference variables and do
319    /// not need their lifetimes preserved (e.g., as part of codegen); otherwise,
320    /// normalization attempt may cause compiler bugs.
321    pub fn struct_lockstep_tails_for_codegen(
322        self,
323        source: Ty<'tcx>,
324        target: Ty<'tcx>,
325        typing_env: ty::TypingEnv<'tcx>,
326    ) -> (Ty<'tcx>, Ty<'tcx>) {
327        let tcx = self;
328        tcx.struct_lockstep_tails_raw(source, target, |ty| {
329            tcx.normalize_erasing_regions(typing_env, ty)
330        })
331    }
332
333    /// Same as applying `struct_tail` on `source` and `target`, but only
334    /// keeps going as long as the two types are instances of the same
335    /// structure definitions.
336    /// For `(Foo<Foo<T>>, Foo<dyn Trait>)`, the result will be `(Foo<T>, Trait)`,
337    /// whereas struct_tail produces `T`, and `Trait`, respectively.
338    ///
339    /// See also `struct_lockstep_tails_for_codegen`, which is suitable for use
340    /// during codegen.
341    pub fn struct_lockstep_tails_raw(
342        self,
343        source: Ty<'tcx>,
344        target: Ty<'tcx>,
345        normalize: impl Fn(Ty<'tcx>) -> Ty<'tcx>,
346    ) -> (Ty<'tcx>, Ty<'tcx>) {
347        let (mut a, mut b) = (source, target);
348        loop {
349            match (a.kind(), b.kind()) {
350                (&ty::Adt(a_def, a_args), &ty::Adt(b_def, b_args))
351                    if a_def == b_def && a_def.is_struct() =>
352                {
353                    if let Some(f) = a_def.non_enum_variant().tail_opt() {
354                        a = f.ty(self, a_args);
355                        b = f.ty(self, b_args);
356                    } else {
357                        break;
358                    }
359                }
360                (&ty::Tuple(a_tys), &ty::Tuple(b_tys)) if a_tys.len() == b_tys.len() => {
361                    if let Some(&a_last) = a_tys.last() {
362                        a = a_last;
363                        b = *b_tys.last().unwrap();
364                    } else {
365                        break;
366                    }
367                }
368                (ty::Alias(..), _) | (_, ty::Alias(..)) => {
369                    // If either side is a projection, attempt to
370                    // progress via normalization. (Should be safe to
371                    // apply to both sides as normalization is
372                    // idempotent.)
373                    let a_norm = normalize(a);
374                    let b_norm = normalize(b);
375                    if a == a_norm && b == b_norm {
376                        break;
377                    } else {
378                        a = a_norm;
379                        b = b_norm;
380                    }
381                }
382
383                _ => break,
384            }
385        }
386        (a, b)
387    }
388
389    /// Calculate the destructor of a given type.
390    pub fn calculate_dtor(
391        self,
392        adt_did: LocalDefId,
393        validate: impl Fn(Self, LocalDefId) -> Result<(), ErrorGuaranteed>,
394    ) -> Option<ty::Destructor> {
395        let drop_trait = self.lang_items().drop_trait()?;
396        self.ensure_ok().coherent_trait(drop_trait).ok()?;
397
398        let mut dtor_candidate = None;
399        // `Drop` impls can only be written in the same crate as the adt, and cannot be blanket impls
400        for &impl_did in self.local_trait_impls(drop_trait) {
401            let Some(adt_def) = self.type_of(impl_did).skip_binder().ty_adt_def() else { continue };
402            if adt_def.did() != adt_did.to_def_id() {
403                continue;
404            }
405
406            if validate(self, impl_did).is_err() {
407                // Already `ErrorGuaranteed`, no need to delay a span bug here.
408                continue;
409            }
410
411            let Some(item_id) = self.associated_item_def_ids(impl_did).first() else {
412                self.dcx()
413                    .span_delayed_bug(self.def_span(impl_did), "Drop impl without drop function");
414                continue;
415            };
416
417            if self.def_kind(item_id) != DefKind::AssocFn {
418                self.dcx().span_delayed_bug(self.def_span(item_id), "drop is not a function");
419                continue;
420            }
421
422            if let Some(old_item_id) = dtor_candidate {
423                self.dcx()
424                    .struct_span_err(self.def_span(item_id), "multiple drop impls found")
425                    .with_span_note(self.def_span(old_item_id), "other impl here")
426                    .delay_as_bug();
427            }
428
429            dtor_candidate = Some(*item_id);
430        }
431
432        let did = dtor_candidate?;
433        Some(ty::Destructor { did })
434    }
435
436    /// Calculate the async destructor of a given type.
437    pub fn calculate_async_dtor(
438        self,
439        adt_did: LocalDefId,
440        validate: impl Fn(Self, LocalDefId) -> Result<(), ErrorGuaranteed>,
441    ) -> Option<ty::AsyncDestructor> {
442        let async_drop_trait = self.lang_items().async_drop_trait()?;
443        self.ensure_ok().coherent_trait(async_drop_trait).ok()?;
444
445        let mut dtor_candidate = None;
446        // `AsyncDrop` impls can only be written in the same crate as the adt, and cannot be blanket impls
447        for &impl_did in self.local_trait_impls(async_drop_trait) {
448            let Some(adt_def) = self.type_of(impl_did).skip_binder().ty_adt_def() else { continue };
449            if adt_def.did() != adt_did.to_def_id() {
450                continue;
451            }
452
453            if validate(self, impl_did).is_err() {
454                // Already `ErrorGuaranteed`, no need to delay a span bug here.
455                continue;
456            }
457
458            if let Some(old_impl_did) = dtor_candidate {
459                self.dcx()
460                    .struct_span_err(self.def_span(impl_did), "multiple async drop impls found")
461                    .with_span_note(self.def_span(old_impl_did), "other impl here")
462                    .delay_as_bug();
463            }
464
465            dtor_candidate = Some(impl_did);
466        }
467
468        Some(ty::AsyncDestructor { impl_did: dtor_candidate?.into() })
469    }
470
471    /// Returns the set of types that are required to be alive in
472    /// order to run the destructor of `def` (see RFCs 769 and
473    /// 1238).
474    ///
475    /// Note that this returns only the constraints for the
476    /// destructor of `def` itself. For the destructors of the
477    /// contents, you need `adt_dtorck_constraint`.
478    pub fn destructor_constraints(self, def: ty::AdtDef<'tcx>) -> Vec<ty::GenericArg<'tcx>> {
479        let dtor = match def.destructor(self) {
480            None => {
481                debug!("destructor_constraints({:?}) - no dtor", def.did());
482                return vec![];
483            }
484            Some(dtor) => dtor.did,
485        };
486
487        let impl_def_id = self.parent(dtor);
488        let impl_generics = self.generics_of(impl_def_id);
489
490        // We have a destructor - all the parameters that are not
491        // pure_wrt_drop (i.e, don't have a #[may_dangle] attribute)
492        // must be live.
493
494        // We need to return the list of parameters from the ADTs
495        // generics/args that correspond to impure parameters on the
496        // impl's generics. This is a bit ugly, but conceptually simple:
497        //
498        // Suppose our ADT looks like the following
499        //
500        //     struct S<X, Y, Z>(X, Y, Z);
501        //
502        // and the impl is
503        //
504        //     impl<#[may_dangle] P0, P1, P2> Drop for S<P1, P2, P0>
505        //
506        // We want to return the parameters (X, Y). For that, we match
507        // up the item-args <X, Y, Z> with the args on the impl ADT,
508        // <P1, P2, P0>, and then look up which of the impl args refer to
509        // parameters marked as pure.
510
511        let impl_args = match *self.type_of(impl_def_id).instantiate_identity().kind() {
512            ty::Adt(def_, args) if def_ == def => args,
513            _ => span_bug!(self.def_span(impl_def_id), "expected ADT for self type of `Drop` impl"),
514        };
515
516        let item_args = ty::GenericArgs::identity_for_item(self, def.did());
517
518        let result = iter::zip(item_args, impl_args)
519            .filter(|&(_, k)| {
520                match k.unpack() {
521                    GenericArgKind::Lifetime(region) => match region.kind() {
522                        ty::ReEarlyParam(ebr) => {
523                            !impl_generics.region_param(ebr, self).pure_wrt_drop
524                        }
525                        // Error: not a region param
526                        _ => false,
527                    },
528                    GenericArgKind::Type(ty) => match *ty.kind() {
529                        ty::Param(pt) => !impl_generics.type_param(pt, self).pure_wrt_drop,
530                        // Error: not a type param
531                        _ => false,
532                    },
533                    GenericArgKind::Const(ct) => match ct.kind() {
534                        ty::ConstKind::Param(pc) => {
535                            !impl_generics.const_param(pc, self).pure_wrt_drop
536                        }
537                        // Error: not a const param
538                        _ => false,
539                    },
540                }
541            })
542            .map(|(item_param, _)| item_param)
543            .collect();
544        debug!("destructor_constraint({:?}) = {:?}", def.did(), result);
545        result
546    }
547
548    /// Checks whether each generic argument is simply a unique generic parameter.
549    pub fn uses_unique_generic_params(
550        self,
551        args: &[ty::GenericArg<'tcx>],
552        ignore_regions: CheckRegions,
553    ) -> Result<(), NotUniqueParam<'tcx>> {
554        let mut seen = GrowableBitSet::default();
555        let mut seen_late = FxHashSet::default();
556        for arg in args {
557            match arg.unpack() {
558                GenericArgKind::Lifetime(lt) => match (ignore_regions, lt.kind()) {
559                    (CheckRegions::FromFunction, ty::ReBound(di, reg)) => {
560                        if !seen_late.insert((di, reg)) {
561                            return Err(NotUniqueParam::DuplicateParam(lt.into()));
562                        }
563                    }
564                    (CheckRegions::OnlyParam | CheckRegions::FromFunction, ty::ReEarlyParam(p)) => {
565                        if !seen.insert(p.index) {
566                            return Err(NotUniqueParam::DuplicateParam(lt.into()));
567                        }
568                    }
569                    (CheckRegions::OnlyParam | CheckRegions::FromFunction, _) => {
570                        return Err(NotUniqueParam::NotParam(lt.into()));
571                    }
572                    (CheckRegions::No, _) => {}
573                },
574                GenericArgKind::Type(t) => match t.kind() {
575                    ty::Param(p) => {
576                        if !seen.insert(p.index) {
577                            return Err(NotUniqueParam::DuplicateParam(t.into()));
578                        }
579                    }
580                    _ => return Err(NotUniqueParam::NotParam(t.into())),
581                },
582                GenericArgKind::Const(c) => match c.kind() {
583                    ty::ConstKind::Param(p) => {
584                        if !seen.insert(p.index) {
585                            return Err(NotUniqueParam::DuplicateParam(c.into()));
586                        }
587                    }
588                    _ => return Err(NotUniqueParam::NotParam(c.into())),
589                },
590            }
591        }
592
593        Ok(())
594    }
595
596    /// Returns `true` if `def_id` refers to a closure, coroutine, or coroutine-closure
597    /// (i.e. an async closure). These are all represented by `hir::Closure`, and all
598    /// have the same `DefKind`.
599    ///
600    /// Note that closures have a `DefId`, but the closure *expression* also has a
601    // `HirId` that is located within the context where the closure appears (and, sadly,
602    // a corresponding `NodeId`, since those are not yet phased out). The parent of
603    // the closure's `DefId` will also be the context where it appears.
604    pub fn is_closure_like(self, def_id: DefId) -> bool {
605        matches!(self.def_kind(def_id), DefKind::Closure)
606    }
607
608    /// Returns `true` if `def_id` refers to a definition that does not have its own
609    /// type-checking context, i.e. closure, coroutine or inline const.
610    pub fn is_typeck_child(self, def_id: DefId) -> bool {
611        matches!(
612            self.def_kind(def_id),
613            DefKind::Closure | DefKind::InlineConst | DefKind::SyntheticCoroutineBody
614        )
615    }
616
617    /// Returns `true` if `def_id` refers to a trait (i.e., `trait Foo { ... }`).
618    pub fn is_trait(self, def_id: DefId) -> bool {
619        self.def_kind(def_id) == DefKind::Trait
620    }
621
622    /// Returns `true` if `def_id` refers to a trait alias (i.e., `trait Foo = ...;`),
623    /// and `false` otherwise.
624    pub fn is_trait_alias(self, def_id: DefId) -> bool {
625        self.def_kind(def_id) == DefKind::TraitAlias
626    }
627
628    /// Returns `true` if this `DefId` refers to the implicit constructor for
629    /// a tuple struct like `struct Foo(u32)`, and `false` otherwise.
630    pub fn is_constructor(self, def_id: DefId) -> bool {
631        matches!(self.def_kind(def_id), DefKind::Ctor(..))
632    }
633
634    /// Given the `DefId`, returns the `DefId` of the innermost item that
635    /// has its own type-checking context or "inference environment".
636    ///
637    /// For example, a closure has its own `DefId`, but it is type-checked
638    /// with the containing item. Similarly, an inline const block has its
639    /// own `DefId` but it is type-checked together with the containing item.
640    ///
641    /// Therefore, when we fetch the
642    /// `typeck` the closure, for example, we really wind up
643    /// fetching the `typeck` the enclosing fn item.
644    pub fn typeck_root_def_id(self, def_id: DefId) -> DefId {
645        let mut def_id = def_id;
646        while self.is_typeck_child(def_id) {
647            def_id = self.parent(def_id);
648        }
649        def_id
650    }
651
652    /// Given the `DefId` and args a closure, creates the type of
653    /// `self` argument that the closure expects. For example, for a
654    /// `Fn` closure, this would return a reference type `&T` where
655    /// `T = closure_ty`.
656    ///
657    /// Returns `None` if this closure's kind has not yet been inferred.
658    /// This should only be possible during type checking.
659    ///
660    /// Note that the return value is a late-bound region and hence
661    /// wrapped in a binder.
662    pub fn closure_env_ty(
663        self,
664        closure_ty: Ty<'tcx>,
665        closure_kind: ty::ClosureKind,
666        env_region: ty::Region<'tcx>,
667    ) -> Ty<'tcx> {
668        match closure_kind {
669            ty::ClosureKind::Fn => Ty::new_imm_ref(self, env_region, closure_ty),
670            ty::ClosureKind::FnMut => Ty::new_mut_ref(self, env_region, closure_ty),
671            ty::ClosureKind::FnOnce => closure_ty,
672        }
673    }
674
675    /// Returns `true` if the node pointed to by `def_id` is a `static` item.
676    #[inline]
677    pub fn is_static(self, def_id: DefId) -> bool {
678        matches!(self.def_kind(def_id), DefKind::Static { .. })
679    }
680
681    #[inline]
682    pub fn static_mutability(self, def_id: DefId) -> Option<hir::Mutability> {
683        if let DefKind::Static { mutability, .. } = self.def_kind(def_id) {
684            Some(mutability)
685        } else {
686            None
687        }
688    }
689
690    /// Returns `true` if this is a `static` item with the `#[thread_local]` attribute.
691    pub fn is_thread_local_static(self, def_id: DefId) -> bool {
692        self.codegen_fn_attrs(def_id).flags.contains(CodegenFnAttrFlags::THREAD_LOCAL)
693    }
694
695    /// Returns `true` if the node pointed to by `def_id` is a mutable `static` item.
696    #[inline]
697    pub fn is_mutable_static(self, def_id: DefId) -> bool {
698        self.static_mutability(def_id) == Some(hir::Mutability::Mut)
699    }
700
701    /// Returns `true` if the item pointed to by `def_id` is a thread local which needs a
702    /// thread local shim generated.
703    #[inline]
704    pub fn needs_thread_local_shim(self, def_id: DefId) -> bool {
705        !self.sess.target.dll_tls_export
706            && self.is_thread_local_static(def_id)
707            && !self.is_foreign_item(def_id)
708    }
709
710    /// Returns the type a reference to the thread local takes in MIR.
711    pub fn thread_local_ptr_ty(self, def_id: DefId) -> Ty<'tcx> {
712        let static_ty = self.type_of(def_id).instantiate_identity();
713        if self.is_mutable_static(def_id) {
714            Ty::new_mut_ptr(self, static_ty)
715        } else if self.is_foreign_item(def_id) {
716            Ty::new_imm_ptr(self, static_ty)
717        } else {
718            // FIXME: These things don't *really* have 'static lifetime.
719            Ty::new_imm_ref(self, self.lifetimes.re_static, static_ty)
720        }
721    }
722
723    /// Get the type of the pointer to the static that we use in MIR.
724    pub fn static_ptr_ty(self, def_id: DefId, typing_env: ty::TypingEnv<'tcx>) -> Ty<'tcx> {
725        // Make sure that any constants in the static's type are evaluated.
726        let static_ty =
727            self.normalize_erasing_regions(typing_env, self.type_of(def_id).instantiate_identity());
728
729        // Make sure that accesses to unsafe statics end up using raw pointers.
730        // For thread-locals, this needs to be kept in sync with `Rvalue::ty`.
731        if self.is_mutable_static(def_id) {
732            Ty::new_mut_ptr(self, static_ty)
733        } else if self.is_foreign_item(def_id) {
734            Ty::new_imm_ptr(self, static_ty)
735        } else {
736            Ty::new_imm_ref(self, self.lifetimes.re_erased, static_ty)
737        }
738    }
739
740    /// Expands the given impl trait type, stopping if the type is recursive.
741    #[instrument(skip(self), level = "debug", ret)]
742    pub fn try_expand_impl_trait_type(
743        self,
744        def_id: DefId,
745        args: GenericArgsRef<'tcx>,
746    ) -> Result<Ty<'tcx>, Ty<'tcx>> {
747        let mut visitor = OpaqueTypeExpander {
748            seen_opaque_tys: FxHashSet::default(),
749            expanded_cache: FxHashMap::default(),
750            primary_def_id: Some(def_id),
751            found_recursion: false,
752            found_any_recursion: false,
753            check_recursion: true,
754            tcx: self,
755        };
756
757        let expanded_type = visitor.expand_opaque_ty(def_id, args).unwrap();
758        if visitor.found_recursion { Err(expanded_type) } else { Ok(expanded_type) }
759    }
760
761    /// Query and get an English description for the item's kind.
762    pub fn def_descr(self, def_id: DefId) -> &'static str {
763        self.def_kind_descr(self.def_kind(def_id), def_id)
764    }
765
766    /// Get an English description for the item's kind.
767    pub fn def_kind_descr(self, def_kind: DefKind, def_id: DefId) -> &'static str {
768        match def_kind {
769            DefKind::AssocFn if self.associated_item(def_id).is_method() => "method",
770            DefKind::Closure if let Some(coroutine_kind) = self.coroutine_kind(def_id) => {
771                match coroutine_kind {
772                    hir::CoroutineKind::Desugared(
773                        hir::CoroutineDesugaring::Async,
774                        hir::CoroutineSource::Fn,
775                    ) => "async fn",
776                    hir::CoroutineKind::Desugared(
777                        hir::CoroutineDesugaring::Async,
778                        hir::CoroutineSource::Block,
779                    ) => "async block",
780                    hir::CoroutineKind::Desugared(
781                        hir::CoroutineDesugaring::Async,
782                        hir::CoroutineSource::Closure,
783                    ) => "async closure",
784                    hir::CoroutineKind::Desugared(
785                        hir::CoroutineDesugaring::AsyncGen,
786                        hir::CoroutineSource::Fn,
787                    ) => "async gen fn",
788                    hir::CoroutineKind::Desugared(
789                        hir::CoroutineDesugaring::AsyncGen,
790                        hir::CoroutineSource::Block,
791                    ) => "async gen block",
792                    hir::CoroutineKind::Desugared(
793                        hir::CoroutineDesugaring::AsyncGen,
794                        hir::CoroutineSource::Closure,
795                    ) => "async gen closure",
796                    hir::CoroutineKind::Desugared(
797                        hir::CoroutineDesugaring::Gen,
798                        hir::CoroutineSource::Fn,
799                    ) => "gen fn",
800                    hir::CoroutineKind::Desugared(
801                        hir::CoroutineDesugaring::Gen,
802                        hir::CoroutineSource::Block,
803                    ) => "gen block",
804                    hir::CoroutineKind::Desugared(
805                        hir::CoroutineDesugaring::Gen,
806                        hir::CoroutineSource::Closure,
807                    ) => "gen closure",
808                    hir::CoroutineKind::Coroutine(_) => "coroutine",
809                }
810            }
811            _ => def_kind.descr(def_id),
812        }
813    }
814
815    /// Gets an English article for the [`TyCtxt::def_descr`].
816    pub fn def_descr_article(self, def_id: DefId) -> &'static str {
817        self.def_kind_descr_article(self.def_kind(def_id), def_id)
818    }
819
820    /// Gets an English article for the [`TyCtxt::def_kind_descr`].
821    pub fn def_kind_descr_article(self, def_kind: DefKind, def_id: DefId) -> &'static str {
822        match def_kind {
823            DefKind::AssocFn if self.associated_item(def_id).is_method() => "a",
824            DefKind::Closure if let Some(coroutine_kind) = self.coroutine_kind(def_id) => {
825                match coroutine_kind {
826                    hir::CoroutineKind::Desugared(hir::CoroutineDesugaring::Async, ..) => "an",
827                    hir::CoroutineKind::Desugared(hir::CoroutineDesugaring::AsyncGen, ..) => "an",
828                    hir::CoroutineKind::Desugared(hir::CoroutineDesugaring::Gen, ..) => "a",
829                    hir::CoroutineKind::Coroutine(_) => "a",
830                }
831            }
832            _ => def_kind.article(),
833        }
834    }
835
836    /// Return `true` if the supplied `CrateNum` is "user-visible," meaning either a [public]
837    /// dependency, or a [direct] private dependency. This is used to decide whether the crate can
838    /// be shown in `impl` suggestions.
839    ///
840    /// [public]: TyCtxt::is_private_dep
841    /// [direct]: rustc_session::cstore::ExternCrate::is_direct
842    pub fn is_user_visible_dep(self, key: CrateNum) -> bool {
843        // `#![rustc_private]` overrides defaults to make private dependencies usable.
844        if self.features().enabled(sym::rustc_private) {
845            return true;
846        }
847
848        // | Private | Direct | Visible |                    |
849        // |---------|--------|---------|--------------------|
850        // | Yes     | Yes    | Yes     | !true || true   |
851        // | No      | Yes    | Yes     | !false || true  |
852        // | Yes     | No     | No      | !true || false  |
853        // | No      | No     | Yes     | !false || false |
854        !self.is_private_dep(key)
855            // If `extern_crate` is `None`, then the crate was injected (e.g., by the allocator).
856            // Treat that kind of crate as "indirect", since it's an implementation detail of
857            // the language.
858            || self.extern_crate(key).is_some_and(|e| e.is_direct())
859    }
860
861    /// Expand any [free alias types][free] contained within the given `value`.
862    ///
863    /// This should be used over other normalization routines in situations where
864    /// it's important not to normalize other alias types and where the predicates
865    /// on the corresponding type alias shouldn't be taken into consideration.
866    ///
867    /// Whenever possible **prefer not to use this function**! Instead, use standard
868    /// normalization routines or if feasible don't normalize at all.
869    ///
870    /// This function comes in handy if you want to mimic the behavior of eager
871    /// type alias expansion in a localized manner.
872    ///
873    /// <div class="warning">
874    /// This delays a bug on overflow! Therefore you need to be certain that the
875    /// contained types get fully normalized at a later stage. Note that even on
876    /// overflow all well-behaved free alias types get expanded correctly, so the
877    /// result is still useful.
878    /// </div>
879    ///
880    /// [free]: ty::Free
881    pub fn expand_free_alias_tys<T: TypeFoldable<TyCtxt<'tcx>>>(self, value: T) -> T {
882        value.fold_with(&mut FreeAliasTypeExpander { tcx: self, depth: 0 })
883    }
884
885    /// Peel off all [free alias types] in this type until there are none left.
886    ///
887    /// This only expands free alias types in “head” / outermost positions. It can
888    /// be used over [expand_free_alias_tys] as an optimization in situations where
889    /// one only really cares about the *kind* of the final aliased type but not
890    /// the types the other constituent types alias.
891    ///
892    /// <div class="warning">
893    /// This delays a bug on overflow! Therefore you need to be certain that the
894    /// type gets fully normalized at a later stage.
895    /// </div>
896    ///
897    /// [free]: ty::Free
898    /// [expand_free_alias_tys]: Self::expand_free_alias_tys
899    pub fn peel_off_free_alias_tys(self, mut ty: Ty<'tcx>) -> Ty<'tcx> {
900        let ty::Alias(ty::Free, _) = ty.kind() else { return ty };
901
902        let limit = self.recursion_limit();
903        let mut depth = 0;
904
905        while let ty::Alias(ty::Free, alias) = ty.kind() {
906            if !limit.value_within_limit(depth) {
907                let guar = self.dcx().delayed_bug("overflow expanding free alias type");
908                return Ty::new_error(self, guar);
909            }
910
911            ty = self.type_of(alias.def_id).instantiate(self, alias.args);
912            depth += 1;
913        }
914
915        ty
916    }
917
918    // Computes the variances for an alias (opaque or RPITIT) that represent
919    // its (un)captured regions.
920    pub fn opt_alias_variances(
921        self,
922        kind: impl Into<ty::AliasTermKind>,
923        def_id: DefId,
924    ) -> Option<&'tcx [ty::Variance]> {
925        match kind.into() {
926            ty::AliasTermKind::ProjectionTy => {
927                if self.is_impl_trait_in_trait(def_id) {
928                    Some(self.variances_of(def_id))
929                } else {
930                    None
931                }
932            }
933            ty::AliasTermKind::OpaqueTy => Some(self.variances_of(def_id)),
934            ty::AliasTermKind::InherentTy
935            | ty::AliasTermKind::InherentConst
936            | ty::AliasTermKind::FreeTy
937            | ty::AliasTermKind::FreeConst
938            | ty::AliasTermKind::UnevaluatedConst
939            | ty::AliasTermKind::ProjectionConst => None,
940        }
941    }
942}
943
944struct OpaqueTypeExpander<'tcx> {
945    // Contains the DefIds of the opaque types that are currently being
946    // expanded. When we expand an opaque type we insert the DefId of
947    // that type, and when we finish expanding that type we remove the
948    // its DefId.
949    seen_opaque_tys: FxHashSet<DefId>,
950    // Cache of all expansions we've seen so far. This is a critical
951    // optimization for some large types produced by async fn trees.
952    expanded_cache: FxHashMap<(DefId, GenericArgsRef<'tcx>), Ty<'tcx>>,
953    primary_def_id: Option<DefId>,
954    found_recursion: bool,
955    found_any_recursion: bool,
956    /// Whether or not to check for recursive opaque types.
957    /// This is `true` when we're explicitly checking for opaque type
958    /// recursion, and 'false' otherwise to avoid unnecessary work.
959    check_recursion: bool,
960    tcx: TyCtxt<'tcx>,
961}
962
963impl<'tcx> OpaqueTypeExpander<'tcx> {
964    fn expand_opaque_ty(&mut self, def_id: DefId, args: GenericArgsRef<'tcx>) -> Option<Ty<'tcx>> {
965        if self.found_any_recursion {
966            return None;
967        }
968        let args = args.fold_with(self);
969        if !self.check_recursion || self.seen_opaque_tys.insert(def_id) {
970            let expanded_ty = match self.expanded_cache.get(&(def_id, args)) {
971                Some(expanded_ty) => *expanded_ty,
972                None => {
973                    let generic_ty = self.tcx.type_of(def_id);
974                    let concrete_ty = generic_ty.instantiate(self.tcx, args);
975                    let expanded_ty = self.fold_ty(concrete_ty);
976                    self.expanded_cache.insert((def_id, args), expanded_ty);
977                    expanded_ty
978                }
979            };
980            if self.check_recursion {
981                self.seen_opaque_tys.remove(&def_id);
982            }
983            Some(expanded_ty)
984        } else {
985            // If another opaque type that we contain is recursive, then it
986            // will report the error, so we don't have to.
987            self.found_any_recursion = true;
988            self.found_recursion = def_id == *self.primary_def_id.as_ref().unwrap();
989            None
990        }
991    }
992}
993
994impl<'tcx> TypeFolder<TyCtxt<'tcx>> for OpaqueTypeExpander<'tcx> {
995    fn cx(&self) -> TyCtxt<'tcx> {
996        self.tcx
997    }
998
999    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
1000        if let ty::Alias(ty::Opaque, ty::AliasTy { def_id, args, .. }) = *t.kind() {
1001            self.expand_opaque_ty(def_id, args).unwrap_or(t)
1002        } else if t.has_opaque_types() {
1003            t.super_fold_with(self)
1004        } else {
1005            t
1006        }
1007    }
1008
1009    fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
1010        if let ty::PredicateKind::Clause(clause) = p.kind().skip_binder()
1011            && let ty::ClauseKind::Projection(projection_pred) = clause
1012        {
1013            p.kind()
1014                .rebind(ty::ProjectionPredicate {
1015                    projection_term: projection_pred.projection_term.fold_with(self),
1016                    // Don't fold the term on the RHS of the projection predicate.
1017                    // This is because for default trait methods with RPITITs, we
1018                    // install a `NormalizesTo(Projection(RPITIT) -> Opaque(RPITIT))`
1019                    // predicate, which would trivially cause a cycle when we do
1020                    // anything that requires `TypingEnv::with_post_analysis_normalized`.
1021                    term: projection_pred.term,
1022                })
1023                .upcast(self.tcx)
1024        } else {
1025            p.super_fold_with(self)
1026        }
1027    }
1028}
1029
1030struct FreeAliasTypeExpander<'tcx> {
1031    tcx: TyCtxt<'tcx>,
1032    depth: usize,
1033}
1034
1035impl<'tcx> TypeFolder<TyCtxt<'tcx>> for FreeAliasTypeExpander<'tcx> {
1036    fn cx(&self) -> TyCtxt<'tcx> {
1037        self.tcx
1038    }
1039
1040    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
1041        if !ty.has_type_flags(ty::TypeFlags::HAS_TY_FREE_ALIAS) {
1042            return ty;
1043        }
1044        let ty::Alias(ty::Free, alias) = ty.kind() else {
1045            return ty.super_fold_with(self);
1046        };
1047        if !self.tcx.recursion_limit().value_within_limit(self.depth) {
1048            let guar = self.tcx.dcx().delayed_bug("overflow expanding free alias type");
1049            return Ty::new_error(self.tcx, guar);
1050        }
1051
1052        self.depth += 1;
1053        ensure_sufficient_stack(|| {
1054            self.tcx.type_of(alias.def_id).instantiate(self.tcx, alias.args).fold_with(self)
1055        })
1056    }
1057
1058    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
1059        if !ct.has_type_flags(ty::TypeFlags::HAS_TY_FREE_ALIAS) {
1060            return ct;
1061        }
1062        ct.super_fold_with(self)
1063    }
1064}
1065
1066impl<'tcx> Ty<'tcx> {
1067    /// Returns the `Size` for primitive types (bool, uint, int, char, float).
1068    pub fn primitive_size(self, tcx: TyCtxt<'tcx>) -> Size {
1069        match *self.kind() {
1070            ty::Bool => Size::from_bytes(1),
1071            ty::Char => Size::from_bytes(4),
1072            ty::Int(ity) => Integer::from_int_ty(&tcx, ity).size(),
1073            ty::Uint(uty) => Integer::from_uint_ty(&tcx, uty).size(),
1074            ty::Float(fty) => Float::from_float_ty(fty).size(),
1075            _ => bug!("non primitive type"),
1076        }
1077    }
1078
1079    pub fn int_size_and_signed(self, tcx: TyCtxt<'tcx>) -> (Size, bool) {
1080        match *self.kind() {
1081            ty::Int(ity) => (Integer::from_int_ty(&tcx, ity).size(), true),
1082            ty::Uint(uty) => (Integer::from_uint_ty(&tcx, uty).size(), false),
1083            _ => bug!("non integer discriminant"),
1084        }
1085    }
1086
1087    /// Returns the minimum and maximum values for the given numeric type (including `char`s) or
1088    /// returns `None` if the type is not numeric.
1089    pub fn numeric_min_and_max_as_bits(self, tcx: TyCtxt<'tcx>) -> Option<(u128, u128)> {
1090        use rustc_apfloat::ieee::{Double, Half, Quad, Single};
1091        Some(match self.kind() {
1092            ty::Int(_) | ty::Uint(_) => {
1093                let (size, signed) = self.int_size_and_signed(tcx);
1094                let min = if signed { size.truncate(size.signed_int_min() as u128) } else { 0 };
1095                let max =
1096                    if signed { size.signed_int_max() as u128 } else { size.unsigned_int_max() };
1097                (min, max)
1098            }
1099            ty::Char => (0, std::char::MAX as u128),
1100            ty::Float(ty::FloatTy::F16) => ((-Half::INFINITY).to_bits(), Half::INFINITY.to_bits()),
1101            ty::Float(ty::FloatTy::F32) => {
1102                ((-Single::INFINITY).to_bits(), Single::INFINITY.to_bits())
1103            }
1104            ty::Float(ty::FloatTy::F64) => {
1105                ((-Double::INFINITY).to_bits(), Double::INFINITY.to_bits())
1106            }
1107            ty::Float(ty::FloatTy::F128) => ((-Quad::INFINITY).to_bits(), Quad::INFINITY.to_bits()),
1108            _ => return None,
1109        })
1110    }
1111
1112    /// Returns the maximum value for the given numeric type (including `char`s)
1113    /// or returns `None` if the type is not numeric.
1114    pub fn numeric_max_val(self, tcx: TyCtxt<'tcx>) -> Option<mir::Const<'tcx>> {
1115        let typing_env = TypingEnv::fully_monomorphized();
1116        self.numeric_min_and_max_as_bits(tcx)
1117            .map(|(_, max)| mir::Const::from_bits(tcx, max, typing_env, self))
1118    }
1119
1120    /// Returns the minimum value for the given numeric type (including `char`s)
1121    /// or returns `None` if the type is not numeric.
1122    pub fn numeric_min_val(self, tcx: TyCtxt<'tcx>) -> Option<mir::Const<'tcx>> {
1123        let typing_env = TypingEnv::fully_monomorphized();
1124        self.numeric_min_and_max_as_bits(tcx)
1125            .map(|(min, _)| mir::Const::from_bits(tcx, min, typing_env, self))
1126    }
1127
1128    /// Checks whether values of this type `T` have a size known at
1129    /// compile time (i.e., whether `T: Sized`). Lifetimes are ignored
1130    /// for the purposes of this check, so it can be an
1131    /// over-approximation in generic contexts, where one can have
1132    /// strange rules like `<T as Foo<'static>>::Bar: Sized` that
1133    /// actually carry lifetime requirements.
1134    pub fn is_sized(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
1135        self.is_trivially_sized(tcx) || tcx.is_sized_raw(typing_env.as_query_input(self))
1136    }
1137
1138    /// Checks whether values of this type `T` implement the `Freeze`
1139    /// trait -- frozen types are those that do not contain an
1140    /// `UnsafeCell` anywhere. This is a language concept used to
1141    /// distinguish "true immutability", which is relevant to
1142    /// optimization as well as the rules around static values. Note
1143    /// that the `Freeze` trait is not exposed to end users and is
1144    /// effectively an implementation detail.
1145    pub fn is_freeze(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
1146        self.is_trivially_freeze() || tcx.is_freeze_raw(typing_env.as_query_input(self))
1147    }
1148
1149    /// Fast path helper for testing if a type is `Freeze`.
1150    ///
1151    /// Returning true means the type is known to be `Freeze`. Returning
1152    /// `false` means nothing -- could be `Freeze`, might not be.
1153    pub fn is_trivially_freeze(self) -> bool {
1154        match self.kind() {
1155            ty::Int(_)
1156            | ty::Uint(_)
1157            | ty::Float(_)
1158            | ty::Bool
1159            | ty::Char
1160            | ty::Str
1161            | ty::Never
1162            | ty::Ref(..)
1163            | ty::RawPtr(_, _)
1164            | ty::FnDef(..)
1165            | ty::Error(_)
1166            | ty::FnPtr(..) => true,
1167            ty::Tuple(fields) => fields.iter().all(Self::is_trivially_freeze),
1168            ty::Pat(ty, _) | ty::Slice(ty) | ty::Array(ty, _) => ty.is_trivially_freeze(),
1169            ty::Adt(..)
1170            | ty::Bound(..)
1171            | ty::Closure(..)
1172            | ty::CoroutineClosure(..)
1173            | ty::Dynamic(..)
1174            | ty::Foreign(_)
1175            | ty::Coroutine(..)
1176            | ty::CoroutineWitness(..)
1177            | ty::UnsafeBinder(_)
1178            | ty::Infer(_)
1179            | ty::Alias(..)
1180            | ty::Param(_)
1181            | ty::Placeholder(_) => false,
1182        }
1183    }
1184
1185    /// Checks whether values of this type `T` implement the `Unpin` trait.
1186    pub fn is_unpin(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
1187        self.is_trivially_unpin() || tcx.is_unpin_raw(typing_env.as_query_input(self))
1188    }
1189
1190    /// Fast path helper for testing if a type is `Unpin`.
1191    ///
1192    /// Returning true means the type is known to be `Unpin`. Returning
1193    /// `false` means nothing -- could be `Unpin`, might not be.
1194    fn is_trivially_unpin(self) -> bool {
1195        match self.kind() {
1196            ty::Int(_)
1197            | ty::Uint(_)
1198            | ty::Float(_)
1199            | ty::Bool
1200            | ty::Char
1201            | ty::Str
1202            | ty::Never
1203            | ty::Ref(..)
1204            | ty::RawPtr(_, _)
1205            | ty::FnDef(..)
1206            | ty::Error(_)
1207            | ty::FnPtr(..) => true,
1208            ty::Tuple(fields) => fields.iter().all(Self::is_trivially_unpin),
1209            ty::Pat(ty, _) | ty::Slice(ty) | ty::Array(ty, _) => ty.is_trivially_unpin(),
1210            ty::Adt(..)
1211            | ty::Bound(..)
1212            | ty::Closure(..)
1213            | ty::CoroutineClosure(..)
1214            | ty::Dynamic(..)
1215            | ty::Foreign(_)
1216            | ty::Coroutine(..)
1217            | ty::CoroutineWitness(..)
1218            | ty::UnsafeBinder(_)
1219            | ty::Infer(_)
1220            | ty::Alias(..)
1221            | ty::Param(_)
1222            | ty::Placeholder(_) => false,
1223        }
1224    }
1225
1226    /// Checks whether this type is an ADT that has unsafe fields.
1227    pub fn has_unsafe_fields(self) -> bool {
1228        if let ty::Adt(adt_def, ..) = self.kind() {
1229            adt_def.all_fields().any(|x| x.safety.is_unsafe())
1230        } else {
1231            false
1232        }
1233    }
1234
1235    /// Checks whether values of this type `T` implement the `AsyncDrop` trait.
1236    pub fn is_async_drop(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
1237        !self.is_trivially_not_async_drop()
1238            && tcx.is_async_drop_raw(typing_env.as_query_input(self))
1239    }
1240
1241    /// Fast path helper for testing if a type is `AsyncDrop`.
1242    ///
1243    /// Returning true means the type is known to be `!AsyncDrop`. Returning
1244    /// `false` means nothing -- could be `AsyncDrop`, might not be.
1245    fn is_trivially_not_async_drop(self) -> bool {
1246        match self.kind() {
1247            ty::Int(_)
1248            | ty::Uint(_)
1249            | ty::Float(_)
1250            | ty::Bool
1251            | ty::Char
1252            | ty::Str
1253            | ty::Never
1254            | ty::Ref(..)
1255            | ty::RawPtr(..)
1256            | ty::FnDef(..)
1257            | ty::Error(_)
1258            | ty::FnPtr(..) => true,
1259            // FIXME(unsafe_binders):
1260            ty::UnsafeBinder(_) => todo!(),
1261            ty::Tuple(fields) => fields.iter().all(Self::is_trivially_not_async_drop),
1262            ty::Pat(elem_ty, _) | ty::Slice(elem_ty) | ty::Array(elem_ty, _) => {
1263                elem_ty.is_trivially_not_async_drop()
1264            }
1265            ty::Adt(..)
1266            | ty::Bound(..)
1267            | ty::Closure(..)
1268            | ty::CoroutineClosure(..)
1269            | ty::Dynamic(..)
1270            | ty::Foreign(_)
1271            | ty::Coroutine(..)
1272            | ty::CoroutineWitness(..)
1273            | ty::Infer(_)
1274            | ty::Alias(..)
1275            | ty::Param(_)
1276            | ty::Placeholder(_) => false,
1277        }
1278    }
1279
1280    /// If `ty.needs_drop(...)` returns `true`, then `ty` is definitely
1281    /// non-copy and *might* have a destructor attached; if it returns
1282    /// `false`, then `ty` definitely has no destructor (i.e., no drop glue).
1283    ///
1284    /// (Note that this implies that if `ty` has a destructor attached,
1285    /// then `needs_drop` will definitely return `true` for `ty`.)
1286    ///
1287    /// Note that this method is used to check eligible types in unions.
1288    #[inline]
1289    pub fn needs_drop(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
1290        // Avoid querying in simple cases.
1291        match needs_drop_components(tcx, self) {
1292            Err(AlwaysRequiresDrop) => true,
1293            Ok(components) => {
1294                let query_ty = match *components {
1295                    [] => return false,
1296                    // If we've got a single component, call the query with that
1297                    // to increase the chance that we hit the query cache.
1298                    [component_ty] => component_ty,
1299                    _ => self,
1300                };
1301
1302                // This doesn't depend on regions, so try to minimize distinct
1303                // query keys used. If normalization fails, we just use `query_ty`.
1304                debug_assert!(!typing_env.param_env.has_infer());
1305                let query_ty = tcx
1306                    .try_normalize_erasing_regions(typing_env, query_ty)
1307                    .unwrap_or_else(|_| tcx.erase_regions(query_ty));
1308
1309                tcx.needs_drop_raw(typing_env.as_query_input(query_ty))
1310            }
1311        }
1312    }
1313
1314    /// If `ty.needs_async_drop(...)` returns `true`, then `ty` is definitely
1315    /// non-copy and *might* have a async destructor attached; if it returns
1316    /// `false`, then `ty` definitely has no async destructor (i.e., no async
1317    /// drop glue).
1318    ///
1319    /// (Note that this implies that if `ty` has an async destructor attached,
1320    /// then `needs_async_drop` will definitely return `true` for `ty`.)
1321    ///
1322    // FIXME(zetanumbers): Note that this method is used to check eligible types
1323    // in unions.
1324    #[inline]
1325    pub fn needs_async_drop(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
1326        // Avoid querying in simple cases.
1327        match needs_drop_components(tcx, self) {
1328            Err(AlwaysRequiresDrop) => true,
1329            Ok(components) => {
1330                let query_ty = match *components {
1331                    [] => return false,
1332                    // If we've got a single component, call the query with that
1333                    // to increase the chance that we hit the query cache.
1334                    [component_ty] => component_ty,
1335                    _ => self,
1336                };
1337
1338                // This doesn't depend on regions, so try to minimize distinct
1339                // query keys used.
1340                // If normalization fails, we just use `query_ty`.
1341                debug_assert!(!typing_env.has_infer());
1342                let query_ty = tcx
1343                    .try_normalize_erasing_regions(typing_env, query_ty)
1344                    .unwrap_or_else(|_| tcx.erase_regions(query_ty));
1345
1346                tcx.needs_async_drop_raw(typing_env.as_query_input(query_ty))
1347            }
1348        }
1349    }
1350
1351    /// Checks if `ty` has a significant drop.
1352    ///
1353    /// Note that this method can return false even if `ty` has a destructor
1354    /// attached; even if that is the case then the adt has been marked with
1355    /// the attribute `rustc_insignificant_dtor`.
1356    ///
1357    /// Note that this method is used to check for change in drop order for
1358    /// 2229 drop reorder migration analysis.
1359    #[inline]
1360    pub fn has_significant_drop(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
1361        // Avoid querying in simple cases.
1362        match needs_drop_components(tcx, self) {
1363            Err(AlwaysRequiresDrop) => true,
1364            Ok(components) => {
1365                let query_ty = match *components {
1366                    [] => return false,
1367                    // If we've got a single component, call the query with that
1368                    // to increase the chance that we hit the query cache.
1369                    [component_ty] => component_ty,
1370                    _ => self,
1371                };
1372
1373                // FIXME(#86868): We should be canonicalizing, or else moving this to a method of inference
1374                // context, or *something* like that, but for now just avoid passing inference
1375                // variables to queries that can't cope with them. Instead, conservatively
1376                // return "true" (may change drop order).
1377                if query_ty.has_infer() {
1378                    return true;
1379                }
1380
1381                // This doesn't depend on regions, so try to minimize distinct
1382                // query keys used.
1383                let erased = tcx.normalize_erasing_regions(typing_env, query_ty);
1384                tcx.has_significant_drop_raw(typing_env.as_query_input(erased))
1385            }
1386        }
1387    }
1388
1389    /// Returns `true` if equality for this type is both reflexive and structural.
1390    ///
1391    /// Reflexive equality for a type is indicated by an `Eq` impl for that type.
1392    ///
1393    /// Primitive types (`u32`, `str`) have structural equality by definition. For composite data
1394    /// types, equality for the type as a whole is structural when it is the same as equality
1395    /// between all components (fields, array elements, etc.) of that type. For ADTs, structural
1396    /// equality is indicated by an implementation of `StructuralPartialEq` for that type.
1397    ///
1398    /// This function is "shallow" because it may return `true` for a composite type whose fields
1399    /// are not `StructuralPartialEq`. For example, `[T; 4]` has structural equality regardless of `T`
1400    /// because equality for arrays is determined by the equality of each array element. If you
1401    /// want to know whether a given call to `PartialEq::eq` will proceed structurally all the way
1402    /// down, you will need to use a type visitor.
1403    #[inline]
1404    pub fn is_structural_eq_shallow(self, tcx: TyCtxt<'tcx>) -> bool {
1405        match self.kind() {
1406            // Look for an impl of `StructuralPartialEq`.
1407            ty::Adt(..) => tcx.has_structural_eq_impl(self),
1408
1409            // Primitive types that satisfy `Eq`.
1410            ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Str | ty::Never => true,
1411
1412            // Composite types that satisfy `Eq` when all of their fields do.
1413            //
1414            // Because this function is "shallow", we return `true` for these composites regardless
1415            // of the type(s) contained within.
1416            ty::Pat(..) | ty::Ref(..) | ty::Array(..) | ty::Slice(_) | ty::Tuple(..) => true,
1417
1418            // Raw pointers use bitwise comparison.
1419            ty::RawPtr(_, _) | ty::FnPtr(..) => true,
1420
1421            // Floating point numbers are not `Eq`.
1422            ty::Float(_) => false,
1423
1424            // Conservatively return `false` for all others...
1425
1426            // Anonymous function types
1427            ty::FnDef(..)
1428            | ty::Closure(..)
1429            | ty::CoroutineClosure(..)
1430            | ty::Dynamic(..)
1431            | ty::Coroutine(..) => false,
1432
1433            // Generic or inferred types
1434            //
1435            // FIXME(ecstaticmorse): Maybe we should `bug` here? This should probably only be
1436            // called for known, fully-monomorphized types.
1437            ty::Alias(..) | ty::Param(_) | ty::Bound(..) | ty::Placeholder(_) | ty::Infer(_) => {
1438                false
1439            }
1440
1441            ty::Foreign(_) | ty::CoroutineWitness(..) | ty::Error(_) | ty::UnsafeBinder(_) => false,
1442        }
1443    }
1444
1445    /// Peel off all reference types in this type until there are none left.
1446    ///
1447    /// This method is idempotent, i.e. `ty.peel_refs().peel_refs() == ty.peel_refs()`.
1448    ///
1449    /// # Examples
1450    ///
1451    /// - `u8` -> `u8`
1452    /// - `&'a mut u8` -> `u8`
1453    /// - `&'a &'b u8` -> `u8`
1454    /// - `&'a *const &'b u8 -> *const &'b u8`
1455    pub fn peel_refs(self) -> Ty<'tcx> {
1456        let mut ty = self;
1457        while let ty::Ref(_, inner_ty, _) = ty.kind() {
1458            ty = *inner_ty;
1459        }
1460        ty
1461    }
1462
1463    // FIXME(compiler-errors): Think about removing this.
1464    #[inline]
1465    pub fn outer_exclusive_binder(self) -> ty::DebruijnIndex {
1466        self.0.outer_exclusive_binder
1467    }
1468}
1469
1470/// Returns a list of types such that the given type needs drop if and only if
1471/// *any* of the returned types need drop. Returns `Err(AlwaysRequiresDrop)` if
1472/// this type always needs drop.
1473//
1474// FIXME(zetanumbers): consider replacing this with only
1475// `needs_drop_components_with_async`
1476#[inline]
1477pub fn needs_drop_components<'tcx>(
1478    tcx: TyCtxt<'tcx>,
1479    ty: Ty<'tcx>,
1480) -> Result<SmallVec<[Ty<'tcx>; 2]>, AlwaysRequiresDrop> {
1481    needs_drop_components_with_async(tcx, ty, Asyncness::No)
1482}
1483
1484/// Returns a list of types such that the given type needs drop if and only if
1485/// *any* of the returned types need drop. Returns `Err(AlwaysRequiresDrop)` if
1486/// this type always needs drop.
1487pub fn needs_drop_components_with_async<'tcx>(
1488    tcx: TyCtxt<'tcx>,
1489    ty: Ty<'tcx>,
1490    asyncness: Asyncness,
1491) -> Result<SmallVec<[Ty<'tcx>; 2]>, AlwaysRequiresDrop> {
1492    match *ty.kind() {
1493        ty::Infer(ty::FreshIntTy(_))
1494        | ty::Infer(ty::FreshFloatTy(_))
1495        | ty::Bool
1496        | ty::Int(_)
1497        | ty::Uint(_)
1498        | ty::Float(_)
1499        | ty::Never
1500        | ty::FnDef(..)
1501        | ty::FnPtr(..)
1502        | ty::Char
1503        | ty::RawPtr(_, _)
1504        | ty::Ref(..)
1505        | ty::Str => Ok(SmallVec::new()),
1506
1507        // Foreign types can never have destructors.
1508        ty::Foreign(..) => Ok(SmallVec::new()),
1509
1510        // FIXME(zetanumbers): Temporary workaround for async drop of dynamic types
1511        ty::Dynamic(..) | ty::Error(_) => {
1512            if asyncness.is_async() {
1513                Ok(SmallVec::new())
1514            } else {
1515                Err(AlwaysRequiresDrop)
1516            }
1517        }
1518
1519        ty::Pat(ty, _) | ty::Slice(ty) => needs_drop_components_with_async(tcx, ty, asyncness),
1520        ty::Array(elem_ty, size) => {
1521            match needs_drop_components_with_async(tcx, elem_ty, asyncness) {
1522                Ok(v) if v.is_empty() => Ok(v),
1523                res => match size.try_to_target_usize(tcx) {
1524                    // Arrays of size zero don't need drop, even if their element
1525                    // type does.
1526                    Some(0) => Ok(SmallVec::new()),
1527                    Some(_) => res,
1528                    // We don't know which of the cases above we are in, so
1529                    // return the whole type and let the caller decide what to
1530                    // do.
1531                    None => Ok(smallvec![ty]),
1532                },
1533            }
1534        }
1535        // If any field needs drop, then the whole tuple does.
1536        ty::Tuple(fields) => fields.iter().try_fold(SmallVec::new(), move |mut acc, elem| {
1537            acc.extend(needs_drop_components_with_async(tcx, elem, asyncness)?);
1538            Ok(acc)
1539        }),
1540
1541        // These require checking for `Copy` bounds or `Adt` destructors.
1542        ty::Adt(..)
1543        | ty::Alias(..)
1544        | ty::Param(_)
1545        | ty::Bound(..)
1546        | ty::Placeholder(..)
1547        | ty::Infer(_)
1548        | ty::Closure(..)
1549        | ty::CoroutineClosure(..)
1550        | ty::Coroutine(..)
1551        | ty::CoroutineWitness(..)
1552        | ty::UnsafeBinder(_) => Ok(smallvec![ty]),
1553    }
1554}
1555
1556/// Does the equivalent of
1557/// ```ignore (illustrative)
1558/// let v = self.iter().map(|p| p.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
1559/// folder.tcx().intern_*(&v)
1560/// ```
1561pub fn fold_list<'tcx, F, L, T>(
1562    list: L,
1563    folder: &mut F,
1564    intern: impl FnOnce(TyCtxt<'tcx>, &[T]) -> L,
1565) -> L
1566where
1567    F: TypeFolder<TyCtxt<'tcx>>,
1568    L: AsRef<[T]>,
1569    T: TypeFoldable<TyCtxt<'tcx>> + PartialEq + Copy,
1570{
1571    let slice = list.as_ref();
1572    let mut iter = slice.iter().copied();
1573    // Look for the first element that changed
1574    match iter.by_ref().enumerate().find_map(|(i, t)| {
1575        let new_t = t.fold_with(folder);
1576        if new_t != t { Some((i, new_t)) } else { None }
1577    }) {
1578        Some((i, new_t)) => {
1579            // An element changed, prepare to intern the resulting list
1580            let mut new_list = SmallVec::<[_; 8]>::with_capacity(slice.len());
1581            new_list.extend_from_slice(&slice[..i]);
1582            new_list.push(new_t);
1583            for t in iter {
1584                new_list.push(t.fold_with(folder))
1585            }
1586            intern(folder.cx(), &new_list)
1587        }
1588        None => list,
1589    }
1590}
1591
1592/// Does the equivalent of
1593/// ```ignore (illustrative)
1594/// let v = self.iter().map(|p| p.try_fold_with(folder)).collect::<SmallVec<[_; 8]>>();
1595/// folder.tcx().intern_*(&v)
1596/// ```
1597pub fn try_fold_list<'tcx, F, L, T>(
1598    list: L,
1599    folder: &mut F,
1600    intern: impl FnOnce(TyCtxt<'tcx>, &[T]) -> L,
1601) -> Result<L, F::Error>
1602where
1603    F: FallibleTypeFolder<TyCtxt<'tcx>>,
1604    L: AsRef<[T]>,
1605    T: TypeFoldable<TyCtxt<'tcx>> + PartialEq + Copy,
1606{
1607    let slice = list.as_ref();
1608    let mut iter = slice.iter().copied();
1609    // Look for the first element that changed
1610    match iter.by_ref().enumerate().find_map(|(i, t)| match t.try_fold_with(folder) {
1611        Ok(new_t) if new_t == t => None,
1612        new_t => Some((i, new_t)),
1613    }) {
1614        Some((i, Ok(new_t))) => {
1615            // An element changed, prepare to intern the resulting list
1616            let mut new_list = SmallVec::<[_; 8]>::with_capacity(slice.len());
1617            new_list.extend_from_slice(&slice[..i]);
1618            new_list.push(new_t);
1619            for t in iter {
1620                new_list.push(t.try_fold_with(folder)?)
1621            }
1622            Ok(intern(folder.cx(), &new_list))
1623        }
1624        Some((_, Err(err))) => {
1625            return Err(err);
1626        }
1627        None => Ok(list),
1628    }
1629}
1630
1631#[derive(Copy, Clone, Debug, HashStable, TyEncodable, TyDecodable)]
1632pub struct AlwaysRequiresDrop;
1633
1634/// Reveals all opaque types in the given value, replacing them
1635/// with their underlying types.
1636pub fn reveal_opaque_types_in_bounds<'tcx>(
1637    tcx: TyCtxt<'tcx>,
1638    val: ty::Clauses<'tcx>,
1639) -> ty::Clauses<'tcx> {
1640    assert!(!tcx.next_trait_solver_globally());
1641    let mut visitor = OpaqueTypeExpander {
1642        seen_opaque_tys: FxHashSet::default(),
1643        expanded_cache: FxHashMap::default(),
1644        primary_def_id: None,
1645        found_recursion: false,
1646        found_any_recursion: false,
1647        check_recursion: false,
1648        tcx,
1649    };
1650    val.fold_with(&mut visitor)
1651}
1652
1653/// Determines whether an item is directly annotated with `doc(hidden)`.
1654fn is_doc_hidden(tcx: TyCtxt<'_>, def_id: LocalDefId) -> bool {
1655    tcx.get_attrs(def_id, sym::doc)
1656        .filter_map(|attr| attr.meta_item_list())
1657        .any(|items| items.iter().any(|item| item.has_name(sym::hidden)))
1658}
1659
1660/// Determines whether an item is annotated with `doc(notable_trait)`.
1661pub fn is_doc_notable_trait(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
1662    tcx.get_attrs(def_id, sym::doc)
1663        .filter_map(|attr| attr.meta_item_list())
1664        .any(|items| items.iter().any(|item| item.has_name(sym::notable_trait)))
1665}
1666
1667/// Determines whether an item is an intrinsic (which may be via Abi or via the `rustc_intrinsic` attribute).
1668///
1669/// We double check the feature gate here because whether a function may be defined as an intrinsic causes
1670/// the compiler to make some assumptions about its shape; if the user doesn't use a feature gate, they may
1671/// cause an ICE that we otherwise may want to prevent.
1672pub fn intrinsic_raw(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Option<ty::IntrinsicDef> {
1673    if tcx.features().intrinsics() && tcx.has_attr(def_id, sym::rustc_intrinsic) {
1674        let must_be_overridden = match tcx.hir_node_by_def_id(def_id) {
1675            hir::Node::Item(hir::Item { kind: hir::ItemKind::Fn { has_body, .. }, .. }) => {
1676                !has_body
1677            }
1678            _ => true,
1679        };
1680        Some(ty::IntrinsicDef {
1681            name: tcx.item_name(def_id.into()),
1682            must_be_overridden,
1683            const_stable: tcx.has_attr(def_id, sym::rustc_intrinsic_const_stable_indirect),
1684        })
1685    } else {
1686        None
1687    }
1688}
1689
1690pub fn provide(providers: &mut Providers) {
1691    *providers = Providers {
1692        reveal_opaque_types_in_bounds,
1693        is_doc_hidden,
1694        is_doc_notable_trait,
1695        intrinsic_raw,
1696        ..*providers
1697    }
1698}