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