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