compiler/rustc_type_ir/src/lib.rs

   1 #![feature(fmt_helpers_for_derive)]
   2 #![feature(min_specialization)]
   3 #![feature(rustc_attrs)]
   4 #![deny(rustc::untranslatable_diagnostic)]
   5 #![deny(rustc::diagnostic_outside_of_impl)]
   6
   7 #[macro_use]
   8 extern crate bitflags;
   9 #[macro_use]
  10 extern crate rustc_macros;
  11
  12 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  13 use rustc_data_structures::unify::{EqUnifyValue, UnifyKey};
  14 use smallvec::SmallVec;
  15 use std::fmt;
  16 use std::fmt::Debug;
  17 use std::hash::Hash;
  18 use std::mem::discriminant;
  19
  20 pub mod codec;
  21 pub mod sty;
  22 pub mod ty_info;
  23
  24 pub use codec::*;
  25 pub use sty::*;
  26 pub use ty_info::*;
  27
  28 /// Needed so we can use #[derive(HashStable_Generic)]
  29 pub trait HashStableContext {}
  30
  31 pub trait Interner {
  32     type AdtDef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  33     type SubstsRef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  34     type DefId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  35     type Ty: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  36     type Const: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  37     type Region: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  38     type TypeAndMut: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  39     type Mutability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  40     type Movability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  41     type PolyFnSig: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  42     type ListBinderExistentialPredicate: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  43     type BinderListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  44     type ListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  45     type AliasTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  46     type ParamTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  47     type BoundTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  48     type PlaceholderType: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  49     type InferTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  50     type ErrorGuaranteed: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  51     type PredicateKind: Clone + Debug + Hash + PartialEq + Eq;
  52     type AllocId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  53
  54     type EarlyBoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  55     type BoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  56     type FreeRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  57     type RegionVid: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  58     type PlaceholderRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
  59 }
  60
  61 pub trait InternAs<T: ?Sized, R> {
  62     type Output;
  63     fn intern_with<F>(self, f: F) -> Self::Output
  64     where
  65         F: FnOnce(&[T]) -> R;
  66 }
  67
  68 impl<I, T, R, E> InternAs<T, R> for I
  69 where
  70     E: InternIteratorElement<T, R>,
  71     I: Iterator<Item = E>,
  72 {
  73     type Output = E::Output;
  74     fn intern_with<F>(self, f: F) -> Self::Output
  75     where
  76         F: FnOnce(&[T]) -> R,
  77     {
  78         E::intern_with(self, f)
  79     }
  80 }
  81
  82 pub trait InternIteratorElement<T, R>: Sized {
  83     type Output;
  84     fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output;
  85 }
  86
  87 impl<T, R> InternIteratorElement<T, R> for T {
  88     type Output = R;
  89     fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(
  90         mut iter: I,
  91         f: F,
  92     ) -> Self::Output {
  93         // This code is hot enough that it's worth specializing for the most
  94         // common length lists, to avoid the overhead of `SmallVec` creation.
  95         // Lengths 0, 1, and 2 typically account for ~95% of cases. If
  96         // `size_hint` is incorrect a panic will occur via an `unwrap` or an
  97         // `assert`.
  98         match iter.size_hint() {
  99             (0, Some(0)) => {
 100                 assert!(iter.next().is_none());
 101                 f(&[])
 102             }
 103             (1, Some(1)) => {
 104                 let t0 = iter.next().unwrap();
 105                 assert!(iter.next().is_none());
 106                 f(&[t0])
 107             }
 108             (2, Some(2)) => {
 109                 let t0 = iter.next().unwrap();
 110                 let t1 = iter.next().unwrap();
 111                 assert!(iter.next().is_none());
 112                 f(&[t0, t1])
 113             }
 114             _ => f(&iter.collect::<SmallVec<[_; 8]>>()),
 115         }
 116     }
 117 }
 118
 119 impl<'a, T, R> InternIteratorElement<T, R> for &'a T
 120 where
 121     T: Clone + 'a,
 122 {
 123     type Output = R;
 124     fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
 125         // This code isn't hot.
 126         f(&iter.cloned().collect::<SmallVec<[_; 8]>>())
 127     }
 128 }
 129
 130 impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> {
 131     type Output = Result<R, E>;
 132     fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(
 133         mut iter: I,
 134         f: F,
 135     ) -> Self::Output {
 136         // This code is hot enough that it's worth specializing for the most
 137         // common length lists, to avoid the overhead of `SmallVec` creation.
 138         // Lengths 0, 1, and 2 typically account for ~95% of cases. If
 139         // `size_hint` is incorrect a panic will occur via an `unwrap` or an
 140         // `assert`, unless a failure happens first, in which case the result
 141         // will be an error anyway.
 142         Ok(match iter.size_hint() {
 143             (0, Some(0)) => {
 144                 assert!(iter.next().is_none());
 145                 f(&[])
 146             }
 147             (1, Some(1)) => {
 148                 let t0 = iter.next().unwrap()?;
 149                 assert!(iter.next().is_none());
 150                 f(&[t0])
 151             }
 152             (2, Some(2)) => {
 153                 let t0 = iter.next().unwrap()?;
 154                 let t1 = iter.next().unwrap()?;
 155                 assert!(iter.next().is_none());
 156                 f(&[t0, t1])
 157             }
 158             _ => f(&iter.collect::<Result<SmallVec<[_; 8]>, _>>()?),
 159         })
 160     }
 161 }
 162
 163 bitflags! {
 164     /// Flags that we track on types. These flags are propagated upwards
 165     /// through the type during type construction, so that we can quickly check
 166     /// whether the type has various kinds of types in it without recursing
 167     /// over the type itself.
 168     pub struct TypeFlags: u32 {
 169         // Does this have parameters? Used to determine whether substitution is
 170         // required.
 171         /// Does this have `Param`?
 172         const HAS_TY_PARAM                = 1 << 0;
 173         /// Does this have `ReEarlyBound`?
 174         const HAS_RE_PARAM                = 1 << 1;
 175         /// Does this have `ConstKind::Param`?
 176         const HAS_CT_PARAM                = 1 << 2;
 177
 178         const NEEDS_SUBST                 = TypeFlags::HAS_TY_PARAM.bits
 179                                           | TypeFlags::HAS_RE_PARAM.bits
 180                                           | TypeFlags::HAS_CT_PARAM.bits;
 181
 182         /// Does this have `Infer`?
 183         const HAS_TY_INFER                = 1 << 3;
 184         /// Does this have `ReVar`?
 185         const HAS_RE_INFER                = 1 << 4;
 186         /// Does this have `ConstKind::Infer`?
 187         const HAS_CT_INFER                = 1 << 5;
 188
 189         /// Does this have inference variables? Used to determine whether
 190         /// inference is required.
 191         const NEEDS_INFER                 = TypeFlags::HAS_TY_INFER.bits
 192                                           | TypeFlags::HAS_RE_INFER.bits
 193                                           | TypeFlags::HAS_CT_INFER.bits;
 194
 195         /// Does this have `Placeholder`?
 196         const HAS_TY_PLACEHOLDER          = 1 << 6;
 197         /// Does this have `RePlaceholder`?
 198         const HAS_RE_PLACEHOLDER          = 1 << 7;
 199         /// Does this have `ConstKind::Placeholder`?
 200         const HAS_CT_PLACEHOLDER          = 1 << 8;
 201
 202         /// `true` if there are "names" of regions and so forth
 203         /// that are local to a particular fn/inferctxt
 204         const HAS_FREE_LOCAL_REGIONS      = 1 << 9;
 205
 206         /// `true` if there are "names" of types and regions and so forth
 207         /// that are local to a particular fn
 208         const HAS_FREE_LOCAL_NAMES        = TypeFlags::HAS_TY_PARAM.bits
 209                                           | TypeFlags::HAS_CT_PARAM.bits
 210                                           | TypeFlags::HAS_TY_INFER.bits
 211                                           | TypeFlags::HAS_CT_INFER.bits
 212                                           | TypeFlags::HAS_TY_PLACEHOLDER.bits
 213                                           | TypeFlags::HAS_CT_PLACEHOLDER.bits
 214                                           // We consider 'freshened' types and constants
 215                                           // to depend on a particular fn.
 216                                           // The freshening process throws away information,
 217                                           // which can make things unsuitable for use in a global
 218                                           // cache. Note that there is no 'fresh lifetime' flag -
 219                                           // freshening replaces all lifetimes with `ReErased`,
 220                                           // which is different from how types/const are freshened.
 221                                           | TypeFlags::HAS_TY_FRESH.bits
 222                                           | TypeFlags::HAS_CT_FRESH.bits
 223                                           | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits
 224                                           | TypeFlags::HAS_RE_ERASED.bits;
 225
 226         /// Does this have `Projection`?
 227         const HAS_TY_PROJECTION           = 1 << 10;
 228         /// Does this have `Opaque`?
 229         const HAS_TY_OPAQUE               = 1 << 11;
 230         /// Does this have `ConstKind::Unevaluated`?
 231         const HAS_CT_PROJECTION           = 1 << 12;
 232
 233         /// Could this type be normalized further?
 234         const HAS_PROJECTION              = TypeFlags::HAS_TY_PROJECTION.bits
 235                                           | TypeFlags::HAS_TY_OPAQUE.bits
 236                                           | TypeFlags::HAS_CT_PROJECTION.bits;
 237
 238         /// Is an error type/const reachable?
 239         const HAS_ERROR                   = 1 << 13;
 240
 241         /// Does this have any region that "appears free" in the type?
 242         /// Basically anything but `ReLateBound` and `ReErased`.
 243         const HAS_FREE_REGIONS            = 1 << 14;
 244
 245         /// Does this have any `ReLateBound` regions?
 246         const HAS_RE_LATE_BOUND           = 1 << 15;
 247         /// Does this have any `Bound` types?
 248         const HAS_TY_LATE_BOUND           = 1 << 16;
 249         /// Does this have any `ConstKind::Bound` consts?
 250         const HAS_CT_LATE_BOUND           = 1 << 17;
 251         /// Does this have any bound variables?
 252         /// Used to check if a global bound is safe to evaluate.
 253         const HAS_LATE_BOUND              = TypeFlags::HAS_RE_LATE_BOUND.bits
 254                                           | TypeFlags::HAS_TY_LATE_BOUND.bits
 255                                           | TypeFlags::HAS_CT_LATE_BOUND.bits;
 256
 257         /// Does this have any `ReErased` regions?
 258         const HAS_RE_ERASED               = 1 << 18;
 259
 260         /// Does this value have parameters/placeholders/inference variables which could be
 261         /// replaced later, in a way that would change the results of `impl` specialization?
 262         const STILL_FURTHER_SPECIALIZABLE = 1 << 19;
 263
 264         /// Does this value have `InferTy::FreshTy/FreshIntTy/FreshFloatTy`?
 265         const HAS_TY_FRESH                = 1 << 20;
 266
 267         /// Does this value have `InferConst::Fresh`?
 268         const HAS_CT_FRESH                = 1 << 21;
 269
 270         /// Does this have `Generator` or `GeneratorWitness`?
 271         const HAS_TY_GENERATOR            = 1 << 22;
 272     }
 273 }
 274
 275 rustc_index::newtype_index! {
 276     /// A [De Bruijn index][dbi] is a standard means of representing
 277     /// regions (and perhaps later types) in a higher-ranked setting. In
 278     /// particular, imagine a type like this:
 279     /// ```ignore (illustrative)
 280     ///    for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
 281     /// // ^          ^            |          |           |
 282     /// // |          |            |          |           |
 283     /// // |          +------------+ 0        |           |
 284     /// // |                                  |           |
 285     /// // +----------------------------------+ 1         |
 286     /// // |                                              |
 287     /// // +----------------------------------------------+ 0
 288     /// ```
 289     /// In this type, there are two binders (the outer fn and the inner
 290     /// fn). We need to be able to determine, for any given region, which
 291     /// fn type it is bound by, the inner or the outer one. There are
 292     /// various ways you can do this, but a De Bruijn index is one of the
 293     /// more convenient and has some nice properties. The basic idea is to
 294     /// count the number of binders, inside out. Some examples should help
 295     /// clarify what I mean.
 296     ///
 297     /// Let's start with the reference type `&'b isize` that is the first
 298     /// argument to the inner function. This region `'b` is assigned a De
 299     /// Bruijn index of 0, meaning "the innermost binder" (in this case, a
 300     /// fn). The region `'a` that appears in the second argument type (`&'a
 301     /// isize`) would then be assigned a De Bruijn index of 1, meaning "the
 302     /// second-innermost binder". (These indices are written on the arrows
 303     /// in the diagram).
 304     ///
 305     /// What is interesting is that De Bruijn index attached to a particular
 306     /// variable will vary depending on where it appears. For example,
 307     /// the final type `&'a char` also refers to the region `'a` declared on
 308     /// the outermost fn. But this time, this reference is not nested within
 309     /// any other binders (i.e., it is not an argument to the inner fn, but
 310     /// rather the outer one). Therefore, in this case, it is assigned a
 311     /// De Bruijn index of 0, because the innermost binder in that location
 312     /// is the outer fn.
 313     ///
 314     /// [dbi]: https://en.wikipedia.org/wiki/De_Bruijn_index
 315     #[derive(HashStable_Generic)]
 316     #[debug_format = "DebruijnIndex({})"]
 317     pub struct DebruijnIndex {
 318         const INNERMOST = 0;
 319     }
 320 }
 321
 322 impl DebruijnIndex {
 323     /// Returns the resulting index when this value is moved into
 324     /// `amount` number of new binders. So, e.g., if you had
 325     ///
 326     ///    for<'a> fn(&'a x)
 327     ///
 328     /// and you wanted to change it to
 329     ///
 330     ///    for<'a> fn(for<'b> fn(&'a x))
 331     ///
 332     /// you would need to shift the index for `'a` into a new binder.
 333     #[inline]
 334     #[must_use]
 335     pub fn shifted_in(self, amount: u32) -> DebruijnIndex {
 336         DebruijnIndex::from_u32(self.as_u32() + amount)
 337     }
 338
 339     /// Update this index in place by shifting it "in" through
 340     /// `amount` number of binders.
 341     #[inline]
 342     pub fn shift_in(&mut self, amount: u32) {
 343         *self = self.shifted_in(amount);
 344     }
 345
 346     /// Returns the resulting index when this value is moved out from
 347     /// `amount` number of new binders.
 348     #[inline]
 349     #[must_use]
 350     pub fn shifted_out(self, amount: u32) -> DebruijnIndex {
 351         DebruijnIndex::from_u32(self.as_u32() - amount)
 352     }
 353
 354     /// Update in place by shifting out from `amount` binders.
 355     #[inline]
 356     pub fn shift_out(&mut self, amount: u32) {
 357         *self = self.shifted_out(amount);
 358     }
 359
 360     /// Adjusts any De Bruijn indices so as to make `to_binder` the
 361     /// innermost binder. That is, if we have something bound at `to_binder`,
 362     /// it will now be bound at INNERMOST. This is an appropriate thing to do
 363     /// when moving a region out from inside binders:
 364     ///
 365     /// ```ignore (illustrative)
 366     ///             for<'a>   fn(for<'b>   for<'c>   fn(&'a u32), _)
 367     /// // Binder:  D3           D2        D1            ^^
 368     /// ```
 369     ///
 370     /// Here, the region `'a` would have the De Bruijn index D3,
 371     /// because it is the bound 3 binders out. However, if we wanted
 372     /// to refer to that region `'a` in the second argument (the `_`),
 373     /// those two binders would not be in scope. In that case, we
 374     /// might invoke `shift_out_to_binder(D3)`. This would adjust the
 375     /// De Bruijn index of `'a` to D1 (the innermost binder).
 376     ///
 377     /// If we invoke `shift_out_to_binder` and the region is in fact
 378     /// bound by one of the binders we are shifting out of, that is an
 379     /// error (and should fail an assertion failure).
 380     #[inline]
 381     pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self {
 382         self.shifted_out(to_binder.as_u32() - INNERMOST.as_u32())
 383     }
 384 }
 385
 386 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 387 #[derive(Encodable, Decodable, HashStable_Generic)]
 388 pub enum IntTy {
 389     Isize,
 390     I8,
 391     I16,
 392     I32,
 393     I64,
 394     I128,
 395 }
 396
 397 impl IntTy {
 398     pub fn name_str(&self) -> &'static str {
 399         match *self {
 400             IntTy::Isize => "isize",
 401             IntTy::I8 => "i8",
 402             IntTy::I16 => "i16",
 403             IntTy::I32 => "i32",
 404             IntTy::I64 => "i64",
 405             IntTy::I128 => "i128",
 406         }
 407     }
 408
 409     pub fn bit_width(&self) -> Option<u64> {
 410         Some(match *self {
 411             IntTy::Isize => return None,
 412             IntTy::I8 => 8,
 413             IntTy::I16 => 16,
 414             IntTy::I32 => 32,
 415             IntTy::I64 => 64,
 416             IntTy::I128 => 128,
 417         })
 418     }
 419
 420     pub fn normalize(&self, target_width: u32) -> Self {
 421         match self {
 422             IntTy::Isize => match target_width {
 423                 16 => IntTy::I16,
 424                 32 => IntTy::I32,
 425                 64 => IntTy::I64,
 426                 _ => unreachable!(),
 427             },
 428             _ => *self,
 429         }
 430     }
 431 }
 432
 433 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Debug)]
 434 #[derive(Encodable, Decodable, HashStable_Generic)]
 435 pub enum UintTy {
 436     Usize,
 437     U8,
 438     U16,
 439     U32,
 440     U64,
 441     U128,
 442 }
 443
 444 impl UintTy {
 445     pub fn name_str(&self) -> &'static str {
 446         match *self {
 447             UintTy::Usize => "usize",
 448             UintTy::U8 => "u8",
 449             UintTy::U16 => "u16",
 450             UintTy::U32 => "u32",
 451             UintTy::U64 => "u64",
 452             UintTy::U128 => "u128",
 453         }
 454     }
 455
 456     pub fn bit_width(&self) -> Option<u64> {
 457         Some(match *self {
 458             UintTy::Usize => return None,
 459             UintTy::U8 => 8,
 460             UintTy::U16 => 16,
 461             UintTy::U32 => 32,
 462             UintTy::U64 => 64,
 463             UintTy::U128 => 128,
 464         })
 465     }
 466
 467     pub fn normalize(&self, target_width: u32) -> Self {
 468         match self {
 469             UintTy::Usize => match target_width {
 470                 16 => UintTy::U16,
 471                 32 => UintTy::U32,
 472                 64 => UintTy::U64,
 473                 _ => unreachable!(),
 474             },
 475             _ => *self,
 476         }
 477     }
 478 }
 479
 480 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 481 #[derive(Encodable, Decodable, HashStable_Generic)]
 482 pub enum FloatTy {
 483     F32,
 484     F64,
 485 }
 486
 487 impl FloatTy {
 488     pub fn name_str(self) -> &'static str {
 489         match self {
 490             FloatTy::F32 => "f32",
 491             FloatTy::F64 => "f64",
 492         }
 493     }
 494
 495     pub fn bit_width(self) -> u64 {
 496         match self {
 497             FloatTy::F32 => 32,
 498             FloatTy::F64 => 64,
 499         }
 500     }
 501 }
 502
 503 #[derive(Clone, Copy, PartialEq, Eq)]
 504 pub enum IntVarValue {
 505     IntType(IntTy),
 506     UintType(UintTy),
 507 }
 508
 509 #[derive(Clone, Copy, PartialEq, Eq)]
 510 pub struct FloatVarValue(pub FloatTy);
 511
 512 rustc_index::newtype_index! {
 513     /// A **ty**pe **v**ariable **ID**.
 514     #[debug_format = "_#{}t"]
 515     pub struct TyVid {}
 516 }
 517
 518 /// An **int**egral (`u32`, `i32`, `usize`, etc.) type **v**ariable **ID**.
 519 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
 520 pub struct IntVid {
 521     pub index: u32,
 522 }
 523
 524 /// An **float**ing-point (`f32` or `f64`) type **v**ariable **ID**.
 525 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
 526 pub struct FloatVid {
 527     pub index: u32,
 528 }
 529
 530 /// A placeholder for a type that hasn't been inferred yet.
 531 ///
 532 /// E.g., if we have an empty array (`[]`), then we create a fresh
 533 /// type variable for the element type since we won't know until it's
 534 /// used what the element type is supposed to be.
 535 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
 536 pub enum InferTy {
 537     /// A type variable.
 538     TyVar(TyVid),
 539     /// An integral type variable (`{integer}`).
 540     ///
 541     /// These are created when the compiler sees an integer literal like
 542     /// `1` that could be several different types (`u8`, `i32`, `u32`, etc.).
 543     /// We don't know until it's used what type it's supposed to be, so
 544     /// we create a fresh type variable.
 545     IntVar(IntVid),
 546     /// A floating-point type variable (`{float}`).
 547     ///
 548     /// These are created when the compiler sees an float literal like
 549     /// `1.0` that could be either an `f32` or an `f64`.
 550     /// We don't know until it's used what type it's supposed to be, so
 551     /// we create a fresh type variable.
 552     FloatVar(FloatVid),
 553
 554     /// A [`FreshTy`][Self::FreshTy] is one that is generated as a replacement
 555     /// for an unbound type variable. This is convenient for caching etc. See
 556     /// `rustc_infer::infer::freshen` for more details.
 557     ///
 558     /// Compare with [`TyVar`][Self::TyVar].
 559     FreshTy(u32),
 560     /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`IntVar`][Self::IntVar].
 561     FreshIntTy(u32),
 562     /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`FloatVar`][Self::FloatVar].
 563     FreshFloatTy(u32),
 564 }
 565
 566 /// Raw `TyVid` are used as the unification key for `sub_relations`;
 567 /// they carry no values.
 568 impl UnifyKey for TyVid {
 569     type Value = ();
 570     #[inline]
 571     fn index(&self) -> u32 {
 572         self.as_u32()
 573     }
 574     #[inline]
 575     fn from_index(i: u32) -> TyVid {
 576         TyVid::from_u32(i)
 577     }
 578     fn tag() -> &'static str {
 579         "TyVid"
 580     }
 581 }
 582
 583 impl EqUnifyValue for IntVarValue {}
 584
 585 impl UnifyKey for IntVid {
 586     type Value = Option<IntVarValue>;
 587     #[inline] // make this function eligible for inlining - it is quite hot.
 588     fn index(&self) -> u32 {
 589         self.index
 590     }
 591     #[inline]
 592     fn from_index(i: u32) -> IntVid {
 593         IntVid { index: i }
 594     }
 595     fn tag() -> &'static str {
 596         "IntVid"
 597     }
 598 }
 599
 600 impl EqUnifyValue for FloatVarValue {}
 601
 602 impl UnifyKey for FloatVid {
 603     type Value = Option<FloatVarValue>;
 604     #[inline]
 605     fn index(&self) -> u32 {
 606         self.index
 607     }
 608     #[inline]
 609     fn from_index(i: u32) -> FloatVid {
 610         FloatVid { index: i }
 611     }
 612     fn tag() -> &'static str {
 613         "FloatVid"
 614     }
 615 }
 616
 617 #[derive(Copy, Clone, PartialEq, Decodable, Encodable, Hash, HashStable_Generic)]
 618 #[rustc_pass_by_value]
 619 pub enum Variance {
 620     Covariant,     // T<A> <: T<B> iff A <: B -- e.g., function return type
 621     Invariant,     // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
 622     Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
 623     Bivariant,     // T<A> <: T<B>            -- e.g., unused type parameter
 624 }
 625
 626 impl Variance {
 627     /// `a.xform(b)` combines the variance of a context with the
 628     /// variance of a type with the following meaning. If we are in a
 629     /// context with variance `a`, and we encounter a type argument in
 630     /// a position with variance `b`, then `a.xform(b)` is the new
 631     /// variance with which the argument appears.
 632     ///
 633     /// Example 1:
 634     /// ```ignore (illustrative)
 635     /// *mut Vec<i32>
 636     /// ```
 637     /// Here, the "ambient" variance starts as covariant. `*mut T` is
 638     /// invariant with respect to `T`, so the variance in which the
 639     /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which
 640     /// yields `Invariant`. Now, the type `Vec<T>` is covariant with
 641     /// respect to its type argument `T`, and hence the variance of
 642     /// the `i32` here is `Invariant.xform(Covariant)`, which results
 643     /// (again) in `Invariant`.
 644     ///
 645     /// Example 2:
 646     /// ```ignore (illustrative)
 647     /// fn(*const Vec<i32>, *mut Vec<i32)
 648     /// ```
 649     /// The ambient variance is covariant. A `fn` type is
 650     /// contravariant with respect to its parameters, so the variance
 651     /// within which both pointer types appear is
 652     /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const
 653     /// T` is covariant with respect to `T`, so the variance within
 654     /// which the first `Vec<i32>` appears is
 655     /// `Contravariant.xform(Covariant)` or `Contravariant`. The same
 656     /// is true for its `i32` argument. In the `*mut T` case, the
 657     /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`,
 658     /// and hence the outermost type is `Invariant` with respect to
 659     /// `Vec<i32>` (and its `i32` argument).
 660     ///
 661     /// Source: Figure 1 of "Taming the Wildcards:
 662     /// Combining Definition- and Use-Site Variance" published in PLDI'11.
 663     pub fn xform(self, v: Variance) -> Variance {
 664         match (self, v) {
 665             // Figure 1, column 1.
 666             (Variance::Covariant, Variance::Covariant) => Variance::Covariant,
 667             (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant,
 668             (Variance::Covariant, Variance::Invariant) => Variance::Invariant,
 669             (Variance::Covariant, Variance::Bivariant) => Variance::Bivariant,
 670
 671             // Figure 1, column 2.
 672             (Variance::Contravariant, Variance::Covariant) => Variance::Contravariant,
 673             (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant,
 674             (Variance::Contravariant, Variance::Invariant) => Variance::Invariant,
 675             (Variance::Contravariant, Variance::Bivariant) => Variance::Bivariant,
 676
 677             // Figure 1, column 3.
 678             (Variance::Invariant, _) => Variance::Invariant,
 679
 680             // Figure 1, column 4.
 681             (Variance::Bivariant, _) => Variance::Bivariant,
 682         }
 683     }
 684 }
 685
 686 impl<CTX> HashStable<CTX> for InferTy {
 687     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 688         use InferTy::*;
 689         discriminant(self).hash_stable(ctx, hasher);
 690         match self {
 691             TyVar(_) | IntVar(_) | FloatVar(_) => {
 692                 panic!("type variables should not be hashed: {self:?}")
 693             }
 694             FreshTy(v) | FreshIntTy(v) | FreshFloatTy(v) => v.hash_stable(ctx, hasher),
 695         }
 696     }
 697 }
 698
 699 impl fmt::Debug for IntVarValue {
 700     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 701         match *self {
 702             IntVarValue::IntType(ref v) => v.fmt(f),
 703             IntVarValue::UintType(ref v) => v.fmt(f),
 704         }
 705     }
 706 }
 707
 708 impl fmt::Debug for FloatVarValue {
 709     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 710         self.0.fmt(f)
 711     }
 712 }
 713
 714 impl fmt::Debug for IntVid {
 715     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 716         write!(f, "_#{}i", self.index)
 717     }
 718 }
 719
 720 impl fmt::Debug for FloatVid {
 721     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 722         write!(f, "_#{}f", self.index)
 723     }
 724 }
 725
 726 impl fmt::Debug for InferTy {
 727     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 728         use InferTy::*;
 729         match *self {
 730             TyVar(ref v) => v.fmt(f),
 731             IntVar(ref v) => v.fmt(f),
 732             FloatVar(ref v) => v.fmt(f),
 733             FreshTy(v) => write!(f, "FreshTy({v:?})"),
 734             FreshIntTy(v) => write!(f, "FreshIntTy({v:?})"),
 735             FreshFloatTy(v) => write!(f, "FreshFloatTy({v:?})"),
 736         }
 737     }
 738 }
 739
 740 impl fmt::Debug for Variance {
 741     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 742         f.write_str(match *self {
 743             Variance::Covariant => "+",
 744             Variance::Contravariant => "-",
 745             Variance::Invariant => "o",
 746             Variance::Bivariant => "*",
 747         })
 748     }
 749 }
 750
 751 impl fmt::Display for InferTy {
 752     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 753         use InferTy::*;
 754         match *self {
 755             TyVar(_) => write!(f, "_"),
 756             IntVar(_) => write!(f, "{}", "{integer}"),
 757             FloatVar(_) => write!(f, "{}", "{float}"),
 758             FreshTy(v) => write!(f, "FreshTy({v})"),
 759             FreshIntTy(v) => write!(f, "FreshIntTy({v})"),
 760             FreshFloatTy(v) => write!(f, "FreshFloatTy({v})"),
 761         }
 762     }
 763 }
 764
 765 rustc_index::newtype_index! {
 766     /// "Universes" are used during type- and trait-checking in the
 767     /// presence of `for<..>` binders to control what sets of names are
 768     /// visible. Universes are arranged into a tree: the root universe
 769     /// contains names that are always visible. Each child then adds a new
 770     /// set of names that are visible, in addition to those of its parent.
 771     /// We say that the child universe "extends" the parent universe with
 772     /// new names.
 773     ///
 774     /// To make this more concrete, consider this program:
 775     ///
 776     /// ```ignore (illustrative)
 777     /// struct Foo { }
 778     /// fn bar<T>(x: T) {
 779     ///   let y: for<'a> fn(&'a u8, Foo) = ...;
 780     /// }
 781     /// ```
 782     ///
 783     /// The struct name `Foo` is in the root universe U0. But the type
 784     /// parameter `T`, introduced on `bar`, is in an extended universe U1
 785     /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside
 786     /// of `bar`, we cannot name `T`. Then, within the type of `y`, the
 787     /// region `'a` is in a universe U2 that extends U1, because we can
 788     /// name it inside the fn type but not outside.
 789     ///
 790     /// Universes are used to do type- and trait-checking around these
 791     /// "forall" binders (also called **universal quantification**). The
 792     /// idea is that when, in the body of `bar`, we refer to `T` as a
 793     /// type, we aren't referring to any type in particular, but rather a
 794     /// kind of "fresh" type that is distinct from all other types we have
 795     /// actually declared. This is called a **placeholder** type, and we
 796     /// use universes to talk about this. In other words, a type name in
 797     /// universe 0 always corresponds to some "ground" type that the user
 798     /// declared, but a type name in a non-zero universe is a placeholder
 799     /// type -- an idealized representative of "types in general" that we
 800     /// use for checking generic functions.
 801     #[derive(HashStable_Generic)]
 802     #[debug_format = "U{}"]
 803     pub struct UniverseIndex {}
 804 }
 805
 806 impl UniverseIndex {
 807     pub const ROOT: UniverseIndex = UniverseIndex::from_u32(0);
 808
 809     /// Returns the "next" universe index in order -- this new index
 810     /// is considered to extend all previous universes. This
 811     /// corresponds to entering a `forall` quantifier. So, for
 812     /// example, suppose we have this type in universe `U`:
 813     ///
 814     /// ```ignore (illustrative)
 815     /// for<'a> fn(&'a u32)
 816     /// ```
 817     ///
 818     /// Once we "enter" into this `for<'a>` quantifier, we are in a
 819     /// new universe that extends `U` -- in this new universe, we can
 820     /// name the region `'a`, but that region was not nameable from
 821     /// `U` because it was not in scope there.
 822     pub fn next_universe(self) -> UniverseIndex {
 823         UniverseIndex::from_u32(self.private.checked_add(1).unwrap())
 824     }
 825
 826     /// Returns `true` if `self` can name a name from `other` -- in other words,
 827     /// if the set of names in `self` is a superset of those in
 828     /// `other` (`self >= other`).
 829     pub fn can_name(self, other: UniverseIndex) -> bool {
 830         self.private >= other.private
 831     }
 832
 833     /// Returns `true` if `self` cannot name some names from `other` -- in other
 834     /// words, if the set of names in `self` is a strict subset of
 835     /// those in `other` (`self < other`).
 836     pub fn cannot_name(self, other: UniverseIndex) -> bool {
 837         self.private < other.private
 838     }
 839 }