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