compiler/rustc_middle/src/ty/mod.rs

   1 //! Defines how the compiler represents types internally.
   2 //!
   3 //! Two important entities in this module are:
   4 //!
   5 //! - [`rustc_middle::ty::Ty`], used to represent the semantics of a type.
   6 //! - [`rustc_middle::ty::TyCtxt`], the central data structure in the compiler.
   7 //!
   8 //! For more information, see ["The `ty` module: representing types"] in the ructc-dev-guide.
   9 //!
  10 //! ["The `ty` module: representing types"]: https://rustc-dev-guide.rust-lang.org/ty.html
  11
  12 // ignore-tidy-filelength
  13 pub use self::fold::{TypeFoldable, TypeFolder, TypeVisitor};
  14 pub use self::AssocItemContainer::*;
  15 pub use self::BorrowKind::*;
  16 pub use self::IntVarValue::*;
  17 pub use self::Variance::*;
  18
  19 use crate::hir::exports::ExportMap;
  20 use crate::hir::place::{
  21     Place as HirPlace, PlaceBase as HirPlaceBase, ProjectionKind as HirProjectionKind,
  22 };
  23 use crate::ich::StableHashingContext;
  24 use crate::middle::cstore::CrateStoreDyn;
  25 use crate::middle::resolve_lifetime::ObjectLifetimeDefault;
  26 use crate::mir::interpret::ErrorHandled;
  27 use crate::mir::Body;
  28 use crate::mir::GeneratorLayout;
  29 use crate::traits::{self, Reveal};
  30 use crate::ty;
  31 use crate::ty::subst::{GenericArg, InternalSubsts, Subst, SubstsRef};
  32 use crate::ty::util::{Discr, IntTypeExt};
  33 use rustc_ast as ast;
  34 use rustc_attr as attr;
  35 use rustc_data_structures::captures::Captures;
  36 use rustc_data_structures::fingerprint::Fingerprint;
  37 use rustc_data_structures::fx::FxHashMap;
  38 use rustc_data_structures::fx::FxHashSet;
  39 use rustc_data_structures::fx::FxIndexMap;
  40 use rustc_data_structures::sorted_map::SortedIndexMultiMap;
  41 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  42 use rustc_data_structures::sync::{self, par_iter, ParallelIterator};
  43 use rustc_data_structures::tagged_ptr::CopyTaggedPtr;
  44 use rustc_errors::ErrorReported;
  45 use rustc_hir as hir;
  46 use rustc_hir::def::{CtorKind, CtorOf, DefKind, Namespace, Res};
  47 use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, LocalDefId, CRATE_DEF_INDEX};
  48 use rustc_hir::lang_items::LangItem;
  49 use rustc_hir::{Constness, Node};
  50 use rustc_index::vec::{Idx, IndexVec};
  51 use rustc_macros::HashStable;
  52 use rustc_serialize::{self, Encodable, Encoder};
  53 use rustc_session::DataTypeKind;
  54 use rustc_span::hygiene::ExpnId;
  55 use rustc_span::symbol::{kw, sym, Ident, Symbol};
  56 use rustc_span::Span;
  57 use rustc_target::abi::{Align, VariantIdx};
  58
  59 use std::cell::RefCell;
  60 use std::cmp::Ordering;
  61 use std::fmt;
  62 use std::hash::{Hash, Hasher};
  63 use std::ops::{ControlFlow, Range};
  64 use std::ptr;
  65 use std::str;
  66
  67 pub use self::sty::BoundRegionKind::*;
  68 pub use self::sty::RegionKind;
  69 pub use self::sty::RegionKind::*;
  70 pub use self::sty::TyKind::*;
  71 pub use self::sty::{Binder, BoundTy, BoundTyKind, BoundVar};
  72 pub use self::sty::{BoundRegion, BoundRegionKind, EarlyBoundRegion, FreeRegion, Region};
  73 pub use self::sty::{CanonicalPolyFnSig, FnSig, GenSig, PolyFnSig, PolyGenSig};
  74 pub use self::sty::{ClosureSubsts, GeneratorSubsts, TypeAndMut, UpvarSubsts};
  75 pub use self::sty::{ClosureSubstsParts, GeneratorSubstsParts};
  76 pub use self::sty::{ConstVid, RegionVid};
  77 pub use self::sty::{ExistentialPredicate, ParamConst, ParamTy, ProjectionTy};
  78 pub use self::sty::{ExistentialProjection, PolyExistentialProjection};
  79 pub use self::sty::{ExistentialTraitRef, PolyExistentialTraitRef};
  80 pub use self::sty::{PolyTraitRef, TraitRef, TyKind};
  81 pub use crate::ty::diagnostics::*;
  82 pub use rustc_type_ir::InferTy::*;
  83 pub use rustc_type_ir::*;
  84
  85 pub use self::binding::BindingMode;
  86 pub use self::binding::BindingMode::*;
  87
  88 pub use self::context::{tls, FreeRegionInfo, TyCtxt};
  89 pub use self::context::{
  90     CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations,
  91     DelaySpanBugEmitted, ResolvedOpaqueTy, UserType, UserTypeAnnotationIndex,
  92 };
  93 pub use self::context::{
  94     CtxtInterners, GeneratorInteriorTypeCause, GlobalCtxt, Lift, TypeckResults,
  95 };
  96
  97 pub use self::instance::{Instance, InstanceDef};
  98
  99 pub use self::list::List;
 100
 101 pub use self::trait_def::TraitDef;
 102
 103 pub use self::query::queries;
 104
 105 pub use self::consts::{Const, ConstInt, ConstKind, InferConst, ScalarInt};
 106
 107 pub mod _match;
 108 pub mod adjustment;
 109 pub mod binding;
 110 pub mod cast;
 111 pub mod codec;
 112 mod erase_regions;
 113 pub mod error;
 114 pub mod fast_reject;
 115 pub mod flags;
 116 pub mod fold;
 117 pub mod inhabitedness;
 118 pub mod layout;
 119 pub mod normalize_erasing_regions;
 120 pub mod outlives;
 121 pub mod print;
 122 pub mod query;
 123 pub mod relate;
 124 pub mod subst;
 125 pub mod trait_def;
 126 pub mod util;
 127 pub mod walk;
 128
 129 mod consts;
 130 mod context;
 131 mod diagnostics;
 132 mod instance;
 133 mod list;
 134 mod structural_impls;
 135 mod sty;
 136
 137 // Data types
 138
 139 pub struct ResolverOutputs {
 140     pub definitions: rustc_hir::definitions::Definitions,
 141     pub cstore: Box<CrateStoreDyn>,
 142     pub visibilities: FxHashMap<LocalDefId, Visibility>,
 143     pub extern_crate_map: FxHashMap<LocalDefId, CrateNum>,
 144     pub maybe_unused_trait_imports: FxHashSet<LocalDefId>,
 145     pub maybe_unused_extern_crates: Vec<(LocalDefId, Span)>,
 146     pub export_map: ExportMap<LocalDefId>,
 147     pub glob_map: FxHashMap<LocalDefId, FxHashSet<Symbol>>,
 148     /// Extern prelude entries. The value is `true` if the entry was introduced
 149     /// via `extern crate` item and not `--extern` option or compiler built-in.
 150     pub extern_prelude: FxHashMap<Symbol, bool>,
 151 }
 152
 153 #[derive(Clone, Copy, PartialEq, Eq, Debug, HashStable, Hash)]
 154 pub enum AssocItemContainer {
 155     TraitContainer(DefId),
 156     ImplContainer(DefId),
 157 }
 158
 159 impl AssocItemContainer {
 160     /// Asserts that this is the `DefId` of an associated item declared
 161     /// in a trait, and returns the trait `DefId`.
 162     pub fn assert_trait(&self) -> DefId {
 163         match *self {
 164             TraitContainer(id) => id,
 165             _ => bug!("associated item has wrong container type: {:?}", self),
 166         }
 167     }
 168
 169     pub fn id(&self) -> DefId {
 170         match *self {
 171             TraitContainer(id) => id,
 172             ImplContainer(id) => id,
 173         }
 174     }
 175 }
 176
 177 /// The "header" of an impl is everything outside the body: a Self type, a trait
 178 /// ref (in the case of a trait impl), and a set of predicates (from the
 179 /// bounds / where-clauses).
 180 #[derive(Clone, Debug, TypeFoldable)]
 181 pub struct ImplHeader<'tcx> {
 182     pub impl_def_id: DefId,
 183     pub self_ty: Ty<'tcx>,
 184     pub trait_ref: Option<TraitRef<'tcx>>,
 185     pub predicates: Vec<Predicate<'tcx>>,
 186 }
 187
 188 #[derive(Copy, Clone, PartialEq, TyEncodable, TyDecodable, HashStable, Debug)]
 189 pub enum ImplPolarity {
 190     /// `impl Trait for Type`
 191     Positive,
 192     /// `impl !Trait for Type`
 193     Negative,
 194     /// `#[rustc_reservation_impl] impl Trait for Type`
 195     ///
 196     /// This is a "stability hack", not a real Rust feature.
 197     /// See #64631 for details.
 198     Reservation,
 199 }
 200
 201 #[derive(Copy, Clone, Debug, PartialEq, HashStable, Eq, Hash)]
 202 pub struct AssocItem {
 203     pub def_id: DefId,
 204     #[stable_hasher(project(name))]
 205     pub ident: Ident,
 206     pub kind: AssocKind,
 207     pub vis: Visibility,
 208     pub defaultness: hir::Defaultness,
 209     pub container: AssocItemContainer,
 210
 211     /// Whether this is a method with an explicit self
 212     /// as its first parameter, allowing method calls.
 213     pub fn_has_self_parameter: bool,
 214 }
 215
 216 #[derive(Copy, Clone, PartialEq, Debug, HashStable, Eq, Hash)]
 217 pub enum AssocKind {
 218     Const,
 219     Fn,
 220     Type,
 221 }
 222
 223 impl AssocKind {
 224     pub fn namespace(&self) -> Namespace {
 225         match *self {
 226             ty::AssocKind::Type => Namespace::TypeNS,
 227             ty::AssocKind::Const | ty::AssocKind::Fn => Namespace::ValueNS,
 228         }
 229     }
 230
 231     pub fn as_def_kind(&self) -> DefKind {
 232         match self {
 233             AssocKind::Const => DefKind::AssocConst,
 234             AssocKind::Fn => DefKind::AssocFn,
 235             AssocKind::Type => DefKind::AssocTy,
 236         }
 237     }
 238 }
 239
 240 impl AssocItem {
 241     pub fn signature(&self, tcx: TyCtxt<'_>) -> String {
 242         match self.kind {
 243             ty::AssocKind::Fn => {
 244                 // We skip the binder here because the binder would deanonymize all
 245                 // late-bound regions, and we don't want method signatures to show up
 246                 // `as for<'r> fn(&'r MyType)`.  Pretty-printing handles late-bound
 247                 // regions just fine, showing `fn(&MyType)`.
 248                 tcx.fn_sig(self.def_id).skip_binder().to_string()
 249             }
 250             ty::AssocKind::Type => format!("type {};", self.ident),
 251             ty::AssocKind::Const => {
 252                 format!("const {}: {:?};", self.ident, tcx.type_of(self.def_id))
 253             }
 254         }
 255     }
 256 }
 257
 258 /// A list of `ty::AssocItem`s in definition order that allows for efficient lookup by name.
 259 ///
 260 /// When doing lookup by name, we try to postpone hygienic comparison for as long as possible since
 261 /// it is relatively expensive. Instead, items are indexed by `Symbol` and hygienic comparison is
 262 /// done only on items with the same name.
 263 #[derive(Debug, Clone, PartialEq, HashStable)]
 264 pub struct AssociatedItems<'tcx> {
 265     items: SortedIndexMultiMap<u32, Symbol, &'tcx ty::AssocItem>,
 266 }
 267
 268 impl<'tcx> AssociatedItems<'tcx> {
 269     /// Constructs an `AssociatedItems` map from a series of `ty::AssocItem`s in definition order.
 270     pub fn new(items_in_def_order: impl IntoIterator<Item = &'tcx ty::AssocItem>) -> Self {
 271         let items = items_in_def_order.into_iter().map(|item| (item.ident.name, item)).collect();
 272         AssociatedItems { items }
 273     }
 274
 275     /// Returns a slice of associated items in the order they were defined.
 276     ///
 277     /// New code should avoid relying on definition order. If you need a particular associated item
 278     /// for a known trait, make that trait a lang item instead of indexing this array.
 279     pub fn in_definition_order(&self) -> impl '_ + Iterator<Item = &ty::AssocItem> {
 280         self.items.iter().map(|(_, v)| *v)
 281     }
 282
 283     pub fn len(&self) -> usize {
 284         self.items.len()
 285     }
 286
 287     /// Returns an iterator over all associated items with the given name, ignoring hygiene.
 288     pub fn filter_by_name_unhygienic(
 289         &self,
 290         name: Symbol,
 291     ) -> impl '_ + Iterator<Item = &ty::AssocItem> {
 292         self.items.get_by_key(&name).copied()
 293     }
 294
 295     /// Returns an iterator over all associated items with the given name.
 296     ///
 297     /// Multiple items may have the same name if they are in different `Namespace`s. For example,
 298     /// an associated type can have the same name as a method. Use one of the `find_by_name_and_*`
 299     /// methods below if you know which item you are looking for.
 300     pub fn filter_by_name(
 301         &'a self,
 302         tcx: TyCtxt<'a>,
 303         ident: Ident,
 304         parent_def_id: DefId,
 305     ) -> impl 'a + Iterator<Item = &'a ty::AssocItem> {
 306         self.filter_by_name_unhygienic(ident.name)
 307             .filter(move |item| tcx.hygienic_eq(ident, item.ident, parent_def_id))
 308     }
 309
 310     /// Returns the associated item with the given name and `AssocKind`, if one exists.
 311     pub fn find_by_name_and_kind(
 312         &self,
 313         tcx: TyCtxt<'_>,
 314         ident: Ident,
 315         kind: AssocKind,
 316         parent_def_id: DefId,
 317     ) -> Option<&ty::AssocItem> {
 318         self.filter_by_name_unhygienic(ident.name)
 319             .filter(|item| item.kind == kind)
 320             .find(|item| tcx.hygienic_eq(ident, item.ident, parent_def_id))
 321     }
 322
 323     /// Returns the associated item with the given name in the given `Namespace`, if one exists.
 324     pub fn find_by_name_and_namespace(
 325         &self,
 326         tcx: TyCtxt<'_>,
 327         ident: Ident,
 328         ns: Namespace,
 329         parent_def_id: DefId,
 330     ) -> Option<&ty::AssocItem> {
 331         self.filter_by_name_unhygienic(ident.name)
 332             .filter(|item| item.kind.namespace() == ns)
 333             .find(|item| tcx.hygienic_eq(ident, item.ident, parent_def_id))
 334     }
 335 }
 336
 337 #[derive(Clone, Debug, PartialEq, Eq, Copy, Hash, TyEncodable, TyDecodable, HashStable)]
 338 pub enum Visibility {
 339     /// Visible everywhere (including in other crates).
 340     Public,
 341     /// Visible only in the given crate-local module.
 342     Restricted(DefId),
 343     /// Not visible anywhere in the local crate. This is the visibility of private external items.
 344     Invisible,
 345 }
 346
 347 pub trait DefIdTree: Copy {
 348     fn parent(self, id: DefId) -> Option<DefId>;
 349
 350     fn is_descendant_of(self, mut descendant: DefId, ancestor: DefId) -> bool {
 351         if descendant.krate != ancestor.krate {
 352             return false;
 353         }
 354
 355         while descendant != ancestor {
 356             match self.parent(descendant) {
 357                 Some(parent) => descendant = parent,
 358                 None => return false,
 359             }
 360         }
 361         true
 362     }
 363 }
 364
 365 impl<'tcx> DefIdTree for TyCtxt<'tcx> {
 366     fn parent(self, id: DefId) -> Option<DefId> {
 367         self.def_key(id).parent.map(|index| DefId { index, ..id })
 368     }
 369 }
 370
 371 impl Visibility {
 372     pub fn from_hir(visibility: &hir::Visibility<'_>, id: hir::HirId, tcx: TyCtxt<'_>) -> Self {
 373         match visibility.node {
 374             hir::VisibilityKind::Public => Visibility::Public,
 375             hir::VisibilityKind::Crate(_) => Visibility::Restricted(DefId::local(CRATE_DEF_INDEX)),
 376             hir::VisibilityKind::Restricted { ref path, .. } => match path.res {
 377                 // If there is no resolution, `resolve` will have already reported an error, so
 378                 // assume that the visibility is public to avoid reporting more privacy errors.
 379                 Res::Err => Visibility::Public,
 380                 def => Visibility::Restricted(def.def_id()),
 381             },
 382             hir::VisibilityKind::Inherited => {
 383                 Visibility::Restricted(tcx.parent_module(id).to_def_id())
 384             }
 385         }
 386     }
 387
 388     /// Returns `true` if an item with this visibility is accessible from the given block.
 389     pub fn is_accessible_from<T: DefIdTree>(self, module: DefId, tree: T) -> bool {
 390         let restriction = match self {
 391             // Public items are visible everywhere.
 392             Visibility::Public => return true,
 393             // Private items from other crates are visible nowhere.
 394             Visibility::Invisible => return false,
 395             // Restricted items are visible in an arbitrary local module.
 396             Visibility::Restricted(other) if other.krate != module.krate => return false,
 397             Visibility::Restricted(module) => module,
 398         };
 399
 400         tree.is_descendant_of(module, restriction)
 401     }
 402
 403     /// Returns `true` if this visibility is at least as accessible as the given visibility
 404     pub fn is_at_least<T: DefIdTree>(self, vis: Visibility, tree: T) -> bool {
 405         let vis_restriction = match vis {
 406             Visibility::Public => return self == Visibility::Public,
 407             Visibility::Invisible => return true,
 408             Visibility::Restricted(module) => module,
 409         };
 410
 411         self.is_accessible_from(vis_restriction, tree)
 412     }
 413
 414     // Returns `true` if this item is visible anywhere in the local crate.
 415     pub fn is_visible_locally(self) -> bool {
 416         match self {
 417             Visibility::Public => true,
 418             Visibility::Restricted(def_id) => def_id.is_local(),
 419             Visibility::Invisible => false,
 420         }
 421     }
 422 }
 423
 424 /// The crate variances map is computed during typeck and contains the
 425 /// variance of every item in the local crate. You should not use it
 426 /// directly, because to do so will make your pass dependent on the
 427 /// HIR of every item in the local crate. Instead, use
 428 /// `tcx.variances_of()` to get the variance for a *particular*
 429 /// item.
 430 #[derive(HashStable, Debug)]
 431 pub struct CrateVariancesMap<'tcx> {
 432     /// For each item with generics, maps to a vector of the variance
 433     /// of its generics. If an item has no generics, it will have no
 434     /// entry.
 435     pub variances: FxHashMap<DefId, &'tcx [ty::Variance]>,
 436 }
 437
 438 // Contains information needed to resolve types and (in the future) look up
 439 // the types of AST nodes.
 440 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 441 pub struct CReaderCacheKey {
 442     pub cnum: CrateNum,
 443     pub pos: usize,
 444 }
 445
 446 #[allow(rustc::usage_of_ty_tykind)]
 447 pub struct TyS<'tcx> {
 448     /// This field shouldn't be used directly and may be removed in the future.
 449     /// Use `TyS::kind()` instead.
 450     kind: TyKind<'tcx>,
 451     /// This field shouldn't be used directly and may be removed in the future.
 452     /// Use `TyS::flags()` instead.
 453     flags: TypeFlags,
 454
 455     /// This is a kind of confusing thing: it stores the smallest
 456     /// binder such that
 457     ///
 458     /// (a) the binder itself captures nothing but
 459     /// (b) all the late-bound things within the type are captured
 460     ///     by some sub-binder.
 461     ///
 462     /// So, for a type without any late-bound things, like `u32`, this
 463     /// will be *innermost*, because that is the innermost binder that
 464     /// captures nothing. But for a type `&'D u32`, where `'D` is a
 465     /// late-bound region with De Bruijn index `D`, this would be `D + 1`
 466     /// -- the binder itself does not capture `D`, but `D` is captured
 467     /// by an inner binder.
 468     ///
 469     /// We call this concept an "exclusive" binder `D` because all
 470     /// De Bruijn indices within the type are contained within `0..D`
 471     /// (exclusive).
 472     outer_exclusive_binder: ty::DebruijnIndex,
 473 }
 474
 475 impl<'tcx> TyS<'tcx> {
 476     /// A constructor used only for internal testing.
 477     #[allow(rustc::usage_of_ty_tykind)]
 478     pub fn make_for_test(
 479         kind: TyKind<'tcx>,
 480         flags: TypeFlags,
 481         outer_exclusive_binder: ty::DebruijnIndex,
 482     ) -> TyS<'tcx> {
 483         TyS { kind, flags, outer_exclusive_binder }
 484     }
 485 }
 486
 487 // `TyS` is used a lot. Make sure it doesn't unintentionally get bigger.
 488 #[cfg(target_arch = "x86_64")]
 489 static_assert_size!(TyS<'_>, 32);
 490
 491 impl<'tcx> Ord for TyS<'tcx> {
 492     fn cmp(&self, other: &TyS<'tcx>) -> Ordering {
 493         self.kind().cmp(other.kind())
 494     }
 495 }
 496
 497 impl<'tcx> PartialOrd for TyS<'tcx> {
 498     fn partial_cmp(&self, other: &TyS<'tcx>) -> Option<Ordering> {
 499         Some(self.kind().cmp(other.kind()))
 500     }
 501 }
 502
 503 impl<'tcx> PartialEq for TyS<'tcx> {
 504     #[inline]
 505     fn eq(&self, other: &TyS<'tcx>) -> bool {
 506         ptr::eq(self, other)
 507     }
 508 }
 509 impl<'tcx> Eq for TyS<'tcx> {}
 510
 511 impl<'tcx> Hash for TyS<'tcx> {
 512     fn hash<H: Hasher>(&self, s: &mut H) {
 513         (self as *const TyS<'_>).hash(s)
 514     }
 515 }
 516
 517 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for TyS<'tcx> {
 518     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 519         let ty::TyS {
 520             ref kind,
 521
 522             // The other fields just provide fast access to information that is
 523             // also contained in `kind`, so no need to hash them.
 524             flags: _,
 525
 526             outer_exclusive_binder: _,
 527         } = *self;
 528
 529         kind.hash_stable(hcx, hasher);
 530     }
 531 }
 532
 533 #[rustc_diagnostic_item = "Ty"]
 534 pub type Ty<'tcx> = &'tcx TyS<'tcx>;
 535
 536 #[derive(
 537     Clone,
 538     Copy,
 539     Debug,
 540     PartialEq,
 541     Eq,
 542     Hash,
 543     TyEncodable,
 544     TyDecodable,
 545     TypeFoldable,
 546     HashStable
 547 )]
 548 pub struct UpvarPath {
 549     pub hir_id: hir::HirId,
 550 }
 551
 552 /// Upvars do not get their own `NodeId`. Instead, we use the pair of
 553 /// the original var ID (that is, the root variable that is referenced
 554 /// by the upvar) and the ID of the closure expression.
 555 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
 556 pub struct UpvarId {
 557     pub var_path: UpvarPath,
 558     pub closure_expr_id: LocalDefId,
 559 }
 560
 561 impl UpvarId {
 562     pub fn new(var_hir_id: hir::HirId, closure_def_id: LocalDefId) -> UpvarId {
 563         UpvarId { var_path: UpvarPath { hir_id: var_hir_id }, closure_expr_id: closure_def_id }
 564     }
 565 }
 566
 567 #[derive(Clone, PartialEq, Debug, TyEncodable, TyDecodable, TypeFoldable, Copy, HashStable)]
 568 pub enum BorrowKind {
 569     /// Data must be immutable and is aliasable.
 570     ImmBorrow,
 571
 572     /// Data must be immutable but not aliasable. This kind of borrow
 573     /// cannot currently be expressed by the user and is used only in
 574     /// implicit closure bindings. It is needed when the closure
 575     /// is borrowing or mutating a mutable referent, e.g.:
 576     ///
 577     /// ```
 578     /// let x: &mut isize = ...;
 579     /// let y = || *x += 5;
 580     /// ```
 581     ///
 582     /// If we were to try to translate this closure into a more explicit
 583     /// form, we'd encounter an error with the code as written:
 584     ///
 585     /// ```
 586     /// struct Env { x: & &mut isize }
 587     /// let x: &mut isize = ...;
 588     /// let y = (&mut Env { &x }, fn_ptr);  // Closure is pair of env and fn
 589     /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
 590     /// ```
 591     ///
 592     /// This is then illegal because you cannot mutate a `&mut` found
 593     /// in an aliasable location. To solve, you'd have to translate with
 594     /// an `&mut` borrow:
 595     ///
 596     /// ```
 597     /// struct Env { x: & &mut isize }
 598     /// let x: &mut isize = ...;
 599     /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
 600     /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
 601     /// ```
 602     ///
 603     /// Now the assignment to `**env.x` is legal, but creating a
 604     /// mutable pointer to `x` is not because `x` is not mutable. We
 605     /// could fix this by declaring `x` as `let mut x`. This is ok in
 606     /// user code, if awkward, but extra weird for closures, since the
 607     /// borrow is hidden.
 608     ///
 609     /// So we introduce a "unique imm" borrow -- the referent is
 610     /// immutable, but not aliasable. This solves the problem. For
 611     /// simplicity, we don't give users the way to express this
 612     /// borrow, it's just used when translating closures.
 613     UniqueImmBorrow,
 614
 615     /// Data is mutable and not aliasable.
 616     MutBorrow,
 617 }
 618
 619 /// Information describing the capture of an upvar. This is computed
 620 /// during `typeck`, specifically by `regionck`.
 621 #[derive(PartialEq, Clone, Debug, Copy, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
 622 pub enum UpvarCapture<'tcx> {
 623     /// Upvar is captured by value. This is always true when the
 624     /// closure is labeled `move`, but can also be true in other cases
 625     /// depending on inference.
 626     ///
 627     /// If the upvar was inferred to be captured by value (e.g. `move`
 628     /// was not used), then the `Span` points to a usage that
 629     /// required it. There may be more than one such usage
 630     /// (e.g. `|| { a; a; }`), in which case we pick an
 631     /// arbitrary one.
 632     ByValue(Option<Span>),
 633
 634     /// Upvar is captured by reference.
 635     ByRef(UpvarBorrow<'tcx>),
 636 }
 637
 638 #[derive(PartialEq, Clone, Copy, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
 639 pub struct UpvarBorrow<'tcx> {
 640     /// The kind of borrow: by-ref upvars have access to shared
 641     /// immutable borrows, which are not part of the normal language
 642     /// syntax.
 643     pub kind: BorrowKind,
 644
 645     /// Region of the resulting reference.
 646     pub region: ty::Region<'tcx>,
 647 }
 648
 649 /// Given the closure DefId this map provides a map of root variables to minimum
 650 /// set of `CapturedPlace`s that need to be tracked to support all captures of that closure.
 651 pub type MinCaptureInformationMap<'tcx> = FxHashMap<DefId, RootVariableMinCaptureList<'tcx>>;
 652
 653 /// Part of `MinCaptureInformationMap`; Maps a root variable to the list of `CapturedPlace`.
 654 /// Used to track the minimum set of `Place`s that need to be captured to support all
 655 /// Places captured by the closure starting at a given root variable.
 656 ///
 657 /// This provides a convenient and quick way of checking if a variable being used within
 658 /// a closure is a capture of a local variable.
 659 pub type RootVariableMinCaptureList<'tcx> = FxIndexMap<hir::HirId, MinCaptureList<'tcx>>;
 660
 661 /// Part of `MinCaptureInformationMap`; List of `CapturePlace`s.
 662 pub type MinCaptureList<'tcx> = Vec<CapturedPlace<'tcx>>;
 663
 664 /// A composite describing a `Place` that is captured by a closure.
 665 #[derive(PartialEq, Clone, Debug, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
 666 pub struct CapturedPlace<'tcx> {
 667     /// The `Place` that is captured.
 668     pub place: HirPlace<'tcx>,
 669
 670     /// `CaptureKind` and expression(s) that resulted in such capture of `place`.
 671     pub info: CaptureInfo<'tcx>,
 672
 673     /// Represents if `place` can be mutated or not.
 674     pub mutability: hir::Mutability,
 675 }
 676
 677 impl CapturedPlace<'tcx> {
 678     /// Returns the hir-id of the root variable for the captured place.
 679     /// e.g., if `a.b.c` was captured, would return the hir-id for `a`.
 680     pub fn get_root_variable(&self) -> hir::HirId {
 681         match self.place.base {
 682             HirPlaceBase::Upvar(upvar_id) => upvar_id.var_path.hir_id,
 683             base => bug!("Expected upvar, found={:?}", base),
 684         }
 685     }
 686 }
 687
 688 pub fn place_to_string_for_capture(tcx: TyCtxt<'tcx>, place: &HirPlace<'tcx>) -> String {
 689     let name = match place.base {
 690         HirPlaceBase::Upvar(upvar_id) => tcx.hir().name(upvar_id.var_path.hir_id).to_string(),
 691         _ => bug!("Capture_information should only contain upvars"),
 692     };
 693     let mut curr_string = name;
 694
 695     for (i, proj) in place.projections.iter().enumerate() {
 696         match proj.kind {
 697             HirProjectionKind::Deref => {
 698                 curr_string = format!("*{}", curr_string);
 699             }
 700             HirProjectionKind::Field(idx, variant) => match place.ty_before_projection(i).kind() {
 701                 ty::Adt(def, ..) => {
 702                     curr_string = format!(
 703                         "{}.{}",
 704                         curr_string,
 705                         def.variants[variant].fields[idx as usize].ident.name.as_str()
 706                     );
 707                 }
 708                 ty::Tuple(_) => {
 709                     curr_string = format!("{}.{}", curr_string, idx);
 710                 }
 711                 _ => {
 712                     bug!(
 713                         "Field projection applied to a type other than Adt or Tuple: {:?}.",
 714                         place.ty_before_projection(i).kind()
 715                     )
 716                 }
 717             },
 718             proj => bug!("{:?} unexpected because it isn't captured", proj),
 719         }
 720     }
 721
 722     curr_string.to_string()
 723 }
 724
 725 /// Part of `MinCaptureInformationMap`; describes the capture kind (&, &mut, move)
 726 /// for a particular capture as well as identifying the part of the source code
 727 /// that triggered this capture to occur.
 728 #[derive(PartialEq, Clone, Debug, Copy, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
 729 pub struct CaptureInfo<'tcx> {
 730     /// Expr Id pointing to use that resulted in selecting the current capture kind
 731     ///
 732     /// Eg:
 733     /// ```rust,no_run
 734     /// let mut t = (0,1);
 735     ///
 736     /// let c = || {
 737     ///     println!("{}",t); // L1
 738     ///     t.1 = 4; // L2
 739     /// };
 740     /// ```
 741     /// `capture_kind_expr_id` will point to the use on L2 and `path_expr_id` will point to the
 742     /// use on L1.
 743     ///
 744     /// If the user doesn't enable feature `capture_disjoint_fields` (RFC 2229) then, it is
 745     /// possible that we don't see the use of a particular place resulting in capture_kind_expr_id being
 746     /// None. In such case we fallback on uvpars_mentioned for span.
 747     ///
 748     /// Eg:
 749     /// ```rust,no_run
 750     /// let x = 5;
 751     ///
 752     /// let c = || {
 753     ///     let _ = x
 754     /// };
 755     /// ```
 756     ///
 757     /// In this example, if `capture_disjoint_fields` is **not** set, then x will be captured,
 758     /// but we won't see it being used during capture analysis, since it's essentially a discard.
 759     pub capture_kind_expr_id: Option<hir::HirId>,
 760     /// Expr Id pointing to use that resulted the corresponding place being captured
 761     ///
 762     /// See `capture_kind_expr_id` for example.
 763     ///
 764     pub path_expr_id: Option<hir::HirId>,
 765
 766     /// Capture mode that was selected
 767     pub capture_kind: UpvarCapture<'tcx>,
 768 }
 769
 770 pub type UpvarListMap = FxHashMap<DefId, FxIndexMap<hir::HirId, UpvarId>>;
 771 pub type UpvarCaptureMap<'tcx> = FxHashMap<UpvarId, UpvarCapture<'tcx>>;
 772
 773 impl ty::EarlyBoundRegion {
 774     /// Does this early bound region have a name? Early bound regions normally
 775     /// always have names except when using anonymous lifetimes (`'_`).
 776     pub fn has_name(&self) -> bool {
 777         self.name != kw::UnderscoreLifetime
 778     }
 779 }
 780
 781 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
 782 pub enum GenericParamDefKind {
 783     Lifetime,
 784     Type {
 785         has_default: bool,
 786         object_lifetime_default: ObjectLifetimeDefault,
 787         synthetic: Option<hir::SyntheticTyParamKind>,
 788     },
 789     Const,
 790 }
 791
 792 impl GenericParamDefKind {
 793     pub fn descr(&self) -> &'static str {
 794         match self {
 795             GenericParamDefKind::Lifetime => "lifetime",
 796             GenericParamDefKind::Type { .. } => "type",
 797             GenericParamDefKind::Const => "constant",
 798         }
 799     }
 800     pub fn to_ord(&self, tcx: TyCtxt<'_>) -> ast::ParamKindOrd {
 801         match self {
 802             GenericParamDefKind::Lifetime => ast::ParamKindOrd::Lifetime,
 803             GenericParamDefKind::Type { .. } => ast::ParamKindOrd::Type,
 804             GenericParamDefKind::Const => {
 805                 ast::ParamKindOrd::Const { unordered: tcx.features().const_generics }
 806             }
 807         }
 808     }
 809 }
 810
 811 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
 812 pub struct GenericParamDef {
 813     pub name: Symbol,
 814     pub def_id: DefId,
 815     pub index: u32,
 816
 817     /// `pure_wrt_drop`, set by the (unsafe) `#[may_dangle]` attribute
 818     /// on generic parameter `'a`/`T`, asserts data behind the parameter
 819     /// `'a`/`T` won't be accessed during the parent type's `Drop` impl.
 820     pub pure_wrt_drop: bool,
 821
 822     pub kind: GenericParamDefKind,
 823 }
 824
 825 impl GenericParamDef {
 826     pub fn to_early_bound_region_data(&self) -> ty::EarlyBoundRegion {
 827         if let GenericParamDefKind::Lifetime = self.kind {
 828             ty::EarlyBoundRegion { def_id: self.def_id, index: self.index, name: self.name }
 829         } else {
 830             bug!("cannot convert a non-lifetime parameter def to an early bound region")
 831         }
 832     }
 833 }
 834
 835 #[derive(Default)]
 836 pub struct GenericParamCount {
 837     pub lifetimes: usize,
 838     pub types: usize,
 839     pub consts: usize,
 840 }
 841
 842 /// Information about the formal type/lifetime parameters associated
 843 /// with an item or method. Analogous to `hir::Generics`.
 844 ///
 845 /// The ordering of parameters is the same as in `Subst` (excluding child generics):
 846 /// `Self` (optionally), `Lifetime` params..., `Type` params...
 847 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
 848 pub struct Generics {
 849     pub parent: Option<DefId>,
 850     pub parent_count: usize,
 851     pub params: Vec<GenericParamDef>,
 852
 853     /// Reverse map to the `index` field of each `GenericParamDef`.
 854     #[stable_hasher(ignore)]
 855     pub param_def_id_to_index: FxHashMap<DefId, u32>,
 856
 857     pub has_self: bool,
 858     pub has_late_bound_regions: Option<Span>,
 859 }
 860
 861 impl<'tcx> Generics {
 862     pub fn count(&self) -> usize {
 863         self.parent_count + self.params.len()
 864     }
 865
 866     pub fn own_counts(&self) -> GenericParamCount {
 867         // We could cache this as a property of `GenericParamCount`, but
 868         // the aim is to refactor this away entirely eventually and the
 869         // presence of this method will be a constant reminder.
 870         let mut own_counts = GenericParamCount::default();
 871
 872         for param in &self.params {
 873             match param.kind {
 874                 GenericParamDefKind::Lifetime => own_counts.lifetimes += 1,
 875                 GenericParamDefKind::Type { .. } => own_counts.types += 1,
 876                 GenericParamDefKind::Const => own_counts.consts += 1,
 877             }
 878         }
 879
 880         own_counts
 881     }
 882
 883     pub fn own_defaults(&self) -> GenericParamCount {
 884         let mut own_defaults = GenericParamCount::default();
 885
 886         for param in &self.params {
 887             match param.kind {
 888                 GenericParamDefKind::Lifetime => (),
 889                 GenericParamDefKind::Type { has_default, .. } => {
 890                     own_defaults.types += has_default as usize;
 891                 }
 892                 GenericParamDefKind::Const => {
 893                     // FIXME(const_generics:defaults)
 894                 }
 895             }
 896         }
 897
 898         own_defaults
 899     }
 900
 901     pub fn requires_monomorphization(&self, tcx: TyCtxt<'tcx>) -> bool {
 902         if self.own_requires_monomorphization() {
 903             return true;
 904         }
 905
 906         if let Some(parent_def_id) = self.parent {
 907             let parent = tcx.generics_of(parent_def_id);
 908             parent.requires_monomorphization(tcx)
 909         } else {
 910             false
 911         }
 912     }
 913
 914     pub fn own_requires_monomorphization(&self) -> bool {
 915         for param in &self.params {
 916             match param.kind {
 917                 GenericParamDefKind::Type { .. } | GenericParamDefKind::Const => return true,
 918                 GenericParamDefKind::Lifetime => {}
 919             }
 920         }
 921         false
 922     }
 923
 924     /// Returns the `GenericParamDef` with the given index.
 925     pub fn param_at(&'tcx self, param_index: usize, tcx: TyCtxt<'tcx>) -> &'tcx GenericParamDef {
 926         if let Some(index) = param_index.checked_sub(self.parent_count) {
 927             &self.params[index]
 928         } else {
 929             tcx.generics_of(self.parent.expect("parent_count > 0 but no parent?"))
 930                 .param_at(param_index, tcx)
 931         }
 932     }
 933
 934     /// Returns the `GenericParamDef` associated with this `EarlyBoundRegion`.
 935     pub fn region_param(
 936         &'tcx self,
 937         param: &EarlyBoundRegion,
 938         tcx: TyCtxt<'tcx>,
 939     ) -> &'tcx GenericParamDef {
 940         let param = self.param_at(param.index as usize, tcx);
 941         match param.kind {
 942             GenericParamDefKind::Lifetime => param,
 943             _ => bug!("expected lifetime parameter, but found another generic parameter"),
 944         }
 945     }
 946
 947     /// Returns the `GenericParamDef` associated with this `ParamTy`.
 948     pub fn type_param(&'tcx self, param: &ParamTy, tcx: TyCtxt<'tcx>) -> &'tcx GenericParamDef {
 949         let param = self.param_at(param.index as usize, tcx);
 950         match param.kind {
 951             GenericParamDefKind::Type { .. } => param,
 952             _ => bug!("expected type parameter, but found another generic parameter"),
 953         }
 954     }
 955
 956     /// Returns the `GenericParamDef` associated with this `ParamConst`.
 957     pub fn const_param(&'tcx self, param: &ParamConst, tcx: TyCtxt<'tcx>) -> &GenericParamDef {
 958         let param = self.param_at(param.index as usize, tcx);
 959         match param.kind {
 960             GenericParamDefKind::Const => param,
 961             _ => bug!("expected const parameter, but found another generic parameter"),
 962         }
 963     }
 964 }
 965
 966 /// Bounds on generics.
 967 #[derive(Copy, Clone, Default, Debug, TyEncodable, TyDecodable, HashStable)]
 968 pub struct GenericPredicates<'tcx> {
 969     pub parent: Option<DefId>,
 970     pub predicates: &'tcx [(Predicate<'tcx>, Span)],
 971 }
 972
 973 impl<'tcx> GenericPredicates<'tcx> {
 974     pub fn instantiate(
 975         &self,
 976         tcx: TyCtxt<'tcx>,
 977         substs: SubstsRef<'tcx>,
 978     ) -> InstantiatedPredicates<'tcx> {
 979         let mut instantiated = InstantiatedPredicates::empty();
 980         self.instantiate_into(tcx, &mut instantiated, substs);
 981         instantiated
 982     }
 983
 984     pub fn instantiate_own(
 985         &self,
 986         tcx: TyCtxt<'tcx>,
 987         substs: SubstsRef<'tcx>,
 988     ) -> InstantiatedPredicates<'tcx> {
 989         InstantiatedPredicates {
 990             predicates: self.predicates.iter().map(|(p, _)| p.subst(tcx, substs)).collect(),
 991             spans: self.predicates.iter().map(|(_, sp)| *sp).collect(),
 992         }
 993     }
 994
 995     fn instantiate_into(
 996         &self,
 997         tcx: TyCtxt<'tcx>,
 998         instantiated: &mut InstantiatedPredicates<'tcx>,
 999         substs: SubstsRef<'tcx>,
1000     ) {
1001         if let Some(def_id) = self.parent {
1002             tcx.predicates_of(def_id).instantiate_into(tcx, instantiated, substs);
1003         }
1004         instantiated.predicates.extend(self.predicates.iter().map(|(p, _)| p.subst(tcx, substs)));
1005         instantiated.spans.extend(self.predicates.iter().map(|(_, sp)| *sp));
1006     }
1007
1008     pub fn instantiate_identity(&self, tcx: TyCtxt<'tcx>) -> InstantiatedPredicates<'tcx> {
1009         let mut instantiated = InstantiatedPredicates::empty();
1010         self.instantiate_identity_into(tcx, &mut instantiated);
1011         instantiated
1012     }
1013
1014     fn instantiate_identity_into(
1015         &self,
1016         tcx: TyCtxt<'tcx>,
1017         instantiated: &mut InstantiatedPredicates<'tcx>,
1018     ) {
1019         if let Some(def_id) = self.parent {
1020             tcx.predicates_of(def_id).instantiate_identity_into(tcx, instantiated);
1021         }
1022         instantiated.predicates.extend(self.predicates.iter().map(|(p, _)| p));
1023         instantiated.spans.extend(self.predicates.iter().map(|(_, s)| s));
1024     }
1025 }
1026
1027 #[derive(Debug)]
1028 crate struct PredicateInner<'tcx> {
1029     kind: Binder<PredicateKind<'tcx>>,
1030     flags: TypeFlags,
1031     /// See the comment for the corresponding field of [TyS].
1032     outer_exclusive_binder: ty::DebruijnIndex,
1033 }
1034
1035 #[cfg(target_arch = "x86_64")]
1036 static_assert_size!(PredicateInner<'_>, 40);
1037
1038 #[derive(Clone, Copy, Lift)]
1039 pub struct Predicate<'tcx> {
1040     inner: &'tcx PredicateInner<'tcx>,
1041 }
1042
1043 impl<'tcx> PartialEq for Predicate<'tcx> {
1044     fn eq(&self, other: &Self) -> bool {
1045         // `self.kind` is always interned.
1046         ptr::eq(self.inner, other.inner)
1047     }
1048 }
1049
1050 impl Hash for Predicate<'_> {
1051     fn hash<H: Hasher>(&self, s: &mut H) {
1052         (self.inner as *const PredicateInner<'_>).hash(s)
1053     }
1054 }
1055
1056 impl<'tcx> Eq for Predicate<'tcx> {}
1057
1058 impl<'tcx> Predicate<'tcx> {
1059     /// Gets the inner `Binder<PredicateKind<'tcx>>`.
1060     pub fn kind(self) -> Binder<PredicateKind<'tcx>> {
1061         self.inner.kind
1062     }
1063 }
1064
1065 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Predicate<'tcx> {
1066     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
1067         let PredicateInner {
1068             ref kind,
1069
1070             // The other fields just provide fast access to information that is
1071             // also contained in `kind`, so no need to hash them.
1072             flags: _,
1073             outer_exclusive_binder: _,
1074         } = self.inner;
1075
1076         kind.hash_stable(hcx, hasher);
1077     }
1078 }
1079
1080 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
1081 #[derive(HashStable, TypeFoldable)]
1082 pub enum PredicateKind<'tcx> {
1083     /// Corresponds to `where Foo: Bar<A, B, C>`. `Foo` here would be
1084     /// the `Self` type of the trait reference and `A`, `B`, and `C`
1085     /// would be the type parameters.
1086     ///
1087     /// A trait predicate will have `Constness::Const` if it originates
1088     /// from a bound on a `const fn` without the `?const` opt-out (e.g.,
1089     /// `const fn foobar<Foo: Bar>() {}`).
1090     Trait(TraitPredicate<'tcx>, Constness),
1091
1092     /// `where 'a: 'b`
1093     RegionOutlives(RegionOutlivesPredicate<'tcx>),
1094
1095     /// `where T: 'a`
1096     TypeOutlives(TypeOutlivesPredicate<'tcx>),
1097
1098     /// `where <T as TraitRef>::Name == X`, approximately.
1099     /// See the `ProjectionPredicate` struct for details.
1100     Projection(ProjectionPredicate<'tcx>),
1101
1102     /// No syntax: `T` well-formed.
1103     WellFormed(GenericArg<'tcx>),
1104
1105     /// Trait must be object-safe.
1106     ObjectSafe(DefId),
1107
1108     /// No direct syntax. May be thought of as `where T: FnFoo<...>`
1109     /// for some substitutions `...` and `T` being a closure type.
1110     /// Satisfied (or refuted) once we know the closure's kind.
1111     ClosureKind(DefId, SubstsRef<'tcx>, ClosureKind),
1112
1113     /// `T1 <: T2`
1114     Subtype(SubtypePredicate<'tcx>),
1115
1116     /// Constant initializer must evaluate successfully.
1117     ConstEvaluatable(ty::WithOptConstParam<DefId>, SubstsRef<'tcx>),
1118
1119     /// Constants must be equal. The first component is the const that is expected.
1120     ConstEquate(&'tcx Const<'tcx>, &'tcx Const<'tcx>),
1121
1122     /// Represents a type found in the environment that we can use for implied bounds.
1123     ///
1124     /// Only used for Chalk.
1125     TypeWellFormedFromEnv(Ty<'tcx>),
1126 }
1127
1128 /// The crate outlives map is computed during typeck and contains the
1129 /// outlives of every item in the local crate. You should not use it
1130 /// directly, because to do so will make your pass dependent on the
1131 /// HIR of every item in the local crate. Instead, use
1132 /// `tcx.inferred_outlives_of()` to get the outlives for a *particular*
1133 /// item.
1134 #[derive(HashStable, Debug)]
1135 pub struct CratePredicatesMap<'tcx> {
1136     /// For each struct with outlive bounds, maps to a vector of the
1137     /// predicate of its outlive bounds. If an item has no outlives
1138     /// bounds, it will have no entry.
1139     pub predicates: FxHashMap<DefId, &'tcx [(Predicate<'tcx>, Span)]>,
1140 }
1141
1142 impl<'tcx> Predicate<'tcx> {
1143     /// Performs a substitution suitable for going from a
1144     /// poly-trait-ref to supertraits that must hold if that
1145     /// poly-trait-ref holds. This is slightly different from a normal
1146     /// substitution in terms of what happens with bound regions. See
1147     /// lengthy comment below for details.
1148     pub fn subst_supertrait(
1149         self,
1150         tcx: TyCtxt<'tcx>,
1151         trait_ref: &ty::PolyTraitRef<'tcx>,
1152     ) -> Predicate<'tcx> {
1153         // The interaction between HRTB and supertraits is not entirely
1154         // obvious. Let me walk you (and myself) through an example.
1155         //
1156         // Let's start with an easy case. Consider two traits:
1157         //
1158         //     trait Foo<'a>: Bar<'a,'a> { }
1159         //     trait Bar<'b,'c> { }
1160         //
1161         // Now, if we have a trait reference `for<'x> T: Foo<'x>`, then
1162         // we can deduce that `for<'x> T: Bar<'x,'x>`. Basically, if we
1163         // knew that `Foo<'x>` (for any 'x) then we also know that
1164         // `Bar<'x,'x>` (for any 'x). This more-or-less falls out from
1165         // normal substitution.
1166         //
1167         // In terms of why this is sound, the idea is that whenever there
1168         // is an impl of `T:Foo<'a>`, it must show that `T:Bar<'a,'a>`
1169         // holds.  So if there is an impl of `T:Foo<'a>` that applies to
1170         // all `'a`, then we must know that `T:Bar<'a,'a>` holds for all
1171         // `'a`.
1172         //
1173         // Another example to be careful of is this:
1174         //
1175         //     trait Foo1<'a>: for<'b> Bar1<'a,'b> { }
1176         //     trait Bar1<'b,'c> { }
1177         //
1178         // Here, if we have `for<'x> T: Foo1<'x>`, then what do we know?
1179         // The answer is that we know `for<'x,'b> T: Bar1<'x,'b>`. The
1180         // reason is similar to the previous example: any impl of
1181         // `T:Foo1<'x>` must show that `for<'b> T: Bar1<'x, 'b>`.  So
1182         // basically we would want to collapse the bound lifetimes from
1183         // the input (`trait_ref`) and the supertraits.
1184         //
1185         // To achieve this in practice is fairly straightforward. Let's
1186         // consider the more complicated scenario:
1187         //
1188         // - We start out with `for<'x> T: Foo1<'x>`. In this case, `'x`
1189         //   has a De Bruijn index of 1. We want to produce `for<'x,'b> T: Bar1<'x,'b>`,
1190         //   where both `'x` and `'b` would have a DB index of 1.
1191         //   The substitution from the input trait-ref is therefore going to be
1192         //   `'a => 'x` (where `'x` has a DB index of 1).
1193         // - The super-trait-ref is `for<'b> Bar1<'a,'b>`, where `'a` is an
1194         //   early-bound parameter and `'b' is a late-bound parameter with a
1195         //   DB index of 1.
1196         // - If we replace `'a` with `'x` from the input, it too will have
1197         //   a DB index of 1, and thus we'll have `for<'x,'b> Bar1<'x,'b>`
1198         //   just as we wanted.
1199         //
1200         // There is only one catch. If we just apply the substitution `'a
1201         // => 'x` to `for<'b> Bar1<'a,'b>`, the substitution code will
1202         // adjust the DB index because we substituting into a binder (it
1203         // tries to be so smart...) resulting in `for<'x> for<'b>
1204         // Bar1<'x,'b>` (we have no syntax for this, so use your
1205         // imagination). Basically the 'x will have DB index of 2 and 'b
1206         // will have DB index of 1. Not quite what we want. So we apply
1207         // the substitution to the *contents* of the trait reference,
1208         // rather than the trait reference itself (put another way, the
1209         // substitution code expects equal binding levels in the values
1210         // from the substitution and the value being substituted into, and
1211         // this trick achieves that).
1212         let substs = trait_ref.skip_binder().substs;
1213         let pred = self.kind().skip_binder();
1214         let new = pred.subst(tcx, substs);
1215         tcx.reuse_or_mk_predicate(self, ty::Binder::bind(new))
1216     }
1217 }
1218
1219 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
1220 #[derive(HashStable, TypeFoldable)]
1221 pub struct TraitPredicate<'tcx> {
1222     pub trait_ref: TraitRef<'tcx>,
1223 }
1224
1225 pub type PolyTraitPredicate<'tcx> = ty::Binder<TraitPredicate<'tcx>>;
1226
1227 impl<'tcx> TraitPredicate<'tcx> {
1228     pub fn def_id(self) -> DefId {
1229         self.trait_ref.def_id
1230     }
1231
1232     pub fn self_ty(self) -> Ty<'tcx> {
1233         self.trait_ref.self_ty()
1234     }
1235 }
1236
1237 impl<'tcx> PolyTraitPredicate<'tcx> {
1238     pub fn def_id(self) -> DefId {
1239         // Ok to skip binder since trait `DefId` does not care about regions.
1240         self.skip_binder().def_id()
1241     }
1242
1243     pub fn self_ty(self) -> ty::Binder<Ty<'tcx>> {
1244         self.map_bound(|trait_ref| trait_ref.self_ty())
1245     }
1246 }
1247
1248 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
1249 #[derive(HashStable, TypeFoldable)]
1250 pub struct OutlivesPredicate<A, B>(pub A, pub B); // `A: B`
1251 pub type RegionOutlivesPredicate<'tcx> = OutlivesPredicate<ty::Region<'tcx>, ty::Region<'tcx>>;
1252 pub type TypeOutlivesPredicate<'tcx> = OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>;
1253 pub type PolyRegionOutlivesPredicate<'tcx> = ty::Binder<RegionOutlivesPredicate<'tcx>>;
1254 pub type PolyTypeOutlivesPredicate<'tcx> = ty::Binder<TypeOutlivesPredicate<'tcx>>;
1255
1256 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
1257 #[derive(HashStable, TypeFoldable)]
1258 pub struct SubtypePredicate<'tcx> {
1259     pub a_is_expected: bool,
1260     pub a: Ty<'tcx>,
1261     pub b: Ty<'tcx>,
1262 }
1263 pub type PolySubtypePredicate<'tcx> = ty::Binder<SubtypePredicate<'tcx>>;
1264
1265 /// This kind of predicate has no *direct* correspondent in the
1266 /// syntax, but it roughly corresponds to the syntactic forms:
1267 ///
1268 /// 1. `T: TraitRef<..., Item = Type>`
1269 /// 2. `<T as TraitRef<...>>::Item == Type` (NYI)
1270 ///
1271 /// In particular, form #1 is "desugared" to the combination of a
1272 /// normal trait predicate (`T: TraitRef<...>`) and one of these
1273 /// predicates. Form #2 is a broader form in that it also permits
1274 /// equality between arbitrary types. Processing an instance of
1275 /// Form #2 eventually yields one of these `ProjectionPredicate`
1276 /// instances to normalize the LHS.
1277 #[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
1278 #[derive(HashStable, TypeFoldable)]
1279 pub struct ProjectionPredicate<'tcx> {
1280     pub projection_ty: ProjectionTy<'tcx>,
1281     pub ty: Ty<'tcx>,
1282 }
1283
1284 pub type PolyProjectionPredicate<'tcx> = Binder<ProjectionPredicate<'tcx>>;
1285
1286 impl<'tcx> PolyProjectionPredicate<'tcx> {
1287     /// Returns the `DefId` of the associated item being projected.
1288     pub fn item_def_id(&self) -> DefId {
1289         self.skip_binder().projection_ty.item_def_id
1290     }
1291
1292     /// Returns the `DefId` of the trait of the associated item being projected.
1293     #[inline]
1294     pub fn trait_def_id(&self, tcx: TyCtxt<'tcx>) -> DefId {
1295         self.skip_binder().projection_ty.trait_def_id(tcx)
1296     }
1297
1298     #[inline]
1299     pub fn projection_self_ty(&self) -> Binder<Ty<'tcx>> {
1300         self.map_bound(|predicate| predicate.projection_ty.self_ty())
1301     }
1302
1303     /// Get the [PolyTraitRef] required for this projection to be well formed.
1304     /// Note that for generic associated types the predicates of the associated
1305     /// type also need to be checked.
1306     #[inline]
1307     pub fn required_poly_trait_ref(&self, tcx: TyCtxt<'tcx>) -> PolyTraitRef<'tcx> {
1308         // Note: unlike with `TraitRef::to_poly_trait_ref()`,
1309         // `self.0.trait_ref` is permitted to have escaping regions.
1310         // This is because here `self` has a `Binder` and so does our
1311         // return value, so we are preserving the number of binding
1312         // levels.
1313         self.map_bound(|predicate| predicate.projection_ty.trait_ref(tcx))
1314     }
1315
1316     pub fn ty(&self) -> Binder<Ty<'tcx>> {
1317         self.map_bound(|predicate| predicate.ty)
1318     }
1319
1320     /// The `DefId` of the `TraitItem` for the associated type.
1321     ///
1322     /// Note that this is not the `DefId` of the `TraitRef` containing this
1323     /// associated type, which is in `tcx.associated_item(projection_def_id()).container`.
1324     pub fn projection_def_id(&self) -> DefId {
1325         // Ok to skip binder since trait `DefId` does not care about regions.
1326         self.skip_binder().projection_ty.item_def_id
1327     }
1328 }
1329
1330 pub trait ToPolyTraitRef<'tcx> {
1331     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
1332 }
1333
1334 impl<'tcx> ToPolyTraitRef<'tcx> for TraitRef<'tcx> {
1335     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
1336         ty::Binder::dummy(*self)
1337     }
1338 }
1339
1340 impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
1341     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
1342         self.map_bound_ref(|trait_pred| trait_pred.trait_ref)
1343     }
1344 }
1345
1346 pub trait ToPredicate<'tcx> {
1347     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx>;
1348 }
1349
1350 impl ToPredicate<'tcx> for Binder<PredicateKind<'tcx>> {
1351     #[inline(always)]
1352     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1353         tcx.mk_predicate(self)
1354     }
1355 }
1356
1357 impl ToPredicate<'tcx> for PredicateKind<'tcx> {
1358     #[inline(always)]
1359     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1360         tcx.mk_predicate(Binder::dummy(self))
1361     }
1362 }
1363
1364 impl<'tcx> ToPredicate<'tcx> for ConstnessAnd<TraitRef<'tcx>> {
1365     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1366         PredicateKind::Trait(ty::TraitPredicate { trait_ref: self.value }, self.constness)
1367             .to_predicate(tcx)
1368     }
1369 }
1370
1371 impl<'tcx> ToPredicate<'tcx> for ConstnessAnd<PolyTraitRef<'tcx>> {
1372     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1373         ConstnessAnd {
1374             value: self.value.map_bound(|trait_ref| ty::TraitPredicate { trait_ref }),
1375             constness: self.constness,
1376         }
1377         .to_predicate(tcx)
1378     }
1379 }
1380
1381 impl<'tcx> ToPredicate<'tcx> for ConstnessAnd<PolyTraitPredicate<'tcx>> {
1382     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1383         self.value.map_bound(|value| PredicateKind::Trait(value, self.constness)).to_predicate(tcx)
1384     }
1385 }
1386
1387 impl<'tcx> ToPredicate<'tcx> for PolyRegionOutlivesPredicate<'tcx> {
1388     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1389         self.map_bound(PredicateKind::RegionOutlives).to_predicate(tcx)
1390     }
1391 }
1392
1393 impl<'tcx> ToPredicate<'tcx> for PolyTypeOutlivesPredicate<'tcx> {
1394     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1395         self.map_bound(PredicateKind::TypeOutlives).to_predicate(tcx)
1396     }
1397 }
1398
1399 impl<'tcx> ToPredicate<'tcx> for PolyProjectionPredicate<'tcx> {
1400     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1401         self.map_bound(PredicateKind::Projection).to_predicate(tcx)
1402     }
1403 }
1404
1405 impl<'tcx> Predicate<'tcx> {
1406     pub fn to_opt_poly_trait_ref(self) -> Option<ConstnessAnd<PolyTraitRef<'tcx>>> {
1407         let predicate = self.kind();
1408         match predicate.skip_binder() {
1409             PredicateKind::Trait(t, constness) => {
1410                 Some(ConstnessAnd { constness, value: predicate.rebind(t.trait_ref) })
1411             }
1412             PredicateKind::Projection(..)
1413             | PredicateKind::Subtype(..)
1414             | PredicateKind::RegionOutlives(..)
1415             | PredicateKind::WellFormed(..)
1416             | PredicateKind::ObjectSafe(..)
1417             | PredicateKind::ClosureKind(..)
1418             | PredicateKind::TypeOutlives(..)
1419             | PredicateKind::ConstEvaluatable(..)
1420             | PredicateKind::ConstEquate(..)
1421             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1422         }
1423     }
1424
1425     pub fn to_opt_type_outlives(self) -> Option<PolyTypeOutlivesPredicate<'tcx>> {
1426         let predicate = self.kind();
1427         match predicate.skip_binder() {
1428             PredicateKind::TypeOutlives(data) => Some(predicate.rebind(data)),
1429             PredicateKind::Trait(..)
1430             | PredicateKind::Projection(..)
1431             | PredicateKind::Subtype(..)
1432             | PredicateKind::RegionOutlives(..)
1433             | PredicateKind::WellFormed(..)
1434             | PredicateKind::ObjectSafe(..)
1435             | PredicateKind::ClosureKind(..)
1436             | PredicateKind::ConstEvaluatable(..)
1437             | PredicateKind::ConstEquate(..)
1438             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1439         }
1440     }
1441 }
1442
1443 /// Represents the bounds declared on a particular set of type
1444 /// parameters. Should eventually be generalized into a flag list of
1445 /// where-clauses. You can obtain a `InstantiatedPredicates` list from a
1446 /// `GenericPredicates` by using the `instantiate` method. Note that this method
1447 /// reflects an important semantic invariant of `InstantiatedPredicates`: while
1448 /// the `GenericPredicates` are expressed in terms of the bound type
1449 /// parameters of the impl/trait/whatever, an `InstantiatedPredicates` instance
1450 /// represented a set of bounds for some particular instantiation,
1451 /// meaning that the generic parameters have been substituted with
1452 /// their values.
1453 ///
1454 /// Example:
1455 ///
1456 ///     struct Foo<T, U: Bar<T>> { ... }
1457 ///
1458 /// Here, the `GenericPredicates` for `Foo` would contain a list of bounds like
1459 /// `[[], [U:Bar<T>]]`. Now if there were some particular reference
1460 /// like `Foo<isize,usize>`, then the `InstantiatedPredicates` would be `[[],
1461 /// [usize:Bar<isize>]]`.
1462 #[derive(Clone, Debug, TypeFoldable)]
1463 pub struct InstantiatedPredicates<'tcx> {
1464     pub predicates: Vec<Predicate<'tcx>>,
1465     pub spans: Vec<Span>,
1466 }
1467
1468 impl<'tcx> InstantiatedPredicates<'tcx> {
1469     pub fn empty() -> InstantiatedPredicates<'tcx> {
1470         InstantiatedPredicates { predicates: vec![], spans: vec![] }
1471     }
1472
1473     pub fn is_empty(&self) -> bool {
1474         self.predicates.is_empty()
1475     }
1476 }
1477
1478 rustc_index::newtype_index! {
1479     /// "Universes" are used during type- and trait-checking in the
1480     /// presence of `for<..>` binders to control what sets of names are
1481     /// visible. Universes are arranged into a tree: the root universe
1482     /// contains names that are always visible. Each child then adds a new
1483     /// set of names that are visible, in addition to those of its parent.
1484     /// We say that the child universe "extends" the parent universe with
1485     /// new names.
1486     ///
1487     /// To make this more concrete, consider this program:
1488     ///
1489     /// ```
1490     /// struct Foo { }
1491     /// fn bar<T>(x: T) {
1492     ///   let y: for<'a> fn(&'a u8, Foo) = ...;
1493     /// }
1494     /// ```
1495     ///
1496     /// The struct name `Foo` is in the root universe U0. But the type
1497     /// parameter `T`, introduced on `bar`, is in an extended universe U1
1498     /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside
1499     /// of `bar`, we cannot name `T`. Then, within the type of `y`, the
1500     /// region `'a` is in a universe U2 that extends U1, because we can
1501     /// name it inside the fn type but not outside.
1502     ///
1503     /// Universes are used to do type- and trait-checking around these
1504     /// "forall" binders (also called **universal quantification**). The
1505     /// idea is that when, in the body of `bar`, we refer to `T` as a
1506     /// type, we aren't referring to any type in particular, but rather a
1507     /// kind of "fresh" type that is distinct from all other types we have
1508     /// actually declared. This is called a **placeholder** type, and we
1509     /// use universes to talk about this. In other words, a type name in
1510     /// universe 0 always corresponds to some "ground" type that the user
1511     /// declared, but a type name in a non-zero universe is a placeholder
1512     /// type -- an idealized representative of "types in general" that we
1513     /// use for checking generic functions.
1514     pub struct UniverseIndex {
1515         derive [HashStable]
1516         DEBUG_FORMAT = "U{}",
1517     }
1518 }
1519
1520 impl UniverseIndex {
1521     pub const ROOT: UniverseIndex = UniverseIndex::from_u32(0);
1522
1523     /// Returns the "next" universe index in order -- this new index
1524     /// is considered to extend all previous universes. This
1525     /// corresponds to entering a `forall` quantifier. So, for
1526     /// example, suppose we have this type in universe `U`:
1527     ///
1528     /// ```
1529     /// for<'a> fn(&'a u32)
1530     /// ```
1531     ///
1532     /// Once we "enter" into this `for<'a>` quantifier, we are in a
1533     /// new universe that extends `U` -- in this new universe, we can
1534     /// name the region `'a`, but that region was not nameable from
1535     /// `U` because it was not in scope there.
1536     pub fn next_universe(self) -> UniverseIndex {
1537         UniverseIndex::from_u32(self.private.checked_add(1).unwrap())
1538     }
1539
1540     /// Returns `true` if `self` can name a name from `other` -- in other words,
1541     /// if the set of names in `self` is a superset of those in
1542     /// `other` (`self >= other`).
1543     pub fn can_name(self, other: UniverseIndex) -> bool {
1544         self.private >= other.private
1545     }
1546
1547     /// Returns `true` if `self` cannot name some names from `other` -- in other
1548     /// words, if the set of names in `self` is a strict subset of
1549     /// those in `other` (`self < other`).
1550     pub fn cannot_name(self, other: UniverseIndex) -> bool {
1551         self.private < other.private
1552     }
1553 }
1554
1555 /// The "placeholder index" fully defines a placeholder region, type, or const. Placeholders are
1556 /// identified by both a universe, as well as a name residing within that universe. Distinct bound
1557 /// regions/types/consts within the same universe simply have an unknown relationship to one
1558 /// another.
1559 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable, PartialOrd, Ord)]
1560 pub struct Placeholder<T> {
1561     pub universe: UniverseIndex,
1562     pub name: T,
1563 }
1564
1565 impl<'a, T> HashStable<StableHashingContext<'a>> for Placeholder<T>
1566 where
1567     T: HashStable<StableHashingContext<'a>>,
1568 {
1569     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
1570         self.universe.hash_stable(hcx, hasher);
1571         self.name.hash_stable(hcx, hasher);
1572     }
1573 }
1574
1575 pub type PlaceholderRegion = Placeholder<BoundRegionKind>;
1576
1577 pub type PlaceholderType = Placeholder<BoundVar>;
1578
1579 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable)]
1580 #[derive(TyEncodable, TyDecodable, PartialOrd, Ord)]
1581 pub struct BoundConst<'tcx> {
1582     pub var: BoundVar,
1583     pub ty: Ty<'tcx>,
1584 }
1585
1586 pub type PlaceholderConst<'tcx> = Placeholder<BoundConst<'tcx>>;
1587
1588 /// A `DefId` which, in case it is a const argument, is potentially bundled with
1589 /// the `DefId` of the generic parameter it instantiates.
1590 ///
1591 /// This is used to avoid calls to `type_of` for const arguments during typeck
1592 /// which cause cycle errors.
1593 ///
1594 /// ```rust
1595 /// struct A;
1596 /// impl A {
1597 ///     fn foo<const N: usize>(&self) -> [u8; N] { [0; N] }
1598 ///     //           ^ const parameter
1599 /// }
1600 /// struct B;
1601 /// impl B {
1602 ///     fn foo<const M: u8>(&self) -> usize { 42 }
1603 ///     //           ^ const parameter
1604 /// }
1605 ///
1606 /// fn main() {
1607 ///     let a = A;
1608 ///     let _b = a.foo::<{ 3 + 7 }>();
1609 ///     //               ^^^^^^^^^ const argument
1610 /// }
1611 /// ```
1612 ///
1613 /// Let's look at the call `a.foo::<{ 3 + 7 }>()` here. We do not know
1614 /// which `foo` is used until we know the type of `a`.
1615 ///
1616 /// We only know the type of `a` once we are inside of `typeck(main)`.
1617 /// We also end up normalizing the type of `_b` during `typeck(main)` which
1618 /// requires us to evaluate the const argument.
1619 ///
1620 /// To evaluate that const argument we need to know its type,
1621 /// which we would get using `type_of(const_arg)`. This requires us to
1622 /// resolve `foo` as it can be either `usize` or `u8` in this example.
1623 /// However, resolving `foo` once again requires `typeck(main)` to get the type of `a`,
1624 /// which results in a cycle.
1625 ///
1626 /// In short we must not call `type_of(const_arg)` during `typeck(main)`.
1627 ///
1628 /// When first creating the `ty::Const` of the const argument inside of `typeck` we have
1629 /// already resolved `foo` so we know which const parameter this argument instantiates.
1630 /// This means that we also know the expected result of `type_of(const_arg)` even if we
1631 /// aren't allowed to call that query: it is equal to `type_of(const_param)` which is
1632 /// trivial to compute.
1633 ///
1634 /// If we now want to use that constant in a place which potentionally needs its type
1635 /// we also pass the type of its `const_param`. This is the point of `WithOptConstParam`,
1636 /// except that instead of a `Ty` we bundle the `DefId` of the const parameter.
1637 /// Meaning that we need to use `type_of(const_param_did)` if `const_param_did` is `Some`
1638 /// to get the type of `did`.
1639 #[derive(Copy, Clone, Debug, TypeFoldable, Lift, TyEncodable, TyDecodable)]
1640 #[derive(PartialEq, Eq, PartialOrd, Ord)]
1641 #[derive(Hash, HashStable)]
1642 pub struct WithOptConstParam<T> {
1643     pub did: T,
1644     /// The `DefId` of the corresponding generic parameter in case `did` is
1645     /// a const argument.
1646     ///
1647     /// Note that even if `did` is a const argument, this may still be `None`.
1648     /// All queries taking `WithOptConstParam` start by calling `tcx.opt_const_param_of(def.did)`
1649     /// to potentially update `param_did` in the case it is `None`.
1650     pub const_param_did: Option<DefId>,
1651 }
1652
1653 impl<T> WithOptConstParam<T> {
1654     /// Creates a new `WithOptConstParam` setting `const_param_did` to `None`.
1655     #[inline(always)]
1656     pub fn unknown(did: T) -> WithOptConstParam<T> {
1657         WithOptConstParam { did, const_param_did: None }
1658     }
1659 }
1660
1661 impl WithOptConstParam<LocalDefId> {
1662     /// Returns `Some((did, param_did))` if `def_id` is a const argument,
1663     /// `None` otherwise.
1664     #[inline(always)]
1665     pub fn try_lookup(did: LocalDefId, tcx: TyCtxt<'_>) -> Option<(LocalDefId, DefId)> {
1666         tcx.opt_const_param_of(did).map(|param_did| (did, param_did))
1667     }
1668
1669     /// In case `self` is unknown but `self.did` is a const argument, this returns
1670     /// a `WithOptConstParam` with the correct `const_param_did`.
1671     #[inline(always)]
1672     pub fn try_upgrade(self, tcx: TyCtxt<'_>) -> Option<WithOptConstParam<LocalDefId>> {
1673         if self.const_param_did.is_none() {
1674             if let const_param_did @ Some(_) = tcx.opt_const_param_of(self.did) {
1675                 return Some(WithOptConstParam { did: self.did, const_param_did });
1676             }
1677         }
1678
1679         None
1680     }
1681
1682     pub fn to_global(self) -> WithOptConstParam<DefId> {
1683         WithOptConstParam { did: self.did.to_def_id(), const_param_did: self.const_param_did }
1684     }
1685
1686     pub fn def_id_for_type_of(self) -> DefId {
1687         if let Some(did) = self.const_param_did { did } else { self.did.to_def_id() }
1688     }
1689 }
1690
1691 impl WithOptConstParam<DefId> {
1692     pub fn as_local(self) -> Option<WithOptConstParam<LocalDefId>> {
1693         self.did
1694             .as_local()
1695             .map(|did| WithOptConstParam { did, const_param_did: self.const_param_did })
1696     }
1697
1698     pub fn as_const_arg(self) -> Option<(LocalDefId, DefId)> {
1699         if let Some(param_did) = self.const_param_did {
1700             if let Some(did) = self.did.as_local() {
1701                 return Some((did, param_did));
1702             }
1703         }
1704
1705         None
1706     }
1707
1708     pub fn expect_local(self) -> WithOptConstParam<LocalDefId> {
1709         self.as_local().unwrap()
1710     }
1711
1712     pub fn is_local(self) -> bool {
1713         self.did.is_local()
1714     }
1715
1716     pub fn def_id_for_type_of(self) -> DefId {
1717         self.const_param_did.unwrap_or(self.did)
1718     }
1719 }
1720
1721 /// When type checking, we use the `ParamEnv` to track
1722 /// details about the set of where-clauses that are in scope at this
1723 /// particular point.
1724 #[derive(Copy, Clone, Hash, PartialEq, Eq)]
1725 pub struct ParamEnv<'tcx> {
1726     /// This packs both caller bounds and the reveal enum into one pointer.
1727     ///
1728     /// Caller bounds are `Obligation`s that the caller must satisfy. This is
1729     /// basically the set of bounds on the in-scope type parameters, translated
1730     /// into `Obligation`s, and elaborated and normalized.
1731     ///
1732     /// Use the `caller_bounds()` method to access.
1733     ///
1734     /// Typically, this is `Reveal::UserFacing`, but during codegen we
1735     /// want `Reveal::All`.
1736     ///
1737     /// Note: This is packed, use the reveal() method to access it.
1738     packed: CopyTaggedPtr<&'tcx List<Predicate<'tcx>>, traits::Reveal, true>,
1739 }
1740
1741 unsafe impl rustc_data_structures::tagged_ptr::Tag for traits::Reveal {
1742     const BITS: usize = 1;
1743     fn into_usize(self) -> usize {
1744         match self {
1745             traits::Reveal::UserFacing => 0,
1746             traits::Reveal::All => 1,
1747         }
1748     }
1749     unsafe fn from_usize(ptr: usize) -> Self {
1750         match ptr {
1751             0 => traits::Reveal::UserFacing,
1752             1 => traits::Reveal::All,
1753             _ => std::hint::unreachable_unchecked(),
1754         }
1755     }
1756 }
1757
1758 impl<'tcx> fmt::Debug for ParamEnv<'tcx> {
1759     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1760         f.debug_struct("ParamEnv")
1761             .field("caller_bounds", &self.caller_bounds())
1762             .field("reveal", &self.reveal())
1763             .finish()
1764     }
1765 }
1766
1767 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for ParamEnv<'tcx> {
1768     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
1769         self.caller_bounds().hash_stable(hcx, hasher);
1770         self.reveal().hash_stable(hcx, hasher);
1771     }
1772 }
1773
1774 impl<'tcx> TypeFoldable<'tcx> for ParamEnv<'tcx> {
1775     fn super_fold_with<F: ty::fold::TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1776         ParamEnv::new(self.caller_bounds().fold_with(folder), self.reveal().fold_with(folder))
1777     }
1778
1779     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1780         self.caller_bounds().visit_with(visitor)?;
1781         self.reveal().visit_with(visitor)
1782     }
1783 }
1784
1785 impl<'tcx> ParamEnv<'tcx> {
1786     /// Construct a trait environment suitable for contexts where
1787     /// there are no where-clauses in scope. Hidden types (like `impl
1788     /// Trait`) are left hidden, so this is suitable for ordinary
1789     /// type-checking.
1790     #[inline]
1791     pub fn empty() -> Self {
1792         Self::new(List::empty(), Reveal::UserFacing)
1793     }
1794
1795     #[inline]
1796     pub fn caller_bounds(self) -> &'tcx List<Predicate<'tcx>> {
1797         self.packed.pointer()
1798     }
1799
1800     #[inline]
1801     pub fn reveal(self) -> traits::Reveal {
1802         self.packed.tag()
1803     }
1804
1805     /// Construct a trait environment with no where-clauses in scope
1806     /// where the values of all `impl Trait` and other hidden types
1807     /// are revealed. This is suitable for monomorphized, post-typeck
1808     /// environments like codegen or doing optimizations.
1809     ///
1810     /// N.B., if you want to have predicates in scope, use `ParamEnv::new`,
1811     /// or invoke `param_env.with_reveal_all()`.
1812     #[inline]
1813     pub fn reveal_all() -> Self {
1814         Self::new(List::empty(), Reveal::All)
1815     }
1816
1817     /// Construct a trait environment with the given set of predicates.
1818     #[inline]
1819     pub fn new(caller_bounds: &'tcx List<Predicate<'tcx>>, reveal: Reveal) -> Self {
1820         ty::ParamEnv { packed: CopyTaggedPtr::new(caller_bounds, reveal) }
1821     }
1822
1823     pub fn with_user_facing(mut self) -> Self {
1824         self.packed.set_tag(Reveal::UserFacing);
1825         self
1826     }
1827
1828     /// Returns a new parameter environment with the same clauses, but
1829     /// which "reveals" the true results of projections in all cases
1830     /// (even for associated types that are specializable). This is
1831     /// the desired behavior during codegen and certain other special
1832     /// contexts; normally though we want to use `Reveal::UserFacing`,
1833     /// which is the default.
1834     /// All opaque types in the caller_bounds of the `ParamEnv`
1835     /// will be normalized to their underlying types.
1836     /// See PR #65989 and issue #65918 for more details
1837     pub fn with_reveal_all_normalized(self, tcx: TyCtxt<'tcx>) -> Self {
1838         if self.packed.tag() == traits::Reveal::All {
1839             return self;
1840         }
1841
1842         ParamEnv::new(tcx.normalize_opaque_types(self.caller_bounds()), Reveal::All)
1843     }
1844
1845     /// Returns this same environment but with no caller bounds.
1846     pub fn without_caller_bounds(self) -> Self {
1847         Self::new(List::empty(), self.reveal())
1848     }
1849
1850     /// Creates a suitable environment in which to perform trait
1851     /// queries on the given value. When type-checking, this is simply
1852     /// the pair of the environment plus value. But when reveal is set to
1853     /// All, then if `value` does not reference any type parameters, we will
1854     /// pair it with the empty environment. This improves caching and is generally
1855     /// invisible.
1856     ///
1857     /// N.B., we preserve the environment when type-checking because it
1858     /// is possible for the user to have wacky where-clauses like
1859     /// `where Box<u32>: Copy`, which are clearly never
1860     /// satisfiable. We generally want to behave as if they were true,
1861     /// although the surrounding function is never reachable.
1862     pub fn and<T: TypeFoldable<'tcx>>(self, value: T) -> ParamEnvAnd<'tcx, T> {
1863         match self.reveal() {
1864             Reveal::UserFacing => ParamEnvAnd { param_env: self, value },
1865
1866             Reveal::All => {
1867                 if value.is_global() {
1868                     ParamEnvAnd { param_env: self.without_caller_bounds(), value }
1869                 } else {
1870                     ParamEnvAnd { param_env: self, value }
1871                 }
1872             }
1873         }
1874     }
1875 }
1876
1877 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TypeFoldable)]
1878 pub struct ConstnessAnd<T> {
1879     pub constness: Constness,
1880     pub value: T,
1881 }
1882
1883 // FIXME(ecstaticmorse): Audit all occurrences of `without_const().to_predicate(tcx)` to ensure that
1884 // the constness of trait bounds is being propagated correctly.
1885 pub trait WithConstness: Sized {
1886     #[inline]
1887     fn with_constness(self, constness: Constness) -> ConstnessAnd<Self> {
1888         ConstnessAnd { constness, value: self }
1889     }
1890
1891     #[inline]
1892     fn with_const(self) -> ConstnessAnd<Self> {
1893         self.with_constness(Constness::Const)
1894     }
1895
1896     #[inline]
1897     fn without_const(self) -> ConstnessAnd<Self> {
1898         self.with_constness(Constness::NotConst)
1899     }
1900 }
1901
1902 impl<T> WithConstness for T {}
1903
1904 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TypeFoldable)]
1905 pub struct ParamEnvAnd<'tcx, T> {
1906     pub param_env: ParamEnv<'tcx>,
1907     pub value: T,
1908 }
1909
1910 impl<'tcx, T> ParamEnvAnd<'tcx, T> {
1911     pub fn into_parts(self) -> (ParamEnv<'tcx>, T) {
1912         (self.param_env, self.value)
1913     }
1914 }
1915
1916 impl<'a, 'tcx, T> HashStable<StableHashingContext<'a>> for ParamEnvAnd<'tcx, T>
1917 where
1918     T: HashStable<StableHashingContext<'a>>,
1919 {
1920     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
1921         let ParamEnvAnd { ref param_env, ref value } = *self;
1922
1923         param_env.hash_stable(hcx, hasher);
1924         value.hash_stable(hcx, hasher);
1925     }
1926 }
1927
1928 #[derive(Copy, Clone, Debug, HashStable)]
1929 pub struct Destructor {
1930     /// The `DefId` of the destructor method
1931     pub did: DefId,
1932 }
1933
1934 bitflags! {
1935     #[derive(HashStable)]
1936     pub struct AdtFlags: u32 {
1937         const NO_ADT_FLAGS        = 0;
1938         /// Indicates whether the ADT is an enum.
1939         const IS_ENUM             = 1 << 0;
1940         /// Indicates whether the ADT is a union.
1941         const IS_UNION            = 1 << 1;
1942         /// Indicates whether the ADT is a struct.
1943         const IS_STRUCT           = 1 << 2;
1944         /// Indicates whether the ADT is a struct and has a constructor.
1945         const HAS_CTOR            = 1 << 3;
1946         /// Indicates whether the type is `PhantomData`.
1947         const IS_PHANTOM_DATA     = 1 << 4;
1948         /// Indicates whether the type has a `#[fundamental]` attribute.
1949         const IS_FUNDAMENTAL      = 1 << 5;
1950         /// Indicates whether the type is `Box`.
1951         const IS_BOX              = 1 << 6;
1952         /// Indicates whether the type is `ManuallyDrop`.
1953         const IS_MANUALLY_DROP    = 1 << 7;
1954         /// Indicates whether the variant list of this ADT is `#[non_exhaustive]`.
1955         /// (i.e., this flag is never set unless this ADT is an enum).
1956         const IS_VARIANT_LIST_NON_EXHAUSTIVE = 1 << 8;
1957     }
1958 }
1959
1960 bitflags! {
1961     #[derive(HashStable)]
1962     pub struct VariantFlags: u32 {
1963         const NO_VARIANT_FLAGS        = 0;
1964         /// Indicates whether the field list of this variant is `#[non_exhaustive]`.
1965         const IS_FIELD_LIST_NON_EXHAUSTIVE = 1 << 0;
1966         /// Indicates whether this variant was obtained as part of recovering from
1967         /// a syntactic error. May be incomplete or bogus.
1968         const IS_RECOVERED = 1 << 1;
1969     }
1970 }
1971
1972 /// Definition of a variant -- a struct's fields or a enum variant.
1973 #[derive(Debug, HashStable)]
1974 pub struct VariantDef {
1975     /// `DefId` that identifies the variant itself.
1976     /// If this variant belongs to a struct or union, then this is a copy of its `DefId`.
1977     pub def_id: DefId,
1978     /// `DefId` that identifies the variant's constructor.
1979     /// If this variant is a struct variant, then this is `None`.
1980     pub ctor_def_id: Option<DefId>,
1981     /// Variant or struct name.
1982     #[stable_hasher(project(name))]
1983     pub ident: Ident,
1984     /// Discriminant of this variant.
1985     pub discr: VariantDiscr,
1986     /// Fields of this variant.
1987     pub fields: Vec<FieldDef>,
1988     /// Type of constructor of variant.
1989     pub ctor_kind: CtorKind,
1990     /// Flags of the variant (e.g. is field list non-exhaustive)?
1991     flags: VariantFlags,
1992 }
1993
1994 impl VariantDef {
1995     /// Creates a new `VariantDef`.
1996     ///
1997     /// `variant_did` is the `DefId` that identifies the enum variant (if this `VariantDef`
1998     /// represents an enum variant).
1999     ///
2000     /// `ctor_did` is the `DefId` that identifies the constructor of unit or
2001     /// tuple-variants/structs. If this is a `struct`-variant then this should be `None`.
2002     ///
2003     /// `parent_did` is the `DefId` of the `AdtDef` representing the enum or struct that
2004     /// owns this variant. It is used for checking if a struct has `#[non_exhaustive]` w/out having
2005     /// to go through the redirect of checking the ctor's attributes - but compiling a small crate
2006     /// requires loading the `AdtDef`s for all the structs in the universe (e.g., coherence for any
2007     /// built-in trait), and we do not want to load attributes twice.
2008     ///
2009     /// If someone speeds up attribute loading to not be a performance concern, they can
2010     /// remove this hack and use the constructor `DefId` everywhere.
2011     pub fn new(
2012         ident: Ident,
2013         variant_did: Option<DefId>,
2014         ctor_def_id: Option<DefId>,
2015         discr: VariantDiscr,
2016         fields: Vec<FieldDef>,
2017         ctor_kind: CtorKind,
2018         adt_kind: AdtKind,
2019         parent_did: DefId,
2020         recovered: bool,
2021         is_field_list_non_exhaustive: bool,
2022     ) -> Self {
2023         debug!(
2024             "VariantDef::new(ident = {:?}, variant_did = {:?}, ctor_def_id = {:?}, discr = {:?},
2025              fields = {:?}, ctor_kind = {:?}, adt_kind = {:?}, parent_did = {:?})",
2026             ident, variant_did, ctor_def_id, discr, fields, ctor_kind, adt_kind, parent_did,
2027         );
2028
2029         let mut flags = VariantFlags::NO_VARIANT_FLAGS;
2030         if is_field_list_non_exhaustive {
2031             flags |= VariantFlags::IS_FIELD_LIST_NON_EXHAUSTIVE;
2032         }
2033
2034         if recovered {
2035             flags |= VariantFlags::IS_RECOVERED;
2036         }
2037
2038         VariantDef {
2039             def_id: variant_did.unwrap_or(parent_did),
2040             ctor_def_id,
2041             ident,
2042             discr,
2043             fields,
2044             ctor_kind,
2045             flags,
2046         }
2047     }
2048
2049     /// Is this field list non-exhaustive?
2050     #[inline]
2051     pub fn is_field_list_non_exhaustive(&self) -> bool {
2052         self.flags.intersects(VariantFlags::IS_FIELD_LIST_NON_EXHAUSTIVE)
2053     }
2054
2055     /// Was this variant obtained as part of recovering from a syntactic error?
2056     #[inline]
2057     pub fn is_recovered(&self) -> bool {
2058         self.flags.intersects(VariantFlags::IS_RECOVERED)
2059     }
2060 }
2061
2062 #[derive(Copy, Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
2063 pub enum VariantDiscr {
2064     /// Explicit value for this variant, i.e., `X = 123`.
2065     /// The `DefId` corresponds to the embedded constant.
2066     Explicit(DefId),
2067
2068     /// The previous variant's discriminant plus one.
2069     /// For efficiency reasons, the distance from the
2070     /// last `Explicit` discriminant is being stored,
2071     /// or `0` for the first variant, if it has none.
2072     Relative(u32),
2073 }
2074
2075 #[derive(Debug, HashStable)]
2076 pub struct FieldDef {
2077     pub did: DefId,
2078     #[stable_hasher(project(name))]
2079     pub ident: Ident,
2080     pub vis: Visibility,
2081 }
2082
2083 /// The definition of a user-defined type, e.g., a `struct`, `enum`, or `union`.
2084 ///
2085 /// These are all interned (by `alloc_adt_def`) into the global arena.
2086 ///
2087 /// The initialism *ADT* stands for an [*algebraic data type (ADT)*][adt].
2088 /// This is slightly wrong because `union`s are not ADTs.
2089 /// Moreover, Rust only allows recursive data types through indirection.
2090 ///
2091 /// [adt]: https://en.wikipedia.org/wiki/Algebraic_data_type
2092 pub struct AdtDef {
2093     /// The `DefId` of the struct, enum or union item.
2094     pub did: DefId,
2095     /// Variants of the ADT. If this is a struct or union, then there will be a single variant.
2096     pub variants: IndexVec<VariantIdx, VariantDef>,
2097     /// Flags of the ADT (e.g., is this a struct? is this non-exhaustive?).
2098     flags: AdtFlags,
2099     /// Repr options provided by the user.
2100     pub repr: ReprOptions,
2101 }
2102
2103 impl PartialOrd for AdtDef {
2104     fn partial_cmp(&self, other: &AdtDef) -> Option<Ordering> {
2105         Some(self.cmp(&other))
2106     }
2107 }
2108
2109 /// There should be only one AdtDef for each `did`, therefore
2110 /// it is fine to implement `Ord` only based on `did`.
2111 impl Ord for AdtDef {
2112     fn cmp(&self, other: &AdtDef) -> Ordering {
2113         self.did.cmp(&other.did)
2114     }
2115 }
2116
2117 impl PartialEq for AdtDef {
2118     // `AdtDef`s are always interned, and this is part of `TyS` equality.
2119     #[inline]
2120     fn eq(&self, other: &Self) -> bool {
2121         ptr::eq(self, other)
2122     }
2123 }
2124
2125 impl Eq for AdtDef {}
2126
2127 impl Hash for AdtDef {
2128     #[inline]
2129     fn hash<H: Hasher>(&self, s: &mut H) {
2130         (self as *const AdtDef).hash(s)
2131     }
2132 }
2133
2134 impl<S: Encoder> Encodable<S> for AdtDef {
2135     fn encode(&self, s: &mut S) -> Result<(), S::Error> {
2136         self.did.encode(s)
2137     }
2138 }
2139
2140 impl<'a> HashStable<StableHashingContext<'a>> for AdtDef {
2141     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
2142         thread_local! {
2143             static CACHE: RefCell<FxHashMap<usize, Fingerprint>> = Default::default();
2144         }
2145
2146         let hash: Fingerprint = CACHE.with(|cache| {
2147             let addr = self as *const AdtDef as usize;
2148             *cache.borrow_mut().entry(addr).or_insert_with(|| {
2149                 let ty::AdtDef { did, ref variants, ref flags, ref repr } = *self;
2150
2151                 let mut hasher = StableHasher::new();
2152                 did.hash_stable(hcx, &mut hasher);
2153                 variants.hash_stable(hcx, &mut hasher);
2154                 flags.hash_stable(hcx, &mut hasher);
2155                 repr.hash_stable(hcx, &mut hasher);
2156
2157                 hasher.finish()
2158             })
2159         });
2160
2161         hash.hash_stable(hcx, hasher);
2162     }
2163 }
2164
2165 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
2166 pub enum AdtKind {
2167     Struct,
2168     Union,
2169     Enum,
2170 }
2171
2172 impl Into<DataTypeKind> for AdtKind {
2173     fn into(self) -> DataTypeKind {
2174         match self {
2175             AdtKind::Struct => DataTypeKind::Struct,
2176             AdtKind::Union => DataTypeKind::Union,
2177             AdtKind::Enum => DataTypeKind::Enum,
2178         }
2179     }
2180 }
2181
2182 bitflags! {
2183     #[derive(TyEncodable, TyDecodable, Default, HashStable)]
2184     pub struct ReprFlags: u8 {
2185         const IS_C               = 1 << 0;
2186         const IS_SIMD            = 1 << 1;
2187         const IS_TRANSPARENT     = 1 << 2;
2188         // Internal only for now. If true, don't reorder fields.
2189         const IS_LINEAR          = 1 << 3;
2190         // If true, don't expose any niche to type's context.
2191         const HIDE_NICHE         = 1 << 4;
2192         // Any of these flags being set prevent field reordering optimisation.
2193         const IS_UNOPTIMISABLE   = ReprFlags::IS_C.bits |
2194                                    ReprFlags::IS_SIMD.bits |
2195                                    ReprFlags::IS_LINEAR.bits;
2196     }
2197 }
2198
2199 /// Represents the repr options provided by the user,
2200 #[derive(Copy, Clone, Debug, Eq, PartialEq, TyEncodable, TyDecodable, Default, HashStable)]
2201 pub struct ReprOptions {
2202     pub int: Option<attr::IntType>,
2203     pub align: Option<Align>,
2204     pub pack: Option<Align>,
2205     pub flags: ReprFlags,
2206 }
2207
2208 impl ReprOptions {
2209     pub fn new(tcx: TyCtxt<'_>, did: DefId) -> ReprOptions {
2210         let mut flags = ReprFlags::empty();
2211         let mut size = None;
2212         let mut max_align: Option<Align> = None;
2213         let mut min_pack: Option<Align> = None;
2214         for attr in tcx.get_attrs(did).iter() {
2215             for r in attr::find_repr_attrs(&tcx.sess, attr) {
2216                 flags.insert(match r {
2217                     attr::ReprC => ReprFlags::IS_C,
2218                     attr::ReprPacked(pack) => {
2219                         let pack = Align::from_bytes(pack as u64).unwrap();
2220                         min_pack = Some(if let Some(min_pack) = min_pack {
2221                             min_pack.min(pack)
2222                         } else {
2223                             pack
2224                         });
2225                         ReprFlags::empty()
2226                     }
2227                     attr::ReprTransparent => ReprFlags::IS_TRANSPARENT,
2228                     attr::ReprNoNiche => ReprFlags::HIDE_NICHE,
2229                     attr::ReprSimd => ReprFlags::IS_SIMD,
2230                     attr::ReprInt(i) => {
2231                         size = Some(i);
2232                         ReprFlags::empty()
2233                     }
2234                     attr::ReprAlign(align) => {
2235                         max_align = max_align.max(Some(Align::from_bytes(align as u64).unwrap()));
2236                         ReprFlags::empty()
2237                     }
2238                 });
2239             }
2240         }
2241
2242         // This is here instead of layout because the choice must make it into metadata.
2243         if !tcx.consider_optimizing(|| format!("Reorder fields of {:?}", tcx.def_path_str(did))) {
2244             flags.insert(ReprFlags::IS_LINEAR);
2245         }
2246         ReprOptions { int: size, align: max_align, pack: min_pack, flags }
2247     }
2248
2249     #[inline]
2250     pub fn simd(&self) -> bool {
2251         self.flags.contains(ReprFlags::IS_SIMD)
2252     }
2253     #[inline]
2254     pub fn c(&self) -> bool {
2255         self.flags.contains(ReprFlags::IS_C)
2256     }
2257     #[inline]
2258     pub fn packed(&self) -> bool {
2259         self.pack.is_some()
2260     }
2261     #[inline]
2262     pub fn transparent(&self) -> bool {
2263         self.flags.contains(ReprFlags::IS_TRANSPARENT)
2264     }
2265     #[inline]
2266     pub fn linear(&self) -> bool {
2267         self.flags.contains(ReprFlags::IS_LINEAR)
2268     }
2269     #[inline]
2270     pub fn hide_niche(&self) -> bool {
2271         self.flags.contains(ReprFlags::HIDE_NICHE)
2272     }
2273
2274     /// Returns the discriminant type, given these `repr` options.
2275     /// This must only be called on enums!
2276     pub fn discr_type(&self) -> attr::IntType {
2277         self.int.unwrap_or(attr::SignedInt(ast::IntTy::Isize))
2278     }
2279
2280     /// Returns `true` if this `#[repr()]` should inhabit "smart enum
2281     /// layout" optimizations, such as representing `Foo<&T>` as a
2282     /// single pointer.
2283     pub fn inhibit_enum_layout_opt(&self) -> bool {
2284         self.c() || self.int.is_some()
2285     }
2286
2287     /// Returns `true` if this `#[repr()]` should inhibit struct field reordering
2288     /// optimizations, such as with `repr(C)`, `repr(packed(1))`, or `repr(<int>)`.
2289     pub fn inhibit_struct_field_reordering_opt(&self) -> bool {
2290         if let Some(pack) = self.pack {
2291             if pack.bytes() == 1 {
2292                 return true;
2293             }
2294         }
2295         self.flags.intersects(ReprFlags::IS_UNOPTIMISABLE) || self.int.is_some()
2296     }
2297
2298     /// Returns `true` if this `#[repr()]` should inhibit union ABI optimisations.
2299     pub fn inhibit_union_abi_opt(&self) -> bool {
2300         self.c()
2301     }
2302 }
2303
2304 impl<'tcx> AdtDef {
2305     /// Creates a new `AdtDef`.
2306     fn new(
2307         tcx: TyCtxt<'_>,
2308         did: DefId,
2309         kind: AdtKind,
2310         variants: IndexVec<VariantIdx, VariantDef>,
2311         repr: ReprOptions,
2312     ) -> Self {
2313         debug!("AdtDef::new({:?}, {:?}, {:?}, {:?})", did, kind, variants, repr);
2314         let mut flags = AdtFlags::NO_ADT_FLAGS;
2315
2316         if kind == AdtKind::Enum && tcx.has_attr(did, sym::non_exhaustive) {
2317             debug!("found non-exhaustive variant list for {:?}", did);
2318             flags = flags | AdtFlags::IS_VARIANT_LIST_NON_EXHAUSTIVE;
2319         }
2320
2321         flags |= match kind {
2322             AdtKind::Enum => AdtFlags::IS_ENUM,
2323             AdtKind::Union => AdtFlags::IS_UNION,
2324             AdtKind::Struct => AdtFlags::IS_STRUCT,
2325         };
2326
2327         if kind == AdtKind::Struct && variants[VariantIdx::new(0)].ctor_def_id.is_some() {
2328             flags |= AdtFlags::HAS_CTOR;
2329         }
2330
2331         let attrs = tcx.get_attrs(did);
2332         if tcx.sess.contains_name(&attrs, sym::fundamental) {
2333             flags |= AdtFlags::IS_FUNDAMENTAL;
2334         }
2335         if Some(did) == tcx.lang_items().phantom_data() {
2336             flags |= AdtFlags::IS_PHANTOM_DATA;
2337         }
2338         if Some(did) == tcx.lang_items().owned_box() {
2339             flags |= AdtFlags::IS_BOX;
2340         }
2341         if Some(did) == tcx.lang_items().manually_drop() {
2342             flags |= AdtFlags::IS_MANUALLY_DROP;
2343         }
2344
2345         AdtDef { did, variants, flags, repr }
2346     }
2347
2348     /// Returns `true` if this is a struct.
2349     #[inline]
2350     pub fn is_struct(&self) -> bool {
2351         self.flags.contains(AdtFlags::IS_STRUCT)
2352     }
2353
2354     /// Returns `true` if this is a union.
2355     #[inline]
2356     pub fn is_union(&self) -> bool {
2357         self.flags.contains(AdtFlags::IS_UNION)
2358     }
2359
2360     /// Returns `true` if this is a enum.
2361     #[inline]
2362     pub fn is_enum(&self) -> bool {
2363         self.flags.contains(AdtFlags::IS_ENUM)
2364     }
2365
2366     /// Returns `true` if the variant list of this ADT is `#[non_exhaustive]`.
2367     #[inline]
2368     pub fn is_variant_list_non_exhaustive(&self) -> bool {
2369         self.flags.contains(AdtFlags::IS_VARIANT_LIST_NON_EXHAUSTIVE)
2370     }
2371
2372     /// Returns the kind of the ADT.
2373     #[inline]
2374     pub fn adt_kind(&self) -> AdtKind {
2375         if self.is_enum() {
2376             AdtKind::Enum
2377         } else if self.is_union() {
2378             AdtKind::Union
2379         } else {
2380             AdtKind::Struct
2381         }
2382     }
2383
2384     /// Returns a description of this abstract data type.
2385     pub fn descr(&self) -> &'static str {
2386         match self.adt_kind() {
2387             AdtKind::Struct => "struct",
2388             AdtKind::Union => "union",
2389             AdtKind::Enum => "enum",
2390         }
2391     }
2392
2393     /// Returns a description of a variant of this abstract data type.
2394     #[inline]
2395     pub fn variant_descr(&self) -> &'static str {
2396         match self.adt_kind() {
2397             AdtKind::Struct => "struct",
2398             AdtKind::Union => "union",
2399             AdtKind::Enum => "variant",
2400         }
2401     }
2402
2403     /// If this function returns `true`, it implies that `is_struct` must return `true`.
2404     #[inline]
2405     pub fn has_ctor(&self) -> bool {
2406         self.flags.contains(AdtFlags::HAS_CTOR)
2407     }
2408
2409     /// Returns `true` if this type is `#[fundamental]` for the purposes
2410     /// of coherence checking.
2411     #[inline]
2412     pub fn is_fundamental(&self) -> bool {
2413         self.flags.contains(AdtFlags::IS_FUNDAMENTAL)
2414     }
2415
2416     /// Returns `true` if this is `PhantomData<T>`.
2417     #[inline]
2418     pub fn is_phantom_data(&self) -> bool {
2419         self.flags.contains(AdtFlags::IS_PHANTOM_DATA)
2420     }
2421
2422     /// Returns `true` if this is Box<T>.
2423     #[inline]
2424     pub fn is_box(&self) -> bool {
2425         self.flags.contains(AdtFlags::IS_BOX)
2426     }
2427
2428     /// Returns `true` if this is `ManuallyDrop<T>`.
2429     #[inline]
2430     pub fn is_manually_drop(&self) -> bool {
2431         self.flags.contains(AdtFlags::IS_MANUALLY_DROP)
2432     }
2433
2434     /// Returns `true` if this type has a destructor.
2435     pub fn has_dtor(&self, tcx: TyCtxt<'tcx>) -> bool {
2436         self.destructor(tcx).is_some()
2437     }
2438
2439     /// Asserts this is a struct or union and returns its unique variant.
2440     pub fn non_enum_variant(&self) -> &VariantDef {
2441         assert!(self.is_struct() || self.is_union());
2442         &self.variants[VariantIdx::new(0)]
2443     }
2444
2445     #[inline]
2446     pub fn predicates(&self, tcx: TyCtxt<'tcx>) -> GenericPredicates<'tcx> {
2447         tcx.predicates_of(self.did)
2448     }
2449
2450     /// Returns an iterator over all fields contained
2451     /// by this ADT.
2452     #[inline]
2453     pub fn all_fields(&self) -> impl Iterator<Item = &FieldDef> + Clone {
2454         self.variants.iter().flat_map(|v| v.fields.iter())
2455     }
2456
2457     /// Whether the ADT lacks fields. Note that this includes uninhabited enums,
2458     /// e.g., `enum Void {}` is considered payload free as well.
2459     pub fn is_payloadfree(&self) -> bool {
2460         self.variants.iter().all(|v| v.fields.is_empty())
2461     }
2462
2463     /// Return a `VariantDef` given a variant id.
2464     pub fn variant_with_id(&self, vid: DefId) -> &VariantDef {
2465         self.variants.iter().find(|v| v.def_id == vid).expect("variant_with_id: unknown variant")
2466     }
2467
2468     /// Return a `VariantDef` given a constructor id.
2469     pub fn variant_with_ctor_id(&self, cid: DefId) -> &VariantDef {
2470         self.variants
2471             .iter()
2472             .find(|v| v.ctor_def_id == Some(cid))
2473             .expect("variant_with_ctor_id: unknown variant")
2474     }
2475
2476     /// Return the index of `VariantDef` given a variant id.
2477     pub fn variant_index_with_id(&self, vid: DefId) -> VariantIdx {
2478         self.variants
2479             .iter_enumerated()
2480             .find(|(_, v)| v.def_id == vid)
2481             .expect("variant_index_with_id: unknown variant")
2482             .0
2483     }
2484
2485     /// Return the index of `VariantDef` given a constructor id.
2486     pub fn variant_index_with_ctor_id(&self, cid: DefId) -> VariantIdx {
2487         self.variants
2488             .iter_enumerated()
2489             .find(|(_, v)| v.ctor_def_id == Some(cid))
2490             .expect("variant_index_with_ctor_id: unknown variant")
2491             .0
2492     }
2493
2494     pub fn variant_of_res(&self, res: Res) -> &VariantDef {
2495         match res {
2496             Res::Def(DefKind::Variant, vid) => self.variant_with_id(vid),
2497             Res::Def(DefKind::Ctor(..), cid) => self.variant_with_ctor_id(cid),
2498             Res::Def(DefKind::Struct, _)
2499             | Res::Def(DefKind::Union, _)
2500             | Res::Def(DefKind::TyAlias, _)
2501             | Res::Def(DefKind::AssocTy, _)
2502             | Res::SelfTy(..)
2503             | Res::SelfCtor(..) => self.non_enum_variant(),
2504             _ => bug!("unexpected res {:?} in variant_of_res", res),
2505         }
2506     }
2507
2508     #[inline]
2509     pub fn eval_explicit_discr(&self, tcx: TyCtxt<'tcx>, expr_did: DefId) -> Option<Discr<'tcx>> {
2510         assert!(self.is_enum());
2511         let param_env = tcx.param_env(expr_did);
2512         let repr_type = self.repr.discr_type();
2513         match tcx.const_eval_poly(expr_did) {
2514             Ok(val) => {
2515                 let ty = repr_type.to_ty(tcx);
2516                 if let Some(b) = val.try_to_bits_for_ty(tcx, param_env, ty) {
2517                     trace!("discriminants: {} ({:?})", b, repr_type);
2518                     Some(Discr { val: b, ty })
2519                 } else {
2520                     info!("invalid enum discriminant: {:#?}", val);
2521                     crate::mir::interpret::struct_error(
2522                         tcx.at(tcx.def_span(expr_did)),
2523                         "constant evaluation of enum discriminant resulted in non-integer",
2524                     )
2525                     .emit();
2526                     None
2527                 }
2528             }
2529             Err(err) => {
2530                 let msg = match err {
2531                     ErrorHandled::Reported(ErrorReported) | ErrorHandled::Linted => {
2532                         "enum discriminant evaluation failed"
2533                     }
2534                     ErrorHandled::TooGeneric => "enum discriminant depends on generics",
2535                 };
2536                 tcx.sess.delay_span_bug(tcx.def_span(expr_did), msg);
2537                 None
2538             }
2539         }
2540     }
2541
2542     #[inline]
2543     pub fn discriminants(
2544         &'tcx self,
2545         tcx: TyCtxt<'tcx>,
2546     ) -> impl Iterator<Item = (VariantIdx, Discr<'tcx>)> + Captures<'tcx> {
2547         assert!(self.is_enum());
2548         let repr_type = self.repr.discr_type();
2549         let initial = repr_type.initial_discriminant(tcx);
2550         let mut prev_discr = None::<Discr<'tcx>>;
2551         self.variants.iter_enumerated().map(move |(i, v)| {
2552             let mut discr = prev_discr.map_or(initial, |d| d.wrap_incr(tcx));
2553             if let VariantDiscr::Explicit(expr_did) = v.discr {
2554                 if let Some(new_discr) = self.eval_explicit_discr(tcx, expr_did) {
2555                     discr = new_discr;
2556                 }
2557             }
2558             prev_discr = Some(discr);
2559
2560             (i, discr)
2561         })
2562     }
2563
2564     #[inline]
2565     pub fn variant_range(&self) -> Range<VariantIdx> {
2566         VariantIdx::new(0)..VariantIdx::new(self.variants.len())
2567     }
2568
2569     /// Computes the discriminant value used by a specific variant.
2570     /// Unlike `discriminants`, this is (amortized) constant-time,
2571     /// only doing at most one query for evaluating an explicit
2572     /// discriminant (the last one before the requested variant),
2573     /// assuming there are no constant-evaluation errors there.
2574     #[inline]
2575     pub fn discriminant_for_variant(
2576         &self,
2577         tcx: TyCtxt<'tcx>,
2578         variant_index: VariantIdx,
2579     ) -> Discr<'tcx> {
2580         assert!(self.is_enum());
2581         let (val, offset) = self.discriminant_def_for_variant(variant_index);
2582         let explicit_value = val
2583             .and_then(|expr_did| self.eval_explicit_discr(tcx, expr_did))
2584             .unwrap_or_else(|| self.repr.discr_type().initial_discriminant(tcx));
2585         explicit_value.checked_add(tcx, offset as u128).0
2586     }
2587
2588     /// Yields a `DefId` for the discriminant and an offset to add to it
2589     /// Alternatively, if there is no explicit discriminant, returns the
2590     /// inferred discriminant directly.
2591     pub fn discriminant_def_for_variant(&self, variant_index: VariantIdx) -> (Option<DefId>, u32) {
2592         assert!(!self.variants.is_empty());
2593         let mut explicit_index = variant_index.as_u32();
2594         let expr_did;
2595         loop {
2596             match self.variants[VariantIdx::from_u32(explicit_index)].discr {
2597                 ty::VariantDiscr::Relative(0) => {
2598                     expr_did = None;
2599                     break;
2600                 }
2601                 ty::VariantDiscr::Relative(distance) => {
2602                     explicit_index -= distance;
2603                 }
2604                 ty::VariantDiscr::Explicit(did) => {
2605                     expr_did = Some(did);
2606                     break;
2607                 }
2608             }
2609         }
2610         (expr_did, variant_index.as_u32() - explicit_index)
2611     }
2612
2613     pub fn destructor(&self, tcx: TyCtxt<'tcx>) -> Option<Destructor> {
2614         tcx.adt_destructor(self.did)
2615     }
2616
2617     /// Returns a list of types such that `Self: Sized` if and only
2618     /// if that type is `Sized`, or `TyErr` if this type is recursive.
2619     ///
2620     /// Oddly enough, checking that the sized-constraint is `Sized` is
2621     /// actually more expressive than checking all members:
2622     /// the `Sized` trait is inductive, so an associated type that references
2623     /// `Self` would prevent its containing ADT from being `Sized`.
2624     ///
2625     /// Due to normalization being eager, this applies even if
2626     /// the associated type is behind a pointer (e.g., issue #31299).
2627     pub fn sized_constraint(&self, tcx: TyCtxt<'tcx>) -> &'tcx [Ty<'tcx>] {
2628         tcx.adt_sized_constraint(self.did).0
2629     }
2630 }
2631
2632 impl<'tcx> FieldDef {
2633     /// Returns the type of this field. The `subst` is typically obtained
2634     /// via the second field of `TyKind::AdtDef`.
2635     pub fn ty(&self, tcx: TyCtxt<'tcx>, subst: SubstsRef<'tcx>) -> Ty<'tcx> {
2636         tcx.type_of(self.did).subst(tcx, subst)
2637     }
2638 }
2639
2640 /// Represents the various closure traits in the language. This
2641 /// will determine the type of the environment (`self`, in the
2642 /// desugaring) argument that the closure expects.
2643 ///
2644 /// You can get the environment type of a closure using
2645 /// `tcx.closure_env_ty()`.
2646 #[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
2647 #[derive(HashStable)]
2648 pub enum ClosureKind {
2649     // Warning: Ordering is significant here! The ordering is chosen
2650     // because the trait Fn is a subtrait of FnMut and so in turn, and
2651     // hence we order it so that Fn < FnMut < FnOnce.
2652     Fn,
2653     FnMut,
2654     FnOnce,
2655 }
2656
2657 impl<'tcx> ClosureKind {
2658     // This is the initial value used when doing upvar inference.
2659     pub const LATTICE_BOTTOM: ClosureKind = ClosureKind::Fn;
2660
2661     pub fn trait_did(&self, tcx: TyCtxt<'tcx>) -> DefId {
2662         match *self {
2663             ClosureKind::Fn => tcx.require_lang_item(LangItem::Fn, None),
2664             ClosureKind::FnMut => tcx.require_lang_item(LangItem::FnMut, None),
2665             ClosureKind::FnOnce => tcx.require_lang_item(LangItem::FnOnce, None),
2666         }
2667     }
2668
2669     /// Returns `true` if a type that impls this closure kind
2670     /// must also implement `other`.
2671     pub fn extends(self, other: ty::ClosureKind) -> bool {
2672         matches!(
2673             (self, other),
2674             (ClosureKind::Fn, ClosureKind::Fn)
2675                 | (ClosureKind::Fn, ClosureKind::FnMut)
2676                 | (ClosureKind::Fn, ClosureKind::FnOnce)
2677                 | (ClosureKind::FnMut, ClosureKind::FnMut)
2678                 | (ClosureKind::FnMut, ClosureKind::FnOnce)
2679                 | (ClosureKind::FnOnce, ClosureKind::FnOnce)
2680         )
2681     }
2682
2683     /// Returns the representative scalar type for this closure kind.
2684     /// See `TyS::to_opt_closure_kind` for more details.
2685     pub fn to_ty(self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
2686         match self {
2687             ty::ClosureKind::Fn => tcx.types.i8,
2688             ty::ClosureKind::FnMut => tcx.types.i16,
2689             ty::ClosureKind::FnOnce => tcx.types.i32,
2690         }
2691     }
2692 }
2693
2694 impl BorrowKind {
2695     pub fn from_mutbl(m: hir::Mutability) -> BorrowKind {
2696         match m {
2697             hir::Mutability::Mut => MutBorrow,
2698             hir::Mutability::Not => ImmBorrow,
2699         }
2700     }
2701
2702     /// Returns a mutability `m` such that an `&m T` pointer could be used to obtain this borrow
2703     /// kind. Because borrow kinds are richer than mutabilities, we sometimes have to pick a
2704     /// mutability that is stronger than necessary so that it at least *would permit* the borrow in
2705     /// question.
2706     pub fn to_mutbl_lossy(self) -> hir::Mutability {
2707         match self {
2708             MutBorrow => hir::Mutability::Mut,
2709             ImmBorrow => hir::Mutability::Not,
2710
2711             // We have no type corresponding to a unique imm borrow, so
2712             // use `&mut`. It gives all the capabilities of an `&uniq`
2713             // and hence is a safe "over approximation".
2714             UniqueImmBorrow => hir::Mutability::Mut,
2715         }
2716     }
2717
2718     pub fn to_user_str(&self) -> &'static str {
2719         match *self {
2720             MutBorrow => "mutable",
2721             ImmBorrow => "immutable",
2722             UniqueImmBorrow => "uniquely immutable",
2723         }
2724     }
2725 }
2726
2727 pub type Attributes<'tcx> = &'tcx [ast::Attribute];
2728
2729 #[derive(Debug, PartialEq, Eq)]
2730 pub enum ImplOverlapKind {
2731     /// These impls are always allowed to overlap.
2732     Permitted {
2733         /// Whether or not the impl is permitted due to the trait being a `#[marker]` trait
2734         marker: bool,
2735     },
2736     /// These impls are allowed to overlap, but that raises
2737     /// an issue #33140 future-compatibility warning.
2738     ///
2739     /// Some background: in Rust 1.0, the trait-object types `Send + Sync` (today's
2740     /// `dyn Send + Sync`) and `Sync + Send` (now `dyn Sync + Send`) were different.
2741     ///
2742     /// The widely-used version 0.1.0 of the crate `traitobject` had accidentally relied
2743     /// that difference, making what reduces to the following set of impls:
2744     ///
2745     /// ```
2746     /// trait Trait {}
2747     /// impl Trait for dyn Send + Sync {}
2748     /// impl Trait for dyn Sync + Send {}
2749     /// ```
2750     ///
2751     /// Obviously, once we made these types be identical, that code causes a coherence
2752     /// error and a fairly big headache for us. However, luckily for us, the trait
2753     /// `Trait` used in this case is basically a marker trait, and therefore having
2754     /// overlapping impls for it is sound.
2755     ///
2756     /// To handle this, we basically regard the trait as a marker trait, with an additional
2757     /// future-compatibility warning. To avoid accidentally "stabilizing" this feature,
2758     /// it has the following restrictions:
2759     ///
2760     /// 1. The trait must indeed be a marker-like trait (i.e., no items), and must be
2761     /// positive impls.
2762     /// 2. The trait-ref of both impls must be equal.
2763     /// 3. The trait-ref of both impls must be a trait object type consisting only of
2764     /// marker traits.
2765     /// 4. Neither of the impls can have any where-clauses.
2766     ///
2767     /// Once `traitobject` 0.1.0 is no longer an active concern, this hack can be removed.
2768     Issue33140,
2769 }
2770
2771 impl<'tcx> TyCtxt<'tcx> {
2772     pub fn typeck_body(self, body: hir::BodyId) -> &'tcx TypeckResults<'tcx> {
2773         self.typeck(self.hir().body_owner_def_id(body))
2774     }
2775
2776     /// Returns an iterator of the `DefId`s for all body-owners in this
2777     /// crate. If you would prefer to iterate over the bodies
2778     /// themselves, you can do `self.hir().krate().body_ids.iter()`.
2779     pub fn body_owners(self) -> impl Iterator<Item = LocalDefId> + Captures<'tcx> + 'tcx {
2780         self.hir()
2781             .krate()
2782             .body_ids
2783             .iter()
2784             .map(move |&body_id| self.hir().body_owner_def_id(body_id))
2785     }
2786
2787     pub fn par_body_owners<F: Fn(LocalDefId) + sync::Sync + sync::Send>(self, f: F) {
2788         par_iter(&self.hir().krate().body_ids)
2789             .for_each(|&body_id| f(self.hir().body_owner_def_id(body_id)));
2790     }
2791
2792     pub fn provided_trait_methods(self, id: DefId) -> impl 'tcx + Iterator<Item = &'tcx AssocItem> {
2793         self.associated_items(id)
2794             .in_definition_order()
2795             .filter(|item| item.kind == AssocKind::Fn && item.defaultness.has_value())
2796     }
2797
2798     fn item_name_from_hir(self, def_id: DefId) -> Option<Ident> {
2799         self.hir().get_if_local(def_id).and_then(|node| node.ident())
2800     }
2801
2802     fn item_name_from_def_id(self, def_id: DefId) -> Option<Symbol> {
2803         if def_id.index == CRATE_DEF_INDEX {
2804             Some(self.original_crate_name(def_id.krate))
2805         } else {
2806             let def_key = self.def_key(def_id);
2807             match def_key.disambiguated_data.data {
2808                 // The name of a constructor is that of its parent.
2809                 rustc_hir::definitions::DefPathData::Ctor => self.item_name_from_def_id(DefId {
2810                     krate: def_id.krate,
2811                     index: def_key.parent.unwrap(),
2812                 }),
2813                 _ => def_key.disambiguated_data.data.get_opt_name(),
2814             }
2815         }
2816     }
2817
2818     /// Look up the name of an item across crates. This does not look at HIR.
2819     ///
2820     /// When possible, this function should be used for cross-crate lookups over
2821     /// [`opt_item_name`] to avoid invalidating the incremental cache. If you
2822     /// need to handle items without a name, or HIR items that will not be
2823     /// serialized cross-crate, or if you need the span of the item, use
2824     /// [`opt_item_name`] instead.
2825     ///
2826     /// [`opt_item_name`]: Self::opt_item_name
2827     pub fn item_name(self, id: DefId) -> Symbol {
2828         // Look at cross-crate items first to avoid invalidating the incremental cache
2829         // unless we have to.
2830         self.item_name_from_def_id(id).unwrap_or_else(|| {
2831             bug!("item_name: no name for {:?}", self.def_path(id));
2832         })
2833     }
2834
2835     /// Look up the name and span of an item or [`Node`].
2836     ///
2837     /// See [`item_name`][Self::item_name] for more information.
2838     pub fn opt_item_name(self, def_id: DefId) -> Option<Ident> {
2839         // Look at the HIR first so the span will be correct if this is a local item.
2840         self.item_name_from_hir(def_id)
2841             .or_else(|| self.item_name_from_def_id(def_id).map(Ident::with_dummy_span))
2842     }
2843
2844     pub fn opt_associated_item(self, def_id: DefId) -> Option<&'tcx AssocItem> {
2845         if let DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy = self.def_kind(def_id) {
2846             Some(self.associated_item(def_id))
2847         } else {
2848             None
2849         }
2850     }
2851
2852     pub fn field_index(self, hir_id: hir::HirId, typeck_results: &TypeckResults<'_>) -> usize {
2853         typeck_results.field_indices().get(hir_id).cloned().expect("no index for a field")
2854     }
2855
2856     pub fn find_field_index(self, ident: Ident, variant: &VariantDef) -> Option<usize> {
2857         variant.fields.iter().position(|field| self.hygienic_eq(ident, field.ident, variant.def_id))
2858     }
2859
2860     /// Returns `true` if the impls are the same polarity and the trait either
2861     /// has no items or is annotated `#[marker]` and prevents item overrides.
2862     pub fn impls_are_allowed_to_overlap(
2863         self,
2864         def_id1: DefId,
2865         def_id2: DefId,
2866     ) -> Option<ImplOverlapKind> {
2867         // If either trait impl references an error, they're allowed to overlap,
2868         // as one of them essentially doesn't exist.
2869         if self.impl_trait_ref(def_id1).map_or(false, |tr| tr.references_error())
2870             || self.impl_trait_ref(def_id2).map_or(false, |tr| tr.references_error())
2871         {
2872             return Some(ImplOverlapKind::Permitted { marker: false });
2873         }
2874
2875         match (self.impl_polarity(def_id1), self.impl_polarity(def_id2)) {
2876             (ImplPolarity::Reservation, _) | (_, ImplPolarity::Reservation) => {
2877                 // `#[rustc_reservation_impl]` impls don't overlap with anything
2878                 debug!(
2879                     "impls_are_allowed_to_overlap({:?}, {:?}) = Some(Permitted) (reservations)",
2880                     def_id1, def_id2
2881                 );
2882                 return Some(ImplOverlapKind::Permitted { marker: false });
2883             }
2884             (ImplPolarity::Positive, ImplPolarity::Negative)
2885             | (ImplPolarity::Negative, ImplPolarity::Positive) => {
2886                 // `impl AutoTrait for Type` + `impl !AutoTrait for Type`
2887                 debug!(
2888                     "impls_are_allowed_to_overlap({:?}, {:?}) - None (differing polarities)",
2889                     def_id1, def_id2
2890                 );
2891                 return None;
2892             }
2893             (ImplPolarity::Positive, ImplPolarity::Positive)
2894             | (ImplPolarity::Negative, ImplPolarity::Negative) => {}
2895         };
2896
2897         let is_marker_overlap = {
2898             let is_marker_impl = |def_id: DefId| -> bool {
2899                 let trait_ref = self.impl_trait_ref(def_id);
2900                 trait_ref.map_or(false, |tr| self.trait_def(tr.def_id).is_marker)
2901             };
2902             is_marker_impl(def_id1) && is_marker_impl(def_id2)
2903         };
2904
2905         if is_marker_overlap {
2906             debug!(
2907                 "impls_are_allowed_to_overlap({:?}, {:?}) = Some(Permitted) (marker overlap)",
2908                 def_id1, def_id2
2909             );
2910             Some(ImplOverlapKind::Permitted { marker: true })
2911         } else {
2912             if let Some(self_ty1) = self.issue33140_self_ty(def_id1) {
2913                 if let Some(self_ty2) = self.issue33140_self_ty(def_id2) {
2914                     if self_ty1 == self_ty2 {
2915                         debug!(
2916                             "impls_are_allowed_to_overlap({:?}, {:?}) - issue #33140 HACK",
2917                             def_id1, def_id2
2918                         );
2919                         return Some(ImplOverlapKind::Issue33140);
2920                     } else {
2921                         debug!(
2922                             "impls_are_allowed_to_overlap({:?}, {:?}) - found {:?} != {:?}",
2923                             def_id1, def_id2, self_ty1, self_ty2
2924                         );
2925                     }
2926                 }
2927             }
2928
2929             debug!("impls_are_allowed_to_overlap({:?}, {:?}) = None", def_id1, def_id2);
2930             None
2931         }
2932     }
2933
2934     /// Returns `ty::VariantDef` if `res` refers to a struct,
2935     /// or variant or their constructors, panics otherwise.
2936     pub fn expect_variant_res(self, res: Res) -> &'tcx VariantDef {
2937         match res {
2938             Res::Def(DefKind::Variant, did) => {
2939                 let enum_did = self.parent(did).unwrap();
2940                 self.adt_def(enum_did).variant_with_id(did)
2941             }
2942             Res::Def(DefKind::Struct | DefKind::Union, did) => self.adt_def(did).non_enum_variant(),
2943             Res::Def(DefKind::Ctor(CtorOf::Variant, ..), variant_ctor_did) => {
2944                 let variant_did = self.parent(variant_ctor_did).unwrap();
2945                 let enum_did = self.parent(variant_did).unwrap();
2946                 self.adt_def(enum_did).variant_with_ctor_id(variant_ctor_did)
2947             }
2948             Res::Def(DefKind::Ctor(CtorOf::Struct, ..), ctor_did) => {
2949                 let struct_did = self.parent(ctor_did).expect("struct ctor has no parent");
2950                 self.adt_def(struct_did).non_enum_variant()
2951             }
2952             _ => bug!("expect_variant_res used with unexpected res {:?}", res),
2953         }
2954     }
2955
2956     /// Returns the possibly-auto-generated MIR of a `(DefId, Subst)` pair.
2957     pub fn instance_mir(self, instance: ty::InstanceDef<'tcx>) -> &'tcx Body<'tcx> {
2958         match instance {
2959             ty::InstanceDef::Item(def) => match self.def_kind(def.did) {
2960                 DefKind::Const
2961                 | DefKind::Static
2962                 | DefKind::AssocConst
2963                 | DefKind::Ctor(..)
2964                 | DefKind::AnonConst => self.mir_for_ctfe_opt_const_arg(def),
2965                 // If the caller wants `mir_for_ctfe` of a function they should not be using
2966                 // `instance_mir`, so we'll assume const fn also wants the optimized version.
2967                 _ => self.optimized_mir_or_const_arg_mir(def),
2968             },
2969             ty::InstanceDef::VtableShim(..)
2970             | ty::InstanceDef::ReifyShim(..)
2971             | ty::InstanceDef::Intrinsic(..)
2972             | ty::InstanceDef::FnPtrShim(..)
2973             | ty::InstanceDef::Virtual(..)
2974             | ty::InstanceDef::ClosureOnceShim { .. }
2975             | ty::InstanceDef::DropGlue(..)
2976             | ty::InstanceDef::CloneShim(..) => self.mir_shims(instance),
2977         }
2978     }
2979
2980     /// Gets the attributes of a definition.
2981     pub fn get_attrs(self, did: DefId) -> Attributes<'tcx> {
2982         if let Some(did) = did.as_local() {
2983             self.hir().attrs(self.hir().local_def_id_to_hir_id(did))
2984         } else {
2985             self.item_attrs(did)
2986         }
2987     }
2988
2989     /// Determines whether an item is annotated with an attribute.
2990     pub fn has_attr(self, did: DefId, attr: Symbol) -> bool {
2991         self.sess.contains_name(&self.get_attrs(did), attr)
2992     }
2993
2994     /// Returns `true` if this is an `auto trait`.
2995     pub fn trait_is_auto(self, trait_def_id: DefId) -> bool {
2996         self.trait_def(trait_def_id).has_auto_impl
2997     }
2998
2999     /// Returns layout of a generator. Layout might be unavailable if the
3000     /// generator is tainted by errors.
3001     pub fn generator_layout(self, def_id: DefId) -> Option<&'tcx GeneratorLayout<'tcx>> {
3002         self.optimized_mir(def_id).generator_layout.as_ref()
3003     }
3004
3005     /// Given the `DefId` of an impl, returns the `DefId` of the trait it implements.
3006     /// If it implements no trait, returns `None`.
3007     pub fn trait_id_of_impl(self, def_id: DefId) -> Option<DefId> {
3008         self.impl_trait_ref(def_id).map(|tr| tr.def_id)
3009     }
3010
3011     /// If the given defid describes a method belonging to an impl, returns the
3012     /// `DefId` of the impl that the method belongs to; otherwise, returns `None`.
3013     pub fn impl_of_method(self, def_id: DefId) -> Option<DefId> {
3014         self.opt_associated_item(def_id).and_then(|trait_item| match trait_item.container {
3015             TraitContainer(_) => None,
3016             ImplContainer(def_id) => Some(def_id),
3017         })
3018     }
3019
3020     /// Looks up the span of `impl_did` if the impl is local; otherwise returns `Err`
3021     /// with the name of the crate containing the impl.
3022     pub fn span_of_impl(self, impl_did: DefId) -> Result<Span, Symbol> {
3023         if let Some(impl_did) = impl_did.as_local() {
3024             let hir_id = self.hir().local_def_id_to_hir_id(impl_did);
3025             Ok(self.hir().span(hir_id))
3026         } else {
3027             Err(self.crate_name(impl_did.krate))
3028         }
3029     }
3030
3031     /// Hygienically compares a use-site name (`use_name`) for a field or an associated item with
3032     /// its supposed definition name (`def_name`). The method also needs `DefId` of the supposed
3033     /// definition's parent/scope to perform comparison.
3034     pub fn hygienic_eq(self, use_name: Ident, def_name: Ident, def_parent_def_id: DefId) -> bool {
3035         // We could use `Ident::eq` here, but we deliberately don't. The name
3036         // comparison fails frequently, and we want to avoid the expensive
3037         // `normalize_to_macros_2_0()` calls required for the span comparison whenever possible.
3038         use_name.name == def_name.name
3039             && use_name
3040                 .span
3041                 .ctxt()
3042                 .hygienic_eq(def_name.span.ctxt(), self.expansion_that_defined(def_parent_def_id))
3043     }
3044
3045     pub fn expansion_that_defined(self, scope: DefId) -> ExpnId {
3046         match scope.as_local() {
3047             // Parsing and expansion aren't incremental, so we don't
3048             // need to go through a query for the same-crate case.
3049             Some(scope) => self.hir().definitions().expansion_that_defined(scope),
3050             None => self.expn_that_defined(scope),
3051         }
3052     }
3053
3054     pub fn adjust_ident(self, mut ident: Ident, scope: DefId) -> Ident {
3055         ident.span.normalize_to_macros_2_0_and_adjust(self.expansion_that_defined(scope));
3056         ident
3057     }
3058
3059     pub fn adjust_ident_and_get_scope(
3060         self,
3061         mut ident: Ident,
3062         scope: DefId,
3063         block: hir::HirId,
3064     ) -> (Ident, DefId) {
3065         let scope =
3066             match ident.span.normalize_to_macros_2_0_and_adjust(self.expansion_that_defined(scope))
3067             {
3068                 Some(actual_expansion) => {
3069                     self.hir().definitions().parent_module_of_macro_def(actual_expansion)
3070                 }
3071                 None => self.parent_module(block).to_def_id(),
3072             };
3073         (ident, scope)
3074     }
3075
3076     pub fn is_object_safe(self, key: DefId) -> bool {
3077         self.object_safety_violations(key).is_empty()
3078     }
3079 }
3080
3081 #[derive(Clone, HashStable, Debug)]
3082 pub struct AdtSizedConstraint<'tcx>(pub &'tcx [Ty<'tcx>]);
3083
3084 /// Yields the parent function's `DefId` if `def_id` is an `impl Trait` definition.
3085 pub fn is_impl_trait_defn(tcx: TyCtxt<'_>, def_id: DefId) -> Option<DefId> {
3086     if let Some(def_id) = def_id.as_local() {
3087         if let Node::Item(item) = tcx.hir().get(tcx.hir().local_def_id_to_hir_id(def_id)) {
3088             if let hir::ItemKind::OpaqueTy(ref opaque_ty) = item.kind {
3089                 return opaque_ty.impl_trait_fn;
3090             }
3091         }
3092     }
3093     None
3094 }
3095
3096 pub fn int_ty(ity: ast::IntTy) -> IntTy {
3097     match ity {
3098         ast::IntTy::Isize => IntTy::Isize,
3099         ast::IntTy::I8 => IntTy::I8,
3100         ast::IntTy::I16 => IntTy::I16,
3101         ast::IntTy::I32 => IntTy::I32,
3102         ast::IntTy::I64 => IntTy::I64,
3103         ast::IntTy::I128 => IntTy::I128,
3104     }
3105 }
3106
3107 pub fn uint_ty(uty: ast::UintTy) -> UintTy {
3108     match uty {
3109         ast::UintTy::Usize => UintTy::Usize,
3110         ast::UintTy::U8 => UintTy::U8,
3111         ast::UintTy::U16 => UintTy::U16,
3112         ast::UintTy::U32 => UintTy::U32,
3113         ast::UintTy::U64 => UintTy::U64,
3114         ast::UintTy::U128 => UintTy::U128,
3115     }
3116 }
3117
3118 pub fn float_ty(fty: ast::FloatTy) -> FloatTy {
3119     match fty {
3120         ast::FloatTy::F32 => FloatTy::F32,
3121         ast::FloatTy::F64 => FloatTy::F64,
3122     }
3123 }
3124
3125 pub fn ast_int_ty(ity: IntTy) -> ast::IntTy {
3126     match ity {
3127         IntTy::Isize => ast::IntTy::Isize,
3128         IntTy::I8 => ast::IntTy::I8,
3129         IntTy::I16 => ast::IntTy::I16,
3130         IntTy::I32 => ast::IntTy::I32,
3131         IntTy::I64 => ast::IntTy::I64,
3132         IntTy::I128 => ast::IntTy::I128,
3133     }
3134 }
3135
3136 pub fn ast_uint_ty(uty: UintTy) -> ast::UintTy {
3137     match uty {
3138         UintTy::Usize => ast::UintTy::Usize,
3139         UintTy::U8 => ast::UintTy::U8,
3140         UintTy::U16 => ast::UintTy::U16,
3141         UintTy::U32 => ast::UintTy::U32,
3142         UintTy::U64 => ast::UintTy::U64,
3143         UintTy::U128 => ast::UintTy::U128,
3144     }
3145 }
3146
3147 pub fn provide(providers: &mut ty::query::Providers) {
3148     context::provide(providers);
3149     erase_regions::provide(providers);
3150     layout::provide(providers);
3151     util::provide(providers);
3152     print::provide(providers);
3153     super::util::bug::provide(providers);
3154     *providers = ty::query::Providers {
3155         trait_impls_of: trait_def::trait_impls_of_provider,
3156         all_local_trait_impls: trait_def::all_local_trait_impls,
3157         type_uninhabited_from: inhabitedness::type_uninhabited_from,
3158         ..*providers
3159     };
3160 }
3161
3162 /// A map for the local crate mapping each type to a vector of its
3163 /// inherent impls. This is not meant to be used outside of coherence;
3164 /// rather, you should request the vector for a specific type via
3165 /// `tcx.inherent_impls(def_id)` so as to minimize your dependencies
3166 /// (constructing this map requires touching the entire crate).
3167 #[derive(Clone, Debug, Default, HashStable)]
3168 pub struct CrateInherentImpls {
3169     pub inherent_impls: DefIdMap<Vec<DefId>>,
3170 }
3171
3172 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, HashStable)]
3173 pub struct SymbolName<'tcx> {
3174     /// `&str` gives a consistent ordering, which ensures reproducible builds.
3175     pub name: &'tcx str,
3176 }
3177
3178 impl<'tcx> SymbolName<'tcx> {
3179     pub fn new(tcx: TyCtxt<'tcx>, name: &str) -> SymbolName<'tcx> {
3180         SymbolName {
3181             name: unsafe { str::from_utf8_unchecked(tcx.arena.alloc_slice(name.as_bytes())) },
3182         }
3183     }
3184 }
3185
3186 impl<'tcx> fmt::Display for SymbolName<'tcx> {
3187     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
3188         fmt::Display::fmt(&self.name, fmt)
3189     }
3190 }
3191
3192 impl<'tcx> fmt::Debug for SymbolName<'tcx> {
3193     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
3194         fmt::Display::fmt(&self.name, fmt)
3195     }
3196 }