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