1 #![feature(fmt_helpers_for_derive)]
2 #![feature(min_specialization)]
3 #![feature(rustc_attrs)]
8 extern crate rustc_macros;
10 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
11 use rustc_data_structures::unify::{EqUnifyValue, UnifyKey};
12 use smallvec::SmallVec;
16 use std::mem::discriminant;
25 type AdtDef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
26 type SubstsRef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
27 type DefId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
28 type Ty: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
29 type Const: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
30 type Region: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
31 type TypeAndMut: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
32 type Mutability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
33 type Movability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
34 type PolyFnSig: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
35 type ListBinderExistentialPredicate: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
36 type BinderListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
37 type ListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
38 type ProjectionTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
39 type ParamTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
40 type BoundTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
41 type PlaceholderType: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
42 type InferTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
43 type DelaySpanBugEmitted: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
44 type PredicateKind: Clone + Debug + Hash + PartialEq + Eq;
45 type AllocId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
47 type EarlyBoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
48 type BoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
49 type FreeRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
50 type RegionVid: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
51 type PlaceholderRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
54 pub trait InternAs<T: ?Sized, R> {
56 fn intern_with<F>(self, f: F) -> Self::Output
61 impl<I, T, R, E> InternAs<[T], R> for I
63 E: InternIteratorElement<T, R>,
64 I: Iterator<Item = E>,
66 type Output = E::Output;
67 fn intern_with<F>(self, f: F) -> Self::Output
71 E::intern_with(self, f)
75 pub trait InternIteratorElement<T, R>: Sized {
77 fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output;
80 impl<T, R> InternIteratorElement<T, R> for T {
82 fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(
86 // This code is hot enough that it's worth specializing for the most
87 // common length lists, to avoid the overhead of `SmallVec` creation.
88 // Lengths 0, 1, and 2 typically account for ~95% of cases. If
89 // `size_hint` is incorrect a panic will occur via an `unwrap` or an
91 match iter.size_hint() {
93 assert!(iter.next().is_none());
97 let t0 = iter.next().unwrap();
98 assert!(iter.next().is_none());
102 let t0 = iter.next().unwrap();
103 let t1 = iter.next().unwrap();
104 assert!(iter.next().is_none());
107 _ => f(&iter.collect::<SmallVec<[_; 8]>>()),
112 impl<'a, T, R> InternIteratorElement<T, R> for &'a T
117 fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
118 // This code isn't hot.
119 f(&iter.cloned().collect::<SmallVec<[_; 8]>>())
123 impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> {
124 type Output = Result<R, E>;
125 fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(
129 // This code is hot enough that it's worth specializing for the most
130 // common length lists, to avoid the overhead of `SmallVec` creation.
131 // Lengths 0, 1, and 2 typically account for ~95% of cases. If
132 // `size_hint` is incorrect a panic will occur via an `unwrap` or an
133 // `assert`, unless a failure happens first, in which case the result
134 // will be an error anyway.
135 Ok(match iter.size_hint() {
137 assert!(iter.next().is_none());
141 let t0 = iter.next().unwrap()?;
142 assert!(iter.next().is_none());
146 let t0 = iter.next().unwrap()?;
147 let t1 = iter.next().unwrap()?;
148 assert!(iter.next().is_none());
151 _ => f(&iter.collect::<Result<SmallVec<[_; 8]>, _>>()?),
157 /// Flags that we track on types. These flags are propagated upwards
158 /// through the type during type construction, so that we can quickly check
159 /// whether the type has various kinds of types in it without recursing
160 /// over the type itself.
161 pub struct TypeFlags: u32 {
162 // Does this have parameters? Used to determine whether substitution is
164 /// Does this have `Param`?
165 const HAS_TY_PARAM = 1 << 0;
166 /// Does this have `ReEarlyBound`?
167 const HAS_RE_PARAM = 1 << 1;
168 /// Does this have `ConstKind::Param`?
169 const HAS_CT_PARAM = 1 << 2;
171 const NEEDS_SUBST = TypeFlags::HAS_TY_PARAM.bits
172 | TypeFlags::HAS_RE_PARAM.bits
173 | TypeFlags::HAS_CT_PARAM.bits;
175 /// Does this have `Infer`?
176 const HAS_TY_INFER = 1 << 3;
177 /// Does this have `ReVar`?
178 const HAS_RE_INFER = 1 << 4;
179 /// Does this have `ConstKind::Infer`?
180 const HAS_CT_INFER = 1 << 5;
182 /// Does this have inference variables? Used to determine whether
183 /// inference is required.
184 const NEEDS_INFER = TypeFlags::HAS_TY_INFER.bits
185 | TypeFlags::HAS_RE_INFER.bits
186 | TypeFlags::HAS_CT_INFER.bits;
188 /// Does this have `Placeholder`?
189 const HAS_TY_PLACEHOLDER = 1 << 6;
190 /// Does this have `RePlaceholder`?
191 const HAS_RE_PLACEHOLDER = 1 << 7;
192 /// Does this have `ConstKind::Placeholder`?
193 const HAS_CT_PLACEHOLDER = 1 << 8;
195 /// `true` if there are "names" of regions and so forth
196 /// that are local to a particular fn/inferctxt
197 const HAS_FREE_LOCAL_REGIONS = 1 << 9;
199 /// `true` if there are "names" of types and regions and so forth
200 /// that are local to a particular fn
201 const HAS_FREE_LOCAL_NAMES = TypeFlags::HAS_TY_PARAM.bits
202 | TypeFlags::HAS_CT_PARAM.bits
203 | TypeFlags::HAS_TY_INFER.bits
204 | TypeFlags::HAS_CT_INFER.bits
205 | TypeFlags::HAS_TY_PLACEHOLDER.bits
206 | TypeFlags::HAS_CT_PLACEHOLDER.bits
207 // The `evaluate_obligation` query does not return further
208 // obligations. If it evaluates an obligation with an opaque
209 // type, that opaque type may get compared to another type,
210 // constraining it. We would lose this information.
211 // FIXME: differentiate between crate-local opaque types
212 // and opaque types from other crates, as only opaque types
213 // from the local crate can possibly be a local name
214 | TypeFlags::HAS_TY_OPAQUE.bits
215 // We consider 'freshened' types and constants
216 // to depend on a particular fn.
217 // The freshening process throws away information,
218 // which can make things unsuitable for use in a global
219 // cache. Note that there is no 'fresh lifetime' flag -
220 // freshening replaces all lifetimes with `ReErased`,
221 // which is different from how types/const are freshened.
222 | TypeFlags::HAS_TY_FRESH.bits
223 | TypeFlags::HAS_CT_FRESH.bits
224 | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits;
226 /// Does this have `Projection`?
227 const HAS_TY_PROJECTION = 1 << 10;
228 /// Does this have `Opaque`?
229 const HAS_TY_OPAQUE = 1 << 11;
230 /// Does this have `ConstKind::Unevaluated`?
231 const HAS_CT_PROJECTION = 1 << 12;
233 /// Could this type be normalized further?
234 const HAS_PROJECTION = TypeFlags::HAS_TY_PROJECTION.bits
235 | TypeFlags::HAS_TY_OPAQUE.bits
236 | TypeFlags::HAS_CT_PROJECTION.bits;
238 /// Is an error type/const reachable?
239 const HAS_ERROR = 1 << 13;
241 /// Does this have any region that "appears free" in the type?
242 /// Basically anything but `ReLateBound` and `ReErased`.
243 const HAS_FREE_REGIONS = 1 << 14;
245 /// Does this have any `ReLateBound` regions? Used to check
246 /// if a global bound is safe to evaluate.
247 const HAS_RE_LATE_BOUND = 1 << 15;
249 /// Does this have any `ReErased` regions?
250 const HAS_RE_ERASED = 1 << 16;
252 /// Does this value have parameters/placeholders/inference variables which could be
253 /// replaced later, in a way that would change the results of `impl` specialization?
254 const STILL_FURTHER_SPECIALIZABLE = 1 << 17;
256 /// Does this value have `InferTy::FreshTy/FreshIntTy/FreshFloatTy`?
257 const HAS_TY_FRESH = 1 << 18;
259 /// Does this value have `InferConst::Fresh`?
260 const HAS_CT_FRESH = 1 << 19;
264 rustc_index::newtype_index! {
265 /// A [De Bruijn index][dbi] is a standard means of representing
266 /// regions (and perhaps later types) in a higher-ranked setting. In
267 /// particular, imagine a type like this:
268 /// ```ignore (illustrative)
269 /// for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
272 /// // | +------------+ 0 | |
274 /// // +----------------------------------+ 1 |
276 /// // +----------------------------------------------+ 0
278 /// In this type, there are two binders (the outer fn and the inner
279 /// fn). We need to be able to determine, for any given region, which
280 /// fn type it is bound by, the inner or the outer one. There are
281 /// various ways you can do this, but a De Bruijn index is one of the
282 /// more convenient and has some nice properties. The basic idea is to
283 /// count the number of binders, inside out. Some examples should help
284 /// clarify what I mean.
286 /// Let's start with the reference type `&'b isize` that is the first
287 /// argument to the inner function. This region `'b` is assigned a De
288 /// Bruijn index of 0, meaning "the innermost binder" (in this case, a
289 /// fn). The region `'a` that appears in the second argument type (`&'a
290 /// isize`) would then be assigned a De Bruijn index of 1, meaning "the
291 /// second-innermost binder". (These indices are written on the arrows
294 /// What is interesting is that De Bruijn index attached to a particular
295 /// variable will vary depending on where it appears. For example,
296 /// the final type `&'a char` also refers to the region `'a` declared on
297 /// the outermost fn. But this time, this reference is not nested within
298 /// any other binders (i.e., it is not an argument to the inner fn, but
299 /// rather the outer one). Therefore, in this case, it is assigned a
300 /// De Bruijn index of 0, because the innermost binder in that location
303 /// [dbi]: https://en.wikipedia.org/wiki/De_Bruijn_index
304 pub struct DebruijnIndex {
305 DEBUG_FORMAT = "DebruijnIndex({})",
311 /// Returns the resulting index when this value is moved into
312 /// `amount` number of new binders. So, e.g., if you had
314 /// for<'a> fn(&'a x)
316 /// and you wanted to change it to
318 /// for<'a> fn(for<'b> fn(&'a x))
320 /// you would need to shift the index for `'a` into a new binder.
322 pub fn shifted_in(self, amount: u32) -> DebruijnIndex {
323 DebruijnIndex::from_u32(self.as_u32() + amount)
326 /// Update this index in place by shifting it "in" through
327 /// `amount` number of binders.
328 pub fn shift_in(&mut self, amount: u32) {
329 *self = self.shifted_in(amount);
332 /// Returns the resulting index when this value is moved out from
333 /// `amount` number of new binders.
335 pub fn shifted_out(self, amount: u32) -> DebruijnIndex {
336 DebruijnIndex::from_u32(self.as_u32() - amount)
339 /// Update in place by shifting out from `amount` binders.
340 pub fn shift_out(&mut self, amount: u32) {
341 *self = self.shifted_out(amount);
344 /// Adjusts any De Bruijn indices so as to make `to_binder` the
345 /// innermost binder. That is, if we have something bound at `to_binder`,
346 /// it will now be bound at INNERMOST. This is an appropriate thing to do
347 /// when moving a region out from inside binders:
349 /// ```ignore (illustrative)
350 /// for<'a> fn(for<'b> for<'c> fn(&'a u32), _)
351 /// // Binder: D3 D2 D1 ^^
354 /// Here, the region `'a` would have the De Bruijn index D3,
355 /// because it is the bound 3 binders out. However, if we wanted
356 /// to refer to that region `'a` in the second argument (the `_`),
357 /// those two binders would not be in scope. In that case, we
358 /// might invoke `shift_out_to_binder(D3)`. This would adjust the
359 /// De Bruijn index of `'a` to D1 (the innermost binder).
361 /// If we invoke `shift_out_to_binder` and the region is in fact
362 /// bound by one of the binders we are shifting out of, that is an
363 /// error (and should fail an assertion failure).
364 pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self {
365 self.shifted_out(to_binder.as_u32() - INNERMOST.as_u32())
369 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
370 #[derive(Encodable, Decodable)]
381 pub fn name_str(&self) -> &'static str {
383 IntTy::Isize => "isize",
388 IntTy::I128 => "i128",
392 pub fn bit_width(&self) -> Option<u64> {
394 IntTy::Isize => return None,
403 pub fn normalize(&self, target_width: u32) -> Self {
405 IntTy::Isize => match target_width {
416 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Debug)]
417 #[derive(Encodable, Decodable)]
428 pub fn name_str(&self) -> &'static str {
430 UintTy::Usize => "usize",
432 UintTy::U16 => "u16",
433 UintTy::U32 => "u32",
434 UintTy::U64 => "u64",
435 UintTy::U128 => "u128",
439 pub fn bit_width(&self) -> Option<u64> {
441 UintTy::Usize => return None,
450 pub fn normalize(&self, target_width: u32) -> Self {
452 UintTy::Usize => match target_width {
463 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
464 #[derive(Encodable, Decodable)]
471 pub fn name_str(self) -> &'static str {
473 FloatTy::F32 => "f32",
474 FloatTy::F64 => "f64",
478 pub fn bit_width(self) -> u64 {
486 #[derive(Clone, Copy, PartialEq, Eq)]
487 pub enum IntVarValue {
492 #[derive(Clone, Copy, PartialEq, Eq)]
493 pub struct FloatVarValue(pub FloatTy);
495 rustc_index::newtype_index! {
496 /// A **ty**pe **v**ariable **ID**.
498 DEBUG_FORMAT = "_#{}t"
502 /// An **int**egral (`u32`, `i32`, `usize`, etc.) type **v**ariable **ID**.
503 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
508 /// An **float**ing-point (`f32` or `f64`) type **v**ariable **ID**.
509 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
510 pub struct FloatVid {
514 /// A placeholder for a type that hasn't been inferred yet.
516 /// E.g., if we have an empty array (`[]`), then we create a fresh
517 /// type variable for the element type since we won't know until it's
518 /// used what the element type is supposed to be.
519 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
523 /// An integral type variable (`{integer}`).
525 /// These are created when the compiler sees an integer literal like
526 /// `1` that could be several different types (`u8`, `i32`, `u32`, etc.).
527 /// We don't know until it's used what type it's supposed to be, so
528 /// we create a fresh type variable.
530 /// A floating-point type variable (`{float}`).
532 /// These are created when the compiler sees an float literal like
533 /// `1.0` that could be either an `f32` or an `f64`.
534 /// We don't know until it's used what type it's supposed to be, so
535 /// we create a fresh type variable.
538 /// A [`FreshTy`][Self::FreshTy] is one that is generated as a replacement
539 /// for an unbound type variable. This is convenient for caching etc. See
540 /// `rustc_infer::infer::freshen` for more details.
542 /// Compare with [`TyVar`][Self::TyVar].
544 /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`IntVar`][Self::IntVar].
546 /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`FloatVar`][Self::FloatVar].
550 /// Raw `TyVid` are used as the unification key for `sub_relations`;
551 /// they carry no values.
552 impl UnifyKey for TyVid {
555 fn index(&self) -> u32 {
559 fn from_index(i: u32) -> TyVid {
562 fn tag() -> &'static str {
567 impl EqUnifyValue for IntVarValue {}
569 impl UnifyKey for IntVid {
570 type Value = Option<IntVarValue>;
571 #[inline] // make this function eligible for inlining - it is quite hot.
572 fn index(&self) -> u32 {
576 fn from_index(i: u32) -> IntVid {
579 fn tag() -> &'static str {
584 impl EqUnifyValue for FloatVarValue {}
586 impl UnifyKey for FloatVid {
587 type Value = Option<FloatVarValue>;
589 fn index(&self) -> u32 {
593 fn from_index(i: u32) -> FloatVid {
594 FloatVid { index: i }
596 fn tag() -> &'static str {
601 #[derive(Copy, Clone, PartialEq, Decodable, Encodable, Hash)]
603 Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type
604 Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
605 Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
606 Bivariant, // T<A> <: T<B> -- e.g., unused type parameter
610 /// `a.xform(b)` combines the variance of a context with the
611 /// variance of a type with the following meaning. If we are in a
612 /// context with variance `a`, and we encounter a type argument in
613 /// a position with variance `b`, then `a.xform(b)` is the new
614 /// variance with which the argument appears.
617 /// ```ignore (illustrative)
620 /// Here, the "ambient" variance starts as covariant. `*mut T` is
621 /// invariant with respect to `T`, so the variance in which the
622 /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which
623 /// yields `Invariant`. Now, the type `Vec<T>` is covariant with
624 /// respect to its type argument `T`, and hence the variance of
625 /// the `i32` here is `Invariant.xform(Covariant)`, which results
626 /// (again) in `Invariant`.
629 /// ```ignore (illustrative)
630 /// fn(*const Vec<i32>, *mut Vec<i32)
632 /// The ambient variance is covariant. A `fn` type is
633 /// contravariant with respect to its parameters, so the variance
634 /// within which both pointer types appear is
635 /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const
636 /// T` is covariant with respect to `T`, so the variance within
637 /// which the first `Vec<i32>` appears is
638 /// `Contravariant.xform(Covariant)` or `Contravariant`. The same
639 /// is true for its `i32` argument. In the `*mut T` case, the
640 /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`,
641 /// and hence the outermost type is `Invariant` with respect to
642 /// `Vec<i32>` (and its `i32` argument).
644 /// Source: Figure 1 of "Taming the Wildcards:
645 /// Combining Definition- and Use-Site Variance" published in PLDI'11.
646 pub fn xform(self, v: Variance) -> Variance {
648 // Figure 1, column 1.
649 (Variance::Covariant, Variance::Covariant) => Variance::Covariant,
650 (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant,
651 (Variance::Covariant, Variance::Invariant) => Variance::Invariant,
652 (Variance::Covariant, Variance::Bivariant) => Variance::Bivariant,
654 // Figure 1, column 2.
655 (Variance::Contravariant, Variance::Covariant) => Variance::Contravariant,
656 (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant,
657 (Variance::Contravariant, Variance::Invariant) => Variance::Invariant,
658 (Variance::Contravariant, Variance::Bivariant) => Variance::Bivariant,
660 // Figure 1, column 3.
661 (Variance::Invariant, _) => Variance::Invariant,
663 // Figure 1, column 4.
664 (Variance::Bivariant, _) => Variance::Bivariant,
669 impl<CTX> HashStable<CTX> for DebruijnIndex {
670 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
671 self.as_u32().hash_stable(ctx, hasher);
675 impl<CTX> HashStable<CTX> for IntTy {
676 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
677 discriminant(self).hash_stable(ctx, hasher);
681 impl<CTX> HashStable<CTX> for UintTy {
682 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
683 discriminant(self).hash_stable(ctx, hasher);
687 impl<CTX> HashStable<CTX> for FloatTy {
688 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
689 discriminant(self).hash_stable(ctx, hasher);
693 impl<CTX> HashStable<CTX> for InferTy {
694 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
696 discriminant(self).hash_stable(ctx, hasher);
698 TyVar(v) => v.as_u32().hash_stable(ctx, hasher),
699 IntVar(v) => v.index.hash_stable(ctx, hasher),
700 FloatVar(v) => v.index.hash_stable(ctx, hasher),
701 FreshTy(v) | FreshIntTy(v) | FreshFloatTy(v) => v.hash_stable(ctx, hasher),
706 impl<CTX> HashStable<CTX> for Variance {
707 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
708 discriminant(self).hash_stable(ctx, hasher);
712 impl fmt::Debug for IntVarValue {
713 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
715 IntVarValue::IntType(ref v) => v.fmt(f),
716 IntVarValue::UintType(ref v) => v.fmt(f),
721 impl fmt::Debug for FloatVarValue {
722 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
727 impl fmt::Debug for IntVid {
728 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
729 write!(f, "_#{}i", self.index)
733 impl fmt::Debug for FloatVid {
734 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
735 write!(f, "_#{}f", self.index)
739 impl fmt::Debug for InferTy {
740 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
743 TyVar(ref v) => v.fmt(f),
744 IntVar(ref v) => v.fmt(f),
745 FloatVar(ref v) => v.fmt(f),
746 FreshTy(v) => write!(f, "FreshTy({:?})", v),
747 FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v),
748 FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v),
753 impl fmt::Debug for Variance {
754 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
755 f.write_str(match *self {
756 Variance::Covariant => "+",
757 Variance::Contravariant => "-",
758 Variance::Invariant => "o",
759 Variance::Bivariant => "*",
764 impl fmt::Display for InferTy {
765 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
768 TyVar(_) => write!(f, "_"),
769 IntVar(_) => write!(f, "{}", "{integer}"),
770 FloatVar(_) => write!(f, "{}", "{float}"),
771 FreshTy(v) => write!(f, "FreshTy({})", v),
772 FreshIntTy(v) => write!(f, "FreshIntTy({})", v),
773 FreshFloatTy(v) => write!(f, "FreshFloatTy({})", v),
778 rustc_index::newtype_index! {
779 /// "Universes" are used during type- and trait-checking in the
780 /// presence of `for<..>` binders to control what sets of names are
781 /// visible. Universes are arranged into a tree: the root universe
782 /// contains names that are always visible. Each child then adds a new
783 /// set of names that are visible, in addition to those of its parent.
784 /// We say that the child universe "extends" the parent universe with
787 /// To make this more concrete, consider this program:
789 /// ```ignore (illustrative)
791 /// fn bar<T>(x: T) {
792 /// let y: for<'a> fn(&'a u8, Foo) = ...;
796 /// The struct name `Foo` is in the root universe U0. But the type
797 /// parameter `T`, introduced on `bar`, is in an extended universe U1
798 /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside
799 /// of `bar`, we cannot name `T`. Then, within the type of `y`, the
800 /// region `'a` is in a universe U2 that extends U1, because we can
801 /// name it inside the fn type but not outside.
803 /// Universes are used to do type- and trait-checking around these
804 /// "forall" binders (also called **universal quantification**). The
805 /// idea is that when, in the body of `bar`, we refer to `T` as a
806 /// type, we aren't referring to any type in particular, but rather a
807 /// kind of "fresh" type that is distinct from all other types we have
808 /// actually declared. This is called a **placeholder** type, and we
809 /// use universes to talk about this. In other words, a type name in
810 /// universe 0 always corresponds to some "ground" type that the user
811 /// declared, but a type name in a non-zero universe is a placeholder
812 /// type -- an idealized representative of "types in general" that we
813 /// use for checking generic functions.
814 pub struct UniverseIndex {
815 DEBUG_FORMAT = "U{}",
820 pub const ROOT: UniverseIndex = UniverseIndex::from_u32(0);
822 /// Returns the "next" universe index in order -- this new index
823 /// is considered to extend all previous universes. This
824 /// corresponds to entering a `forall` quantifier. So, for
825 /// example, suppose we have this type in universe `U`:
827 /// ```ignore (illustrative)
828 /// for<'a> fn(&'a u32)
831 /// Once we "enter" into this `for<'a>` quantifier, we are in a
832 /// new universe that extends `U` -- in this new universe, we can
833 /// name the region `'a`, but that region was not nameable from
834 /// `U` because it was not in scope there.
835 pub fn next_universe(self) -> UniverseIndex {
836 UniverseIndex::from_u32(self.private.checked_add(1).unwrap())
839 /// Returns `true` if `self` can name a name from `other` -- in other words,
840 /// if the set of names in `self` is a superset of those in
841 /// `other` (`self >= other`).
842 pub fn can_name(self, other: UniverseIndex) -> bool {
843 self.private >= other.private
846 /// Returns `true` if `self` cannot name some names from `other` -- in other
847 /// words, if the set of names in `self` is a strict subset of
848 /// those in `other` (`self < other`).
849 pub fn cannot_name(self, other: UniverseIndex) -> bool {
850 self.private < other.private
854 impl<CTX> HashStable<CTX> for UniverseIndex {
855 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
856 self.private.hash_stable(ctx, hasher);