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