compiler/rustc_middle/src/ty/adt.rs

   1 use crate::mir::interpret::ErrorHandled;
   2 use crate::ty;
   3 use crate::ty::util::{Discr, IntTypeExt};
   4 use rustc_data_structures::captures::Captures;
   5 use rustc_data_structures::fingerprint::Fingerprint;
   6 use rustc_data_structures::fx::FxHashMap;
   7 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
   8 use rustc_errors::ErrorReported;
   9 use rustc_hir as hir;
  10 use rustc_hir::def::{CtorKind, DefKind, Res};
  11 use rustc_hir::def_id::DefId;
  12 use rustc_index::vec::{Idx, IndexVec};
  13 use rustc_query_system::ich::StableHashingContext;
  14 use rustc_serialize::{self, Encodable, Encoder};
  15 use rustc_session::DataTypeKind;
  16 use rustc_span::symbol::sym;
  17 use rustc_target::abi::VariantIdx;
  18
  19 use std::cell::RefCell;
  20 use std::cmp::Ordering;
  21 use std::hash::{Hash, Hasher};
  22 use std::ops::Range;
  23 use std::{ptr, str};
  24
  25 use super::{
  26     Destructor, FieldDef, GenericPredicates, ReprOptions, Ty, TyCtxt, VariantDef, VariantDiscr,
  27 };
  28
  29 #[derive(Clone, HashStable, Debug)]
  30 pub struct AdtSizedConstraint<'tcx>(pub &'tcx [Ty<'tcx>]);
  31
  32 bitflags! {
  33     #[derive(HashStable)]
  34     pub struct AdtFlags: u32 {
  35         const NO_ADT_FLAGS        = 0;
  36         /// Indicates whether the ADT is an enum.
  37         const IS_ENUM             = 1 << 0;
  38         /// Indicates whether the ADT is a union.
  39         const IS_UNION            = 1 << 1;
  40         /// Indicates whether the ADT is a struct.
  41         const IS_STRUCT           = 1 << 2;
  42         /// Indicates whether the ADT is a struct and has a constructor.
  43         const HAS_CTOR            = 1 << 3;
  44         /// Indicates whether the type is `PhantomData`.
  45         const IS_PHANTOM_DATA     = 1 << 4;
  46         /// Indicates whether the type has a `#[fundamental]` attribute.
  47         const IS_FUNDAMENTAL      = 1 << 5;
  48         /// Indicates whether the type is `Box`.
  49         const IS_BOX              = 1 << 6;
  50         /// Indicates whether the type is `ManuallyDrop`.
  51         const IS_MANUALLY_DROP    = 1 << 7;
  52         /// Indicates whether the variant list of this ADT is `#[non_exhaustive]`.
  53         /// (i.e., this flag is never set unless this ADT is an enum).
  54         const IS_VARIANT_LIST_NON_EXHAUSTIVE = 1 << 8;
  55     }
  56 }
  57
  58 /// The definition of a user-defined type, e.g., a `struct`, `enum`, or `union`.
  59 ///
  60 /// These are all interned (by `alloc_adt_def`) into the global arena.
  61 ///
  62 /// The initialism *ADT* stands for an [*algebraic data type (ADT)*][adt].
  63 /// This is slightly wrong because `union`s are not ADTs.
  64 /// Moreover, Rust only allows recursive data types through indirection.
  65 ///
  66 /// [adt]: https://en.wikipedia.org/wiki/Algebraic_data_type
  67 ///
  68 /// # Recursive types
  69 ///
  70 /// It may seem impossible to represent recursive types using [`Ty`],
  71 /// since [`TyKind::Adt`] includes [`AdtDef`], which includes its fields,
  72 /// creating a cycle. However, `AdtDef` does not actually include the *types*
  73 /// of its fields; it includes just their [`DefId`]s.
  74 ///
  75 /// [`TyKind::Adt`]: ty::TyKind::Adt
  76 ///
  77 /// For example, the following type:
  78 ///
  79 /// ```
  80 /// struct S { x: Box<S> }
  81 /// ```
  82 ///
  83 /// is essentially represented with [`Ty`] as the following pseudocode:
  84 ///
  85 /// ```
  86 /// struct S { x }
  87 /// ```
  88 ///
  89 /// where `x` here represents the `DefId` of `S.x`. Then, the `DefId`
  90 /// can be used with [`TyCtxt::type_of()`] to get the type of the field.
  91 pub struct AdtDef {
  92     /// The `DefId` of the struct, enum or union item.
  93     pub did: DefId,
  94     /// Variants of the ADT. If this is a struct or union, then there will be a single variant.
  95     pub variants: IndexVec<VariantIdx, VariantDef>,
  96     /// Flags of the ADT (e.g., is this a struct? is this non-exhaustive?).
  97     flags: AdtFlags,
  98     /// Repr options provided by the user.
  99     pub repr: ReprOptions,
 100 }
 101
 102 impl PartialOrd for AdtDef {
 103     fn partial_cmp(&self, other: &AdtDef) -> Option<Ordering> {
 104         Some(self.cmp(&other))
 105     }
 106 }
 107
 108 /// There should be only one AdtDef for each `did`, therefore
 109 /// it is fine to implement `Ord` only based on `did`.
 110 impl Ord for AdtDef {
 111     fn cmp(&self, other: &AdtDef) -> Ordering {
 112         self.did.cmp(&other.did)
 113     }
 114 }
 115
 116 impl PartialEq for AdtDef {
 117     // `AdtDef`s are always interned, and this is part of `TyS` equality.
 118     #[inline]
 119     fn eq(&self, other: &Self) -> bool {
 120         ptr::eq(self, other)
 121     }
 122 }
 123
 124 impl Eq for AdtDef {}
 125
 126 impl Hash for AdtDef {
 127     #[inline]
 128     fn hash<H: Hasher>(&self, s: &mut H) {
 129         (self as *const AdtDef).hash(s)
 130     }
 131 }
 132
 133 impl<S: Encoder> Encodable<S> for AdtDef {
 134     fn encode(&self, s: &mut S) -> Result<(), S::Error> {
 135         self.did.encode(s)
 136     }
 137 }
 138
 139 impl<'a> HashStable<StableHashingContext<'a>> for AdtDef {
 140     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 141         thread_local! {
 142             static CACHE: RefCell<FxHashMap<usize, Fingerprint>> = Default::default();
 143         }
 144
 145         let hash: Fingerprint = CACHE.with(|cache| {
 146             let addr = self as *const AdtDef as usize;
 147             *cache.borrow_mut().entry(addr).or_insert_with(|| {
 148                 let ty::AdtDef { did, ref variants, ref flags, ref repr } = *self;
 149
 150                 let mut hasher = StableHasher::new();
 151                 did.hash_stable(hcx, &mut hasher);
 152                 variants.hash_stable(hcx, &mut hasher);
 153                 flags.hash_stable(hcx, &mut hasher);
 154                 repr.hash_stable(hcx, &mut hasher);
 155
 156                 hasher.finish()
 157             })
 158         });
 159
 160         hash.hash_stable(hcx, hasher);
 161     }
 162 }
 163
 164 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
 165 pub enum AdtKind {
 166     Struct,
 167     Union,
 168     Enum,
 169 }
 170
 171 impl Into<DataTypeKind> for AdtKind {
 172     fn into(self) -> DataTypeKind {
 173         match self {
 174             AdtKind::Struct => DataTypeKind::Struct,
 175             AdtKind::Union => DataTypeKind::Union,
 176             AdtKind::Enum => DataTypeKind::Enum,
 177         }
 178     }
 179 }
 180
 181 impl<'tcx> AdtDef {
 182     /// Creates a new `AdtDef`.
 183     pub(super) fn new(
 184         tcx: TyCtxt<'_>,
 185         did: DefId,
 186         kind: AdtKind,
 187         variants: IndexVec<VariantIdx, VariantDef>,
 188         repr: ReprOptions,
 189     ) -> Self {
 190         debug!("AdtDef::new({:?}, {:?}, {:?}, {:?})", did, kind, variants, repr);
 191         let mut flags = AdtFlags::NO_ADT_FLAGS;
 192
 193         if kind == AdtKind::Enum && tcx.has_attr(did, sym::non_exhaustive) {
 194             debug!("found non-exhaustive variant list for {:?}", did);
 195             flags = flags | AdtFlags::IS_VARIANT_LIST_NON_EXHAUSTIVE;
 196         }
 197
 198         flags |= match kind {
 199             AdtKind::Enum => AdtFlags::IS_ENUM,
 200             AdtKind::Union => AdtFlags::IS_UNION,
 201             AdtKind::Struct => AdtFlags::IS_STRUCT,
 202         };
 203
 204         if kind == AdtKind::Struct && variants[VariantIdx::new(0)].ctor_def_id.is_some() {
 205             flags |= AdtFlags::HAS_CTOR;
 206         }
 207
 208         let attrs = tcx.get_attrs(did);
 209         if tcx.sess.contains_name(&attrs, sym::fundamental) {
 210             flags |= AdtFlags::IS_FUNDAMENTAL;
 211         }
 212         if Some(did) == tcx.lang_items().phantom_data() {
 213             flags |= AdtFlags::IS_PHANTOM_DATA;
 214         }
 215         if Some(did) == tcx.lang_items().owned_box() {
 216             flags |= AdtFlags::IS_BOX;
 217         }
 218         if Some(did) == tcx.lang_items().manually_drop() {
 219             flags |= AdtFlags::IS_MANUALLY_DROP;
 220         }
 221
 222         AdtDef { did, variants, flags, repr }
 223     }
 224
 225     /// Returns `true` if this is a struct.
 226     #[inline]
 227     pub fn is_struct(&self) -> bool {
 228         self.flags.contains(AdtFlags::IS_STRUCT)
 229     }
 230
 231     /// Returns `true` if this is a union.
 232     #[inline]
 233     pub fn is_union(&self) -> bool {
 234         self.flags.contains(AdtFlags::IS_UNION)
 235     }
 236
 237     /// Returns `true` if this is an enum.
 238     #[inline]
 239     pub fn is_enum(&self) -> bool {
 240         self.flags.contains(AdtFlags::IS_ENUM)
 241     }
 242
 243     /// Returns `true` if the variant list of this ADT is `#[non_exhaustive]`.
 244     #[inline]
 245     pub fn is_variant_list_non_exhaustive(&self) -> bool {
 246         self.flags.contains(AdtFlags::IS_VARIANT_LIST_NON_EXHAUSTIVE)
 247     }
 248
 249     /// Returns the kind of the ADT.
 250     #[inline]
 251     pub fn adt_kind(&self) -> AdtKind {
 252         if self.is_enum() {
 253             AdtKind::Enum
 254         } else if self.is_union() {
 255             AdtKind::Union
 256         } else {
 257             AdtKind::Struct
 258         }
 259     }
 260
 261     /// Returns a description of this abstract data type.
 262     pub fn descr(&self) -> &'static str {
 263         match self.adt_kind() {
 264             AdtKind::Struct => "struct",
 265             AdtKind::Union => "union",
 266             AdtKind::Enum => "enum",
 267         }
 268     }
 269
 270     /// Returns a description of a variant of this abstract data type.
 271     #[inline]
 272     pub fn variant_descr(&self) -> &'static str {
 273         match self.adt_kind() {
 274             AdtKind::Struct => "struct",
 275             AdtKind::Union => "union",
 276             AdtKind::Enum => "variant",
 277         }
 278     }
 279
 280     /// If this function returns `true`, it implies that `is_struct` must return `true`.
 281     #[inline]
 282     pub fn has_ctor(&self) -> bool {
 283         self.flags.contains(AdtFlags::HAS_CTOR)
 284     }
 285
 286     /// Returns `true` if this type is `#[fundamental]` for the purposes
 287     /// of coherence checking.
 288     #[inline]
 289     pub fn is_fundamental(&self) -> bool {
 290         self.flags.contains(AdtFlags::IS_FUNDAMENTAL)
 291     }
 292
 293     /// Returns `true` if this is `PhantomData<T>`.
 294     #[inline]
 295     pub fn is_phantom_data(&self) -> bool {
 296         self.flags.contains(AdtFlags::IS_PHANTOM_DATA)
 297     }
 298
 299     /// Returns `true` if this is Box<T>.
 300     #[inline]
 301     pub fn is_box(&self) -> bool {
 302         self.flags.contains(AdtFlags::IS_BOX)
 303     }
 304
 305     /// Returns `true` if this is `ManuallyDrop<T>`.
 306     #[inline]
 307     pub fn is_manually_drop(&self) -> bool {
 308         self.flags.contains(AdtFlags::IS_MANUALLY_DROP)
 309     }
 310
 311     /// Returns `true` if this type has a destructor.
 312     pub fn has_dtor(&self, tcx: TyCtxt<'tcx>) -> bool {
 313         self.destructor(tcx).is_some()
 314     }
 315
 316     pub fn has_non_const_dtor(&self, tcx: TyCtxt<'tcx>) -> bool {
 317         matches!(self.destructor(tcx), Some(Destructor { constness: hir::Constness::NotConst, .. }))
 318     }
 319
 320     /// Asserts this is a struct or union and returns its unique variant.
 321     pub fn non_enum_variant(&self) -> &VariantDef {
 322         assert!(self.is_struct() || self.is_union());
 323         &self.variants[VariantIdx::new(0)]
 324     }
 325
 326     #[inline]
 327     pub fn predicates(&self, tcx: TyCtxt<'tcx>) -> GenericPredicates<'tcx> {
 328         tcx.predicates_of(self.did)
 329     }
 330
 331     /// Returns an iterator over all fields contained
 332     /// by this ADT.
 333     #[inline]
 334     pub fn all_fields(&self) -> impl Iterator<Item = &FieldDef> + Clone {
 335         self.variants.iter().flat_map(|v| v.fields.iter())
 336     }
 337
 338     /// Whether the ADT lacks fields. Note that this includes uninhabited enums,
 339     /// e.g., `enum Void {}` is considered payload free as well.
 340     pub fn is_payloadfree(&self) -> bool {
 341         // Treat the ADT as not payload-free if arbitrary_enum_discriminant is used (#88621).
 342         // This would disallow the following kind of enum from being casted into integer.
 343         // ```
 344         // enum Enum {
 345         //    Foo() = 1,
 346         //    Bar{} = 2,
 347         //    Baz = 3,
 348         // }
 349         // ```
 350         if self
 351             .variants
 352             .iter()
 353             .any(|v| matches!(v.discr, VariantDiscr::Explicit(_)) && v.ctor_kind != CtorKind::Const)
 354         {
 355             return false;
 356         }
 357         self.variants.iter().all(|v| v.fields.is_empty())
 358     }
 359
 360     /// Return a `VariantDef` given a variant id.
 361     pub fn variant_with_id(&self, vid: DefId) -> &VariantDef {
 362         self.variants.iter().find(|v| v.def_id == vid).expect("variant_with_id: unknown variant")
 363     }
 364
 365     /// Return a `VariantDef` given a constructor id.
 366     pub fn variant_with_ctor_id(&self, cid: DefId) -> &VariantDef {
 367         self.variants
 368             .iter()
 369             .find(|v| v.ctor_def_id == Some(cid))
 370             .expect("variant_with_ctor_id: unknown variant")
 371     }
 372
 373     /// Return the index of `VariantDef` given a variant id.
 374     pub fn variant_index_with_id(&self, vid: DefId) -> VariantIdx {
 375         self.variants
 376             .iter_enumerated()
 377             .find(|(_, v)| v.def_id == vid)
 378             .expect("variant_index_with_id: unknown variant")
 379             .0
 380     }
 381
 382     /// Return the index of `VariantDef` given a constructor id.
 383     pub fn variant_index_with_ctor_id(&self, cid: DefId) -> VariantIdx {
 384         self.variants
 385             .iter_enumerated()
 386             .find(|(_, v)| v.ctor_def_id == Some(cid))
 387             .expect("variant_index_with_ctor_id: unknown variant")
 388             .0
 389     }
 390
 391     pub fn variant_of_res(&self, res: Res) -> &VariantDef {
 392         match res {
 393             Res::Def(DefKind::Variant, vid) => self.variant_with_id(vid),
 394             Res::Def(DefKind::Ctor(..), cid) => self.variant_with_ctor_id(cid),
 395             Res::Def(DefKind::Struct, _)
 396             | Res::Def(DefKind::Union, _)
 397             | Res::Def(DefKind::TyAlias, _)
 398             | Res::Def(DefKind::AssocTy, _)
 399             | Res::SelfTy(..)
 400             | Res::SelfCtor(..) => self.non_enum_variant(),
 401             _ => bug!("unexpected res {:?} in variant_of_res", res),
 402         }
 403     }
 404
 405     #[inline]
 406     pub fn eval_explicit_discr(&self, tcx: TyCtxt<'tcx>, expr_did: DefId) -> Option<Discr<'tcx>> {
 407         assert!(self.is_enum());
 408         let param_env = tcx.param_env(expr_did);
 409         let repr_type = self.repr.discr_type();
 410         match tcx.const_eval_poly(expr_did) {
 411             Ok(val) => {
 412                 let ty = repr_type.to_ty(tcx);
 413                 if let Some(b) = val.try_to_bits_for_ty(tcx, param_env, ty) {
 414                     trace!("discriminants: {} ({:?})", b, repr_type);
 415                     Some(Discr { val: b, ty })
 416                 } else {
 417                     info!("invalid enum discriminant: {:#?}", val);
 418                     crate::mir::interpret::struct_error(
 419                         tcx.at(tcx.def_span(expr_did)),
 420                         "constant evaluation of enum discriminant resulted in non-integer",
 421                     )
 422                     .emit();
 423                     None
 424                 }
 425             }
 426             Err(err) => {
 427                 let msg = match err {
 428                     ErrorHandled::Reported(ErrorReported) | ErrorHandled::Linted => {
 429                         "enum discriminant evaluation failed"
 430                     }
 431                     ErrorHandled::TooGeneric => "enum discriminant depends on generics",
 432                 };
 433                 tcx.sess.delay_span_bug(tcx.def_span(expr_did), msg);
 434                 None
 435             }
 436         }
 437     }
 438
 439     #[inline]
 440     pub fn discriminants(
 441         &'tcx self,
 442         tcx: TyCtxt<'tcx>,
 443     ) -> impl Iterator<Item = (VariantIdx, Discr<'tcx>)> + Captures<'tcx> {
 444         assert!(self.is_enum());
 445         let repr_type = self.repr.discr_type();
 446         let initial = repr_type.initial_discriminant(tcx);
 447         let mut prev_discr = None::<Discr<'tcx>>;
 448         self.variants.iter_enumerated().map(move |(i, v)| {
 449             let mut discr = prev_discr.map_or(initial, |d| d.wrap_incr(tcx));
 450             if let VariantDiscr::Explicit(expr_did) = v.discr {
 451                 if let Some(new_discr) = self.eval_explicit_discr(tcx, expr_did) {
 452                     discr = new_discr;
 453                 }
 454             }
 455             prev_discr = Some(discr);
 456
 457             (i, discr)
 458         })
 459     }
 460
 461     #[inline]
 462     pub fn variant_range(&self) -> Range<VariantIdx> {
 463         VariantIdx::new(0)..VariantIdx::new(self.variants.len())
 464     }
 465
 466     /// Computes the discriminant value used by a specific variant.
 467     /// Unlike `discriminants`, this is (amortized) constant-time,
 468     /// only doing at most one query for evaluating an explicit
 469     /// discriminant (the last one before the requested variant),
 470     /// assuming there are no constant-evaluation errors there.
 471     #[inline]
 472     pub fn discriminant_for_variant(
 473         &self,
 474         tcx: TyCtxt<'tcx>,
 475         variant_index: VariantIdx,
 476     ) -> Discr<'tcx> {
 477         assert!(self.is_enum());
 478         let (val, offset) = self.discriminant_def_for_variant(variant_index);
 479         let explicit_value = val
 480             .and_then(|expr_did| self.eval_explicit_discr(tcx, expr_did))
 481             .unwrap_or_else(|| self.repr.discr_type().initial_discriminant(tcx));
 482         explicit_value.checked_add(tcx, offset as u128).0
 483     }
 484
 485     /// Yields a `DefId` for the discriminant and an offset to add to it
 486     /// Alternatively, if there is no explicit discriminant, returns the
 487     /// inferred discriminant directly.
 488     pub fn discriminant_def_for_variant(&self, variant_index: VariantIdx) -> (Option<DefId>, u32) {
 489         assert!(!self.variants.is_empty());
 490         let mut explicit_index = variant_index.as_u32();
 491         let expr_did;
 492         loop {
 493             match self.variants[VariantIdx::from_u32(explicit_index)].discr {
 494                 ty::VariantDiscr::Relative(0) => {
 495                     expr_did = None;
 496                     break;
 497                 }
 498                 ty::VariantDiscr::Relative(distance) => {
 499                     explicit_index -= distance;
 500                 }
 501                 ty::VariantDiscr::Explicit(did) => {
 502                     expr_did = Some(did);
 503                     break;
 504                 }
 505             }
 506         }
 507         (expr_did, variant_index.as_u32() - explicit_index)
 508     }
 509
 510     pub fn destructor(&self, tcx: TyCtxt<'tcx>) -> Option<Destructor> {
 511         tcx.adt_destructor(self.did)
 512     }
 513
 514     /// Returns a list of types such that `Self: Sized` if and only
 515     /// if that type is `Sized`, or `TyErr` if this type is recursive.
 516     ///
 517     /// Oddly enough, checking that the sized-constraint is `Sized` is
 518     /// actually more expressive than checking all members:
 519     /// the `Sized` trait is inductive, so an associated type that references
 520     /// `Self` would prevent its containing ADT from being `Sized`.
 521     ///
 522     /// Due to normalization being eager, this applies even if
 523     /// the associated type is behind a pointer (e.g., issue #31299).
 524     pub fn sized_constraint(&self, tcx: TyCtxt<'tcx>) -> &'tcx [Ty<'tcx>] {
 525         tcx.adt_sized_constraint(self.did).0
 526     }
 527 }