compiler/rustc_type_ir/src/lib.rs

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