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