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