diff options
Diffstat (limited to 'compiler/rustc_type_ir/src/lib.rs')
| -rw-r--r-- | compiler/rustc_type_ir/src/lib.rs | 856 |
1 files changed, 856 insertions, 0 deletions
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs new file mode 100644 index 000000000..791e9e0f5 --- /dev/null +++ b/compiler/rustc_type_ir/src/lib.rs @@ -0,0 +1,856 @@ +#![feature(fmt_helpers_for_derive)] +#![feature(min_specialization)] +#![feature(rustc_attrs)] + +#[macro_use] +extern crate bitflags; +#[macro_use] +extern crate rustc_macros; + +use rustc_data_structures::stable_hasher::{HashStable, StableHasher}; +use rustc_data_structures::unify::{EqUnifyValue, UnifyKey}; +use smallvec::SmallVec; +use std::fmt; +use std::fmt::Debug; +use std::hash::Hash; +use std::mem::discriminant; + +pub mod codec; +pub mod sty; + +pub use codec::*; +pub use sty::*; + +pub trait Interner { + type AdtDef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type SubstsRef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type DefId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type Ty: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type Const: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type Region: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type TypeAndMut: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type Mutability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type Movability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type PolyFnSig: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type ListBinderExistentialPredicate: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type BinderListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type ListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type ProjectionTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type ParamTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type BoundTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type PlaceholderType: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type InferTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type DelaySpanBugEmitted: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type PredicateKind: Clone + Debug + Hash + PartialEq + Eq; + type AllocId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + + type EarlyBoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type BoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type FreeRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type RegionVid: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; + type PlaceholderRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; +} + +pub trait InternAs<T: ?Sized, R> { + type Output; + fn intern_with<F>(self, f: F) -> Self::Output + where + F: FnOnce(&T) -> R; +} + +impl<I, T, R, E> InternAs<[T], R> for I +where + E: InternIteratorElement<T, R>, + I: Iterator<Item = E>, +{ + type Output = E::Output; + fn intern_with<F>(self, f: F) -> Self::Output + where + F: FnOnce(&[T]) -> R, + { + E::intern_with(self, f) + } +} + +pub trait InternIteratorElement<T, R>: Sized { + type Output; + fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output; +} + +impl<T, R> InternIteratorElement<T, R> for T { + type Output = R; + fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>( + mut iter: I, + f: F, + ) -> Self::Output { + // This code is hot enough that it's worth specializing for the most + // common length lists, to avoid the overhead of `SmallVec` creation. + // Lengths 0, 1, and 2 typically account for ~95% of cases. If + // `size_hint` is incorrect a panic will occur via an `unwrap` or an + // `assert`. + match iter.size_hint() { + (0, Some(0)) => { + assert!(iter.next().is_none()); + f(&[]) + } + (1, Some(1)) => { + let t0 = iter.next().unwrap(); + assert!(iter.next().is_none()); + f(&[t0]) + } + (2, Some(2)) => { + let t0 = iter.next().unwrap(); + let t1 = iter.next().unwrap(); + assert!(iter.next().is_none()); + f(&[t0, t1]) + } + _ => f(&iter.collect::<SmallVec<[_; 8]>>()), + } + } +} + +impl<'a, T, R> InternIteratorElement<T, R> for &'a T +where + T: Clone + 'a, +{ + type Output = R; + fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output { + // This code isn't hot. + f(&iter.cloned().collect::<SmallVec<[_; 8]>>()) + } +} + +impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> { + type Output = Result<R, E>; + fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>( + mut iter: I, + f: F, + ) -> Self::Output { + // This code is hot enough that it's worth specializing for the most + // common length lists, to avoid the overhead of `SmallVec` creation. + // Lengths 0, 1, and 2 typically account for ~95% of cases. If + // `size_hint` is incorrect a panic will occur via an `unwrap` or an + // `assert`, unless a failure happens first, in which case the result + // will be an error anyway. + Ok(match iter.size_hint() { + (0, Some(0)) => { + assert!(iter.next().is_none()); + f(&[]) + } + (1, Some(1)) => { + let t0 = iter.next().unwrap()?; + assert!(iter.next().is_none()); + f(&[t0]) + } + (2, Some(2)) => { + let t0 = iter.next().unwrap()?; + let t1 = iter.next().unwrap()?; + assert!(iter.next().is_none()); + f(&[t0, t1]) + } + _ => f(&iter.collect::<Result<SmallVec<[_; 8]>, _>>()?), + }) + } +} + +bitflags! { + /// Flags that we track on types. These flags are propagated upwards + /// through the type during type construction, so that we can quickly check + /// whether the type has various kinds of types in it without recursing + /// over the type itself. + pub struct TypeFlags: u32 { + // Does this have parameters? Used to determine whether substitution is + // required. + /// Does this have `Param`? + const HAS_TY_PARAM = 1 << 0; + /// Does this have `ReEarlyBound`? + const HAS_RE_PARAM = 1 << 1; + /// Does this have `ConstKind::Param`? + const HAS_CT_PARAM = 1 << 2; + + const NEEDS_SUBST = TypeFlags::HAS_TY_PARAM.bits + | TypeFlags::HAS_RE_PARAM.bits + | TypeFlags::HAS_CT_PARAM.bits; + + /// Does this have `Infer`? + const HAS_TY_INFER = 1 << 3; + /// Does this have `ReVar`? + const HAS_RE_INFER = 1 << 4; + /// Does this have `ConstKind::Infer`? + const HAS_CT_INFER = 1 << 5; + + /// Does this have inference variables? Used to determine whether + /// inference is required. + const NEEDS_INFER = TypeFlags::HAS_TY_INFER.bits + | TypeFlags::HAS_RE_INFER.bits + | TypeFlags::HAS_CT_INFER.bits; + + /// Does this have `Placeholder`? + const HAS_TY_PLACEHOLDER = 1 << 6; + /// Does this have `RePlaceholder`? + const HAS_RE_PLACEHOLDER = 1 << 7; + /// Does this have `ConstKind::Placeholder`? + const HAS_CT_PLACEHOLDER = 1 << 8; + + /// `true` if there are "names" of regions and so forth + /// that are local to a particular fn/inferctxt + const HAS_FREE_LOCAL_REGIONS = 1 << 9; + + /// `true` if there are "names" of types and regions and so forth + /// that are local to a particular fn + const HAS_FREE_LOCAL_NAMES = TypeFlags::HAS_TY_PARAM.bits + | TypeFlags::HAS_CT_PARAM.bits + | TypeFlags::HAS_TY_INFER.bits + | TypeFlags::HAS_CT_INFER.bits + | TypeFlags::HAS_TY_PLACEHOLDER.bits + | TypeFlags::HAS_CT_PLACEHOLDER.bits + // We consider 'freshened' types and constants + // to depend on a particular fn. + // The freshening process throws away information, + // which can make things unsuitable for use in a global + // cache. Note that there is no 'fresh lifetime' flag - + // freshening replaces all lifetimes with `ReErased`, + // which is different from how types/const are freshened. + | TypeFlags::HAS_TY_FRESH.bits + | TypeFlags::HAS_CT_FRESH.bits + | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits; + + /// Does this have `Projection`? + const HAS_TY_PROJECTION = 1 << 10; + /// Does this have `Opaque`? + const HAS_TY_OPAQUE = 1 << 11; + /// Does this have `ConstKind::Unevaluated`? + const HAS_CT_PROJECTION = 1 << 12; + + /// Could this type be normalized further? + const HAS_PROJECTION = TypeFlags::HAS_TY_PROJECTION.bits + | TypeFlags::HAS_TY_OPAQUE.bits + | TypeFlags::HAS_CT_PROJECTION.bits; + + /// Is an error type/const reachable? + const HAS_ERROR = 1 << 13; + + /// Does this have any region that "appears free" in the type? + /// Basically anything but `ReLateBound` and `ReErased`. + const HAS_FREE_REGIONS = 1 << 14; + + /// Does this have any `ReLateBound` regions? Used to check + /// if a global bound is safe to evaluate. + const HAS_RE_LATE_BOUND = 1 << 15; + + /// Does this have any `ReErased` regions? + const HAS_RE_ERASED = 1 << 16; + + /// Does this value have parameters/placeholders/inference variables which could be + /// replaced later, in a way that would change the results of `impl` specialization? + const STILL_FURTHER_SPECIALIZABLE = 1 << 17; + + /// Does this value have `InferTy::FreshTy/FreshIntTy/FreshFloatTy`? + const HAS_TY_FRESH = 1 << 18; + + /// Does this value have `InferConst::Fresh`? + const HAS_CT_FRESH = 1 << 19; + } +} + +rustc_index::newtype_index! { + /// A [De Bruijn index][dbi] is a standard means of representing + /// regions (and perhaps later types) in a higher-ranked setting. In + /// particular, imagine a type like this: + /// ```ignore (illustrative) + /// for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char) + /// // ^ ^ | | | + /// // | | | | | + /// // | +------------+ 0 | | + /// // | | | + /// // +----------------------------------+ 1 | + /// // | | + /// // +----------------------------------------------+ 0 + /// ``` + /// In this type, there are two binders (the outer fn and the inner + /// fn). We need to be able to determine, for any given region, which + /// fn type it is bound by, the inner or the outer one. There are + /// various ways you can do this, but a De Bruijn index is one of the + /// more convenient and has some nice properties. The basic idea is to + /// count the number of binders, inside out. Some examples should help + /// clarify what I mean. + /// + /// Let's start with the reference type `&'b isize` that is the first + /// argument to the inner function. This region `'b` is assigned a De + /// Bruijn index of 0, meaning "the innermost binder" (in this case, a + /// fn). The region `'a` that appears in the second argument type (`&'a + /// isize`) would then be assigned a De Bruijn index of 1, meaning "the + /// second-innermost binder". (These indices are written on the arrows + /// in the diagram). + /// + /// What is interesting is that De Bruijn index attached to a particular + /// variable will vary depending on where it appears. For example, + /// the final type `&'a char` also refers to the region `'a` declared on + /// the outermost fn. But this time, this reference is not nested within + /// any other binders (i.e., it is not an argument to the inner fn, but + /// rather the outer one). Therefore, in this case, it is assigned a + /// De Bruijn index of 0, because the innermost binder in that location + /// is the outer fn. + /// + /// [dbi]: https://en.wikipedia.org/wiki/De_Bruijn_index + pub struct DebruijnIndex { + DEBUG_FORMAT = "DebruijnIndex({})", + const INNERMOST = 0, + } +} + +impl DebruijnIndex { + /// Returns the resulting index when this value is moved into + /// `amount` number of new binders. So, e.g., if you had + /// + /// for<'a> fn(&'a x) + /// + /// and you wanted to change it to + /// + /// for<'a> fn(for<'b> fn(&'a x)) + /// + /// you would need to shift the index for `'a` into a new binder. + #[inline] + #[must_use] + pub fn shifted_in(self, amount: u32) -> DebruijnIndex { + DebruijnIndex::from_u32(self.as_u32() + amount) + } + + /// Update this index in place by shifting it "in" through + /// `amount` number of binders. + #[inline] + pub fn shift_in(&mut self, amount: u32) { + *self = self.shifted_in(amount); + } + + /// Returns the resulting index when this value is moved out from + /// `amount` number of new binders. + #[inline] + #[must_use] + pub fn shifted_out(self, amount: u32) -> DebruijnIndex { + DebruijnIndex::from_u32(self.as_u32() - amount) + } + + /// Update in place by shifting out from `amount` binders. + #[inline] + pub fn shift_out(&mut self, amount: u32) { + *self = self.shifted_out(amount); + } + + /// Adjusts any De Bruijn indices so as to make `to_binder` the + /// innermost binder. That is, if we have something bound at `to_binder`, + /// it will now be bound at INNERMOST. This is an appropriate thing to do + /// when moving a region out from inside binders: + /// + /// ```ignore (illustrative) + /// for<'a> fn(for<'b> for<'c> fn(&'a u32), _) + /// // Binder: D3 D2 D1 ^^ + /// ``` + /// + /// Here, the region `'a` would have the De Bruijn index D3, + /// because it is the bound 3 binders out. However, if we wanted + /// to refer to that region `'a` in the second argument (the `_`), + /// those two binders would not be in scope. In that case, we + /// might invoke `shift_out_to_binder(D3)`. This would adjust the + /// De Bruijn index of `'a` to D1 (the innermost binder). + /// + /// If we invoke `shift_out_to_binder` and the region is in fact + /// bound by one of the binders we are shifting out of, that is an + /// error (and should fail an assertion failure). + #[inline] + pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self { + self.shifted_out(to_binder.as_u32() - INNERMOST.as_u32()) + } +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] +#[derive(Encodable, Decodable)] +pub enum IntTy { + Isize, + I8, + I16, + I32, + I64, + I128, +} + +impl IntTy { + pub fn name_str(&self) -> &'static str { + match *self { + IntTy::Isize => "isize", + IntTy::I8 => "i8", + IntTy::I16 => "i16", + IntTy::I32 => "i32", + IntTy::I64 => "i64", + IntTy::I128 => "i128", + } + } + + pub fn bit_width(&self) -> Option<u64> { + Some(match *self { + IntTy::Isize => return None, + IntTy::I8 => 8, + IntTy::I16 => 16, + IntTy::I32 => 32, + IntTy::I64 => 64, + IntTy::I128 => 128, + }) + } + + pub fn normalize(&self, target_width: u32) -> Self { + match self { + IntTy::Isize => match target_width { + 16 => IntTy::I16, + 32 => IntTy::I32, + 64 => IntTy::I64, + _ => unreachable!(), + }, + _ => *self, + } + } +} + +#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Debug)] +#[derive(Encodable, Decodable)] +pub enum UintTy { + Usize, + U8, + U16, + U32, + U64, + U128, +} + +impl UintTy { + pub fn name_str(&self) -> &'static str { + match *self { + UintTy::Usize => "usize", + UintTy::U8 => "u8", + UintTy::U16 => "u16", + UintTy::U32 => "u32", + UintTy::U64 => "u64", + UintTy::U128 => "u128", + } + } + + pub fn bit_width(&self) -> Option<u64> { + Some(match *self { + UintTy::Usize => return None, + UintTy::U8 => 8, + UintTy::U16 => 16, + UintTy::U32 => 32, + UintTy::U64 => 64, + UintTy::U128 => 128, + }) + } + + pub fn normalize(&self, target_width: u32) -> Self { + match self { + UintTy::Usize => match target_width { + 16 => UintTy::U16, + 32 => UintTy::U32, + 64 => UintTy::U64, + _ => unreachable!(), + }, + _ => *self, + } + } +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] +#[derive(Encodable, Decodable)] +pub enum FloatTy { + F32, + F64, +} + +impl FloatTy { + pub fn name_str(self) -> &'static str { + match self { + FloatTy::F32 => "f32", + FloatTy::F64 => "f64", + } + } + + pub fn bit_width(self) -> u64 { + match self { + FloatTy::F32 => 32, + FloatTy::F64 => 64, + } + } +} + +#[derive(Clone, Copy, PartialEq, Eq)] +pub enum IntVarValue { + IntType(IntTy), + UintType(UintTy), +} + +#[derive(Clone, Copy, PartialEq, Eq)] +pub struct FloatVarValue(pub FloatTy); + +rustc_index::newtype_index! { + /// A **ty**pe **v**ariable **ID**. + pub struct TyVid { + DEBUG_FORMAT = "_#{}t" + } +} + +/// An **int**egral (`u32`, `i32`, `usize`, etc.) type **v**ariable **ID**. +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)] +pub struct IntVid { + pub index: u32, +} + +/// An **float**ing-point (`f32` or `f64`) type **v**ariable **ID**. +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)] +pub struct FloatVid { + pub index: u32, +} + +/// A placeholder for a type that hasn't been inferred yet. +/// +/// E.g., if we have an empty array (`[]`), then we create a fresh +/// type variable for the element type since we won't know until it's +/// used what the element type is supposed to be. +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)] +pub enum InferTy { + /// A type variable. + TyVar(TyVid), + /// An integral type variable (`{integer}`). + /// + /// These are created when the compiler sees an integer literal like + /// `1` that could be several different types (`u8`, `i32`, `u32`, etc.). + /// We don't know until it's used what type it's supposed to be, so + /// we create a fresh type variable. + IntVar(IntVid), + /// A floating-point type variable (`{float}`). + /// + /// These are created when the compiler sees an float literal like + /// `1.0` that could be either an `f32` or an `f64`. + /// We don't know until it's used what type it's supposed to be, so + /// we create a fresh type variable. + FloatVar(FloatVid), + + /// A [`FreshTy`][Self::FreshTy] is one that is generated as a replacement + /// for an unbound type variable. This is convenient for caching etc. See + /// `rustc_infer::infer::freshen` for more details. + /// + /// Compare with [`TyVar`][Self::TyVar]. + FreshTy(u32), + /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`IntVar`][Self::IntVar]. + FreshIntTy(u32), + /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`FloatVar`][Self::FloatVar]. + FreshFloatTy(u32), +} + +/// Raw `TyVid` are used as the unification key for `sub_relations`; +/// they carry no values. +impl UnifyKey for TyVid { + type Value = (); + #[inline] + fn index(&self) -> u32 { + self.as_u32() + } + #[inline] + fn from_index(i: u32) -> TyVid { + TyVid::from_u32(i) + } + fn tag() -> &'static str { + "TyVid" + } +} + +impl EqUnifyValue for IntVarValue {} + +impl UnifyKey for IntVid { + type Value = Option<IntVarValue>; + #[inline] // make this function eligible for inlining - it is quite hot. + fn index(&self) -> u32 { + self.index + } + #[inline] + fn from_index(i: u32) -> IntVid { + IntVid { index: i } + } + fn tag() -> &'static str { + "IntVid" + } +} + +impl EqUnifyValue for FloatVarValue {} + +impl UnifyKey for FloatVid { + type Value = Option<FloatVarValue>; + #[inline] + fn index(&self) -> u32 { + self.index + } + #[inline] + fn from_index(i: u32) -> FloatVid { + FloatVid { index: i } + } + fn tag() -> &'static str { + "FloatVid" + } +} + +#[derive(Copy, Clone, PartialEq, Decodable, Encodable, Hash)] +#[rustc_pass_by_value] +pub enum Variance { + Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type + Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell + Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type + Bivariant, // T<A> <: T<B> -- e.g., unused type parameter +} + +impl Variance { + /// `a.xform(b)` combines the variance of a context with the + /// variance of a type with the following meaning. If we are in a + /// context with variance `a`, and we encounter a type argument in + /// a position with variance `b`, then `a.xform(b)` is the new + /// variance with which the argument appears. + /// + /// Example 1: + /// ```ignore (illustrative) + /// *mut Vec<i32> + /// ``` + /// Here, the "ambient" variance starts as covariant. `*mut T` is + /// invariant with respect to `T`, so the variance in which the + /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which + /// yields `Invariant`. Now, the type `Vec<T>` is covariant with + /// respect to its type argument `T`, and hence the variance of + /// the `i32` here is `Invariant.xform(Covariant)`, which results + /// (again) in `Invariant`. + /// + /// Example 2: + /// ```ignore (illustrative) + /// fn(*const Vec<i32>, *mut Vec<i32) + /// ``` + /// The ambient variance is covariant. A `fn` type is + /// contravariant with respect to its parameters, so the variance + /// within which both pointer types appear is + /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const + /// T` is covariant with respect to `T`, so the variance within + /// which the first `Vec<i32>` appears is + /// `Contravariant.xform(Covariant)` or `Contravariant`. The same + /// is true for its `i32` argument. In the `*mut T` case, the + /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`, + /// and hence the outermost type is `Invariant` with respect to + /// `Vec<i32>` (and its `i32` argument). + /// + /// Source: Figure 1 of "Taming the Wildcards: + /// Combining Definition- and Use-Site Variance" published in PLDI'11. + pub fn xform(self, v: Variance) -> Variance { + match (self, v) { + // Figure 1, column 1. + (Variance::Covariant, Variance::Covariant) => Variance::Covariant, + (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant, + (Variance::Covariant, Variance::Invariant) => Variance::Invariant, + (Variance::Covariant, Variance::Bivariant) => Variance::Bivariant, + + // Figure 1, column 2. + (Variance::Contravariant, Variance::Covariant) => Variance::Contravariant, + (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant, + (Variance::Contravariant, Variance::Invariant) => Variance::Invariant, + (Variance::Contravariant, Variance::Bivariant) => Variance::Bivariant, + + // Figure 1, column 3. + (Variance::Invariant, _) => Variance::Invariant, + + // Figure 1, column 4. + (Variance::Bivariant, _) => Variance::Bivariant, + } + } +} + +impl<CTX> HashStable<CTX> for DebruijnIndex { + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + self.as_u32().hash_stable(ctx, hasher); + } +} + +impl<CTX> HashStable<CTX> for IntTy { + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + discriminant(self).hash_stable(ctx, hasher); + } +} + +impl<CTX> HashStable<CTX> for UintTy { + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + discriminant(self).hash_stable(ctx, hasher); + } +} + +impl<CTX> HashStable<CTX> for FloatTy { + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + discriminant(self).hash_stable(ctx, hasher); + } +} + +impl<CTX> HashStable<CTX> for InferTy { + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + use InferTy::*; + discriminant(self).hash_stable(ctx, hasher); + match self { + TyVar(v) => v.as_u32().hash_stable(ctx, hasher), + IntVar(v) => v.index.hash_stable(ctx, hasher), + FloatVar(v) => v.index.hash_stable(ctx, hasher), + FreshTy(v) | FreshIntTy(v) | FreshFloatTy(v) => v.hash_stable(ctx, hasher), + } + } +} + +impl<CTX> HashStable<CTX> for Variance { + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + discriminant(self).hash_stable(ctx, hasher); + } +} + +impl fmt::Debug for IntVarValue { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + IntVarValue::IntType(ref v) => v.fmt(f), + IntVarValue::UintType(ref v) => v.fmt(f), + } + } +} + +impl fmt::Debug for FloatVarValue { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0.fmt(f) + } +} + +impl fmt::Debug for IntVid { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "_#{}i", self.index) + } +} + +impl fmt::Debug for FloatVid { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "_#{}f", self.index) + } +} + +impl fmt::Debug for InferTy { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + use InferTy::*; + match *self { + TyVar(ref v) => v.fmt(f), + IntVar(ref v) => v.fmt(f), + FloatVar(ref v) => v.fmt(f), + FreshTy(v) => write!(f, "FreshTy({:?})", v), + FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v), + FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v), + } + } +} + +impl fmt::Debug for Variance { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str(match *self { + Variance::Covariant => "+", + Variance::Contravariant => "-", + Variance::Invariant => "o", + Variance::Bivariant => "*", + }) + } +} + +impl fmt::Display for InferTy { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + use InferTy::*; + match *self { + TyVar(_) => write!(f, "_"), + IntVar(_) => write!(f, "{}", "{integer}"), + FloatVar(_) => write!(f, "{}", "{float}"), + FreshTy(v) => write!(f, "FreshTy({})", v), + FreshIntTy(v) => write!(f, "FreshIntTy({})", v), + FreshFloatTy(v) => write!(f, "FreshFloatTy({})", v), + } + } +} + +rustc_index::newtype_index! { + /// "Universes" are used during type- and trait-checking in the + /// presence of `for<..>` binders to control what sets of names are + /// visible. Universes are arranged into a tree: the root universe + /// contains names that are always visible. Each child then adds a new + /// set of names that are visible, in addition to those of its parent. + /// We say that the child universe "extends" the parent universe with + /// new names. + /// + /// To make this more concrete, consider this program: + /// + /// ```ignore (illustrative) + /// struct Foo { } + /// fn bar<T>(x: T) { + /// let y: for<'a> fn(&'a u8, Foo) = ...; + /// } + /// ``` + /// + /// The struct name `Foo` is in the root universe U0. But the type + /// parameter `T`, introduced on `bar`, is in an extended universe U1 + /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside + /// of `bar`, we cannot name `T`. Then, within the type of `y`, the + /// region `'a` is in a universe U2 that extends U1, because we can + /// name it inside the fn type but not outside. + /// + /// Universes are used to do type- and trait-checking around these + /// "forall" binders (also called **universal quantification**). The + /// idea is that when, in the body of `bar`, we refer to `T` as a + /// type, we aren't referring to any type in particular, but rather a + /// kind of "fresh" type that is distinct from all other types we have + /// actually declared. This is called a **placeholder** type, and we + /// use universes to talk about this. In other words, a type name in + /// universe 0 always corresponds to some "ground" type that the user + /// declared, but a type name in a non-zero universe is a placeholder + /// type -- an idealized representative of "types in general" that we + /// use for checking generic functions. + pub struct UniverseIndex { + DEBUG_FORMAT = "U{}", + } +} + +impl UniverseIndex { + pub const ROOT: UniverseIndex = UniverseIndex::from_u32(0); + + /// Returns the "next" universe index in order -- this new index + /// is considered to extend all previous universes. This + /// corresponds to entering a `forall` quantifier. So, for + /// example, suppose we have this type in universe `U`: + /// + /// ```ignore (illustrative) + /// for<'a> fn(&'a u32) + /// ``` + /// + /// Once we "enter" into this `for<'a>` quantifier, we are in a + /// new universe that extends `U` -- in this new universe, we can + /// name the region `'a`, but that region was not nameable from + /// `U` because it was not in scope there. + pub fn next_universe(self) -> UniverseIndex { + UniverseIndex::from_u32(self.private.checked_add(1).unwrap()) + } + + /// Returns `true` if `self` can name a name from `other` -- in other words, + /// if the set of names in `self` is a superset of those in + /// `other` (`self >= other`). + pub fn can_name(self, other: UniverseIndex) -> bool { + self.private >= other.private + } + + /// Returns `true` if `self` cannot name some names from `other` -- in other + /// words, if the set of names in `self` is a strict subset of + /// those in `other` (`self < other`). + pub fn cannot_name(self, other: UniverseIndex) -> bool { + self.private < other.private + } +} + +impl<CTX> HashStable<CTX> for UniverseIndex { + fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { + self.private.hash_stable(ctx, hasher); + } +} |