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::Ambiguous
 624             | PredicateKind::TypeWellFormedFromEnv(_) => true,
 625         }
 626     }
 627 }
 628
 629 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Predicate<'tcx> {
 630     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 631         let PredicateS {
 632             ref kind,
 633
 634             // The other fields just provide fast access to information that is
 635             // also contained in `kind`, so no need to hash them.
 636             flags: _,
 637             outer_exclusive_binder: _,
 638         } = self.0.0;
 639
 640         kind.hash_stable(hcx, hasher);
 641     }
 642 }
 643
 644 impl rustc_errors::IntoDiagnosticArg for Predicate<'_> {
 645     fn into_diagnostic_arg(self) -> rustc_errors::DiagnosticArgValue<'static> {
 646         rustc_errors::DiagnosticArgValue::Str(std::borrow::Cow::Owned(self.to_string()))
 647     }
 648 }
 649
 650 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
 651 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 652 pub enum PredicateKind<'tcx> {
 653     /// Corresponds to `where Foo: Bar<A, B, C>`. `Foo` here would be
 654     /// the `Self` type of the trait reference and `A`, `B`, and `C`
 655     /// would be the type parameters.
 656     Trait(TraitPredicate<'tcx>),
 657
 658     /// `where 'a: 'b`
 659     RegionOutlives(RegionOutlivesPredicate<'tcx>),
 660
 661     /// `where T: 'a`
 662     TypeOutlives(TypeOutlivesPredicate<'tcx>),
 663
 664     /// `where <T as TraitRef>::Name == X`, approximately.
 665     /// See the `ProjectionPredicate` struct for details.
 666     Projection(ProjectionPredicate<'tcx>),
 667
 668     /// No syntax: `T` well-formed.
 669     WellFormed(GenericArg<'tcx>),
 670
 671     /// Trait must be object-safe.
 672     ObjectSafe(DefId),
 673
 674     /// No direct syntax. May be thought of as `where T: FnFoo<...>`
 675     /// for some substitutions `...` and `T` being a closure type.
 676     /// Satisfied (or refuted) once we know the closure's kind.
 677     ClosureKind(DefId, SubstsRef<'tcx>, ClosureKind),
 678
 679     /// `T1 <: T2`
 680     ///
 681     /// This obligation is created most often when we have two
 682     /// unresolved type variables and hence don't have enough
 683     /// information to process the subtyping obligation yet.
 684     Subtype(SubtypePredicate<'tcx>),
 685
 686     /// `T1` coerced to `T2`
 687     ///
 688     /// Like a subtyping obligation, this is created most often
 689     /// when we have two unresolved type variables and hence
 690     /// don't have enough information to process the coercion
 691     /// obligation yet. At the moment, we actually process coercions
 692     /// very much like subtyping and don't handle the full coercion
 693     /// logic.
 694     Coerce(CoercePredicate<'tcx>),
 695
 696     /// Constant initializer must evaluate successfully.
 697     ConstEvaluatable(ty::Const<'tcx>),
 698
 699     /// Constants must be equal. The first component is the const that is expected.
 700     ConstEquate(Const<'tcx>, Const<'tcx>),
 701
 702     /// Represents a type found in the environment that we can use for implied bounds.
 703     ///
 704     /// Only used for Chalk.
 705     TypeWellFormedFromEnv(Ty<'tcx>),
 706
 707     /// A marker predicate that is always ambiguous.
 708     /// Used for coherence to mark opaque types as possibly equal to each other but ambiguous.
 709     Ambiguous,
 710 }
 711
 712 /// The crate outlives map is computed during typeck and contains the
 713 /// outlives of every item in the local crate. You should not use it
 714 /// directly, because to do so will make your pass dependent on the
 715 /// HIR of every item in the local crate. Instead, use
 716 /// `tcx.inferred_outlives_of()` to get the outlives for a *particular*
 717 /// item.
 718 #[derive(HashStable, Debug)]
 719 pub struct CratePredicatesMap<'tcx> {
 720     /// For each struct with outlive bounds, maps to a vector of the
 721     /// predicate of its outlive bounds. If an item has no outlives
 722     /// bounds, it will have no entry.
 723     pub predicates: FxHashMap<DefId, &'tcx [(Predicate<'tcx>, Span)]>,
 724 }
 725
 726 impl<'tcx> Predicate<'tcx> {
 727     /// Performs a substitution suitable for going from a
 728     /// poly-trait-ref to supertraits that must hold if that
 729     /// poly-trait-ref holds. This is slightly different from a normal
 730     /// substitution in terms of what happens with bound regions. See
 731     /// lengthy comment below for details.
 732     pub fn subst_supertrait(
 733         self,
 734         tcx: TyCtxt<'tcx>,
 735         trait_ref: &ty::PolyTraitRef<'tcx>,
 736     ) -> Predicate<'tcx> {
 737         // The interaction between HRTB and supertraits is not entirely
 738         // obvious. Let me walk you (and myself) through an example.
 739         //
 740         // Let's start with an easy case. Consider two traits:
 741         //
 742         //     trait Foo<'a>: Bar<'a,'a> { }
 743         //     trait Bar<'b,'c> { }
 744         //
 745         // Now, if we have a trait reference `for<'x> T: Foo<'x>`, then
 746         // we can deduce that `for<'x> T: Bar<'x,'x>`. Basically, if we
 747         // knew that `Foo<'x>` (for any 'x) then we also know that
 748         // `Bar<'x,'x>` (for any 'x). This more-or-less falls out from
 749         // normal substitution.
 750         //
 751         // In terms of why this is sound, the idea is that whenever there
 752         // is an impl of `T:Foo<'a>`, it must show that `T:Bar<'a,'a>`
 753         // holds.  So if there is an impl of `T:Foo<'a>` that applies to
 754         // all `'a`, then we must know that `T:Bar<'a,'a>` holds for all
 755         // `'a`.
 756         //
 757         // Another example to be careful of is this:
 758         //
 759         //     trait Foo1<'a>: for<'b> Bar1<'a,'b> { }
 760         //     trait Bar1<'b,'c> { }
 761         //
 762         // Here, if we have `for<'x> T: Foo1<'x>`, then what do we know?
 763         // The answer is that we know `for<'x,'b> T: Bar1<'x,'b>`. The
 764         // reason is similar to the previous example: any impl of
 765         // `T:Foo1<'x>` must show that `for<'b> T: Bar1<'x, 'b>`.  So
 766         // basically we would want to collapse the bound lifetimes from
 767         // the input (`trait_ref`) and the supertraits.
 768         //
 769         // To achieve this in practice is fairly straightforward. Let's
 770         // consider the more complicated scenario:
 771         //
 772         // - We start out with `for<'x> T: Foo1<'x>`. In this case, `'x`
 773         //   has a De Bruijn index of 1. We want to produce `for<'x,'b> T: Bar1<'x,'b>`,
 774         //   where both `'x` and `'b` would have a DB index of 1.
 775         //   The substitution from the input trait-ref is therefore going to be
 776         //   `'a => 'x` (where `'x` has a DB index of 1).
 777         // - The supertrait-ref is `for<'b> Bar1<'a,'b>`, where `'a` is an
 778         //   early-bound parameter and `'b' is a late-bound parameter with a
 779         //   DB index of 1.
 780         // - If we replace `'a` with `'x` from the input, it too will have
 781         //   a DB index of 1, and thus we'll have `for<'x,'b> Bar1<'x,'b>`
 782         //   just as we wanted.
 783         //
 784         // There is only one catch. If we just apply the substitution `'a
 785         // => 'x` to `for<'b> Bar1<'a,'b>`, the substitution code will
 786         // adjust the DB index because we substituting into a binder (it
 787         // tries to be so smart...) resulting in `for<'x> for<'b>
 788         // Bar1<'x,'b>` (we have no syntax for this, so use your
 789         // imagination). Basically the 'x will have DB index of 2 and 'b
 790         // will have DB index of 1. Not quite what we want. So we apply
 791         // the substitution to the *contents* of the trait reference,
 792         // rather than the trait reference itself (put another way, the
 793         // substitution code expects equal binding levels in the values
 794         // from the substitution and the value being substituted into, and
 795         // this trick achieves that).
 796
 797         // Working through the second example:
 798         // trait_ref: for<'x> T: Foo1<'^0.0>; substs: [T, '^0.0]
 799         // predicate: for<'b> Self: Bar1<'a, '^0.0>; substs: [Self, 'a, '^0.0]
 800         // We want to end up with:
 801         //     for<'x, 'b> T: Bar1<'^0.0, '^0.1>
 802         // To do this:
 803         // 1) We must shift all bound vars in predicate by the length
 804         //    of trait ref's bound vars. So, we would end up with predicate like
 805         //    Self: Bar1<'a, '^0.1>
 806         // 2) We can then apply the trait substs to this, ending up with
 807         //    T: Bar1<'^0.0, '^0.1>
 808         // 3) Finally, to create the final bound vars, we concatenate the bound
 809         //    vars of the trait ref with those of the predicate:
 810         //    ['x, 'b]
 811         let bound_pred = self.kind();
 812         let pred_bound_vars = bound_pred.bound_vars();
 813         let trait_bound_vars = trait_ref.bound_vars();
 814         // 1) Self: Bar1<'a, '^0.0> -> Self: Bar1<'a, '^0.1>
 815         let shifted_pred =
 816             tcx.shift_bound_var_indices(trait_bound_vars.len(), bound_pred.skip_binder());
 817         // 2) Self: Bar1<'a, '^0.1> -> T: Bar1<'^0.0, '^0.1>
 818         let new = EarlyBinder(shifted_pred).subst(tcx, trait_ref.skip_binder().substs);
 819         // 3) ['x] + ['b] -> ['x, 'b]
 820         let bound_vars =
 821             tcx.mk_bound_variable_kinds(trait_bound_vars.iter().chain(pred_bound_vars));
 822         tcx.reuse_or_mk_predicate(self, ty::Binder::bind_with_vars(new, bound_vars))
 823     }
 824 }
 825
 826 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
 827 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 828 pub struct TraitPredicate<'tcx> {
 829     pub trait_ref: TraitRef<'tcx>,
 830
 831     pub constness: BoundConstness,
 832
 833     /// If polarity is Positive: we are proving that the trait is implemented.
 834     ///
 835     /// If polarity is Negative: we are proving that a negative impl of this trait
 836     /// exists. (Note that coherence also checks whether negative impls of supertraits
 837     /// exist via a series of predicates.)
 838     ///
 839     /// If polarity is Reserved: that's a bug.
 840     pub polarity: ImplPolarity,
 841 }
 842
 843 pub type PolyTraitPredicate<'tcx> = ty::Binder<'tcx, TraitPredicate<'tcx>>;
 844
 845 impl<'tcx> TraitPredicate<'tcx> {
 846     pub fn remap_constness(&mut self, param_env: &mut ParamEnv<'tcx>) {
 847         *param_env = param_env.with_constness(self.constness.and(param_env.constness()))
 848     }
 849
 850     /// Remap the constness of this predicate before emitting it for diagnostics.
 851     pub fn remap_constness_diag(&mut self, param_env: ParamEnv<'tcx>) {
 852         // this is different to `remap_constness` that callees want to print this predicate
 853         // in case of selection errors. `T: ~const Drop` bounds cannot end up here when the
 854         // param_env is not const because it is always satisfied in non-const contexts.
 855         if let hir::Constness::NotConst = param_env.constness() {
 856             self.constness = ty::BoundConstness::NotConst;
 857         }
 858     }
 859
 860     pub fn with_self_type(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
 861         Self { trait_ref: self.trait_ref.with_self_type(tcx, self_ty), ..self }
 862     }
 863
 864     pub fn def_id(self) -> DefId {
 865         self.trait_ref.def_id
 866     }
 867
 868     pub fn self_ty(self) -> Ty<'tcx> {
 869         self.trait_ref.self_ty()
 870     }
 871
 872     #[inline]
 873     pub fn is_const_if_const(self) -> bool {
 874         self.constness == BoundConstness::ConstIfConst
 875     }
 876
 877     pub fn is_constness_satisfied_by(self, constness: hir::Constness) -> bool {
 878         match (self.constness, constness) {
 879             (BoundConstness::NotConst, _)
 880             | (BoundConstness::ConstIfConst, hir::Constness::Const) => true,
 881             (BoundConstness::ConstIfConst, hir::Constness::NotConst) => false,
 882         }
 883     }
 884
 885     pub fn without_const(mut self) -> Self {
 886         self.constness = BoundConstness::NotConst;
 887         self
 888     }
 889 }
 890
 891 impl<'tcx> PolyTraitPredicate<'tcx> {
 892     pub fn def_id(self) -> DefId {
 893         // Ok to skip binder since trait `DefId` does not care about regions.
 894         self.skip_binder().def_id()
 895     }
 896
 897     pub fn self_ty(self) -> ty::Binder<'tcx, Ty<'tcx>> {
 898         self.map_bound(|trait_ref| trait_ref.self_ty())
 899     }
 900
 901     /// Remap the constness of this predicate before emitting it for diagnostics.
 902     pub fn remap_constness_diag(&mut self, param_env: ParamEnv<'tcx>) {
 903         *self = self.map_bound(|mut p| {
 904             p.remap_constness_diag(param_env);
 905             p
 906         });
 907     }
 908
 909     #[inline]
 910     pub fn is_const_if_const(self) -> bool {
 911         self.skip_binder().is_const_if_const()
 912     }
 913 }
 914
 915 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
 916 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 917 pub struct OutlivesPredicate<A, B>(pub A, pub B); // `A: B`
 918 pub type RegionOutlivesPredicate<'tcx> = OutlivesPredicate<ty::Region<'tcx>, ty::Region<'tcx>>;
 919 pub type TypeOutlivesPredicate<'tcx> = OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>;
 920 pub type PolyRegionOutlivesPredicate<'tcx> = ty::Binder<'tcx, RegionOutlivesPredicate<'tcx>>;
 921 pub type PolyTypeOutlivesPredicate<'tcx> = ty::Binder<'tcx, TypeOutlivesPredicate<'tcx>>;
 922
 923 /// Encodes that `a` must be a subtype of `b`. The `a_is_expected` flag indicates
 924 /// whether the `a` type is the type that we should label as "expected" when
 925 /// presenting user diagnostics.
 926 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
 927 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 928 pub struct SubtypePredicate<'tcx> {
 929     pub a_is_expected: bool,
 930     pub a: Ty<'tcx>,
 931     pub b: Ty<'tcx>,
 932 }
 933 pub type PolySubtypePredicate<'tcx> = ty::Binder<'tcx, SubtypePredicate<'tcx>>;
 934
 935 /// Encodes that we have to coerce *from* the `a` type to the `b` type.
 936 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
 937 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 938 pub struct CoercePredicate<'tcx> {
 939     pub a: Ty<'tcx>,
 940     pub b: Ty<'tcx>,
 941 }
 942 pub type PolyCoercePredicate<'tcx> = ty::Binder<'tcx, CoercePredicate<'tcx>>;
 943
 944 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 945 pub struct Term<'tcx> {
 946     ptr: NonZeroUsize,
 947     marker: PhantomData<(Ty<'tcx>, Const<'tcx>)>,
 948 }
 949
 950 impl Debug for Term<'_> {
 951     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 952         let data = if let Some(ty) = self.ty() {
 953             format!("Term::Ty({:?})", ty)
 954         } else if let Some(ct) = self.ct() {
 955             format!("Term::Ct({:?})", ct)
 956         } else {
 957             unreachable!()
 958         };
 959         f.write_str(&data)
 960     }
 961 }
 962
 963 impl<'tcx> From<Ty<'tcx>> for Term<'tcx> {
 964     fn from(ty: Ty<'tcx>) -> Self {
 965         TermKind::Ty(ty).pack()
 966     }
 967 }
 968
 969 impl<'tcx> From<Const<'tcx>> for Term<'tcx> {
 970     fn from(c: Const<'tcx>) -> Self {
 971         TermKind::Const(c).pack()
 972     }
 973 }
 974
 975 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Term<'tcx> {
 976     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 977         self.unpack().hash_stable(hcx, hasher);
 978     }
 979 }
 980
 981 impl<'tcx> TypeFoldable<'tcx> for Term<'tcx> {
 982     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 983         Ok(self.unpack().try_fold_with(folder)?.pack())
 984     }
 985 }
 986
 987 impl<'tcx> TypeVisitable<'tcx> for Term<'tcx> {
 988     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 989         self.unpack().visit_with(visitor)
 990     }
 991 }
 992
 993 impl<'tcx, E: TyEncoder<I = TyCtxt<'tcx>>> Encodable<E> for Term<'tcx> {
 994     fn encode(&self, e: &mut E) {
 995         self.unpack().encode(e)
 996     }
 997 }
 998
 999 impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> Decodable<D> for Term<'tcx> {
