diff options
Diffstat (limited to '')
-rw-r--r-- | compiler/rustc_type_ir/src/codec.rs | 64 | ||||
-rw-r--r-- | compiler/rustc_type_ir/src/lib.rs | 856 | ||||
-rw-r--r-- | compiler/rustc_type_ir/src/sty.rs | 1329 |
3 files changed, 2249 insertions, 0 deletions
diff --git a/compiler/rustc_type_ir/src/codec.rs b/compiler/rustc_type_ir/src/codec.rs new file mode 100644 index 000000000..ee249050c --- /dev/null +++ b/compiler/rustc_type_ir/src/codec.rs @@ -0,0 +1,64 @@ +use crate::Interner; + +use rustc_data_structures::fx::FxHashMap; +use rustc_serialize::{Decoder, Encoder}; + +/// The shorthand encoding uses an enum's variant index `usize` +/// and is offset by this value so it never matches a real variant. +/// This offset is also chosen so that the first byte is never < 0x80. +pub const SHORTHAND_OFFSET: usize = 0x80; + +/// Trait for decoding to a reference. +/// +/// This is a separate trait from `Decodable` so that we can implement it for +/// upstream types, such as `FxHashSet`. +/// +/// The `TyDecodable` derive macro will use this trait for fields that are +/// references (and don't use a type alias to hide that). +/// +/// `Decodable` can still be implemented in cases where `Decodable` is required +/// by a trait bound. +pub trait RefDecodable<'tcx, D: TyDecoder> { + fn decode(d: &mut D) -> &'tcx Self; +} + +pub trait TyEncoder: Encoder { + type I: Interner; + const CLEAR_CROSS_CRATE: bool; + + fn position(&self) -> usize; + fn type_shorthands(&mut self) -> &mut FxHashMap<<Self::I as Interner>::Ty, usize>; + fn predicate_shorthands( + &mut self, + ) -> &mut FxHashMap<<Self::I as Interner>::PredicateKind, usize>; + fn encode_alloc_id(&mut self, alloc_id: &<Self::I as Interner>::AllocId); +} + +pub trait TyDecoder: Decoder { + type I: Interner; + const CLEAR_CROSS_CRATE: bool; + + fn interner(&self) -> Self::I; + + fn peek_byte(&self) -> u8; + + fn position(&self) -> usize; + + fn cached_ty_for_shorthand<F>( + &mut self, + shorthand: usize, + or_insert_with: F, + ) -> <Self::I as Interner>::Ty + where + F: FnOnce(&mut Self) -> <Self::I as Interner>::Ty; + + fn with_position<F, R>(&mut self, pos: usize, f: F) -> R + where + F: FnOnce(&mut Self) -> R; + + fn positioned_at_shorthand(&self) -> bool { + (self.peek_byte() & (SHORTHAND_OFFSET as u8)) != 0 + } + + fn decode_alloc_id(&mut self) -> <Self::I as Interner>::AllocId; +} 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); + } +} diff --git a/compiler/rustc_type_ir/src/sty.rs b/compiler/rustc_type_ir/src/sty.rs new file mode 100644 index 000000000..74737e30b --- /dev/null +++ b/compiler/rustc_type_ir/src/sty.rs @@ -0,0 +1,1329 @@ +#![allow(rustc::usage_of_ty_tykind)] + +use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd}; +use std::{fmt, hash}; + +use crate::DebruijnIndex; +use crate::FloatTy; +use crate::IntTy; +use crate::Interner; +use crate::TyDecoder; +use crate::TyEncoder; +use crate::UintTy; +use crate::UniverseIndex; + +use self::RegionKind::*; +use self::TyKind::*; + +use rustc_data_structures::stable_hasher::HashStable; +use rustc_serialize::{Decodable, Decoder, Encodable}; + +/// Defines the kinds of types used by the type system. +/// +/// Types written by the user start out as `hir::TyKind` and get +/// converted to this representation using `AstConv::ast_ty_to_ty`. +#[rustc_diagnostic_item = "IrTyKind"] +pub enum TyKind<I: Interner> { + /// The primitive boolean type. Written as `bool`. + Bool, + + /// The primitive character type; holds a Unicode scalar value + /// (a non-surrogate code point). Written as `char`. + Char, + + /// A primitive signed integer type. For example, `i32`. + Int(IntTy), + + /// A primitive unsigned integer type. For example, `u32`. + Uint(UintTy), + + /// A primitive floating-point type. For example, `f64`. + Float(FloatTy), + + /// Algebraic data types (ADT). For example: structures, enumerations and unions. + /// + /// For example, the type `List<i32>` would be represented using the `AdtDef` + /// for `struct List<T>` and the substs `[i32]`. + /// + /// Note that generic parameters in fields only get lazily substituted + /// by using something like `adt_def.all_fields().map(|field| field.ty(tcx, substs))`. + Adt(I::AdtDef, I::SubstsRef), + + /// An unsized FFI type that is opaque to Rust. Written as `extern type T`. + Foreign(I::DefId), + + /// The pointee of a string slice. Written as `str`. + Str, + + /// An array with the given length. Written as `[T; N]`. + Array(I::Ty, I::Const), + + /// The pointee of an array slice. Written as `[T]`. + Slice(I::Ty), + + /// A raw pointer. Written as `*mut T` or `*const T` + RawPtr(I::TypeAndMut), + + /// A reference; a pointer with an associated lifetime. Written as + /// `&'a mut T` or `&'a T`. + Ref(I::Region, I::Ty, I::Mutability), + + /// The anonymous type of a function declaration/definition. Each + /// function has a unique type. + /// + /// For the function `fn foo() -> i32 { 3 }` this type would be + /// shown to the user as `fn() -> i32 {foo}`. + /// + /// For example the type of `bar` here: + /// ```rust + /// fn foo() -> i32 { 1 } + /// let bar = foo; // bar: fn() -> i32 {foo} + /// ``` + FnDef(I::DefId, I::SubstsRef), + + /// A pointer to a function. Written as `fn() -> i32`. + /// + /// Note that both functions and closures start out as either + /// [FnDef] or [Closure] which can be then be coerced to this variant. + /// + /// For example the type of `bar` here: + /// + /// ```rust + /// fn foo() -> i32 { 1 } + /// let bar: fn() -> i32 = foo; + /// ``` + FnPtr(I::PolyFnSig), + + /// A trait object. Written as `dyn for<'b> Trait<'b, Assoc = u32> + Send + 'a`. + Dynamic(I::ListBinderExistentialPredicate, I::Region), + + /// The anonymous type of a closure. Used to represent the type of `|a| a`. + /// + /// Closure substs contain both the - potentially substituted - generic parameters + /// of its parent and some synthetic parameters. See the documentation for + /// `ClosureSubsts` for more details. + Closure(I::DefId, I::SubstsRef), + + /// The anonymous type of a generator. Used to represent the type of + /// `|a| yield a`. + /// + /// For more info about generator substs, visit the documentation for + /// `GeneratorSubsts`. + Generator(I::DefId, I::SubstsRef, I::Movability), + + /// A type representing the types stored inside a generator. + /// This should only appear as part of the `GeneratorSubsts`. + /// + /// Note that the captured variables for generators are stored separately + /// using a tuple in the same way as for closures. + /// + /// Unlike upvars, the witness can reference lifetimes from + /// inside of the generator itself. To deal with them in + /// the type of the generator, we convert them to higher ranked + /// lifetimes bound by the witness itself. + /// + /// Looking at the following example, the witness for this generator + /// may end up as something like `for<'a> [Vec<i32>, &'a Vec<i32>]`: + /// + /// ```ignore UNSOLVED (ask @compiler-errors, should this error? can we just swap the yields?) + /// #![feature(generators)] + /// |a| { + /// let x = &vec![3]; + /// yield a; + /// yield x[0]; + /// } + /// # ; + /// ``` + GeneratorWitness(I::BinderListTy), + + /// The never type `!`. + Never, + + /// A tuple type. For example, `(i32, bool)`. + Tuple(I::ListTy), + + /// The projection of an associated type. For example, + /// `<T as Trait<..>>::N`. + Projection(I::ProjectionTy), + + /// Opaque (`impl Trait`) type found in a return type. + /// + /// The `DefId` comes either from + /// * the `impl Trait` ast::Ty node, + /// * or the `type Foo = impl Trait` declaration + /// + /// For RPIT the substitutions are for the generics of the function, + /// while for TAIT it is used for the generic parameters of the alias. + /// + /// During codegen, `tcx.type_of(def_id)` can be used to get the underlying type. + Opaque(I::DefId, I::SubstsRef), + + /// A type parameter; for example, `T` in `fn f<T>(x: T) {}`. + Param(I::ParamTy), + + /// Bound type variable, used to represent the `'a` in `for<'a> fn(&'a ())`. + /// + /// For canonical queries, we replace inference variables with bound variables, + /// so e.g. when checking whether `&'_ (): Trait<_>` holds, we canonicalize that to + /// `for<'a, T> &'a (): Trait<T>` and then convert the introduced bound variables + /// back to inference variables in a new inference context when inside of the query. + /// + /// See the `rustc-dev-guide` for more details about + /// [higher-ranked trait bounds][1] and [canonical queries][2]. + /// + /// [1]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html + /// [2]: https://rustc-dev-guide.rust-lang.org/traits/canonical-queries.html + Bound(DebruijnIndex, I::BoundTy), + + /// A placeholder type, used during higher ranked subtyping to instantiate + /// bound variables. + Placeholder(I::PlaceholderType), + + /// A type variable used during type checking. + /// + /// Similar to placeholders, inference variables also live in a universe to + /// correctly deal with higher ranked types. Though unlike placeholders, + /// that universe is stored in the `InferCtxt` instead of directly + /// inside of the type. + Infer(I::InferTy), + + /// A placeholder for a type which could not be computed; this is + /// propagated to avoid useless error messages. + Error(I::DelaySpanBugEmitted), +} + +impl<I: Interner> TyKind<I> { + #[inline] + pub fn is_primitive(&self) -> bool { + matches!(self, Bool | Char | Int(_) | Uint(_) | Float(_)) + } +} + +// This is manually implemented for `TyKind` because `std::mem::discriminant` +// returns an opaque value that is `PartialEq` but not `PartialOrd` +#[inline] +const fn tykind_discriminant<I: Interner>(value: &TyKind<I>) -> usize { + match value { + Bool => 0, + Char => 1, + Int(_) => 2, + Uint(_) => 3, + Float(_) => 4, + Adt(_, _) => 5, + Foreign(_) => 6, + Str => 7, + Array(_, _) => 8, + Slice(_) => 9, + RawPtr(_) => 10, + Ref(_, _, _) => 11, + FnDef(_, _) => 12, + FnPtr(_) => 13, + Dynamic(_, _) => 14, + Closure(_, _) => 15, + Generator(_, _, _) => 16, + GeneratorWitness(_) => 17, + Never => 18, + Tuple(_) => 19, + Projection(_) => 20, + Opaque(_, _) => 21, + Param(_) => 22, + Bound(_, _) => 23, + Placeholder(_) => 24, + Infer(_) => 25, + Error(_) => 26, + } +} + +// This is manually implemented because a derive would require `I: Clone` +impl<I: Interner> Clone for TyKind<I> { + fn clone(&self) -> Self { + match self { + Bool => Bool, + Char => Char, + Int(i) => Int(i.clone()), + Uint(u) => Uint(u.clone()), + Float(f) => Float(f.clone()), + Adt(d, s) => Adt(d.clone(), s.clone()), + Foreign(d) => Foreign(d.clone()), + Str => Str, + Array(t, c) => Array(t.clone(), c.clone()), + Slice(t) => Slice(t.clone()), + RawPtr(t) => RawPtr(t.clone()), + Ref(r, t, m) => Ref(r.clone(), t.clone(), m.clone()), + FnDef(d, s) => FnDef(d.clone(), s.clone()), + FnPtr(s) => FnPtr(s.clone()), + Dynamic(p, r) => Dynamic(p.clone(), r.clone()), + Closure(d, s) => Closure(d.clone(), s.clone()), + Generator(d, s, m) => Generator(d.clone(), s.clone(), m.clone()), + GeneratorWitness(g) => GeneratorWitness(g.clone()), + Never => Never, + Tuple(t) => Tuple(t.clone()), + Projection(p) => Projection(p.clone()), + Opaque(d, s) => Opaque(d.clone(), s.clone()), + Param(p) => Param(p.clone()), + Bound(d, b) => Bound(d.clone(), b.clone()), + Placeholder(p) => Placeholder(p.clone()), + Infer(t) => Infer(t.clone()), + Error(e) => Error(e.clone()), + } + } +} + +// This is manually implemented because a derive would require `I: PartialEq` +impl<I: Interner> PartialEq for TyKind<I> { + #[inline] + fn eq(&self, other: &TyKind<I>) -> bool { + let __self_vi = tykind_discriminant(self); + let __arg_1_vi = tykind_discriminant(other); + if __self_vi == __arg_1_vi { + match (&*self, &*other) { + (&Int(ref __self_0), &Int(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Uint(ref __self_0), &Uint(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Float(ref __self_0), &Float(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Adt(ref __self_0, ref __self_1), &Adt(ref __arg_1_0, ref __arg_1_1)) => { + __self_0 == __arg_1_0 && __self_1 == __arg_1_1 + } + (&Foreign(ref __self_0), &Foreign(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Array(ref __self_0, ref __self_1), &Array(ref __arg_1_0, ref __arg_1_1)) => { + __self_0 == __arg_1_0 && __self_1 == __arg_1_1 + } + (&Slice(ref __self_0), &Slice(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&RawPtr(ref __self_0), &RawPtr(ref __arg_1_0)) => __self_0 == __arg_1_0, + ( + &Ref(ref __self_0, ref __self_1, ref __self_2), + &Ref(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2), + ) => __self_0 == __arg_1_0 && __self_1 == __arg_1_1 && __self_2 == __arg_1_2, + (&FnDef(ref __self_0, ref __self_1), &FnDef(ref __arg_1_0, ref __arg_1_1)) => { + __self_0 == __arg_1_0 && __self_1 == __arg_1_1 + } + (&FnPtr(ref __self_0), &FnPtr(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Dynamic(ref __self_0, ref __self_1), &Dynamic(ref __arg_1_0, ref __arg_1_1)) => { + __self_0 == __arg_1_0 && __self_1 == __arg_1_1 + } + (&Closure(ref __self_0, ref __self_1), &Closure(ref __arg_1_0, ref __arg_1_1)) => { + __self_0 == __arg_1_0 && __self_1 == __arg_1_1 + } + ( + &Generator(ref __self_0, ref __self_1, ref __self_2), + &Generator(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2), + ) => __self_0 == __arg_1_0 && __self_1 == __arg_1_1 && __self_2 == __arg_1_2, + (&GeneratorWitness(ref __self_0), &GeneratorWitness(ref __arg_1_0)) => { + __self_0 == __arg_1_0 + } + (&Tuple(ref __self_0), &Tuple(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Projection(ref __self_0), &Projection(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Opaque(ref __self_0, ref __self_1), &Opaque(ref __arg_1_0, ref __arg_1_1)) => { + __self_0 == __arg_1_0 && __self_1 == __arg_1_1 + } + (&Param(ref __self_0), &Param(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Bound(ref __self_0, ref __self_1), &Bound(ref __arg_1_0, ref __arg_1_1)) => { + __self_0 == __arg_1_0 && __self_1 == __arg_1_1 + } + (&Placeholder(ref __self_0), &Placeholder(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Infer(ref __self_0), &Infer(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&Error(ref __self_0), &Error(ref __arg_1_0)) => __self_0 == __arg_1_0, + _ => true, + } + } else { + false + } + } +} + +// This is manually implemented because a derive would require `I: Eq` +impl<I: Interner> Eq for TyKind<I> {} + +// This is manually implemented because a derive would require `I: PartialOrd` +impl<I: Interner> PartialOrd for TyKind<I> { + #[inline] + fn partial_cmp(&self, other: &TyKind<I>) -> Option<Ordering> { + Some(Ord::cmp(self, other)) + } +} + +// This is manually implemented because a derive would require `I: Ord` +impl<I: Interner> Ord for TyKind<I> { + #[inline] + fn cmp(&self, other: &TyKind<I>) -> Ordering { + let __self_vi = tykind_discriminant(self); + let __arg_1_vi = tykind_discriminant(other); + if __self_vi == __arg_1_vi { + match (&*self, &*other) { + (&Int(ref __self_0), &Int(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Uint(ref __self_0), &Uint(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Float(ref __self_0), &Float(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Adt(ref __self_0, ref __self_1), &Adt(ref __arg_1_0, ref __arg_1_1)) => { + match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + } + } + (&Foreign(ref __self_0), &Foreign(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Array(ref __self_0, ref __self_1), &Array(ref __arg_1_0, ref __arg_1_1)) => { + match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + } + } + (&Slice(ref __self_0), &Slice(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&RawPtr(ref __self_0), &RawPtr(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + ( + &Ref(ref __self_0, ref __self_1, ref __self_2), + &Ref(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2), + ) => match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => match Ord::cmp(__self_1, __arg_1_1) { + Ordering::Equal => Ord::cmp(__self_2, __arg_1_2), + cmp => cmp, + }, + cmp => cmp, + }, + (&FnDef(ref __self_0, ref __self_1), &FnDef(ref __arg_1_0, ref __arg_1_1)) => { + match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + } + } + (&FnPtr(ref __self_0), &FnPtr(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Dynamic(ref __self_0, ref __self_1), &Dynamic(ref __arg_1_0, ref __arg_1_1)) => { + match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + } + } + (&Closure(ref __self_0, ref __self_1), &Closure(ref __arg_1_0, ref __arg_1_1)) => { + match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + } + } + ( + &Generator(ref __self_0, ref __self_1, ref __self_2), + &Generator(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2), + ) => match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => match Ord::cmp(__self_1, __arg_1_1) { + Ordering::Equal => Ord::cmp(__self_2, __arg_1_2), + cmp => cmp, + }, + cmp => cmp, + }, + (&GeneratorWitness(ref __self_0), &GeneratorWitness(ref __arg_1_0)) => { + Ord::cmp(__self_0, __arg_1_0) + } + (&Tuple(ref __self_0), &Tuple(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Projection(ref __self_0), &Projection(ref __arg_1_0)) => { + Ord::cmp(__self_0, __arg_1_0) + } + (&Opaque(ref __self_0, ref __self_1), &Opaque(ref __arg_1_0, ref __arg_1_1)) => { + match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + } + } + (&Param(ref __self_0), &Param(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Bound(ref __self_0, ref __self_1), &Bound(ref __arg_1_0, ref __arg_1_1)) => { + match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + } + } + (&Placeholder(ref __self_0), &Placeholder(ref __arg_1_0)) => { + Ord::cmp(__self_0, __arg_1_0) + } + (&Infer(ref __self_0), &Infer(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&Error(ref __self_0), &Error(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + _ => Ordering::Equal, + } + } else { + Ord::cmp(&__self_vi, &__arg_1_vi) + } + } +} + +// This is manually implemented because a derive would require `I: Hash` +impl<I: Interner> hash::Hash for TyKind<I> { + fn hash<__H: hash::Hasher>(&self, state: &mut __H) -> () { + match (&*self,) { + (&Int(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Uint(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Float(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Adt(ref __self_0, ref __self_1),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&Foreign(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Array(ref __self_0, ref __self_1),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&Slice(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&RawPtr(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Ref(ref __self_0, ref __self_1, ref __self_2),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state); + hash::Hash::hash(__self_2, state) + } + (&FnDef(ref __self_0, ref __self_1),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&FnPtr(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Dynamic(ref __self_0, ref __self_1),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&Closure(ref __self_0, ref __self_1),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&Generator(ref __self_0, ref __self_1, ref __self_2),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state); + hash::Hash::hash(__self_2, state) + } + (&GeneratorWitness(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Tuple(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Projection(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Opaque(ref __self_0, ref __self_1),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&Param(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Bound(ref __self_0, ref __self_1),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&Placeholder(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Infer(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&Error(ref __self_0),) => { + hash::Hash::hash(&tykind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + _ => hash::Hash::hash(&tykind_discriminant(self), state), + } + } +} + +// This is manually implemented because a derive would require `I: Debug` +impl<I: Interner> fmt::Debug for TyKind<I> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + use std::fmt::*; + match self { + Bool => Formatter::write_str(f, "Bool"), + Char => Formatter::write_str(f, "Char"), + Int(f0) => Formatter::debug_tuple_field1_finish(f, "Int", f0), + Uint(f0) => Formatter::debug_tuple_field1_finish(f, "Uint", f0), + Float(f0) => Formatter::debug_tuple_field1_finish(f, "Float", f0), + Adt(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Adt", f0, f1), + Foreign(f0) => Formatter::debug_tuple_field1_finish(f, "Foreign", f0), + Str => Formatter::write_str(f, "Str"), + Array(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Array", f0, f1), + Slice(f0) => Formatter::debug_tuple_field1_finish(f, "Slice", f0), + RawPtr(f0) => Formatter::debug_tuple_field1_finish(f, "RawPtr", f0), + Ref(f0, f1, f2) => Formatter::debug_tuple_field3_finish(f, "Ref", f0, f1, f2), + FnDef(f0, f1) => Formatter::debug_tuple_field2_finish(f, "FnDef", f0, f1), + FnPtr(f0) => Formatter::debug_tuple_field1_finish(f, "FnPtr", f0), + Dynamic(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Dynamic", f0, f1), + Closure(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Closure", f0, f1), + Generator(f0, f1, f2) => { + Formatter::debug_tuple_field3_finish(f, "Generator", f0, f1, f2) + } + GeneratorWitness(f0) => Formatter::debug_tuple_field1_finish(f, "GeneratorWitness", f0), + Never => Formatter::write_str(f, "Never"), + Tuple(f0) => Formatter::debug_tuple_field1_finish(f, "Tuple", f0), + Projection(f0) => Formatter::debug_tuple_field1_finish(f, "Projection", f0), + Opaque(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Opaque", f0, f1), + Param(f0) => Formatter::debug_tuple_field1_finish(f, "Param", f0), + Bound(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Bound", f0, f1), + Placeholder(f0) => Formatter::debug_tuple_field1_finish(f, "Placeholder", f0), + Infer(f0) => Formatter::debug_tuple_field1_finish(f, "Infer", f0), + TyKind::Error(f0) => Formatter::debug_tuple_field1_finish(f, "Error", f0), + } + } +} + +// This is manually implemented because a derive would require `I: Encodable` +impl<I: Interner, E: TyEncoder> Encodable<E> for TyKind<I> +where + I::DelaySpanBugEmitted: Encodable<E>, + I::AdtDef: Encodable<E>, + I::SubstsRef: Encodable<E>, + I::DefId: Encodable<E>, + I::Ty: Encodable<E>, + I::Const: Encodable<E>, + I::Region: Encodable<E>, + I::TypeAndMut: Encodable<E>, + I::Mutability: Encodable<E>, + I::Movability: Encodable<E>, + I::PolyFnSig: Encodable<E>, + I::ListBinderExistentialPredicate: Encodable<E>, + I::BinderListTy: Encodable<E>, + I::ListTy: Encodable<E>, + I::ProjectionTy: Encodable<E>, + I::ParamTy: Encodable<E>, + I::BoundTy: Encodable<E>, + I::PlaceholderType: Encodable<E>, + I::InferTy: Encodable<E>, + I::DelaySpanBugEmitted: Encodable<E>, + I::PredicateKind: Encodable<E>, + I::AllocId: Encodable<E>, +{ + fn encode(&self, e: &mut E) { + let disc = tykind_discriminant(self); + match self { + Bool => e.emit_enum_variant(disc, |_| {}), + Char => e.emit_enum_variant(disc, |_| {}), + Int(i) => e.emit_enum_variant(disc, |e| { + i.encode(e); + }), + Uint(u) => e.emit_enum_variant(disc, |e| { + u.encode(e); + }), + Float(f) => e.emit_enum_variant(disc, |e| { + f.encode(e); + }), + Adt(adt, substs) => e.emit_enum_variant(disc, |e| { + adt.encode(e); + substs.encode(e); + }), + Foreign(def_id) => e.emit_enum_variant(disc, |e| { + def_id.encode(e); + }), + Str => e.emit_enum_variant(disc, |_| {}), + Array(t, c) => e.emit_enum_variant(disc, |e| { + t.encode(e); + c.encode(e); + }), + Slice(t) => e.emit_enum_variant(disc, |e| { + t.encode(e); + }), + RawPtr(tam) => e.emit_enum_variant(disc, |e| { + tam.encode(e); + }), + Ref(r, t, m) => e.emit_enum_variant(disc, |e| { + r.encode(e); + t.encode(e); + m.encode(e); + }), + FnDef(def_id, substs) => e.emit_enum_variant(disc, |e| { + def_id.encode(e); + substs.encode(e); + }), + FnPtr(polyfnsig) => e.emit_enum_variant(disc, |e| { + polyfnsig.encode(e); + }), + Dynamic(l, r) => e.emit_enum_variant(disc, |e| { + l.encode(e); + r.encode(e); + }), + Closure(def_id, substs) => e.emit_enum_variant(disc, |e| { + def_id.encode(e); + substs.encode(e); + }), + Generator(def_id, substs, m) => e.emit_enum_variant(disc, |e| { + def_id.encode(e); + substs.encode(e); + m.encode(e); + }), + GeneratorWitness(b) => e.emit_enum_variant(disc, |e| { + b.encode(e); + }), + Never => e.emit_enum_variant(disc, |_| {}), + Tuple(substs) => e.emit_enum_variant(disc, |e| { + substs.encode(e); + }), + Projection(p) => e.emit_enum_variant(disc, |e| { + p.encode(e); + }), + Opaque(def_id, substs) => e.emit_enum_variant(disc, |e| { + def_id.encode(e); + substs.encode(e); + }), + Param(p) => e.emit_enum_variant(disc, |e| { + p.encode(e); + }), + Bound(d, b) => e.emit_enum_variant(disc, |e| { + d.encode(e); + b.encode(e); + }), + Placeholder(p) => e.emit_enum_variant(disc, |e| { + p.encode(e); + }), + Infer(i) => e.emit_enum_variant(disc, |e| { + i.encode(e); + }), + Error(d) => e.emit_enum_variant(disc, |e| { + d.encode(e); + }), + } + } +} + +// This is manually implemented because a derive would require `I: Decodable` +impl<I: Interner, D: TyDecoder<I = I>> Decodable<D> for TyKind<I> +where + I::DelaySpanBugEmitted: Decodable<D>, + I::AdtDef: Decodable<D>, + I::SubstsRef: Decodable<D>, + I::DefId: Decodable<D>, + I::Ty: Decodable<D>, + I::Const: Decodable<D>, + I::Region: Decodable<D>, + I::TypeAndMut: Decodable<D>, + I::Mutability: Decodable<D>, + I::Movability: Decodable<D>, + I::PolyFnSig: Decodable<D>, + I::ListBinderExistentialPredicate: Decodable<D>, + I::BinderListTy: Decodable<D>, + I::ListTy: Decodable<D>, + I::ProjectionTy: Decodable<D>, + I::ParamTy: Decodable<D>, + I::BoundTy: Decodable<D>, + I::PlaceholderType: Decodable<D>, + I::InferTy: Decodable<D>, + I::DelaySpanBugEmitted: Decodable<D>, + I::PredicateKind: Decodable<D>, + I::AllocId: Decodable<D>, +{ + fn decode(d: &mut D) -> Self { + match Decoder::read_usize(d) { + 0 => Bool, + 1 => Char, + 2 => Int(Decodable::decode(d)), + 3 => Uint(Decodable::decode(d)), + 4 => Float(Decodable::decode(d)), + 5 => Adt(Decodable::decode(d), Decodable::decode(d)), + 6 => Foreign(Decodable::decode(d)), + 7 => Str, + 8 => Array(Decodable::decode(d), Decodable::decode(d)), + 9 => Slice(Decodable::decode(d)), + 10 => RawPtr(Decodable::decode(d)), + 11 => Ref(Decodable::decode(d), Decodable::decode(d), Decodable::decode(d)), + 12 => FnDef(Decodable::decode(d), Decodable::decode(d)), + 13 => FnPtr(Decodable::decode(d)), + 14 => Dynamic(Decodable::decode(d), Decodable::decode(d)), + 15 => Closure(Decodable::decode(d), Decodable::decode(d)), + 16 => Generator(Decodable::decode(d), Decodable::decode(d), Decodable::decode(d)), + 17 => GeneratorWitness(Decodable::decode(d)), + 18 => Never, + 19 => Tuple(Decodable::decode(d)), + 20 => Projection(Decodable::decode(d)), + 21 => Opaque(Decodable::decode(d), Decodable::decode(d)), + 22 => Param(Decodable::decode(d)), + 23 => Bound(Decodable::decode(d), Decodable::decode(d)), + 24 => Placeholder(Decodable::decode(d)), + 25 => Infer(Decodable::decode(d)), + 26 => Error(Decodable::decode(d)), + _ => panic!( + "{}", + format!( + "invalid enum variant tag while decoding `{}`, expected 0..{}", + "TyKind", 27, + ) + ), + } + } +} + +// This is not a derived impl because a derive would require `I: HashStable` +#[allow(rustc::usage_of_ty_tykind)] +impl<CTX, I: Interner> HashStable<CTX> for TyKind<I> +where + I::AdtDef: HashStable<CTX>, + I::DefId: HashStable<CTX>, + I::SubstsRef: HashStable<CTX>, + I::Ty: HashStable<CTX>, + I::Const: HashStable<CTX>, + I::TypeAndMut: HashStable<CTX>, + I::PolyFnSig: HashStable<CTX>, + I::ListBinderExistentialPredicate: HashStable<CTX>, + I::Region: HashStable<CTX>, + I::Movability: HashStable<CTX>, + I::Mutability: HashStable<CTX>, + I::BinderListTy: HashStable<CTX>, + I::ListTy: HashStable<CTX>, + I::ProjectionTy: HashStable<CTX>, + I::BoundTy: HashStable<CTX>, + I::ParamTy: HashStable<CTX>, + I::PlaceholderType: HashStable<CTX>, + I::InferTy: HashStable<CTX>, + I::DelaySpanBugEmitted: HashStable<CTX>, +{ + #[inline] + fn hash_stable( + &self, + __hcx: &mut CTX, + __hasher: &mut rustc_data_structures::stable_hasher::StableHasher, + ) { + std::mem::discriminant(self).hash_stable(__hcx, __hasher); + match self { + Bool => {} + Char => {} + Int(i) => { + i.hash_stable(__hcx, __hasher); + } + Uint(u) => { + u.hash_stable(__hcx, __hasher); + } + Float(f) => { + f.hash_stable(__hcx, __hasher); + } + Adt(adt, substs) => { + adt.hash_stable(__hcx, __hasher); + substs.hash_stable(__hcx, __hasher); + } + Foreign(def_id) => { + def_id.hash_stable(__hcx, __hasher); + } + Str => {} + Array(t, c) => { + t.hash_stable(__hcx, __hasher); + c.hash_stable(__hcx, __hasher); + } + Slice(t) => { + t.hash_stable(__hcx, __hasher); + } + RawPtr(tam) => { + tam.hash_stable(__hcx, __hasher); + } + Ref(r, t, m) => { + r.hash_stable(__hcx, __hasher); + t.hash_stable(__hcx, __hasher); + m.hash_stable(__hcx, __hasher); + } + FnDef(def_id, substs) => { + def_id.hash_stable(__hcx, __hasher); + substs.hash_stable(__hcx, __hasher); + } + FnPtr(polyfnsig) => { + polyfnsig.hash_stable(__hcx, __hasher); + } + Dynamic(l, r) => { + l.hash_stable(__hcx, __hasher); + r.hash_stable(__hcx, __hasher); + } + Closure(def_id, substs) => { + def_id.hash_stable(__hcx, __hasher); + substs.hash_stable(__hcx, __hasher); + } + Generator(def_id, substs, m) => { + def_id.hash_stable(__hcx, __hasher); + substs.hash_stable(__hcx, __hasher); + m.hash_stable(__hcx, __hasher); + } + GeneratorWitness(b) => { + b.hash_stable(__hcx, __hasher); + } + Never => {} + Tuple(substs) => { + substs.hash_stable(__hcx, __hasher); + } + Projection(p) => { + p.hash_stable(__hcx, __hasher); + } + Opaque(def_id, substs) => { + def_id.hash_stable(__hcx, __hasher); + substs.hash_stable(__hcx, __hasher); + } + Param(p) => { + p.hash_stable(__hcx, __hasher); + } + Bound(d, b) => { + d.hash_stable(__hcx, __hasher); + b.hash_stable(__hcx, __hasher); + } + Placeholder(p) => { + p.hash_stable(__hcx, __hasher); + } + Infer(i) => { + i.hash_stable(__hcx, __hasher); + } + Error(d) => { + d.hash_stable(__hcx, __hasher); + } + } + } +} + +/// Representation of regions. Note that the NLL checker uses a distinct +/// representation of regions. For this reason, it internally replaces all the +/// regions with inference variables -- the index of the variable is then used +/// to index into internal NLL data structures. See `rustc_const_eval::borrow_check` +/// module for more information. +/// +/// Note: operations are on the wrapper `Region` type, which is interned, +/// rather than this type. +/// +/// ## The Region lattice within a given function +/// +/// In general, the region lattice looks like +/// +/// ```text +/// static ----------+-----...------+ (greatest) +/// | | | +/// early-bound and | | +/// free regions | | +/// | | | +/// | | | +/// empty(root) placeholder(U1) | +/// | / | +/// | / placeholder(Un) +/// empty(U1) -- / +/// | / +/// ... / +/// | / +/// empty(Un) -------- (smallest) +/// ``` +/// +/// Early-bound/free regions are the named lifetimes in scope from the +/// function declaration. They have relationships to one another +/// determined based on the declared relationships from the +/// function. +/// +/// Note that inference variables and bound regions are not included +/// in this diagram. In the case of inference variables, they should +/// be inferred to some other region from the diagram. In the case of +/// bound regions, they are excluded because they don't make sense to +/// include -- the diagram indicates the relationship between free +/// regions. +/// +/// ## Inference variables +/// +/// During region inference, we sometimes create inference variables, +/// represented as `ReVar`. These will be inferred by the code in +/// `infer::lexical_region_resolve` to some free region from the +/// lattice above (the minimal region that meets the +/// constraints). +/// +/// During NLL checking, where regions are defined differently, we +/// also use `ReVar` -- in that case, the index is used to index into +/// the NLL region checker's data structures. The variable may in fact +/// represent either a free region or an inference variable, in that +/// case. +/// +/// ## Bound Regions +/// +/// These are regions that are stored behind a binder and must be substituted +/// with some concrete region before being used. There are two kind of +/// bound regions: early-bound, which are bound in an item's `Generics`, +/// and are substituted by an `InternalSubsts`, and late-bound, which are part of +/// higher-ranked types (e.g., `for<'a> fn(&'a ())`), and are substituted by +/// the likes of `liberate_late_bound_regions`. The distinction exists +/// because higher-ranked lifetimes aren't supported in all places. See [1][2]. +/// +/// Unlike `Param`s, bound regions are not supposed to exist "in the wild" +/// outside their binder, e.g., in types passed to type inference, and +/// should first be substituted (by placeholder regions, free regions, +/// or region variables). +/// +/// ## Placeholder and Free Regions +/// +/// One often wants to work with bound regions without knowing their precise +/// identity. For example, when checking a function, the lifetime of a borrow +/// can end up being assigned to some region parameter. In these cases, +/// it must be ensured that bounds on the region can't be accidentally +/// assumed without being checked. +/// +/// To do this, we replace the bound regions with placeholder markers, +/// which don't satisfy any relation not explicitly provided. +/// +/// There are two kinds of placeholder regions in rustc: `ReFree` and +/// `RePlaceholder`. When checking an item's body, `ReFree` is supposed +/// to be used. These also support explicit bounds: both the internally-stored +/// *scope*, which the region is assumed to outlive, as well as other +/// relations stored in the `FreeRegionMap`. Note that these relations +/// aren't checked when you `make_subregion` (or `eq_types`), only by +/// `resolve_regions_and_report_errors`. +/// +/// When working with higher-ranked types, some region relations aren't +/// yet known, so you can't just call `resolve_regions_and_report_errors`. +/// `RePlaceholder` is designed for this purpose. In these contexts, +/// there's also the risk that some inference variable laying around will +/// get unified with your placeholder region: if you want to check whether +/// `for<'a> Foo<'_>: 'a`, and you substitute your bound region `'a` +/// with a placeholder region `'%a`, the variable `'_` would just be +/// instantiated to the placeholder region `'%a`, which is wrong because +/// the inference variable is supposed to satisfy the relation +/// *for every value of the placeholder region*. To ensure that doesn't +/// happen, you can use `leak_check`. This is more clearly explained +/// by the [rustc dev guide]. +/// +/// [1]: https://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/ +/// [2]: https://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/ +/// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html +pub enum RegionKind<I: Interner> { + /// Region bound in a type or fn declaration which will be + /// substituted 'early' -- that is, at the same time when type + /// parameters are substituted. + ReEarlyBound(I::EarlyBoundRegion), + + /// Region bound in a function scope, which will be substituted when the + /// function is called. + ReLateBound(DebruijnIndex, I::BoundRegion), + + /// When checking a function body, the types of all arguments and so forth + /// that refer to bound region parameters are modified to refer to free + /// region parameters. + ReFree(I::FreeRegion), + + /// Static data that has an "infinite" lifetime. Top in the region lattice. + ReStatic, + + /// A region variable. Should not exist outside of type inference. + ReVar(I::RegionVid), + + /// A placeholder region -- basically, the higher-ranked version of `ReFree`. + /// Should not exist outside of type inference. + RePlaceholder(I::PlaceholderRegion), + + /// Empty lifetime is for data that is never accessed. We tag the + /// empty lifetime with a universe -- the idea is that we don't + /// want `exists<'a> { forall<'b> { 'b: 'a } }` to be satisfiable. + /// Therefore, the `'empty` in a universe `U` is less than all + /// regions visible from `U`, but not less than regions not visible + /// from `U`. + ReEmpty(UniverseIndex), + + /// Erased region, used by trait selection, in MIR and during codegen. + ReErased, +} + +// This is manually implemented for `RegionKind` because `std::mem::discriminant` +// returns an opaque value that is `PartialEq` but not `PartialOrd` +#[inline] +const fn regionkind_discriminant<I: Interner>(value: &RegionKind<I>) -> usize { + match value { + ReEarlyBound(_) => 0, + ReLateBound(_, _) => 1, + ReFree(_) => 2, + ReStatic => 3, + ReVar(_) => 4, + RePlaceholder(_) => 5, + ReEmpty(_) => 6, + ReErased => 7, + } +} + +// This is manually implemented because a derive would require `I: Copy` +impl<I: Interner> Copy for RegionKind<I> +where + I::EarlyBoundRegion: Copy, + I::BoundRegion: Copy, + I::FreeRegion: Copy, + I::RegionVid: Copy, + I::PlaceholderRegion: Copy, +{ +} + +// This is manually implemented because a derive would require `I: Clone` +impl<I: Interner> Clone for RegionKind<I> { + fn clone(&self) -> Self { + match self { + ReEarlyBound(a) => ReEarlyBound(a.clone()), + ReLateBound(a, b) => ReLateBound(a.clone(), b.clone()), + ReFree(a) => ReFree(a.clone()), + ReStatic => ReStatic, + ReVar(a) => ReVar(a.clone()), + RePlaceholder(a) => RePlaceholder(a.clone()), + ReEmpty(a) => ReEmpty(a.clone()), + ReErased => ReErased, + } + } +} + +// This is manually implemented because a derive would require `I: PartialEq` +impl<I: Interner> PartialEq for RegionKind<I> { + #[inline] + fn eq(&self, other: &RegionKind<I>) -> bool { + let __self_vi = regionkind_discriminant(self); + let __arg_1_vi = regionkind_discriminant(other); + if __self_vi == __arg_1_vi { + match (&*self, &*other) { + (&ReEarlyBound(ref __self_0), &ReEarlyBound(ref __arg_1_0)) => { + __self_0 == __arg_1_0 + } + ( + &ReLateBound(ref __self_0, ref __self_1), + &ReLateBound(ref __arg_1_0, ref __arg_1_1), + ) => __self_0 == __arg_1_0 && __self_1 == __arg_1_1, + (&ReFree(ref __self_0), &ReFree(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&ReStatic, &ReStatic) => true, + (&ReVar(ref __self_0), &ReVar(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&RePlaceholder(ref __self_0), &RePlaceholder(ref __arg_1_0)) => { + __self_0 == __arg_1_0 + } + (&ReEmpty(ref __self_0), &ReEmpty(ref __arg_1_0)) => __self_0 == __arg_1_0, + (&ReErased, &ReErased) => true, + _ => true, + } + } else { + false + } + } +} + +// This is manually implemented because a derive would require `I: Eq` +impl<I: Interner> Eq for RegionKind<I> {} + +// This is manually implemented because a derive would require `I: PartialOrd` +impl<I: Interner> PartialOrd for RegionKind<I> { + #[inline] + fn partial_cmp(&self, other: &RegionKind<I>) -> Option<Ordering> { + Some(Ord::cmp(self, other)) + } +} + +// This is manually implemented because a derive would require `I: Ord` +impl<I: Interner> Ord for RegionKind<I> { + #[inline] + fn cmp(&self, other: &RegionKind<I>) -> Ordering { + let __self_vi = regionkind_discriminant(self); + let __arg_1_vi = regionkind_discriminant(other); + if __self_vi == __arg_1_vi { + match (&*self, &*other) { + (&ReEarlyBound(ref __self_0), &ReEarlyBound(ref __arg_1_0)) => { + Ord::cmp(__self_0, __arg_1_0) + } + ( + &ReLateBound(ref __self_0, ref __self_1), + &ReLateBound(ref __arg_1_0, ref __arg_1_1), + ) => match Ord::cmp(__self_0, __arg_1_0) { + Ordering::Equal => Ord::cmp(__self_1, __arg_1_1), + cmp => cmp, + }, + (&ReFree(ref __self_0), &ReFree(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&ReStatic, &ReStatic) => Ordering::Equal, + (&ReVar(ref __self_0), &ReVar(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&RePlaceholder(ref __self_0), &RePlaceholder(ref __arg_1_0)) => { + Ord::cmp(__self_0, __arg_1_0) + } + (&ReEmpty(ref __self_0), &ReEmpty(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0), + (&ReErased, &ReErased) => Ordering::Equal, + _ => Ordering::Equal, + } + } else { + Ord::cmp(&__self_vi, &__arg_1_vi) + } + } +} + +// This is manually implemented because a derive would require `I: Hash` +impl<I: Interner> hash::Hash for RegionKind<I> { + fn hash<__H: hash::Hasher>(&self, state: &mut __H) -> () { + match (&*self,) { + (&ReEarlyBound(ref __self_0),) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&ReLateBound(ref __self_0, ref __self_1),) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + hash::Hash::hash(__self_0, state); + hash::Hash::hash(__self_1, state) + } + (&ReFree(ref __self_0),) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&ReStatic,) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + } + (&ReVar(ref __self_0),) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&RePlaceholder(ref __self_0),) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&ReEmpty(ref __self_0),) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + hash::Hash::hash(__self_0, state) + } + (&ReErased,) => { + hash::Hash::hash(®ionkind_discriminant(self), state); + } + } + } +} + +// This is manually implemented because a derive would require `I: Debug` +impl<I: Interner> fmt::Debug for RegionKind<I> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + ReEarlyBound(ref data) => write!(f, "ReEarlyBound({:?})", data), + + ReLateBound(binder_id, ref bound_region) => { + write!(f, "ReLateBound({:?}, {:?})", binder_id, bound_region) + } + + ReFree(ref fr) => fr.fmt(f), + + ReStatic => write!(f, "ReStatic"), + + ReVar(ref vid) => vid.fmt(f), + + RePlaceholder(placeholder) => write!(f, "RePlaceholder({:?})", placeholder), + + ReEmpty(ui) => write!(f, "ReEmpty({:?})", ui), + + ReErased => write!(f, "ReErased"), + } + } +} + +// This is manually implemented because a derive would require `I: Encodable` +impl<I: Interner, E: TyEncoder> Encodable<E> for RegionKind<I> +where + I::EarlyBoundRegion: Encodable<E>, + I::BoundRegion: Encodable<E>, + I::FreeRegion: Encodable<E>, + I::RegionVid: Encodable<E>, + I::PlaceholderRegion: Encodable<E>, +{ + fn encode(&self, e: &mut E) { + let disc = regionkind_discriminant(self); + match self { + ReEarlyBound(a) => e.emit_enum_variant(disc, |e| { + a.encode(e); + }), + ReLateBound(a, b) => e.emit_enum_variant(disc, |e| { + a.encode(e); + b.encode(e); + }), + ReFree(a) => e.emit_enum_variant(disc, |e| { + a.encode(e); + }), + ReStatic => e.emit_enum_variant(disc, |_| {}), + ReVar(a) => e.emit_enum_variant(disc, |e| { + a.encode(e); + }), + RePlaceholder(a) => e.emit_enum_variant(disc, |e| { + a.encode(e); + }), + ReEmpty(a) => e.emit_enum_variant(disc, |e| { + a.encode(e); + }), + ReErased => e.emit_enum_variant(disc, |_| {}), + } + } +} + +// This is manually implemented because a derive would require `I: Decodable` +impl<I: Interner, D: TyDecoder<I = I>> Decodable<D> for RegionKind<I> +where + I::EarlyBoundRegion: Decodable<D>, + I::BoundRegion: Decodable<D>, + I::FreeRegion: Decodable<D>, + I::RegionVid: Decodable<D>, + I::PlaceholderRegion: Decodable<D>, +{ + fn decode(d: &mut D) -> Self { + match Decoder::read_usize(d) { + 0 => ReEarlyBound(Decodable::decode(d)), + 1 => ReLateBound(Decodable::decode(d), Decodable::decode(d)), + 2 => ReFree(Decodable::decode(d)), + 3 => ReStatic, + 4 => ReVar(Decodable::decode(d)), + 5 => RePlaceholder(Decodable::decode(d)), + 6 => ReEmpty(Decodable::decode(d)), + 7 => ReErased, + _ => panic!( + "{}", + format!( + "invalid enum variant tag while decoding `{}`, expected 0..{}", + "RegionKind", 8, + ) + ), + } + } +} + +// This is not a derived impl because a derive would require `I: HashStable` +impl<CTX, I: Interner> HashStable<CTX> for RegionKind<I> +where + I::EarlyBoundRegion: HashStable<CTX>, + I::BoundRegion: HashStable<CTX>, + I::FreeRegion: HashStable<CTX>, + I::RegionVid: HashStable<CTX>, + I::PlaceholderRegion: HashStable<CTX>, +{ + #[inline] + fn hash_stable( + &self, + hcx: &mut CTX, + hasher: &mut rustc_data_structures::stable_hasher::StableHasher, + ) { + std::mem::discriminant(self).hash_stable(hcx, hasher); + match self { + ReErased | ReStatic => { + // No variant fields to hash for these ... + } + ReEmpty(universe) => { + universe.hash_stable(hcx, hasher); + } + ReLateBound(db, br) => { + db.hash_stable(hcx, hasher); + br.hash_stable(hcx, hasher); + } + ReEarlyBound(eb) => { + eb.hash_stable(hcx, hasher); + } + ReFree(ref free_region) => { + free_region.hash_stable(hcx, hasher); + } + RePlaceholder(p) => { + p.hash_stable(hcx, hasher); + } + ReVar(reg) => { + reg.hash_stable(hcx, hasher); + } + } + } +} |