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 rustc-dev-guide.
   9 //!
  10 //! ["The `ty` module: representing types"]: https://rustc-dev-guide.rust-lang.org/ty.html
  11
  12 pub use self::fold::{FallibleTypeFolder, TypeFoldable, TypeFolder, TypeSuperFoldable};
  13 pub use self::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor};
  14 pub use self::AssocItemContainer::*;
  15 pub use self::BorrowKind::*;
  16 pub use self::IntVarValue::*;
  17 pub use self::Variance::*;
  18 use crate::error::{OpaqueHiddenTypeMismatch, TypeMismatchReason};
  19 use crate::metadata::ModChild;
  20 use crate::middle::privacy::EffectiveVisibilities;
  21 use crate::mir::{Body, GeneratorLayout};
  22 use crate::traits::{self, Reveal};
  23 use crate::ty;
  24 use crate::ty::fast_reject::SimplifiedType;
  25 use crate::ty::util::Discr;
  26 pub use adt::*;
  27 pub use assoc::*;
  28 pub use generics::*;
  29 use hir::OpaqueTyOrigin;
  30 use rustc_ast as ast;
  31 use rustc_ast::node_id::NodeMap;
  32 use rustc_attr as attr;
  33 use rustc_data_structures::fingerprint::Fingerprint;
  34 use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap, FxIndexSet};
  35 use rustc_data_structures::intern::{Interned, WithStableHash};
  36 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  37 use rustc_data_structures::tagged_ptr::CopyTaggedPtr;
  38 use rustc_hir as hir;
  39 use rustc_hir::def::{CtorKind, CtorOf, DefKind, LifetimeRes, Res};
  40 use rustc_hir::def_id::{CrateNum, DefId, LocalDefId, LocalDefIdMap};
  41 use rustc_hir::definitions::Definitions;
  42 use rustc_hir::Node;
  43 use rustc_index::vec::IndexVec;
  44 use rustc_macros::HashStable;
  45 use rustc_query_system::ich::StableHashingContext;
  46 use rustc_serialize::{Decodable, Encodable};
  47 use rustc_session::cstore::CrateStoreDyn;
  48 use rustc_span::hygiene::MacroKind;
  49 use rustc_span::symbol::{kw, sym, Ident, Symbol};
  50 use rustc_span::{ExpnId, Span};
  51 use rustc_target::abi::{Align, VariantIdx};
  52 pub use subst::*;
  53 pub use vtable::*;
  54
  55 use std::fmt::Debug;
  56 use std::hash::{Hash, Hasher};
  57 use std::marker::PhantomData;
  58 use std::mem;
  59 use std::num::NonZeroUsize;
  60 use std::ops::ControlFlow;
  61 use std::{fmt, str};
  62
  63 pub use crate::ty::diagnostics::*;
  64 pub use rustc_type_ir::DynKind::*;
  65 pub use rustc_type_ir::InferTy::*;
  66 pub use rustc_type_ir::RegionKind::*;
  67 pub use rustc_type_ir::TyKind::*;
  68 pub use rustc_type_ir::*;
  69
  70 pub use self::binding::BindingMode;
  71 pub use self::binding::BindingMode::*;
  72 pub use self::closure::{
  73     is_ancestor_or_same_capture, place_to_string_for_capture, BorrowKind, CaptureInfo,
  74     CapturedPlace, ClosureKind, MinCaptureInformationMap, MinCaptureList,
  75     RootVariableMinCaptureList, UpvarCapture, UpvarCaptureMap, UpvarId, UpvarListMap, UpvarPath,
  76     CAPTURE_STRUCT_LOCAL,
  77 };
  78 pub use self::consts::{
  79     Const, ConstInt, ConstKind, ConstS, InferConst, ScalarInt, UnevaluatedConst, ValTree,
  80 };
  81 pub use self::context::{
  82     tls, CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations,
  83     CtxtInterners, DeducedParamAttrs, FreeRegionInfo, GeneratorDiagnosticData,
  84     GeneratorInteriorTypeCause, GlobalCtxt, Lift, OnDiskCache, TyCtxt, TypeckResults, UserType,
  85     UserTypeAnnotationIndex,
  86 };
  87 pub use self::instance::{Instance, InstanceDef, ShortInstance};
  88 pub use self::list::List;
  89 pub use self::parameterized::ParameterizedOverTcx;
  90 pub use self::rvalue_scopes::RvalueScopes;
  91 pub use self::sty::BoundRegionKind::*;
  92 pub use self::sty::{
  93     Article, Binder, BoundRegion, BoundRegionKind, BoundTy, BoundTyKind, BoundVar,
  94     BoundVariableKind, CanonicalPolyFnSig, ClosureSubsts, ClosureSubstsParts, ConstVid,
  95     EarlyBoundRegion, ExistentialPredicate, ExistentialProjection, ExistentialTraitRef, FnSig,
  96     FreeRegion, GenSig, GeneratorSubsts, GeneratorSubstsParts, InlineConstSubsts,
  97     InlineConstSubstsParts, ParamConst, ParamTy, PolyExistentialPredicate,
  98     PolyExistentialProjection, PolyExistentialTraitRef, PolyFnSig, PolyGenSig, PolyTraitRef,
  99     ProjectionTy, Region, RegionKind, RegionVid, TraitRef, TyKind, TypeAndMut, UpvarSubsts,
 100     VarianceDiagInfo,
 101 };
 102 pub use self::trait_def::TraitDef;
 103
 104 pub mod _match;
 105 pub mod abstract_const;
 106 pub mod adjustment;
 107 pub mod binding;
 108 pub mod cast;
 109 pub mod codec;
 110 pub mod error;
 111 pub mod fast_reject;
 112 pub mod flags;
 113 pub mod fold;
 114 pub mod inhabitedness;
 115 pub mod layout;
 116 pub mod normalize_erasing_regions;
 117 pub mod print;
 118 pub mod query;
 119 pub mod relate;
 120 pub mod subst;
 121 pub mod trait_def;
 122 pub mod util;
 123 pub mod visit;
 124 pub mod vtable;
 125 pub mod walk;
 126
 127 mod adt;
 128 mod assoc;
 129 mod closure;
 130 mod consts;
 131 mod context;
 132 mod diagnostics;
 133 mod erase_regions;
 134 mod generics;
 135 mod impls_ty;
 136 mod instance;
 137 mod list;
 138 mod opaque_types;
 139 mod parameterized;
 140 mod rvalue_scopes;
 141 mod structural_impls;
 142 mod sty;
 143
 144 // Data types
 145
 146 pub type RegisteredTools = FxHashSet<Ident>;
 147
 148 pub struct ResolverOutputs {
 149     pub definitions: Definitions,
 150     pub global_ctxt: ResolverGlobalCtxt,
 151     pub ast_lowering: ResolverAstLowering,
 152 }
 153
 154 #[derive(Debug)]
 155 pub struct ResolverGlobalCtxt {
 156     pub cstore: Box<CrateStoreDyn>,
 157     pub visibilities: FxHashMap<LocalDefId, Visibility>,
 158     /// This field is used to decide whether we should make `PRIVATE_IN_PUBLIC` a hard error.
 159     pub has_pub_restricted: bool,
 160     /// Item with a given `LocalDefId` was defined during macro expansion with ID `ExpnId`.
 161     pub expn_that_defined: FxHashMap<LocalDefId, ExpnId>,
 162     /// Reference span for definitions.
 163     pub source_span: IndexVec<LocalDefId, Span>,
 164     pub effective_visibilities: EffectiveVisibilities,
 165     pub extern_crate_map: FxHashMap<LocalDefId, CrateNum>,
 166     pub maybe_unused_trait_imports: FxIndexSet<LocalDefId>,
 167     pub maybe_unused_extern_crates: Vec<(LocalDefId, Span)>,
 168     pub reexport_map: FxHashMap<LocalDefId, Vec<ModChild>>,
 169     pub glob_map: FxHashMap<LocalDefId, FxHashSet<Symbol>>,
 170     /// Extern prelude entries. The value is `true` if the entry was introduced
 171     /// via `extern crate` item and not `--extern` option or compiler built-in.
 172     pub extern_prelude: FxHashMap<Symbol, bool>,
 173     pub main_def: Option<MainDefinition>,
 174     pub trait_impls: FxIndexMap<DefId, Vec<LocalDefId>>,
 175     /// A list of proc macro LocalDefIds, written out in the order in which
 176     /// they are declared in the static array generated by proc_macro_harness.
 177     pub proc_macros: Vec<LocalDefId>,
 178     /// Mapping from ident span to path span for paths that don't exist as written, but that
 179     /// exist under `std`. For example, wrote `str::from_utf8` instead of `std::str::from_utf8`.
 180     pub confused_type_with_std_module: FxHashMap<Span, Span>,
 181     pub registered_tools: RegisteredTools,
 182 }
 183
 184 /// Resolutions that should only be used for lowering.
 185 /// This struct is meant to be consumed by lowering.
 186 #[derive(Debug)]
 187 pub struct ResolverAstLowering {
 188     pub legacy_const_generic_args: FxHashMap<DefId, Option<Vec<usize>>>,
 189
 190     /// Resolutions for nodes that have a single resolution.
 191     pub partial_res_map: NodeMap<hir::def::PartialRes>,
 192     /// Resolutions for import nodes, which have multiple resolutions in different namespaces.
 193     pub import_res_map: NodeMap<hir::def::PerNS<Option<Res<ast::NodeId>>>>,
 194     /// Resolutions for labels (node IDs of their corresponding blocks or loops).
 195     pub label_res_map: NodeMap<ast::NodeId>,
 196     /// Resolutions for lifetimes.
 197     pub lifetimes_res_map: NodeMap<LifetimeRes>,
 198     /// Lifetime parameters that lowering will have to introduce.
 199     pub extra_lifetime_params_map: NodeMap<Vec<(Ident, ast::NodeId, LifetimeRes)>>,
 200
 201     pub next_node_id: ast::NodeId,
 202
 203     pub node_id_to_def_id: FxHashMap<ast::NodeId, LocalDefId>,
 204     pub def_id_to_node_id: IndexVec<LocalDefId, ast::NodeId>,
 205
 206     pub trait_map: NodeMap<Vec<hir::TraitCandidate>>,
 207     /// A small map keeping true kinds of built-in macros that appear to be fn-like on
 208     /// the surface (`macro` items in libcore), but are actually attributes or derives.
 209     pub builtin_macro_kinds: FxHashMap<LocalDefId, MacroKind>,
 210 }
 211
 212 #[derive(Clone, Copy, Debug)]
 213 pub struct MainDefinition {
 214     pub res: Res<ast::NodeId>,
 215     pub is_import: bool,
 216     pub span: Span,
 217 }
 218
 219 impl MainDefinition {
 220     pub fn opt_fn_def_id(self) -> Option<DefId> {
 221         if let Res::Def(DefKind::Fn, def_id) = self.res { Some(def_id) } else { None }
 222     }
 223 }
 224
 225 /// The "header" of an impl is everything outside the body: a Self type, a trait
 226 /// ref (in the case of a trait impl), and a set of predicates (from the
 227 /// bounds / where-clauses).
 228 #[derive(Clone, Debug, TypeFoldable, TypeVisitable)]
 229 pub struct ImplHeader<'tcx> {
 230     pub impl_def_id: DefId,
 231     pub self_ty: Ty<'tcx>,
 232     pub trait_ref: Option<TraitRef<'tcx>>,
 233     pub predicates: Vec<Predicate<'tcx>>,
 234 }
 235
 236 #[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable)]
 237 pub enum ImplSubject<'tcx> {
 238     Trait(TraitRef<'tcx>),
 239     Inherent(Ty<'tcx>),
 240 }
 241
 242 #[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable, HashStable, Debug)]
 243 #[derive(TypeFoldable, TypeVisitable)]
 244 pub enum ImplPolarity {
 245     /// `impl Trait for Type`
 246     Positive,
 247     /// `impl !Trait for Type`
 248     Negative,
 249     /// `#[rustc_reservation_impl] impl Trait for Type`
 250     ///
 251     /// This is a "stability hack", not a real Rust feature.
 252     /// See #64631 for details.
 253     Reservation,
 254 }
 255
 256 impl ImplPolarity {
 257     /// Flips polarity by turning `Positive` into `Negative` and `Negative` into `Positive`.
 258     pub fn flip(&self) -> Option<ImplPolarity> {
 259         match self {
 260             ImplPolarity::Positive => Some(ImplPolarity::Negative),
 261             ImplPolarity::Negative => Some(ImplPolarity::Positive),
 262             ImplPolarity::Reservation => None,
 263         }
 264     }
 265 }
 266
 267 impl fmt::Display for ImplPolarity {
 268     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 269         match self {
 270             Self::Positive => f.write_str("positive"),
 271             Self::Negative => f.write_str("negative"),
 272             Self::Reservation => f.write_str("reservation"),
 273         }
 274     }
 275 }
 276
 277 #[derive(Clone, Debug, PartialEq, Eq, Copy, Hash, Encodable, Decodable, HashStable)]
 278 pub enum Visibility<Id = LocalDefId> {
 279     /// Visible everywhere (including in other crates).
 280     Public,
 281     /// Visible only in the given crate-local module.
 282     Restricted(Id),
 283 }
 284
 285 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable, TyEncodable, TyDecodable)]
 286 pub enum BoundConstness {
 287     /// `T: Trait`
 288     NotConst,
 289     /// `T: ~const Trait`
 290     ///
 291     /// Requires resolving to const only when we are in a const context.
 292     ConstIfConst,
 293 }
 294
 295 impl BoundConstness {
 296     /// Reduce `self` and `constness` to two possible combined states instead of four.
 297     pub fn and(&mut self, constness: hir::Constness) -> hir::Constness {
 298         match (constness, self) {
 299             (hir::Constness::Const, BoundConstness::ConstIfConst) => hir::Constness::Const,
 300             (_, this) => {
 301                 *this = BoundConstness::NotConst;
 302                 hir::Constness::NotConst
 303             }
 304         }
 305     }
 306 }
 307
 308 impl fmt::Display for BoundConstness {
 309     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 310         match self {
 311             Self::NotConst => f.write_str("normal"),
 312             Self::ConstIfConst => f.write_str("`~const`"),
 313         }
 314     }
 315 }
 316
 317 #[derive(Clone, Debug, PartialEq, Eq, Copy, Hash, TyEncodable, TyDecodable, HashStable)]
 318 #[derive(TypeFoldable, TypeVisitable)]
 319 pub struct ClosureSizeProfileData<'tcx> {
 320     /// Tuple containing the types of closure captures before the feature `capture_disjoint_fields`
 321     pub before_feature_tys: Ty<'tcx>,
 322     /// Tuple containing the types of closure captures after the feature `capture_disjoint_fields`
 323     pub after_feature_tys: Ty<'tcx>,
 324 }
 325
 326 pub trait DefIdTree: Copy {
 327     fn opt_parent(self, id: DefId) -> Option<DefId>;
 328
 329     #[inline]
 330     #[track_caller]
 331     fn parent(self, id: DefId) -> DefId {
 332         match self.opt_parent(id) {
 333             Some(id) => id,
 334             // not `unwrap_or_else` to avoid breaking caller tracking
 335             None => bug!("{id:?} doesn't have a parent"),
 336         }
 337     }
 338
 339     #[inline]
 340     #[track_caller]
 341     fn opt_local_parent(self, id: LocalDefId) -> Option<LocalDefId> {
 342         self.opt_parent(id.to_def_id()).map(DefId::expect_local)
 343     }
 344
 345     #[inline]
 346     #[track_caller]
 347     fn local_parent(self, id: LocalDefId) -> LocalDefId {
 348         self.parent(id.to_def_id()).expect_local()
 349     }
 350
 351     fn is_descendant_of(self, mut descendant: DefId, ancestor: DefId) -> bool {
 352         if descendant.krate != ancestor.krate {
 353             return false;
 354         }
 355
 356         while descendant != ancestor {
 357             match self.opt_parent(descendant) {
 358                 Some(parent) => descendant = parent,
 359                 None => return false,
 360             }
 361         }
 362         true
 363     }
 364 }
 365
 366 impl<'tcx> DefIdTree for TyCtxt<'tcx> {
 367     #[inline]
 368     fn opt_parent(self, id: DefId) -> Option<DefId> {
 369         self.def_key(id).parent.map(|index| DefId { index, ..id })
 370     }
 371 }
 372
 373 impl<Id> Visibility<Id> {
 374     pub fn is_public(self) -> bool {
 375         matches!(self, Visibility::Public)
 376     }
 377
 378     pub fn map_id<OutId>(self, f: impl FnOnce(Id) -> OutId) -> Visibility<OutId> {
 379         match self {
 380             Visibility::Public => Visibility::Public,
 381             Visibility::Restricted(id) => Visibility::Restricted(f(id)),
 382         }
 383     }
 384 }
 385
 386 impl<Id: Into<DefId>> Visibility<Id> {
 387     pub fn to_def_id(self) -> Visibility<DefId> {
 388         self.map_id(Into::into)
 389     }
 390
 391     /// Returns `true` if an item with this visibility is accessible from the given module.
 392     pub fn is_accessible_from(self, module: impl Into<DefId>, tree: impl DefIdTree) -> bool {
 393         match self {
 394             // Public items are visible everywhere.
 395             Visibility::Public => true,
 396             Visibility::Restricted(id) => tree.is_descendant_of(module.into(), id.into()),
 397         }
 398     }
 399
 400     /// Returns `true` if this visibility is at least as accessible as the given visibility
 401     pub fn is_at_least(self, vis: Visibility<impl Into<DefId>>, tree: impl DefIdTree) -> bool {
 402         match vis {
 403             Visibility::Public => self.is_public(),
 404             Visibility::Restricted(id) => self.is_accessible_from(id, tree),
 405         }
 406     }
 407 }
 408
 409 impl Visibility<DefId> {
 410     pub fn expect_local(self) -> Visibility {
 411         self.map_id(|id| id.expect_local())
 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         }
 420     }
 421 }
 422
 423 /// The crate variances map is computed during typeck and contains the
 424 /// variance of every item in the local crate. You should not use it
 425 /// directly, because to do so will make your pass dependent on the
 426 /// HIR of every item in the local crate. Instead, use
 427 /// `tcx.variances_of()` to get the variance for a *particular*
 428 /// item.
 429 #[derive(HashStable, Debug)]
 430 pub struct CrateVariancesMap<'tcx> {
 431     /// For each item with generics, maps to a vector of the variance
 432     /// of its generics. If an item has no generics, it will have no
 433     /// entry.
 434     pub variances: FxHashMap<DefId, &'tcx [ty::Variance]>,
 435 }
 436
 437 // Contains information needed to resolve types and (in the future) look up
 438 // the types of AST nodes.
 439 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 440 pub struct CReaderCacheKey {
 441     pub cnum: Option<CrateNum>,
 442     pub pos: usize,
 443 }
 444
 445 /// Represents a type.
 446 ///
 447 /// IMPORTANT:
 448 /// - This is a very "dumb" struct (with no derives and no `impls`).
 449 /// - Values of this type are always interned and thus unique, and are stored
 450 ///   as an `Interned<TyS>`.
 451 /// - `Ty` (which contains a reference to a `Interned<TyS>`) or `Interned<TyS>`
 452 ///   should be used everywhere instead of `TyS`. In particular, `Ty` has most
 453 ///   of the relevant methods.
 454 #[derive(PartialEq, Eq, PartialOrd, Ord)]
 455 #[allow(rustc::usage_of_ty_tykind)]
 456 pub(crate) struct TyS<'tcx> {
 457     /// This field shouldn't be used directly and may be removed in the future.
 458     /// Use `Ty::kind()` instead.
 459     kind: TyKind<'tcx>,
 460
 461     /// This field provides fast access to information that is also contained
 462     /// in `kind`.
 463     ///
 464     /// This field shouldn't be used directly and may be removed in the future.
 465     /// Use `Ty::flags()` instead.
 466     flags: TypeFlags,
 467
 468     /// This field provides fast access to information that is also contained
 469     /// in `kind`.
 470     ///
 471     /// This is a kind of confusing thing: it stores the smallest
 472     /// binder such that
 473     ///
 474     /// (a) the binder itself captures nothing but
 475     /// (b) all the late-bound things within the type are captured
 476     ///     by some sub-binder.
 477     ///
 478     /// So, for a type without any late-bound things, like `u32`, this
 479     /// will be *innermost*, because that is the innermost binder that
 480     /// captures nothing. But for a type `&'D u32`, where `'D` is a
 481     /// late-bound region with De Bruijn index `D`, this would be `D + 1`
 482     /// -- the binder itself does not capture `D`, but `D` is captured
 483     /// by an inner binder.
 484     ///
 485     /// We call this concept an "exclusive" binder `D` because all
 486     /// De Bruijn indices within the type are contained within `0..D`
 487     /// (exclusive).
 488     outer_exclusive_binder: ty::DebruijnIndex,
 489 }
 490
 491 /// Use this rather than `TyS`, whenever possible.
 492 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, HashStable)]
 493 #[rustc_diagnostic_item = "Ty"]
 494 #[rustc_pass_by_value]
 495 pub struct Ty<'tcx>(Interned<'tcx, WithStableHash<TyS<'tcx>>>);
 496
 497 impl<'tcx> TyCtxt<'tcx> {
 498     /// A "bool" type used in rustc_mir_transform unit tests when we
 499     /// have not spun up a TyCtxt.
 500     pub const BOOL_TY_FOR_UNIT_TESTING: Ty<'tcx> = Ty(Interned::new_unchecked(&WithStableHash {
 501         internee: TyS {
 502             kind: ty::Bool,
 503             flags: TypeFlags::empty(),
 504             outer_exclusive_binder: DebruijnIndex::from_usize(0),
 505         },
 506         stable_hash: Fingerprint::ZERO,
 507     }));
 508 }
 509
 510 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for TyS<'tcx> {
 511     #[inline]
 512     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 513         let TyS {
 514             kind,
 515
 516             // The other fields just provide fast access to information that is
 517             // also contained in `kind`, so no need to hash them.
 518             flags: _,
 519
 520             outer_exclusive_binder: _,
 521         } = self;
 522
 523         kind.hash_stable(hcx, hasher)
 524     }
 525 }
 526
 527 impl ty::EarlyBoundRegion {
 528     /// Does this early bound region have a name? Early bound regions normally
 529     /// always have names except when using anonymous lifetimes (`'_`).
 530     pub fn has_name(&self) -> bool {
 531         self.name != kw::UnderscoreLifetime
 532     }
 533 }
 534
 535 /// Represents a predicate.
 536 ///
 537 /// See comments on `TyS`, which apply here too (albeit for
 538 /// `PredicateS`/`Predicate` rather than `TyS`/`Ty`).
 539 #[derive(Debug)]
 540 pub(crate) struct PredicateS<'tcx> {
 541     kind: Binder<'tcx, PredicateKind<'tcx>>,
 542     flags: TypeFlags,
 543     /// See the comment for the corresponding field of [TyS].
 544     outer_exclusive_binder: ty::DebruijnIndex,
 545 }
 546
 547 /// Use this rather than `PredicateS`, whenever possible.
 548 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
 549 #[rustc_pass_by_value]
 550 pub struct Predicate<'tcx>(Interned<'tcx, PredicateS<'tcx>>);
 551
 552 impl<'tcx> Predicate<'tcx> {
 553     /// Gets the inner `Binder<'tcx, PredicateKind<'tcx>>`.
 554     #[inline]
 555     pub fn kind(self) -> Binder<'tcx, PredicateKind<'tcx>> {
 556         self.0.kind
 557     }
 558
 559     #[inline(always)]
 560     pub fn flags(self) -> TypeFlags {
 561         self.0.flags
 562     }
 563
 564     #[inline(always)]
 565     pub fn outer_exclusive_binder(self) -> DebruijnIndex {
 566         self.0.outer_exclusive_binder
 567     }
 568
 569     /// Flips the polarity of a Predicate.
 570     ///
 571     /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
 572     pub fn flip_polarity(self, tcx: TyCtxt<'tcx>) -> Option<Predicate<'tcx>> {
 573         let kind = self
 574             .kind()
 575             .map_bound(|kind| match kind {
 576                 PredicateKind::Trait(TraitPredicate { trait_ref, constness, polarity }) => {
 577                     Some(PredicateKind::Trait(TraitPredicate {
 578                         trait_ref,
 579                         constness,
 580                         polarity: polarity.flip()?,
 581                     }))
 582                 }
 583
 584                 _ => None,
 585             })
 586             .transpose()?;
 587
 588         Some(tcx.mk_predicate(kind))
 589     }
 590
 591     pub fn without_const(mut self, tcx: TyCtxt<'tcx>) -> Self {
 592         if let PredicateKind::Trait(TraitPredicate { trait_ref, constness, polarity }) = self.kind().skip_binder()
 593             && constness != BoundConstness::NotConst
 594         {
 595             self = tcx.mk_predicate(self.kind().rebind(PredicateKind::Trait(TraitPredicate {
 596                 trait_ref,
 597                 constness: BoundConstness::NotConst,
 598                 polarity,
 599             })));
 600         }
 601         self
 602     }
 603
 604     /// Whether this projection can be soundly normalized.
 605     ///
 606     /// Wf predicates must not be normalized, as normalization
 607     /// can remove required bounds which would cause us to
 608     /// unsoundly accept some programs. See #91068.
 609     #[inline]
 610     pub fn allow_normalization(self) -> bool {
 611         match self.kind().skip_binder() {
 612             PredicateKind::WellFormed(_) => false,
 613             PredicateKind::Trait(_)
 614             | PredicateKind::RegionOutlives(_)
 615             | PredicateKind::TypeOutlives(_)
 616             | PredicateKind::Projection(_)
 617             | PredicateKind::ObjectSafe(_)
 618             | PredicateKind::ClosureKind(_, _, _)
 619             | PredicateKind::Subtype(_)
 620             | PredicateKind::Coerce(_)
 621             | PredicateKind::ConstEvaluatable(_)
 622             | PredicateKind::ConstEquate(_, _)
 623             | PredicateKind::TypeWellFormedFromEnv(_) => true,
 624         }
 625     }
 626 }
 627
 628 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Predicate<'tcx> {
 629     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 630         let PredicateS {
 631             ref kind,
 632
 633             // The other fields just provide fast access to information that is
 634             // also contained in `kind`, so no need to hash them.
 635             flags: _,
 636             outer_exclusive_binder: _,
 637         } = self.0.0;
 638
 639         kind.hash_stable(hcx, hasher);
 640     }
 641 }
 642
 643 impl rustc_errors::IntoDiagnosticArg for Predicate<'_> {
 644     fn into_diagnostic_arg(self) -> rustc_errors::DiagnosticArgValue<'static> {
 645         rustc_errors::DiagnosticArgValue::Str(std::borrow::Cow::Owned(self.to_string()))
 646     }
 647 }
 648
 649 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
 650 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 651 pub enum PredicateKind<'tcx> {
 652     /// Corresponds to `where Foo: Bar<A, B, C>`. `Foo` here would be
 653     /// the `Self` type of the trait reference and `A`, `B`, and `C`
 654     /// would be the type parameters.
 655     Trait(TraitPredicate<'tcx>),
 656
 657     /// `where 'a: 'b`
 658     RegionOutlives(RegionOutlivesPredicate<'tcx>),
 659
 660     /// `where T: 'a`
 661     TypeOutlives(TypeOutlivesPredicate<'tcx>),
 662
 663     /// `where <T as TraitRef>::Name == X`, approximately.
 664     /// See the `ProjectionPredicate` struct for details.
 665     Projection(ProjectionPredicate<'tcx>),
 666
 667     /// No syntax: `T` well-formed.
 668     WellFormed(GenericArg<'tcx>),
 669
 670     /// Trait must be object-safe.
 671     ObjectSafe(DefId),
 672
 673     /// No direct syntax. May be thought of as `where T: FnFoo<...>`
 674     /// for some substitutions `...` and `T` being a closure type.
 675     /// Satisfied (or refuted) once we know the closure's kind.
 676     ClosureKind(DefId, SubstsRef<'tcx>, ClosureKind),
 677
 678     /// `T1 <: T2`
 679     ///
 680     /// This obligation is created most often when we have two
 681     /// unresolved type variables and hence don't have enough
 682     /// information to process the subtyping obligation yet.
 683     Subtype(SubtypePredicate<'tcx>),
 684
 685     /// `T1` coerced to `T2`
 686     ///
 687     /// Like a subtyping obligation, this is created most often
 688     /// when we have two unresolved type variables and hence
 689     /// don't have enough information to process the coercion
 690     /// obligation yet. At the moment, we actually process coercions
 691     /// very much like subtyping and don't handle the full coercion
 692     /// logic.
 693     Coerce(CoercePredicate<'tcx>),
 694
 695     /// Constant initializer must evaluate successfully.
 696     ConstEvaluatable(ty::Const<'tcx>),
 697
 698     /// Constants must be equal. The first component is the const that is expected.
 699     ConstEquate(Const<'tcx>, Const<'tcx>),
 700
 701     /// Represents a type found in the environment that we can use for implied bounds.
 702     ///
 703     /// Only used for Chalk.
 704     TypeWellFormedFromEnv(Ty<'tcx>),
 705 }
 706
 707 /// The crate outlives map is computed during typeck and contains the
 708 /// outlives of every item in the local crate. You should not use it
 709 /// directly, because to do so will make your pass dependent on the
 710 /// HIR of every item in the local crate. Instead, use
 711 /// `tcx.inferred_outlives_of()` to get the outlives for a *particular*
 712 /// item.
 713 #[derive(HashStable, Debug)]
 714 pub struct CratePredicatesMap<'tcx> {
 715     /// For each struct with outlive bounds, maps to a vector of the
 716     /// predicate of its outlive bounds. If an item has no outlives
 717     /// bounds, it will have no entry.
 718     pub predicates: FxHashMap<DefId, &'tcx [(Predicate<'tcx>, Span)]>,
 719 }
 720
 721 impl<'tcx> Predicate<'tcx> {
 722     /// Performs a substitution suitable for going from a
 723     /// poly-trait-ref to supertraits that must hold if that
 724     /// poly-trait-ref holds. This is slightly different from a normal
 725     /// substitution in terms of what happens with bound regions. See
 726     /// lengthy comment below for details.
 727     pub fn subst_supertrait(
 728         self,
 729         tcx: TyCtxt<'tcx>,
 730         trait_ref: &ty::PolyTraitRef<'tcx>,
 731     ) -> Predicate<'tcx> {
 732         // The interaction between HRTB and supertraits is not entirely
 733         // obvious. Let me walk you (and myself) through an example.
 734         //
 735         // Let's start with an easy case. Consider two traits:
 736         //
 737         //     trait Foo<'a>: Bar<'a,'a> { }
 738         //     trait Bar<'b,'c> { }
 739         //
 740         // Now, if we have a trait reference `for<'x> T: Foo<'x>`, then
 741         // we can deduce that `for<'x> T: Bar<'x,'x>`. Basically, if we
 742         // knew that `Foo<'x>` (for any 'x) then we also know that
 743         // `Bar<'x,'x>` (for any 'x). This more-or-less falls out from
 744         // normal substitution.
 745         //
 746         // In terms of why this is sound, the idea is that whenever there
 747         // is an impl of `T:Foo<'a>`, it must show that `T:Bar<'a,'a>`
 748         // holds.  So if there is an impl of `T:Foo<'a>` that applies to
 749         // all `'a`, then we must know that `T:Bar<'a,'a>` holds for all
 750         // `'a`.
 751         //
 752         // Another example to be careful of is this:
 753         //
 754         //     trait Foo1<'a>: for<'b> Bar1<'a,'b> { }
 755         //     trait Bar1<'b,'c> { }
 756         //
 757         // Here, if we have `for<'x> T: Foo1<'x>`, then what do we know?
 758         // The answer is that we know `for<'x,'b> T: Bar1<'x,'b>`. The
 759         // reason is similar to the previous example: any impl of
 760         // `T:Foo1<'x>` must show that `for<'b> T: Bar1<'x, 'b>`.  So
 761         // basically we would want to collapse the bound lifetimes from
 762         // the input (`trait_ref`) and the supertraits.
 763         //
 764         // To achieve this in practice is fairly straightforward. Let's
 765         // consider the more complicated scenario:
 766         //
 767         // - We start out with `for<'x> T: Foo1<'x>`. In this case, `'x`
 768         //   has a De Bruijn index of 1. We want to produce `for<'x,'b> T: Bar1<'x,'b>`,
 769         //   where both `'x` and `'b` would have a DB index of 1.
 770         //   The substitution from the input trait-ref is therefore going to be
 771         //   `'a => 'x` (where `'x` has a DB index of 1).
 772         // - The supertrait-ref is `for<'b> Bar1<'a,'b>`, where `'a` is an
 773         //   early-bound parameter and `'b' is a late-bound parameter with a
 774         //   DB index of 1.
 775         // - If we replace `'a` with `'x` from the input, it too will have
 776         //   a DB index of 1, and thus we'll have `for<'x,'b> Bar1<'x,'b>`
 777         //   just as we wanted.
 778         //
 779         // There is only one catch. If we just apply the substitution `'a
 780         // => 'x` to `for<'b> Bar1<'a,'b>`, the substitution code will
 781         // adjust the DB index because we substituting into a binder (it
 782         // tries to be so smart...) resulting in `for<'x> for<'b>
 783         // Bar1<'x,'b>` (we have no syntax for this, so use your
 784         // imagination). Basically the 'x will have DB index of 2 and 'b
 785         // will have DB index of 1. Not quite what we want. So we apply
 786         // the substitution to the *contents* of the trait reference,
 787         // rather than the trait reference itself (put another way, the
 788         // substitution code expects equal binding levels in the values
 789         // from the substitution and the value being substituted into, and
 790         // this trick achieves that).
 791
 792         // Working through the second example:
 793         // trait_ref: for<'x> T: Foo1<'^0.0>; substs: [T, '^0.0]
 794         // predicate: for<'b> Self: Bar1<'a, '^0.0>; substs: [Self, 'a, '^0.0]
 795         // We want to end up with:
 796         //     for<'x, 'b> T: Bar1<'^0.0, '^0.1>
 797         // To do this:
 798         // 1) We must shift all bound vars in predicate by the length
 799         //    of trait ref's bound vars. So, we would end up with predicate like
 800         //    Self: Bar1<'a, '^0.1>
 801         // 2) We can then apply the trait substs to this, ending up with
 802         //    T: Bar1<'^0.0, '^0.1>
 803         // 3) Finally, to create the final bound vars, we concatenate the bound
 804         //    vars of the trait ref with those of the predicate:
 805         //    ['x, 'b]
 806         let bound_pred = self.kind();
 807         let pred_bound_vars = bound_pred.bound_vars();
 808         let trait_bound_vars = trait_ref.bound_vars();
 809         // 1) Self: Bar1<'a, '^0.0> -> Self: Bar1<'a, '^0.1>
 810         let shifted_pred =
 811             tcx.shift_bound_var_indices(trait_bound_vars.len(), bound_pred.skip_binder());
 812         // 2) Self: Bar1<'a, '^0.1> -> T: Bar1<'^0.0, '^0.1>
 813         let new = EarlyBinder(shifted_pred).subst(tcx, trait_ref.skip_binder().substs);
 814         // 3) ['x] + ['b] -> ['x, 'b]
 815         let bound_vars =
 816             tcx.mk_bound_variable_kinds(trait_bound_vars.iter().chain(pred_bound_vars));
 817         tcx.reuse_or_mk_predicate(self, ty::Binder::bind_with_vars(new, bound_vars))
 818     }
 819 }
 820
 821 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
 822 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 823 pub struct TraitPredicate<'tcx> {
 824     pub trait_ref: TraitRef<'tcx>,
 825
 826     pub constness: BoundConstness,
 827
 828     /// If polarity is Positive: we are proving that the trait is implemented.
 829     ///
 830     /// If polarity is Negative: we are proving that a negative impl of this trait
 831     /// exists. (Note that coherence also checks whether negative impls of supertraits
 832     /// exist via a series of predicates.)
 833     ///
 834     /// If polarity is Reserved: that's a bug.
 835     pub polarity: ImplPolarity,
 836 }
 837
 838 pub type PolyTraitPredicate<'tcx> = ty::Binder<'tcx, TraitPredicate<'tcx>>;
 839
 840 impl<'tcx> TraitPredicate<'tcx> {
 841     pub fn remap_constness(&mut self, param_env: &mut ParamEnv<'tcx>) {
 842         *param_env = param_env.with_constness(self.constness.and(param_env.constness()))
 843     }
 844
 845     /// Remap the constness of this predicate before emitting it for diagnostics.
 846     pub fn remap_constness_diag(&mut self, param_env: ParamEnv<'tcx>) {
 847         // this is different to `remap_constness` that callees want to print this predicate
 848         // in case of selection errors. `T: ~const Drop` bounds cannot end up here when the
 849         // param_env is not const because it is always satisfied in non-const contexts.
 850         if let hir::Constness::NotConst = param_env.constness() {
 851             self.constness = ty::BoundConstness::NotConst;
 852         }
 853     }
 854
 855     pub fn with_self_type(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
 856         Self { trait_ref: self.trait_ref.with_self_type(tcx, self_ty), ..self }
 857     }
 858
 859     pub fn def_id(self) -> DefId {
 860         self.trait_ref.def_id
 861     }
 862
 863     pub fn self_ty(self) -> Ty<'tcx> {
 864         self.trait_ref.self_ty()
 865     }
 866
 867     #[inline]
 868     pub fn is_const_if_const(self) -> bool {
 869         self.constness == BoundConstness::ConstIfConst
 870     }
 871
 872     pub fn is_constness_satisfied_by(self, constness: hir::Constness) -> bool {
 873         match (self.constness, constness) {
 874             (BoundConstness::NotConst, _)
 875             | (BoundConstness::ConstIfConst, hir::Constness::Const) => true,
 876             (BoundConstness::ConstIfConst, hir::Constness::NotConst) => false,
 877         }
 878     }
 879
 880     pub fn without_const(mut self) -> Self {
 881         self.constness = BoundConstness::NotConst;
 882         self
 883     }
 884 }
 885
 886 impl<'tcx> PolyTraitPredicate<'tcx> {
 887     pub fn def_id(self) -> DefId {
 888         // Ok to skip binder since trait `DefId` does not care about regions.
 889         self.skip_binder().def_id()
 890     }
 891
 892     pub fn self_ty(self) -> ty::Binder<'tcx, Ty<'tcx>> {
 893         self.map_bound(|trait_ref| trait_ref.self_ty())
 894     }
 895
 896     /// Remap the constness of this predicate before emitting it for diagnostics.
 897     pub fn remap_constness_diag(&mut self, param_env: ParamEnv<'tcx>) {
 898         *self = self.map_bound(|mut p| {
 899             p.remap_constness_diag(param_env);
 900             p
 901         });
 902     }
 903
 904     #[inline]
 905     pub fn is_const_if_const(self) -> bool {
 906         self.skip_binder().is_const_if_const()
 907     }
 908 }
 909
 910 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
 911 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 912 pub struct OutlivesPredicate<A, B>(pub A, pub B); // `A: B`
 913 pub type RegionOutlivesPredicate<'tcx> = OutlivesPredicate<ty::Region<'tcx>, ty::Region<'tcx>>;
 914 pub type TypeOutlivesPredicate<'tcx> = OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>;
 915 pub type PolyRegionOutlivesPredicate<'tcx> = ty::Binder<'tcx, RegionOutlivesPredicate<'tcx>>;
 916 pub type PolyTypeOutlivesPredicate<'tcx> = ty::Binder<'tcx, TypeOutlivesPredicate<'tcx>>;
 917
 918 /// Encodes that `a` must be a subtype of `b`. The `a_is_expected` flag indicates
 919 /// whether the `a` type is the type that we should label as "expected" when
 920 /// presenting user diagnostics.
 921 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
 922 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 923 pub struct SubtypePredicate<'tcx> {
 924     pub a_is_expected: bool,
 925     pub a: Ty<'tcx>,
 926     pub b: Ty<'tcx>,
 927 }
 928 pub type PolySubtypePredicate<'tcx> = ty::Binder<'tcx, SubtypePredicate<'tcx>>;
 929
 930 /// Encodes that we have to coerce *from* the `a` type to the `b` type.
 931 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
 932 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 933 pub struct CoercePredicate<'tcx> {
 934     pub a: Ty<'tcx>,
 935     pub b: Ty<'tcx>,
 936 }
 937 pub type PolyCoercePredicate<'tcx> = ty::Binder<'tcx, CoercePredicate<'tcx>>;
 938
 939 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 940 pub struct Term<'tcx> {
 941     ptr: NonZeroUsize,
 942     marker: PhantomData<(Ty<'tcx>, Const<'tcx>)>,
 943 }
 944
 945 impl Debug for Term<'_> {
 946     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 947         let data = if let Some(ty) = self.ty() {
 948             format!("Term::Ty({:?})", ty)
 949         } else if let Some(ct) = self.ct() {
 950             format!("Term::Ct({:?})", ct)
 951         } else {
 952             unreachable!()
 953         };
 954         f.write_str(&data)
 955     }
 956 }
 957
 958 impl<'tcx> From<Ty<'tcx>> for Term<'tcx> {
 959     fn from(ty: Ty<'tcx>) -> Self {
 960         TermKind::Ty(ty).pack()
 961     }
 962 }
 963
 964 impl<'tcx> From<Const<'tcx>> for Term<'tcx> {
 965     fn from(c: Const<'tcx>) -> Self {
 966         TermKind::Const(c).pack()
 967     }
 968 }
 969
 970 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Term<'tcx> {
 971     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 972         self.unpack().hash_stable(hcx, hasher);
 973     }
 974 }
 975
 976 impl<'tcx> TypeFoldable<'tcx> for Term<'tcx> {
 977     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 978         Ok(self.unpack().try_fold_with(folder)?.pack())
 979     }
 980 }
 981
 982 impl<'tcx> TypeVisitable<'tcx> for Term<'tcx> {
 983     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 984         self.unpack().visit_with(visitor)
 985     }
 986 }
 987
 988 impl<'tcx, E: TyEncoder<I = TyCtxt<'tcx>>> Encodable<E> for Term<'tcx> {
 989     fn encode(&self, e: &mut E) {
 990         self.unpack().encode(e)
 991     }
 992 }
 993
 994 impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> Decodable<D> for Term<'tcx> {
 995     fn decode(d: &mut D) -> Self {
 996         let res: TermKind<'tcx> = Decodable::decode(d);
 997         res.pack()
 998     }
 999 }
