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