compiler/rustc_middle/src/ty/util.rs

   1 //! Miscellaneous type-system utilities that are too small to deserve their own modules.
   2
   3 use crate::middle::codegen_fn_attrs::CodegenFnAttrFlags;
   4 use crate::ty::layout::IntegerExt;
   5 use crate::ty::{
   6     self, DefIdTree, FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable,
   7     TypeVisitable,
   8 };
   9 use crate::ty::{GenericArgKind, SubstsRef};
  10 use rustc_apfloat::Float as _;
  11 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  12 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  13 use rustc_errors::ErrorGuaranteed;
  14 use rustc_hir as hir;
  15 use rustc_hir::def::{CtorOf, DefKind, Res};
  16 use rustc_hir::def_id::DefId;
  17 use rustc_index::bit_set::GrowableBitSet;
  18 use rustc_macros::HashStable;
  19 use rustc_span::{sym, DUMMY_SP};
  20 use rustc_target::abi::{Integer, IntegerType, Size, TargetDataLayout};
  21 use rustc_target::spec::abi::Abi;
  22 use smallvec::SmallVec;
  23 use std::{fmt, iter};
  24
  25 #[derive(Copy, Clone, Debug)]
  26 pub struct Discr<'tcx> {
  27     /// Bit representation of the discriminant (e.g., `-128i8` is `0xFF_u128`).
  28     pub val: u128,
  29     pub ty: Ty<'tcx>,
  30 }
  31
  32 /// Used as an input to [`TyCtxt::uses_unique_generic_params`].
  33 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  34 pub enum IgnoreRegions {
  35     Yes,
  36     No,
  37 }
  38
  39 #[derive(Copy, Clone, Debug)]
  40 pub enum NotUniqueParam<'tcx> {
  41     DuplicateParam(ty::GenericArg<'tcx>),
  42     NotParam(ty::GenericArg<'tcx>),
  43 }
  44
  45 impl<'tcx> fmt::Display for Discr<'tcx> {
  46     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
  47         match *self.ty.kind() {
  48             ty::Int(ity) => {
  49                 let size = ty::tls::with(|tcx| Integer::from_int_ty(&tcx, ity).size());
  50                 let x = self.val;
  51                 // sign extend the raw representation to be an i128
  52                 let x = size.sign_extend(x) as i128;
  53                 write!(fmt, "{}", x)
  54             }
  55             _ => write!(fmt, "{}", self.val),
  56         }
  57     }
  58 }
  59
  60 fn int_size_and_signed<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> (Size, bool) {
  61     let (int, signed) = match *ty.kind() {
  62         ty::Int(ity) => (Integer::from_int_ty(&tcx, ity), true),
  63         ty::Uint(uty) => (Integer::from_uint_ty(&tcx, uty), false),
  64         _ => bug!("non integer discriminant"),
  65     };
  66     (int.size(), signed)
  67 }
  68
  69 impl<'tcx> Discr<'tcx> {
  70     /// Adds `1` to the value and wraps around if the maximum for the type is reached.
  71     pub fn wrap_incr(self, tcx: TyCtxt<'tcx>) -> Self {
  72         self.checked_add(tcx, 1).0
  73     }
  74     pub fn checked_add(self, tcx: TyCtxt<'tcx>, n: u128) -> (Self, bool) {
  75         let (size, signed) = int_size_and_signed(tcx, self.ty);
  76         let (val, oflo) = if signed {
  77             let min = size.signed_int_min();
  78             let max = size.signed_int_max();
  79             let val = size.sign_extend(self.val) as i128;
  80             assert!(n < (i128::MAX as u128));
  81             let n = n as i128;
  82             let oflo = val > max - n;
  83             let val = if oflo { min + (n - (max - val) - 1) } else { val + n };
  84             // zero the upper bits
  85             let val = val as u128;
  86             let val = size.truncate(val);
  87             (val, oflo)
  88         } else {
  89             let max = size.unsigned_int_max();
  90             let val = self.val;
  91             let oflo = val > max - n;
  92             let val = if oflo { n - (max - val) - 1 } else { val + n };
  93             (val, oflo)
  94         };
  95         (Self { val, ty: self.ty }, oflo)
  96     }
  97 }
  98
  99 pub trait IntTypeExt {
 100     fn to_ty<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx>;
 101     fn disr_incr<'tcx>(&self, tcx: TyCtxt<'tcx>, val: Option<Discr<'tcx>>) -> Option<Discr<'tcx>>;
 102     fn initial_discriminant<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Discr<'tcx>;
 103 }
 104
 105 impl IntTypeExt for 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
 129 impl<'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>) -> u64 {
 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     pub fn has_error_field(self, ty: Ty<'tcx>) -> bool {
 177         if let ty::Adt(def, substs) = *ty.kind() {
 178             for field in def.all_fields() {
 179                 let field_ty = field.ty(self, substs);
 180                 if let ty::Error(_) = field_ty.kind() {
 181                     return true;
 182                 }
 183             }
 184         }
 185         false
 186     }
 187
 188     /// Attempts to returns the deeply last field of nested structures, but
 189     /// does not apply any normalization in its search. Returns the same type
 190     /// if input `ty` is not a structure at all.
 191     pub fn struct_tail_without_normalization(self, ty: Ty<'tcx>) -> Ty<'tcx> {
 192         let tcx = self;
 193         tcx.struct_tail_with_normalize(ty, |ty| ty, || {})
 194     }
 195
 196     /// Returns the deeply last field of nested structures, or the same type if
 197     /// not a structure at all. Corresponds to the only possible unsized field,
 198     /// and its type can be used to determine unsizing strategy.
 199     ///
 200     /// Should only be called if `ty` has no inference variables and does not
 201     /// need its lifetimes preserved (e.g. as part of codegen); otherwise
 202     /// normalization attempt may cause compiler bugs.
 203     pub fn struct_tail_erasing_lifetimes(
 204         self,
 205         ty: Ty<'tcx>,
 206         param_env: ty::ParamEnv<'tcx>,
 207     ) -> Ty<'tcx> {
 208         let tcx = self;
 209         tcx.struct_tail_with_normalize(ty, |ty| tcx.normalize_erasing_regions(param_env, ty), || {})
 210     }
 211
 212     /// Returns the deeply last field of nested structures, or the same type if
 213     /// not a structure at all. Corresponds to the only possible unsized field,
 214     /// and its type can be used to determine unsizing strategy.
 215     ///
 216     /// This is parameterized over the normalization strategy (i.e. how to
 217     /// handle `<T as Trait>::Assoc` and `impl Trait`); pass the identity
 218     /// function to indicate no normalization should take place.
 219     ///
 220     /// See also `struct_tail_erasing_lifetimes`, which is suitable for use
 221     /// during codegen.
 222     pub fn struct_tail_with_normalize(
 223         self,
 224         mut ty: Ty<'tcx>,
 225         mut normalize: impl FnMut(Ty<'tcx>) -> Ty<'tcx>,
 226         // This is currently used to allow us to walk a ValTree
 227         // in lockstep with the type in order to get the ValTree branch that
 228         // corresponds to an unsized field.
 229         mut f: impl FnMut() -> (),
 230     ) -> Ty<'tcx> {
 231         let recursion_limit = self.recursion_limit();
 232         for iteration in 0.. {
 233             if !recursion_limit.value_within_limit(iteration) {
 234                 return self.ty_error_with_message(
 235                     DUMMY_SP,
 236                     &format!("reached the recursion limit finding the struct tail for {}", ty),
 237                 );
 238             }
 239             match *ty.kind() {
 240                 ty::Adt(def, substs) => {
 241                     if !def.is_struct() {
 242                         break;
 243                     }
 244                     match def.non_enum_variant().fields.last() {
 245                         Some(field) => {
 246                             f();
 247                             ty = field.ty(self, substs);
 248                         }
 249                         None => break,
 250                     }
 251                 }
 252
 253                 ty::Tuple(tys) if let Some((&last_ty, _)) = tys.split_last() => {
 254                     f();
 255                     ty = last_ty;
 256                 }
 257
 258                 ty::Tuple(_) => break,
 259
 260                 ty::Projection(_) | ty::Opaque(..) => {
 261                     let normalized = normalize(ty);
 262                     if ty == normalized {
 263                         return ty;
 264                     } else {
 265                         ty = normalized;
 266                     }
 267                 }
 268
 269                 _ => {
 270                     break;
 271                 }
 272             }
 273         }
 274         ty
 275     }
 276
 277     /// Same as applying `struct_tail` on `source` and `target`, but only
 278     /// keeps going as long as the two types are instances of the same
 279     /// structure definitions.
 280     /// For `(Foo<Foo<T>>, Foo<dyn Trait>)`, the result will be `(Foo<T>, Trait)`,
 281     /// whereas struct_tail produces `T`, and `Trait`, respectively.
 282     ///
 283     /// Should only be called if the types have no inference variables and do
 284     /// not need their lifetimes preserved (e.g., as part of codegen); otherwise,
 285     /// normalization attempt may cause compiler bugs.
 286     pub fn struct_lockstep_tails_erasing_lifetimes(
 287         self,
 288         source: Ty<'tcx>,
 289         target: Ty<'tcx>,
 290         param_env: ty::ParamEnv<'tcx>,
 291     ) -> (Ty<'tcx>, Ty<'tcx>) {
 292         let tcx = self;
 293         tcx.struct_lockstep_tails_with_normalize(source, target, |ty| {
 294             tcx.normalize_erasing_regions(param_env, ty)
 295         })
 296     }
 297
 298     /// Same as applying `struct_tail` on `source` and `target`, but only
 299     /// keeps going as long as the two types are instances of the same
 300     /// structure definitions.
 301     /// For `(Foo<Foo<T>>, Foo<dyn Trait>)`, the result will be `(Foo<T>, Trait)`,
 302     /// whereas struct_tail produces `T`, and `Trait`, respectively.
 303     ///
 304     /// See also `struct_lockstep_tails_erasing_lifetimes`, which is suitable for use
 305     /// during codegen.
 306     pub fn struct_lockstep_tails_with_normalize(
 307         self,
 308         source: Ty<'tcx>,
 309         target: Ty<'tcx>,
 310         normalize: impl Fn(Ty<'tcx>) -> Ty<'tcx>,
 311     ) -> (Ty<'tcx>, Ty<'tcx>) {
 312         let (mut a, mut b) = (source, target);
 313         loop {
 314             match (&a.kind(), &b.kind()) {
 315                 (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs))
 316                     if a_def == b_def && a_def.is_struct() =>
 317                 {
 318                     if let Some(f) = a_def.non_enum_variant().fields.last() {
 319                         a = f.ty(self, a_substs);
 320                         b = f.ty(self, b_substs);
 321                     } else {
 322                         break;
 323                     }
 324                 }
 325                 (&ty::Tuple(a_tys), &ty::Tuple(b_tys)) if a_tys.len() == b_tys.len() => {
 326                     if let Some(&a_last) = a_tys.last() {
 327                         a = a_last;
 328                         b = *b_tys.last().unwrap();
 329                     } else {
 330                         break;
 331                     }
 332                 }
 333                 (ty::Projection(_) | ty::Opaque(..), _)
 334                 | (_, ty::Projection(_) | ty::Opaque(..)) => {
 335                     // If either side is a projection, attempt to
 336                     // progress via normalization. (Should be safe to
 337                     // apply to both sides as normalization is
 338                     // idempotent.)
 339                     let a_norm = normalize(a);
 340                     let b_norm = normalize(b);
 341                     if a == a_norm && b == b_norm {
 342                         break;
 343                     } else {
 344                         a = a_norm;
 345                         b = b_norm;
 346                     }
 347                 }
 348
 349                 _ => break,
 350             }
 351         }
 352         (a, b)
 353     }
 354
 355     /// Calculate the destructor of a given type.
 356     pub fn calculate_dtor(
 357         self,
 358         adt_did: DefId,
 359         validate: impl Fn(Self, DefId) -> Result<(), ErrorGuaranteed>,
 360     ) -> Option<ty::Destructor> {
 361         let drop_trait = self.lang_items().drop_trait()?;
 362         self.ensure().coherent_trait(drop_trait);
 363
 364         let ty = self.type_of(adt_did);
 365         let (did, constness) = self.find_map_relevant_impl(drop_trait, ty, |impl_did| {
 366             if let Some(item_id) = self.associated_item_def_ids(impl_did).first() {
 367                 if validate(self, impl_did).is_ok() {
 368                     return Some((*item_id, self.constness(impl_did)));
 369                 }
 370             }
 371             None
 372         })?;
 373
 374         Some(ty::Destructor { did, constness })
 375     }
 376
 377     /// Returns the set of types that are required to be alive in
 378     /// order to run the destructor of `def` (see RFCs 769 and
 379     /// 1238).
 380     ///
 381     /// Note that this returns only the constraints for the
 382     /// destructor of `def` itself. For the destructors of the
 383     /// contents, you need `adt_dtorck_constraint`.
 384     pub fn destructor_constraints(self, def: ty::AdtDef<'tcx>) -> Vec<ty::subst::GenericArg<'tcx>> {
 385         let dtor = match def.destructor(self) {
 386             None => {
 387                 debug!("destructor_constraints({:?}) - no dtor", def.did());
 388                 return vec![];
 389             }
 390             Some(dtor) => dtor.did,
 391         };
 392
 393         let impl_def_id = self.parent(dtor);
 394         let impl_generics = self.generics_of(impl_def_id);
 395
 396         // We have a destructor - all the parameters that are not
 397         // pure_wrt_drop (i.e, don't have a #[may_dangle] attribute)
 398         // must be live.
 399
 400         // We need to return the list of parameters from the ADTs
 401         // generics/substs that correspond to impure parameters on the
 402         // impl's generics. This is a bit ugly, but conceptually simple:
 403         //
 404         // Suppose our ADT looks like the following
 405         //
 406         //     struct S<X, Y, Z>(X, Y, Z);
 407         //
 408         // and the impl is
 409         //
 410         //     impl<#[may_dangle] P0, P1, P2> Drop for S<P1, P2, P0>
 411         //
 412         // We want to return the parameters (X, Y). For that, we match
 413         // up the item-substs <X, Y, Z> with the substs on the impl ADT,
 414         // <P1, P2, P0>, and then look up which of the impl substs refer to
 415         // parameters marked as pure.
 416
 417         let impl_substs = match *self.type_of(impl_def_id).kind() {
 418             ty::Adt(def_, substs) if def_ == def => substs,
 419             _ => bug!(),
 420         };
 421
 422         let item_substs = match *self.type_of(def.did()).kind() {
 423             ty::Adt(def_, substs) if def_ == def => substs,
 424             _ => bug!(),
 425         };
 426
 427         let result = iter::zip(item_substs, impl_substs)
 428             .filter(|&(_, k)| {
 429                 match k.unpack() {
 430                     GenericArgKind::Lifetime(region) => match region.kind() {
 431                         ty::ReEarlyBound(ref ebr) => {
 432                             !impl_generics.region_param(ebr, self).pure_wrt_drop
 433                         }
 434                         // Error: not a region param
 435                         _ => false,
 436                     },
 437                     GenericArgKind::Type(ty) => match ty.kind() {
 438                         ty::Param(ref pt) => !impl_generics.type_param(pt, self).pure_wrt_drop,
 439                         // Error: not a type param
 440                         _ => false,
 441                     },
 442                     GenericArgKind::Const(ct) => match ct.kind() {
 443                         ty::ConstKind::Param(ref pc) => {
 444                             !impl_generics.const_param(pc, self).pure_wrt_drop
 445                         }
 446                         // Error: not a const param
 447                         _ => false,
 448                     },
 449                 }
 450             })
 451             .map(|(item_param, _)| item_param)
 452             .collect();
 453         debug!("destructor_constraint({:?}) = {:?}", def.did(), result);
 454         result
 455     }
 456
 457     /// Checks whether each generic argument is simply a unique generic parameter.
 458     pub fn uses_unique_generic_params(
 459         self,
 460         substs: SubstsRef<'tcx>,
 461         ignore_regions: IgnoreRegions,
 462     ) -> Result<(), NotUniqueParam<'tcx>> {
 463         let mut seen = GrowableBitSet::default();
 464         for arg in substs {
 465             match arg.unpack() {
 466                 GenericArgKind::Lifetime(lt) => {
 467                     if ignore_regions == IgnoreRegions::No {
 468                         let ty::ReEarlyBound(p) = lt.kind() else {
 469                             return Err(NotUniqueParam::NotParam(lt.into()))
 470                         };
 471                         if !seen.insert(p.index) {
 472                             return Err(NotUniqueParam::DuplicateParam(lt.into()));
 473                         }
 474                     }
 475                 }
 476                 GenericArgKind::Type(t) => match t.kind() {
 477                     ty::Param(p) => {
 478                         if !seen.insert(p.index) {
 479                             return Err(NotUniqueParam::DuplicateParam(t.into()));
 480                         }
 481                     }
 482                     _ => return Err(NotUniqueParam::NotParam(t.into())),
 483                 },
 484                 GenericArgKind::Const(c) => match c.kind() {
 485                     ty::ConstKind::Param(p) => {
 486                         if !seen.insert(p.index) {
 487                             return Err(NotUniqueParam::DuplicateParam(c.into()));
 488                         }
 489                     }
 490                     _ => return Err(NotUniqueParam::NotParam(c.into())),
 491                 },
 492             }
 493         }
 494
 495         Ok(())
 496     }
 497
 498     /// Returns `true` if `def_id` refers to a closure (e.g., `|x| x * 2`). Note
 499     /// that closures have a `DefId`, but the closure *expression* also
 500     /// has a `HirId` that is located within the context where the
 501     /// closure appears (and, sadly, a corresponding `NodeId`, since
 502     /// those are not yet phased out). The parent of the closure's
 503     /// `DefId` will also be the context where it appears.
 504     pub fn is_closure(self, def_id: DefId) -> bool {
 505         matches!(self.def_kind(def_id), DefKind::Closure | DefKind::Generator)
 506     }
 507
 508     /// Returns `true` if `def_id` refers to a definition that does not have its own
 509     /// type-checking context, i.e. closure, generator or inline const.
 510     pub fn is_typeck_child(self, def_id: DefId) -> bool {
 511         matches!(
 512             self.def_kind(def_id),
 513             DefKind::Closure | DefKind::Generator | DefKind::InlineConst
 514         )
 515     }
 516
 517     /// Returns `true` if `def_id` refers to a trait (i.e., `trait Foo { ... }`).
 518     pub fn is_trait(self, def_id: DefId) -> bool {
 519         self.def_kind(def_id) == DefKind::Trait
 520     }
 521
 522     /// Returns `true` if `def_id` refers to a trait alias (i.e., `trait Foo = ...;`),
 523     /// and `false` otherwise.
 524     pub fn is_trait_alias(self, def_id: DefId) -> bool {
 525         self.def_kind(def_id) == DefKind::TraitAlias
 526     }
 527
 528     /// Returns `true` if this `DefId` refers to the implicit constructor for
 529     /// a tuple struct like `struct Foo(u32)`, and `false` otherwise.
 530     pub fn is_constructor(self, def_id: DefId) -> bool {
 531         matches!(self.def_kind(def_id), DefKind::Ctor(..))
 532     }
 533
 534     /// Given the `DefId`, returns the `DefId` of the innermost item that
 535     /// has its own type-checking context or "inference environment".
 536     ///
 537     /// For example, a closure has its own `DefId`, but it is type-checked
 538     /// with the containing item. Similarly, an inline const block has its
 539     /// own `DefId` but it is type-checked together with the containing item.
 540     ///
 541     /// Therefore, when we fetch the
 542     /// `typeck` the closure, for example, we really wind up
 543     /// fetching the `typeck` the enclosing fn item.
 544     pub fn typeck_root_def_id(self, def_id: DefId) -> DefId {
 545         let mut def_id = def_id;
 546         while self.is_typeck_child(def_id) {
 547             def_id = self.parent(def_id);
 548         }
 549         def_id
 550     }
 551
 552     /// Given the `DefId` and substs a closure, creates the type of
 553     /// `self` argument that the closure expects. For example, for a
 554     /// `Fn` closure, this would return a reference type `&T` where
 555     /// `T = closure_ty`.
 556     ///
 557     /// Returns `None` if this closure's kind has not yet been inferred.
 558     /// This should only be possible during type checking.
 559     ///
 560     /// Note that the return value is a late-bound region and hence
 561     /// wrapped in a binder.
 562     pub fn closure_env_ty(
 563         self,
 564         closure_def_id: DefId,
 565         closure_substs: SubstsRef<'tcx>,
 566         env_region: ty::RegionKind<'tcx>,
 567     ) -> Option<Ty<'tcx>> {
 568         let closure_ty = self.mk_closure(closure_def_id, closure_substs);
 569         let closure_kind_ty = closure_substs.as_closure().kind_ty();
 570         let closure_kind = closure_kind_ty.to_opt_closure_kind()?;
 571         let env_ty = match closure_kind {
 572             ty::ClosureKind::Fn => self.mk_imm_ref(self.mk_region(env_region), closure_ty),
 573             ty::ClosureKind::FnMut => self.mk_mut_ref(self.mk_region(env_region), closure_ty),
 574             ty::ClosureKind::FnOnce => closure_ty,
 575         };
 576         Some(env_ty)
 577     }
 578
 579     /// Returns `true` if the node pointed to by `def_id` is a `static` item.
 580     #[inline]
 581     pub fn is_static(self, def_id: DefId) -> bool {
 582         matches!(self.def_kind(def_id), DefKind::Static(_))
 583     }
 584
 585     #[inline]
 586     pub fn static_mutability(self, def_id: DefId) -> Option<hir::Mutability> {
 587         if let DefKind::Static(mt) = self.def_kind(def_id) { Some(mt) } else { None }
 588     }
 589
 590     /// Returns `true` if this is a `static` item with the `#[thread_local]` attribute.
 591     pub fn is_thread_local_static(self, def_id: DefId) -> bool {
 592         self.codegen_fn_attrs(def_id).flags.contains(CodegenFnAttrFlags::THREAD_LOCAL)
 593     }
 594
 595     /// Returns `true` if the node pointed to by `def_id` is a mutable `static` item.
 596     #[inline]
 597     pub fn is_mutable_static(self, def_id: DefId) -> bool {
 598         self.static_mutability(def_id) == Some(hir::Mutability::Mut)
 599     }
 600
 601     /// Get the type of the pointer to the static that we use in MIR.
 602     pub fn static_ptr_ty(self, def_id: DefId) -> Ty<'tcx> {
 603         // Make sure that any constants in the static's type are evaluated.
 604         let static_ty = self.normalize_erasing_regions(ty::ParamEnv::empty(), self.type_of(def_id));
 605
 606         // Make sure that accesses to unsafe statics end up using raw pointers.
 607         // For thread-locals, this needs to be kept in sync with `Rvalue::ty`.
 608         if self.is_mutable_static(def_id) {
 609             self.mk_mut_ptr(static_ty)
 610         } else if self.is_foreign_item(def_id) {
 611             self.mk_imm_ptr(static_ty)
 612         } else {
 613             self.mk_imm_ref(self.lifetimes.re_erased, static_ty)
 614         }
 615     }
 616
 617     /// Expands the given impl trait type, stopping if the type is recursive.
 618     #[instrument(skip(self), level = "debug", ret)]
 619     pub fn try_expand_impl_trait_type(
 620         self,
 621         def_id: DefId,
 622         substs: SubstsRef<'tcx>,
 623     ) -> Result<Ty<'tcx>, Ty<'tcx>> {
 624         let mut visitor = OpaqueTypeExpander {
 625             seen_opaque_tys: FxHashSet::default(),
 626             expanded_cache: FxHashMap::default(),
 627             primary_def_id: Some(def_id),
 628             found_recursion: false,
 629             found_any_recursion: false,
 630             check_recursion: true,
 631             tcx: self,
 632         };
 633
 634         let expanded_type = visitor.expand_opaque_ty(def_id, substs).unwrap();
 635         if visitor.found_recursion { Err(expanded_type) } else { Ok(expanded_type) }
 636     }
 637
 638     pub fn bound_type_of(self, def_id: DefId) -> ty::EarlyBinder<Ty<'tcx>> {
 639         ty::EarlyBinder(self.type_of(def_id))
 640     }
 641
 642     pub fn bound_trait_impl_trait_tys(
 643         self,
 644         def_id: DefId,
 645     ) -> ty::EarlyBinder<Result<&'tcx FxHashMap<DefId, Ty<'tcx>>, ErrorGuaranteed>> {
 646         ty::EarlyBinder(self.collect_trait_impl_trait_tys(def_id))
 647     }
 648
 649     pub fn bound_fn_sig(self, def_id: DefId) -> ty::EarlyBinder<ty::PolyFnSig<'tcx>> {
 650         ty::EarlyBinder(self.fn_sig(def_id))
 651     }
 652
 653     pub fn bound_impl_trait_ref(
 654         self,
 655         def_id: DefId,
 656     ) -> Option<ty::EarlyBinder<ty::TraitRef<'tcx>>> {
 657         self.impl_trait_ref(def_id).map(|i| ty::EarlyBinder(i))
 658     }
 659
 660     pub fn bound_explicit_item_bounds(
 661         self,
 662         def_id: DefId,
 663     ) -> ty::EarlyBinder<&'tcx [(ty::Predicate<'tcx>, rustc_span::Span)]> {
 664         ty::EarlyBinder(self.explicit_item_bounds(def_id))
 665     }
 666
 667     pub fn bound_item_bounds(
 668         self,
 669         def_id: DefId,
 670     ) -> ty::EarlyBinder<&'tcx ty::List<ty::Predicate<'tcx>>> {
 671         ty::EarlyBinder(self.item_bounds(def_id))
 672     }
 673
 674     pub fn bound_const_param_default(self, def_id: DefId) -> ty::EarlyBinder<ty::Const<'tcx>> {
 675         ty::EarlyBinder(self.const_param_default(def_id))
 676     }
 677
 678     pub fn bound_predicates_of(
 679         self,
 680         def_id: DefId,
 681     ) -> ty::EarlyBinder<ty::generics::GenericPredicates<'tcx>> {
 682         ty::EarlyBinder(self.predicates_of(def_id))
 683     }
 684
 685     pub fn bound_explicit_predicates_of(
 686         self,
 687         def_id: DefId,
 688     ) -> ty::EarlyBinder<ty::generics::GenericPredicates<'tcx>> {
 689         ty::EarlyBinder(self.explicit_predicates_of(def_id))
 690     }
 691
 692     pub fn bound_impl_subject(self, def_id: DefId) -> ty::EarlyBinder<ty::ImplSubject<'tcx>> {
 693         ty::EarlyBinder(self.impl_subject(def_id))
 694     }
 695 }
 696
 697 struct OpaqueTypeExpander<'tcx> {
 698     // Contains the DefIds of the opaque types that are currently being
 699     // expanded. When we expand an opaque type we insert the DefId of
 700     // that type, and when we finish expanding that type we remove the
 701     // its DefId.
 702     seen_opaque_tys: FxHashSet<DefId>,
 703     // Cache of all expansions we've seen so far. This is a critical
 704     // optimization for some large types produced by async fn trees.
 705     expanded_cache: FxHashMap<(DefId, SubstsRef<'tcx>), Ty<'tcx>>,
 706     primary_def_id: Option<DefId>,
 707     found_recursion: bool,
 708     found_any_recursion: bool,
 709     /// Whether or not to check for recursive opaque types.
 710     /// This is `true` when we're explicitly checking for opaque type
 711     /// recursion, and 'false' otherwise to avoid unnecessary work.
 712     check_recursion: bool,
 713     tcx: TyCtxt<'tcx>,
 714 }
 715
 716 impl<'tcx> OpaqueTypeExpander<'tcx> {
 717     fn expand_opaque_ty(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) -> Option<Ty<'tcx>> {
 718         if self.found_any_recursion {
 719             return None;
 720         }
 721         let substs = substs.fold_with(self);
 722         if !self.check_recursion || self.seen_opaque_tys.insert(def_id) {
 723             let expanded_ty = match self.expanded_cache.get(&(def_id, substs)) {
 724                 Some(expanded_ty) => *expanded_ty,
 725                 None => {
 726                     let generic_ty = self.tcx.bound_type_of(def_id);
 727                     let concrete_ty = generic_ty.subst(self.tcx, substs);
 728                     let expanded_ty = self.fold_ty(concrete_ty);
 729                     self.expanded_cache.insert((def_id, substs), expanded_ty);
 730                     expanded_ty
 731                 }
 732             };
 733             if self.check_recursion {
 734                 self.seen_opaque_tys.remove(&def_id);
 735             }
 736             Some(expanded_ty)
 737         } else {
 738             // If another opaque type that we contain is recursive, then it
 739             // will report the error, so we don't have to.
 740             self.found_any_recursion = true;
 741             self.found_recursion = def_id == *self.primary_def_id.as_ref().unwrap();
 742             None
 743         }
 744     }
 745 }
 746
 747 impl<'tcx> TypeFolder<'tcx> for OpaqueTypeExpander<'tcx> {
 748     fn tcx(&self) -> TyCtxt<'tcx> {
 749         self.tcx
 750     }
 751
 752     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 753         if let ty::Opaque(def_id, substs) = *t.kind() {
 754             self.expand_opaque_ty(def_id, substs).unwrap_or(t)
 755         } else if t.has_opaque_types() {
 756             t.super_fold_with(self)
 757         } else {
 758             t
 759         }
 760     }
 761 }
 762
 763 impl<'tcx> Ty<'tcx> {
 764     /// Returns the maximum value for the given numeric type (including `char`s)
 765     /// or returns `None` if the type is not numeric.
 766     pub fn numeric_max_val(self, tcx: TyCtxt<'tcx>) -> Option<ty::Const<'tcx>> {
 767         let val = match self.kind() {
 768             ty::Int(_) | ty::Uint(_) => {
 769                 let (size, signed) = int_size_and_signed(tcx, self);
 770                 let val =
 771                     if signed { size.signed_int_max() as u128 } else { size.unsigned_int_max() };
 772                 Some(val)
 773             }
 774             ty::Char => Some(std::char::MAX as u128),
 775             ty::Float(fty) => Some(match fty {
 776                 ty::FloatTy::F32 => rustc_apfloat::ieee::Single::INFINITY.to_bits(),
 777                 ty::FloatTy::F64 => rustc_apfloat::ieee::Double::INFINITY.to_bits(),
 778             }),
 779             _ => None,
 780         };
 781
 782         val.map(|v| ty::Const::from_bits(tcx, v, ty::ParamEnv::empty().and(self)))
 783     }
 784
 785     /// Returns the minimum value for the given numeric type (including `char`s)
 786     /// or returns `None` if the type is not numeric.
 787     pub fn numeric_min_val(self, tcx: TyCtxt<'tcx>) -> Option<ty::Const<'tcx>> {
 788         let val = match self.kind() {
 789             ty::Int(_) | ty::Uint(_) => {
 790                 let (size, signed) = int_size_and_signed(tcx, self);
 791                 let val = if signed { size.truncate(size.signed_int_min() as u128) } else { 0 };
 792                 Some(val)
 793             }
 794             ty::Char => Some(0),
 795             ty::Float(fty) => Some(match fty {
 796                 ty::FloatTy::F32 => (-::rustc_apfloat::ieee::Single::INFINITY).to_bits(),
 797                 ty::FloatTy::F64 => (-::rustc_apfloat::ieee::Double::INFINITY).to_bits(),
 798             }),
 799             _ => None,
 800         };
 801
 802         val.map(|v| ty::Const::from_bits(tcx, v, ty::ParamEnv::empty().and(self)))
 803     }
 804
 805     /// Checks whether values of this type `T` are *moved* or *copied*
 806     /// when referenced -- this amounts to a check for whether `T:
 807     /// Copy`, but note that we **don't** consider lifetimes when
 808     /// doing this check. This means that we may generate MIR which
 809     /// does copies even when the type actually doesn't satisfy the
 810     /// full requirements for the `Copy` trait (cc #29149) -- this
 811     /// winds up being reported as an error during NLL borrow check.
 812     pub fn is_copy_modulo_regions(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> bool {
 813         self.is_trivially_pure_clone_copy() || tcx.is_copy_raw(param_env.and(self))
 814     }
 815
 816     /// Checks whether values of this type `T` have a size known at
 817     /// compile time (i.e., whether `T: Sized`). Lifetimes are ignored
 818     /// for the purposes of this check, so it can be an
 819     /// over-approximation in generic contexts, where one can have
 820     /// strange rules like `<T as Foo<'static>>::Bar: Sized` that
 821     /// actually carry lifetime requirements.
 822     pub fn is_sized(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> bool {
 823         self.is_trivially_sized(tcx) || tcx.is_sized_raw(param_env.and(self))
 824     }
 825
 826     /// Checks whether values of this type `T` implement the `Freeze`
 827     /// trait -- frozen types are those that do not contain an
 828     /// `UnsafeCell` anywhere. This is a language concept used to
 829     /// distinguish "true immutability", which is relevant to
 830     /// optimization as well as the rules around static values. Note
 831     /// that the `Freeze` trait is not exposed to end users and is
 832     /// effectively an implementation detail.
 833     pub fn is_freeze(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> bool {
 834         self.is_trivially_freeze() || tcx.is_freeze_raw(param_env.and(self))
 835     }
 836
 837     /// Fast path helper for testing if a type is `Freeze`.
 838     ///
 839     /// Returning true means the type is known to be `Freeze`. Returning
 840     /// `false` means nothing -- could be `Freeze`, might not be.
 841     fn is_trivially_freeze(self) -> bool {
 842         match self.kind() {
 843             ty::Int(_)
 844             | ty::Uint(_)
 845             | ty::Float(_)
 846             | ty::Bool
 847             | ty::Char
 848             | ty::Str
 849             | ty::Never
 850             | ty::Ref(..)
 851             | ty::RawPtr(_)
 852             | ty::FnDef(..)
 853             | ty::Error(_)
 854             | ty::FnPtr(_) => true,
 855             ty::Tuple(fields) => fields.iter().all(Self::is_trivially_freeze),
 856             ty::Slice(elem_ty) | ty::Array(elem_ty, _) => elem_ty.is_trivially_freeze(),
 857             ty::Adt(..)
 858             | ty::Bound(..)
 859             | ty::Closure(..)
 860             | ty::Dynamic(..)
 861             | ty::Foreign(_)
 862             | ty::Generator(..)
 863             | ty::GeneratorWitness(_)
 864             | ty::Infer(_)
 865             | ty::Opaque(..)
 866             | ty::Param(_)
 867             | ty::Placeholder(_)
 868             | ty::Projection(_) => false,
 869         }
 870     }
 871
 872     /// Checks whether values of this type `T` implement the `Unpin` trait.
 873     pub fn is_unpin(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> bool {
 874         self.is_trivially_unpin() || tcx.is_unpin_raw(param_env.and(self))
 875     }
 876
 877     /// Fast path helper for testing if a type is `Unpin`.
 878     ///
 879     /// Returning true means the type is known to be `Unpin`. Returning
 880     /// `false` means nothing -- could be `Unpin`, might not be.
 881     fn is_trivially_unpin(self) -> bool {
 882         match self.kind() {
 883             ty::Int(_)
 884             | ty::Uint(_)
 885             | ty::Float(_)
 886             | ty::Bool
 887             | ty::Char
 888             | ty::Str
 889             | ty::Never
 890             | ty::Ref(..)
 891             | ty::RawPtr(_)
 892             | ty::FnDef(..)
 893             | ty::Error(_)
 894             | ty::FnPtr(_) => true,
 895             ty::Tuple(fields) => fields.iter().all(Self::is_trivially_unpin),
 896             ty::Slice(elem_ty) | ty::Array(elem_ty, _) => elem_ty.is_trivially_unpin(),
 897             ty::Adt(..)
 898             | ty::Bound(..)
 899             | ty::Closure(..)
 900             | ty::Dynamic(..)
 901             | ty::Foreign(_)
 902             | ty::Generator(..)
 903             | ty::GeneratorWitness(_)
 904             | ty::Infer(_)
 905             | ty::Opaque(..)
 906             | ty::Param(_)
 907             | ty::Placeholder(_)
 908             | ty::Projection(_) => false,
 909         }
 910     }
 911
 912     /// If `ty.needs_drop(...)` returns `true`, then `ty` is definitely
 913     /// non-copy and *might* have a destructor attached; if it returns
 914     /// `false`, then `ty` definitely has no destructor (i.e., no drop glue).
 915     ///
 916     /// (Note that this implies that if `ty` has a destructor attached,
 917     /// then `needs_drop` will definitely return `true` for `ty`.)
 918     ///
 919     /// Note that this method is used to check eligible types in unions.
 920     #[inline]
 921     pub fn needs_drop(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> bool {
 922         // Avoid querying in simple cases.
 923         match needs_drop_components(self, &tcx.data_layout) {
 924             Err(AlwaysRequiresDrop) => true,
 925             Ok(components) => {
 926                 let query_ty = match *components {
 927                     [] => return false,
 928                     // If we've got a single component, call the query with that
 929                     // to increase the chance that we hit the query cache.
 930                     [component_ty] => component_ty,
 931                     _ => self,
 932                 };
 933
 934                 // This doesn't depend on regions, so try to minimize distinct
 935                 // query keys used.
 936                 // If normalization fails, we just use `query_ty`.
 937                 let query_ty =
 938                     tcx.try_normalize_erasing_regions(param_env, query_ty).unwrap_or(query_ty);
 939
 940                 tcx.needs_drop_raw(param_env.and(query_ty))
 941             }
 942         }
 943     }
 944
 945     /// Checks if `ty` has a significant drop.
 946     ///
 947     /// Note that this method can return false even if `ty` has a destructor
 948     /// attached; even if that is the case then the adt has been marked with
 949     /// the attribute `rustc_insignificant_dtor`.
 950     ///
 951     /// Note that this method is used to check for change in drop order for
 952     /// 2229 drop reorder migration analysis.
 953     #[inline]
 954     pub fn has_significant_drop(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> bool {
 955         // Avoid querying in simple cases.
 956         match needs_drop_components(self, &tcx.data_layout) {
 957             Err(AlwaysRequiresDrop) => true,
 958             Ok(components) => {
 959                 let query_ty = match *components {
 960                     [] => return false,
 961                     // If we've got a single component, call the query with that
 962                     // to increase the chance that we hit the query cache.
 963                     [component_ty] => component_ty,
 964                     _ => self,
 965                 };
 966
 967                 // FIXME(#86868): We should be canonicalizing, or else moving this to a method of inference
 968                 // context, or *something* like that, but for now just avoid passing inference
 969                 // variables to queries that can't cope with them. Instead, conservatively
 970                 // return "true" (may change drop order).
 971                 if query_ty.needs_infer() {
 972                     return true;
 973                 }
 974
 975                 // This doesn't depend on regions, so try to minimize distinct
 976                 // query keys used.
 977                 let erased = tcx.normalize_erasing_regions(param_env, query_ty);
 978                 tcx.has_significant_drop_raw(param_env.and(erased))
 979             }
 980         }
 981     }
 982
 983     /// Returns `true` if equality for this type is both reflexive and structural.
 984     ///
 985     /// Reflexive equality for a type is indicated by an `Eq` impl for that type.
 986     ///
 987     /// Primitive types (`u32`, `str`) have structural equality by definition. For composite data
 988     /// types, equality for the type as a whole is structural when it is the same as equality
 989     /// between all components (fields, array elements, etc.) of that type. For ADTs, structural
 990     /// equality is indicated by an implementation of `PartialStructuralEq` and `StructuralEq` for
 991     /// that type.
 992     ///
 993     /// This function is "shallow" because it may return `true` for a composite type whose fields
 994     /// are not `StructuralEq`. For example, `[T; 4]` has structural equality regardless of `T`
 995     /// because equality for arrays is determined by the equality of each array element. If you
 996     /// want to know whether a given call to `PartialEq::eq` will proceed structurally all the way
 997     /// down, you will need to use a type visitor.
 998     #[inline]
 999     pub fn is_structural_eq_shallow(self, tcx: TyCtxt<'tcx>) -> bool {
1000         match self.kind() {
1001             // Look for an impl of both `PartialStructuralEq` and `StructuralEq`.
1002             ty::Adt(..) => tcx.has_structural_eq_impls(self),
1003
1004             // Primitive types that satisfy `Eq`.
1005             ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Str | ty::Never => true,
1006
1007             // Composite types that satisfy `Eq` when all of their fields do.
1008             //
1009             // Because this function is "shallow", we return `true` for these composites regardless
1010             // of the type(s) contained within.
1011             ty::Ref(..) | ty::Array(..) | ty::Slice(_) | ty::Tuple(..) => true,
1012
1013             // Raw pointers use bitwise comparison.
1014             ty::RawPtr(_) | ty::FnPtr(_) => true,
1015
1016             // Floating point numbers are not `Eq`.
1017             ty::Float(_) => false,
1018
1019             // Conservatively return `false` for all others...
1020
1021             // Anonymous function types
1022             ty::FnDef(..) | ty::Closure(..) | ty::Dynamic(..) | ty::Generator(..) => false,
1023
1024             // Generic or inferred types
1025             //
1026             // FIXME(ecstaticmorse): Maybe we should `bug` here? This should probably only be
1027             // called for known, fully-monomorphized types.
1028             ty::Projection(_)
1029             | ty::Opaque(..)
1030             | ty::Param(_)
1031             | ty::Bound(..)
1032             | ty::Placeholder(_)
1033             | ty::Infer(_) => false,
1034
1035             ty::Foreign(_) | ty::GeneratorWitness(..) | ty::Error(_) => false,
1036         }
1037     }
1038
1039     /// Peel off all reference types in this type until there are none left.
1040     ///
1041     /// This method is idempotent, i.e. `ty.peel_refs().peel_refs() == ty.peel_refs()`.
1042     ///
1043     /// # Examples
1044     ///
1045     /// - `u8` -> `u8`
1046     /// - `&'a mut u8` -> `u8`
1047     /// - `&'a &'b u8` -> `u8`
1048     /// - `&'a *const &'b u8 -> *const &'b u8`
1049     pub fn peel_refs(self) -> Ty<'tcx> {
1050         let mut ty = self;
1051         while let ty::Ref(_, inner_ty, _) = ty.kind() {
1052             ty = *inner_ty;
1053         }
1054         ty
1055     }
1056
1057     #[inline]
1058     pub fn outer_exclusive_binder(self) -> ty::DebruijnIndex {
1059         self.0.outer_exclusive_binder
1060     }
1061 }
1062
1063 pub enum ExplicitSelf<'tcx> {
1064     ByValue,
1065     ByReference(ty::Region<'tcx>, hir::Mutability),
1066     ByRawPointer(hir::Mutability),
1067     ByBox,
1068     Other,
1069 }
1070
1071 impl<'tcx> ExplicitSelf<'tcx> {
1072     /// Categorizes an explicit self declaration like `self: SomeType`
1073     /// into either `self`, `&self`, `&mut self`, `Box<self>`, or
1074     /// `Other`.
1075     /// This is mainly used to require the arbitrary_self_types feature
1076     /// in the case of `Other`, to improve error messages in the common cases,
1077     /// and to make `Other` non-object-safe.
1078     ///
1079     /// Examples:
1080     ///
1081     /// ```ignore (illustrative)
1082     /// impl<'a> Foo for &'a T {
1083     ///     // Legal declarations:
1084     ///     fn method1(self: &&'a T); // ExplicitSelf::ByReference
1085     ///     fn method2(self: &'a T); // ExplicitSelf::ByValue
1086     ///     fn method3(self: Box<&'a T>); // ExplicitSelf::ByBox
1087     ///     fn method4(self: Rc<&'a T>); // ExplicitSelf::Other
1088     ///
1089     ///     // Invalid cases will be caught by `check_method_receiver`:
1090     ///     fn method_err1(self: &'a mut T); // ExplicitSelf::Other
1091     ///     fn method_err2(self: &'static T) // ExplicitSelf::ByValue
1092     ///     fn method_err3(self: &&T) // ExplicitSelf::ByReference
1093     /// }
1094     /// ```
1095     ///
1096     pub fn determine<P>(self_arg_ty: Ty<'tcx>, is_self_ty: P) -> ExplicitSelf<'tcx>
1097     where
1098         P: Fn(Ty<'tcx>) -> bool,
1099     {
1100         use self::ExplicitSelf::*;
1101
1102         match *self_arg_ty.kind() {
1103             _ if is_self_ty(self_arg_ty) => ByValue,
1104             ty::Ref(region, ty, mutbl) if is_self_ty(ty) => ByReference(region, mutbl),
1105             ty::RawPtr(ty::TypeAndMut { ty, mutbl }) if is_self_ty(ty) => ByRawPointer(mutbl),
1106             ty::Adt(def, _) if def.is_box() && is_self_ty(self_arg_ty.boxed_ty()) => ByBox,
1107             _ => Other,
1108         }
1109     }
1110 }
1111
1112 /// Returns a list of types such that the given type needs drop if and only if
1113 /// *any* of the returned types need drop. Returns `Err(AlwaysRequiresDrop)` if
1114 /// this type always needs drop.
1115 pub fn needs_drop_components<'tcx>(
1116     ty: Ty<'tcx>,
1117     target_layout: &TargetDataLayout,
1118 ) -> Result<SmallVec<[Ty<'tcx>; 2]>, AlwaysRequiresDrop> {
1119     match ty.kind() {
1120         ty::Infer(ty::FreshIntTy(_))
1121         | ty::Infer(ty::FreshFloatTy(_))
1122         | ty::Bool
1123         | ty::Int(_)
1124         | ty::Uint(_)
1125         | ty::Float(_)
1126         | ty::Never
1127         | ty::FnDef(..)
1128         | ty::FnPtr(_)
1129         | ty::Char
1130         | ty::GeneratorWitness(..)
1131         | ty::RawPtr(_)
1132         | ty::Ref(..)
1133         | ty::Str => Ok(SmallVec::new()),
1134
1135         // Foreign types can never have destructors.
1136         ty::Foreign(..) => Ok(SmallVec::new()),
1137
1138         ty::Dynamic(..) | ty::Error(_) => Err(AlwaysRequiresDrop),
1139
1140         ty::Slice(ty) => needs_drop_components(*ty, target_layout),
1141         ty::Array(elem_ty, size) => {
1142             match needs_drop_components(*elem_ty, target_layout) {
1143                 Ok(v) if v.is_empty() => Ok(v),
1144                 res => match size.kind().try_to_bits(target_layout.pointer_size) {
1145                     // Arrays of size zero don't need drop, even if their element
1146                     // type does.
1147                     Some(0) => Ok(SmallVec::new()),
1148                     Some(_) => res,
1149                     // We don't know which of the cases above we are in, so
1150                     // return the whole type and let the caller decide what to
1151                     // do.
1152                     None => Ok(smallvec![ty]),
1153                 },
1154             }
1155         }
1156         // If any field needs drop, then the whole tuple does.
1157         ty::Tuple(fields) => fields.iter().try_fold(SmallVec::new(), move |mut acc, elem| {
1158             acc.extend(needs_drop_components(elem, target_layout)?);
1159             Ok(acc)
1160         }),
1161
1162         // These require checking for `Copy` bounds or `Adt` destructors.
1163         ty::Adt(..)
1164         | ty::Projection(..)
1165         | ty::Param(_)
1166         | ty::Bound(..)
1167         | ty::Placeholder(..)
1168         | ty::Opaque(..)
1169         | ty::Infer(_)
1170         | ty::Closure(..)
1171         | ty::Generator(..) => Ok(smallvec![ty]),
1172     }
1173 }
1174
1175 pub fn is_trivially_const_drop<'tcx>(ty: Ty<'tcx>) -> bool {
1176     match *ty.kind() {
1177         ty::Bool
1178         | ty::Char
1179         | ty::Int(_)
1180         | ty::Uint(_)
1181         | ty::Float(_)
1182         | ty::Infer(ty::IntVar(_))
1183         | ty::Infer(ty::FloatVar(_))
1184         | ty::Str
1185         | ty::RawPtr(_)
1186         | ty::Ref(..)
1187         | ty::FnDef(..)
1188         | ty::FnPtr(_)
1189         | ty::Never
1190         | ty::Foreign(_) => true,
1191
1192         ty::Opaque(..)
1193         | ty::Dynamic(..)
1194         | ty::Error(_)
1195         | ty::Bound(..)
1196         | ty::Param(_)
1197         | ty::Placeholder(_)
1198         | ty::Projection(_)
1199         | ty::Infer(_) => false,
1200
1201         // Not trivial because they have components, and instead of looking inside,
1202         // we'll just perform trait selection.
1203         ty::Closure(..) | ty::Generator(..) | ty::GeneratorWitness(_) | ty::Adt(..) => false,
1204
1205         ty::Array(ty, _) | ty::Slice(ty) => is_trivially_const_drop(ty),
1206
1207         ty::Tuple(tys) => tys.iter().all(|ty| is_trivially_const_drop(ty)),
1208     }
1209 }
1210
1211 /// Does the equivalent of
1212 /// ```ignore (ilustrative)
1213 /// let v = self.iter().map(|p| p.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
1214 /// folder.tcx().intern_*(&v)
1215 /// ```
1216 pub fn fold_list<'tcx, F, T>(
1217     list: &'tcx ty::List<T>,
1218     folder: &mut F,
1219     intern: impl FnOnce(TyCtxt<'tcx>, &[T]) -> &'tcx ty::List<T>,
1220 ) -> Result<&'tcx ty::List<T>, F::Error>
1221 where
1222     F: FallibleTypeFolder<'tcx>,
1223     T: TypeFoldable<'tcx> + PartialEq + Copy,
1224 {
1225     let mut iter = list.iter();
1226     // Look for the first element that changed
1227     match iter.by_ref().enumerate().find_map(|(i, t)| match t.try_fold_with(folder) {
1228         Ok(new_t) if new_t == t => None,
1229         new_t => Some((i, new_t)),
1230     }) {
1231         Some((i, Ok(new_t))) => {
1232             // An element changed, prepare to intern the resulting list
1233             let mut new_list = SmallVec::<[_; 8]>::with_capacity(list.len());
1234             new_list.extend_from_slice(&list[..i]);
1235             new_list.push(new_t);
1236             for t in iter {
1237                 new_list.push(t.try_fold_with(folder)?)
1238             }
1239             Ok(intern(folder.tcx(), &new_list))
1240         }
1241         Some((_, Err(err))) => {
1242             return Err(err);
1243         }
1244         None => Ok(list),
1245     }
1246 }
1247
1248 #[derive(Copy, Clone, Debug, HashStable, TyEncodable, TyDecodable)]
1249 pub struct AlwaysRequiresDrop;
1250
1251 /// Reveals all opaque types in the given value, replacing them
1252 /// with their underlying types.
1253 pub fn reveal_opaque_types_in_bounds<'tcx>(
1254     tcx: TyCtxt<'tcx>,
1255     val: &'tcx ty::List<ty::Predicate<'tcx>>,
1256 ) -> &'tcx ty::List<ty::Predicate<'tcx>> {
1257     let mut visitor = OpaqueTypeExpander {
1258         seen_opaque_tys: FxHashSet::default(),
1259         expanded_cache: FxHashMap::default(),
1260         primary_def_id: None,
1261         found_recursion: false,
1262         found_any_recursion: false,
1263         check_recursion: false,
1264         tcx,
1265     };
1266     val.fold_with(&mut visitor)
1267 }
1268
1269 /// Determines whether an item is annotated with `doc(hidden)`.
1270 pub fn is_doc_hidden(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
1271     tcx.get_attrs(def_id, sym::doc)
1272         .filter_map(|attr| attr.meta_item_list())
1273         .any(|items| items.iter().any(|item| item.has_name(sym::hidden)))
1274 }
1275
1276 /// Determines whether an item is annotated with `doc(notable_trait)`.
1277 pub fn is_doc_notable_trait(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
1278     tcx.get_attrs(def_id, sym::doc)
1279         .filter_map(|attr| attr.meta_item_list())
1280         .any(|items| items.iter().any(|item| item.has_name(sym::notable_trait)))
1281 }
1282
1283 /// Determines whether an item is an intrinsic by Abi.
1284 pub fn is_intrinsic(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
1285     matches!(tcx.fn_sig(def_id).abi(), Abi::RustIntrinsic | Abi::PlatformIntrinsic)
1286 }
1287
1288 pub fn provide(providers: &mut ty::query::Providers) {
1289     *providers = ty::query::Providers {
1290         reveal_opaque_types_in_bounds,
1291         is_doc_hidden,
1292         is_doc_notable_trait,
1293         is_intrinsic,
1294         ..*providers
1295     }
1296 }