1000
1001 impl<'tcx> Term<'tcx> {
1002     #[inline]
1003     pub fn unpack(self) -> TermKind<'tcx> {
1004         let ptr = self.ptr.get();
1005         // SAFETY: use of `Interned::new_unchecked` here is ok because these
1006         // pointers were originally created from `Interned` types in `pack()`,
1007         // and this is just going in the other direction.
1008         unsafe {
1009             match ptr & TAG_MASK {
1010                 TYPE_TAG => TermKind::Ty(Ty(Interned::new_unchecked(
1011                     &*((ptr & !TAG_MASK) as *const WithStableHash<ty::TyS<'tcx>>),
1012                 ))),
1013                 CONST_TAG => TermKind::Const(ty::Const(Interned::new_unchecked(
1014                     &*((ptr & !TAG_MASK) as *const ty::ConstS<'tcx>),
1015                 ))),
1016                 _ => core::intrinsics::unreachable(),
1017             }
1018         }
1019     }
1020
1021     pub fn ty(&self) -> Option<Ty<'tcx>> {
1022         if let TermKind::Ty(ty) = self.unpack() { Some(ty) } else { None }
1023     }
1024
1025     pub fn ct(&self) -> Option<Const<'tcx>> {
1026         if let TermKind::Const(c) = self.unpack() { Some(c) } else { None }
1027     }
1028
1029     pub fn into_arg(self) -> GenericArg<'tcx> {
1030         match self.unpack() {
1031             TermKind::Ty(ty) => ty.into(),
1032             TermKind::Const(c) => c.into(),
1033         }
1034     }
1035 }
1036
1037 const TAG_MASK: usize = 0b11;
1038 const TYPE_TAG: usize = 0b00;
1039 const CONST_TAG: usize = 0b01;
1040
1041 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, TyEncodable, TyDecodable)]
1042 #[derive(HashStable, TypeFoldable, TypeVisitable)]
1043 pub enum TermKind<'tcx> {
1044     Ty(Ty<'tcx>),
1045     Const(Const<'tcx>),
1046 }
1047
1048 impl<'tcx> TermKind<'tcx> {
1049     #[inline]
1050     fn pack(self) -> Term<'tcx> {
1051         let (tag, ptr) = match self {
1052             TermKind::Ty(ty) => {
1053                 // Ensure we can use the tag bits.
1054                 assert_eq!(mem::align_of_val(&*ty.0.0) & TAG_MASK, 0);
1055                 (TYPE_TAG, ty.0.0 as *const WithStableHash<ty::TyS<'tcx>> as usize)
1056             }
1057             TermKind::Const(ct) => {
1058                 // Ensure we can use the tag bits.
1059                 assert_eq!(mem::align_of_val(&*ct.0.0) & TAG_MASK, 0);
1060                 (CONST_TAG, ct.0.0 as *const ty::ConstS<'tcx> as usize)
1061             }
1062         };
1063
1064         Term { ptr: unsafe { NonZeroUsize::new_unchecked(ptr | tag) }, marker: PhantomData }
1065     }
1066 }
1067
1068 /// This kind of predicate has no *direct* correspondent in the
1069 /// syntax, but it roughly corresponds to the syntactic forms:
1070 ///
1071 /// 1. `T: TraitRef<..., Item = Type>`
1072 /// 2. `<T as TraitRef<...>>::Item == Type` (NYI)
1073 ///
1074 /// In particular, form #1 is "desugared" to the combination of a
1075 /// normal trait predicate (`T: TraitRef<...>`) and one of these
1076 /// predicates. Form #2 is a broader form in that it also permits
1077 /// equality between arbitrary types. Processing an instance of
1078 /// Form #2 eventually yields one of these `ProjectionPredicate`
1079 /// instances to normalize the LHS.
1080 #[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
1081 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
1082 pub struct ProjectionPredicate<'tcx> {
1083     pub projection_ty: ProjectionTy<'tcx>,
1084     pub term: Term<'tcx>,
1085 }
1086
1087 pub type PolyProjectionPredicate<'tcx> = Binder<'tcx, ProjectionPredicate<'tcx>>;
1088
1089 impl<'tcx> PolyProjectionPredicate<'tcx> {
1090     /// Returns the `DefId` of the trait of the associated item being projected.
1091     #[inline]
1092     pub fn trait_def_id(&self, tcx: TyCtxt<'tcx>) -> DefId {
1093         self.skip_binder().projection_ty.trait_def_id(tcx)
1094     }
1095
1096     /// Get the [PolyTraitRef] required for this projection to be well formed.
1097     /// Note that for generic associated types the predicates of the associated
1098     /// type also need to be checked.
1099     #[inline]
1100     pub fn required_poly_trait_ref(&self, tcx: TyCtxt<'tcx>) -> PolyTraitRef<'tcx> {
1101         // Note: unlike with `TraitRef::to_poly_trait_ref()`,
1102         // `self.0.trait_ref` is permitted to have escaping regions.
1103         // This is because here `self` has a `Binder` and so does our
1104         // return value, so we are preserving the number of binding
1105         // levels.
1106         self.map_bound(|predicate| predicate.projection_ty.trait_ref(tcx))
1107     }
1108
1109     pub fn term(&self) -> Binder<'tcx, Term<'tcx>> {
1110         self.map_bound(|predicate| predicate.term)
1111     }
1112
1113     /// The `DefId` of the `TraitItem` for the associated type.
1114     ///
1115     /// Note that this is not the `DefId` of the `TraitRef` containing this
1116     /// associated type, which is in `tcx.associated_item(projection_def_id()).container`.
1117     pub fn projection_def_id(&self) -> DefId {
1118         // Ok to skip binder since trait `DefId` does not care about regions.
1119         self.skip_binder().projection_ty.item_def_id
1120     }
1121 }
1122
1123 pub trait ToPolyTraitRef<'tcx> {
1124     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
1125 }
1126
1127 impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
1128     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
1129         self.map_bound_ref(|trait_pred| trait_pred.trait_ref)
1130     }
1131 }
1132
1133 pub trait ToPredicate<'tcx, Predicate> {
1134     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate;
1135 }
1136
1137 impl<'tcx, T> ToPredicate<'tcx, T> for T {
1138     fn to_predicate(self, _tcx: TyCtxt<'tcx>) -> T {
1139         self
1140     }
1141 }
1142
1143 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for Binder<'tcx, PredicateKind<'tcx>> {
1144     #[inline(always)]
1145     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1146         tcx.mk_predicate(self)
1147     }
1148 }
1149
1150 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyTraitPredicate<'tcx> {
1151     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1152         self.map_bound(PredicateKind::Trait).to_predicate(tcx)
1153     }
1154 }
1155
1156 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyRegionOutlivesPredicate<'tcx> {
1157     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1158         self.map_bound(PredicateKind::RegionOutlives).to_predicate(tcx)
1159     }
1160 }
1161
1162 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyTypeOutlivesPredicate<'tcx> {
1163     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1164         self.map_bound(PredicateKind::TypeOutlives).to_predicate(tcx)
1165     }
1166 }
1167
1168 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyProjectionPredicate<'tcx> {
1169     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1170         self.map_bound(PredicateKind::Projection).to_predicate(tcx)
1171     }
1172 }
1173
1174 impl<'tcx> Predicate<'tcx> {
1175     pub fn to_opt_poly_trait_pred(self) -> Option<PolyTraitPredicate<'tcx>> {
1176         let predicate = self.kind();
1177         match predicate.skip_binder() {
1178             PredicateKind::Trait(t) => Some(predicate.rebind(t)),
1179             PredicateKind::Projection(..)
1180             | PredicateKind::Subtype(..)
1181             | PredicateKind::Coerce(..)
1182             | PredicateKind::RegionOutlives(..)
1183             | PredicateKind::WellFormed(..)
1184             | PredicateKind::ObjectSafe(..)
1185             | PredicateKind::ClosureKind(..)
1186             | PredicateKind::TypeOutlives(..)
1187             | PredicateKind::ConstEvaluatable(..)
1188             | PredicateKind::ConstEquate(..)
1189             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1190         }
1191     }
1192
1193     pub fn to_opt_poly_projection_pred(self) -> Option<PolyProjectionPredicate<'tcx>> {
1194         let predicate = self.kind();
1195         match predicate.skip_binder() {
1196             PredicateKind::Projection(t) => Some(predicate.rebind(t)),
1197             PredicateKind::Trait(..)
1198             | PredicateKind::Subtype(..)
1199             | PredicateKind::Coerce(..)
1200             | PredicateKind::RegionOutlives(..)
1201             | PredicateKind::WellFormed(..)
1202             | PredicateKind::ObjectSafe(..)
1203             | PredicateKind::ClosureKind(..)
1204             | PredicateKind::TypeOutlives(..)
1205             | PredicateKind::ConstEvaluatable(..)
1206             | PredicateKind::ConstEquate(..)
1207             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1208         }
1209     }
1210
1211     pub fn to_opt_type_outlives(self) -> Option<PolyTypeOutlivesPredicate<'tcx>> {
1212         let predicate = self.kind();
1213         match predicate.skip_binder() {
1214             PredicateKind::TypeOutlives(data) => Some(predicate.rebind(data)),
1215             PredicateKind::Trait(..)
1216             | PredicateKind::Projection(..)
1217             | PredicateKind::Subtype(..)
1218             | PredicateKind::Coerce(..)
1219             | PredicateKind::RegionOutlives(..)
1220             | PredicateKind::WellFormed(..)
1221             | PredicateKind::ObjectSafe(..)
1222             | PredicateKind::ClosureKind(..)
1223             | PredicateKind::ConstEvaluatable(..)
1224             | PredicateKind::ConstEquate(..)
1225             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1226         }
1227     }
1228 }
1229
1230 /// Represents the bounds declared on a particular set of type
1231 /// parameters. Should eventually be generalized into a flag list of
1232 /// where-clauses. You can obtain an `InstantiatedPredicates` list from a
1233 /// `GenericPredicates` by using the `instantiate` method. Note that this method
1234 /// reflects an important semantic invariant of `InstantiatedPredicates`: while
1235 /// the `GenericPredicates` are expressed in terms of the bound type
1236 /// parameters of the impl/trait/whatever, an `InstantiatedPredicates` instance
1237 /// represented a set of bounds for some particular instantiation,
1238 /// meaning that the generic parameters have been substituted with
1239 /// their values.
1240 ///
1241 /// Example:
1242 /// ```ignore (illustrative)
1243 /// struct Foo<T, U: Bar<T>> { ... }
1244 /// ```
1245 /// Here, the `GenericPredicates` for `Foo` would contain a list of bounds like
1246 /// `[[], [U:Bar<T>]]`. Now if there were some particular reference
1247 /// like `Foo<isize,usize>`, then the `InstantiatedPredicates` would be `[[],
1248 /// [usize:Bar<isize>]]`.
1249 #[derive(Clone, Debug, TypeFoldable, TypeVisitable)]
1250 pub struct InstantiatedPredicates<'tcx> {
1251     pub predicates: Vec<Predicate<'tcx>>,
1252     pub spans: Vec<Span>,
1253 }
1254
1255 impl<'tcx> InstantiatedPredicates<'tcx> {
1256     pub fn empty() -> InstantiatedPredicates<'tcx> {
1257         InstantiatedPredicates { predicates: vec![], spans: vec![] }
1258     }
1259
1260     pub fn is_empty(&self) -> bool {
1261         self.predicates.is_empty()
1262     }
1263 }
1264
1265 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable, TyEncodable, TyDecodable, Lift)]
1266 #[derive(TypeFoldable, TypeVisitable)]
1267 pub struct OpaqueTypeKey<'tcx> {
1268     pub def_id: LocalDefId,
1269     pub substs: SubstsRef<'tcx>,
1270 }
1271
1272 #[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable, HashStable, TyEncodable, TyDecodable)]
1273 pub struct OpaqueHiddenType<'tcx> {
1274     /// The span of this particular definition of the opaque type. So
1275     /// for example:
1276     ///
1277     /// ```ignore (incomplete snippet)
1278     /// type Foo = impl Baz;
1279     /// fn bar() -> Foo {
1280     /// //          ^^^ This is the span we are looking for!
1281     /// }
1282     /// ```
1283     ///
1284     /// In cases where the fn returns `(impl Trait, impl Trait)` or
1285     /// other such combinations, the result is currently
1286     /// over-approximated, but better than nothing.
1287     pub span: Span,
1288
1289     /// The type variable that represents the value of the opaque type
1290     /// that we require. In other words, after we compile this function,
1291     /// we will be created a constraint like:
1292     /// ```ignore (pseudo-rust)
1293     /// Foo<'a, T> = ?C
1294     /// ```
1295     /// where `?C` is the value of this type variable. =) It may
1296     /// naturally refer to the type and lifetime parameters in scope
1297     /// in this function, though ultimately it should only reference
1298     /// those that are arguments to `Foo` in the constraint above. (In
1299     /// other words, `?C` should not include `'b`, even though it's a
1300     /// lifetime parameter on `foo`.)
1301     pub ty: Ty<'tcx>,
1302 }
1303
1304 impl<'tcx> OpaqueHiddenType<'tcx> {
1305     pub fn report_mismatch(&self, other: &Self, tcx: TyCtxt<'tcx>) {
1306         // Found different concrete types for the opaque type.
1307         let sub_diag = if self.span == other.span {
1308             TypeMismatchReason::ConflictType { span: self.span }
1309         } else {
1310             TypeMismatchReason::PreviousUse { span: self.span }
1311         };
1312         tcx.sess.emit_err(OpaqueHiddenTypeMismatch {
1313             self_ty: self.ty,
1314             other_ty: other.ty,
1315             other_span: other.span,
1316             sub: sub_diag,
1317         });
1318     }
1319
1320     #[instrument(level = "debug", skip(tcx), ret)]
1321     pub fn remap_generic_params_to_declaration_params(
1322         self,
1323         opaque_type_key: OpaqueTypeKey<'tcx>,
1324         tcx: TyCtxt<'tcx>,
1325         // typeck errors have subpar spans for opaque types, so delay error reporting until borrowck.
1326         ignore_errors: bool,
1327         origin: OpaqueTyOrigin,
1328     ) -> Self {
1329         let OpaqueTypeKey { def_id, substs } = opaque_type_key;
1330
1331         // Use substs to build up a reverse map from regions to their
1332         // identity mappings. This is necessary because of `impl
1333         // Trait` lifetimes are computed by replacing existing
1334         // lifetimes with 'static and remapping only those used in the
1335         // `impl Trait` return type, resulting in the parameters
1336         // shifting.
1337         let id_substs = InternalSubsts::identity_for_item(tcx, def_id.to_def_id());
1338         debug!(?id_substs);
1339
1340         // This zip may have several times the same lifetime in `substs` paired with a different
1341         // lifetime from `id_substs`.  Simply `collect`ing the iterator is the correct behaviour:
1342         // it will pick the last one, which is the one we introduced in the impl-trait desugaring.
1343         let map = substs.iter().zip(id_substs);
1344
1345         let map: FxHashMap<GenericArg<'tcx>, GenericArg<'tcx>> = match origin {
1346             // HACK: The HIR lowering for async fn does not generate
1347             // any `+ Captures<'x>` bounds for the `impl Future<...>`, so all async fns with lifetimes
1348             // would now fail to compile. We should probably just make hir lowering fill this in properly.
1349             OpaqueTyOrigin::AsyncFn(_) => map.collect(),
1350             OpaqueTyOrigin::FnReturn(_) | OpaqueTyOrigin::TyAlias => {
1351                 // Opaque types may only use regions that are bound. So for
1352                 // ```rust
1353                 // type Foo<'a, 'b, 'c> = impl Trait<'a> + 'b;
1354                 // ```
1355                 // we may not use `'c` in the hidden type.
1356                 let variances = tcx.variances_of(def_id);
1357                 debug!(?variances);
1358
1359                 map.filter(|(_, v)| {
1360                     let ty::GenericArgKind::Lifetime(lt) = v.unpack() else { return true };
1361                     let ty::ReEarlyBound(ebr) = lt.kind() else { bug!() };
1362                     variances[ebr.index as usize] == ty::Variance::Invariant
1363                 })
1364                 .collect()
1365             }
1366         };
1367         debug!("map = {:#?}", map);
1368
1369         // Convert the type from the function into a type valid outside
1370         // the function, by replacing invalid regions with 'static,
1371         // after producing an error for each of them.
1372         self.fold_with(&mut opaque_types::ReverseMapper::new(tcx, map, self.span, ignore_errors))
1373     }
1374 }
1375
1376 /// The "placeholder index" fully defines a placeholder region, type, or const. Placeholders are
1377 /// identified by both a universe, as well as a name residing within that universe. Distinct bound
1378 /// regions/types/consts within the same universe simply have an unknown relationship to one
1379 /// another.
1380 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
1381 #[derive(HashStable, TyEncodable, TyDecodable)]
1382 pub struct Placeholder<T> {
1383     pub universe: UniverseIndex,
1384     pub name: T,
1385 }
1386
1387 pub type PlaceholderRegion = Placeholder<BoundRegionKind>;
1388
1389 pub type PlaceholderType = Placeholder<BoundVar>;
1390
1391 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable)]
1392 #[derive(TyEncodable, TyDecodable, PartialOrd, Ord)]
1393 pub struct BoundConst<'tcx> {
1394     pub var: BoundVar,
1395     pub ty: Ty<'tcx>,
1396 }
1397
1398 pub type PlaceholderConst<'tcx> = Placeholder<BoundVar>;
1399
1400 /// A `DefId` which, in case it is a const argument, is potentially bundled with
1401 /// the `DefId` of the generic parameter it instantiates.
1402 ///
1403 /// This is used to avoid calls to `type_of` for const arguments during typeck
1404 /// which cause cycle errors.
1405 ///
1406 /// ```rust
1407 /// struct A;
1408 /// impl A {
1409 ///     fn foo<const N: usize>(&self) -> [u8; N] { [0; N] }
1410 ///     //           ^ const parameter
1411 /// }
1412 /// struct B;
1413 /// impl B {
1414 ///     fn foo<const M: u8>(&self) -> usize { 42 }
1415 ///     //           ^ const parameter
1416 /// }
1417 ///
1418 /// fn main() {
1419 ///     let a = A;
1420 ///     let _b = a.foo::<{ 3 + 7 }>();
1421 ///     //               ^^^^^^^^^ const argument
1422 /// }
1423 /// ```
1424 ///
1425 /// Let's look at the call `a.foo::<{ 3 + 7 }>()` here. We do not know
1426 /// which `foo` is used until we know the type of `a`.
1427 ///
1428 /// We only know the type of `a` once we are inside of `typeck(main)`.
1429 /// We also end up normalizing the type of `_b` during `typeck(main)` which
1430 /// requires us to evaluate the const argument.
1431 ///
1432 /// To evaluate that const argument we need to know its type,
1433 /// which we would get using `type_of(const_arg)`. This requires us to
1434 /// resolve `foo` as it can be either `usize` or `u8` in this example.
1435 /// However, resolving `foo` once again requires `typeck(main)` to get the type of `a`,
1436 /// which results in a cycle.
1437 ///
1438 /// In short we must not call `type_of(const_arg)` during `typeck(main)`.
1439 ///
1440 /// When first creating the `ty::Const` of the const argument inside of `typeck` we have
1441 /// already resolved `foo` so we know which const parameter this argument instantiates.
1442 /// This means that we also know the expected result of `type_of(const_arg)` even if we
1443 /// aren't allowed to call that query: it is equal to `type_of(const_param)` which is
1444 /// trivial to compute.
1445 ///
1446 /// If we now want to use that constant in a place which potentially needs its type
1447 /// we also pass the type of its `const_param`. This is the point of `WithOptConstParam`,
1448 /// except that instead of a `Ty` we bundle the `DefId` of the const parameter.
1449 /// Meaning that we need to use `type_of(const_param_did)` if `const_param_did` is `Some`
1450 /// to get the type of `did`.
1451 #[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable, Lift, TyEncodable, TyDecodable)]
1452 #[derive(PartialEq, Eq, PartialOrd, Ord)]
1453 #[derive(Hash, HashStable)]
1454 pub struct WithOptConstParam<T> {
1455     pub did: T,
1456     /// The `DefId` of the corresponding generic parameter in case `did` is
1457     /// a const argument.
1458     ///
1459     /// Note that even if `did` is a const argument, this may still be `None`.
1460     /// All queries taking `WithOptConstParam` start by calling `tcx.opt_const_param_of(def.did)`
1461     /// to potentially update `param_did` in the case it is `None`.
1462     pub const_param_did: Option<DefId>,
1463 }
1464
1465 impl<T> WithOptConstParam<T> {
1466     /// Creates a new `WithOptConstParam` setting `const_param_did` to `None`.
1467     #[inline(always)]
1468     pub fn unknown(did: T) -> WithOptConstParam<T> {
1469         WithOptConstParam { did, const_param_did: None }
1470     }
1471 }
1472
1473 impl WithOptConstParam<LocalDefId> {
1474     /// Returns `Some((did, param_did))` if `def_id` is a const argument,
1475     /// `None` otherwise.
1476     #[inline(always)]
1477     pub fn try_lookup(did: LocalDefId, tcx: TyCtxt<'_>) -> Option<(LocalDefId, DefId)> {
1478         tcx.opt_const_param_of(did).map(|param_did| (did, param_did))
1479     }
1480
1481     /// In case `self` is unknown but `self.did` is a const argument, this returns
1482     /// a `WithOptConstParam` with the correct `const_param_did`.
1483     #[inline(always)]
1484     pub fn try_upgrade(self, tcx: TyCtxt<'_>) -> Option<WithOptConstParam<LocalDefId>> {
1485         if self.const_param_did.is_none() {
1486             if let const_param_did @ Some(_) = tcx.opt_const_param_of(self.did) {
1487                 return Some(WithOptConstParam { did: self.did, const_param_did });
1488             }
1489         }
1490
1491         None
1492     }
1493
1494     pub fn to_global(self) -> WithOptConstParam<DefId> {
1495         WithOptConstParam { did: self.did.to_def_id(), const_param_did: self.const_param_did }
1496     }
1497
1498     pub fn def_id_for_type_of(self) -> DefId {
1499         if let Some(did) = self.const_param_did { did } else { self.did.to_def_id() }
1500     }
1501 }
1502
1503 impl WithOptConstParam<DefId> {
1504     pub fn as_local(self) -> Option<WithOptConstParam<LocalDefId>> {
1505         self.did
1506             .as_local()
1507             .map(|did| WithOptConstParam { did, const_param_did: self.const_param_did })
1508     }
1509
1510     pub fn as_const_arg(self) -> Option<(LocalDefId, DefId)> {
1511         if let Some(param_did) = self.const_param_did {
1512             if let Some(did) = self.did.as_local() {
1513                 return Some((did, param_did));
1514             }
1515         }
1516
1517         None
1518     }
1519
1520     pub fn is_local(self) -> bool {
1521         self.did.is_local()
1522     }
1523
1524     pub fn def_id_for_type_of(self) -> DefId {
1525         self.const_param_did.unwrap_or(self.did)
1526     }
1527 }
1528
1529 /// When type checking, we use the `ParamEnv` to track
1530 /// details about the set of where-clauses that are in scope at this
1531 /// particular point.
1532 #[derive(Copy, Clone, Hash, PartialEq, Eq)]
1533 pub struct ParamEnv<'tcx> {
1534     /// This packs both caller bounds and the reveal enum into one pointer.
1535     ///
1536     /// Caller bounds are `Obligation`s that the caller must satisfy. This is
1537     /// basically the set of bounds on the in-scope type parameters, translated
1538     /// into `Obligation`s, and elaborated and normalized.
1539     ///
1540     /// Use the `caller_bounds()` method to access.
1541     ///
1542     /// Typically, this is `Reveal::UserFacing`, but during codegen we
1543     /// want `Reveal::All`.
1544     ///
1545     /// Note: This is packed, use the reveal() method to access it.
1546     packed: CopyTaggedPtr<&'tcx List<Predicate<'tcx>>, ParamTag, true>,
1547 }
1548
1549 #[derive(Copy, Clone)]
1550 struct ParamTag {
1551     reveal: traits::Reveal,
1552     constness: hir::Constness,
1553 }
1554
1555 unsafe impl rustc_data_structures::tagged_ptr::Tag for ParamTag {
1556     const BITS: usize = 2;
1557     #[inline]
1558     fn into_usize(self) -> usize {
1559         match self {
1560             Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::NotConst } => 0,
1561             Self { reveal: traits::Reveal::All, constness: hir::Constness::NotConst } => 1,
1562             Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::Const } => 2,
1563             Self { reveal: traits::Reveal::All, constness: hir::Constness::Const } => 3,
1564         }
1565     }
1566     #[inline]
1567     unsafe fn from_usize(ptr: usize) -> Self {
1568         match ptr {
1569             0 => Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::NotConst },
1570             1 => Self { reveal: traits::Reveal::All, constness: hir::Constness::NotConst },
1571             2 => Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::Const },
1572             3 => Self { reveal: traits::Reveal::All, constness: hir::Constness::Const },
1573             _ => std::hint::unreachable_unchecked(),
1574         }
1575     }
1576 }
1577
1578 impl<'tcx> fmt::Debug for ParamEnv<'tcx> {
1579     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1580         f.debug_struct("ParamEnv")
1581             .field("caller_bounds", &self.caller_bounds())
1582             .field("reveal", &self.reveal())
1583             .field("constness", &self.constness())
1584             .finish()
1585     }
1586 }
1587
1588 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for ParamEnv<'tcx> {
1589     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
1590         self.caller_bounds().hash_stable(hcx, hasher);
1591         self.reveal().hash_stable(hcx, hasher);
1592         self.constness().hash_stable(hcx, hasher);
1593     }
1594 }
1595
1596 impl<'tcx> TypeFoldable<'tcx> for ParamEnv<'tcx> {
1597     fn try_fold_with<F: ty::fold::FallibleTypeFolder<'tcx>>(
1598         self,
1599         folder: &mut F,
1600     ) -> Result<Self, F::Error> {
1601         Ok(ParamEnv::new(
1602             self.caller_bounds().try_fold_with(folder)?,
1603             self.reveal().try_fold_with(folder)?,
1604             self.constness(),
1605         ))
1606     }
1607 }
1608
1609 impl<'tcx> TypeVisitable<'tcx> for ParamEnv<'tcx> {
1610     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1611         self.caller_bounds().visit_with(visitor)?;
1612         self.reveal().visit_with(visitor)
1613     }
1614 }
1615
1616 impl<'tcx> ParamEnv<'tcx> {
1617     /// Construct a trait environment suitable for contexts where
1618     /// there are no where-clauses in scope. Hidden types (like `impl
1619     /// Trait`) are left hidden, so this is suitable for ordinary
1620     /// type-checking.
1621     #[inline]
1622     pub fn empty() -> Self {
1623         Self::new(List::empty(), Reveal::UserFacing, hir::Constness::NotConst)
1624     }
1625
1626     #[inline]
1627     pub fn caller_bounds(self) -> &'tcx List<Predicate<'tcx>> {
1628         self.packed.pointer()
1629     }
1630
1631     #[inline]
1632     pub fn reveal(self) -> traits::Reveal {
1633         self.packed.tag().reveal
1634     }
1635
1636     #[inline]
1637     pub fn constness(self) -> hir::Constness {
1638         self.packed.tag().constness
1639     }
1640
1641     #[inline]
1642     pub fn is_const(self) -> bool {
1643         self.packed.tag().constness == hir::Constness::Const
1644     }
1645
1646     /// Construct a trait environment with no where-clauses in scope
1647     /// where the values of all `impl Trait` and other hidden types
1648     /// are revealed. This is suitable for monomorphized, post-typeck
1649     /// environments like codegen or doing optimizations.
1650     ///
1651     /// N.B., if you want to have predicates in scope, use `ParamEnv::new`,
1652     /// or invoke `param_env.with_reveal_all()`.
1653     #[inline]
1654     pub fn reveal_all() -> Self {
1655         Self::new(List::empty(), Reveal::All, hir::Constness::NotConst)
1656     }
1657
1658     /// Construct a trait environment with the given set of predicates.
1659     #[inline]
1660     pub fn new(
1661         caller_bounds: &'tcx List<Predicate<'tcx>>,
1662         reveal: Reveal,
1663         constness: hir::Constness,
1664     ) -> Self {
1665         ty::ParamEnv { packed: CopyTaggedPtr::new(caller_bounds, ParamTag { reveal, constness }) }
1666     }
1667
1668     pub fn with_user_facing(mut self) -> Self {
1669         self.packed.set_tag(ParamTag { reveal: Reveal::UserFacing, ..self.packed.tag() });
1670         self
1671     }
1672
1673     #[inline]
1674     pub fn with_constness(mut self, constness: hir::Constness) -> Self {
1675         self.packed.set_tag(ParamTag { constness, ..self.packed.tag() });
1676         self
1677     }
1678
1679     #[inline]
1680     pub fn with_const(mut self) -> Self {
1681         self.packed.set_tag(ParamTag { constness: hir::Constness::Const, ..self.packed.tag() });
1682         self
1683     }
1684
1685     #[inline]
1686     pub fn without_const(mut self) -> Self {
1687         self.packed.set_tag(ParamTag { constness: hir::Constness::NotConst, ..self.packed.tag() });
1688         self
1689     }
1690
1691     #[inline]
1692     pub fn remap_constness_with(&mut self, mut constness: ty::BoundConstness) {
1693         *self = self.with_constness(constness.and(self.constness()))
1694     }
1695
1696     /// Returns a new parameter environment with the same clauses, but
1697     /// which "reveals" the true results of projections in all cases
1698     /// (even for associated types that are specializable). This is
1699     /// the desired behavior during codegen and certain other special
1700     /// contexts; normally though we want to use `Reveal::UserFacing`,
1701     /// which is the default.
1702     /// All opaque types in the caller_bounds of the `ParamEnv`
1703     /// will be normalized to their underlying types.
1704     /// See PR #65989 and issue #65918 for more details
1705     pub fn with_reveal_all_normalized(self, tcx: TyCtxt<'tcx>) -> Self {
1706         if self.packed.tag().reveal == traits::Reveal::All {
1707             return self;
1708         }
1709
1710         ParamEnv::new(
1711             tcx.normalize_opaque_types(self.caller_bounds()),
1712             Reveal::All,
1713             self.constness(),
1714         )
1715     }
1716
1717     /// Returns this same environment but with no caller bounds.
1718     #[inline]
1719     pub fn without_caller_bounds(self) -> Self {
1720         Self::new(List::empty(), self.reveal(), self.constness())
1721     }
1722
1723     /// Creates a suitable environment in which to perform trait
1724     /// queries on the given value. When type-checking, this is simply
1725     /// the pair of the environment plus value. But when reveal is set to
1726     /// All, then if `value` does not reference any type parameters, we will
1727     /// pair it with the empty environment. This improves caching and is generally
1728     /// invisible.
1729     ///
1730     /// N.B., we preserve the environment when type-checking because it
1731     /// is possible for the user to have wacky where-clauses like
1732     /// `where Box<u32>: Copy`, which are clearly never
1733     /// satisfiable. We generally want to behave as if they were true,
1734     /// although the surrounding function is never reachable.
1735     pub fn and<T: TypeVisitable<'tcx>>(self, value: T) -> ParamEnvAnd<'tcx, T> {
1736         match self.reveal() {
1737             Reveal::UserFacing => ParamEnvAnd { param_env: self, value },
1738
1739             Reveal::All => {
1740                 if value.is_global() {
1741                     ParamEnvAnd { param_env: self.without_caller_bounds(), value }
1742                 } else {
1743                     ParamEnvAnd { param_env: self, value }
1744                 }
1745             }
1746         }
1747     }
1748 }
1749
1750 // FIXME(ecstaticmorse): Audit all occurrences of `without_const().to_predicate(tcx)` to ensure that
1751 // the constness of trait bounds is being propagated correctly.
1752 impl<'tcx> PolyTraitRef<'tcx> {
1753     #[inline]
1754     pub fn with_constness(self, constness: BoundConstness) -> PolyTraitPredicate<'tcx> {
1755         self.map_bound(|trait_ref| ty::TraitPredicate {
1756             trait_ref,
1757             constness,
1758             polarity: ty::ImplPolarity::Positive,
1759         })
1760     }
1761
1762     #[inline]
1763     pub fn without_const(self) -> PolyTraitPredicate<'tcx> {
1764         self.with_constness(BoundConstness::NotConst)
1765     }
1766 }
1767
1768 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
1769 #[derive(HashStable, Lift)]
1770 pub struct ParamEnvAnd<'tcx, T> {
1771     pub param_env: ParamEnv<'tcx>,
1772     pub value: T,
1773 }
1774
1775 impl<'tcx, T> ParamEnvAnd<'tcx, T> {
1776     pub fn into_parts(self) -> (ParamEnv<'tcx>, T) {
1777         (self.param_env, self.value)
1778     }
1779
1780     #[inline]
1781     pub fn without_const(mut self) -> Self {
1782         self.param_env = self.param_env.without_const();
1783         self
1784     }
1785 }
1786
1787 #[derive(Copy, Clone, Debug, HashStable, Encodable, Decodable)]
1788 pub struct Destructor {
1789     /// The `DefId` of the destructor method
1790     pub did: DefId,
1791     /// The constness of the destructor method
1792     pub constness: hir::Constness,
1793 }
1794
1795 bitflags! {
1796     #[derive(HashStable, TyEncodable, TyDecodable)]
1797     pub struct VariantFlags: u32 {
1798         const NO_VARIANT_FLAGS        = 0;
1799         /// Indicates whether the field list of this variant is `#[non_exhaustive]`.
1800         const IS_FIELD_LIST_NON_EXHAUSTIVE = 1 << 0;
1801         /// Indicates whether this variant was obtained as part of recovering from
1802         /// a syntactic error. May be incomplete or bogus.
1803         const IS_RECOVERED = 1 << 1;
1804     }
1805 }
1806
1807 /// Definition of a variant -- a struct's fields or an enum variant.
1808 #[derive(Debug, HashStable, TyEncodable, TyDecodable)]
1809 pub struct VariantDef {
1810     /// `DefId` that identifies the variant itself.
1811     /// If this variant belongs to a struct or union, then this is a copy of its `DefId`.
1812     pub def_id: DefId,
1813     /// `DefId` that identifies the variant's constructor.
1814     /// If this variant is a struct variant, then this is `None`.
1815     pub ctor: Option<(CtorKind, DefId)>,
1816     /// Variant or struct name.
1817     pub name: Symbol,
1818     /// Discriminant of this variant.
1819     pub discr: VariantDiscr,
1820     /// Fields of this variant.
1821     pub fields: Vec<FieldDef>,
1822     /// Flags of the variant (e.g. is field list non-exhaustive)?
1823     flags: VariantFlags,
1824 }
1825
1826 impl VariantDef {
1827     /// Creates a new `VariantDef`.
1828     ///
1829     /// `variant_did` is the `DefId` that identifies the enum variant (if this `VariantDef`
1830     /// represents an enum variant).
1831     ///
1832     /// `ctor_did` is the `DefId` that identifies the constructor of unit or
1833     /// tuple-variants/structs. If this is a `struct`-variant then this should be `None`.
1834     ///
1835     /// `parent_did` is the `DefId` of the `AdtDef` representing the enum or struct that
1836     /// owns this variant. It is used for checking if a struct has `#[non_exhaustive]` w/out having
1837     /// to go through the redirect of checking the ctor's attributes - but compiling a small crate
1838     /// requires loading the `AdtDef`s for all the structs in the universe (e.g., coherence for any
1839     /// built-in trait), and we do not want to load attributes twice.
1840     ///
1841     /// If someone speeds up attribute loading to not be a performance concern, they can
1842     /// remove this hack and use the constructor `DefId` everywhere.
1843     pub fn new(
1844         name: Symbol,
1845         variant_did: Option<DefId>,
1846         ctor: Option<(CtorKind, DefId)>,
1847         discr: VariantDiscr,
1848         fields: Vec<FieldDef>,
1849         adt_kind: AdtKind,
1850         parent_did: DefId,
1851         recovered: bool,
1852         is_field_list_non_exhaustive: bool,
1853     ) -> Self {
1854         debug!(
1855             "VariantDef::new(name = {:?}, variant_did = {:?}, ctor = {:?}, discr = {:?},
1856              fields = {:?}, adt_kind = {:?}, parent_did = {:?})",
1857             name, variant_did, ctor, discr, fields, adt_kind, parent_did,
1858         );
1859
1860         let mut flags = VariantFlags::NO_VARIANT_FLAGS;
1861         if is_field_list_non_exhaustive {
1862             flags |= VariantFlags::IS_FIELD_LIST_NON_EXHAUSTIVE;
1863         }
1864
1865         if recovered {
1866             flags |= VariantFlags::IS_RECOVERED;
1867         }
1868
1869         VariantDef { def_id: variant_did.unwrap_or(parent_did), ctor, name, discr, fields, flags }
1870     }
1871
1872     /// Is this field list non-exhaustive?
1873     #[inline]
1874     pub fn is_field_list_non_exhaustive(&self) -> bool {
1875         self.flags.intersects(VariantFlags::IS_FIELD_LIST_NON_EXHAUSTIVE)
1876     }
1877
1878     /// Was this variant obtained as part of recovering from a syntactic error?
1879     #[inline]
1880     pub fn is_recovered(&self) -> bool {
1881         self.flags.intersects(VariantFlags::IS_RECOVERED)
1882     }
1883
1884     /// Computes the `Ident` of this variant by looking up the `Span`
1885     pub fn ident(&self, tcx: TyCtxt<'_>) -> Ident {
1886         Ident::new(self.name, tcx.def_ident_span(self.def_id).unwrap())
1887     }
1888
1889     #[inline]
1890     pub fn ctor_kind(&self) -> Option<CtorKind> {
1891         self.ctor.map(|(kind, _)| kind)
1892     }
1893
1894     #[inline]
1895     pub fn ctor_def_id(&self) -> Option<DefId> {
1896         self.ctor.map(|(_, def_id)| def_id)
1897     }
1898 }
1899
1900 impl PartialEq for VariantDef {
1901     #[inline]
1902     fn eq(&self, other: &Self) -> bool {
1903         // There should be only one `VariantDef` for each `def_id`, therefore
1904         // it is fine to implement `PartialEq` only based on `def_id`.
1905         //
1906         // Below, we exhaustively destructure `self` and `other` so that if the
1907         // definition of `VariantDef` changes, a compile-error will be produced,
1908         // reminding us to revisit this assumption.
1909
1910         let Self { def_id: lhs_def_id, ctor: _, name: _, discr: _, fields: _, flags: _ } = &self;
1911         let Self { def_id: rhs_def_id, ctor: _, name: _, discr: _, fields: _, flags: _ } = other;
1912         lhs_def_id == rhs_def_id
1913     }
1914 }
1915
1916 impl Eq for VariantDef {}
1917
1918 impl Hash for VariantDef {
1919     #[inline]
1920     fn hash<H: Hasher>(&self, s: &mut H) {
1921         // There should be only one `VariantDef` for each `def_id`, therefore
1922         // it is fine to implement `Hash` only based on `def_id`.
1923         //
1924         // Below, we exhaustively destructure `self` so that if the definition
1925         // of `VariantDef` changes, a compile-error will be produced, reminding
1926         // us to revisit this assumption.
1927
1928         let Self { def_id, ctor: _, name: _, discr: _, fields: _, flags: _ } = &self;
1929         def_id.hash(s)
1930     }
1931 }
1932
1933 #[derive(Copy, Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
1934 pub enum VariantDiscr {
1935     /// Explicit value for this variant, i.e., `X = 123`.
1936     /// The `DefId` corresponds to the embedded constant.
1937     Explicit(DefId),
1938
1939     /// The previous variant's discriminant plus one.
1940     /// For efficiency reasons, the distance from the
1941     /// last `Explicit` discriminant is being stored,
1942     /// or `0` for the first variant, if it has none.
1943     Relative(u32),
1944 }
1945
1946 #[derive(Debug, HashStable, TyEncodable, TyDecodable)]
1947 pub struct FieldDef {
1948     pub did: DefId,
1949     pub name: Symbol,
1950     pub vis: Visibility<DefId>,
1951 }
1952
1953 impl PartialEq for FieldDef {
1954     #[inline]
1955     fn eq(&self, other: &Self) -> bool {
1956         // There should be only one `FieldDef` for each `did`, therefore it is
1957         // fine to implement `PartialEq` only based on `did`.
1958         //
1959         // Below, we exhaustively destructure `self` so that if the definition
1960         // of `FieldDef` changes, a compile-error will be produced, reminding
1961         // us to revisit this assumption.
1962
1963         let Self { did: lhs_did, name: _, vis: _ } = &self;
1964
1965         let Self { did: rhs_did, name: _, vis: _ } = other;
1966
1967         lhs_did == rhs_did
1968     }
1969 }
1970
1971 impl Eq for FieldDef {}
1972
1973 impl Hash for FieldDef {
1974     #[inline]
1975     fn hash<H: Hasher>(&self, s: &mut H) {
1976         // There should be only one `FieldDef` for each `did`, therefore it is
1977         // fine to implement `Hash` only based on `did`.
1978         //
1979         // Below, we exhaustively destructure `self` so that if the definition
1980         // of `FieldDef` changes, a compile-error will be produced, reminding
1981         // us to revisit this assumption.
1982
1983         let Self { did, name: _, vis: _ } = &self;
1984
1985         did.hash(s)
1986     }
1987 }
1988
1989 bitflags! {
1990     #[derive(TyEncodable, TyDecodable, Default, HashStable)]
1991     pub struct ReprFlags: u8 {
1992         const IS_C               = 1 << 0;
1993         const IS_SIMD            = 1 << 1;
1994         const IS_TRANSPARENT     = 1 << 2;
1995         // Internal only for now. If true, don't reorder fields.
1996         const IS_LINEAR          = 1 << 3;
1997         // If true, the type's layout can be randomized using
1998         // the seed stored in `ReprOptions.layout_seed`
1999         const RANDOMIZE_LAYOUT   = 1 << 4;
2000         // Any of these flags being set prevent field reordering optimisation.
2001         const IS_UNOPTIMISABLE   = ReprFlags::IS_C.bits
2002                                  | ReprFlags::IS_SIMD.bits
2003                                  | ReprFlags::IS_LINEAR.bits;
2004     }
2005 }
2006
2007 /// Represents the repr options provided by the user,
2008 #[derive(Copy, Clone, Debug, Eq, PartialEq, TyEncodable, TyDecodable, Default, HashStable)]
2009 pub struct ReprOptions {
2010     pub int: Option<attr::IntType>,
2011     pub align: Option<Align>,
2012     pub pack: Option<Align>,
2013     pub flags: ReprFlags,
2014     /// The seed to be used for randomizing a type's layout
2015     ///
2016     /// Note: This could technically be a `[u8; 16]` (a `u128`) which would
2017     /// be the "most accurate" hash as it'd encompass the item and crate
2018     /// hash without loss, but it does pay the price of being larger.
2019     /// Everything's a tradeoff, a `u64` seed should be sufficient for our
2020     /// purposes (primarily `-Z randomize-layout`)
2021     pub field_shuffle_seed: u64,
2022 }
2023
2024 impl ReprOptions {
2025     pub fn new(tcx: TyCtxt<'_>, did: DefId) -> ReprOptions {
2026         let mut flags = ReprFlags::empty();
2027         let mut size = None;
2028         let mut max_align: Option<Align> = None;
2029         let mut min_pack: Option<Align> = None;
2030
2031         // Generate a deterministically-derived seed from the item's path hash
2032         // to allow for cross-crate compilation to actually work
2033         let mut field_shuffle_seed = tcx.def_path_hash(did).0.to_smaller_hash();
2034
2035         // If the user defined a custom seed for layout randomization, xor the item's
2036         // path hash with the user defined seed, this will allowing determinism while
2037         // still allowing users to further randomize layout generation for e.g. fuzzing
2038         if let Some(user_seed) = tcx.sess.opts.unstable_opts.layout_seed {
2039             field_shuffle_seed ^= user_seed;
2040         }
2041
2042         for attr in tcx.get_attrs(did, sym::repr) {
2043             for r in attr::parse_repr_attr(&tcx.sess, attr) {
2044                 flags.insert(match r {
2045                     attr::ReprC => ReprFlags::IS_C,
2046                     attr::ReprPacked(pack) => {
2047                         let pack = Align::from_bytes(pack as u64).unwrap();
2048                         min_pack = Some(if let Some(min_pack) = min_pack {
2049                             min_pack.min(pack)
2050                         } else {
2051                             pack
2052                         });
2053                         ReprFlags::empty()
2054                     }
2055                     attr::ReprTransparent => ReprFlags::IS_TRANSPARENT,
2056                     attr::ReprSimd => ReprFlags::IS_SIMD,
2057                     attr::ReprInt(i) => {
2058                         size = Some(i);
2059                         ReprFlags::empty()
2060                     }
2061                     attr::ReprAlign(align) => {
2062                         max_align = max_align.max(Some(Align::from_bytes(align as u64).unwrap()));
2063                         ReprFlags::empty()
2064                     }
2065                 });
2066             }
2067         }
2068
2069         // If `-Z randomize-layout` was enabled for the type definition then we can
2070         // consider performing layout randomization
2071         if tcx.sess.opts.unstable_opts.randomize_layout {
2072             flags.insert(ReprFlags::RANDOMIZE_LAYOUT);
2073         }
2074
2075         // This is here instead of layout because the choice must make it into metadata.
2076         if !tcx.consider_optimizing(|| format!("Reorder fields of {:?}", tcx.def_path_str(did))) {
2077             flags.insert(ReprFlags::IS_LINEAR);
2078         }
2079
2080         Self { int: size, align: max_align, pack: min_pack, flags, field_shuffle_seed }
2081     }
2082
2083     #[inline]
2084     pub fn simd(&self) -> bool {
2085         self.flags.contains(ReprFlags::IS_SIMD)
2086     }
2087
2088     #[inline]
2089     pub fn c(&self) -> bool {
2090         self.flags.contains(ReprFlags::IS_C)
2091     }
2092
2093     #[inline]
2094     pub fn packed(&self) -> bool {
2095         self.pack.is_some()
2096     }
2097
2098     #[inline]
2099     pub fn transparent(&self) -> bool {
2100         self.flags.contains(ReprFlags::IS_TRANSPARENT)
2101     }
2102
2103     #[inline]
2104     pub fn linear(&self) -> bool {
2105         self.flags.contains(ReprFlags::IS_LINEAR)
2106     }
2107
2108     /// Returns the discriminant type, given these `repr` options.
2109     /// This must only be called on enums!
2110     pub fn discr_type(&self) -> attr::IntType {
2111         self.int.unwrap_or(attr::SignedInt(ast::IntTy::Isize))
2112     }
2113
2114     /// Returns `true` if this `#[repr()]` should inhabit "smart enum
2115     /// layout" optimizations, such as representing `Foo<&T>` as a
2116     /// single pointer.
2117     pub fn inhibit_enum_layout_opt(&self) -> bool {
2118         self.c() || self.int.is_some()
2119     }
2120
2121     /// Returns `true` if this `#[repr()]` should inhibit struct field reordering
2122     /// optimizations, such as with `repr(C)`, `repr(packed(1))`, or `repr(<int>)`.
2123     pub fn inhibit_struct_field_reordering_opt(&self) -> bool {
2124         if let Some(pack) = self.pack {
2125             if pack.bytes() == 1 {
2126                 return true;
2127             }
2128         }
2129
2130         self.flags.intersects(ReprFlags::IS_UNOPTIMISABLE) || self.int.is_some()
2131     }
2132
2133     /// Returns `true` if this type is valid for reordering and `-Z randomize-layout`
2134     /// was enabled for its declaration crate
2135     pub fn can_randomize_type_layout(&self) -> bool {
2136         !self.inhibit_struct_field_reordering_opt()
2137             && self.flags.contains(ReprFlags::RANDOMIZE_LAYOUT)
2138     }
2139
2140     /// Returns `true` if this `#[repr()]` should inhibit union ABI optimisations.
2141     pub fn inhibit_union_abi_opt(&self) -> bool {
2142         self.c()
2143     }
2144 }
2145
2146 impl<'tcx> FieldDef {
2147     /// Returns the type of this field. The resulting type is not normalized. The `subst` is
2148     /// typically obtained via the second field of [`TyKind::Adt`].
2149     pub fn ty(&self, tcx: TyCtxt<'tcx>, subst: SubstsRef<'tcx>) -> Ty<'tcx> {
2150         tcx.bound_type_of(self.did).subst(tcx, subst)
2151     }
2152
2153     /// Computes the `Ident` of this variant by looking up the `Span`
2154     pub fn ident(&self, tcx: TyCtxt<'_>) -> Ident {
2155         Ident::new(self.name, tcx.def_ident_span(self.did).unwrap())
2156     }
2157 }
2158
2159 pub type Attributes<'tcx> = impl Iterator<Item = &'tcx ast::Attribute>;
2160 #[derive(Debug, PartialEq, Eq)]
2161 pub enum ImplOverlapKind {
2162     /// These impls are always allowed to overlap.
2163     Permitted {
2164         /// Whether or not the impl is permitted due to the trait being a `#[marker]` trait
2165         marker: bool,
2166     },
2167     /// These impls are allowed to overlap, but that raises
2168     /// an issue #33140 future-compatibility warning.
2169     ///
2170     /// Some background: in Rust 1.0, the trait-object types `Send + Sync` (today's
2171     /// `dyn Send + Sync`) and `Sync + Send` (now `dyn Sync + Send`) were different.
2172     ///
2173     /// The widely-used version 0.1.0 of the crate `traitobject` had accidentally relied
2174     /// that difference, making what reduces to the following set of impls:
2175     ///
2176     /// ```compile_fail,(E0119)
2177     /// trait Trait {}
2178     /// impl Trait for dyn Send + Sync {}
2179     /// impl Trait for dyn Sync + Send {}
2180     /// ```
2181     ///
2182     /// Obviously, once we made these types be identical, that code causes a coherence
2183     /// error and a fairly big headache for us. However, luckily for us, the trait
2184     /// `Trait` used in this case is basically a marker trait, and therefore having
2185     /// overlapping impls for it is sound.
2186     ///
2187     /// To handle this, we basically regard the trait as a marker trait, with an additional
2188     /// future-compatibility warning. To avoid accidentally "stabilizing" this feature,
2189     /// it has the following restrictions:
2190     ///
2191     /// 1. The trait must indeed be a marker-like trait (i.e., no items), and must be
2192     /// positive impls.
2193     /// 2. The trait-ref of both impls must be equal.
2194     /// 3. The trait-ref of both impls must be a trait object type consisting only of
2195     /// marker traits.
2196     /// 4. Neither of the impls can have any where-clauses.
2197     ///
2198     /// Once `traitobject` 0.1.0 is no longer an active concern, this hack can be removed.
2199     Issue33140,
2200 }
2201
2202 impl<'tcx> TyCtxt<'tcx> {
2203     pub fn typeck_body(self, body: hir::BodyId) -> &'tcx TypeckResults<'tcx> {
2204         self.typeck(self.hir().body_owner_def_id(body))
2205     }
2206
2207     pub fn provided_trait_methods(self, id: DefId) -> impl 'tcx + Iterator<Item = &'tcx AssocItem> {
2208         self.associated_items(id)
2209             .in_definition_order()
2210             .filter(move |item| item.kind == AssocKind::Fn && item.defaultness(self).has_value())
2211     }
2212
2213     /// Look up the name of a definition across crates. This does not look at HIR.
2214     pub fn opt_item_name(self, def_id: DefId) -> Option<Symbol> {
2215         if let Some(cnum) = def_id.as_crate_root() {
2216             Some(self.crate_name(cnum))
2217         } else {
2218             let def_key = self.def_key(def_id);
2219             match def_key.disambiguated_data.data {
2220                 // The name of a constructor is that of its parent.
2221                 rustc_hir::definitions::DefPathData::Ctor => self
2222                     .opt_item_name(DefId { krate: def_id.krate, index: def_key.parent.unwrap() }),
2223                 // The name of opaque types only exists in HIR.
2224                 rustc_hir::definitions::DefPathData::ImplTrait
2225                     if let Some(def_id) = def_id.as_local() =>
2226                     self.hir().opt_name(self.hir().local_def_id_to_hir_id(def_id)),
2227                 _ => def_key.get_opt_name(),
2228             }
2229         }
2230     }
2231
2232     /// Look up the name of a definition across crates. This does not look at HIR.
2233     ///
2234     /// This method will ICE if the corresponding item does not have a name.  In these cases, use
2235     /// [`opt_item_name`] instead.
2236     ///
2237     /// [`opt_item_name`]: Self::opt_item_name
2238     pub fn item_name(self, id: DefId) -> Symbol {
2239         self.opt_item_name(id).unwrap_or_else(|| {
2240             bug!("item_name: no name for {:?}", self.def_path(id));
2241         })
2242     }
2243
2244     /// Look up the name and span of a definition.
2245     ///
2246     /// See [`item_name`][Self::item_name] for more information.
2247     pub fn opt_item_ident(self, def_id: DefId) -> Option<Ident> {
2248         let def = self.opt_item_name(def_id)?;
2249         let span = def_id
2250             .as_local()
2251             .and_then(|id| self.def_ident_span(id))
2252             .unwrap_or(rustc_span::DUMMY_SP);
2253         Some(Ident::new(def, span))
2254     }
2255
2256     pub fn opt_associated_item(self, def_id: DefId) -> Option<&'tcx AssocItem> {
2257         if let DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy = self.def_kind(def_id) {
2258             Some(self.associated_item(def_id))
2259         } else {
2260             None
2261         }
2262     }
2263
2264     pub fn field_index(self, hir_id: hir::HirId, typeck_results: &TypeckResults<'_>) -> usize {
2265         typeck_results.field_indices().get(hir_id).cloned().expect("no index for a field")
2266     }
2267
2268     pub fn find_field_index(self, ident: Ident, variant: &VariantDef) -> Option<usize> {
2269         variant
2270             .fields
2271             .iter()
2272             .position(|field| self.hygienic_eq(ident, field.ident(self), variant.def_id))
2273     }
2274
2275     /// Returns `true` if the impls are the same polarity and the trait either
2276     /// has no items or is annotated `#[marker]` and prevents item overrides.
2277     pub fn impls_are_allowed_to_overlap(
2278         self,
2279         def_id1: DefId,
2280         def_id2: DefId,
2281     ) -> Option<ImplOverlapKind> {
2282         // If either trait impl references an error, they're allowed to overlap,
2283         // as one of them essentially doesn't exist.
2284         if self.impl_trait_ref(def_id1).map_or(false, |tr| tr.references_error())
2285             || self.impl_trait_ref(def_id2).map_or(false, |tr| tr.references_error())
2286         {
2287             return Some(ImplOverlapKind::Permitted { marker: false });
2288         }
2289
2290         match (self.impl_polarity(def_id1), self.impl_polarity(def_id2)) {
2291             (ImplPolarity::Reservation, _) | (_, ImplPolarity::Reservation) => {
2292                 // `#[rustc_reservation_impl]` impls don't overlap with anything
2293                 debug!(
2294                     "impls_are_allowed_to_overlap({:?}, {:?}) = Some(Permitted) (reservations)",
2295                     def_id1, def_id2
2296                 );
2297                 return Some(ImplOverlapKind::Permitted { marker: false });
2298             }
2299             (ImplPolarity::Positive, ImplPolarity::Negative)
2300             | (ImplPolarity::Negative, ImplPolarity::Positive) => {
2301                 // `impl AutoTrait for Type` + `impl !AutoTrait for Type`
2302                 debug!(
2303                     "impls_are_allowed_to_overlap({:?}, {:?}) - None (differing polarities)",
2304                     def_id1, def_id2
2305                 );
2306                 return None;
2307             }
2308             (ImplPolarity::Positive, ImplPolarity::Positive)
2309             | (ImplPolarity::Negative, ImplPolarity::Negative) => {}
2310         };
2311
2312         let is_marker_overlap = {
2313             let is_marker_impl = |def_id: DefId| -> bool {
2314                 let trait_ref = self.impl_trait_ref(def_id);
2315                 trait_ref.map_or(false, |tr| self.trait_def(tr.def_id).is_marker)
2316             };
2317             is_marker_impl(def_id1) && is_marker_impl(def_id2)
2318         };
2319
2320         if is_marker_overlap {
2321             debug!(
2322                 "impls_are_allowed_to_overlap({:?}, {:?}) = Some(Permitted) (marker overlap)",
2323                 def_id1, def_id2
2324             );
2325             Some(ImplOverlapKind::Permitted { marker: true })
2326         } else {
2327             if let Some(self_ty1) = self.issue33140_self_ty(def_id1) {
2328                 if let Some(self_ty2) = self.issue33140_self_ty(def_id2) {
2329                     if self_ty1 == self_ty2 {
2330                         debug!(
2331                             "impls_are_allowed_to_overlap({:?}, {:?}) - issue #33140 HACK",
2332                             def_id1, def_id2
2333                         );
2334                         return Some(ImplOverlapKind::Issue33140);
2335                     } else {
2336                         debug!(
2337                             "impls_are_allowed_to_overlap({:?}, {:?}) - found {:?} != {:?}",
2338                             def_id1, def_id2, self_ty1, self_ty2
2339                         );
2340                     }
2341                 }
2342             }
2343
2344             debug!("impls_are_allowed_to_overlap({:?}, {:?}) = None", def_id1, def_id2);
2345             None
2346         }
2347     }
2348
2349     /// Returns `ty::VariantDef` if `res` refers to a struct,
2350     /// or variant or their constructors, panics otherwise.
2351     pub fn expect_variant_res(self, res: Res) -> &'tcx VariantDef {
2352         match res {
2353             Res::Def(DefKind::Variant, did) => {
2354                 let enum_did = self.parent(did);
2355                 self.adt_def(enum_did).variant_with_id(did)
2356             }
2357             Res::Def(DefKind::Struct | DefKind::Union, did) => self.adt_def(did).non_enum_variant(),
2358             Res::Def(DefKind::Ctor(CtorOf::Variant, ..), variant_ctor_did) => {
2359                 let variant_did = self.parent(variant_ctor_did);
2360                 let enum_did = self.parent(variant_did);
2361                 self.adt_def(enum_did).variant_with_ctor_id(variant_ctor_did)
2362             }
2363             Res::Def(DefKind::Ctor(CtorOf::Struct, ..), ctor_did) => {
2364                 let struct_did = self.parent(ctor_did);
2365                 self.adt_def(struct_did).non_enum_variant()
2366             }
2367             _ => bug!("expect_variant_res used with unexpected res {:?}", res),
2368         }
2369     }
2370
2371     /// Returns the possibly-auto-generated MIR of a `(DefId, Subst)` pair.
2372     #[instrument(skip(self), level = "debug")]
2373     pub fn instance_mir(self, instance: ty::InstanceDef<'tcx>) -> &'tcx Body<'tcx> {
2374         match instance {
2375             ty::InstanceDef::Item(def) => {
2376                 debug!("calling def_kind on def: {:?}", def);
2377                 let def_kind = self.def_kind(def.did);
2378                 debug!("returned from def_kind: {:?}", def_kind);
2379                 match def_kind {
2380                     DefKind::Const
2381                     | DefKind::Static(..)
2382                     | DefKind::AssocConst
2383                     | DefKind::Ctor(..)
2384                     | DefKind::AnonConst
2385                     | DefKind::InlineConst => self.mir_for_ctfe_opt_const_arg(def),
2386                     // If the caller wants `mir_for_ctfe` of a function they should not be using
2387                     // `instance_mir`, so we'll assume const fn also wants the optimized version.
2388                     _ => {
2389                         assert_eq!(def.const_param_did, None);
2390                         self.optimized_mir(def.did)
2391                     }
2392                 }
2393             }
2394             ty::InstanceDef::VTableShim(..)
2395             | ty::InstanceDef::ReifyShim(..)
2396             | ty::InstanceDef::Intrinsic(..)
2397             | ty::InstanceDef::FnPtrShim(..)
2398             | ty::InstanceDef::Virtual(..)
2399             | ty::InstanceDef::ClosureOnceShim { .. }
2400             | ty::InstanceDef::DropGlue(..)
2401             | ty::InstanceDef::CloneShim(..) => self.mir_shims(instance),
2402         }
2403     }
2404
2405     // FIXME(@lcnr): Remove this function.
2406     pub fn get_attrs_unchecked(self, did: DefId) -> &'tcx [ast::Attribute] {
2407         if let Some(did) = did.as_local() {
2408             self.hir().attrs(self.hir().local_def_id_to_hir_id(did))
2409         } else {
2410             self.item_attrs(did)
2411         }
2412     }
2413
2414     /// Gets all attributes with the given name.
2415     pub fn get_attrs(self, did: DefId, attr: Symbol) -> ty::Attributes<'tcx> {
2416         let filter_fn = move |a: &&ast::Attribute| a.has_name(attr);
2417         if let Some(did) = did.as_local() {
2418             self.hir().attrs(self.hir().local_def_id_to_hir_id(did)).iter().filter(filter_fn)
2419         } else if cfg!(debug_assertions) && rustc_feature::is_builtin_only_local(attr) {
2420             bug!("tried to access the `only_local` attribute `{}` from an extern crate", attr);
2421         } else {
2422             self.item_attrs(did).iter().filter(filter_fn)
2423         }
2424     }
2425
2426     pub fn get_attr(self, did: DefId, attr: Symbol) -> Option<&'tcx ast::Attribute> {
2427         if cfg!(debug_assertions) && !rustc_feature::is_valid_for_get_attr(attr) {
2428             bug!("get_attr: unexpected called with DefId `{:?}`, attr `{:?}`", did, attr);
2429         } else {
2430             self.get_attrs(did, attr).next()
2431         }
2432     }
2433
2434     /// Determines whether an item is annotated with an attribute.
2435     pub fn has_attr(self, did: DefId, attr: Symbol) -> bool {
2436         if cfg!(debug_assertions) && !did.is_local() && rustc_feature::is_builtin_only_local(attr) {
2437             bug!("tried to access the `only_local` attribute `{}` from an extern crate", attr);
2438         } else {
2439             self.get_attrs(did, attr).next().is_some()
2440         }
2441     }
2442
2443     /// Returns `true` if this is an `auto trait`.
2444     pub fn trait_is_auto(self, trait_def_id: DefId) -> bool {
2445         self.trait_def(trait_def_id).has_auto_impl
2446     }
2447
2448     pub fn trait_is_coinductive(self, trait_def_id: DefId) -> bool {
2449         self.trait_is_auto(trait_def_id) || self.lang_items().sized_trait() == Some(trait_def_id)
2450     }
2451
2452     /// Returns layout of a generator. Layout might be unavailable if the
2453     /// generator is tainted by errors.
2454     pub fn generator_layout(self, def_id: DefId) -> Option<&'tcx GeneratorLayout<'tcx>> {
2455         self.optimized_mir(def_id).generator_layout()
2456     }
2457
2458     /// Given the `DefId` of an impl, returns the `DefId` of the trait it implements.
2459     /// If it implements no trait, returns `None`.
2460     pub fn trait_id_of_impl(self, def_id: DefId) -> Option<DefId> {
2461         self.impl_trait_ref(def_id).map(|tr| tr.def_id)
2462     }
2463
2464     /// If the given `DefId` describes an item belonging to a trait,
2465     /// returns the `DefId` of the trait that the trait item belongs to;
2466     /// otherwise, returns `None`.
2467     pub fn trait_of_item(self, def_id: DefId) -> Option<DefId> {
2468         if let DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy = self.def_kind(def_id) {
2469             let parent = self.parent(def_id);
2470             if let DefKind::Trait | DefKind::TraitAlias = self.def_kind(parent) {
2471                 return Some(parent);
2472             }
2473         }
2474         None
2475     }
2476
2477     /// If the given `DefId` describes a method belonging to an impl, returns the
2478     /// `DefId` of the impl that the method belongs to; otherwise, returns `None`.
2479     pub fn impl_of_method(self, def_id: DefId) -> Option<DefId> {
2480         if let DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy = self.def_kind(def_id) {
2481             let parent = self.parent(def_id);
2482             if let DefKind::Impl = self.def_kind(parent) {
2483                 return Some(parent);
2484             }
2485         }
2486         None
2487     }
2488
2489     /// If the given `DefId` belongs to a trait that was automatically derived, returns `true`.
2490     pub fn is_builtin_derive(self, def_id: DefId) -> bool {
2491         self.has_attr(def_id, sym::automatically_derived)
2492     }
2493
2494     /// Looks up the span of `impl_did` if the impl is local; otherwise returns `Err`
2495     /// with the name of the crate containing the impl.
2496     pub fn span_of_impl(self, impl_def_id: DefId) -> Result<Span, Symbol> {
2497         if let Some(impl_def_id) = impl_def_id.as_local() {
2498             Ok(self.def_span(impl_def_id))
2499         } else {
2500             Err(self.crate_name(impl_def_id.krate))
2501         }
2502     }
2503
2504     /// Hygienically compares a use-site name (`use_name`) for a field or an associated item with
2505     /// its supposed definition name (`def_name`). The method also needs `DefId` of the supposed
2506     /// definition's parent/scope to perform comparison.
2507     pub fn hygienic_eq(self, use_name: Ident, def_name: Ident, def_parent_def_id: DefId) -> bool {
2508         // We could use `Ident::eq` here, but we deliberately don't. The name
2509         // comparison fails frequently, and we want to avoid the expensive
2510         // `normalize_to_macros_2_0()` calls required for the span comparison whenever possible.
2511         use_name.name == def_name.name
2512             && use_name
2513                 .span
2514                 .ctxt()
2515                 .hygienic_eq(def_name.span.ctxt(), self.expn_that_defined(def_parent_def_id))
2516     }
2517
2518     pub fn adjust_ident(self, mut ident: Ident, scope: DefId) -> Ident {
2519         ident.span.normalize_to_macros_2_0_and_adjust(self.expn_that_defined(scope));
2520         ident
2521     }
2522
2523     pub fn adjust_ident_and_get_scope(
2524         self,
2525         mut ident: Ident,
2526         scope: DefId,
2527         block: hir::HirId,
2528     ) -> (Ident, DefId) {
2529         let scope = ident
2530             .span
2531             .normalize_to_macros_2_0_and_adjust(self.expn_that_defined(scope))
2532             .and_then(|actual_expansion| actual_expansion.expn_data().parent_module)
2533             .unwrap_or_else(|| self.parent_module(block).to_def_id());
2534         (ident, scope)
2535     }
2536
2537     /// Returns `true` if the debuginfo for `span` should be collapsed to the outermost expansion
2538     /// site. Only applies when `Span` is the result of macro expansion.
2539     ///
2540     /// - If the `collapse_debuginfo` feature is enabled then debuginfo is not collapsed by default
2541     ///   and only when a macro definition is annotated with `#[collapse_debuginfo]`.
2542     /// - If `collapse_debuginfo` is not enabled, then debuginfo is collapsed by default.
2543     ///
2544     /// When `-Zdebug-macros` is provided then debuginfo will never be collapsed.
2545     pub fn should_collapse_debuginfo(self, span: Span) -> bool {
2546         !self.sess.opts.unstable_opts.debug_macros
2547             && if self.features().collapse_debuginfo {
2548                 span.in_macro_expansion_with_collapse_debuginfo()
2549             } else {
2550                 // Inlined spans should not be collapsed as that leads to all of the
2551                 // inlined code being attributed to the inline callsite.
2552                 span.from_expansion() && !span.is_inlined()
2553             }
2554     }
2555
2556     pub fn is_object_safe(self, key: DefId) -> bool {
2557         self.object_safety_violations(key).is_empty()
2558     }
2559
2560     #[inline]
2561     pub fn is_const_fn_raw(self, def_id: DefId) -> bool {
2562         matches!(self.def_kind(def_id), DefKind::Fn | DefKind::AssocFn | DefKind::Ctor(..))
2563             && self.constness(def_id) == hir::Constness::Const
2564     }
2565
2566     #[inline]
2567     pub fn is_const_default_method(self, def_id: DefId) -> bool {
2568         matches!(self.trait_of_item(def_id), Some(trait_id) if self.has_attr(trait_id, sym::const_trait))
2569     }
2570
2571     pub fn impl_trait_in_trait_parent(self, mut def_id: DefId) -> DefId {
2572         while let def_kind = self.def_kind(def_id) && def_kind != DefKind::AssocFn {
2573             debug_assert_eq!(def_kind, DefKind::ImplTraitPlaceholder);
2574             def_id = self.parent(def_id);
2575         }
2576         def_id
2577     }
2578 }
2579
2580 /// Yields the parent function's `LocalDefId` if `def_id` is an `impl Trait` definition.
2581 pub fn is_impl_trait_defn(tcx: TyCtxt<'_>, def_id: DefId) -> Option<LocalDefId> {
2582     let def_id = def_id.as_local()?;
2583     if let Node::Item(item) = tcx.hir().get_by_def_id(def_id) {
2584         if let hir::ItemKind::OpaqueTy(ref opaque_ty) = item.kind {
2585             return match opaque_ty.origin {
2586                 hir::OpaqueTyOrigin::FnReturn(parent) | hir::OpaqueTyOrigin::AsyncFn(parent) => {
2587                     Some(parent)
2588                 }
2589                 hir::OpaqueTyOrigin::TyAlias => None,
2590             };
2591         }
2592     }
2593     None
2594 }
2595
2596 pub fn int_ty(ity: ast::IntTy) -> IntTy {
2597     match ity {
2598         ast::IntTy::Isize => IntTy::Isize,
2599         ast::IntTy::I8 => IntTy::I8,
2600         ast::IntTy::I16 => IntTy::I16,
2601         ast::IntTy::I32 => IntTy::I32,
2602         ast::IntTy::I64 => IntTy::I64,
2603         ast::IntTy::I128 => IntTy::I128,
2604     }
2605 }
2606
2607 pub fn uint_ty(uty: ast::UintTy) -> UintTy {
2608     match uty {
2609         ast::UintTy::Usize => UintTy::Usize,
2610         ast::UintTy::U8 => UintTy::U8,
2611         ast::UintTy::U16 => UintTy::U16,
2612         ast::UintTy::U32 => UintTy::U32,
2613         ast::UintTy::U64 => UintTy::U64,
2614         ast::UintTy::U128 => UintTy::U128,
2615     }
2616 }
2617
2618 pub fn float_ty(fty: ast::FloatTy) -> FloatTy {
2619     match fty {
2620         ast::FloatTy::F32 => FloatTy::F32,
2621         ast::FloatTy::F64 => FloatTy::F64,
2622     }
2623 }
2624
2625 pub fn ast_int_ty(ity: IntTy) -> ast::IntTy {
2626     match ity {
2627         IntTy::Isize => ast::IntTy::Isize,
2628         IntTy::I8 => ast::IntTy::I8,
2629         IntTy::I16 => ast::IntTy::I16,
2630         IntTy::I32 => ast::IntTy::I32,
2631         IntTy::I64 => ast::IntTy::I64,
2632         IntTy::I128 => ast::IntTy::I128,
2633     }
2634 }
2635
2636 pub fn ast_uint_ty(uty: UintTy) -> ast::UintTy {
2637     match uty {
2638         UintTy::Usize => ast::UintTy::Usize,
2639         UintTy::U8 => ast::UintTy::U8,
2640         UintTy::U16 => ast::UintTy::U16,
2641         UintTy::U32 => ast::UintTy::U32,
2642         UintTy::U64 => ast::UintTy::U64,
2643         UintTy::U128 => ast::UintTy::U128,
2644     }
2645 }
2646
2647 pub fn provide(providers: &mut ty::query::Providers) {
2648     closure::provide(providers);
2649     context::provide(providers);
2650     erase_regions::provide(providers);
2651     inhabitedness::provide(providers);
2652     util::provide(providers);
2653     print::provide(providers);
2654     super::util::bug::provide(providers);
2655     super::middle::provide(providers);
2656     *providers = ty::query::Providers {
2657         trait_impls_of: trait_def::trait_impls_of_provider,
2658         incoherent_impls: trait_def::incoherent_impls_provider,
2659         const_param_default: consts::const_param_default,
2660         vtable_allocation: vtable::vtable_allocation_provider,
2661         ..*providers
2662     };
2663 }
2664
2665 /// A map for the local crate mapping each type to a vector of its
2666 /// inherent impls. This is not meant to be used outside of coherence;
2667 /// rather, you should request the vector for a specific type via
2668 /// `tcx.inherent_impls(def_id)` so as to minimize your dependencies
2669 /// (constructing this map requires touching the entire crate).
2670 #[derive(Clone, Debug, Default, HashStable)]
2671 pub struct CrateInherentImpls {
2672     pub inherent_impls: LocalDefIdMap<Vec<DefId>>,
2673     pub incoherent_impls: FxHashMap<SimplifiedType, Vec<LocalDefId>>,
2674 }
2675
2676 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, HashStable)]
2677 pub struct SymbolName<'tcx> {
2678     /// `&str` gives a consistent ordering, which ensures reproducible builds.
2679     pub name: &'tcx str,
2680 }
2681
2682 impl<'tcx> SymbolName<'tcx> {
2683     pub fn new(tcx: TyCtxt<'tcx>, name: &str) -> SymbolName<'tcx> {
2684         SymbolName {
2685             name: unsafe { str::from_utf8_unchecked(tcx.arena.alloc_slice(name.as_bytes())) },
2686         }
2687     }
2688 }
2689
2690 impl<'tcx> fmt::Display for SymbolName<'tcx> {
2691     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
2692         fmt::Display::fmt(&self.name, fmt)
2693     }
2694 }
2695
2696 impl<'tcx> fmt::Debug for SymbolName<'tcx> {
2697     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
2698         fmt::Display::fmt(&self.name, fmt)
2699     }
2700 }
2701
2702 #[derive(Debug, Default, Copy, Clone)]
2703 pub struct FoundRelationships {
2704     /// This is true if we identified that this Ty (`?T`) is found in a `?T: Foo`
2705     /// obligation, where:
2706     ///
2707     ///  * `Foo` is not `Sized`
2708     ///  * `(): Foo` may be satisfied
2709     pub self_in_trait: bool,
2710     /// This is true if we identified that this Ty (`?T`) is found in a `<_ as
2711     /// _>::AssocType = ?T`
2712     pub output: bool,
2713 }
2714
2715 /// The constituent parts of a type level constant of kind ADT or array.
2716 #[derive(Copy, Clone, Debug, HashStable)]
2717 pub struct DestructuredConst<'tcx> {
2718     pub variant: Option<VariantIdx>,
2719     pub fields: &'tcx [ty::Const<'tcx>],
2720 }
2721
2722 // Some types are used a lot. Make sure they don't unintentionally get bigger.
2723 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
2724 mod size_asserts {
2725     use super::*;
2726     use rustc_data_structures::static_assert_size;
2727     // tidy-alphabetical-start
2728     static_assert_size!(PredicateS<'_>, 48);
2729     static_assert_size!(TyS<'_>, 40);
2730     static_assert_size!(WithStableHash<TyS<'_>>, 56);
2731     // tidy-alphabetical-end
2732 }