1000     fn decode(d: &mut D) -> Self {
1001         let res: TermKind<'tcx> = Decodable::decode(d);
1002         res.pack()
1003     }
1004 }
1005
1006 impl<'tcx> Term<'tcx> {
1007     #[inline]
1008     pub fn unpack(self) -> TermKind<'tcx> {
1009         let ptr = self.ptr.get();
1010         // SAFETY: use of `Interned::new_unchecked` here is ok because these
1011         // pointers were originally created from `Interned` types in `pack()`,
1012         // and this is just going in the other direction.
1013         unsafe {
1014             match ptr & TAG_MASK {
1015                 TYPE_TAG => TermKind::Ty(Ty(Interned::new_unchecked(
1016                     &*((ptr & !TAG_MASK) as *const WithStableHash<ty::TyS<'tcx>>),
1017                 ))),
1018                 CONST_TAG => TermKind::Const(ty::Const(Interned::new_unchecked(
1019                     &*((ptr & !TAG_MASK) as *const ty::ConstS<'tcx>),
1020                 ))),
1021                 _ => core::intrinsics::unreachable(),
1022             }
1023         }
1024     }
1025
1026     pub fn ty(&self) -> Option<Ty<'tcx>> {
1027         if let TermKind::Ty(ty) = self.unpack() { Some(ty) } else { None }
1028     }
1029
1030     pub fn ct(&self) -> Option<Const<'tcx>> {
1031         if let TermKind::Const(c) = self.unpack() { Some(c) } else { None }
1032     }
1033
1034     pub fn into_arg(self) -> GenericArg<'tcx> {
1035         match self.unpack() {
1036             TermKind::Ty(ty) => ty.into(),
1037             TermKind::Const(c) => c.into(),
1038         }
1039     }
1040 }
1041
1042 const TAG_MASK: usize = 0b11;
1043 const TYPE_TAG: usize = 0b00;
1044 const CONST_TAG: usize = 0b01;
1045
1046 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, TyEncodable, TyDecodable)]
1047 #[derive(HashStable, TypeFoldable, TypeVisitable)]
1048 pub enum TermKind<'tcx> {
1049     Ty(Ty<'tcx>),
1050     Const(Const<'tcx>),
1051 }
1052
1053 impl<'tcx> TermKind<'tcx> {
1054     #[inline]
1055     fn pack(self) -> Term<'tcx> {
1056         let (tag, ptr) = match self {
1057             TermKind::Ty(ty) => {
1058                 // Ensure we can use the tag bits.
1059                 assert_eq!(mem::align_of_val(&*ty.0.0) & TAG_MASK, 0);
1060                 (TYPE_TAG, ty.0.0 as *const WithStableHash<ty::TyS<'tcx>> as usize)
1061             }
1062             TermKind::Const(ct) => {
1063                 // Ensure we can use the tag bits.
1064                 assert_eq!(mem::align_of_val(&*ct.0.0) & TAG_MASK, 0);
1065                 (CONST_TAG, ct.0.0 as *const ty::ConstS<'tcx> as usize)
1066             }
1067         };
1068
1069         Term { ptr: unsafe { NonZeroUsize::new_unchecked(ptr | tag) }, marker: PhantomData }
1070     }
1071 }
1072
1073 /// This kind of predicate has no *direct* correspondent in the
1074 /// syntax, but it roughly corresponds to the syntactic forms:
1075 ///
1076 /// 1. `T: TraitRef<..., Item = Type>`
1077 /// 2. `<T as TraitRef<...>>::Item == Type` (NYI)
1078 ///
1079 /// In particular, form #1 is "desugared" to the combination of a
1080 /// normal trait predicate (`T: TraitRef<...>`) and one of these
1081 /// predicates. Form #2 is a broader form in that it also permits
1082 /// equality between arbitrary types. Processing an instance of
1083 /// Form #2 eventually yields one of these `ProjectionPredicate`
1084 /// instances to normalize the LHS.
1085 #[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
1086 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
1087 pub struct ProjectionPredicate<'tcx> {
1088     pub projection_ty: ProjectionTy<'tcx>,
1089     pub term: Term<'tcx>,
1090 }
1091
1092 pub type PolyProjectionPredicate<'tcx> = Binder<'tcx, ProjectionPredicate<'tcx>>;
1093
1094 impl<'tcx> PolyProjectionPredicate<'tcx> {
1095     /// Returns the `DefId` of the trait of the associated item being projected.
1096     #[inline]
1097     pub fn trait_def_id(&self, tcx: TyCtxt<'tcx>) -> DefId {
1098         self.skip_binder().projection_ty.trait_def_id(tcx)
1099     }
1100
1101     /// Get the [PolyTraitRef] required for this projection to be well formed.
1102     /// Note that for generic associated types the predicates of the associated
1103     /// type also need to be checked.
1104     #[inline]
1105     pub fn required_poly_trait_ref(&self, tcx: TyCtxt<'tcx>) -> PolyTraitRef<'tcx> {
1106         // Note: unlike with `TraitRef::to_poly_trait_ref()`,
1107         // `self.0.trait_ref` is permitted to have escaping regions.
1108         // This is because here `self` has a `Binder` and so does our
1109         // return value, so we are preserving the number of binding
1110         // levels.
1111         self.map_bound(|predicate| predicate.projection_ty.trait_ref(tcx))
1112     }
1113
1114     pub fn term(&self) -> Binder<'tcx, Term<'tcx>> {
1115         self.map_bound(|predicate| predicate.term)
1116     }
1117
1118     /// The `DefId` of the `TraitItem` for the associated type.
1119     ///
1120     /// Note that this is not the `DefId` of the `TraitRef` containing this
1121     /// associated type, which is in `tcx.associated_item(projection_def_id()).container`.
1122     pub fn projection_def_id(&self) -> DefId {
1123         // Ok to skip binder since trait `DefId` does not care about regions.
1124         self.skip_binder().projection_ty.item_def_id
1125     }
1126 }
1127
1128 pub trait ToPolyTraitRef<'tcx> {
1129     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
1130 }
1131
1132 impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
1133     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
1134         self.map_bound_ref(|trait_pred| trait_pred.trait_ref)
1135     }
1136 }
1137
1138 pub trait ToPredicate<'tcx, Predicate> {
1139     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate;
1140 }
1141
1142 impl<'tcx, T> ToPredicate<'tcx, T> for T {
1143     fn to_predicate(self, _tcx: TyCtxt<'tcx>) -> T {
1144         self
1145     }
1146 }
1147
1148 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for Binder<'tcx, PredicateKind<'tcx>> {
1149     #[inline(always)]
1150     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1151         tcx.mk_predicate(self)
1152     }
1153 }
1154
1155 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyTraitPredicate<'tcx> {
1156     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1157         self.map_bound(PredicateKind::Trait).to_predicate(tcx)
1158     }
1159 }
1160
1161 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyRegionOutlivesPredicate<'tcx> {
1162     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1163         self.map_bound(PredicateKind::RegionOutlives).to_predicate(tcx)
1164     }
1165 }
1166
1167 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyTypeOutlivesPredicate<'tcx> {
1168     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1169         self.map_bound(PredicateKind::TypeOutlives).to_predicate(tcx)
1170     }
1171 }
1172
1173 impl<'tcx> ToPredicate<'tcx, Predicate<'tcx>> for PolyProjectionPredicate<'tcx> {
1174     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
1175         self.map_bound(PredicateKind::Projection).to_predicate(tcx)
1176     }
1177 }
1178
1179 impl<'tcx> Predicate<'tcx> {
1180     pub fn to_opt_poly_trait_pred(self) -> Option<PolyTraitPredicate<'tcx>> {
1181         let predicate = self.kind();
1182         match predicate.skip_binder() {
1183             PredicateKind::Trait(t) => Some(predicate.rebind(t)),
1184             PredicateKind::Projection(..)
1185             | PredicateKind::Subtype(..)
1186             | PredicateKind::Coerce(..)
1187             | PredicateKind::RegionOutlives(..)
1188             | PredicateKind::WellFormed(..)
1189             | PredicateKind::ObjectSafe(..)
1190             | PredicateKind::ClosureKind(..)
1191             | PredicateKind::TypeOutlives(..)
1192             | PredicateKind::ConstEvaluatable(..)
1193             | PredicateKind::ConstEquate(..)
1194             | PredicateKind::Ambiguous
1195             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1196         }
1197     }
1198
1199     pub fn to_opt_poly_projection_pred(self) -> Option<PolyProjectionPredicate<'tcx>> {
1200         let predicate = self.kind();
1201         match predicate.skip_binder() {
1202             PredicateKind::Projection(t) => Some(predicate.rebind(t)),
1203             PredicateKind::Trait(..)
1204             | PredicateKind::Subtype(..)
1205             | PredicateKind::Coerce(..)
1206             | PredicateKind::RegionOutlives(..)
1207             | PredicateKind::WellFormed(..)
1208             | PredicateKind::ObjectSafe(..)
1209             | PredicateKind::ClosureKind(..)
1210             | PredicateKind::TypeOutlives(..)
1211             | PredicateKind::ConstEvaluatable(..)
1212             | PredicateKind::ConstEquate(..)
1213             | PredicateKind::Ambiguous
1214             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1215         }
1216     }
1217
1218     pub fn to_opt_type_outlives(self) -> Option<PolyTypeOutlivesPredicate<'tcx>> {
1219         let predicate = self.kind();
1220         match predicate.skip_binder() {
1221             PredicateKind::TypeOutlives(data) => Some(predicate.rebind(data)),
1222             PredicateKind::Trait(..)
1223             | PredicateKind::Projection(..)
1224             | PredicateKind::Subtype(..)
1225             | PredicateKind::Coerce(..)
1226             | PredicateKind::RegionOutlives(..)
1227             | PredicateKind::WellFormed(..)
1228             | PredicateKind::ObjectSafe(..)
1229             | PredicateKind::ClosureKind(..)
1230             | PredicateKind::ConstEvaluatable(..)
1231             | PredicateKind::ConstEquate(..)
1232             | PredicateKind::Ambiguous
1233             | PredicateKind::TypeWellFormedFromEnv(..) => None,
1234         }
1235     }
1236 }
1237
1238 /// Represents the bounds declared on a particular set of type
1239 /// parameters. Should eventually be generalized into a flag list of
1240 /// where-clauses. You can obtain an `InstantiatedPredicates` list from a
1241 /// `GenericPredicates` by using the `instantiate` method. Note that this method
1242 /// reflects an important semantic invariant of `InstantiatedPredicates`: while
1243 /// the `GenericPredicates` are expressed in terms of the bound type
1244 /// parameters of the impl/trait/whatever, an `InstantiatedPredicates` instance
1245 /// represented a set of bounds for some particular instantiation,
1246 /// meaning that the generic parameters have been substituted with
1247 /// their values.
1248 ///
1249 /// Example:
1250 /// ```ignore (illustrative)
1251 /// struct Foo<T, U: Bar<T>> { ... }
1252 /// ```
1253 /// Here, the `GenericPredicates` for `Foo` would contain a list of bounds like
1254 /// `[[], [U:Bar<T>]]`. Now if there were some particular reference
1255 /// like `Foo<isize,usize>`, then the `InstantiatedPredicates` would be `[[],
1256 /// [usize:Bar<isize>]]`.
1257 #[derive(Clone, Debug, TypeFoldable, TypeVisitable)]
1258 pub struct InstantiatedPredicates<'tcx> {
1259     pub predicates: Vec<Predicate<'tcx>>,
1260     pub spans: Vec<Span>,
1261 }
1262
1263 impl<'tcx> InstantiatedPredicates<'tcx> {
1264     pub fn empty() -> InstantiatedPredicates<'tcx> {
1265         InstantiatedPredicates { predicates: vec![], spans: vec![] }
1266     }
1267
1268     pub fn is_empty(&self) -> bool {
1269         self.predicates.is_empty()
1270     }
1271 }
1272
1273 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable, TyEncodable, TyDecodable, Lift)]
1274 #[derive(TypeFoldable, TypeVisitable)]
1275 pub struct OpaqueTypeKey<'tcx> {
1276     pub def_id: LocalDefId,
1277     pub substs: SubstsRef<'tcx>,
1278 }
1279
1280 #[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable, HashStable, TyEncodable, TyDecodable)]
1281 pub struct OpaqueHiddenType<'tcx> {
1282     /// The span of this particular definition of the opaque type. So
1283     /// for example:
1284     ///
1285     /// ```ignore (incomplete snippet)
1286     /// type Foo = impl Baz;
1287     /// fn bar() -> Foo {
1288     /// //          ^^^ This is the span we are looking for!
1289     /// }
1290     /// ```
1291     ///
1292     /// In cases where the fn returns `(impl Trait, impl Trait)` or
1293     /// other such combinations, the result is currently
1294     /// over-approximated, but better than nothing.
1295     pub span: Span,
1296
1297     /// The type variable that represents the value of the opaque type
1298     /// that we require. In other words, after we compile this function,
1299     /// we will be created a constraint like:
1300     /// ```ignore (pseudo-rust)
1301     /// Foo<'a, T> = ?C
1302     /// ```
1303     /// where `?C` is the value of this type variable. =) It may
1304     /// naturally refer to the type and lifetime parameters in scope
1305     /// in this function, though ultimately it should only reference
1306     /// those that are arguments to `Foo` in the constraint above. (In
1307     /// other words, `?C` should not include `'b`, even though it's a
1308     /// lifetime parameter on `foo`.)
1309     pub ty: Ty<'tcx>,
1310 }
1311
1312 impl<'tcx> OpaqueHiddenType<'tcx> {
1313     pub fn report_mismatch(&self, other: &Self, tcx: TyCtxt<'tcx>) {
1314         // Found different concrete types for the opaque type.
1315         let sub_diag = if self.span == other.span {
1316             TypeMismatchReason::ConflictType { span: self.span }
1317         } else {
1318             TypeMismatchReason::PreviousUse { span: self.span }
1319         };
1320         tcx.sess.emit_err(OpaqueHiddenTypeMismatch {
1321             self_ty: self.ty,
1322             other_ty: other.ty,
1323             other_span: other.span,
1324             sub: sub_diag,
1325         });
1326     }
1327
1328     #[instrument(level = "debug", skip(tcx), ret)]
1329     pub fn remap_generic_params_to_declaration_params(
1330         self,
1331         opaque_type_key: OpaqueTypeKey<'tcx>,
1332         tcx: TyCtxt<'tcx>,
1333         // typeck errors have subpar spans for opaque types, so delay error reporting until borrowck.
1334         ignore_errors: bool,
1335         origin: OpaqueTyOrigin,
1336     ) -> Self {
1337         let OpaqueTypeKey { def_id, substs } = opaque_type_key;
1338
1339         // Use substs to build up a reverse map from regions to their
1340         // identity mappings. This is necessary because of `impl
1341         // Trait` lifetimes are computed by replacing existing
1342         // lifetimes with 'static and remapping only those used in the
1343         // `impl Trait` return type, resulting in the parameters
1344         // shifting.
1345         let id_substs = InternalSubsts::identity_for_item(tcx, def_id.to_def_id());
1346         debug!(?id_substs);
1347
1348         // This zip may have several times the same lifetime in `substs` paired with a different
1349         // lifetime from `id_substs`.  Simply `collect`ing the iterator is the correct behaviour:
1350         // it will pick the last one, which is the one we introduced in the impl-trait desugaring.
1351         let map = substs.iter().zip(id_substs);
1352
1353         let map: FxHashMap<GenericArg<'tcx>, GenericArg<'tcx>> = match origin {
1354             // HACK: The HIR lowering for async fn does not generate
1355             // any `+ Captures<'x>` bounds for the `impl Future<...>`, so all async fns with lifetimes
1356             // would now fail to compile. We should probably just make hir lowering fill this in properly.
1357             OpaqueTyOrigin::AsyncFn(_) => map.collect(),
1358             OpaqueTyOrigin::FnReturn(_) | OpaqueTyOrigin::TyAlias => {
1359                 // Opaque types may only use regions that are bound. So for
1360                 // ```rust
1361                 // type Foo<'a, 'b, 'c> = impl Trait<'a> + 'b;
1362                 // ```
1363                 // we may not use `'c` in the hidden type.
1364                 let variances = tcx.variances_of(def_id);
1365                 debug!(?variances);
1366
1367                 map.filter(|(_, v)| {
1368                     let ty::GenericArgKind::Lifetime(lt) = v.unpack() else { return true };
1369                     let ty::ReEarlyBound(ebr) = lt.kind() else { bug!() };
1370                     variances[ebr.index as usize] == ty::Variance::Invariant
1371                 })
1372                 .collect()
1373             }
1374         };
1375         debug!("map = {:#?}", map);
1376
1377         // Convert the type from the function into a type valid outside
1378         // the function, by replacing invalid regions with 'static,
1379         // after producing an error for each of them.
1380         self.fold_with(&mut opaque_types::ReverseMapper::new(tcx, map, self.span, ignore_errors))
1381     }
1382 }
1383
1384 /// The "placeholder index" fully defines a placeholder region, type, or const. Placeholders are
1385 /// identified by both a universe, as well as a name residing within that universe. Distinct bound
1386 /// regions/types/consts within the same universe simply have an unknown relationship to one
1387 /// another.
1388 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
1389 #[derive(HashStable, TyEncodable, TyDecodable)]
1390 pub struct Placeholder<T> {
1391     pub universe: UniverseIndex,
1392     pub name: T,
1393 }
1394
1395 pub type PlaceholderRegion = Placeholder<BoundRegionKind>;
1396
1397 pub type PlaceholderType = Placeholder<BoundVar>;
1398
1399 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable)]
1400 #[derive(TyEncodable, TyDecodable, PartialOrd, Ord)]
1401 pub struct BoundConst<'tcx> {
1402     pub var: BoundVar,
1403     pub ty: Ty<'tcx>,
1404 }
1405
1406 pub type PlaceholderConst<'tcx> = Placeholder<BoundVar>;
1407
1408 /// A `DefId` which, in case it is a const argument, is potentially bundled with
1409 /// the `DefId` of the generic parameter it instantiates.
1410 ///
1411 /// This is used to avoid calls to `type_of` for const arguments during typeck
1412 /// which cause cycle errors.
1413 ///
1414 /// ```rust
1415 /// struct A;
1416 /// impl A {
1417 ///     fn foo<const N: usize>(&self) -> [u8; N] { [0; N] }
1418 ///     //           ^ const parameter
1419 /// }
1420 /// struct B;
1421 /// impl B {
1422 ///     fn foo<const M: u8>(&self) -> usize { 42 }
1423 ///     //           ^ const parameter
1424 /// }
1425 ///
1426 /// fn main() {
1427 ///     let a = A;
1428 ///     let _b = a.foo::<{ 3 + 7 }>();
1429 ///     //               ^^^^^^^^^ const argument
1430 /// }
1431 /// ```
1432 ///
1433 /// Let's look at the call `a.foo::<{ 3 + 7 }>()` here. We do not know
1434 /// which `foo` is used until we know the type of `a`.
1435 ///
1436 /// We only know the type of `a` once we are inside of `typeck(main)`.
1437 /// We also end up normalizing the type of `_b` during `typeck(main)` which
1438 /// requires us to evaluate the const argument.
1439 ///
1440 /// To evaluate that const argument we need to know its type,
1441 /// which we would get using `type_of(const_arg)`. This requires us to
1442 /// resolve `foo` as it can be either `usize` or `u8` in this example.
1443 /// However, resolving `foo` once again requires `typeck(main)` to get the type of `a`,
1444 /// which results in a cycle.
1445 ///
1446 /// In short we must not call `type_of(const_arg)` during `typeck(main)`.
1447 ///
1448 /// When first creating the `ty::Const` of the const argument inside of `typeck` we have
1449 /// already resolved `foo` so we know which const parameter this argument instantiates.
1450 /// This means that we also know the expected result of `type_of(const_arg)` even if we
1451 /// aren't allowed to call that query: it is equal to `type_of(const_param)` which is
1452 /// trivial to compute.
1453 ///
1454 /// If we now want to use that constant in a place which potentially needs its type
1455 /// we also pass the type of its `const_param`. This is the point of `WithOptConstParam`,
1456 /// except that instead of a `Ty` we bundle the `DefId` of the const parameter.
1457 /// Meaning that we need to use `type_of(const_param_did)` if `const_param_did` is `Some`
1458 /// to get the type of `did`.
1459 #[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable, Lift, TyEncodable, TyDecodable)]
1460 #[derive(PartialEq, Eq, PartialOrd, Ord)]
1461 #[derive(Hash, HashStable)]
1462 pub struct WithOptConstParam<T> {
1463     pub did: T,
1464     /// The `DefId` of the corresponding generic parameter in case `did` is
1465     /// a const argument.
1466     ///
1467     /// Note that even if `did` is a const argument, this may still be `None`.
1468     /// All queries taking `WithOptConstParam` start by calling `tcx.opt_const_param_of(def.did)`
1469     /// to potentially update `param_did` in the case it is `None`.
1470     pub const_param_did: Option<DefId>,
1471 }
1472
1473 impl<T> WithOptConstParam<T> {
1474     /// Creates a new `WithOptConstParam` setting `const_param_did` to `None`.
1475     #[inline(always)]
1476     pub fn unknown(did: T) -> WithOptConstParam<T> {
1477         WithOptConstParam { did, const_param_did: None }
1478     }
1479 }
1480
1481 impl WithOptConstParam<LocalDefId> {
1482     /// Returns `Some((did, param_did))` if `def_id` is a const argument,
1483     /// `None` otherwise.
1484     #[inline(always)]
1485     pub fn try_lookup(did: LocalDefId, tcx: TyCtxt<'_>) -> Option<(LocalDefId, DefId)> {
1486         tcx.opt_const_param_of(did).map(|param_did| (did, param_did))
1487     }
1488
1489     /// In case `self` is unknown but `self.did` is a const argument, this returns
1490     /// a `WithOptConstParam` with the correct `const_param_did`.
1491     #[inline(always)]
1492     pub fn try_upgrade(self, tcx: TyCtxt<'_>) -> Option<WithOptConstParam<LocalDefId>> {
1493         if self.const_param_did.is_none() {
1494             if let const_param_did @ Some(_) = tcx.opt_const_param_of(self.did) {
1495                 return Some(WithOptConstParam { did: self.did, const_param_did });
1496             }
1497         }
1498
1499         None
1500     }
1501
1502     pub fn to_global(self) -> WithOptConstParam<DefId> {
1503         WithOptConstParam { did: self.did.to_def_id(), const_param_did: self.const_param_did }
1504     }
1505
1506     pub fn def_id_for_type_of(self) -> DefId {
1507         if let Some(did) = self.const_param_did { did } else { self.did.to_def_id() }
1508     }
1509 }
1510
1511 impl WithOptConstParam<DefId> {
1512     pub fn as_local(self) -> Option<WithOptConstParam<LocalDefId>> {
1513         self.did
1514             .as_local()
1515             .map(|did| WithOptConstParam { did, const_param_did: self.const_param_did })
1516     }
1517
1518     pub fn as_const_arg(self) -> Option<(LocalDefId, DefId)> {
1519         if let Some(param_did) = self.const_param_did {
1520             if let Some(did) = self.did.as_local() {
1521                 return Some((did, param_did));
1522             }
1523         }
1524
1525         None
1526     }
1527
1528     pub fn is_local(self) -> bool {
1529         self.did.is_local()
1530     }
1531
1532     pub fn def_id_for_type_of(self) -> DefId {
1533         self.const_param_did.unwrap_or(self.did)
1534     }
1535 }
1536
1537 /// When type checking, we use the `ParamEnv` to track
1538 /// details about the set of where-clauses that are in scope at this
1539 /// particular point.
1540 #[derive(Copy, Clone, Hash, PartialEq, Eq)]
1541 pub struct ParamEnv<'tcx> {
1542     /// This packs both caller bounds and the reveal enum into one pointer.
1543     ///
1544     /// Caller bounds are `Obligation`s that the caller must satisfy. This is
1545     /// basically the set of bounds on the in-scope type parameters, translated
1546     /// into `Obligation`s, and elaborated and normalized.
1547     ///
1548     /// Use the `caller_bounds()` method to access.
1549     ///
1550     /// Typically, this is `Reveal::UserFacing`, but during codegen we
1551     /// want `Reveal::All`.
1552     ///
1553     /// Note: This is packed, use the reveal() method to access it.
1554     packed: CopyTaggedPtr<&'tcx List<Predicate<'tcx>>, ParamTag, true>,
1555 }
1556
1557 #[derive(Copy, Clone)]
1558 struct ParamTag {
1559     reveal: traits::Reveal,
1560     constness: hir::Constness,
1561 }
1562
1563 unsafe impl rustc_data_structures::tagged_ptr::Tag for ParamTag {
1564     const BITS: usize = 2;
1565     #[inline]
1566     fn into_usize(self) -> usize {
1567         match self {
1568             Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::NotConst } => 0,
1569             Self { reveal: traits::Reveal::All, constness: hir::Constness::NotConst } => 1,
1570             Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::Const } => 2,
1571             Self { reveal: traits::Reveal::All, constness: hir::Constness::Const } => 3,
1572         }
1573     }
1574     #[inline]
1575     unsafe fn from_usize(ptr: usize) -> Self {
1576         match ptr {
1577             0 => Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::NotConst },
1578             1 => Self { reveal: traits::Reveal::All, constness: hir::Constness::NotConst },
1579             2 => Self { reveal: traits::Reveal::UserFacing, constness: hir::Constness::Const },
1580             3 => Self { reveal: traits::Reveal::All, constness: hir::Constness::Const },
1581             _ => std::hint::unreachable_unchecked(),
1582         }
1583     }
1584 }
1585
1586 impl<'tcx> fmt::Debug for ParamEnv<'tcx> {
1587     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1588         f.debug_struct("ParamEnv")
1589             .field("caller_bounds", &self.caller_bounds())
1590             .field("reveal", &self.reveal())
1591             .field("constness", &self.constness())
1592             .finish()
1593     }
1594 }
1595
1596 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for ParamEnv<'tcx> {
1597     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
1598         self.caller_bounds().hash_stable(hcx, hasher);
1599         self.reveal().hash_stable(hcx, hasher);
1600         self.constness().hash_stable(hcx, hasher);
1601     }
1602 }
1603
1604 impl<'tcx> TypeFoldable<'tcx> for ParamEnv<'tcx> {
1605     fn try_fold_with<F: ty::fold::FallibleTypeFolder<'tcx>>(
1606         self,
1607         folder: &mut F,
1608     ) -> Result<Self, F::Error> {
1609         Ok(ParamEnv::new(
1610             self.caller_bounds().try_fold_with(folder)?,
1611             self.reveal().try_fold_with(folder)?,
1612             self.constness(),
1613         ))
1614     }
1615 }
1616
1617 impl<'tcx> TypeVisitable<'tcx> for ParamEnv<'tcx> {
1618     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1619         self.caller_bounds().visit_with(visitor)?;
1620         self.reveal().visit_with(visitor)
1621     }
1622 }
1623
1624 impl<'tcx> ParamEnv<'tcx> {
1625     /// Construct a trait environment suitable for contexts where
1626     /// there are no where-clauses in scope. Hidden types (like `impl
1627     /// Trait`) are left hidden, so this is suitable for ordinary
1628     /// type-checking.
1629     #[inline]
1630     pub fn empty() -> Self {
1631         Self::new(List::empty(), Reveal::UserFacing, hir::Constness::NotConst)
1632     }
1633
1634     #[inline]
1635     pub fn caller_bounds(self) -> &'tcx List<Predicate<'tcx>> {
1636         self.packed.pointer()
1637     }
1638
1639     #[inline]
1640     pub fn reveal(self) -> traits::Reveal {
1641         self.packed.tag().reveal
1642     }
1643
1644     #[inline]
1645     pub fn constness(self) -> hir::Constness {
1646         self.packed.tag().constness
1647     }
1648
1649     #[inline]
1650     pub fn is_const(self) -> bool {
1651         self.packed.tag().constness == hir::Constness::Const
1652     }
1653
1654     /// Construct a trait environment with no where-clauses in scope
1655     /// where the values of all `impl Trait` and other hidden types
1656     /// are revealed. This is suitable for monomorphized, post-typeck
1657     /// environments like codegen or doing optimizations.
1658     ///
1659     /// N.B., if you want to have predicates in scope, use `ParamEnv::new`,
1660     /// or invoke `param_env.with_reveal_all()`.
1661     #[inline]
1662     pub fn reveal_all() -> Self {
1663         Self::new(List::empty(), Reveal::All, hir::Constness::NotConst)
1664     }
1665
1666     /// Construct a trait environment with the given set of predicates.
1667     #[inline]
1668     pub fn new(
1669         caller_bounds: &'tcx List<Predicate<'tcx>>,
1670         reveal: Reveal,
1671         constness: hir::Constness,
1672     ) -> Self {
1673         ty::ParamEnv { packed: CopyTaggedPtr::new(caller_bounds, ParamTag { reveal, constness }) }
1674     }
1675
1676     pub fn with_user_facing(mut self) -> Self {
1677         self.packed.set_tag(ParamTag { reveal: Reveal::UserFacing, ..self.packed.tag() });
1678         self
1679     }
1680
1681     #[inline]
1682     pub fn with_constness(mut self, constness: hir::Constness) -> Self {
1683         self.packed.set_tag(ParamTag { constness, ..self.packed.tag() });
1684         self
1685     }
1686
1687     #[inline]
1688     pub fn with_const(mut self) -> Self {
1689         self.packed.set_tag(ParamTag { constness: hir::Constness::Const, ..self.packed.tag() });
1690         self
1691     }
1692
1693     #[inline]
1694     pub fn without_const(mut self) -> Self {
1695         self.packed.set_tag(ParamTag { constness: hir::Constness::NotConst, ..self.packed.tag() });
1696         self
1697     }
1698
1699     #[inline]
1700     pub fn remap_constness_with(&mut self, mut constness: ty::BoundConstness) {
1701         *self = self.with_constness(constness.and(self.constness()))
1702     }
1703
1704     /// Returns a new parameter environment with the same clauses, but
1705     /// which "reveals" the true results of projections in all cases
1706     /// (even for associated types that are specializable). This is
1707     /// the desired behavior during codegen and certain other special
1708     /// contexts; normally though we want to use `Reveal::UserFacing`,
1709     /// which is the default.
1710     /// All opaque types in the caller_bounds of the `ParamEnv`
1711     /// will be normalized to their underlying types.
1712     /// See PR #65989 and issue #65918 for more details
1713     pub fn with_reveal_all_normalized(self, tcx: TyCtxt<'tcx>) -> Self {
1714         if self.packed.tag().reveal == traits::Reveal::All {
1715             return self;
1716         }
1717
1718         ParamEnv::new(
1719             tcx.normalize_opaque_types(self.caller_bounds()),
1720             Reveal::All,
1721             self.constness(),
1722         )
1723     }
1724
1725     /// Returns this same environment but with no caller bounds.
1726     #[inline]
1727     pub fn without_caller_bounds(self) -> Self {
1728         Self::new(List::empty(), self.reveal(), self.constness())
1729     }
1730
1731     /// Creates a suitable environment in which to perform trait
1732     /// queries on the given value. When type-checking, this is simply
1733     /// the pair of the environment plus value. But when reveal is set to
1734     /// All, then if `value` does not reference any type parameters, we will
1735     /// pair it with the empty environment. This improves caching and is generally
1736     /// invisible.
1737     ///
1738     /// N.B., we preserve the environment when type-checking because it
1739     /// is possible for the user to have wacky where-clauses like
1740     /// `where Box<u32>: Copy`, which are clearly never
1741     /// satisfiable. We generally want to behave as if they were true,
1742     /// although the surrounding function is never reachable.
1743     pub fn and<T: TypeVisitable<'tcx>>(self, value: T) -> ParamEnvAnd<'tcx, T> {
1744         match self.reveal() {
1745             Reveal::UserFacing => ParamEnvAnd { param_env: self, value },
1746
1747             Reveal::All => {
1748                 if value.is_global() {
1749                     ParamEnvAnd { param_env: self.without_caller_bounds(), value }
1750                 } else {
1751                     ParamEnvAnd { param_env: self, value }
1752                 }
1753             }
1754         }
1755     }
1756 }
1757
1758 // FIXME(ecstaticmorse): Audit all occurrences of `without_const().to_predicate(tcx)` to ensure that
1759 // the constness of trait bounds is being propagated correctly.
1760 impl<'tcx> PolyTraitRef<'tcx> {
1761     #[inline]
1762     pub fn with_constness(self, constness: BoundConstness) -> PolyTraitPredicate<'tcx> {
1763         self.map_bound(|trait_ref| ty::TraitPredicate {
1764             trait_ref,
1765             constness,
1766             polarity: ty::ImplPolarity::Positive,
1767         })
1768     }
1769
1770     #[inline]
1771     pub fn without_const(self) -> PolyTraitPredicate<'tcx> {
1772         self.with_constness(BoundConstness::NotConst)
1773     }
1774 }
1775
1776 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
1777 #[derive(HashStable, Lift)]
1778 pub struct ParamEnvAnd<'tcx, T> {
1779     pub param_env: ParamEnv<'tcx>,
1780     pub value: T,
1781 }
1782
1783 impl<'tcx, T> ParamEnvAnd<'tcx, T> {
1784     pub fn into_parts(self) -> (ParamEnv<'tcx>, T) {
1785         (self.param_env, self.value)
1786     }
1787
1788     #[inline]
1789     pub fn without_const(mut self) -> Self {
1790         self.param_env = self.param_env.without_const();
1791         self
1792     }
1793 }
1794
1795 #[derive(Copy, Clone, Debug, HashStable, Encodable, Decodable)]
1796 pub struct Destructor {
1797     /// The `DefId` of the destructor method
1798     pub did: DefId,
1799     /// The constness of the destructor method
1800     pub constness: hir::Constness,
1801 }
1802
1803 bitflags! {
1804     #[derive(HashStable, TyEncodable, TyDecodable)]
1805     pub struct VariantFlags: u32 {
1806         const NO_VARIANT_FLAGS        = 0;
1807         /// Indicates whether the field list of this variant is `#[non_exhaustive]`.
1808         const IS_FIELD_LIST_NON_EXHAUSTIVE = 1 << 0;
1809         /// Indicates whether this variant was obtained as part of recovering from
1810         /// a syntactic error. May be incomplete or bogus.
1811         const IS_RECOVERED = 1 << 1;
1812     }
1813 }
1814
1815 /// Definition of a variant -- a struct's fields or an enum variant.
1816 #[derive(Debug, HashStable, TyEncodable, TyDecodable)]
1817 pub struct VariantDef {
1818     /// `DefId` that identifies the variant itself.
1819     /// If this variant belongs to a struct or union, then this is a copy of its `DefId`.
1820     pub def_id: DefId,
1821     /// `DefId` that identifies the variant's constructor.
1822     /// If this variant is a struct variant, then this is `None`.
1823     pub ctor: Option<(CtorKind, DefId)>,
1824     /// Variant or struct name.
1825     pub name: Symbol,
1826     /// Discriminant of this variant.
1827     pub discr: VariantDiscr,
1828     /// Fields of this variant.
1829     pub fields: Vec<FieldDef>,
1830     /// Flags of the variant (e.g. is field list non-exhaustive)?
1831     flags: VariantFlags,
1832 }
1833
1834 impl VariantDef {
1835     /// Creates a new `VariantDef`.
1836     ///
1837     /// `variant_did` is the `DefId` that identifies the enum variant (if this `VariantDef`
1838     /// represents an enum variant).
1839     ///
1840     /// `ctor_did` is the `DefId` that identifies the constructor of unit or
1841     /// tuple-variants/structs. If this is a `struct`-variant then this should be `None`.
1842     ///
1843     /// `parent_did` is the `DefId` of the `AdtDef` representing the enum or struct that
1844     /// owns this variant. It is used for checking if a struct has `#[non_exhaustive]` w/out having
1845     /// to go through the redirect of checking the ctor's attributes - but compiling a small crate
1846     /// requires loading the `AdtDef`s for all the structs in the universe (e.g., coherence for any
1847     /// built-in trait), and we do not want to load attributes twice.
1848     ///
1849     /// If someone speeds up attribute loading to not be a performance concern, they can
1850     /// remove this hack and use the constructor `DefId` everywhere.
1851     pub fn new(
1852         name: Symbol,
1853         variant_did: Option<DefId>,
1854         ctor: Option<(CtorKind, DefId)>,
1855         discr: VariantDiscr,
1856         fields: Vec<FieldDef>,
1857         adt_kind: AdtKind,
1858         parent_did: DefId,
1859         recovered: bool,
1860         is_field_list_non_exhaustive: bool,
1861     ) -> Self {
1862         debug!(
1863             "VariantDef::new(name = {:?}, variant_did = {:?}, ctor = {:?}, discr = {:?},
1864              fields = {:?}, adt_kind = {:?}, parent_did = {:?})",
1865             name, variant_did, ctor, discr, fields, adt_kind, parent_did,
1866         );
1867
1868         let mut flags = VariantFlags::NO_VARIANT_FLAGS;
1869         if is_field_list_non_exhaustive {
1870             flags |= VariantFlags::IS_FIELD_LIST_NON_EXHAUSTIVE;
1871         }
1872
1873         if recovered {
1874             flags |= VariantFlags::IS_RECOVERED;
1875         }
1876
1877         VariantDef { def_id: variant_did.unwrap_or(parent_did), ctor, name, discr, fields, flags }
1878     }
1879
1880     /// Is this field list non-exhaustive?
1881     #[inline]
1882     pub fn is_field_list_non_exhaustive(&self) -> bool {
1883         self.flags.intersects(VariantFlags::IS_FIELD_LIST_NON_EXHAUSTIVE)
1884     }
1885
1886     /// Was this variant obtained as part of recovering from a syntactic error?
1887     #[inline]
1888     pub fn is_recovered(&self) -> bool {
1889         self.flags.intersects(VariantFlags::IS_RECOVERED)
1890     }
1891
1892     /// Computes the `Ident` of this variant by looking up the `Span`
1893     pub fn ident(&self, tcx: TyCtxt<'_>) -> Ident {
1894         Ident::new(self.name, tcx.def_ident_span(self.def_id).unwrap())
1895     }
1896
1897     #[inline]
1898     pub fn ctor_kind(&self) -> Option<CtorKind> {
1899         self.ctor.map(|(kind, _)| kind)
1900     }
1901
1902     #[inline]
1903     pub fn ctor_def_id(&self) -> Option<DefId> {
1904         self.ctor.map(|(_, def_id)| def_id)
1905     }
1906 }
1907
1908 impl PartialEq for VariantDef {
1909     #[inline]
1910     fn eq(&self, other: &Self) -> bool {
1911         // There should be only one `VariantDef` for each `def_id`, therefore
1912         // it is fine to implement `PartialEq` only based on `def_id`.
1913         //
1914         // Below, we exhaustively destructure `self` and `other` so that if the
1915         // definition of `VariantDef` changes, a compile-error will be produced,
1916         // reminding us to revisit this assumption.
1917
1918         let Self { def_id: lhs_def_id, ctor: _, name: _, discr: _, fields: _, flags: _ } = &self;
1919         let Self { def_id: rhs_def_id, ctor: _, name: _, discr: _, fields: _, flags: _ } = other;
1920         lhs_def_id == rhs_def_id
1921     }
1922 }
1923
1924 impl Eq for VariantDef {}
1925
1926 impl Hash for VariantDef {
1927     #[inline]
1928     fn hash<H: Hasher>(&self, s: &mut H) {
1929         // There should be only one `VariantDef` for each `def_id`, therefore
1930         // it is fine to implement `Hash` only based on `def_id`.
1931         //
1932         // Below, we exhaustively destructure `self` so that if the definition
1933         // of `VariantDef` changes, a compile-error will be produced, reminding
1934         // us to revisit this assumption.
1935
1936         let Self { def_id, ctor: _, name: _, discr: _, fields: _, flags: _ } = &self;
1937         def_id.hash(s)
1938     }
1939 }
1940
1941 #[derive(Copy, Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
1942 pub enum VariantDiscr {
1943     /// Explicit value for this variant, i.e., `X = 123`.
1944     /// The `DefId` corresponds to the embedded constant.
1945     Explicit(DefId),
1946
1947     /// The previous variant's discriminant plus one.
1948     /// For efficiency reasons, the distance from the
1949     /// last `Explicit` discriminant is being stored,
1950     /// or `0` for the first variant, if it has none.
1951     Relative(u32),
1952 }
1953
1954 #[derive(Debug, HashStable, TyEncodable, TyDecodable)]
1955 pub struct FieldDef {
1956     pub did: DefId,
1957     pub name: Symbol,
1958     pub vis: Visibility<DefId>,
1959 }
1960
1961 impl PartialEq for FieldDef {
1962     #[inline]
1963     fn eq(&self, other: &Self) -> bool {
1964         // There should be only one `FieldDef` for each `did`, therefore it is
1965         // fine to implement `PartialEq` only based on `did`.
1966         //
1967         // Below, we exhaustively destructure `self` so that if the definition
1968         // of `FieldDef` changes, a compile-error will be produced, reminding
1969         // us to revisit this assumption.
1970
1971         let Self { did: lhs_did, name: _, vis: _ } = &self;
1972
1973         let Self { did: rhs_did, name: _, vis: _ } = other;
1974
1975         lhs_did == rhs_did
1976     }
1977 }
1978
1979 impl Eq for FieldDef {}
1980
1981 impl Hash for FieldDef {
1982     #[inline]
1983     fn hash<H: Hasher>(&self, s: &mut H) {
1984         // There should be only one `FieldDef` for each `did`, therefore it is
1985         // fine to implement `Hash` only based on `did`.
1986         //
1987         // Below, we exhaustively destructure `self` so that if the definition
1988         // of `FieldDef` changes, a compile-error will be produced, reminding
1989         // us to revisit this assumption.
1990
1991         let Self { did, name: _, vis: _ } = &self;
1992
1993         did.hash(s)
1994     }
1995 }
1996
1997 bitflags! {
1998     #[derive(TyEncodable, TyDecodable, Default, HashStable)]
1999     pub struct ReprFlags: u8 {
2000         const IS_C               = 1 << 0;
2001         const IS_SIMD            = 1 << 1;
2002         const IS_TRANSPARENT     = 1 << 2;
2003         // Internal only for now. If true, don't reorder fields.
2004         const IS_LINEAR          = 1 << 3;
2005         // If true, the type's layout can be randomized using
2006         // the seed stored in `ReprOptions.layout_seed`
2007         const RANDOMIZE_LAYOUT   = 1 << 4;
2008         // Any of these flags being set prevent field reordering optimisation.
2009         const IS_UNOPTIMISABLE   = ReprFlags::IS_C.bits
2010                                  | ReprFlags::IS_SIMD.bits
2011                                  | ReprFlags::IS_LINEAR.bits;
2012     }
2013 }
2014
2015 /// Represents the repr options provided by the user,
2016 #[derive(Copy, Clone, Debug, Eq, PartialEq, TyEncodable, TyDecodable, Default, HashStable)]
2017 pub struct ReprOptions {
2018     pub int: Option<attr::IntType>,
2019     pub align: Option<Align>,
2020     pub pack: Option<Align>,
2021     pub flags: ReprFlags,
2022     /// The seed to be used for randomizing a type's layout
2023     ///
2024     /// Note: This could technically be a `[u8; 16]` (a `u128`) which would
2025     /// be the "most accurate" hash as it'd encompass the item and crate
2026     /// hash without loss, but it does pay the price of being larger.
2027     /// Everything's a tradeoff, a `u64` seed should be sufficient for our
2028     /// purposes (primarily `-Z randomize-layout`)
2029     pub field_shuffle_seed: u64,
2030 }
2031
2032 impl ReprOptions {
2033     pub fn new(tcx: TyCtxt<'_>, did: DefId) -> ReprOptions {
2034         let mut flags = ReprFlags::empty();
2035         let mut size = None;
2036         let mut max_align: Option<Align> = None;
2037         let mut min_pack: Option<Align> = None;
2038
2039         // Generate a deterministically-derived seed from the item's path hash
2040         // to allow for cross-crate compilation to actually work
2041         let mut field_shuffle_seed = tcx.def_path_hash(did).0.to_smaller_hash();
2042
2043         // If the user defined a custom seed for layout randomization, xor the item's
2044         // path hash with the user defined seed, this will allowing determinism while
2045         // still allowing users to further randomize layout generation for e.g. fuzzing
2046         if let Some(user_seed) = tcx.sess.opts.unstable_opts.layout_seed {
2047             field_shuffle_seed ^= user_seed;
2048         }
2049
2050         for attr in tcx.get_attrs(did, sym::repr) {
2051             for r in attr::parse_repr_attr(&tcx.sess, attr) {
2052                 flags.insert(match r {
2053                     attr::ReprC => ReprFlags::IS_C,
2054                     attr::ReprPacked(pack) => {
2055                         let pack = Align::from_bytes(pack as u64).unwrap();
2056                         min_pack = Some(if let Some(min_pack) = min_pack {
2057                             min_pack.min(pack)
2058                         } else {
2059                             pack
2060                         });
2061                         ReprFlags::empty()
2062                     }
2063                     attr::ReprTransparent => ReprFlags::IS_TRANSPARENT,
2064                     attr::ReprSimd => ReprFlags::IS_SIMD,
2065                     attr::ReprInt(i) => {
2066                         size = Some(i);
2067                         ReprFlags::empty()
2068                     }
2069                     attr::ReprAlign(align) => {
2070                         max_align = max_align.max(Some(Align::from_bytes(align as u64).unwrap()));
2071                         ReprFlags::empty()
2072                     }
2073                 });
2074             }
2075         }
2076
2077         // If `-Z randomize-layout` was enabled for the type definition then we can
2078         // consider performing layout randomization
2079         if tcx.sess.opts.unstable_opts.randomize_layout {
2080             flags.insert(ReprFlags::RANDOMIZE_LAYOUT);
2081         }
2082
2083         // This is here instead of layout because the choice must make it into metadata.
2084         if !tcx.consider_optimizing(|| format!("Reorder fields of {:?}", tcx.def_path_str(did))) {
2085             flags.insert(ReprFlags::IS_LINEAR);
2086         }
2087
2088         Self { int: size, align: max_align, pack: min_pack, flags, field_shuffle_seed }
2089     }
2090
2091     #[inline]
2092     pub fn simd(&self) -> bool {
2093         self.flags.contains(ReprFlags::IS_SIMD)
2094     }
2095
2096     #[inline]
2097     pub fn c(&self) -> bool {
2098         self.flags.contains(ReprFlags::IS_C)
2099     }
2100
2101     #[inline]
2102     pub fn packed(&self) -> bool {
2103         self.pack.is_some()
2104     }
2105
2106     #[inline]
2107     pub fn transparent(&self) -> bool {
2108         self.flags.contains(ReprFlags::IS_TRANSPARENT)
2109     }
2110
2111     #[inline]
2112     pub fn linear(&self) -> bool {
2113         self.flags.contains(ReprFlags::IS_LINEAR)
2114     }
2115
2116     /// Returns the discriminant type, given these `repr` options.
2117     /// This must only be called on enums!
2118     pub fn discr_type(&self) -> attr::IntType {
2119         self.int.unwrap_or(attr::SignedInt(ast::IntTy::Isize))
2120     }
2121
2122     /// Returns `true` if this `#[repr()]` should inhabit "smart enum
2123     /// layout" optimizations, such as representing `Foo<&T>` as a
2124     /// single pointer.
2125     pub fn inhibit_enum_layout_opt(&self) -> bool {
2126         self.c() || self.int.is_some()
2127     }
2128
2129     /// Returns `true` if this `#[repr()]` should inhibit struct field reordering
2130     /// optimizations, such as with `repr(C)`, `repr(packed(1))`, or `repr(<int>)`.
2131     pub fn inhibit_struct_field_reordering_opt(&self) -> bool {
2132         if let Some(pack) = self.pack {
2133             if pack.bytes() == 1 {
2134                 return true;
2135             }
2136         }
2137
2138         self.flags.intersects(ReprFlags::IS_UNOPTIMISABLE) || self.int.is_some()
2139     }
2140
2141     /// Returns `true` if this type is valid for reordering and `-Z randomize-layout`
2142     /// was enabled for its declaration crate
2143     pub fn can_randomize_type_layout(&self) -> bool {
2144         !self.inhibit_struct_field_reordering_opt()
2145             && self.flags.contains(ReprFlags::RANDOMIZE_LAYOUT)
2146     }
2147
2148     /// Returns `true` if this `#[repr()]` should inhibit union ABI optimisations.
2149     pub fn inhibit_union_abi_opt(&self) -> bool {
2150         self.c()
2151     }
2152 }
2153
2154 impl<'tcx> FieldDef {
2155     /// Returns the type of this field. The resulting type is not normalized. The `subst` is
2156     /// typically obtained via the second field of [`TyKind::Adt`].
2157     pub fn ty(&self, tcx: TyCtxt<'tcx>, subst: SubstsRef<'tcx>) -> Ty<'tcx> {
2158         tcx.bound_type_of(self.did).subst(tcx, subst)
2159     }
2160
2161     /// Computes the `Ident` of this variant by looking up the `Span`
2162     pub fn ident(&self, tcx: TyCtxt<'_>) -> Ident {
2163         Ident::new(self.name, tcx.def_ident_span(self.did).unwrap())
2164     }
2165 }
2166
2167 pub type Attributes<'tcx> = impl Iterator<Item = &'tcx ast::Attribute>;
2168 #[derive(Debug, PartialEq, Eq)]
2169 pub enum ImplOverlapKind {
2170     /// These impls are always allowed to overlap.
2171     Permitted {
2172         /// Whether or not the impl is permitted due to the trait being a `#[marker]` trait
2173         marker: bool,
2174     },
2175     /// These impls are allowed to overlap, but that raises
2176     /// an issue #33140 future-compatibility warning.
2177     ///
2178     /// Some background: in Rust 1.0, the trait-object types `Send + Sync` (today's
2179     /// `dyn Send + Sync`) and `Sync + Send` (now `dyn Sync + Send`) were different.
2180     ///
2181     /// The widely-used version 0.1.0 of the crate `traitobject` had accidentally relied
2182     /// that difference, making what reduces to the following set of impls:
2183     ///
2184     /// ```compile_fail,(E0119)
2185     /// trait Trait {}
2186     /// impl Trait for dyn Send + Sync {}
2187     /// impl Trait for dyn Sync + Send {}
2188     /// ```
2189     ///
2190     /// Obviously, once we made these types be identical, that code causes a coherence
2191     /// error and a fairly big headache for us. However, luckily for us, the trait
2192     /// `Trait` used in this case is basically a marker trait, and therefore having
2193     /// overlapping impls for it is sound.
2194     ///
2195     /// To handle this, we basically regard the trait as a marker trait, with an additional
2196     /// future-compatibility warning. To avoid accidentally "stabilizing" this feature,
2197     /// it has the following restrictions:
2198     ///
2199     /// 1. The trait must indeed be a marker-like trait (i.e., no items), and must be
2200     /// positive impls.
2201     /// 2. The trait-ref of both impls must be equal.
2202     /// 3. The trait-ref of both impls must be a trait object type consisting only of
2203     /// marker traits.
2204     /// 4. Neither of the impls can have any where-clauses.
2205     ///
2206     /// Once `traitobject` 0.1.0 is no longer an active concern, this hack can be removed.
2207     Issue33140,
2208 }
2209
2210 impl<'tcx> TyCtxt<'tcx> {
2211     pub fn typeck_body(self, body: hir::BodyId) -> &'tcx TypeckResults<'tcx> {
2212         self.typeck(self.hir().body_owner_def_id(body))
2213     }
2214
2215     pub fn provided_trait_methods(self, id: DefId) -> impl 'tcx + Iterator<Item = &'tcx AssocItem> {
2216         self.associated_items(id)
2217             .in_definition_order()
2218             .filter(move |item| item.kind == AssocKind::Fn && item.defaultness(self).has_value())
2219     }
2220
2221     /// Look up the name of a definition across crates. This does not look at HIR.
2222     pub fn opt_item_name(self, def_id: DefId) -> Option<Symbol> {
2223         if let Some(cnum) = def_id.as_crate_root() {
2224             Some(self.crate_name(cnum))
2225         } else {
2226             let def_key = self.def_key(def_id);
2227             match def_key.disambiguated_data.data {
2228                 // The name of a constructor is that of its parent.
2229                 rustc_hir::definitions::DefPathData::Ctor => self
2230                     .opt_item_name(DefId { krate: def_id.krate, index: def_key.parent.unwrap() }),
2231                 // The name of opaque types only exists in HIR.
2232                 rustc_hir::definitions::DefPathData::ImplTrait
2233                     if let Some(def_id) = def_id.as_local() =>
2234                     self.hir().opt_name(self.hir().local_def_id_to_hir_id(def_id)),
2235                 _ => def_key.get_opt_name(),
2236             }
2237         }
2238     }
2239
2240     /// Look up the name of a definition across crates. This does not look at HIR.
2241     ///
2242     /// This method will ICE if the corresponding item does not have a name.  In these cases, use
2243     /// [`opt_item_name`] instead.
2244     ///
2245     /// [`opt_item_name`]: Self::opt_item_name
2246     pub fn item_name(self, id: DefId) -> Symbol {
2247         self.opt_item_name(id).unwrap_or_else(|| {
2248             bug!("item_name: no name for {:?}", self.def_path(id));
2249         })
2250     }
2251
2252     /// Look up the name and span of a definition.
2253     ///
2254     /// See [`item_name`][Self::item_name] for more information.
2255     pub fn opt_item_ident(self, def_id: DefId) -> Option<Ident> {
2256         let def = self.opt_item_name(def_id)?;
2257         let span = def_id
2258             .as_local()
2259             .and_then(|id| self.def_ident_span(id))
2260             .unwrap_or(rustc_span::DUMMY_SP);
2261         Some(Ident::new(def, span))
2262     }
2263
2264     pub fn opt_associated_item(self, def_id: DefId) -> Option<&'tcx AssocItem> {
2265         if let DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy = self.def_kind(def_id) {
2266             Some(self.associated_item(def_id))
2267         } else {
2268             None
2269         }
2270     }
2271
2272     pub fn field_index(self, hir_id: hir::HirId, typeck_results: &TypeckResults<'_>) -> usize {
2273         typeck_results.field_indices().get(hir_id).cloned().expect("no index for a field")
2274     }
2275
2276     pub fn find_field_index(self, ident: Ident, variant: &VariantDef) -> Option<usize> {
2277         variant
2278             .fields
2279             .iter()
2280             .position(|field| self.hygienic_eq(ident, field.ident(self), variant.def_id))
2281     }
2282
2283     /// Returns `true` if the impls are the same polarity and the trait either
2284     /// has no items or is annotated `#[marker]` and prevents item overrides.
2285     pub fn impls_are_allowed_to_overlap(
2286         self,
2287         def_id1: DefId,
2288         def_id2: DefId,
2289     ) -> Option<ImplOverlapKind> {
2290         // If either trait impl references an error, they're allowed to overlap,
2291         // as one of them essentially doesn't exist.
2292         if self.impl_trait_ref(def_id1).map_or(false, |tr| tr.references_error())
2293             || self.impl_trait_ref(def_id2).map_or(false, |tr| tr.references_error())
2294         {
2295             return Some(ImplOverlapKind::Permitted { marker: false });
2296         }
2297
2298         match (self.impl_polarity(def_id1), self.impl_polarity(def_id2)) {
2299             (ImplPolarity::Reservation, _) | (_, ImplPolarity::Reservation) => {
2300                 // `#[rustc_reservation_impl]` impls don't overlap with anything
2301                 debug!(
2302                     "impls_are_allowed_to_overlap({:?}, {:?}) = Some(Permitted) (reservations)",
2303                     def_id1, def_id2
2304                 );
2305                 return Some(ImplOverlapKind::Permitted { marker: false });
2306             }
2307             (ImplPolarity::Positive, ImplPolarity::Negative)
2308             | (ImplPolarity::Negative, ImplPolarity::Positive) => {
2309                 // `impl AutoTrait for Type` + `impl !AutoTrait for Type`
2310                 debug!(
2311                     "impls_are_allowed_to_overlap({:?}, {:?}) - None (differing polarities)",
2312                     def_id1, def_id2
2313                 );
2314                 return None;
2315             }
2316             (ImplPolarity::Positive, ImplPolarity::Positive)
2317             | (ImplPolarity::Negative, ImplPolarity::Negative) => {}
2318         };
2319
2320         let is_marker_overlap = {
2321             let is_marker_impl = |def_id: DefId| -> bool {
2322                 let trait_ref = self.impl_trait_ref(def_id);
2323                 trait_ref.map_or(false, |tr| self.trait_def(tr.def_id).is_marker)
2324             };
2325             is_marker_impl(def_id1) && is_marker_impl(def_id2)
2326         };
2327
2328         if is_marker_overlap {
2329             debug!(
2330                 "impls_are_allowed_to_overlap({:?}, {:?}) = Some(Permitted) (marker overlap)",
2331                 def_id1, def_id2
2332             );
2333             Some(ImplOverlapKind::Permitted { marker: true })
2334         } else {
2335             if let Some(self_ty1) = self.issue33140_self_ty(def_id1) {
2336                 if let Some(self_ty2) = self.issue33140_self_ty(def_id2) {
2337                     if self_ty1 == self_ty2 {
2338                         debug!(
2339                             "impls_are_allowed_to_overlap({:?}, {:?}) - issue #33140 HACK",
2340                             def_id1, def_id2
2341                         );
2342                         return Some(ImplOverlapKind::Issue33140);
2343                     } else {
2344                         debug!(
2345                             "impls_are_allowed_to_overlap({:?}, {:?}) - found {:?} != {:?}",
2346                             def_id1, def_id2, self_ty1, self_ty2
2347                         );
2348                     }
2349                 }
2350             }
2351
2352             debug!("impls_are_allowed_to_overlap({:?}, {:?}) = None", def_id1, def_id2);
2353             None
2354         }
2355     }
2356
2357     /// Returns `ty::VariantDef` if `res` refers to a struct,
2358     /// or variant or their constructors, panics otherwise.
2359     pub fn expect_variant_res(self, res: Res) -> &'tcx VariantDef {
2360         match res {
2361             Res::Def(DefKind::Variant, did) => {
2362                 let enum_did = self.parent(did);
2363                 self.adt_def(enum_did).variant_with_id(did)
2364             }
2365             Res::Def(DefKind::Struct | DefKind::Union, did) => self.adt_def(did).non_enum_variant(),
2366             Res::Def(DefKind::Ctor(CtorOf::Variant, ..), variant_ctor_did) => {
2367                 let variant_did = self.parent(variant_ctor_did);
2368                 let enum_did = self.parent(variant_did);
2369                 self.adt_def(enum_did).variant_with_ctor_id(variant_ctor_did)
2370             }
2371             Res::Def(DefKind::Ctor(CtorOf::Struct, ..), ctor_did) => {
2372                 let struct_did = self.parent(ctor_did);
2373                 self.adt_def(struct_did).non_enum_variant()
2374             }
2375             _ => bug!("expect_variant_res used with unexpected res {:?}", res),
2376         }
2377     }
2378
2379     /// Returns the possibly-auto-generated MIR of a `(DefId, Subst)` pair.
2380     #[instrument(skip(self), level = "debug")]
2381     pub fn instance_mir(self, instance: ty::InstanceDef<'tcx>) -> &'tcx Body<'tcx> {
2382         match instance {
2383             ty::InstanceDef::Item(def) => {
2384                 debug!("calling def_kind on def: {:?}", def);
2385                 let def_kind = self.def_kind(def.did);
2386                 debug!("returned from def_kind: {:?}", def_kind);
2387                 match def_kind {
2388                     DefKind::Const
2389                     | DefKind::Static(..)
2390                     | DefKind::AssocConst
2391                     | DefKind::Ctor(..)
2392                     | DefKind::AnonConst
2393                     | DefKind::InlineConst => self.mir_for_ctfe_opt_const_arg(def),
2394                     // If the caller wants `mir_for_ctfe` of a function they should not be using
2395                     // `instance_mir`, so we'll assume const fn also wants the optimized version.
2396                     _ => {
2397                         assert_eq!(def.const_param_did, None);
2398                         self.optimized_mir(def.did)
2399                     }
2400                 }
2401             }
2402             ty::InstanceDef::VTableShim(..)
2403             | ty::InstanceDef::ReifyShim(..)
2404             | ty::InstanceDef::Intrinsic(..)
2405             | ty::InstanceDef::FnPtrShim(..)
2406             | ty::InstanceDef::Virtual(..)
2407             | ty::InstanceDef::ClosureOnceShim { .. }
2408             | ty::InstanceDef::DropGlue(..)
2409             | ty::InstanceDef::CloneShim(..) => self.mir_shims(instance),
2410         }
2411     }
2412
2413     // FIXME(@lcnr): Remove this function.
2414     pub fn get_attrs_unchecked(self, did: DefId) -> &'tcx [ast::Attribute] {
2415         if let Some(did) = did.as_local() {
2416             self.hir().attrs(self.hir().local_def_id_to_hir_id(did))
2417         } else {
2418             self.item_attrs(did)
2419         }
2420     }
2421
2422     /// Gets all attributes with the given name.
2423     pub fn get_attrs(self, did: DefId, attr: Symbol) -> ty::Attributes<'tcx> {
2424         let filter_fn = move |a: &&ast::Attribute| a.has_name(attr);
2425         if let Some(did) = did.as_local() {
2426             self.hir().attrs(self.hir().local_def_id_to_hir_id(did)).iter().filter(filter_fn)
2427         } else if cfg!(debug_assertions) && rustc_feature::is_builtin_only_local(attr) {
2428             bug!("tried to access the `only_local` attribute `{}` from an extern crate", attr);
2429         } else {
2430             self.item_attrs(did).iter().filter(filter_fn)
2431         }
2432     }
2433
2434     pub fn get_attr(self, did: DefId, attr: Symbol) -> Option<&'tcx ast::Attribute> {
2435         if cfg!(debug_assertions) && !rustc_feature::is_valid_for_get_attr(attr) {
2436             bug!("get_attr: unexpected called with DefId `{:?}`, attr `{:?}`", did, attr);
2437         } else {
2438             self.get_attrs(did, attr).next()
2439         }
2440     }
2441
2442     /// Determines whether an item is annotated with an attribute.
2443     pub fn has_attr(self, did: DefId, attr: Symbol) -> bool {
2444         if cfg!(debug_assertions) && !did.is_local() && rustc_feature::is_builtin_only_local(attr) {
2445             bug!("tried to access the `only_local` attribute `{}` from an extern crate", attr);
2446         } else {
2447             self.get_attrs(did, attr).next().is_some()
2448         }
2449     }
2450
2451     /// Returns `true` if this is an `auto trait`.
2452     pub fn trait_is_auto(self, trait_def_id: DefId) -> bool {
2453         self.trait_def(trait_def_id).has_auto_impl
2454     }
2455
2456     pub fn trait_is_coinductive(self, trait_def_id: DefId) -> bool {
2457         self.trait_is_auto(trait_def_id) || self.lang_items().sized_trait() == Some(trait_def_id)
2458     }
2459
2460     /// Returns layout of a generator. Layout might be unavailable if the
2461     /// generator is tainted by errors.
2462     pub fn generator_layout(self, def_id: DefId) -> Option<&'tcx GeneratorLayout<'tcx>> {
2463         self.optimized_mir(def_id).generator_layout()
2464     }
2465
2466     /// Given the `DefId` of an impl, returns the `DefId` of the trait it implements.
2467     /// If it implements no trait, returns `None`.
2468     pub fn trait_id_of_impl(self, def_id: DefId) -> Option<DefId> {
2469         self.impl_trait_ref(def_id).map(|tr| tr.def_id)
2470     }
2471
2472     /// If the given `DefId` describes an item belonging to a trait,
2473     /// returns the `DefId` of the trait that the trait item belongs to;
2474     /// otherwise, returns `None`.
2475     pub fn trait_of_item(self, def_id: DefId) -> Option<DefId> {
2476         if let DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy = self.def_kind(def_id) {
2477             let parent = self.parent(def_id);
2478             if let DefKind::Trait | DefKind::TraitAlias = self.def_kind(parent) {
2479                 return Some(parent);
2480             }
2481         }
2482         None
2483     }
2484
2485     /// If the given `DefId` describes a method belonging to an impl, returns the
2486     /// `DefId` of the impl that the method belongs to; otherwise, returns `None`.
2487     pub fn impl_of_method(self, def_id: DefId) -> Option<DefId> {
2488         if let DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy = self.def_kind(def_id) {
2489             let parent = self.parent(def_id);
2490             if let DefKind::Impl = self.def_kind(parent) {
2491                 return Some(parent);
2492             }
2493         }
2494         None
2495     }
2496
2497     /// If the given `DefId` belongs to a trait that was automatically derived, returns `true`.
2498     pub fn is_builtin_derive(self, def_id: DefId) -> bool {
2499         self.has_attr(def_id, sym::automatically_derived)
2500     }
2501
2502     /// Looks up the span of `impl_did` if the impl is local; otherwise returns `Err`
2503     /// with the name of the crate containing the impl.
2504     pub fn span_of_impl(self, impl_def_id: DefId) -> Result<Span, Symbol> {
2505         if let Some(impl_def_id) = impl_def_id.as_local() {
2506             Ok(self.def_span(impl_def_id))
2507         } else {
2508             Err(self.crate_name(impl_def_id.krate))
2509         }
2510     }
2511
2512     /// Hygienically compares a use-site name (`use_name`) for a field or an associated item with
2513     /// its supposed definition name (`def_name`). The method also needs `DefId` of the supposed
2514     /// definition's parent/scope to perform comparison.
2515     pub fn hygienic_eq(self, use_name: Ident, def_name: Ident, def_parent_def_id: DefId) -> bool {
2516         // We could use `Ident::eq` here, but we deliberately don't. The name
2517         // comparison fails frequently, and we want to avoid the expensive
2518         // `normalize_to_macros_2_0()` calls required for the span comparison whenever possible.
2519         use_name.name == def_name.name
2520             && use_name
2521                 .span
2522                 .ctxt()
2523                 .hygienic_eq(def_name.span.ctxt(), self.expn_that_defined(def_parent_def_id))
2524     }
2525
2526     pub fn adjust_ident(self, mut ident: Ident, scope: DefId) -> Ident {
2527         ident.span.normalize_to_macros_2_0_and_adjust(self.expn_that_defined(scope));
2528         ident
2529     }
2530
2531     pub fn adjust_ident_and_get_scope(
2532         self,
2533         mut ident: Ident,
2534         scope: DefId,
2535         block: hir::HirId,
2536     ) -> (Ident, DefId) {
2537         let scope = ident
2538             .span
2539             .normalize_to_macros_2_0_and_adjust(self.expn_that_defined(scope))
2540             .and_then(|actual_expansion| actual_expansion.expn_data().parent_module)
2541             .unwrap_or_else(|| self.parent_module(block).to_def_id());
2542         (ident, scope)
2543     }
2544
2545     /// Returns `true` if the debuginfo for `span` should be collapsed to the outermost expansion
2546     /// site. Only applies when `Span` is the result of macro expansion.
2547     ///
2548     /// - If the `collapse_debuginfo` feature is enabled then debuginfo is not collapsed by default
2549     ///   and only when a macro definition is annotated with `#[collapse_debuginfo]`.
2550     /// - If `collapse_debuginfo` is not enabled, then debuginfo is collapsed by default.
2551     ///
2552     /// When `-Zdebug-macros` is provided then debuginfo will never be collapsed.
2553     pub fn should_collapse_debuginfo(self, span: Span) -> bool {
2554         !self.sess.opts.unstable_opts.debug_macros
2555             && if self.features().collapse_debuginfo {
2556                 span.in_macro_expansion_with_collapse_debuginfo()
2557             } else {
2558                 // Inlined spans should not be collapsed as that leads to all of the
2559                 // inlined code being attributed to the inline callsite.
2560                 span.from_expansion() && !span.is_inlined()
2561             }
2562     }
2563
2564     pub fn is_object_safe(self, key: DefId) -> bool {
2565         self.object_safety_violations(key).is_empty()
2566     }
2567
2568     #[inline]
2569     pub fn is_const_fn_raw(self, def_id: DefId) -> bool {
2570         matches!(self.def_kind(def_id), DefKind::Fn | DefKind::AssocFn | DefKind::Ctor(..))
2571             && self.constness(def_id) == hir::Constness::Const
2572     }
2573
2574     #[inline]
2575     pub fn is_const_default_method(self, def_id: DefId) -> bool {
2576         matches!(self.trait_of_item(def_id), Some(trait_id) if self.has_attr(trait_id, sym::const_trait))
2577     }
2578
2579     pub fn impl_trait_in_trait_parent(self, mut def_id: DefId) -> DefId {
2580         while let def_kind = self.def_kind(def_id) && def_kind != DefKind::AssocFn {
2581             debug_assert_eq!(def_kind, DefKind::ImplTraitPlaceholder);
2582             def_id = self.parent(def_id);
2583         }
2584         def_id
2585     }
2586 }
2587
2588 /// Yields the parent function's `LocalDefId` if `def_id` is an `impl Trait` definition.
2589 pub fn is_impl_trait_defn(tcx: TyCtxt<'_>, def_id: DefId) -> Option<LocalDefId> {
2590     let def_id = def_id.as_local()?;
2591     if let Node::Item(item) = tcx.hir().get_by_def_id(def_id) {
2592         if let hir::ItemKind::OpaqueTy(ref opaque_ty) = item.kind {
2593             return match opaque_ty.origin {
2594                 hir::OpaqueTyOrigin::FnReturn(parent) | hir::OpaqueTyOrigin::AsyncFn(parent) => {
2595                     Some(parent)
2596                 }
2597                 hir::OpaqueTyOrigin::TyAlias => None,
2598             };
2599         }
2600     }
2601     None
2602 }
2603
2604 pub fn int_ty(ity: ast::IntTy) -> IntTy {
2605     match ity {
2606         ast::IntTy::Isize => IntTy::Isize,
2607         ast::IntTy::I8 => IntTy::I8,
2608         ast::IntTy::I16 => IntTy::I16,
2609         ast::IntTy::I32 => IntTy::I32,
2610         ast::IntTy::I64 => IntTy::I64,
2611         ast::IntTy::I128 => IntTy::I128,
2612     }
2613 }
2614
2615 pub fn uint_ty(uty: ast::UintTy) -> UintTy {
2616     match uty {
2617         ast::UintTy::Usize => UintTy::Usize,
2618         ast::UintTy::U8 => UintTy::U8,
2619         ast::UintTy::U16 => UintTy::U16,
2620         ast::UintTy::U32 => UintTy::U32,
2621         ast::UintTy::U64 => UintTy::U64,
2622         ast::UintTy::U128 => UintTy::U128,
2623     }
2624 }
2625
2626 pub fn float_ty(fty: ast::FloatTy) -> FloatTy {
2627     match fty {
2628         ast::FloatTy::F32 => FloatTy::F32,
2629         ast::FloatTy::F64 => FloatTy::F64,
2630     }
2631 }
2632
2633 pub fn ast_int_ty(ity: IntTy) -> ast::IntTy {
2634     match ity {
2635         IntTy::Isize => ast::IntTy::Isize,
2636         IntTy::I8 => ast::IntTy::I8,
2637         IntTy::I16 => ast::IntTy::I16,
2638         IntTy::I32 => ast::IntTy::I32,
2639         IntTy::I64 => ast::IntTy::I64,
2640         IntTy::I128 => ast::IntTy::I128,
2641     }
2642 }
2643
2644 pub fn ast_uint_ty(uty: UintTy) -> ast::UintTy {
2645     match uty {
2646         UintTy::Usize => ast::UintTy::Usize,
2647         UintTy::U8 => ast::UintTy::U8,
2648         UintTy::U16 => ast::UintTy::U16,
2649         UintTy::U32 => ast::UintTy::U32,
2650         UintTy::U64 => ast::UintTy::U64,
2651         UintTy::U128 => ast::UintTy::U128,
2652     }
2653 }
2654
2655 pub fn provide(providers: &mut ty::query::Providers) {
2656     closure::provide(providers);
2657     context::provide(providers);
2658     erase_regions::provide(providers);
2659     inhabitedness::provide(providers);
2660     util::provide(providers);
2661     print::provide(providers);
2662     super::util::bug::provide(providers);
2663     super::middle::provide(providers);
2664     *providers = ty::query::Providers {
2665         trait_impls_of: trait_def::trait_impls_of_provider,
2666         incoherent_impls: trait_def::incoherent_impls_provider,
2667         const_param_default: consts::const_param_default,
2668         vtable_allocation: vtable::vtable_allocation_provider,
2669         ..*providers
2670     };
2671 }
2672
2673 /// A map for the local crate mapping each type to a vector of its
2674 /// inherent impls. This is not meant to be used outside of coherence;
2675 /// rather, you should request the vector for a specific type via
2676 /// `tcx.inherent_impls(def_id)` so as to minimize your dependencies
2677 /// (constructing this map requires touching the entire crate).
2678 #[derive(Clone, Debug, Default, HashStable)]
2679 pub struct CrateInherentImpls {
2680     pub inherent_impls: LocalDefIdMap<Vec<DefId>>,
2681     pub incoherent_impls: FxHashMap<SimplifiedType, Vec<LocalDefId>>,
2682 }
2683
2684 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, HashStable)]
2685 pub struct SymbolName<'tcx> {
2686     /// `&str` gives a consistent ordering, which ensures reproducible builds.
2687     pub name: &'tcx str,
2688 }
2689
2690 impl<'tcx> SymbolName<'tcx> {
2691     pub fn new(tcx: TyCtxt<'tcx>, name: &str) -> SymbolName<'tcx> {
2692         SymbolName {
2693             name: unsafe { str::from_utf8_unchecked(tcx.arena.alloc_slice(name.as_bytes())) },
2694         }
2695     }
2696 }
2697
2698 impl<'tcx> fmt::Display for SymbolName<'tcx> {
2699     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
2700         fmt::Display::fmt(&self.name, fmt)
2701     }
2702 }
2703
2704 impl<'tcx> fmt::Debug for SymbolName<'tcx> {
2705     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
2706         fmt::Display::fmt(&self.name, fmt)
2707     }
2708 }
2709
2710 #[derive(Debug, Default, Copy, Clone)]
2711 pub struct FoundRelationships {
2712     /// This is true if we identified that this Ty (`?T`) is found in a `?T: Foo`
2713     /// obligation, where:
2714     ///
2715     ///  * `Foo` is not `Sized`
2716     ///  * `(): Foo` may be satisfied
2717     pub self_in_trait: bool,
2718     /// This is true if we identified that this Ty (`?T`) is found in a `<_ as
2719     /// _>::AssocType = ?T`
2720     pub output: bool,
2721 }
2722
2723 /// The constituent parts of a type level constant of kind ADT or array.
2724 #[derive(Copy, Clone, Debug, HashStable)]
2725 pub struct DestructuredConst<'tcx> {
2726     pub variant: Option<VariantIdx>,
2727     pub fields: &'tcx [ty::Const<'tcx>],
2728 }
2729
2730 // Some types are used a lot. Make sure they don't unintentionally get bigger.
2731 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
2732 mod size_asserts {
2733     use super::*;
2734     use rustc_data_structures::static_assert_size;
2735     // tidy-alphabetical-start
2736     static_assert_size!(PredicateS<'_>, 48);
2737     static_assert_size!(TyS<'_>, 40);
2738     static_assert_size!(WithStableHash<TyS<'_>>, 56);
2739     // tidy-alphabetical-end
2740 }