compiler/rustc_middle/src/ty/sty.rs

   1 //! This module contains `TyKind` and its major components.
   2
   3 #![allow(rustc::usage_of_ty_tykind)]
   4
   5 use crate::infer::canonical::Canonical;
   6 use crate::ty::subst::{GenericArg, InternalSubsts, SubstsRef};
   7 use crate::ty::visit::ValidateBoundVars;
   8 use crate::ty::InferTy::*;
   9 use crate::ty::{
  10     self, AdtDef, DefIdTree, Discr, FallibleTypeFolder, Term, Ty, TyCtxt, TypeFlags, TypeFoldable,
  11     TypeSuperFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitor,
  12 };
  13 use crate::ty::{List, ParamEnv};
  14 use hir::def::DefKind;
  15 use polonius_engine::Atom;
  16 use rustc_data_structures::captures::Captures;
  17 use rustc_data_structures::intern::Interned;
  18 use rustc_hir as hir;
  19 use rustc_hir::def_id::DefId;
  20 use rustc_hir::LangItem;
  21 use rustc_index::vec::Idx;
  22 use rustc_macros::HashStable;
  23 use rustc_span::symbol::{kw, sym, Symbol};
  24 use rustc_span::Span;
  25 use rustc_target::abi::VariantIdx;
  26 use rustc_target::spec::abi;
  27 use std::borrow::Cow;
  28 use std::cmp::Ordering;
  29 use std::fmt;
  30 use std::marker::PhantomData;
  31 use std::ops::{ControlFlow, Deref, Range};
  32 use ty::util::IntTypeExt;
  33
  34 use rustc_type_ir::sty::TyKind::*;
  35 use rustc_type_ir::RegionKind as IrRegionKind;
  36 use rustc_type_ir::TyKind as IrTyKind;
  37
  38 // Re-export the `TyKind` from `rustc_type_ir` here for convenience
  39 #[rustc_diagnostic_item = "TyKind"]
  40 pub type TyKind<'tcx> = IrTyKind<TyCtxt<'tcx>>;
  41 pub type RegionKind<'tcx> = IrRegionKind<TyCtxt<'tcx>>;
  42
  43 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
  44 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
  45 pub struct TypeAndMut<'tcx> {
  46     pub ty: Ty<'tcx>,
  47     pub mutbl: hir::Mutability,
  48 }
  49
  50 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, TyEncodable, TyDecodable, Copy)]
  51 #[derive(HashStable)]
  52 /// A "free" region `fr` can be interpreted as "some region
  53 /// at least as big as the scope `fr.scope`".
  54 pub struct FreeRegion {
  55     pub scope: DefId,
  56     pub bound_region: BoundRegionKind,
  57 }
  58
  59 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, TyEncodable, TyDecodable, Copy)]
  60 #[derive(HashStable)]
  61 pub enum BoundRegionKind {
  62     /// An anonymous region parameter for a given fn (&T)
  63     BrAnon(u32, Option<Span>),
  64
  65     /// Named region parameters for functions (a in &'a T)
  66     ///
  67     /// The `DefId` is needed to distinguish free regions in
  68     /// the event of shadowing.
  69     BrNamed(DefId, Symbol),
  70
  71     /// Anonymous region for the implicit env pointer parameter
  72     /// to a closure
  73     BrEnv,
  74 }
  75
  76 #[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable, Debug, PartialOrd, Ord)]
  77 #[derive(HashStable)]
  78 pub struct BoundRegion {
  79     pub var: BoundVar,
  80     pub kind: BoundRegionKind,
  81 }
  82
  83 impl BoundRegionKind {
  84     pub fn is_named(&self) -> bool {
  85         match *self {
  86             BoundRegionKind::BrNamed(_, name) => {
  87                 name != kw::UnderscoreLifetime && name != kw::Empty
  88             }
  89             _ => false,
  90         }
  91     }
  92
  93     pub fn get_name(&self) -> Option<Symbol> {
  94         if self.is_named() {
  95             match *self {
  96                 BoundRegionKind::BrNamed(_, name) => return Some(name),
  97                 _ => unreachable!(),
  98             }
  99         }
 100
 101         None
 102     }
 103
 104     pub fn get_id(&self) -> Option<DefId> {
 105         match *self {
 106             BoundRegionKind::BrNamed(id, _) => return Some(id),
 107             _ => None,
 108         }
 109     }
 110 }
 111
 112 pub trait Article {
 113     fn article(&self) -> &'static str;
 114 }
 115
 116 impl<'tcx> Article for TyKind<'tcx> {
 117     /// Get the article ("a" or "an") to use with this type.
 118     fn article(&self) -> &'static str {
 119         match self {
 120             Int(_) | Float(_) | Array(_, _) => "an",
 121             Adt(def, _) if def.is_enum() => "an",
 122             // This should never happen, but ICEing and causing the user's code
 123             // to not compile felt too harsh.
 124             Error(_) => "a",
 125             _ => "a",
 126         }
 127     }
 128 }
 129
 130 // `TyKind` is used a lot. Make sure it doesn't unintentionally get bigger.
 131 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 132 static_assert_size!(TyKind<'_>, 32);
 133
 134 /// A closure can be modeled as a struct that looks like:
 135 /// ```ignore (illustrative)
 136 /// struct Closure<'l0...'li, T0...Tj, CK, CS, U>(...U);
 137 /// ```
 138 /// where:
 139 ///
 140 /// - 'l0...'li and T0...Tj are the generic parameters
 141 ///   in scope on the function that defined the closure,
 142 /// - CK represents the *closure kind* (Fn vs FnMut vs FnOnce). This
 143 ///   is rather hackily encoded via a scalar type. See
 144 ///   `Ty::to_opt_closure_kind` for details.
 145 /// - CS represents the *closure signature*, representing as a `fn()`
 146 ///   type. For example, `fn(u32, u32) -> u32` would mean that the closure
 147 ///   implements `CK<(u32, u32), Output = u32>`, where `CK` is the trait
 148 ///   specified above.
 149 /// - U is a type parameter representing the types of its upvars, tupled up
 150 ///   (borrowed, if appropriate; that is, if a U field represents a by-ref upvar,
 151 ///    and the up-var has the type `Foo`, then that field of U will be `&Foo`).
 152 ///
 153 /// So, for example, given this function:
 154 /// ```ignore (illustrative)
 155 /// fn foo<'a, T>(data: &'a mut T) {
 156 ///      do(|| data.count += 1)
 157 /// }
 158 /// ```
 159 /// the type of the closure would be something like:
 160 /// ```ignore (illustrative)
 161 /// struct Closure<'a, T, U>(...U);
 162 /// ```
 163 /// Note that the type of the upvar is not specified in the struct.
 164 /// You may wonder how the impl would then be able to use the upvar,
 165 /// if it doesn't know it's type? The answer is that the impl is
 166 /// (conceptually) not fully generic over Closure but rather tied to
 167 /// instances with the expected upvar types:
 168 /// ```ignore (illustrative)
 169 /// impl<'b, 'a, T> FnMut() for Closure<'a, T, (&'b mut &'a mut T,)> {
 170 ///     ...
 171 /// }
 172 /// ```
 173 /// You can see that the *impl* fully specified the type of the upvar
 174 /// and thus knows full well that `data` has type `&'b mut &'a mut T`.
 175 /// (Here, I am assuming that `data` is mut-borrowed.)
 176 ///
 177 /// Now, the last question you may ask is: Why include the upvar types
 178 /// in an extra type parameter? The reason for this design is that the
 179 /// upvar types can reference lifetimes that are internal to the
 180 /// creating function. In my example above, for example, the lifetime
 181 /// `'b` represents the scope of the closure itself; this is some
 182 /// subset of `foo`, probably just the scope of the call to the to
 183 /// `do()`. If we just had the lifetime/type parameters from the
 184 /// enclosing function, we couldn't name this lifetime `'b`. Note that
 185 /// there can also be lifetimes in the types of the upvars themselves,
 186 /// if one of them happens to be a reference to something that the
 187 /// creating fn owns.
 188 ///
 189 /// OK, you say, so why not create a more minimal set of parameters
 190 /// that just includes the extra lifetime parameters? The answer is
 191 /// primarily that it would be hard --- we don't know at the time when
 192 /// we create the closure type what the full types of the upvars are,
 193 /// nor do we know which are borrowed and which are not. In this
 194 /// design, we can just supply a fresh type parameter and figure that
 195 /// out later.
 196 ///
 197 /// All right, you say, but why include the type parameters from the
 198 /// original function then? The answer is that codegen may need them
 199 /// when monomorphizing, and they may not appear in the upvars. A
 200 /// closure could capture no variables but still make use of some
 201 /// in-scope type parameter with a bound (e.g., if our example above
 202 /// had an extra `U: Default`, and the closure called `U::default()`).
 203 ///
 204 /// There is another reason. This design (implicitly) prohibits
 205 /// closures from capturing themselves (except via a trait
 206 /// object). This simplifies closure inference considerably, since it
 207 /// means that when we infer the kind of a closure or its upvars, we
 208 /// don't have to handle cycles where the decisions we make for
 209 /// closure C wind up influencing the decisions we ought to make for
 210 /// closure C (which would then require fixed point iteration to
 211 /// handle). Plus it fixes an ICE. :P
 212 ///
 213 /// ## Generators
 214 ///
 215 /// Generators are handled similarly in `GeneratorSubsts`. The set of
 216 /// type parameters is similar, but `CK` and `CS` are replaced by the
 217 /// following type parameters:
 218 ///
 219 /// * `GS`: The generator's "resume type", which is the type of the
 220 ///   argument passed to `resume`, and the type of `yield` expressions
 221 ///   inside the generator.
 222 /// * `GY`: The "yield type", which is the type of values passed to
 223 ///   `yield` inside the generator.
 224 /// * `GR`: The "return type", which is the type of value returned upon
 225 ///   completion of the generator.
 226 /// * `GW`: The "generator witness".
 227 #[derive(Copy, Clone, PartialEq, Eq, Debug, TypeFoldable, TypeVisitable, Lift)]
 228 pub struct ClosureSubsts<'tcx> {
 229     /// Lifetime and type parameters from the enclosing function,
 230     /// concatenated with a tuple containing the types of the upvars.
 231     ///
 232     /// These are separated out because codegen wants to pass them around
 233     /// when monomorphizing.
 234     pub substs: SubstsRef<'tcx>,
 235 }
 236
 237 /// Struct returned by `split()`.
 238 pub struct ClosureSubstsParts<'tcx, T> {
 239     pub parent_substs: &'tcx [GenericArg<'tcx>],
 240     pub closure_kind_ty: T,
 241     pub closure_sig_as_fn_ptr_ty: T,
 242     pub tupled_upvars_ty: T,
 243 }
 244
 245 impl<'tcx> ClosureSubsts<'tcx> {
 246     /// Construct `ClosureSubsts` from `ClosureSubstsParts`, containing `Substs`
 247     /// for the closure parent, alongside additional closure-specific components.
 248     pub fn new(
 249         tcx: TyCtxt<'tcx>,
 250         parts: ClosureSubstsParts<'tcx, Ty<'tcx>>,
 251     ) -> ClosureSubsts<'tcx> {
 252         ClosureSubsts {
 253             substs: tcx.mk_substs(
 254                 parts.parent_substs.iter().copied().chain(
 255                     [parts.closure_kind_ty, parts.closure_sig_as_fn_ptr_ty, parts.tupled_upvars_ty]
 256                         .iter()
 257                         .map(|&ty| ty.into()),
 258                 ),
 259             ),
 260         }
 261     }
 262
 263     /// Divides the closure substs into their respective components.
 264     /// The ordering assumed here must match that used by `ClosureSubsts::new` above.
 265     fn split(self) -> ClosureSubstsParts<'tcx, GenericArg<'tcx>> {
 266         match self.substs[..] {
 267             [
 268                 ref parent_substs @ ..,
 269                 closure_kind_ty,
 270                 closure_sig_as_fn_ptr_ty,
 271                 tupled_upvars_ty,
 272             ] => ClosureSubstsParts {
 273                 parent_substs,
 274                 closure_kind_ty,
 275                 closure_sig_as_fn_ptr_ty,
 276                 tupled_upvars_ty,
 277             },
 278             _ => bug!("closure substs missing synthetics"),
 279         }
 280     }
 281
 282     /// Returns `true` only if enough of the synthetic types are known to
 283     /// allow using all of the methods on `ClosureSubsts` without panicking.
 284     ///
 285     /// Used primarily by `ty::print::pretty` to be able to handle closure
 286     /// types that haven't had their synthetic types substituted in.
 287     pub fn is_valid(self) -> bool {
 288         self.substs.len() >= 3
 289             && matches!(self.split().tupled_upvars_ty.expect_ty().kind(), Tuple(_))
 290     }
 291
 292     /// Returns the substitutions of the closure's parent.
 293     pub fn parent_substs(self) -> &'tcx [GenericArg<'tcx>] {
 294         self.split().parent_substs
 295     }
 296
 297     /// Returns an iterator over the list of types of captured paths by the closure.
 298     /// In case there was a type error in figuring out the types of the captured path, an
 299     /// empty iterator is returned.
 300     #[inline]
 301     pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
 302         match self.tupled_upvars_ty().kind() {
 303             TyKind::Error(_) => None,
 304             TyKind::Tuple(..) => Some(self.tupled_upvars_ty().tuple_fields()),
 305             TyKind::Infer(_) => bug!("upvar_tys called before capture types are inferred"),
 306             ty => bug!("Unexpected representation of upvar types tuple {:?}", ty),
 307         }
 308         .into_iter()
 309         .flatten()
 310     }
 311
 312     /// Returns the tuple type representing the upvars for this closure.
 313     #[inline]
 314     pub fn tupled_upvars_ty(self) -> Ty<'tcx> {
 315         self.split().tupled_upvars_ty.expect_ty()
 316     }
 317
 318     /// Returns the closure kind for this closure; may return a type
 319     /// variable during inference. To get the closure kind during
 320     /// inference, use `infcx.closure_kind(substs)`.
 321     pub fn kind_ty(self) -> Ty<'tcx> {
 322         self.split().closure_kind_ty.expect_ty()
 323     }
 324
 325     /// Returns the `fn` pointer type representing the closure signature for this
 326     /// closure.
 327     // FIXME(eddyb) this should be unnecessary, as the shallowly resolved
 328     // type is known at the time of the creation of `ClosureSubsts`,
 329     // see `rustc_hir_analysis::check::closure`.
 330     pub fn sig_as_fn_ptr_ty(self) -> Ty<'tcx> {
 331         self.split().closure_sig_as_fn_ptr_ty.expect_ty()
 332     }
 333
 334     /// Returns the closure kind for this closure; only usable outside
 335     /// of an inference context, because in that context we know that
 336     /// there are no type variables.
 337     ///
 338     /// If you have an inference context, use `infcx.closure_kind()`.
 339     pub fn kind(self) -> ty::ClosureKind {
 340         self.kind_ty().to_opt_closure_kind().unwrap()
 341     }
 342
 343     /// Extracts the signature from the closure.
 344     pub fn sig(self) -> ty::PolyFnSig<'tcx> {
 345         let ty = self.sig_as_fn_ptr_ty();
 346         match ty.kind() {
 347             ty::FnPtr(sig) => *sig,
 348             _ => bug!("closure_sig_as_fn_ptr_ty is not a fn-ptr: {:?}", ty.kind()),
 349         }
 350     }
 351
 352     pub fn print_as_impl_trait(self) -> ty::print::PrintClosureAsImpl<'tcx> {
 353         ty::print::PrintClosureAsImpl { closure: self }
 354     }
 355 }
 356
 357 /// Similar to `ClosureSubsts`; see the above documentation for more.
 358 #[derive(Copy, Clone, PartialEq, Eq, Debug, TypeFoldable, TypeVisitable, Lift)]
 359 pub struct GeneratorSubsts<'tcx> {
 360     pub substs: SubstsRef<'tcx>,
 361 }
 362
 363 pub struct GeneratorSubstsParts<'tcx, T> {
 364     pub parent_substs: &'tcx [GenericArg<'tcx>],
 365     pub resume_ty: T,
 366     pub yield_ty: T,
 367     pub return_ty: T,
 368     pub witness: T,
 369     pub tupled_upvars_ty: T,
 370 }
 371
 372 impl<'tcx> GeneratorSubsts<'tcx> {
 373     /// Construct `GeneratorSubsts` from `GeneratorSubstsParts`, containing `Substs`
 374     /// for the generator parent, alongside additional generator-specific components.
 375     pub fn new(
 376         tcx: TyCtxt<'tcx>,
 377         parts: GeneratorSubstsParts<'tcx, Ty<'tcx>>,
 378     ) -> GeneratorSubsts<'tcx> {
 379         GeneratorSubsts {
 380             substs: tcx.mk_substs(
 381                 parts.parent_substs.iter().copied().chain(
 382                     [
 383                         parts.resume_ty,
 384                         parts.yield_ty,
 385                         parts.return_ty,
 386                         parts.witness,
 387                         parts.tupled_upvars_ty,
 388                     ]
 389                     .iter()
 390                     .map(|&ty| ty.into()),
 391                 ),
 392             ),
 393         }
 394     }
 395
 396     /// Divides the generator substs into their respective components.
 397     /// The ordering assumed here must match that used by `GeneratorSubsts::new` above.
 398     fn split(self) -> GeneratorSubstsParts<'tcx, GenericArg<'tcx>> {
 399         match self.substs[..] {
 400             [ref parent_substs @ .., resume_ty, yield_ty, return_ty, witness, tupled_upvars_ty] => {
 401                 GeneratorSubstsParts {
 402                     parent_substs,
 403                     resume_ty,
 404                     yield_ty,
 405                     return_ty,
 406                     witness,
 407                     tupled_upvars_ty,
 408                 }
 409             }
 410             _ => bug!("generator substs missing synthetics"),
 411         }
 412     }
 413
 414     /// Returns `true` only if enough of the synthetic types are known to
 415     /// allow using all of the methods on `GeneratorSubsts` without panicking.
 416     ///
 417     /// Used primarily by `ty::print::pretty` to be able to handle generator
 418     /// types that haven't had their synthetic types substituted in.
 419     pub fn is_valid(self) -> bool {
 420         self.substs.len() >= 5
 421             && matches!(self.split().tupled_upvars_ty.expect_ty().kind(), Tuple(_))
 422     }
 423
 424     /// Returns the substitutions of the generator's parent.
 425     pub fn parent_substs(self) -> &'tcx [GenericArg<'tcx>] {
 426         self.split().parent_substs
 427     }
 428
 429     /// This describes the types that can be contained in a generator.
 430     /// It will be a type variable initially and unified in the last stages of typeck of a body.
 431     /// It contains a tuple of all the types that could end up on a generator frame.
 432     /// The state transformation MIR pass may only produce layouts which mention types
 433     /// in this tuple. Upvars are not counted here.
 434     pub fn witness(self) -> Ty<'tcx> {
 435         self.split().witness.expect_ty()
 436     }
 437
 438     /// Returns an iterator over the list of types of captured paths by the generator.
 439     /// In case there was a type error in figuring out the types of the captured path, an
 440     /// empty iterator is returned.
 441     #[inline]
 442     pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
 443         match self.tupled_upvars_ty().kind() {
 444             TyKind::Error(_) => None,
 445             TyKind::Tuple(..) => Some(self.tupled_upvars_ty().tuple_fields()),
 446             TyKind::Infer(_) => bug!("upvar_tys called before capture types are inferred"),
 447             ty => bug!("Unexpected representation of upvar types tuple {:?}", ty),
 448         }
 449         .into_iter()
 450         .flatten()
 451     }
 452
 453     /// Returns the tuple type representing the upvars for this generator.
 454     #[inline]
 455     pub fn tupled_upvars_ty(self) -> Ty<'tcx> {
 456         self.split().tupled_upvars_ty.expect_ty()
 457     }
 458
 459     /// Returns the type representing the resume type of the generator.
 460     pub fn resume_ty(self) -> Ty<'tcx> {
 461         self.split().resume_ty.expect_ty()
 462     }
 463
 464     /// Returns the type representing the yield type of the generator.
 465     pub fn yield_ty(self) -> Ty<'tcx> {
 466         self.split().yield_ty.expect_ty()
 467     }
 468
 469     /// Returns the type representing the return type of the generator.
 470     pub fn return_ty(self) -> Ty<'tcx> {
 471         self.split().return_ty.expect_ty()
 472     }
 473
 474     /// Returns the "generator signature", which consists of its yield
 475     /// and return types.
 476     ///
 477     /// N.B., some bits of the code prefers to see this wrapped in a
 478     /// binder, but it never contains bound regions. Probably this
 479     /// function should be removed.
 480     pub fn poly_sig(self) -> PolyGenSig<'tcx> {
 481         ty::Binder::dummy(self.sig())
 482     }
 483
 484     /// Returns the "generator signature", which consists of its resume, yield
 485     /// and return types.
 486     pub fn sig(self) -> GenSig<'tcx> {
 487         ty::GenSig {
 488             resume_ty: self.resume_ty(),
 489             yield_ty: self.yield_ty(),
 490             return_ty: self.return_ty(),
 491         }
 492     }
 493 }
 494
 495 impl<'tcx> GeneratorSubsts<'tcx> {
 496     /// Generator has not been resumed yet.
 497     pub const UNRESUMED: usize = 0;
 498     /// Generator has returned or is completed.
 499     pub const RETURNED: usize = 1;
 500     /// Generator has been poisoned.
 501     pub const POISONED: usize = 2;
 502
 503     const UNRESUMED_NAME: &'static str = "Unresumed";
 504     const RETURNED_NAME: &'static str = "Returned";
 505     const POISONED_NAME: &'static str = "Panicked";
 506
 507     /// The valid variant indices of this generator.
 508     #[inline]
 509     pub fn variant_range(&self, def_id: DefId, tcx: TyCtxt<'tcx>) -> Range<VariantIdx> {
 510         // FIXME requires optimized MIR
 511         let num_variants = tcx.generator_layout(def_id).unwrap().variant_fields.len();
 512         VariantIdx::new(0)..VariantIdx::new(num_variants)
 513     }
 514
 515     /// The discriminant for the given variant. Panics if the `variant_index` is
 516     /// out of range.
 517     #[inline]
 518     pub fn discriminant_for_variant(
 519         &self,
 520         def_id: DefId,
 521         tcx: TyCtxt<'tcx>,
 522         variant_index: VariantIdx,
 523     ) -> Discr<'tcx> {
 524         // Generators don't support explicit discriminant values, so they are
 525         // the same as the variant index.
 526         assert!(self.variant_range(def_id, tcx).contains(&variant_index));
 527         Discr { val: variant_index.as_usize() as u128, ty: self.discr_ty(tcx) }
 528     }
 529
 530     /// The set of all discriminants for the generator, enumerated with their
 531     /// variant indices.
 532     #[inline]
 533     pub fn discriminants(
 534         self,
 535         def_id: DefId,
 536         tcx: TyCtxt<'tcx>,
 537     ) -> impl Iterator<Item = (VariantIdx, Discr<'tcx>)> + Captures<'tcx> {
 538         self.variant_range(def_id, tcx).map(move |index| {
 539             (index, Discr { val: index.as_usize() as u128, ty: self.discr_ty(tcx) })
 540         })
 541     }
 542
 543     /// Calls `f` with a reference to the name of the enumerator for the given
 544     /// variant `v`.
 545     pub fn variant_name(v: VariantIdx) -> Cow<'static, str> {
 546         match v.as_usize() {
 547             Self::UNRESUMED => Cow::from(Self::UNRESUMED_NAME),
 548             Self::RETURNED => Cow::from(Self::RETURNED_NAME),
 549             Self::POISONED => Cow::from(Self::POISONED_NAME),
 550             _ => Cow::from(format!("Suspend{}", v.as_usize() - 3)),
 551         }
 552     }
 553
 554     /// The type of the state discriminant used in the generator type.
 555     #[inline]
 556     pub fn discr_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
 557         tcx.types.u32
 558     }
 559
 560     /// This returns the types of the MIR locals which had to be stored across suspension points.
 561     /// It is calculated in rustc_mir_transform::generator::StateTransform.
 562     /// All the types here must be in the tuple in GeneratorInterior.
 563     ///
 564     /// The locals are grouped by their variant number. Note that some locals may
 565     /// be repeated in multiple variants.
 566     #[inline]
 567     pub fn state_tys(
 568         self,
 569         def_id: DefId,
 570         tcx: TyCtxt<'tcx>,
 571     ) -> impl Iterator<Item = impl Iterator<Item = Ty<'tcx>> + Captures<'tcx>> {
 572         let layout = tcx.generator_layout(def_id).unwrap();
 573         layout.variant_fields.iter().map(move |variant| {
 574             variant
 575                 .iter()
 576                 .map(move |field| ty::EarlyBinder(layout.field_tys[*field]).subst(tcx, self.substs))
 577         })
 578     }
 579
 580     /// This is the types of the fields of a generator which are not stored in a
 581     /// variant.
 582     #[inline]
 583     pub fn prefix_tys(self) -> impl Iterator<Item = Ty<'tcx>> {
 584         self.upvar_tys()
 585     }
 586 }
 587
 588 #[derive(Debug, Copy, Clone, HashStable)]
 589 pub enum UpvarSubsts<'tcx> {
 590     Closure(SubstsRef<'tcx>),
 591     Generator(SubstsRef<'tcx>),
 592 }
 593
 594 impl<'tcx> UpvarSubsts<'tcx> {
 595     /// Returns an iterator over the list of types of captured paths by the closure/generator.
 596     /// In case there was a type error in figuring out the types of the captured path, an
 597     /// empty iterator is returned.
 598     #[inline]
 599     pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
 600         let tupled_tys = match self {
 601             UpvarSubsts::Closure(substs) => substs.as_closure().tupled_upvars_ty(),
 602             UpvarSubsts::Generator(substs) => substs.as_generator().tupled_upvars_ty(),
 603         };
 604
 605         match tupled_tys.kind() {
 606             TyKind::Error(_) => None,
 607             TyKind::Tuple(..) => Some(self.tupled_upvars_ty().tuple_fields()),
 608             TyKind::Infer(_) => bug!("upvar_tys called before capture types are inferred"),
 609             ty => bug!("Unexpected representation of upvar types tuple {:?}", ty),
 610         }
 611         .into_iter()
 612         .flatten()
 613     }
 614
 615     #[inline]
 616     pub fn tupled_upvars_ty(self) -> Ty<'tcx> {
 617         match self {
 618             UpvarSubsts::Closure(substs) => substs.as_closure().tupled_upvars_ty(),
 619             UpvarSubsts::Generator(substs) => substs.as_generator().tupled_upvars_ty(),
 620         }
 621     }
 622 }
 623
 624 /// An inline const is modeled like
 625 /// ```ignore (illustrative)
 626 /// const InlineConst<'l0...'li, T0...Tj, R>: R;
 627 /// ```
 628 /// where:
 629 ///
 630 /// - 'l0...'li and T0...Tj are the generic parameters
 631 ///   inherited from the item that defined the inline const,
 632 /// - R represents the type of the constant.
 633 ///
 634 /// When the inline const is instantiated, `R` is substituted as the actual inferred
 635 /// type of the constant. The reason that `R` is represented as an extra type parameter
 636 /// is the same reason that [`ClosureSubsts`] have `CS` and `U` as type parameters:
 637 /// inline const can reference lifetimes that are internal to the creating function.
 638 #[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable)]
 639 pub struct InlineConstSubsts<'tcx> {
 640     /// Generic parameters from the enclosing item,
 641     /// concatenated with the inferred type of the constant.
 642     pub substs: SubstsRef<'tcx>,
 643 }
 644
 645 /// Struct returned by `split()`.
 646 pub struct InlineConstSubstsParts<'tcx, T> {
 647     pub parent_substs: &'tcx [GenericArg<'tcx>],
 648     pub ty: T,
 649 }
 650
 651 impl<'tcx> InlineConstSubsts<'tcx> {
 652     /// Construct `InlineConstSubsts` from `InlineConstSubstsParts`.
 653     pub fn new(
 654         tcx: TyCtxt<'tcx>,
 655         parts: InlineConstSubstsParts<'tcx, Ty<'tcx>>,
 656     ) -> InlineConstSubsts<'tcx> {
 657         InlineConstSubsts {
 658             substs: tcx.mk_substs(
 659                 parts.parent_substs.iter().copied().chain(std::iter::once(parts.ty.into())),
 660             ),
 661         }
 662     }
 663
 664     /// Divides the inline const substs into their respective components.
 665     /// The ordering assumed here must match that used by `InlineConstSubsts::new` above.
 666     fn split(self) -> InlineConstSubstsParts<'tcx, GenericArg<'tcx>> {
 667         match self.substs[..] {
 668             [ref parent_substs @ .., ty] => InlineConstSubstsParts { parent_substs, ty },
 669             _ => bug!("inline const substs missing synthetics"),
 670         }
 671     }
 672
 673     /// Returns the substitutions of the inline const's parent.
 674     pub fn parent_substs(self) -> &'tcx [GenericArg<'tcx>] {
 675         self.split().parent_substs
 676     }
 677
 678     /// Returns the type of this inline const.
 679     pub fn ty(self) -> Ty<'tcx> {
 680         self.split().ty.expect_ty()
 681     }
 682 }
 683
 684 #[derive(Debug, Copy, Clone, PartialEq, PartialOrd, Ord, Eq, Hash, TyEncodable, TyDecodable)]
 685 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 686 pub enum ExistentialPredicate<'tcx> {
 687     /// E.g., `Iterator`.
 688     Trait(ExistentialTraitRef<'tcx>),
 689     /// E.g., `Iterator::Item = T`.
 690     Projection(ExistentialProjection<'tcx>),
 691     /// E.g., `Send`.
 692     AutoTrait(DefId),
 693 }
 694
 695 impl<'tcx> ExistentialPredicate<'tcx> {
 696     /// Compares via an ordering that will not change if modules are reordered or other changes are
 697     /// made to the tree. In particular, this ordering is preserved across incremental compilations.
 698     pub fn stable_cmp(&self, tcx: TyCtxt<'tcx>, other: &Self) -> Ordering {
 699         use self::ExistentialPredicate::*;
 700         match (*self, *other) {
 701             (Trait(_), Trait(_)) => Ordering::Equal,
 702             (Projection(ref a), Projection(ref b)) => {
 703                 tcx.def_path_hash(a.def_id).cmp(&tcx.def_path_hash(b.def_id))
 704             }
 705             (AutoTrait(ref a), AutoTrait(ref b)) => {
 706                 tcx.def_path_hash(*a).cmp(&tcx.def_path_hash(*b))
 707             }
 708             (Trait(_), _) => Ordering::Less,
 709             (Projection(_), Trait(_)) => Ordering::Greater,
 710             (Projection(_), _) => Ordering::Less,
 711             (AutoTrait(_), _) => Ordering::Greater,
 712         }
 713     }
 714 }
 715
 716 pub type PolyExistentialPredicate<'tcx> = Binder<'tcx, ExistentialPredicate<'tcx>>;
 717
 718 impl<'tcx> PolyExistentialPredicate<'tcx> {
 719     /// Given an existential predicate like `?Self: PartialEq<u32>` (e.g., derived from `dyn PartialEq<u32>`),
 720     /// and a concrete type `self_ty`, returns a full predicate where the existentially quantified variable `?Self`
 721     /// has been replaced with `self_ty` (e.g., `self_ty: PartialEq<u32>`, in our example).
 722     pub fn with_self_ty(&self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> ty::Predicate<'tcx> {
 723         use crate::ty::ToPredicate;
 724         match self.skip_binder() {
 725             ExistentialPredicate::Trait(tr) => {
 726                 self.rebind(tr).with_self_ty(tcx, self_ty).without_const().to_predicate(tcx)
 727             }
 728             ExistentialPredicate::Projection(p) => {
 729                 self.rebind(p.with_self_ty(tcx, self_ty)).to_predicate(tcx)
 730             }
 731             ExistentialPredicate::AutoTrait(did) => {
 732                 let generics = tcx.generics_of(did);
 733                 let trait_ref = if generics.params.len() == 1 {
 734                     tcx.mk_trait_ref(did, [self_ty])
 735                 } else {
 736                     // If this is an ill-formed auto trait, then synthesize
 737                     // new error substs for the missing generics.
 738                     let err_substs =
 739                         ty::InternalSubsts::extend_with_error(tcx, did, &[self_ty.into()]);
 740                     tcx.mk_trait_ref(did, err_substs)
 741                 };
 742                 self.rebind(trait_ref).without_const().to_predicate(tcx)
 743             }
 744         }
 745     }
 746 }
 747
 748 impl<'tcx> List<ty::PolyExistentialPredicate<'tcx>> {
 749     /// Returns the "principal `DefId`" of this set of existential predicates.
 750     ///
 751     /// A Rust trait object type consists (in addition to a lifetime bound)
 752     /// of a set of trait bounds, which are separated into any number
 753     /// of auto-trait bounds, and at most one non-auto-trait bound. The
 754     /// non-auto-trait bound is called the "principal" of the trait
 755     /// object.
 756     ///
 757     /// Only the principal can have methods or type parameters (because
 758     /// auto traits can have neither of them). This is important, because
 759     /// it means the auto traits can be treated as an unordered set (methods
 760     /// would force an order for the vtable, while relating traits with
 761     /// type parameters without knowing the order to relate them in is
 762     /// a rather non-trivial task).
 763     ///
 764     /// For example, in the trait object `dyn fmt::Debug + Sync`, the
 765     /// principal bound is `Some(fmt::Debug)`, while the auto-trait bounds
 766     /// are the set `{Sync}`.
 767     ///
 768     /// It is also possible to have a "trivial" trait object that
 769     /// consists only of auto traits, with no principal - for example,
 770     /// `dyn Send + Sync`. In that case, the set of auto-trait bounds
 771     /// is `{Send, Sync}`, while there is no principal. These trait objects
 772     /// have a "trivial" vtable consisting of just the size, alignment,
 773     /// and destructor.
 774     pub fn principal(&self) -> Option<ty::Binder<'tcx, ExistentialTraitRef<'tcx>>> {
 775         self[0]
 776             .map_bound(|this| match this {
 777                 ExistentialPredicate::Trait(tr) => Some(tr),
 778                 _ => None,
 779             })
 780             .transpose()
 781     }
 782
 783     pub fn principal_def_id(&self) -> Option<DefId> {
 784         self.principal().map(|trait_ref| trait_ref.skip_binder().def_id)
 785     }
 786
 787     #[inline]
 788     pub fn projection_bounds<'a>(
 789         &'a self,
 790     ) -> impl Iterator<Item = ty::Binder<'tcx, ExistentialProjection<'tcx>>> + 'a {
 791         self.iter().filter_map(|predicate| {
 792             predicate
 793                 .map_bound(|pred| match pred {
 794                     ExistentialPredicate::Projection(projection) => Some(projection),
 795                     _ => None,
 796                 })
 797                 .transpose()
 798         })
 799     }
 800
 801     #[inline]
 802     pub fn auto_traits<'a>(&'a self) -> impl Iterator<Item = DefId> + Captures<'tcx> + 'a {
 803         self.iter().filter_map(|predicate| match predicate.skip_binder() {
 804             ExistentialPredicate::AutoTrait(did) => Some(did),
 805             _ => None,
 806         })
 807     }
 808 }
 809
 810 /// A complete reference to a trait. These take numerous guises in syntax,
 811 /// but perhaps the most recognizable form is in a where-clause:
 812 /// ```ignore (illustrative)
 813 /// T: Foo<U>
 814 /// ```
 815 /// This would be represented by a trait-reference where the `DefId` is the
 816 /// `DefId` for the trait `Foo` and the substs define `T` as parameter 0,
 817 /// and `U` as parameter 1.
 818 ///
 819 /// Trait references also appear in object types like `Foo<U>`, but in
 820 /// that case the `Self` parameter is absent from the substitutions.
 821 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
 822 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 823 pub struct TraitRef<'tcx> {
 824     pub def_id: DefId,
 825     pub substs: SubstsRef<'tcx>,
 826     /// This field exists to prevent the creation of `TraitRef` without
 827     /// calling [TyCtxt::mk_trait_ref].
 828     pub(super) _use_mk_trait_ref_instead: (),
 829 }
 830
 831 impl<'tcx> TraitRef<'tcx> {
 832     pub fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
 833         tcx.mk_trait_ref(
 834             self.def_id,
 835             [self_ty.into()].into_iter().chain(self.substs.iter().skip(1)),
 836         )
 837     }
 838
 839     /// Returns a `TraitRef` of the form `P0: Foo<P1..Pn>` where `Pi`
 840     /// are the parameters defined on trait.
 841     pub fn identity(tcx: TyCtxt<'tcx>, def_id: DefId) -> Binder<'tcx, TraitRef<'tcx>> {
 842         ty::Binder::dummy(tcx.mk_trait_ref(def_id, InternalSubsts::identity_for_item(tcx, def_id)))
 843     }
 844
 845     #[inline]
 846     pub fn self_ty(&self) -> Ty<'tcx> {
 847         self.substs.type_at(0)
 848     }
 849
 850     pub fn from_method(
 851         tcx: TyCtxt<'tcx>,
 852         trait_id: DefId,
 853         substs: SubstsRef<'tcx>,
 854     ) -> ty::TraitRef<'tcx> {
 855         let defs = tcx.generics_of(trait_id);
 856         tcx.mk_trait_ref(trait_id, tcx.intern_substs(&substs[..defs.params.len()]))
 857     }
 858 }
 859
 860 pub type PolyTraitRef<'tcx> = Binder<'tcx, TraitRef<'tcx>>;
 861
 862 impl<'tcx> PolyTraitRef<'tcx> {
 863     pub fn self_ty(&self) -> Binder<'tcx, Ty<'tcx>> {
 864         self.map_bound_ref(|tr| tr.self_ty())
 865     }
 866
 867     pub fn def_id(&self) -> DefId {
 868         self.skip_binder().def_id
 869     }
 870 }
 871
 872 impl rustc_errors::IntoDiagnosticArg for PolyTraitRef<'_> {
 873     fn into_diagnostic_arg(self) -> rustc_errors::DiagnosticArgValue<'static> {
 874         self.to_string().into_diagnostic_arg()
 875     }
 876 }
 877
 878 /// An existential reference to a trait, where `Self` is erased.
 879 /// For example, the trait object `Trait<'a, 'b, X, Y>` is:
 880 /// ```ignore (illustrative)
 881 /// exists T. T: Trait<'a, 'b, X, Y>
 882 /// ```
 883 /// The substitutions don't include the erased `Self`, only trait
 884 /// type and lifetime parameters (`[X, Y]` and `['a, 'b]` above).
 885 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
 886 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 887 pub struct ExistentialTraitRef<'tcx> {
 888     pub def_id: DefId,
 889     pub substs: SubstsRef<'tcx>,
 890 }
 891
 892 impl<'tcx> ExistentialTraitRef<'tcx> {
 893     pub fn erase_self_ty(
 894         tcx: TyCtxt<'tcx>,
 895         trait_ref: ty::TraitRef<'tcx>,
 896     ) -> ty::ExistentialTraitRef<'tcx> {
 897         // Assert there is a Self.
 898         trait_ref.substs.type_at(0);
 899
 900         ty::ExistentialTraitRef {
 901             def_id: trait_ref.def_id,
 902             substs: tcx.intern_substs(&trait_ref.substs[1..]),
 903         }
 904     }
 905
 906     /// Object types don't have a self type specified. Therefore, when
 907     /// we convert the principal trait-ref into a normal trait-ref,
 908     /// you must give *some* self type. A common choice is `mk_err()`
 909     /// or some placeholder type.
 910     pub fn with_self_ty(&self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> ty::TraitRef<'tcx> {
 911         // otherwise the escaping vars would be captured by the binder
 912         // debug_assert!(!self_ty.has_escaping_bound_vars());
 913
 914         tcx.mk_trait_ref(self.def_id, [self_ty.into()].into_iter().chain(self.substs.iter()))
 915     }
 916 }
 917
 918 pub type PolyExistentialTraitRef<'tcx> = Binder<'tcx, ExistentialTraitRef<'tcx>>;
 919
 920 impl<'tcx> PolyExistentialTraitRef<'tcx> {
 921     pub fn def_id(&self) -> DefId {
 922         self.skip_binder().def_id
 923     }
 924
 925     /// Object types don't have a self type specified. Therefore, when
 926     /// we convert the principal trait-ref into a normal trait-ref,
 927     /// you must give *some* self type. A common choice is `mk_err()`
 928     /// or some placeholder type.
 929     pub fn with_self_ty(&self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> ty::PolyTraitRef<'tcx> {
 930         self.map_bound(|trait_ref| trait_ref.with_self_ty(tcx, self_ty))
 931     }
 932 }
 933
 934 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
 935 #[derive(HashStable)]
 936 pub enum BoundVariableKind {
 937     Ty(BoundTyKind),
 938     Region(BoundRegionKind),
 939     Const,
 940 }
 941
 942 impl BoundVariableKind {
 943     pub fn expect_region(self) -> BoundRegionKind {
 944         match self {
 945             BoundVariableKind::Region(lt) => lt,
 946             _ => bug!("expected a region, but found another kind"),
 947         }
 948     }
 949
 950     pub fn expect_ty(self) -> BoundTyKind {
 951         match self {
 952             BoundVariableKind::Ty(ty) => ty,
 953             _ => bug!("expected a type, but found another kind"),
 954         }
 955     }
 956
 957     pub fn expect_const(self) {
 958         match self {
 959             BoundVariableKind::Const => (),
 960             _ => bug!("expected a const, but found another kind"),
 961         }
 962     }
 963 }
 964
 965 /// Binder is a binder for higher-ranked lifetimes or types. It is part of the
 966 /// compiler's representation for things like `for<'a> Fn(&'a isize)`
 967 /// (which would be represented by the type `PolyTraitRef ==
 968 /// Binder<'tcx, TraitRef>`). Note that when we instantiate,
 969 /// erase, or otherwise "discharge" these bound vars, we change the
 970 /// type from `Binder<'tcx, T>` to just `T` (see
 971 /// e.g., `liberate_late_bound_regions`).
 972 ///
 973 /// `Decodable` and `Encodable` are implemented for `Binder<T>` using the `impl_binder_encode_decode!` macro.
 974 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 975 #[derive(HashStable, Lift)]
 976 pub struct Binder<'tcx, T>(T, &'tcx List<BoundVariableKind>);
 977
 978 impl<'tcx, T> Binder<'tcx, T>
 979 where
 980     T: TypeVisitable<'tcx>,
 981 {
 982     /// Wraps `value` in a binder, asserting that `value` does not
 983     /// contain any bound vars that would be bound by the
 984     /// binder. This is commonly used to 'inject' a value T into a
 985     /// different binding level.
 986     #[track_caller]
 987     pub fn dummy(value: T) -> Binder<'tcx, T> {
 988         assert!(
 989             !value.has_escaping_bound_vars(),
 990             "`{value:?}` has escaping bound vars, so it cannot be wrapped in a dummy binder."
 991         );
 992         Binder(value, ty::List::empty())
 993     }
 994
 995     pub fn bind_with_vars(value: T, vars: &'tcx List<BoundVariableKind>) -> Binder<'tcx, T> {
 996         if cfg!(debug_assertions) {
 997             let mut validator = ValidateBoundVars::new(vars);
 998             value.visit_with(&mut validator);
 999         }
1000         Binder(value, vars)
1001     }
1002 }
1003
1004 impl<'tcx, T> Binder<'tcx, T> {
1005     /// Skips the binder and returns the "bound" value. This is a
1006     /// risky thing to do because it's easy to get confused about
1007     /// De Bruijn indices and the like. It is usually better to
1008     /// discharge the binder using `no_bound_vars` or
1009     /// `replace_late_bound_regions` or something like
1010     /// that. `skip_binder` is only valid when you are either
1011     /// extracting data that has nothing to do with bound vars, you
1012     /// are doing some sort of test that does not involve bound
1013     /// regions, or you are being very careful about your depth
1014     /// accounting.
1015     ///
1016     /// Some examples where `skip_binder` is reasonable:
1017     ///
1018     /// - extracting the `DefId` from a PolyTraitRef;
1019     /// - comparing the self type of a PolyTraitRef to see if it is equal to
1020     ///   a type parameter `X`, since the type `X` does not reference any regions
1021     pub fn skip_binder(self) -> T {
1022         self.0
1023     }
1024
1025     pub fn bound_vars(&self) -> &'tcx List<BoundVariableKind> {
1026         self.1
1027     }
1028
1029     pub fn as_ref(&self) -> Binder<'tcx, &T> {
1030         Binder(&self.0, self.1)
1031     }
1032
1033     pub fn as_deref(&self) -> Binder<'tcx, &T::Target>
1034     where
1035         T: Deref,
1036     {
1037         Binder(&self.0, self.1)
1038     }
1039
1040     pub fn map_bound_ref_unchecked<F, U>(&self, f: F) -> Binder<'tcx, U>
1041     where
1042         F: FnOnce(&T) -> U,
1043     {
1044         let value = f(&self.0);
1045         Binder(value, self.1)
1046     }
1047
1048     pub fn map_bound_ref<F, U: TypeVisitable<'tcx>>(&self, f: F) -> Binder<'tcx, U>
1049     where
1050         F: FnOnce(&T) -> U,
1051     {
1052         self.as_ref().map_bound(f)
1053     }
1054
1055     pub fn map_bound<F, U: TypeVisitable<'tcx>>(self, f: F) -> Binder<'tcx, U>
1056     where
1057         F: FnOnce(T) -> U,
1058     {
1059         let value = f(self.0);
1060         if cfg!(debug_assertions) {
1061             let mut validator = ValidateBoundVars::new(self.1);
1062             value.visit_with(&mut validator);
1063         }
1064         Binder(value, self.1)
1065     }
1066
1067     pub fn try_map_bound<F, U: TypeVisitable<'tcx>, E>(self, f: F) -> Result<Binder<'tcx, U>, E>
1068     where
1069         F: FnOnce(T) -> Result<U, E>,
1070     {
1071         let value = f(self.0)?;
1072         if cfg!(debug_assertions) {
1073             let mut validator = ValidateBoundVars::new(self.1);
1074             value.visit_with(&mut validator);
1075         }
1076         Ok(Binder(value, self.1))
1077     }
1078
1079     /// Wraps a `value` in a binder, using the same bound variables as the
1080     /// current `Binder`. This should not be used if the new value *changes*
1081     /// the bound variables. Note: the (old or new) value itself does not
1082     /// necessarily need to *name* all the bound variables.
1083     ///
1084     /// This currently doesn't do anything different than `bind`, because we
1085     /// don't actually track bound vars. However, semantically, it is different
1086     /// because bound vars aren't allowed to change here, whereas they are
1087     /// in `bind`. This may be (debug) asserted in the future.
1088     pub fn rebind<U>(&self, value: U) -> Binder<'tcx, U>
1089     where
1090         U: TypeVisitable<'tcx>,
1091     {
1092         if cfg!(debug_assertions) {
1093             let mut validator = ValidateBoundVars::new(self.bound_vars());
1094             value.visit_with(&mut validator);
1095         }
1096         Binder(value, self.1)
1097     }
1098
1099     /// Unwraps and returns the value within, but only if it contains
1100     /// no bound vars at all. (In other words, if this binder --
1101     /// and indeed any enclosing binder -- doesn't bind anything at
1102     /// all.) Otherwise, returns `None`.
1103     ///
1104     /// (One could imagine having a method that just unwraps a single
1105     /// binder, but permits late-bound vars bound by enclosing
1106     /// binders, but that would require adjusting the debruijn
1107     /// indices, and given the shallow binding structure we often use,
1108     /// would not be that useful.)
1109     pub fn no_bound_vars(self) -> Option<T>
1110     where
1111         T: TypeVisitable<'tcx>,
1112     {
1113         if self.0.has_escaping_bound_vars() { None } else { Some(self.skip_binder()) }
1114     }
1115
1116     pub fn no_bound_vars_ignoring_escaping(self, tcx: TyCtxt<'tcx>) -> Option<T>
1117     where
1118         T: TypeFoldable<'tcx>,
1119     {
1120         if !self.0.has_escaping_bound_vars() {
1121             Some(self.skip_binder())
1122         } else {
1123             self.0.try_fold_with(&mut SkipBindersAt { index: ty::INNERMOST, tcx }).ok()
1124         }
1125     }
1126
1127     /// Splits the contents into two things that share the same binder
1128     /// level as the original, returning two distinct binders.
1129     ///
1130     /// `f` should consider bound regions at depth 1 to be free, and
1131     /// anything it produces with bound regions at depth 1 will be
1132     /// bound in the resulting return values.
1133     pub fn split<U, V, F>(self, f: F) -> (Binder<'tcx, U>, Binder<'tcx, V>)
1134     where
1135         F: FnOnce(T) -> (U, V),
1136     {
1137         let (u, v) = f(self.0);
1138         (Binder(u, self.1), Binder(v, self.1))
1139     }
1140 }
1141
1142 impl<'tcx, T> Binder<'tcx, Option<T>> {
1143     pub fn transpose(self) -> Option<Binder<'tcx, T>> {
1144         let bound_vars = self.1;
1145         self.0.map(|v| Binder(v, bound_vars))
1146     }
1147 }
1148
1149 impl<'tcx, T: IntoIterator> Binder<'tcx, T> {
1150     pub fn iter(self) -> impl Iterator<Item = ty::Binder<'tcx, T::Item>> {
1151         let bound_vars = self.1;
1152         self.0.into_iter().map(|v| Binder(v, bound_vars))
1153     }
1154 }
1155
1156 struct SkipBindersAt<'tcx> {
1157     tcx: TyCtxt<'tcx>,
1158     index: ty::DebruijnIndex,
1159 }
1160
1161 impl<'tcx> FallibleTypeFolder<'tcx> for SkipBindersAt<'tcx> {
1162     type Error = ();
1163
1164     fn tcx(&self) -> TyCtxt<'tcx> {
1165         self.tcx
1166     }
1167
1168     fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error>
1169     where
1170         T: ty::TypeFoldable<'tcx>,
1171     {
1172         self.index.shift_in(1);
1173         let value = t.try_map_bound(|t| t.try_fold_with(self));
1174         self.index.shift_out(1);
1175         value
1176     }
1177
1178     fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
1179         if !ty.has_escaping_bound_vars() {
1180             Ok(ty)
1181         } else if let ty::Bound(index, bv) = *ty.kind() {
1182             if index == self.index {
1183                 Err(())
1184             } else {
1185                 Ok(self.tcx().mk_ty(ty::Bound(index.shifted_out(1), bv)))
1186             }
1187         } else {
1188             ty.try_super_fold_with(self)
1189         }
1190     }
1191
1192     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
1193         if !r.has_escaping_bound_vars() {
1194             Ok(r)
1195         } else if let ty::ReLateBound(index, bv) = r.kind() {
1196             if index == self.index {
1197                 Err(())
1198             } else {
1199                 Ok(self.tcx().mk_region(ty::ReLateBound(index.shifted_out(1), bv)))
1200             }
1201         } else {
1202             r.try_super_fold_with(self)
1203         }
1204     }
1205
1206     fn try_fold_const(&mut self, ct: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
1207         if !ct.has_escaping_bound_vars() {
1208             Ok(ct)
1209         } else if let ty::ConstKind::Bound(index, bv) = ct.kind() {
1210             if index == self.index {
1211                 Err(())
1212             } else {
1213                 Ok(self.tcx().mk_const(
1214                     ty::ConstKind::Bound(index.shifted_out(1), bv),
1215                     ct.ty().try_fold_with(self)?,
1216                 ))
1217             }
1218         } else {
1219             ct.try_super_fold_with(self)
1220         }
1221     }
1222
1223     fn try_fold_predicate(
1224         &mut self,
1225         p: ty::Predicate<'tcx>,
1226     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
1227         if !p.has_escaping_bound_vars() { Ok(p) } else { p.try_super_fold_with(self) }
1228     }
1229 }
1230
1231 /// Represents the projection of an associated type.
1232 ///
1233 /// For a projection, this would be `<Ty as Trait<...>>::N`.
1234 ///
1235 /// For an opaque type, there is no explicit syntax.
1236 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
1237 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
1238 pub struct AliasTy<'tcx> {
1239     /// The parameters of the associated or opaque item.
1240     ///
1241     /// For a projection, these are the substitutions for the trait and the
1242     /// GAT substitutions, if there are any.
1243     ///
1244     /// For RPIT the substitutions are for the generics of the function,
1245     /// while for TAIT it is used for the generic parameters of the alias.
1246     pub substs: SubstsRef<'tcx>,
1247
1248     /// The `DefId` of the `TraitItem` for the associated type `N` if this is a projection,
1249     /// or the `OpaqueType` item if this is an opaque.
1250     ///
1251     /// During codegen, `tcx.type_of(def_id)` can be used to get the type of the
1252     /// underlying type if the type is an opaque.
1253     ///
1254     /// Note that if this is an associated type, this is not the `DefId` of the
1255     /// `TraitRef` containing this associated type, which is in `tcx.associated_item(def_id).container`,
1256     /// aka. `tcx.parent(def_id)`.
1257     pub def_id: DefId,
1258
1259     /// This field exists to prevent the creation of `ProjectionTy` without using
1260     /// [TyCtxt::mk_alias_ty].
1261     pub(super) _use_mk_alias_ty_instead: (),
1262 }
1263
1264 impl<'tcx> AliasTy<'tcx> {
1265     pub fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId {
1266         match tcx.def_kind(self.def_id) {
1267             DefKind::AssocTy | DefKind::AssocConst => tcx.parent(self.def_id),
1268             DefKind::ImplTraitPlaceholder => {
1269                 tcx.parent(tcx.impl_trait_in_trait_parent(self.def_id))
1270             }
1271             kind => bug!("unexpected DefKind in ProjectionTy: {kind:?}"),
1272         }
1273     }
1274
1275     /// Extracts the underlying trait reference and own substs from this projection.
1276     /// For example, if this is a projection of `<T as StreamingIterator>::Item<'a>`,
1277     /// then this function would return a `T: Iterator` trait reference and `['a]` as the own substs
1278     pub fn trait_ref_and_own_substs(
1279         self,
1280         tcx: TyCtxt<'tcx>,
1281     ) -> (ty::TraitRef<'tcx>, &'tcx [ty::GenericArg<'tcx>]) {
1282         debug_assert!(matches!(tcx.def_kind(self.def_id), DefKind::AssocTy | DefKind::AssocConst));
1283         let trait_def_id = self.trait_def_id(tcx);
1284         let trait_generics = tcx.generics_of(trait_def_id);
1285         (
1286             tcx.mk_trait_ref(trait_def_id, self.substs.truncate_to(tcx, trait_generics)),
1287             &self.substs[trait_generics.count()..],
1288         )
1289     }
1290
1291     /// Extracts the underlying trait reference from this projection.
1292     /// For example, if this is a projection of `<T as Iterator>::Item`,
1293     /// then this function would return a `T: Iterator` trait reference.
1294     ///
1295     /// WARNING: This will drop the substs for generic associated types
1296     /// consider calling [Self::trait_ref_and_own_substs] to get those
1297     /// as well.
1298     pub fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> {
1299         let def_id = self.trait_def_id(tcx);
1300         tcx.mk_trait_ref(def_id, self.substs.truncate_to(tcx, tcx.generics_of(def_id)))
1301     }
1302
1303     pub fn self_ty(self) -> Ty<'tcx> {
1304         self.substs.type_at(0)
1305     }
1306
1307     pub fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
1308         tcx.mk_alias_ty(self.def_id, [self_ty.into()].into_iter().chain(self.substs.iter().skip(1)))
1309     }
1310 }
1311
1312 #[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable, Lift)]
1313 pub struct GenSig<'tcx> {
1314     pub resume_ty: Ty<'tcx>,
1315     pub yield_ty: Ty<'tcx>,
1316     pub return_ty: Ty<'tcx>,
1317 }
1318
1319 pub type PolyGenSig<'tcx> = Binder<'tcx, GenSig<'tcx>>;
1320
1321 /// Signature of a function type, which we have arbitrarily
1322 /// decided to use to refer to the input/output types.
1323 ///
1324 /// - `inputs`: is the list of arguments and their modes.
1325 /// - `output`: is the return type.
1326 /// - `c_variadic`: indicates whether this is a C-variadic function.
1327 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
1328 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
1329 pub struct FnSig<'tcx> {
1330     pub inputs_and_output: &'tcx List<Ty<'tcx>>,
1331     pub c_variadic: bool,
1332     pub unsafety: hir::Unsafety,
1333     pub abi: abi::Abi,
1334 }
1335
1336 impl<'tcx> FnSig<'tcx> {
1337     pub fn inputs(&self) -> &'tcx [Ty<'tcx>] {
1338         &self.inputs_and_output[..self.inputs_and_output.len() - 1]
1339     }
1340
1341     pub fn output(&self) -> Ty<'tcx> {
1342         self.inputs_and_output[self.inputs_and_output.len() - 1]
1343     }
1344
1345     // Creates a minimal `FnSig` to be used when encountering a `TyKind::Error` in a fallible
1346     // method.
1347     fn fake() -> FnSig<'tcx> {
1348         FnSig {
1349             inputs_and_output: List::empty(),
1350             c_variadic: false,
1351             unsafety: hir::Unsafety::Normal,
1352             abi: abi::Abi::Rust,
1353         }
1354     }
1355 }
1356
1357 pub type PolyFnSig<'tcx> = Binder<'tcx, FnSig<'tcx>>;
1358
1359 impl<'tcx> PolyFnSig<'tcx> {
1360     #[inline]
1361     pub fn inputs(&self) -> Binder<'tcx, &'tcx [Ty<'tcx>]> {
1362         self.map_bound_ref_unchecked(|fn_sig| fn_sig.inputs())
1363     }
1364     #[inline]
1365     pub fn input(&self, index: usize) -> ty::Binder<'tcx, Ty<'tcx>> {
1366         self.map_bound_ref(|fn_sig| fn_sig.inputs()[index])
1367     }
1368     pub fn inputs_and_output(&self) -> ty::Binder<'tcx, &'tcx List<Ty<'tcx>>> {
1369         self.map_bound_ref(|fn_sig| fn_sig.inputs_and_output)
1370     }
1371     #[inline]
1372     pub fn output(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
1373         self.map_bound_ref(|fn_sig| fn_sig.output())
1374     }
1375     pub fn c_variadic(&self) -> bool {
1376         self.skip_binder().c_variadic
1377     }
1378     pub fn unsafety(&self) -> hir::Unsafety {
1379         self.skip_binder().unsafety
1380     }
1381     pub fn abi(&self) -> abi::Abi {
1382         self.skip_binder().abi
1383     }
1384 }
1385
1386 pub type CanonicalPolyFnSig<'tcx> = Canonical<'tcx, Binder<'tcx, FnSig<'tcx>>>;
1387
1388 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
1389 #[derive(HashStable)]
1390 pub struct ParamTy {
1391     pub index: u32,
1392     pub name: Symbol,
1393 }
1394
1395 impl<'tcx> ParamTy {
1396     pub fn new(index: u32, name: Symbol) -> ParamTy {
1397         ParamTy { index, name }
1398     }
1399
1400     pub fn for_def(def: &ty::GenericParamDef) -> ParamTy {
1401         ParamTy::new(def.index, def.name)
1402     }
1403
1404     #[inline]
1405     pub fn to_ty(self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
1406         tcx.mk_ty_param(self.index, self.name)
1407     }
1408
1409     pub fn span_from_generics(&self, tcx: TyCtxt<'tcx>, item_with_generics: DefId) -> Span {
1410         let generics = tcx.generics_of(item_with_generics);
1411         let type_param = generics.type_param(self, tcx);
1412         tcx.def_span(type_param.def_id)
1413     }
1414 }
1415
1416 #[derive(Copy, Clone, Hash, TyEncodable, TyDecodable, Eq, PartialEq, Ord, PartialOrd)]
1417 #[derive(HashStable)]
1418 pub struct ParamConst {
1419     pub index: u32,
1420     pub name: Symbol,
1421 }
1422
1423 impl ParamConst {
1424     pub fn new(index: u32, name: Symbol) -> ParamConst {
1425         ParamConst { index, name }
1426     }
1427
1428     pub fn for_def(def: &ty::GenericParamDef) -> ParamConst {
1429         ParamConst::new(def.index, def.name)
1430     }
1431 }
1432
1433 /// Use this rather than `RegionKind`, whenever possible.
1434 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, HashStable)]
1435 #[rustc_pass_by_value]
1436 pub struct Region<'tcx>(pub Interned<'tcx, RegionKind<'tcx>>);
1437
1438 impl<'tcx> Deref for Region<'tcx> {
1439     type Target = RegionKind<'tcx>;
1440
1441     #[inline]
1442     fn deref(&self) -> &RegionKind<'tcx> {
1443         &self.0.0
1444     }
1445 }
1446
1447 impl<'tcx> fmt::Debug for Region<'tcx> {
1448     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1449         write!(f, "{:?}", self.kind())
1450     }
1451 }
1452
1453 #[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable, PartialOrd, Ord)]
1454 #[derive(HashStable)]
1455 pub struct EarlyBoundRegion {
1456     pub def_id: DefId,
1457     pub index: u32,
1458     pub name: Symbol,
1459 }
1460
1461 impl fmt::Debug for EarlyBoundRegion {
1462     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1463         write!(f, "{}, {}", self.index, self.name)
1464     }
1465 }
1466
1467 /// A **`const`** **v**ariable **ID**.
1468 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
1469 #[derive(HashStable, TyEncodable, TyDecodable)]
1470 pub struct ConstVid<'tcx> {
1471     pub index: u32,
1472     pub phantom: PhantomData<&'tcx ()>,
1473 }
1474
1475 rustc_index::newtype_index! {
1476     /// A **region** (lifetime) **v**ariable **ID**.
1477     #[derive(HashStable)]
1478     #[debug_format = "'_#{}r"]
1479     pub struct RegionVid {}
1480 }
1481
1482 impl Atom for RegionVid {
1483     fn index(self) -> usize {
1484         Idx::index(self)
1485     }
1486 }
1487
1488 rustc_index::newtype_index! {
1489     #[derive(HashStable)]
1490     pub struct BoundVar {}
1491 }
1492
1493 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
1494 #[derive(HashStable)]
1495 pub struct BoundTy {
1496     pub var: BoundVar,
1497     pub kind: BoundTyKind,
1498 }
1499
1500 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
1501 #[derive(HashStable)]
1502 pub enum BoundTyKind {
1503     Anon,
1504     Param(Symbol),
1505 }
1506
1507 impl From<BoundVar> for BoundTy {
1508     fn from(var: BoundVar) -> Self {
1509         BoundTy { var, kind: BoundTyKind::Anon }
1510     }
1511 }
1512
1513 /// A `ProjectionPredicate` for an `ExistentialTraitRef`.
1514 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
1515 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
1516 pub struct ExistentialProjection<'tcx> {
1517     pub def_id: DefId,
1518     pub substs: SubstsRef<'tcx>,
1519     pub term: Term<'tcx>,
1520 }
1521
1522 pub type PolyExistentialProjection<'tcx> = Binder<'tcx, ExistentialProjection<'tcx>>;
1523
1524 impl<'tcx> ExistentialProjection<'tcx> {
1525     /// Extracts the underlying existential trait reference from this projection.
1526     /// For example, if this is a projection of `exists T. <T as Iterator>::Item == X`,
1527     /// then this function would return an `exists T. T: Iterator` existential trait
1528     /// reference.
1529     pub fn trait_ref(&self, tcx: TyCtxt<'tcx>) -> ty::ExistentialTraitRef<'tcx> {
1530         let def_id = tcx.parent(self.def_id);
1531         let subst_count = tcx.generics_of(def_id).count() - 1;
1532         let substs = tcx.intern_substs(&self.substs[..subst_count]);
1533         ty::ExistentialTraitRef { def_id, substs }
1534     }
1535
1536     pub fn with_self_ty(
1537         &self,
1538         tcx: TyCtxt<'tcx>,
1539         self_ty: Ty<'tcx>,
1540     ) -> ty::ProjectionPredicate<'tcx> {
1541         // otherwise the escaping regions would be captured by the binders
1542         debug_assert!(!self_ty.has_escaping_bound_vars());
1543
1544         ty::ProjectionPredicate {
1545             projection_ty: tcx
1546                 .mk_alias_ty(self.def_id, [self_ty.into()].into_iter().chain(self.substs)),
1547             term: self.term,
1548         }
1549     }
1550
1551     pub fn erase_self_ty(
1552         tcx: TyCtxt<'tcx>,
1553         projection_predicate: ty::ProjectionPredicate<'tcx>,
1554     ) -> Self {
1555         // Assert there is a Self.
1556         projection_predicate.projection_ty.substs.type_at(0);
1557
1558         Self {
1559             def_id: projection_predicate.projection_ty.def_id,
1560             substs: tcx.intern_substs(&projection_predicate.projection_ty.substs[1..]),
1561             term: projection_predicate.term,
1562         }
1563     }
1564 }
1565
1566 impl<'tcx> PolyExistentialProjection<'tcx> {
1567     pub fn with_self_ty(
1568         &self,
1569         tcx: TyCtxt<'tcx>,
1570         self_ty: Ty<'tcx>,
1571     ) -> ty::PolyProjectionPredicate<'tcx> {
1572         self.map_bound(|p| p.with_self_ty(tcx, self_ty))
1573     }
1574
1575     pub fn item_def_id(&self) -> DefId {
1576         self.skip_binder().def_id
1577     }
1578 }
1579
1580 /// Region utilities
1581 impl<'tcx> Region<'tcx> {
1582     pub fn kind(self) -> RegionKind<'tcx> {
1583         *self.0.0
1584     }
1585
1586     pub fn get_name(self) -> Option<Symbol> {
1587         if self.has_name() {
1588             let name = match *self {
1589                 ty::ReEarlyBound(ebr) => Some(ebr.name),
1590                 ty::ReLateBound(_, br) => br.kind.get_name(),
1591                 ty::ReFree(fr) => fr.bound_region.get_name(),
1592                 ty::ReStatic => Some(kw::StaticLifetime),
1593                 ty::RePlaceholder(placeholder) => placeholder.name.get_name(),
1594                 _ => None,
1595             };
1596
1597             return name;
1598         }
1599
1600         None
1601     }
1602
1603     /// Is this region named by the user?
1604     pub fn has_name(self) -> bool {
1605         match *self {
1606             ty::ReEarlyBound(ebr) => ebr.has_name(),
1607             ty::ReLateBound(_, br) => br.kind.is_named(),
1608             ty::ReFree(fr) => fr.bound_region.is_named(),
1609             ty::ReStatic => true,
1610             ty::ReVar(..) => false,
1611             ty::RePlaceholder(placeholder) => placeholder.name.is_named(),
1612             ty::ReErased => false,
1613         }
1614     }
1615
1616     #[inline]
1617     pub fn is_static(self) -> bool {
1618         matches!(*self, ty::ReStatic)
1619     }
1620
1621     #[inline]
1622     pub fn is_erased(self) -> bool {
1623         matches!(*self, ty::ReErased)
1624     }
1625
1626     #[inline]
1627     pub fn is_late_bound(self) -> bool {
1628         matches!(*self, ty::ReLateBound(..))
1629     }
1630
1631     #[inline]
1632     pub fn is_placeholder(self) -> bool {
1633         matches!(*self, ty::RePlaceholder(..))
1634     }
1635
1636     #[inline]
1637     pub fn bound_at_or_above_binder(self, index: ty::DebruijnIndex) -> bool {
1638         match *self {
1639             ty::ReLateBound(debruijn, _) => debruijn >= index,
1640             _ => false,
1641         }
1642     }
1643
1644     pub fn type_flags(self) -> TypeFlags {
1645         let mut flags = TypeFlags::empty();
1646
1647         match *self {
1648             ty::ReVar(..) => {
1649                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
1650                 flags = flags | TypeFlags::HAS_FREE_LOCAL_REGIONS;
1651                 flags = flags | TypeFlags::HAS_RE_INFER;
1652             }
1653             ty::RePlaceholder(..) => {
1654                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
1655                 flags = flags | TypeFlags::HAS_FREE_LOCAL_REGIONS;
1656                 flags = flags | TypeFlags::HAS_RE_PLACEHOLDER;
1657             }
1658             ty::ReEarlyBound(..) => {
1659                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
1660                 flags = flags | TypeFlags::HAS_FREE_LOCAL_REGIONS;
1661                 flags = flags | TypeFlags::HAS_RE_PARAM;
1662             }
1663             ty::ReFree { .. } => {
1664                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
1665                 flags = flags | TypeFlags::HAS_FREE_LOCAL_REGIONS;
1666             }
1667             ty::ReStatic => {
1668                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
1669             }
1670             ty::ReLateBound(..) => {
1671                 flags = flags | TypeFlags::HAS_RE_LATE_BOUND;
1672             }
1673             ty::ReErased => {
1674                 flags = flags | TypeFlags::HAS_RE_ERASED;
1675             }
1676         }
1677
1678         debug!("type_flags({:?}) = {:?}", self, flags);
1679
1680         flags
1681     }
1682
1683     /// Given an early-bound or free region, returns the `DefId` where it was bound.
1684     /// For example, consider the regions in this snippet of code:
1685     ///
1686     /// ```ignore (illustrative)
1687     /// impl<'a> Foo {
1688     /// //   ^^ -- early bound, declared on an impl
1689     ///
1690     ///     fn bar<'b, 'c>(x: &self, y: &'b u32, z: &'c u64) where 'static: 'c
1691     /// //         ^^  ^^     ^ anonymous, late-bound
1692     /// //         |   early-bound, appears in where-clauses
1693     /// //         late-bound, appears only in fn args
1694     ///     {..}
1695     /// }
1696     /// ```
1697     ///
1698     /// Here, `free_region_binding_scope('a)` would return the `DefId`
1699     /// of the impl, and for all the other highlighted regions, it
1700     /// would return the `DefId` of the function. In other cases (not shown), this
1701     /// function might return the `DefId` of a closure.
1702     pub fn free_region_binding_scope(self, tcx: TyCtxt<'_>) -> DefId {
1703         match *self {
1704             ty::ReEarlyBound(br) => tcx.parent(br.def_id),
1705             ty::ReFree(fr) => fr.scope,
1706             _ => bug!("free_region_binding_scope invoked on inappropriate region: {:?}", self),
1707         }
1708     }
1709
1710     /// True for free regions other than `'static`.
1711     pub fn is_free(self) -> bool {
1712         matches!(*self, ty::ReEarlyBound(_) | ty::ReFree(_))
1713     }
1714
1715     /// True if `self` is a free region or static.
1716     pub fn is_free_or_static(self) -> bool {
1717         match *self {
1718             ty::ReStatic => true,
1719             _ => self.is_free(),
1720         }
1721     }
1722
1723     pub fn is_var(self) -> bool {
1724         matches!(self.kind(), ty::ReVar(_))
1725     }
1726 }
1727
1728 /// Type utilities
1729 impl<'tcx> Ty<'tcx> {
1730     #[inline(always)]
1731     pub fn kind(self) -> &'tcx TyKind<'tcx> {
1732         &self.0.0
1733     }
1734
1735     #[inline(always)]
1736     pub fn flags(self) -> TypeFlags {
1737         self.0.0.flags
1738     }
1739
1740     #[inline]
1741     pub fn is_unit(self) -> bool {
1742         match self.kind() {
1743             Tuple(ref tys) => tys.is_empty(),
1744             _ => false,
1745         }
1746     }
1747
1748     #[inline]
1749     pub fn is_never(self) -> bool {
1750         matches!(self.kind(), Never)
1751     }
1752
1753     #[inline]
1754     pub fn is_primitive(self) -> bool {
1755         self.kind().is_primitive()
1756     }
1757
1758     #[inline]
1759     pub fn is_adt(self) -> bool {
1760         matches!(self.kind(), Adt(..))
1761     }
1762
1763     #[inline]
1764     pub fn is_ref(self) -> bool {
1765         matches!(self.kind(), Ref(..))
1766     }
1767
1768     #[inline]
1769     pub fn is_ty_var(self) -> bool {
1770         matches!(self.kind(), Infer(TyVar(_)))
1771     }
1772
1773     #[inline]
1774     pub fn ty_vid(self) -> Option<ty::TyVid> {
1775         match self.kind() {
1776             &Infer(TyVar(vid)) => Some(vid),
1777             _ => None,
1778         }
1779     }
1780
1781     #[inline]
1782     pub fn is_ty_or_numeric_infer(self) -> bool {
1783         matches!(self.kind(), Infer(_))
1784     }
1785
1786     #[inline]
1787     pub fn is_phantom_data(self) -> bool {
1788         if let Adt(def, _) = self.kind() { def.is_phantom_data() } else { false }
1789     }
1790
1791     #[inline]
1792     pub fn is_bool(self) -> bool {
1793         *self.kind() == Bool
1794     }
1795
1796     /// Returns `true` if this type is a `str`.
1797     #[inline]
1798     pub fn is_str(self) -> bool {
1799         *self.kind() == Str
1800     }
1801
1802     #[inline]
1803     pub fn is_param(self, index: u32) -> bool {
1804         match self.kind() {
1805             ty::Param(ref data) => data.index == index,
1806             _ => false,
1807         }
1808     }
1809
1810     #[inline]
1811     pub fn is_slice(self) -> bool {
1812         matches!(self.kind(), Slice(_))
1813     }
1814
1815     #[inline]
1816     pub fn is_array_slice(self) -> bool {
1817         match self.kind() {
1818             Slice(_) => true,
1819             RawPtr(TypeAndMut { ty, .. }) | Ref(_, ty, _) => matches!(ty.kind(), Slice(_)),
1820             _ => false,
1821         }
1822     }
1823
1824     #[inline]
1825     pub fn is_array(self) -> bool {
1826         matches!(self.kind(), Array(..))
1827     }
1828
1829     #[inline]
1830     pub fn is_simd(self) -> bool {
1831         match self.kind() {
1832             Adt(def, _) => def.repr().simd(),
1833             _ => false,
1834         }
1835     }
1836
1837     pub fn sequence_element_type(self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
1838         match self.kind() {
1839             Array(ty, _) | Slice(ty) => *ty,
1840             Str => tcx.types.u8,
1841             _ => bug!("`sequence_element_type` called on non-sequence value: {}", self),
1842         }
1843     }
1844
1845     pub fn simd_size_and_type(self, tcx: TyCtxt<'tcx>) -> (u64, Ty<'tcx>) {
1846         match self.kind() {
1847             Adt(def, substs) => {
1848                 assert!(def.repr().simd(), "`simd_size_and_type` called on non-SIMD type");
1849                 let variant = def.non_enum_variant();
1850                 let f0_ty = variant.fields[0].ty(tcx, substs);
1851
1852                 match f0_ty.kind() {
1853                     // If the first field is an array, we assume it is the only field and its
1854                     // elements are the SIMD components.
1855                     Array(f0_elem_ty, f0_len) => {
1856                         // FIXME(repr_simd): https://github.com/rust-lang/rust/pull/78863#discussion_r522784112
1857                         // The way we evaluate the `N` in `[T; N]` here only works since we use
1858                         // `simd_size_and_type` post-monomorphization. It will probably start to ICE
1859                         // if we use it in generic code. See the `simd-array-trait` ui test.
1860                         (f0_len.eval_usize(tcx, ParamEnv::empty()) as u64, *f0_elem_ty)
1861                     }
1862                     // Otherwise, the fields of this Adt are the SIMD components (and we assume they
1863                     // all have the same type).
1864                     _ => (variant.fields.len() as u64, f0_ty),
1865                 }
1866             }
1867             _ => bug!("`simd_size_and_type` called on invalid type"),
1868         }
1869     }
1870
1871     #[inline]
1872     pub fn is_region_ptr(self) -> bool {
1873         matches!(self.kind(), Ref(..))
1874     }
1875
1876     #[inline]
1877     pub fn is_mutable_ptr(self) -> bool {
1878         matches!(
1879             self.kind(),
1880             RawPtr(TypeAndMut { mutbl: hir::Mutability::Mut, .. })
1881                 | Ref(_, _, hir::Mutability::Mut)
1882         )
1883     }
1884
1885     /// Get the mutability of the reference or `None` when not a reference
1886     #[inline]
1887     pub fn ref_mutability(self) -> Option<hir::Mutability> {
1888         match self.kind() {
1889             Ref(_, _, mutability) => Some(*mutability),
1890             _ => None,
1891         }
1892     }
1893
1894     #[inline]
1895     pub fn is_unsafe_ptr(self) -> bool {
1896         matches!(self.kind(), RawPtr(_))
1897     }
1898
1899     /// Tests if this is any kind of primitive pointer type (reference, raw pointer, fn pointer).
1900     #[inline]
1901     pub fn is_any_ptr(self) -> bool {
1902         self.is_region_ptr() || self.is_unsafe_ptr() || self.is_fn_ptr()
1903     }
1904
1905     #[inline]
1906     pub fn is_box(self) -> bool {
1907         match self.kind() {
1908             Adt(def, _) => def.is_box(),
1909             _ => false,
1910         }
1911     }
1912
1913     /// Panics if called on any type other than `Box<T>`.
1914     pub fn boxed_ty(self) -> Ty<'tcx> {
1915         match self.kind() {
1916             Adt(def, substs) if def.is_box() => substs.type_at(0),
1917             _ => bug!("`boxed_ty` is called on non-box type {:?}", self),
1918         }
1919     }
1920
1921     /// A scalar type is one that denotes an atomic datum, with no sub-components.
1922     /// (A RawPtr is scalar because it represents a non-managed pointer, so its
1923     /// contents are abstract to rustc.)
1924     #[inline]
1925     pub fn is_scalar(self) -> bool {
1926         matches!(
1927             self.kind(),
1928             Bool | Char
1929                 | Int(_)
1930                 | Float(_)
1931                 | Uint(_)
1932                 | FnDef(..)
1933                 | FnPtr(_)
1934                 | RawPtr(_)
1935                 | Infer(IntVar(_) | FloatVar(_))
1936         )
1937     }
1938
1939     /// Returns `true` if this type is a floating point type.
1940     #[inline]
1941     pub fn is_floating_point(self) -> bool {
1942         matches!(self.kind(), Float(_) | Infer(FloatVar(_)))
1943     }
1944
1945     #[inline]
1946     pub fn is_trait(self) -> bool {
1947         matches!(self.kind(), Dynamic(_, _, ty::Dyn))
1948     }
1949
1950     #[inline]
1951     pub fn is_dyn_star(self) -> bool {
1952         matches!(self.kind(), Dynamic(_, _, ty::DynStar))
1953     }
1954
1955     #[inline]
1956     pub fn is_enum(self) -> bool {
1957         matches!(self.kind(), Adt(adt_def, _) if adt_def.is_enum())
1958     }
1959
1960     #[inline]
1961     pub fn is_union(self) -> bool {
1962         matches!(self.kind(), Adt(adt_def, _) if adt_def.is_union())
1963     }
1964
1965     #[inline]
1966     pub fn is_closure(self) -> bool {
1967         matches!(self.kind(), Closure(..))
1968     }
1969
1970     #[inline]
1971     pub fn is_generator(self) -> bool {
1972         matches!(self.kind(), Generator(..))
1973     }
1974
1975     #[inline]
1976     pub fn is_integral(self) -> bool {
1977         matches!(self.kind(), Infer(IntVar(_)) | Int(_) | Uint(_))
1978     }
1979
1980     #[inline]
1981     pub fn is_fresh_ty(self) -> bool {
1982         matches!(self.kind(), Infer(FreshTy(_)))
1983     }
1984
1985     #[inline]
1986     pub fn is_fresh(self) -> bool {
1987         matches!(self.kind(), Infer(FreshTy(_) | FreshIntTy(_) | FreshFloatTy(_)))
1988     }
1989
1990     #[inline]
1991     pub fn is_char(self) -> bool {
1992         matches!(self.kind(), Char)
1993     }
1994
1995     #[inline]
1996     pub fn is_numeric(self) -> bool {
1997         self.is_integral() || self.is_floating_point()
1998     }
1999
2000     #[inline]
2001     pub fn is_signed(self) -> bool {
2002         matches!(self.kind(), Int(_))
2003     }
2004
2005     #[inline]
2006     pub fn is_ptr_sized_integral(self) -> bool {
2007         matches!(self.kind(), Int(ty::IntTy::Isize) | Uint(ty::UintTy::Usize))
2008     }
2009
2010     #[inline]
2011     pub fn has_concrete_skeleton(self) -> bool {
2012         !matches!(self.kind(), Param(_) | Infer(_) | Error(_))
2013     }
2014
2015     /// Checks whether a type recursively contains another type
2016     ///
2017     /// Example: `Option<()>` contains `()`
2018     pub fn contains(self, other: Ty<'tcx>) -> bool {
2019         struct ContainsTyVisitor<'tcx>(Ty<'tcx>);
2020
2021         impl<'tcx> TypeVisitor<'tcx> for ContainsTyVisitor<'tcx> {
2022             type BreakTy = ();
2023
2024             fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
2025                 if self.0 == t { ControlFlow::BREAK } else { t.super_visit_with(self) }
2026             }
2027         }
2028
2029         let cf = self.visit_with(&mut ContainsTyVisitor(other));
2030         cf.is_break()
2031     }
2032
2033     /// Returns the type and mutability of `*ty`.
2034     ///
2035     /// The parameter `explicit` indicates if this is an *explicit* dereference.
2036     /// Some types -- notably unsafe ptrs -- can only be dereferenced explicitly.
2037     pub fn builtin_deref(self, explicit: bool) -> Option<TypeAndMut<'tcx>> {
2038         match self.kind() {
2039             Adt(def, _) if def.is_box() => {
2040                 Some(TypeAndMut { ty: self.boxed_ty(), mutbl: hir::Mutability::Not })
2041             }
2042             Ref(_, ty, mutbl) => Some(TypeAndMut { ty: *ty, mutbl: *mutbl }),
2043             RawPtr(mt) if explicit => Some(*mt),
2044             _ => None,
2045         }
2046     }
2047
2048     /// Returns the type of `ty[i]`.
2049     pub fn builtin_index(self) -> Option<Ty<'tcx>> {
2050         match self.kind() {
2051             Array(ty, _) | Slice(ty) => Some(*ty),
2052             _ => None,
2053         }
2054     }
2055
2056     pub fn fn_sig(self, tcx: TyCtxt<'tcx>) -> PolyFnSig<'tcx> {
2057         match self.kind() {
2058             FnDef(def_id, substs) => tcx.bound_fn_sig(*def_id).subst(tcx, substs),
2059             FnPtr(f) => *f,
2060             Error(_) => {
2061                 // ignore errors (#54954)
2062                 ty::Binder::dummy(FnSig::fake())
2063             }
2064             Closure(..) => bug!(
2065                 "to get the signature of a closure, use `substs.as_closure().sig()` not `fn_sig()`",
2066             ),
2067             _ => bug!("Ty::fn_sig() called on non-fn type: {:?}", self),
2068         }
2069     }
2070
2071     #[inline]
2072     pub fn is_fn(self) -> bool {
2073         matches!(self.kind(), FnDef(..) | FnPtr(_))
2074     }
2075
2076     #[inline]
2077     pub fn is_fn_ptr(self) -> bool {
2078         matches!(self.kind(), FnPtr(_))
2079     }
2080
2081     #[inline]
2082     pub fn is_impl_trait(self) -> bool {
2083         matches!(self.kind(), Alias(ty::Opaque, ..))
2084     }
2085
2086     #[inline]
2087     pub fn ty_adt_def(self) -> Option<AdtDef<'tcx>> {
2088         match self.kind() {
2089             Adt(adt, _) => Some(*adt),
2090             _ => None,
2091         }
2092     }
2093
2094     /// Iterates over tuple fields.
2095     /// Panics when called on anything but a tuple.
2096     #[inline]
2097     pub fn tuple_fields(self) -> &'tcx List<Ty<'tcx>> {
2098         match self.kind() {
2099             Tuple(substs) => substs,
2100             _ => bug!("tuple_fields called on non-tuple"),
2101         }
2102     }
2103
2104     /// If the type contains variants, returns the valid range of variant indices.
2105     //
2106     // FIXME: This requires the optimized MIR in the case of generators.
2107     #[inline]
2108     pub fn variant_range(self, tcx: TyCtxt<'tcx>) -> Option<Range<VariantIdx>> {
2109         match self.kind() {
2110             TyKind::Adt(adt, _) => Some(adt.variant_range()),
2111             TyKind::Generator(def_id, substs, _) => {
2112                 Some(substs.as_generator().variant_range(*def_id, tcx))
2113             }
2114             _ => None,
2115         }
2116     }
2117
2118     /// If the type contains variants, returns the variant for `variant_index`.
2119     /// Panics if `variant_index` is out of range.
2120     //
2121     // FIXME: This requires the optimized MIR in the case of generators.
2122     #[inline]
2123     pub fn discriminant_for_variant(
2124         self,
2125         tcx: TyCtxt<'tcx>,
2126         variant_index: VariantIdx,
2127     ) -> Option<Discr<'tcx>> {
2128         match self.kind() {
2129             TyKind::Adt(adt, _) if adt.variants().is_empty() => {
2130                 // This can actually happen during CTFE, see
2131                 // https://github.com/rust-lang/rust/issues/89765.
2132                 None
2133             }
2134             TyKind::Adt(adt, _) if adt.is_enum() => {
2135                 Some(adt.discriminant_for_variant(tcx, variant_index))
2136             }
2137             TyKind::Generator(def_id, substs, _) => {
2138                 Some(substs.as_generator().discriminant_for_variant(*def_id, tcx, variant_index))
2139             }
2140             _ => None,
2141         }
2142     }
2143
2144     /// Returns the type of the discriminant of this type.
2145     pub fn discriminant_ty(self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
2146         match self.kind() {
2147             ty::Adt(adt, _) if adt.is_enum() => adt.repr().discr_type().to_ty(tcx),
2148             ty::Generator(_, substs, _) => substs.as_generator().discr_ty(tcx),
2149
2150             ty::Param(_) | ty::Alias(..) | ty::Infer(ty::TyVar(_)) => {
2151                 let assoc_items = tcx.associated_item_def_ids(
2152                     tcx.require_lang_item(hir::LangItem::DiscriminantKind, None),
2153                 );
2154                 tcx.mk_projection(assoc_items[0], tcx.intern_substs(&[self.into()]))
2155             }
2156
2157             ty::Bool
2158             | ty::Char
2159             | ty::Int(_)
2160             | ty::Uint(_)
2161             | ty::Float(_)
2162             | ty::Adt(..)
2163             | ty::Foreign(_)
2164             | ty::Str
2165             | ty::Array(..)
2166             | ty::Slice(_)
2167             | ty::RawPtr(_)
2168             | ty::Ref(..)
2169             | ty::FnDef(..)
2170             | ty::FnPtr(..)
2171             | ty::Dynamic(..)
2172             | ty::Closure(..)
2173             | ty::GeneratorWitness(..)
2174             | ty::Never
2175             | ty::Tuple(_)
2176             | ty::Error(_)
2177             | ty::Infer(IntVar(_) | FloatVar(_)) => tcx.types.u8,
2178
2179             ty::Bound(..)
2180             | ty::Placeholder(_)
2181             | ty::Infer(FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
2182                 bug!("`discriminant_ty` applied to unexpected type: {:?}", self)
2183             }
2184         }
2185     }
2186
2187     /// Returns the type of metadata for (potentially fat) pointers to this type,
2188     /// and a boolean signifying if this is conditional on this type being `Sized`.
2189     pub fn ptr_metadata_ty(
2190         self,
2191         tcx: TyCtxt<'tcx>,
2192         normalize: impl FnMut(Ty<'tcx>) -> Ty<'tcx>,
2193     ) -> (Ty<'tcx>, bool) {
2194         let tail = tcx.struct_tail_with_normalize(self, normalize, || {});
2195         match tail.kind() {
2196             // Sized types
2197             ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
2198             | ty::Uint(_)
2199             | ty::Int(_)
2200             | ty::Bool
2201             | ty::Float(_)
2202             | ty::FnDef(..)
2203             | ty::FnPtr(_)
2204             | ty::RawPtr(..)
2205             | ty::Char
2206             | ty::Ref(..)
2207             | ty::Generator(..)
2208             | ty::GeneratorWitness(..)
2209             | ty::Array(..)
2210             | ty::Closure(..)
2211             | ty::Never
2212             | ty::Error(_)
2213             // Extern types have metadata = ().
2214             | ty::Foreign(..)
2215             // If returned by `struct_tail_without_normalization` this is a unit struct
2216             // without any fields, or not a struct, and therefore is Sized.
2217             | ty::Adt(..)
2218             // If returned by `struct_tail_without_normalization` this is the empty tuple,
2219             // a.k.a. unit type, which is Sized
2220             | ty::Tuple(..) => (tcx.types.unit, false),
2221
2222             ty::Str | ty::Slice(_) => (tcx.types.usize, false),
2223             ty::Dynamic(..) => {
2224                 let dyn_metadata = tcx.require_lang_item(LangItem::DynMetadata, None);
2225                 (tcx.bound_type_of(dyn_metadata).subst(tcx, &[tail.into()]), false)
2226             },
2227
2228             // type parameters only have unit metadata if they're sized, so return true
2229             // to make sure we double check this during confirmation
2230             ty::Param(_) |  ty::Alias(..) => (tcx.types.unit, true),
2231
2232             ty::Infer(ty::TyVar(_))
2233             | ty::Bound(..)
2234             | ty::Placeholder(..)
2235             | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
2236                 bug!("`ptr_metadata_ty` applied to unexpected type: {:?} (tail = {:?})", self, tail)
2237             }
2238         }
2239     }
2240
2241     /// When we create a closure, we record its kind (i.e., what trait
2242     /// it implements) into its `ClosureSubsts` using a type
2243     /// parameter. This is kind of a phantom type, except that the
2244     /// most convenient thing for us to are the integral types. This
2245     /// function converts such a special type into the closure
2246     /// kind. To go the other way, use `closure_kind.to_ty(tcx)`.
2247     ///
2248     /// Note that during type checking, we use an inference variable
2249     /// to represent the closure kind, because it has not yet been
2250     /// inferred. Once upvar inference (in `rustc_hir_analysis/src/check/upvar.rs`)
2251     /// is complete, that type variable will be unified.
2252     pub fn to_opt_closure_kind(self) -> Option<ty::ClosureKind> {
2253         match self.kind() {
2254             Int(int_ty) => match int_ty {
2255                 ty::IntTy::I8 => Some(ty::ClosureKind::Fn),
2256                 ty::IntTy::I16 => Some(ty::ClosureKind::FnMut),
2257                 ty::IntTy::I32 => Some(ty::ClosureKind::FnOnce),
2258                 _ => bug!("cannot convert type `{:?}` to a closure kind", self),
2259             },
2260
2261             // "Bound" types appear in canonical queries when the
2262             // closure type is not yet known
2263             Bound(..) | Infer(_) => None,
2264
2265             Error(_) => Some(ty::ClosureKind::Fn),
2266
2267             _ => bug!("cannot convert type `{:?}` to a closure kind", self),
2268         }
2269     }
2270
2271     /// Fast path helper for testing if a type is `Sized`.
2272     ///
2273     /// Returning true means the type is known to be sized. Returning
2274     /// `false` means nothing -- could be sized, might not be.
2275     ///
2276     /// Note that we could never rely on the fact that a type such as `[_]` is
2277     /// trivially `!Sized` because we could be in a type environment with a
2278     /// bound such as `[_]: Copy`. A function with such a bound obviously never
2279     /// can be called, but that doesn't mean it shouldn't typecheck. This is why
2280     /// this method doesn't return `Option<bool>`.
2281     pub fn is_trivially_sized(self, tcx: TyCtxt<'tcx>) -> bool {
2282         match self.kind() {
2283             ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
2284             | ty::Uint(_)
2285             | ty::Int(_)
2286             | ty::Bool
2287             | ty::Float(_)
2288             | ty::FnDef(..)
2289             | ty::FnPtr(_)
2290             | ty::RawPtr(..)
2291             | ty::Char
2292             | ty::Ref(..)
2293             | ty::Generator(..)
2294             | ty::GeneratorWitness(..)
2295             | ty::Array(..)
2296             | ty::Closure(..)
2297             | ty::Never
2298             | ty::Error(_) => true,
2299
2300             ty::Str | ty::Slice(_) | ty::Dynamic(..) | ty::Foreign(..) => false,
2301
2302             ty::Tuple(tys) => tys.iter().all(|ty| ty.is_trivially_sized(tcx)),
2303
2304             ty::Adt(def, _substs) => def.sized_constraint(tcx).0.is_empty(),
2305
2306             ty::Alias(..) | ty::Param(_) => false,
2307
2308             ty::Infer(ty::TyVar(_)) => false,
2309
2310             ty::Bound(..)
2311             | ty::Placeholder(..)
2312             | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
2313                 bug!("`is_trivially_sized` applied to unexpected type: {:?}", self)
2314             }
2315         }
2316     }
2317
2318     /// Fast path helper for primitives which are always `Copy` and which
2319     /// have a side-effect-free `Clone` impl.
2320     ///
2321     /// Returning true means the type is known to be pure and `Copy+Clone`.
2322     /// Returning `false` means nothing -- could be `Copy`, might not be.
2323     ///
2324     /// This is mostly useful for optimizations, as there are the types
2325     /// on which we can replace cloning with dereferencing.
2326     pub fn is_trivially_pure_clone_copy(self) -> bool {
2327         match self.kind() {
2328             ty::Bool | ty::Char | ty::Never => true,
2329
2330             // These aren't even `Clone`
2331             ty::Str | ty::Slice(..) | ty::Foreign(..) | ty::Dynamic(..) => false,
2332
2333             ty::Infer(ty::InferTy::FloatVar(_) | ty::InferTy::IntVar(_))
2334             | ty::Int(..)
2335             | ty::Uint(..)
2336             | ty::Float(..) => true,
2337
2338             // The voldemort ZSTs are fine.
2339             ty::FnDef(..) => true,
2340
2341             ty::Array(element_ty, _len) => element_ty.is_trivially_pure_clone_copy(),
2342
2343             // A 100-tuple isn't "trivial", so doing this only for reasonable sizes.
2344             ty::Tuple(field_tys) => {
2345                 field_tys.len() <= 3 && field_tys.iter().all(Self::is_trivially_pure_clone_copy)
2346             }
2347
2348             // Sometimes traits aren't implemented for every ABI or arity,
2349             // because we can't be generic over everything yet.
2350             ty::FnPtr(..) => false,
2351
2352             // Definitely absolutely not copy.
2353             ty::Ref(_, _, hir::Mutability::Mut) => false,
2354
2355             // Thin pointers & thin shared references are pure-clone-copy, but for
2356             // anything with custom metadata it might be more complicated.
2357             ty::Ref(_, _, hir::Mutability::Not) | ty::RawPtr(..) => false,
2358
2359             ty::Generator(..) | ty::GeneratorWitness(..) => false,
2360
2361             // Might be, but not "trivial" so just giving the safe answer.
2362             ty::Adt(..) | ty::Closure(..) => false,
2363
2364             // Needs normalization or revealing to determine, so no is the safe answer.
2365             ty::Alias(..) => false,
2366
2367             ty::Param(..) | ty::Infer(..) | ty::Error(..) => false,
2368
2369             ty::Bound(..) | ty::Placeholder(..) => {
2370                 bug!("`is_trivially_pure_clone_copy` applied to unexpected type: {:?}", self);
2371             }
2372         }
2373     }
2374
2375     /// If `self` is a primitive, return its [`Symbol`].
2376     pub fn primitive_symbol(self) -> Option<Symbol> {
2377         match self.kind() {
2378             ty::Bool => Some(sym::bool),
2379             ty::Char => Some(sym::char),
2380             ty::Float(f) => match f {
2381                 ty::FloatTy::F32 => Some(sym::f32),
2382                 ty::FloatTy::F64 => Some(sym::f64),
2383             },
2384             ty::Int(f) => match f {
2385                 ty::IntTy::Isize => Some(sym::isize),
2386                 ty::IntTy::I8 => Some(sym::i8),
2387                 ty::IntTy::I16 => Some(sym::i16),
2388                 ty::IntTy::I32 => Some(sym::i32),
2389                 ty::IntTy::I64 => Some(sym::i64),
2390                 ty::IntTy::I128 => Some(sym::i128),
2391             },
2392             ty::Uint(f) => match f {
2393                 ty::UintTy::Usize => Some(sym::usize),
2394                 ty::UintTy::U8 => Some(sym::u8),
2395                 ty::UintTy::U16 => Some(sym::u16),
2396                 ty::UintTy::U32 => Some(sym::u32),
2397                 ty::UintTy::U64 => Some(sym::u64),
2398                 ty::UintTy::U128 => Some(sym::u128),
2399             },
2400             _ => None,
2401         }
2402     }
2403 }
2404
2405 /// Extra information about why we ended up with a particular variance.
2406 /// This is only used to add more information to error messages, and
2407 /// has no effect on soundness. While choosing the 'wrong' `VarianceDiagInfo`
2408 /// may lead to confusing notes in error messages, it will never cause
2409 /// a miscompilation or unsoundness.
2410 ///
2411 /// When in doubt, use `VarianceDiagInfo::default()`
2412 #[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
2413 pub enum VarianceDiagInfo<'tcx> {
2414     /// No additional information - this is the default.
2415     /// We will not add any additional information to error messages.
2416     #[default]
2417     None,
2418     /// We switched our variance because a generic argument occurs inside
2419     /// the invariant generic argument of another type.
2420     Invariant {
2421         /// The generic type containing the generic parameter
2422         /// that changes the variance (e.g. `*mut T`, `MyStruct<T>`)
2423         ty: Ty<'tcx>,
2424         /// The index of the generic parameter being used
2425         /// (e.g. `0` for `*mut T`, `1` for `MyStruct<'CovariantParam, 'InvariantParam>`)
2426         param_index: u32,
2427     },
2428 }
2429
2430 impl<'tcx> VarianceDiagInfo<'tcx> {
2431     /// Mirrors `Variance::xform` - used to 'combine' the existing
2432     /// and new `VarianceDiagInfo`s when our variance changes.
2433     pub fn xform(self, other: VarianceDiagInfo<'tcx>) -> VarianceDiagInfo<'tcx> {
2434         // For now, just use the first `VarianceDiagInfo::Invariant` that we see
2435         match self {
2436             VarianceDiagInfo::None => other,
2437             VarianceDiagInfo::Invariant { .. } => self,
2438         }
2439     }
2440 }