compiler/rustc_middle/src/ty/adt.rs

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